本書是編者在多年離散數(shù)學(xué)教學(xué)實(shí)踐經(jīng)驗(yàn)的基礎(chǔ)上，針對(duì)應(yīng)用型本科教學(xué)的特點(diǎn)，參考了國(guó)內(nèi)外多種教材編寫而成的。應(yīng)用型本科注重理論，以夠用為限，重點(diǎn)突出，加強(qiáng)理論與實(shí)際的聯(lián)系。本書力求理論體系完整、科學(xué)嚴(yán)謹(jǐn)，內(nèi)容敘述深入淺出、簡(jiǎn)明扼要，概念盡量用例子加以說(shuō)明。本書強(qiáng)化基本概念的理解，注重基本理論的證明方法。書中配有典型例題，各章后面配有適量典型習(xí)題供學(xué)生練習(xí)。

離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，它的研究對(duì)象是各種離散量的結(jié)構(gòu)及離散量之間的關(guān)系，在數(shù)據(jù)結(jié)構(gòu)、編譯系統(tǒng)、程序設(shè)計(jì)語(yǔ)言、數(shù)據(jù)庫(kù)原理、操作系統(tǒng)、人工智能、計(jì)算機(jī)圖形學(xué)、軟件工程、網(wǎng)絡(luò)與分布式計(jì)算以及計(jì)算機(jī)體系結(jié)構(gòu)等領(lǐng)域中都得到廣泛的應(yīng)用。因此，離散數(shù)學(xué)是計(jì)算機(jī)專業(yè)學(xué)生的一門重要的專業(yè)基礎(chǔ)課程。

通過(guò)對(duì)離散數(shù)學(xué)的學(xué)習(xí)，不僅能使學(xué)生掌握進(jìn)一步學(xué)習(xí)其他課程所必需的數(shù)學(xué)基礎(chǔ)知識(shí)，還可以培養(yǎng)學(xué)生的抽象思維能力和嚴(yán)密的邏輯推理能力，同時(shí)也可以提高學(xué)生發(fā)現(xiàn)問題、分析問題和解決問題的能力。

本書是編者在多年離散數(shù)學(xué)教學(xué)實(shí)踐經(jīng)驗(yàn)的基礎(chǔ)上，針對(duì)應(yīng)用型本科教學(xué)的特點(diǎn)，參考了國(guó)內(nèi)外多種教材編寫而成的。應(yīng)用型本科注重理論，以夠用為限，重點(diǎn)突出，加強(qiáng)理論與實(shí)際的聯(lián)系。本書力求理論體系完整、科學(xué)嚴(yán)謹(jǐn)，內(nèi)容敘述深入淺出、簡(jiǎn)明扼要，概念盡量用例子加以說(shuō)明。本書強(qiáng)化基本概念的理解，注重基本理論的證明方法。書中配有典型例題，各章后面配有適量典型習(xí)題供學(xué)生練習(xí)。

全書共分11章，主要內(nèi)容有：

第1章和第2章分別介紹命題邏輯和謂詞邏輯的基本概念、等值演算和推理理論。第3章至第6章為集合論，介紹了集合的基本概念和運(yùn)算、二元關(guān)系、函數(shù)、基數(shù)等內(nèi)容。第7章至第9章為圖論，介紹了圖的基本概念、圖的矩陣表示、歐拉圖、哈密爾頓圖、樹、平面圖等內(nèi)容。第10章和第11章為代數(shù)系統(tǒng)，介紹了代數(shù)系統(tǒng)、半群、獨(dú)異點(diǎn)、群、環(huán)、域、格、有補(bǔ)格、分配格和布爾代數(shù)等內(nèi)容。

本書第1章至第3章由賈振華編寫，第4章由賈振華和李新榮共同編寫；第5章和第6章由李瑛編寫；第7章和第8章由李新榮編寫；第9章至第11章由黃中升編寫。趙輝、李杰、崔玉寶、趙麗艷等同志參加了部分章節(jié)的習(xí)題編寫和校對(duì)工作。

在編寫過(guò)程中，作者參考了大量的離散數(shù)學(xué)教材和相關(guān)的文獻(xiàn)資料，從中汲取了許多好的思想，引用了不少有用的素材，在此一并向有關(guān)作者表示感謝。還要感謝中國(guó)水利水電出版社的編輯和領(lǐng)導(dǎo)以及院系領(lǐng)導(dǎo)對(duì)教材出版的支持和幫助。

