離散數(shù)學(xué)（第二版）

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

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

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

第二版前言

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

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

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

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

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

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

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

編 者

2016年5月

第二版前言
第一版前言
第一部分 數(shù)理邏輯
第1章 命題邏輯 2
本章學(xué)習(xí)目標(biāo) 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 真值表與等價(jià)公式 11
1.3.1 真值表 11
1.3.2 命題公式的分類 13
1.3.3 等價(jià)公式 15
1.3.4 代入規(guī)則和替換規(guī)則 18
1.4 對(duì)偶定理 23
1.5 范式 25
1.5.1 合取范式和析取范式 25
1.5.2 主析取范式和主合取范式 27
1.6 公式的蘊(yùn)涵 33
1.6.1 蘊(yùn)涵的概念 33
1.6.2 蘊(yùn)涵式的證明方法 34
1.6.3 基本蘊(yùn)涵式 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í)目標(biāo) 52
2.1 謂詞邏輯命題的符號(hào)化 52
2.1.1 個(gè)體詞與謂詞 53
2.1.2 量詞 54
2.1.3 謂詞邏輯中命題的符號(hào)化 55
2.2 謂詞邏輯公式與解釋 57
2.2.1 謂詞邏輯的合式公式 57
2.2.2 謂詞的約束和替換 59
2.2.3 謂詞邏輯公式的解釋 61
2.3 謂詞邏輯公式的等價(jià)與蘊(yùn)涵 63
2.3.1 謂詞邏輯的等價(jià)公式 63
2.3.2 謂詞邏輯的蘊(yùn)涵公式 67
2.3.3 多個(gè)量詞的使用 68
2.4 前束范式 69
2.5 謂詞邏輯的推理理論 71
本章小結(jié) 76
習(xí)題2 76
第二部分 集合論
第3章 集合 81
本章學(xué)習(xí)目標(biāo) 81
3.1 集合的概念與表示 81
3.1.1 集合的基本概念 81
3.1.2 集合的表示 82
3.1.3 集合之間的關(guān)系 83
3.2 集合的運(yùn)算 86
3.2.1 集合的交運(yùn)算 86
3.2.2 集合的并運(yùn)算 87
3.2.3 集合的補(bǔ) 88
3.2.4 集合的對(duì)稱差 90
3.3 包含排斥原理 91
本章小結(jié) 94
習(xí)題3 94
第4章 關(guān)系 98
本章學(xué)習(xí)目標(biāo) 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)系的運(yùn)算 105
4.3.1 關(guān)系的交、并、差、補(bǔ)運(yùn)算 105
4.3.2 關(guān)系的復(fù)合運(yùn)算 106
4.3.3 關(guān)系的逆運(yùn)算 110
4.4 關(guān)系的性質(zhì) 112
4.4.1 自反性和反自反性 112
4.4.2 對(duì)稱性和反對(duì)稱性 112
4.4.3 傳遞性 113
4.4.4 關(guān)系性質(zhì)的判定 113
4.5 關(guān)系的閉包 120
4.6 等價(jià)關(guān)系與集合的劃分 125
4.6.1 等價(jià)關(guān)系 125
4.6.2 等價(jià)類 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í)目標(biāo) 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í)目標(biāo) 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í)目標(biāo) 166
7.1 圖的基本概念 166
7.1.1 圖論的發(fā)展 166
7.1.2 圖的基本概念 167
7.2 通路與回路 175
7.3 圖的連通性 176
7.3.1 無(wú)向圖的連通性 176
7.3.2 有向圖的連通性 179
7.4 圖的矩陣表示 183
7.4.1 圖的鄰接矩陣 183
7.4.2 圖的關(guān)聯(lián)矩陣 185
7.4.3 有向圖的可達(dá)矩陣 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í)目標(biāo) 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í)目標(biāo) 210
9.1 樹 210
9.1.1 無(wú)向樹 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 庫(kù)拉托夫斯基定理 229
9.3.4 平面圖的對(duì)偶圖 230
本章小結(jié) 232
習(xí)題9 232
第四部分 代數(shù)系統(tǒng)
第10章 代數(shù)結(jié)構(gòu) 236
本章學(xué)習(xí)目標(biāo) 236
10.1 二元運(yùn)算及其性質(zhì) 236
10.1.1 二元運(yùn)算 236
10.1.2 二元運(yùn)算的性質(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í)目標(biāo) 271
11.1 格的定義和性質(zhì) 271
11.1.1 格的定義 271
11.1.2 格的對(duì)偶原理 272
11.1.3 格的性質(zhì) 273
11.1.4 子格和格的同態(tài) 276
11.2 分配格和有補(bǔ)格 278
11.2.1 模格 278
11.2.2 分配格 279
11.2.3 有界格 281
11.2.4 有補(bǔ)格 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
參考文獻(xiàn) 355

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