強化基本概念的理解，注重基本理論的證明方法。重點突出，加強理論與實際的聯系。

理論體系完整、科學嚴謹，內容敘述深入淺出、簡明扼要，概念盡量用例子加以說明。

書中配有典型例題和習題供學生練習，并提供章后習題答案供教師和學生使用和參考。

第二版前言

《離散數學》第一版經過了八年多的使用，收到很多院校教師和學生的反饋，包含了對本書的認可和一些中肯的意見。第二版在保留第一版的全部優點和特色基礎上，作了全面修訂、優化和補充，包括：

（1）訂正了原書中的錯誤，對全部章節進行了修訂，修改了書中發現的所有錯誤。

（2）補充了部分內容，如最優二叉樹的構建、哈夫曼編碼等。

（3）解決了反映比較強烈的章后習題答案問題，對每章后的習題進行詳細解答，并附加在書后，有助于教師和學生的使用和參考。

（4）可讀性和易讀性進一步提高，對全書進行通讀，字斟句酌、反復推敲，盡可能使句子通俗易懂。

本書由賈振華主編，楊麗娟、孫紅艷任副主編。各章主要編寫分工如下：第二版第一部分第1章、第2章修訂工作及課后習題參考解答由賈振華完成，第三部分第7章、第8章、第9章修訂工作及課后習題參考解答由賈振華和邯鄲工程高級技工學校張志偉共同完成，第二部分第3章到第6章修訂工作及課后習題參考解答由楊麗娟完成，第四部分第10章、第11章修訂工作及課后習題參考解答由孫紅艷完成，李新榮、黃中升、崔玉寶、李瑛、郭輝、趙輝、李杰、王興會等參加了部分習題的解答和校對工作。

由于作者水平有限，難免出現錯誤和安排不妥之處，敬請廣大師生不吝指正。Email：[email protected]。

編 者

2016年5月

第二版前言
第一版前言
第一部分 數理邏輯
第1章 命題邏輯 2
本章學習目標 2
1.1 命題和命題聯結詞 2
1.1.1 命題 2
1.1.2 命題聯結詞 4
1.2 命題公式與解釋 8
1.2.1 命題公式 8
1.2.2 命題公式的解釋 10
1.3 真值表與等價公式 11
1.3.1 真值表 11
1.3.2 命題公式的分類 13
1.3.3 等價公式 15
1.3.4 代入規則和替換規則 18
1.4 對偶定理 23
1.5 范式 25
1.5.1 合取范式和析取范式 25
1.5.2 主析取范式和主合取范式 27
1.6 公式的蘊涵 33
1.6.1 蘊涵的概念 33
1.6.2 蘊涵式的證明方法 34
1.6.3 基本蘊涵式 35
1.7 其他聯結詞與最小聯結詞組 36
1.7.1 其他聯結詞 36
1.7.2 最小聯結詞組 39
1.8 命題邏輯推理理論 40
1.8.1 命題邏輯推理理論 40
1.8.2 推理規則 42
1.8.3 判斷有效結論的常用方法 44
本章小結 48
習題1 48
第2章 謂詞邏輯 52
本章學習目標 52
2.1 謂詞邏輯命題的符號化 52
2.1.1 個體詞與謂詞 53
2.1.2 量詞 54
2.1.3 謂詞邏輯中命題的符號化 55
2.2 謂詞邏輯公式與解釋 57
2.2.1 謂詞邏輯的合式公式 57
2.2.2 謂詞的約束和替換 59
2.2.3 謂詞邏輯公式的解釋 61
2.3 謂詞邏輯公式的等價與蘊涵 63
2.3.1 謂詞邏輯的等價公式 63
2.3.2 謂詞邏輯的蘊涵公式 67
2.3.3 多個量詞的使用 68
2.4 前束范式 69
2.5 謂詞邏輯的推理理論 71
本章小結 76
習題2 76
第二部分 集合論
第3章 集合 81
本章學習目標 81
3.1 集合的概念與表示 81
3.1.1 集合的基本概念 81
3.1.2 集合的表示 82
3.1.3 集合之間的關系 83
3.2 集合的運算 86
3.2.1 集合的交運算 86
3.2.2 集合的并運算 87
3.2.3 集合的補 88
3.2.4 集合的對稱差 90
3.3 包含排斥原理 91
本章小結 94
習題3 94
第4章 關系 98
本章學習目標 98
4.1 序偶與笛卡爾積 98
4.1.1 有序n元組 98
4.1.2 笛卡爾積的概念 99
4.1.3 笛卡爾積的性質 100
4.2 二元關系及其表示 102
4.2.1 二元關系的概念 102
4.2.2 二元關系的表示 103
4.3 關系的運算 105
4.3.1 關系的交、并、差、補運算 105
4.3.2 關系的復合運算 106
4.3.3 關系的逆運算 110
4.4 關系的性質 112
4.4.1 自反性和反自反性 112
4.4.2 對稱性和反對稱性 112
4.4.3 傳遞性 113
4.4.4 關系性質的判定 113
4.5 關系的閉包 120
4.6 等價關系與集合的劃分 125
4.6.1 等價關系 125
4.6.2 等價類 126
4.6.3 集合的劃分 127
4.7 相容關系 130
4.7.1 相容關系 130
4.7.2 覆蓋 132
4.8 偏序關系 134
4.8.1 偏序關系 134
4.8.2 哈斯圖 135
4.8.3 全序關系 137
4.8.4 良序關系 139
本章小結 140
習題4 140
第5章 函數 144
本章學習目標 144
5.1 函數的概念 144
5.2 函數的性質 146
5.3 復合函數和逆函數 149
5.3.1 復合函數 149
5.3.2 逆函數 151
5.4 置換 152
本章小結 154
習題5 154
第6章 集合的基數 156
本章學習目標 156
6.1 基數的概念 156
6.2 可數集和不可數集 158
6.2.1 可數集 158
6.2.2 不可數集 160
6.3 基數的比較 161
本章小結 163
習題6 164
第三部分 圖論
第7章 圖 166
本章學習目標 166
7.1 圖的基本概念 166
7.1.1 圖論的發展 166
7.1.2 圖的基本概念 167
7.2 通路與回路 175
7.3 圖的連通性 176
7.3.1 無向圖的連通性 176
7.3.2 有向圖的連通性 179
7.4 圖的矩陣表示 183
7.4.1 圖的鄰接矩陣 183
7.4.2 圖的關聯矩陣 185
7.4.3 有向圖的可達矩陣 188
7.5 圖的應用 190
7.5.1 帶權圖的最短通路 190
7.5.2 帶權圖的關鍵路徑 193
本章小結 196
習題7 196
第8章 歐拉圖與哈密爾頓圖 200
本章學習目標 200
8.1 歐拉圖 200
8.1.1 歐拉圖的定義 200
8.1.2 歐拉圖的判定 201
8.1.3 求歐拉回路的算法 203
8.1.4 歐拉圖的應用 204
8.2 哈密爾頓圖 205
8.2.1 哈密爾頓圖 205
8.2.2 哈密爾頓圖的判定 206
本章小結 207
習題8 208
第9章 特殊圖 210
本章學習目標 210
9.1 樹 210
9.1.1 無向樹 210
9.1.2 生成樹與最小生成樹 213
9.1.3 有向樹與根樹 214
9.1.4 最優二叉樹及其應用 219
9.2 二部圖 222
9.3 平面圖 225
9.3.1 平面圖的定義 225
9.3.2 歐拉公式 226
9.3.3 庫拉托夫斯基定理 229
9.3.4 平面圖的對偶圖 230
本章小結 232
習題9 232
第四部分 代數系統
第10章 代數結構 236
本章學習目標 236
10.1 二元運算及其性質 236
10.1.1 二元運算 236
10.1.2 二元運算的性質 238
10.2 代數系統 242
10.3 群的定義 243
10.3.1 半群 243
10.3.2 群 245
10.3.3 群的性質 247
10.4 子群 248
10.4.1 子群 248
10.4.2 子群的判定 249
10.5 阿貝爾群和循環群 251
10.5.1 阿貝爾群 251
10.5.2 循環群 252
10.6 置換群與伯恩賽德定理 254
10.6.1 置換群 254
*10.6.2 伯恩賽德定理（Burnside） 257
10.7 陪集與拉格朗日定理 260
10.7.1 陪集 260
10.7.2 正規子群和商群 261
10.7.3 拉格朗日定理 263
10.8 群的同態與同構 264
本章小結 267
習題10 267
第11章 格與布爾代數 271
本章學習目標 271
11.1 格的定義和性質 271
11.1.1 格的定義 271
11.1.2 格的對偶原理 272
11.1.3 格的性質 273
11.1.4 子格和格的同態 276
11.2 分配格和有補格 278
11.2.1 模格 278
11.2.2 分配格 279
11.2.3 有界格 281
11.2.4 有補格 281
11.3 布爾代數 282
11.3.1 布爾代數的定義及性質 282
11.3.2 布爾代數的同構與同態 284
11.3.3 布爾代數的表示理論 287
本章小結 289
習題11 289
習題參考答案 292
參考文獻 355

