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

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

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

第二版前言

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

（1）訂正了原書中的錯誤，對全部章節(jié)進行了修訂，修改了書中發(fā)現(xiàn)的所有錯誤。

（2）補充了部分內(nèi)容，如最優(yōu)二叉樹的構(gòu)建、哈夫曼編碼等。

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

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

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

由于作者水平有限，難免出現(xiàn)錯誤和安排不妥之處，敬請廣大師生不吝指正。Email：jiazhenhualf@163.com。

編 者

2016年5月

第二版前言
第一版前言
第一部分 數(shù)理邏輯
第1章 命題邏輯 2
本章學(xué)習(xí)目標 2
1.1 命題和命題聯(lián)結(jié)詞 2
1.1.1 命題 2
1.1.2 命題聯(lián)結(jié)詞 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 代入規(guī)則和替換規(guī)則 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 其他聯(lián)結(jié)詞與最小聯(lián)結(jié)詞組 36
1.7.1 其他聯(lián)結(jié)詞 36
1.7.2 最小聯(lián)結(jié)詞組 39
1.8 命題邏輯推理理論 40
1.8.1 命題邏輯推理理論 40
1.8.2 推理規(guī)則 42
1.8.3 判斷有效結(jié)論的常用方法 44
本章小結(jié) 48
習(xí)題1 48
第2章 謂詞邏輯 52
本章學(xué)習(xí)目標 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
本章小結(jié) 76
習(xí)題2 76
第二部分 集合論
第3章 集合 81
本章學(xué)習(xí)目標 81
3.1 集合的概念與表示 81
3.1.1 集合的基本概念 81
3.1.2 集合的表示 82
3.1.3 集合之間的關(guān)系 83
3.2 集合的運算 86
3.2.1 集合的交運算 86
3.2.2 集合的并運算 87
3.2.3 集合的補 88
3.2.4 集合的對稱差 90
3.3 包含排斥原理 91
本章小結(jié) 94
習(xí)題3 94
第4章 關(guān)系 98
本章學(xué)習(xí)目標 98
4.1 序偶與笛卡爾積 98
4.1.1 有序n元組 98
4.1.2 笛卡爾積的概念 99
4.1.3 笛卡爾積的性質(zhì) 100
4.2 二元關(guān)系及其表示 102
4.2.1 二元關(guān)系的概念 102
4.2.2 二元關(guān)系的表示 103
4.3 關(guān)系的運算 105
4.3.1 關(guān)系的交、并、差、補運算 105
4.3.2 關(guān)系的復(fù)合運算 106
4.3.3 關(guān)系的逆運算 110
4.4 關(guān)系的性質(zhì) 112
4.4.1 自反性和反自反性 112
4.4.2 對稱性和反對稱性 112
4.4.3 傳遞性 113
4.4.4 關(guān)系性質(zhì)的判定 113
4.5 關(guān)系的閉包 120
4.6 等價關(guān)系與集合的劃分 125
4.6.1 等價關(guān)系 125
4.6.2 等價類 126
4.6.3 集合的劃分 127
4.7 相容關(guān)系 130
4.7.1 相容關(guān)系 130
4.7.2 覆蓋 132
4.8 偏序關(guān)系 134
4.8.1 偏序關(guān)系 134
4.8.2 哈斯圖 135
4.8.3 全序關(guān)系 137
4.8.4 良序關(guān)系 139
本章小結(jié) 140
習(xí)題4 140
第5章 函數(shù) 144
本章學(xué)習(xí)目標 144
5.1 函數(shù)的概念 144
5.2 函數(shù)的性質(zhì) 146
5.3 復(fù)合函數(shù)和逆函數(shù) 149
5.3.1 復(fù)合函數(shù) 149
5.3.2 逆函數(shù) 151
5.4 置換 152
本章小結(jié) 154
習(xí)題5 154
第6章 集合的基數(shù) 156
本章學(xué)習(xí)目標 156
6.1 基數(shù)的概念 156
6.2 可數(shù)集和不可數(shù)集 158
6.2.1 可數(shù)集 158
6.2.2 不可數(shù)集 160
6.3 基數(shù)的比較 161
本章小結(jié) 163
習(xí)題6 164
第三部分 圖論
第7章 圖 166
本章學(xué)習(xí)目標 166
7.1 圖的基本概念 166
7.1.1 圖論的發(fā)展 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 圖的關(guān)聯(lián)矩陣 185
7.4.3 有向圖的可達矩陣 188
7.5 圖的應(yīng)用 190
7.5.1 帶權(quán)圖的最短通路 190
7.5.2 帶權(quán)圖的關(guān)鍵路徑 193
本章小結(jié) 196
習(xí)題7 196
第8章 歐拉圖與哈密爾頓圖 200
本章學(xué)習(xí)目標 200
8.1 歐拉圖 200
8.1.1 歐拉圖的定義 200
8.1.2 歐拉圖的判定 201
8.1.3 求歐拉回路的算法 203
8.1.4 歐拉圖的應(yīng)用 204
8.2 哈密爾頓圖 205
8.2.1 哈密爾頓圖 205
8.2.2 哈密爾頓圖的判定 206
本章小結(jié) 207
習(xí)題8 208
第9章 特殊圖 210
本章學(xué)習(xí)目標 210
9.1 樹 210
9.1.1 無向樹 210
9.1.2 生成樹與最小生成樹 213
9.1.3 有向樹與根樹 214
9.1.4 最優(yōu)二叉樹及其應(yīng)用 219
9.2 二部圖 222
9.3 平面圖 225
9.3.1 平面圖的定義 225
9.3.2 歐拉公式 226
9.3.3 庫拉托夫斯基定理 229
9.3.4 平面圖的對偶圖 230
本章小結(jié) 232
習(xí)題9 232
第四部分 代數(shù)系統(tǒng)
第10章 代數(shù)結(jié)構(gòu) 236
本章學(xué)習(xí)目標 236
10.1 二元運算及其性質(zhì) 236
10.1.1 二元運算 236
10.1.2 二元運算的性質(zhì) 238
10.2 代數(shù)系統(tǒng) 242
10.3 群的定義 243
10.3.1 半群 243
10.3.2 群 245
10.3.3 群的性質(zhì) 247
10.4 子群 248
10.4.1 子群 248
10.4.2 子群的判定 249
10.5 阿貝爾群和循環(huán)群 251
10.5.1 阿貝爾群 251
10.5.2 循環(huán)群 252
10.6 置換群與伯恩賽德定理 254
10.6.1 置換群 254
*10.6.2 伯恩賽德定理（Burnside） 257
10.7 陪集與拉格朗日定理 260
10.7.1 陪集 260
10.7.2 正規(guī)子群和商群 261
10.7.3 拉格朗日定理 263
10.8 群的同態(tài)與同構(gòu) 264
本章小結(jié) 267
習(xí)題10 267
第11章 格與布爾代數(shù) 271
本章學(xué)習(xí)目標 271
11.1 格的定義和性質(zhì) 271
11.1.1 格的定義 271
11.1.2 格的對偶原理 272
11.1.3 格的性質(zhì) 273
11.1.4 子格和格的同態(tài) 276
11.2 分配格和有補格 278
11.2.1 模格 278
11.2.2 分配格 279
11.2.3 有界格 281
11.2.4 有補格 281
11.3 布爾代數(shù) 282
11.3.1 布爾代數(shù)的定義及性質(zhì) 282
11.3.2 布爾代數(shù)的同構(gòu)與同態(tài) 284
11.3.3 布爾代數(shù)的表示理論 287
本章小結(jié) 289
習(xí)題11 289
習(xí)題參考答案 292
參考文獻 355

