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