第1章命題演算基礎1
1.1命題和聯結詞1
1.1.1命題1
1.1.2聯結詞2
1.1.3合式公式5
1.1.4命題邏輯的應用6
1.2真假性9
1.2.1解釋9
1.2.2等價公式10
1.2.3聯結詞的完備集11
1.2.4對偶式和內否式12
1.3範式及其應用14
1.3.1範式14
1.3.2主範式16
1.3.3範式的應用19
1.4典型例題20
習題21
第2章命題演算的推理理論25
2.1命題演算的公理繫統25
2.1.1公理繫統的組成部分26
2.1.2公理繫統的推理過程27
2.2若干重要的導出規則29
2.2.1分離規則的討論29
2.2.2公理和定理的導出規則29
2.3命題演算的假設推理繫統31
2.3.1假設推理繫統的組成31
2.3.2假設推理繫統的推理過程32
2.3.3額外假設推理法34
2.4命題演算的歸結推理法36
2.4.1歸結證明過程36
2.4.2歸結證明示例37
2.5典型例題38
習題41
〖3〗離散數學（微課版）目錄〖3〗第3章謂詞演算基礎43
3.1個體和謂詞43
3.1.1個體43
3.1.2謂詞43
3.2函數項和量詞46
3.2.1函數項46
3.2.2量詞46
3.3和48
3.3.1自由出現和約束出現48
3.3.2改名和代入49
3.4永真性和可滿足性50
3.4.1真假性50
3.4.2同真假性、永真性和可滿足性52
3.4.3範式55
3.5唯一性量詞和摹狀詞56
3.5.1唯一性量詞56
3.5.2摹狀詞57
3.6典型例題58
習題59
第4章謂詞演算的推理理論62
4.1謂詞演算的永真推理繫統62
4.1.1公理繫統的組成部分62
4.1.2公理繫統的推理過程64
4.2謂詞演算的假設推理繫統65
4.2.1假設推理繫統的組成及證明方法65
4.2.2定理的假設推導過程66
4.3謂詞演算的歸結推理繫統67
4.3.1置換68
4.3.2歸結反演繫統69
4.4霍恩子句邏輯程序72
4.5Prolog簡介74
4.6典型例題76
習題78
第5章遞歸函數論81
5.1數論函數和數論謂詞81
5.1.1數論函數81
5.1.2數論謂詞和特征函數82
5.2函數的構造84
5.2.1迭置法84
5.2.2算子法85
5.2.3原始遞歸函數86
5.3典型例題87
習題88
第6章集合89
6.1集合的基本概念89
6.1.1集合的定義89
6.1.2集合的表示90
6.1.3集合的包含關繫91
6.1.4集合的特點91
6.1.5多重集92
6.2集合的基本運算92
6.2.1集合的並、交、差92
6.2.2集合的對稱差94
6.2.3文氏圖94
6.2.4集合的冪集合95
6.2.5多個集合的並與交96
6.3全集和補集97
6.3.1全集和補集的定義97
6.3.2基本運算定理97
6.3.3集合的計算機表示98
6.4自然數與自然數集99
6.4.1後繼99
6.4.2自然數和自然數集的定義99
6.4.3皮亞諾公理假設100
6.4.4自然數集的性質101
6.4.5集合的遞歸定義與遞歸子程序102
6.5包含與排斥原理104
6.6典型例題106
習題107
第7章關繫111
7.1集合的笛卡兒積集111
7.1.1組111
7.1.2笛卡兒積集111
7.1.3組、n個集合的笛卡兒積集112
7關繫的基本概念113
7.2關繫113
7.2關繫的表示113
7.2關繫與數據結構114
7.2關繫的運算115
7關繫及其運算117
7.3關繫117
7.3關繫的運算118
7關繫的性質120
7.4.1自反性、反自反性、對稱性、反對稱性、傳遞性和反傳遞性120
7.4關繫性質的判定定理122
7關繫的閉包運算124
7.5.1自反閉包、對稱閉包和傳遞閉包124
7.5.2閉包的判定定理124
7.6等價關繫和集合的劃分128
7.6.1等價關繫和等價類128
7.6.2商集合129
7.6.3集合的劃分130
7.7偏序關繫和格132
7.7.1偏序關繫和偏序集132
7.7.2哈斯圖133
7.7.3鏈、反鏈、全序集133
7.7.134
7.7.5上界、下界、最小上界和最大下界135
7.7.6格135
7.7.7拓撲排序136
7.8粗糙集概論138
7.8.1知識與知識分類138
7.8.2集合近似與粗糙集概念140
7.9典型例題141
習題142
第8章函數與集合的勢148
8.1函數的基本概念148
8.1.1函數(映射)的定義148
8.1.2函數的性質150
8.2函數的復合和逆函數151
8.2.1函數的復合151
8.2.2左可逆函數、右可逆函數和逆函數152
8.3無限集155
8.3.1勢155
8.3.2有限集和無限集156
8.3.3可數無限集和不可數無限集157
8.4集合勢大小的比較159
8.4.1集合勢的大小159
8.4.2伯恩斯坦定理159
8.5鴿巢原理160
8.6典型例題161
習題162
第9章圖論165
9.1圖的基本概念165
9.1.1有向圖和無向圖166
9.1.2圖的同構、子圖和補圖167
9.1.3頂點的度168
9.2圖中的通路、圖的連通性和圖的矩陣表示169
9.2.1通路、回路和連通性169
9.2.2圖的矩陣表示171
9.3帶權圖與帶權圖中的最短通路174
9.4歐拉圖176
9.5哈密頓圖180
9.6二部圖183
9.7平面圖與平面圖的著色186
9.7.1平面圖186
9.7.2平面圖的著色189
9.8典型例題191
習題192
第10章樹和有序樹197
10.1樹的基本概念197
10.2連通圖的生成樹和帶權連通圖的最小生成樹199
10.3有序樹202
10.3.1根樹202
10.3.2根樹的應用203
10.4前綴碼和最優2分樹206
10.4.1前綴碼206
10.4.2最優2分樹207
10.4.3赫夫曼編碼210
10.5典型例題211
習題213
第11章群和環216
11.1代數運算的基本概念216
11.1.1代數運算216
11.1.2交換律、結合律217
11.1運算218
11.2代數繫統和半群219
11.2.1代數繫統219
11.2.2同態映射和同構映射219
11.2.3半群與含幺半群221
11.3群的基本概念223
11.3223
11.3.2群的定義223
11.3.3群的同態、同構226
11.3.4無限群、有限群、交的階228
11.4群的幾個等價定義230
11.5變換群和置換群231
11.5.1變換群231
11.5.2置換群232
11.6循環群235
11.7子群237
11.7.1子群的定義237
11.7.2子群的判定定理237
11.8子群的陪集239
11.8.1按子群劃分的剩餘類239
11.8.2右陪集239
11.8.3左陪集241
11.8.4拉格朗日定理242
11.9正規子群和商群244
11.9.1正規子群244
11.9.2商群245
11.10環和域247
11.10.1環、子環與理想248
11.10.2交換環和整環248
11.10.3除環和域249
11.11典型例題249
習題253
第12章格與布爾代數256
12.1格定義的代數繫統256
12.2格258
12.2.1格的代數定義258
12.2.2子格260
12.2.3格的同態和同構260
12.3一些特殊的格261
12.3.1分配格261
12.3.2布爾格和布爾代數263
12.4有限布爾代數的唯一性263
12.4.1原子263
12.4.2有限布爾代素的表達264
12.4.3布爾代數的同構265
12.5布爾表達式和布爾函數266
12.5.1布爾表達式266
12.5.2布爾函數267
12.6典型例題269
習題270
參考文獻272