由于作者水平有限，書中難免出現(xiàn)一些錯(cuò)誤和不妥之處，敬請(qǐng)讀者不吝指正。作者電子郵箱：jiazhenhualf@163.com。

編 者

2006年10月

序
前言
第一部分 數(shù)理邏輯
 第1章 命題邏輯 2
本章學(xué)習(xí)目標(biāo) 2
1.1 命題和命題聯(lián)結(jié)詞 2
1.1.1 命題 2
1.1.2 命題聯(lián)結(jié)詞 3
1.2 命題公式與解釋 7
1.2.1 命題公式 7
1.2.2 命題公式的解釋 9
1.3 真值表與等價(jià)公式 10
1.3.1 真值表 10
1.3.2 命題公式的分類 11
1.3.3 等價(jià)公式 12
1.3.4 代入規(guī)則和替換規(guī)則 15
1.4 對(duì)偶定理 19
1.5 范式 20
1.5.1 合取范式和析取范式 20
1.5.2 主析取范式和主合取范式 22
1.6 公式的蘊(yùn)涵 27
1.6.1 蘊(yùn)涵的概念 27
1.6.2 蘊(yùn)涵式的證明方法 28
1.6.3 基本蘊(yùn)涵式 29
1.7 其他聯(lián)結(jié)詞與最小聯(lián)結(jié)詞組 29
1.7.1 其他聯(lián)結(jié)詞 29
1.7.2 最小聯(lián)結(jié)詞組 32
1.8 命題邏輯推理理論 33
1.8.1 命題邏輯推理理論 33
1.8.2 推理規(guī)則 35
1.8.3 判斷有效結(jié)論的常用方法 36
本章小結(jié) 39
習(xí)題一 40
 第2章 謂詞邏輯 43
本章學(xué)習(xí)目標(biāo) 43
2.1 謂詞邏輯命題的符號(hào)化 43
2.1.1 個(gè)體詞與謂詞 43
2.1.2 量詞 45
2.1.3 謂詞邏輯中命題的符號(hào)化 45
2.2 謂詞邏輯公式與解釋 47
2.2.1 謂詞邏輯的合式公式 47
2.2.2 謂詞的約束和替換 49
2.2.3 謂詞邏輯公式的解釋 50
2.3 謂詞邏輯公式的等價(jià)與蘊(yùn)涵 52
2.3.1 謂詞邏輯的等價(jià)公式 52
2.3.2 謂詞邏輯的蘊(yùn)涵公式 55
2.3.3 多個(gè)量詞的使用 56
2.4 前束范式 57
2.5 謂詞邏輯的推理理論 59
本章小結(jié) 63
習(xí)題二 63
第二部分 集合論
 第3章 集合 68
本章學(xué)習(xí)目標(biāo) 68
3.1 集合的概念與表示 68
3.1.1 集合的基本概念 68
3.1.2 集合的表示 68
3.1.3 集合之間的關(guān)系 69
3.2 集合的運(yùn)算 72
3.2.1 集合的交運(yùn)算 72
3.2.2 集合的并運(yùn)算 73
3.2.3 集合的補(bǔ) 74
3.2.4 集合的對(duì)稱差 75
3.3 包含排斥原理 76
本章小結(jié) 79
習(xí)題三 79
 第4章 關(guān)系 82
本章學(xué)習(xí)目標(biāo) 82
4.1 序偶與笛卡兒積 82
4.1.1 有序n元組 82
4.1.2 笛卡兒積的概念 83
4.1.3 笛卡兒積的性質(zhì) 83
4.2 二元關(guān)系及其表示 85
4.2.1 二元關(guān)系的概念 85
4.2.2 二元關(guān)系的表示 86
4.3 關(guān)系的運(yùn)算 88
4.3.1 關(guān)系的交、并、差、補(bǔ)運(yùn)算 88
4.3.2 關(guān)系的復(fù)合運(yùn)算 89
4.3.3 關(guān)系的逆運(yùn)算 92
4.4 關(guān)系的性質(zhì) 93
4.4.1 自反性和反自反性 93
4.4.2 對(duì)稱性和反對(duì)稱性 94
4.4.3 傳遞性 94
4.4.4 關(guān)系性質(zhì)的判定 95
4.5 關(guān)系的閉包 100
4.6 等價(jià)關(guān)系與集合的劃分 105
4.6.1 等價(jià)關(guān)系 105
4.6.2 等價(jià)類 106
4.6.3 集合的劃分 106
4.7 相容關(guān)系 109
4.7.1 相容關(guān)系 109
4.7.2 覆蓋 110
4.8 偏序關(guān)系 112
4.8.1 偏序關(guān)系 112
4.8.2 哈斯圖 113
4.8.3 全序關(guān)系 114
4.8.4 良序關(guān)系 116
本章小結(jié) 117
習(xí)題四 117
 第5章 函數(shù) 120
