離散數學（微課版）（第2版）

王慶先 王慶先 電子科技大學信息與軟件工程學院教授/博士生導師，電子科技大學計算機應用技術專業博士，先後到美國明尼蘇達大學大學、美國羅切斯特大學交流訪問。長期從事《離散數學》，《組合數學》，《算法分析與設計》課程的教學。目前主要從事人工智能、大數據應用等方面的研究，在Neurocomputing，Physicas等高水平刊物和國際會議上發表學術論文數十篇，主持和參與多項國家級項目、省部級項目和企業橫向合作項目。 至2004年以來，長期從事離散數學課程的教學研究，融合科研成果，利用現代信息技術探索新的教學方法和教學模式，取得了較好的教學研究成果。主持教育部產學研協同育人項目《離散數學在線學習系統》（項目編號：201802111012,2018-2020）1項，作為第二負責人完成教育部《離散數學》精品資源共享課程建設項目（2012-2013），參與完成（排名第二）《離散數學》MOOC建設》（項目編號：201701049023,2017-2019），參與完成（排名第三）教育部《離散數學》國家雙語示範課程建設（2008-2012），參與完成（排名第二）《離散數學》省級教學團隊項目（2009-2013），參與完成（排名第三）國家級精品課程《離散數學》建設項目（2006-2010），參與編寫（工作量1/4）國家“十一五”規劃教材《離散數學及應用（2019年第3版，2013年第2版，2007年第1版）》，撰寫的教研論文“離散數學課堂簽到研究與實踐”，“離散數學實時判卷系統”在《大學數學》期刊上發表；自主研發的“離散數學學習系統”目前已在所教學班級試用，取得了較好的效果。

第 1 章 集合論

歷史人物

本章思維導圖

1.1　集合的基本概念

1.1.1　集合的表示

1.1.2　集合與集合的關系

1.2　幾個特殊集合

1.3　集合的運算

1.4　無限集

1.4.1　可數集

1.4.2　不可數集

1.5　集合的應用

1.5.1　集合的計算機表示

1.5.2　計數問題

1.6　習題

第　2 章 命題邏輯

歷史人物

本章思維導圖

2.1　命題與命題聯結詞

2.1.1　命題

2.1.2　命題聯結詞

2.1.3　自然語言的命題符號化

2.2　命題公式、解釋與真值表

2.2.1　命題公式

2.2.2　命題公式的解釋與真值表

2.2.3　命題公式的基本等價定律

2.3　公式的標準型——範式

2.3.1　命題聯結詞的完備集

2.3.2　析取範式和合取範式

2.3.3　主合取範式和主析取範式

2.4　命題邏輯的推理理論

2.4.1　推理的基本概念

2.4.2　推理有效性的判別方法

2.5　命題邏輯的應用

2.5.1　命題聯結詞的應用

2.5.2　命題公式的應用

2.5.3　範式的應用

2.5.4　命題邏輯推理的應用

2.6　習題

第　3 章 謂詞邏輯

歷史人物

本章思維導圖

3.1　自然語言的謂詞符號化

3.1.1　謂詞

3.1.2　量詞

3.2　謂詞公式與解釋

3.2.1　謂詞公式

3.2.2　自由變元和約束變元

3.2.3　謂詞公式的解釋

3.2.4　謂詞公式的基本等價定律

3.3　謂詞公式的標準型——前束範式*

3.3.1　前束範式

3.3.2　Skolem 範式

3.4　謂詞邏輯的推理理論

3.4.1　推理規則與推理定律

3.4.2　推理有效性的判別方法

3.5　謂詞邏輯的應用

3.5.1　謂詞符號化的應用

3.5.2　謂詞邏輯推理的應用

3.6　習題

第　4 章 二元關系

歷史人物

本章思維導圖

4.1　二元關系及其表示

4.1.1　序偶和笛卡兒積

4.1.2　關系的定義

4.1.3　關系的表示法

4.2　關系的運算

4.2.1　關系的復合運算

4.2.2　關系的逆運算

4.2.3　關系的冪運算

4.3　關系的性質

4.3.1　關系性質的定義

4.3.2　關系性質的判定定理

4.3.3　關系性質的保守性

4.4　關系的閉包

4.5　關系的應用

4.5.1　二元關系及表示的應用