離散數學是計算機科學與技術重要的理論基礎課程，它不僅是計算機科學的核心課程，而且已成為電子信息類專業的熱門選修課。離散數學與計算機科學有著十分密切的關繫。無論是數字計算機雛形的圖靈機，還是數字電路的布爾代數，以及程序設計工具的語言、關繫數據庫、知識表示、人工智能等領域均離不開離散數學；同時兩者的相互滲透推動了離散數學的發展。因此，學好離散數學對計算機科學與理論的研究有著重要的作用。
離散數學以研究離散量的結構和相互間的關繫為主要目標，旨在介紹離散數學各個分支的基本概念、基本理論和基本方法。本書以離散數學課程重要知識點為紐帶，夯實程序設計思路，拓展數據和關繫的表示方法，強化從實例計算到模型計算的應用能力，使讀者充分掌握問題-形式化-自動化（計算機化）方法，為後續的學習和科學研究打下良好的基礎。
本書基於全國高等學校計算機教育研究會的教材規範對離散數學教學內容進行編著，強化了離散數學的相關概念及其應用，注重相關課程內容的相互滲透。本書共12章，主要內容包括命題演算基礎、命題演算的推理理論、謂詞演算基礎、謂詞演算的推理理論、遞歸函數論、集合、關繫、函數與集合的勢、圖論、樹和有序樹、群和環、格與布爾代數。
本書第1、2、3、4、5、7、9、10、11章由朱保平編寫，第6、8、12章由金忠編寫，第6~12章由葉有培教授統一策劃。第1~11章微課視頻由朱保平錄制，第12章微課視頻由金忠錄制。
由於作者水平有限，書中難免存在疏漏和不足之處，懇請讀者批評指正。

作者
2023年8月
於南京理工大學