離散數(shù)學

前言

近年來，計算機科學與信息技術(shù)正在以驚人的速度迅猛發(fā)展，并且對人類社會的各個領(lǐng)域產(chǎn)生著日益廣泛和深遠的影響。離散數(shù)學，作為計算機科學與技術(shù)的重要理論基礎(chǔ)之一，也因此更加顯示出它的重要性。離散數(shù)學在計算機科學與技術(shù)中的地位如同微積分在物理學和工程技術(shù)中的地位一樣，離散數(shù)學為計算機科學與技術(shù)的發(fā)展奠定了重要的數(shù)學基礎(chǔ)。不僅離散數(shù)學的基本思想、概念和方法廣泛地滲透到計算機科學與技術(shù)的各個領(lǐng)域，而且其基本理論和研究成果更是全面而系統(tǒng)地影響和推動著這些領(lǐng)域的發(fā)展。例如，布爾代數(shù)為開關(guān)電路的研究提供了重要的分析工具，并且導致了數(shù)字邏輯理論的建立；自動機理論對形式語言及其編譯產(chǎn)生了重大的影響，并形成了完整而嚴密的理論體系；謂詞演算成為程序理論的一種重要研究工具；代數(shù)結(jié)構(gòu)為編碼理論的研究提供了新的途徑；圖靈機模型和遞歸函數(shù)理論構(gòu)成了可計算性理論研究的基礎(chǔ)。離散數(shù)學的這些重要成果和作用，使得它成為一個計算機科學工作者和工程師所必須具備的基本理論知識。對于計算機專業(yè)的學生來說，離散數(shù)學不僅是很多后續(xù)專業(yè)課程所必需的先修課，而且也為高等院校工科本科生提供了必要的抽象思維和嚴密推理的基本訓練。

內(nèi)容概要

　　《離散數(shù)學（修訂版）》由五篇構(gòu)成。第一篇數(shù)理邏輯，內(nèi)容包括：命題邏輯，謂詞邏輯，公理系統(tǒng)，歸結(jié)法原理。第二篇集合論，內(nèi)容包括：集合的基本概念及其運算，關(guān)系，函數(shù)，自然數(shù)和基數(shù)。第三篇圖論，內(nèi)容包括：基本概念，通路問題，圖的矩陣表示，樹，穿程問題，二分圖的匹配問題，平面圖及色數(shù)。第四篇代數(shù)系統(tǒng)，內(nèi)容包括：基本概念，半群和群，環(huán)和域，格和布爾代數(shù)，抽象數(shù)據(jù)類型的代數(shù)規(guī)范。第五篇有限自動機理論，內(nèi)容包括：基本概念，有限自動機的簡化，有限自動機和正則表達式，有限自動機的綜合與應(yīng)用?！　　峨x散數(shù)學（修訂版）》內(nèi)容系統(tǒng)、全面，概念清晰，敘述嚴謹精煉，推理詳盡嚴格，語言簡明易懂，各部分獨立成篇，并有大量例題和習題，便于讀者理解和掌握相關(guān)知識。《離散數(shù)學（修訂版）》可作為高等院校本科計算機專業(yè)離散數(shù)學課程的教材，也可供計算機科學與工程技術(shù)人員學習參考。

書籍目錄