1. 嵌入式人工智能技術應用（數字教材） [主編 胡娜 楊國勇 晏廷榮]
2. Java Web項目化設計實踐教程 [邱云 曾陳萍]
3. 人工智能開發框架應用 [主編 王明超 蘆婭云]
4. 民航客艙服務實用英語教程 [主編 田靜 徐亞玲]
5. Python數據分析 [主編　馮志輝　趙磊　李放]
6. 大學信息技術 [曾翰穎 編著]
7. 多維視域下的高�；@球教學創新研究 [張利超 李寧 著]
8. 創新創業訓練實踐教程 [主編 王日華 陳武 黃喆誠]
9. 實用運籌學 [主編　邢育紅　于晉臣]
10. 電子技術（第二版） [主編 覃愛娜 李飛]
11. 勞動爭議處理實務 [主編 王秀卿 羅靜]
12. 工程數學 [主編 郭立娟 王海]
13. 語音識別理論與實踐 [主編　莫宏偉]
14. 武術基礎教程 [主編 李代勇 謝志民]
15. 計算機網絡實訓教程 [主編 張浩軍 趙玉娟]
16. 畫法幾何與機械制圖習題集（多學時） [主編 趙軍]
17. 電工電子技術基礎 [主編 劉 軍 楊國龍 劉天成]
18. MySQL數據庫項目式教程 [陳亞峰]
19. 機械設計基礎（第二版） [主編 田亞平 李愛姣]
20. 畫法幾何與機械制圖 [主編 趙軍]
21. C語言程序設計習題與實驗指導（第二版） [主編 甄增榮 張賓]
22. C語言程序設計（第二版） [主編 甄增榮 田云霞]
23. Unity3D虛擬現實應用開發實踐 [主 編 劉龍]
24. 智能化技術基礎（第三版） [鄧文達　李禮]
25. 面向對象程序設計 [主編 張勇 張平華 趙小龍]
26. 網絡營銷 [主編 夏薇薇 劉婷 尚潔]
27. 電視節目策劃與制作（微課版） [主　編　黃滴滴]
28. 數據庫技術與應用實踐教程（SQL Server 2019） [主 編 嚴暉 周肆清]
29. 大學應用數學 [主編 郭立娟]
30. 工業機器人拆裝與調試 [主編 胡月霞 向艷芳 朱奇]