本章學(xué)習(xí)目標(biāo) 120
5.1 函數(shù)的概念 120
5.2 函數(shù)的性質(zhì) 121
5.3 復(fù)合函數(shù)和逆函數(shù) 124
5.3.1 復(fù)合函數(shù) 124
5.3.2 逆函數(shù) 125
5.4 置換 127
本章小結(jié) 128
習(xí)題五 128
 第6章 集合的基數(shù) 130
本章學(xué)習(xí)目標(biāo) 130
6.1 基數(shù)的概念 130
6.2 可數(shù)集和不可數(shù)集 132
6.2.1 可數(shù)集 132
6.2.2 不可數(shù)集 134
6.3 基數(shù)的比較 134
本章小結(jié) 136
習(xí)題六 136
第三部分 圖論
 第7章 圖 140
本章學(xué)習(xí)目標(biāo) 140
7.1 圖的基本概念 140
7.1.1 圖論的發(fā)展 140
7.1.2 圖的基本概念 141
7.2 通路與回路 146
7.3 圖的連通性 148
7.3.1 無(wú)向圖的連通性 148
7.3.2 有向圖的連通性 150
7.4 圖的矩陣表示 153
7.4.1 圖的鄰接矩陣 153
7.4.2 圖的關(guān)聯(lián)矩陣 155
7.4.3 有向圖的可達(dá)矩陣 156
7.5 圖的應(yīng)用 158
7.5.1 帶權(quán)圖的最短通路 158
7.5.2 帶權(quán)圖的關(guān)鍵路徑 161
本章小結(jié) 162
習(xí)題七 163
 第8章 歐拉圖與哈密爾頓圖 166
本章學(xué)習(xí)目標(biāo) 166
8.1 歐拉圖 166
8.1.1 歐拉圖的定義 166
8.1.2 歐拉圖的判定 167
8.1.3 求歐拉回路的算法 168
8.1.4 歐拉圖的應(yīng)用 169
8.2 哈密爾頓圖 170
8.2.1 哈密爾頓圖 170
8.2.2 哈密爾頓圖的判定 170
本章小結(jié) 171
習(xí)題八 172
 第9章 特殊圖 173
本章學(xué)習(xí)目標(biāo) 173
9.1 樹 173
9.1.1 無(wú)向樹 173
9.1.2 生成樹與最小生成樹 175
9.1.3 有向樹與根樹 177
9.2 二部圖 180
9.3 平面圖 182
9.3.1 平面圖的定義 182
9.3.2 歐拉公式 183
9.3.3 庫(kù)拉托夫斯基定理 185
9.3.4 平面圖的對(duì)偶圖 186
本章小結(jié) 188
習(xí)題九 188
第四部分 代數(shù)系統(tǒng)
 第10章 代數(shù)結(jié)構(gòu) 192
本章學(xué)習(xí)目標(biāo) 192
10.1 二元運(yùn)算及其性質(zhì) 192
10.1.1 二元運(yùn)算 192
10.1.2 二元運(yùn)算的性質(zhì) 194
10.2 代數(shù)系統(tǒng) 196
10.3 群的定義 198
10.3.1 半群 198
10.3.2 群 199
10.3.3 群的性質(zhì) 200
10.4 子群 202
10.4.1 子群 202
10.4.2 子群的判定 203
10.5 阿貝爾群和循環(huán)群 204
10.5.1 阿貝爾群 204
10.5.2 循環(huán)群 205
10.6 置換群與伯恩賽德定理 206
10.6.1 置換群 206
*10.6.2 伯恩賽德定理（Burnside） 209
10.7 陪集與拉格朗日定理 211
10.7.1 陪集 211
10.7.2 正規(guī)子群和商群 213
10.7.3 拉格朗日定理 214
10.8 群的同態(tài)與同構(gòu) 215
本章小結(jié) 217
習(xí)題十 218
 第11章 格與布爾代數(shù) 221