1. 實用運籌學(xué) [主編　邢育紅　于晉臣]
2. 電子技術(shù)（第二版） [主編 覃愛娜 李飛]
3. 勞動爭議處理實務(wù) [主編 王秀卿 羅靜]
4. 工程數(shù)學(xué) [主編 郭立娟 王海]
5. 語音識別理論與實踐 [主編　莫宏偉]
6. 武術(shù)基礎(chǔ)教程 [主編 李代勇 謝志民]
7. 計算機網(wǎng)絡(luò)實訓(xùn)教程 [主編 張浩軍 趙玉娟]
8. 畫法幾何與機械制圖習(xí)題集（多學(xué)時） [主編 趙軍]
9. 電工電子技術(shù)基礎(chǔ) [主編 劉 軍 楊國龍 劉天成]
10. MySQL數(shù)據(jù)庫項目式教程 [陳亞峰]
11. 機械設(shè)計基礎(chǔ)（第二版） [主編 田亞平 李愛姣]
12. 畫法幾何與機械制圖 [主編 趙軍]
13. C語言程序設(shè)計習(xí)題與實驗指導(dǎo)（第二版） [主編 甄增榮 張賓]
14. C語言程序設(shè)計（第二版） [主編 甄增榮 田云霞]
15. Unity3D虛擬現(xiàn)實應(yīng)用開發(fā)實踐 [主 編 劉龍]
16. 智能化技術(shù)基礎(chǔ)（第三版） [鄧文達　李禮]
17. 面向?qū)ο蟪绦蛟O(shè)計 [主編 張勇 張平華 趙小龍]
18. 網(wǎng)絡(luò)營銷 [主編 夏薇薇 劉婷 尚潔]
19. 電視節(jié)目策劃與制作（微課版） [主　編　黃滴滴]
20. 數(shù)據(jù)庫技術(shù)與應(yīng)用實踐教程（SQL Server 2019） [主 編 嚴暉 周肆清]
21. 大學(xué)應(yīng)用數(shù)學(xué) [主編 郭立娟]
22. 工業(yè)機器人拆裝與調(diào)試 [主編 胡月霞 向艷芳 朱奇]
23. 功能材料制備與表征實驗指導(dǎo)書 [龔偉平 趙軍峰 梅海娟 等編著]
24. 信號與系統(tǒng)（第二版） [主編 張宇]
25. 信息技術(shù)基礎(chǔ) [主編 唐倩 邵銳]
26. Python 語言程序設(shè)計實踐指導(dǎo) [主編　張雙獅]
27. Photoshop 圖形圖像項目化教程 [主編 胡斌斌 黎婭 蘇大椿]
28. 體育舞蹈教程 [主編 劉偉 陳志明 曾明]
29. 線性代數(shù)導(dǎo)學(xué)篇 [主編 史昱]
30. 信息技術(shù)基礎(chǔ)實訓(xùn)與習(xí)題指導(dǎo)（Windows7+Office2016） [主編 周金容 唐天國]