第一篇 數(shù)理邏輯第一章 命題邏輯§1．1 命題和聯(lián)結(jié)詞§1．2 公式和真值賦值§1．3 等值演算§1．4 對偶定理§1．5 聯(lián)結(jié)詞的完全集§1．6 范式§1．7 邏輯推論習題第二章 謂詞邏輯§2．1 謂詞和量詞§2．2 項和公式§2．3 解釋和賦值§2．4 永真式§2．5 等值演算§2．6 邏輯推論習題二第三章 公理系統(tǒng)§3．1 命題邏輯的公理系統(tǒng)§3．2 謂詞邏輯的公理系統(tǒng)習題三第四章 歸結(jié)法原理§4．1 命題邏輯的歸結(jié)法§4．2 前束范式與斯科倫范式§4．3 謂詞邏輯的歸結(jié)法習題四參考文獻第二篇 集合論第五章 集合的基本概念及其運算§5．1 集合與元素§5．2 集合間的相等和包含關(guān)系§5．3 冪集§5．4 集合的運算§5．5 有窮集的計數(shù)原理§5．6 集合的歸納定義法§5．7 有序偶和笛卡兒乘積習題五第六章 關(guān)系§6．1 關(guān)系及其性質(zhì)§6．2 關(guān)系的運算§6．3 次序關(guān)系  §6．4 等價關(guān)系、劃分及其他習題六第七章 函數(shù)§7．1 基本概念§7．2 函數(shù)的復(fù)合§7．3 特殊性質(zhì)的函數(shù)§7．4 集合的特征函數(shù)習題七第八章 自然數(shù)和基數(shù)§8．1 自然數(shù)及數(shù)學歸納法§8．2 基數(shù)習題八 參考文獻第三篇 圖論第九章 基本概念§9．1 有向圖及無向圖  §9．2 圖的基本結(jié)構(gòu)§9．3 子圖  §9．4 連通性  §9．5 頂點基和強分圖習題九第十章 通路問題§10．1 最短通路§10．2 關(guān)鍵通路習題十第十一章 圖的矩陣表示§11．1 鄰接矩陣§11．2 有向圖的可達性矩陣§11．3 關(guān)聯(lián)矩陣習題十第十二章 樹§12．1 樹的一般定義§12．2 根樹與有序樹§12．3 二元樹§12．4 生成樹§12．5 割集習題十二第十三章 穿程問題§13．1 歐拉圖§13．2 哈密頓圖習題十三第十四章 二分圖的匹配問題§14．1 基本概念§14．2 二分圖的最大匹配§14．3 從x到y(tǒng)的匹配習題十四第十五章 平面圖及色數(shù)§15．1 平面圖§15．2 色數(shù)習題十五參考文獻 第四篇 代數(shù)系統(tǒng)第十六章基本概念§16．1 代數(shù)系統(tǒng)§16．2 同態(tài)和同構(gòu)§16．3 子代數(shù)和商代數(shù)習題十六第十七章 半群和群§17．1 半群的概念§17．2 子半群和半群同態(tài)§17．3 商半群和半群直積§17．4 群的概念§17．5 子群和群的同態(tài)§17．6 變換群、置換群和循環(huán)群§17．7 不變子群和商群習題十七第十八章 環(huán)和域§18．1 環(huán)和域的概念§18．2 子環(huán)和環(huán)的同態(tài)§18．3 理想和商環(huán)習題十八第十九章 格和布爾代數(shù)§19．1 格的定義與基本性質(zhì)§19．2 子格和格的同態(tài)§19．3 布爾代數(shù)§19．4 布爾代數(shù)的表示習題十九第二十章 抽象數(shù)據(jù)類型的代數(shù)規(guī)范§20．1 標記、項和代數(shù)規(guī)范§20．2 ∑-代數(shù)和范疇§20．3 代數(shù)規(guī)范的初始語義習題二十參考文獻第五篇 有限自動機理論第二十一章 基本概念§21．1 字符表、字符串及其集合的運算§21．2 有限自動機的定義§21．3 有限自動機的等價§21．4 Mealy機與Moore機習題二十第二十二章 有限自動機的簡化§22．1 最小有限自動機的定義及性質(zhì)§22．2 狀態(tài)集的S劃分和格LM§22．3 有限自動機的最小化習題二十二第二十三章 有限自動機和正則表達式§23．1 有限自動機的識別功能§23．2 非確定有限自動機§23．3 正則表達式§23．4 由正則表達式構(gòu)造FA的算法§23．5 有限自動機和正則表達式的等價性§23．6 正則集合及其性質(zhì)習題二十三第二十四章 有限自動機的綜合與應(yīng)用§24．1 有限自動機的綜合§24．2 FA理論在算法設(shè)計中的應(yīng)用§24．3 FA理論與形式語言理論的關(guān)系習題二十四參考文獻名詞索引

章節(jié)摘錄

插圖：邏輯學是研究推理的科學，具有十分悠久的歷史，在兩千多年前的古希臘時代就已很發(fā)達。數(shù)理邏輯是數(shù)學化的邏輯學，是用數(shù)學方法研究推理的科學，其歷史只有三百多年。德國數(shù)學家、哲學家萊布尼茨（Leibniz）于17世紀中葉明確地提出了建立通用的符號語言和通用代數(shù)的思想[1]。他指出，如果我們能對人類的全部思想進行綜合分析，并把它們化歸成最簡單的概念，那么，只要再進一步設(shè)計出適當?shù)姆杹肀硎具@些基本概念及其組合關(guān)系，就可以獲得一種既簡單又嚴密的符號語言。由于這種語言克服了自然語言的弊病及局限性（如不規(guī)則性、歧義性等），因此，它是一種理想的、世界性的公共語言，即所謂的“通用語言”。其次，通用語言的建立不僅有益于思想的交流，而且也有益于思維。由于在通用語言中實現(xiàn)了徹底的符號化，其中的推理過程就表現(xiàn)為符號序列的變形，從而只要對此做出明確的規(guī)定，就可以按照這些規(guī)定機械地實行推理，正如人們在代數(shù)運算中按照明確的法則對代數(shù)式進行演算一樣。我們最終所獲得的就不僅是一種“通用語言”，而且也是一種“通用代數(shù)”。在這種符號語言中，思維被“演算化”了。萊布尼茨只是進行了一些初步的嘗試，并沒有能夠?qū)崿F(xiàn)他的關(guān)于通用符號語言和通用代數(shù)的設(shè)想，但是數(shù)理邏輯卻是沿著他的設(shè)想發(fā)展起來的。因此，人們公認萊布尼茨為數(shù)理邏輯的創(chuàng)始人。布爾（Boole）構(gòu)造了一個抽象的代數(shù)系統(tǒng)，并且給予它多種解釋，如類的演算、命題演算、概率演算。當然，布爾所提出的演算很不成熟，某些演算公式?jīng)]有邏輯解釋。但是，布爾的貢獻在于，他在邏輯史上首先提出了一個邏輯演算，實現(xiàn)了萊布尼茨的一部分設(shè)想。經(jīng)過許多數(shù)學家的改進，今天的布爾代數(shù)已發(fā)展成為具有廣泛應(yīng)用的豐富的代數(shù)理論。

編輯推薦

《離散數(shù)學(修訂版)》為高等學校教材之一，由高等教育出版社出版。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    離散數(shù)學 PDF格式下載

---