本章學(xué)習(xí)目標(biāo) 221
11.1 格的定義和性質(zhì) 221
11.1.1 格的定義 221
11.1.2 格的對(duì)偶原理 222
11.1.3 格的性質(zhì) 222
11.1.4 子格和格的同態(tài) 225
11.2 分配格和有補(bǔ)格 227
11.2.1 模格 227
11.2.2 分配格 227
11.2.3 有界格 229
11.2.4 有補(bǔ)格 229
11.3 布爾代數(shù) 230
11.3.1 布爾代數(shù)的定義及性質(zhì) 230
11.3.2 布爾代數(shù)的同構(gòu)與同態(tài) 231
11.3.3 布爾代數(shù)的表示理論 234
本章小結(jié) 235
習(xí)題十一 236
參考文獻(xiàn) 238

1. 教學(xué)的智慧—高三數(shù)學(xué)落實(shí)核心素養(yǎng)教法指導(dǎo) [王春紅 等 編著]
2. 應(yīng)用數(shù)學(xué) [吳小寧]
3. 大學(xué)生創(chuàng)新創(chuàng)業(yè)實(shí)踐——數(shù)學(xué)類 [主編 吳天慶]
4. 工程數(shù)學(xué) [主編 郭立娟 王海]
5. 應(yīng)用數(shù)學(xué) [梁瑋 蔡超 高志]
6. 大學(xué)應(yīng)用數(shù)學(xué) [主編 郭立娟]
7. 高等數(shù)學(xué)導(dǎo)學(xué)篇（下冊(cè)） [主編 李文婧 胡雷 尹金生]
8. 高等數(shù)學(xué)導(dǎo)學(xué)篇（上冊(cè)） [主編 李文婧 胡雷 尹金生]
9. 高等數(shù)學(xué)（下冊(cè)） [主編 李愛芹 胡雷 尹金生]
10. 高等數(shù)學(xué)（上冊(cè)） [主編 李愛芹 胡雷 尹金生]
11. 高等數(shù)學(xué)（下冊(cè)） [秦紅兵]
12. 應(yīng)用數(shù)學(xué) [主編 劉東海 劉麗瑤]
13. 高等數(shù)學(xué)（上冊(cè)） [主編 白莉 秦紅兵]
14. 高等數(shù)學(xué)（下冊(cè)）（第二版） [主編 何春江]
15. 高等數(shù)學(xué)（上冊(cè)）（第二版） [主編 何春江]
16. 高等數(shù)學(xué) [主編 劉彥輝 張 靜]
17. 應(yīng)用數(shù)學(xué)（第二版） [主編 劉麗瑤]
18. 數(shù)學(xué)（下冊(cè)） [單鳳娟 劉艷平 李楊 馬秀芬 ]
19. 數(shù)學(xué)（上冊(cè)） [單鳳娟 劉艷平 李楊 馬秀芬 ]
20. 應(yīng)用數(shù)學(xué)基礎(chǔ) [主編 劉彥輝 李先明]
21. 高等數(shù)學(xué)學(xué)習(xí)輔導(dǎo)與習(xí)題解答（第三版） [主編 翟秀娜]
22. 離散數(shù)學(xué)（第二版） [主編 賈振華]
23. 數(shù)學(xué)（二）職業(yè)模塊 [李麗君 吳白旺 楊勇]
24. 高等數(shù)學(xué)（下冊(cè)） [何春江]
25. 數(shù)學(xué)（一）職業(yè)模塊 [主編 楊勇 海敏娟 禇麗娜]
26. 高等數(shù)學(xué)（上冊(cè)） [何春江]
27. 應(yīng)用數(shù)學(xué)（第二版•下冊(cè)） [主 編 孫振營(yíng) 徐自立]
28. 應(yīng)用數(shù)學(xué)（第二版•上冊(cè)） [主編 孫振營(yíng) 夏云青]
29. 數(shù)學(xué)（一）職業(yè)模塊 [主編 楊勇 海敏娟 禇麗娜]
30. 計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)（第二版） [主編 何春江]