4.5.2　關系運算的應用

4.6　習題

第　5 章 特殊關系

歷史人物

本章思維導圖

5.1　相容關系

5.1.1　相容關系的定義

5.1.2　集合的覆蓋

5.2　等價關系

5.2.1　等價關系的定義

5.2.2　集合的劃分

5.2.3　等價類與商集

5.2.4　等價關系與劃分

5.3　次序關系

5.3.1　擬序關系

5.3.2　偏序關系

5.3.3　全序關系

5.3.4　良序關系

5.4　函數

5.4.1　函數的基本概念

5.4.2　函數的運算

5.4.3　置換函數

5.5　特殊關系的應用

5.5.1　等價關系的應用

5.5.2　次序關系的應用

5.5.3　函數的應用

5.5.4　置換函數的應用

5.6　習題

第　6 章 圖

歷史人物

本章思維導圖

6.1　圖的基本概念

6.1.1　圖的定義

6.1.2　圖的表示

6.1.3　圖的操作

6.1.4　鄰接點與鄰接邊

6.1.4　圖的分類

6.1.5　子圖與補圖

6.2　握手定理

6.3　圖的同構

6.4　通路與回路

6.4.1　通路與回路

6.4.2　無向賦權圖的最短通路

6.5　圖的連通性

6.5.1　無向圖的連通性

6.5.2　有向圖的連通性

6.6　圖的應用

6.6.1　網絡的結構

6.6.2　渡河問題

6.6.3　均分問題

6.7　習題

第　7 章 特殊圖

歷史人物

思維導圖

7.1　樹

7.1.1　樹的基本概念及性質

7.1.2　生成樹及算法

7.2　根樹

7.1.3　根樹的定義與分類

7.1.4　根樹的遍歷

7.1.5　最優樹與哈夫曼算法

7.2　歐拉圖

7.2.1　歐拉圖的引入與定義

7.2.2　歐拉圖的判定

7.3　哈密頓圖

7.3.1　哈密頓圖的引入與定義

7.3.2　哈密頓圖的判定

7.4　偶圖

7.4.1　偶圖的定義

7.4.2　偶圖的判定

7.4.3　匹配

7.5　平面圖

7.5.1　平面圖的定義

7.5.2　平面圖的簡單判定方法——觀察法

7.5.3　歐拉公式

7.5.4　庫拉托夫斯基定理

7.6　特殊圖的應用

7.6.1　無向樹的應用

7.6.2　根樹的應用

7.6.3　歐拉圖的應用

7.6.4　哈密頓圖的應用

7.6.5　偶圖的應用

7.6.6　平面圖的應用

7.7　習題

第　8 章 代數系統

歷史人物

本章思維導圖

8.1　代數系統

8.1.1　代數運算

8.1.2　代數系統與子代數

8.2　運算律和特殊元

8.2.1　二元運算律

8.2.2　二元運算的特殊元

8.3　同態與同構

8.3.1　同態與同構的定義

8.3.2　同態的性質

8.4　代數系統的應用

8.4.1　代數系統的計算機表示

8.4.2　數據庫與關系代數

8.5　習題

第　9 章 群 環 域

歷史人物

本章思維導圖

9.1　群的基本概念

9.1.1　群的定義

9.1.2　元素的階

9.1.3　子群

9.1.4　群的同態和同構

9.2　特殊群

9.2.1　循環群

9.2.2　置換群

9.3　陪集與拉格朗日定理

9.3.1　陪集

9.3.2　拉格朗日定理

9.4　正規子群與商群

9.4.1　正規子群

9.4.2　商群

9.5　環和域

9.5.1　環和域的定義

9.5.2　子環、理想和商環

9.5.3　環的同態和同構

9.6　群環域的應用

9.6.1　計數問題

9.6.2　多項式編碼

9.7　習題

第　10 章 格與布爾代數

歷史人物

思維導圖

10.1　格的定義和性質

10.1.1　格的定義

10.1.2　格的性質

10.2　子格與格同態

10.2.1　子格和理想

10.2.2　格同態

10.3　特殊格

10.3.1　分配格與模格

10.3.2　有界格與有補格

10.4　布爾代數

10.5　格與布爾代數的應用

10.5.1　格與樹形圖結構

10.5.2　布爾函數及其表示

10.6　習題