離散數(shù)學(xué)

目錄 第1章命題演算基礎(chǔ)1
1.1命題和聯(lián)結(jié)詞1
1.1.1命題1
1.1.2聯(lián)結(jié)詞2
1.1.3合式公式6
1.1.4命題邏輯的應(yīng)用6
1.2真假性9
1.2.1解釋9
1.2.2等價公式10
1.2.3聯(lián)結(jié)詞的完備集12
1.2.4對偶式和內(nèi)否式13
1.3范式及其應(yīng)用15
1.3.1范式15
1.3.2主范式17
1.3.3范式的應(yīng)用20
1.4典型例題21
習(xí)題23
第2章命題演算的推理理論26
2.1命題演算的公理系統(tǒng)26
2.1.1公理系統(tǒng)的組成部分27
2.1.2公理系統(tǒng)的推理過程28
2.2若干重要的導(dǎo)出規(guī)則30
2.2.1分離規(guī)則的討論30
2.2.2公理和定理的導(dǎo)出規(guī)則30
2.3命題演算的假設(shè)推理系統(tǒng)32
2.3.1假設(shè)推理系統(tǒng)的組成32
2.3.2假設(shè)推理系統(tǒng)的推理過程33〖1〗離 散 數(shù) 學(xué) 〖1〗目錄 2.3.3額外假設(shè)推理法35
2.4命題演算的歸結(jié)推理法37
2.4.1歸結(jié)證明過程38
2.4.2歸結(jié)證明示例39
2.5典型例題40
習(xí)題43
第3章謂詞演算基礎(chǔ)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
習(xí)題62
第4章謂詞演算的推理理論65
4.1謂詞演算的永真推理系統(tǒng)65
4.1.1公理系統(tǒng)的組成部分65
4.1.2公理系統(tǒng)的推理過程67
4.2謂詞演算的假設(shè)推理系統(tǒng)68
4.2.1假設(shè)推理系統(tǒng)的組成及證明方法68
4.2.2定理的假設(shè)推導(dǎo)過程69
4.3謂詞演算的歸結(jié)推理系統(tǒng)71
4.3.1置換72
4.3.2歸結(jié)反演系統(tǒng)72
4.3.3霍恩子句邏輯程序75
4.4Prolog簡介78
4.5典型例題80
習(xí)題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ù)的構(gòu)造88
5.2.1迭置法88
5.2.2算子法90
5.2.3原始遞歸函數(shù)91
5.3典型例題92
習(xí)題92
第6章集合94
6.1集合的基本概念94
6.1.1集合的定義94
6.1.2集合的表示95
6.1.3集合的包含關(guān)系96
6.1.4集合的特點97
6.1.5多重集97
6.2集合的基本運(yùn)算98
6.2.1集合的并、交、差98
6.2.2集合的對稱差99
6.2.3文氏圖100
6.2.4集合的冪集合101
6.2.5多個集合的并與交101
6.3全集和補(bǔ)集102
6.3.1全集和補(bǔ)集的定義102
6.3.2基本運(yùn)算定理103
6.3.3集合的計算機(jī)表示104
6.4自然數(shù)與自然數(shù)集105
6.4.1后繼105
6.4.2自然數(shù)和自然數(shù)集105
6.4.3皮亞諾公理假設(shè)106
6.4.4自然數(shù)集的性質(zhì)107
6.4.5集合的遞歸定義與遞歸子程序108
6.5包含與排斥原理110
6.6典型例題112
習(xí)題113
第7章關(guān)系118
7.1集合的笛卡兒積集118
7.1.1有序二元組118
7.1.2笛卡兒積集118
7.1.3有序n元組、n個集合的笛卡兒積集119
7.2二元關(guān)系的基本概念120
7.2.1二元關(guān)系120
7.2.2二元關(guān)系的表示120
7.2.3二元關(guān)系與數(shù)據(jù)結(jié)構(gòu)122
7.2.4二元關(guān)系的運(yùn)算122
7.3n元關(guān)系及其運(yùn)算125
7.3.1n元關(guān)系125
7.3.2n元關(guān)系的運(yùn)算125
7.4二元關(guān)系的性質(zhì)128
7.4.1自反性、反自反性、對稱性、反對稱性、傳遞性和反傳遞性128
7.4.2二元關(guān)系性質(zhì)的判定定理130
7.5二元關(guān)系的閉包運(yùn)算132
7.5.1自反閉包、對稱閉包和傳遞閉包132
7.5.2閉包的判定定理132
7.6等價關(guān)系和集合的劃分137
7.6.1等價關(guān)系和等價類137
7.6.2商集合138
7.6.3集合的劃分138
7.7偏序關(guān)系和格141
7.7.1偏序關(guān)系和偏序集141
7.7.2哈斯圖142
7.7.3鏈、反鏈、全序集142
7.7.4極大元、極小元、最大元和最小元143
7.7.5上界、下界、最小上界和最大下界143
7.7.6格144
7.7.7拓?fù)渑判?45
7.8粗糙集概論147
7.8.1知識與知識分類147
7.8.2集合近似與粗糙集概念150
7.9典型例題151
習(xí)題152
第8章函數(shù)與集合的勢157
8.1函數(shù)的基本概念157
8.1.1函數(shù)(映射)的定義157
8.1.2函數(shù)的性質(zhì)159
8.2函數(shù)的復(fù)合和逆函數(shù)160
8.2.1函數(shù)的復(fù)合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
習(xí)題172
第9章圖論175
9.1圖的基本概念175
9.1.1有向圖和無向圖176
9.1.2圖的同構(gòu)、子圖和補(bǔ)圖177
9.1.3頂點的度178
9.2圖中的通路、圖的連通性和圖的矩陣表示179
9.2.1通路、回路和連通性179
9.2.2圖的矩陣表示181
9.3帶權(quán)圖與帶權(quán)圖中的最短通路184
9.4歐拉圖187
9.5哈密頓圖190
9.6二部圖194
9.7平面圖與平面圖的著色197
9.7.1平面圖197
9.7.2平面圖的著色200
9.8典型例題203
習(xí)題204
第10章樹和有序樹209
10.1樹的基本概念209
10.2連通圖的生成樹和帶權(quán)連通圖的最小生成樹211
10.3有序樹214
10.3.1根樹214
10.3.2根樹的應(yīng)用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
習(xí)題226
第11章群和環(huán)229
11.1代數(shù)運(yùn)算的基本概念229
11.1.1代數(shù)運(yùn)算229
11.1.2交換律、結(jié)合律230
11.1.3n元運(yùn)算231
11.2代數(shù)系統(tǒng)和半群232
11.2.1代數(shù)系統(tǒng)232
11.2.2同態(tài)映射和同構(gòu)映射233
11.2.3半群與含幺半群235
11.3群的基本概念236
11.3.1逆元236
11.3.2群的定義237
11.3.3群的同態(tài)、同構(gòu)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
習(xí)題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)和同構(gòu)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ù)非零元素的表達(dá)279
12.4.3布爾代數(shù)的同構(gòu)280
12.5布爾表達(dá)式和布爾函數(shù)282
12.5.1布爾表達(dá)式282
12.5.2布爾函數(shù)283
12.6典型例題285
習(xí)題286
參考文獻(xiàn)288