離散數學（簡體書）

《離散數學》是全國高等學校計算機教育研究會支持的立項教材，較全面地介紹了離散數學的基本理論及基本方法。該書以離散數學課程重要知識點為紐帶，夯實程序設計思路，拓展數據和關係的表示方法，強化從實例計算到模型計算和問題-形式化-自動化（計算機化）等方法，旨在為後續的科學研究打下良好的基礎。全書由命題演算基礎、命題演算的推理理論、謂詞演算基礎、謂詞演算的推理理論、遞歸函數論、集合、關係、函數與集合的勢、圖論、樹和有序樹、群和環、格與布爾代數共12章組成。
《離散數學》可作為高等院校計算機科學與技術及相關專業離散數學課程教材，也可作為教師、研究生或軟件技術人員的參考書。

目錄 第1章命題演算基礎1
1.1命題和聯結詞1
1.1.1命題1
1.1.2聯結詞2
1.1.3合式公式6
1.1.4命題邏輯的應用6
1.2真假性9
1.2.1解釋9
1.2.2等價公式10
1.2.3聯結詞的完備集12
1.2.4對偶式和內否式13
1.3范式及其應用15
1.3.1範式15
1.3.2主範式17
1.3.3范式的應用20
1.4典型例題21
習題23
第2章命題演算的推理理論26
2.1命題演算的公理系統26
2.1.1公理系統的組成部分27
2.1.2公理系統的推理過程28
2.2若干重要的導出規則30
2.2.1分離規則的討論30
2.2.2公理和定理的導出規則30
2.3命題演算的假設推理系統32
2.3.1假設推理系統的組成32
2.3.2假設推理系統的推理過程33〖1〗離 散 數 學 〖1〗目錄 2.3.3額外假設推理法35
2.4命題演算的歸結推理法37
2.4.1歸結證明過程38
2.4.2歸結證明示例39
2.5典型例題40
習題43
第3章謂詞演算基礎45
3.1謂詞和個體45
3.1.1個體45
3.1.2謂詞45
3.2函數項和量詞48
3.2.1函數項48
3.2.2量詞49
3.3自由變元和約束變元51
3.3.1自由出現和約束出現51
3.3.2改名和代入51
3.4永真性和可滿足性53
3.4.1真假性53
3.4.2同真假性、永真性和可滿足性55
3.4.3範式58
3.5唯一性量詞和摹狀詞59
3.5.1唯一性量詞59
3.5.2摹狀詞60
3.6典型例題61
習題62
第4章謂詞演算的推理理論65
4.1謂詞演算的永真推理系統65
4.1.1公理系統的組成部分65
4.1.2公理系統的推理過程67
4.2謂詞演算的假設推理系統68
4.2.1假設推理系統的組成及證明方法68
4.2.2定理的假設推導過程69
4.3謂詞演算的歸結推理系統71
4.3.1置換72
4.3.2歸結反演系統72
4.3.3霍恩子句邏輯程序75
4.4Prolog簡介78
4.5典型例題80
習題82
第5章遞歸函數論85
5.1數論函數和數論謂詞85
5.1.1數論函數85
5.1.2數論謂詞和特徵函數86
5.2函數的構造88
5.2.1迭置法88
5.2.2算子法90
5.2.3原始遞歸函數91
5.3典型例題92
習題92
第6章集合94
6.1集合的基本概念94
6.1.1集合的定義94
6.1.2集合的表示95
6.1.3集合的包含關係96
6.1.4集合的特點97
6.1.5多重集97
6.2集合的基本運算98
6.2.1集合的並、交、差98
6.2.2集合的對稱差99
6.2.3文氏圖100
6.2.4集合的冪集合101
6.2.5多個集合的並與交101
6.3全集和補集102
6.3.1全集和補集的定義102
6.3.2基本運算定理103
6.3.3集合的計算機表示104
6.4自然數與自然數集105
6.4.1後繼105
6.4.2自然數和自然數集105
6.4.3皮亞諾公理假設106
6.4.4自然數集的性質107
6.4.5集合的遞歸定義與遞歸子程序108
6.5包含與排斥原理110
6.6典型例題112
習題113
第7章關係118
7.1集合的笛卡兒積集118
7.1.1有序二元組118
7.1.2笛卡兒積集118
7.1.3有序n元組、n個集合的笛卡兒積集119
7.2二元關係的基本概念120
7.2.1二元關係120
7.2.2二元關係的表示120
7.2.3二元關係與數據結構122
7.2.4二元關係的運算122
7.3n元關係及其運算125
7.3.1n元關係125
7.3.2n元關係的運算125
7.4二元關係的性質128
7.4.1自反性、反自反性、對稱性、反對稱性、傳遞性和反傳遞性128
7.4.2二元關係性質的判定定理130
7.5二元關係的閉包運算132
7.5.1自反閉包、對稱閉包和傳遞閉包132
7.5.2閉包的判定定理132
7.6等價關係和集合的劃分137
7.6.1等價關係和等價類137
7.6.2商集合138
7.6.3集合的劃分138
7.7偏序關係和格141
7.7.1偏序關係和偏序集141
7.7.2哈斯圖142
7.7.3鏈、反鏈、全序集142
7.7.4極大元、極小元、最大元和最小元143
7.7.5上界、下界、最小上界和最大下界143
7.7.6格144
7.7.7拓撲排序145
7.8粗糙集概論147
7.8.1知識與知識分類147
7.8.2集合近似與粗糙集概念150
7.9典型例題151
習題152
第8章函數與集合的勢157
8.1函數的基本概念157
8.1.1函數(映射)的定義157
8.1.2函數的性質159
8.2函數的複合和逆函數160
8.2.1函數的複合160
8.2.2左可逆函數、右可逆函數和逆函數162
8.3無限集164
8.3.1勢164
8.3.2有限集和無限集166
8.3.3可數無限集和不可數無限集166
8.4集合勢大小的比較168
8.4.1集合勢的大小168
8.4.2伯恩斯坦定理169
8.5鴿巢原理169
8.6典型例題171
習題172
第9章圖論175
9.1圖的基本概念175
9.1.1有向圖和無向圖176
9.1.2圖的同構、子圖和補圖177
9.1.3頂點的度178
9.2圖中的通路、圖的連通性和圖的矩陣表示179
9.2.1通路、回路和連通性179
9.2.2圖的矩陣表示181
9.3帶權圖與帶權圖中的最短通路184
9.4歐拉圖187
9.5哈密頓圖190
9.6二部圖194
9.7平面圖與平面圖的著色197
9.7.1平面圖197
9.7.2平面圖的著色200
9.8典型例題203
習題204
第10章樹和有序樹209
10.1樹的基本概念209
10.2連通圖的生成樹和帶權連通圖的最小生成樹211
10.3有序樹214
10.3.1根樹214
10.3.2根樹的應用216
10.4前綴碼和最優2分樹218
10.4.1前綴碼218
10.4.2最優2分樹220
10.4.3赫夫曼編碼222
10.5典型例題224
習題226
第11章群和環229
11.1代數運算的基本概念229
11.1.1代數運算229
11.1.2交換律、結合律230
11.1.3n元運算231
11.2代數系統和半群232
11.2.1代數系統232
11.2.2同態映射和同構映射233
11.2.3半群與含么半群235
11.3群的基本概念236
11.3.1逆元236
11.3.2群的定義237
11.3.3群的同態、同構240
11.3.4無限群、有限群、交換群和元的階242
11.4群的幾個等價定義244
11.5變換群和置換群245
11.5.1變換群246
11.5.2置換群247
11.6循環群250
11.7子群252
11.7.1子群的定義252
11.7.2子群的判定定理252
11.8子群的陪集254
11.8.1按子群劃分的剩餘類254
11.8.2右陪集254
11.8.3左陪集256
11.8.4拉格朗日定理257
11.9正規子群和商群259
11.9.1正規子群259
11.9.2商群260
11.10環和域262
11.10.1環、子環與理想263
11.10.2交換環和整環264
11.10.3除環和域264
11.11典型例題265
習題268
第12章格與布爾代數271
12.1格定義的代數系統271
12.2格的代數定義273
12.2.1格的代數定義273
12.2.2子格275
12.2.3格的同態和同構275
12.3一些特殊的格276
12.3.1分配格276
12.3.2布爾格和布爾代數278
12.4有限布爾代數的唯一性279
12.4.1原子279
12.4.2有限布爾代數非零元素的表達279
12.4.3布爾代數的同構280
12.5布爾表達式和布爾函數282
12.5.1布爾表達式282
12.5.2布爾函數283
12.6典型例題285
習題286
參考文獻288