離散數(shù)學

目錄 第1章命題演算基礎1
1.1命題和聯(lián)結詞1
1.1.1命題1
1.1.2聯(lián)結詞2
1.1.3合式公式6
1.1.4命題邏輯的應用6
1.2真假性9
1.2.1解釋9
1.2.2等價公式10
1.2.3聯(lián)結詞的完備集12
1.2.4對偶式和內(nèi)否式13
1.3范式及其應用15
1.3.1范式15
1.3.2主范式17
1.3.3范式的應用20
1.4典型例題21
習題23
第2章命題演算的推理理論26
2.1命題演算的公理系統(tǒng)26
2.1.1公理系統(tǒng)的組成部分27
2.1.2公理系統(tǒng)的推理過程28
2.2若干重要的導出規(guī)則30
2.2.1分離規(guī)則的討論30
2.2.2公理和定理的導出規(guī)則30
2.3命題演算的假設推理系統(tǒng)32
2.3.1假設推理系統(tǒng)的組成32
2.3.2假設推理系統(tǒng)的推理過程33〖1〗離 散 數(shù) 學 〖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函數(shù)項和量詞48
3.2.1函數(shù)項48
3.2.2量詞49
3.3自由變元和約束變元51
3.3.1自由出現(xiàn)和約束出現(xiàn)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謂詞演算的永真推理系統(tǒng)65
4.1.1公理系統(tǒng)的組成部分65
4.1.2公理系統(tǒng)的推理過程67
4.2謂詞演算的假設推理系統(tǒng)68
4.2.1假設推理系統(tǒng)的組成及證明方法68
4.2.2定理的假設推導過程69
4.3謂詞演算的歸結推理系統(tǒng)71
4.3.1置換72
4.3.2歸結反演系統(tǒng)72
4.3.3霍恩子句邏輯程序75
4.4Prolog簡介78
4.5典型例題80
習題82
第5章遞歸函數(shù)論85
5.1數(shù)論函數(shù)和數(shù)論謂詞85
5.1.1數(shù)論函數(shù)85
5.1.2數(shù)論謂詞和特征函數(shù)86
5.2函數(shù)的構造88
5.2.1迭置法88
5.2.2算子法90
5.2.3原始遞歸函數(shù)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自然數(shù)與自然數(shù)集105
6.4.1后繼105
6.4.2自然數(shù)和自然數(shù)集105
6.4.3皮亞諾公理假設106
6.4.4自然數(shù)集的性質(zhì)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二元關系與數(shù)據(jù)結構122
7.2.4二元關系的運算122
7.3n元關系及其運算125
7.3.1n元關系125
7.3.2n元關系的運算125
7.4二元關系的性質(zhì)128
7.4.1自反性、反自反性、對稱性、反對稱性、傳遞性和反傳遞性128
7.4.2二元關系性質(zhì)的判定定理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章函數(shù)與集合的勢157
8.1函數(shù)的基本概念157
8.1.1函數(shù)(映射)的定義157
8.1.2函數(shù)的性質(zhì)159
8.2函數(shù)的復合和逆函數(shù)160
8.2.1函數(shù)的復合160
8.2.2左可逆函數(shù)、右可逆函數(shù)和逆函數(shù)162
8.3無限集164
8.3.1勢164
8.3.2有限集和無限集166
8.3.3可數(shù)無限集和不可數(shù)無限集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前綴碼和最優(yōu)2分樹218
10.4.1前綴碼218
10.4.2最優(yōu)2分樹220
10.4.3赫夫曼編碼222
10.5典型例題224
習題226
第11章群和環(huán)229
11.1代數(shù)運算的基本概念229
11.1.1代數(shù)運算229
11.1.2交換律、結合律230
11.1.3n元運算231
11.2代數(shù)系統(tǒng)和半群232
11.2.1代數(shù)系統(tǒng)232
11.2.2同態(tài)映射和同構映射233
11.2.3半群與含幺半群235
11.3群的基本概念236
11.3.1逆元236
11.3.2群的定義237
11.3.3群的同態(tài)、同構240
11.3.4無限群、有限群、交換群和元的階242
11.4群的幾個等價定義244
11.5變換群和置換群245
11.5.1變換群246
11.5.2置換群247
11.6循環(huán)群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正規(guī)子群和商群259
11.9.1正規(guī)子群259
11.9.2商群260
11.10環(huán)和域262
11.10.1環(huán)、子環(huán)與理想263
11.10.2交換環(huán)和整環(huán)264
11.10.3除環(huán)和域264
11.11典型例題265
習題268
第12章格與布爾代數(shù)271
12.1格定義的代數(shù)系統(tǒng)271
12.2格的代數(shù)定義273
12.2.1格的代數(shù)定義273
12.2.2子格275
12.2.3格的同態(tài)和同構275
12.3一些特殊的格276
12.3.1分配格276
12.3.2布爾格和布爾代數(shù)278
12.4有限布爾代數(shù)的唯一性279
12.4.1原子279
12.4.2有限布爾代數(shù)非零元素的表達279
12.4.3布爾代數(shù)的同構280
12.5布爾表達式和布爾函數(shù)282
12.5.1布爾表達式282
12.5.2布爾函數(shù)283
12.6典型例題285
習題286
參考文獻288