離散數(shù)學

第1章命題邏輯1
1.1現(xiàn)代邏輯學的基本研究方法1
1.1.1思維： 感知的概念化和理性化1
1.1.2現(xiàn)代邏輯學求助數(shù)學——符號化2
1.1.3現(xiàn)代邏輯學追隨數(shù)學——公理化2
1.1.4現(xiàn)代邏輯學改造數(shù)學——形式化3
1.2命題及其表示法4
1.2.1命題的概念4
1.2.2復合命題4
1.2.3聯(lián)結(jié)詞5
1.2.4復合命題真假值7
1.3命題公式與翻譯9
1.3.1命題公式的定義9
1.3.2公式的層次10
1.3.3翻譯10
1.4真值表與等價公式11
1.4.1真值表11
1.4.2等價公式12
1.5重言式與等值演算12
1.5.1重言式12
1.5.2等值演算14
1.6對偶與范式16
1.6.1對偶16
1.6.2簡單合取式和簡單析取式17
1.6.3范式18
1.6.4范式的唯一性——主范式20
1.7其他聯(lián)結(jié)詞25
1.7.1n元真值函數(shù)26
1.7.2真值函數(shù)與命題公式的關(guān)系26
1.7.3聯(lián)結(jié)詞完備集27
1.7.4單元素聯(lián)結(jié)詞構(gòu)成的聯(lián)結(jié)詞完備集28
1.8推理理論29
1.8.1有效推理29
1.8.2有效推理的等價定理30
1.8.3重言蘊涵式32
1.8.4形式推理系統(tǒng)P134
1.8.5自然推理系統(tǒng)P235
習題41
第2章謂詞邏輯51
2.1謂詞邏輯的基本概念51
2.1.1個體詞52
2.1.2謂詞52
2.1.3量詞53
2.2謂詞邏輯公式與翻譯54
2.2.1一階語言54
2.2.2自由與約束55
2.2.3閉公式56
2.2.4謂詞邏輯公式的解釋57
2.2.5謂詞邏輯命題符號化58
2.2.6謂詞邏輯公式的分類61
2.3謂詞邏輯等值演算62
2.3.1基本等價式與置換規(guī)則62
2.3.2謂詞邏輯前束范式66
2.4謂詞演算的推理理論68
2.4.1推理定律68
2.4.2量詞消去與引入規(guī)則69
2.4.3一階謂詞演算公理系統(tǒng)F169
2.4.4自然推理系統(tǒng)F271
2.5邏輯在計算機科學中的作用73
2.5.1邏輯與計算73
2.5.2邏輯與計算機的起源74
2.5.3邏輯與程序設計75
習題76離散數(shù)學目錄
第3章集合與關(guān)系82
3.1集合的概念和表示法82
3.1.1集合的表示82
3.1.2集合的基本概念84
3.2集合的運算85
3.2.1集合的基本運算85
3.2.2有窮計數(shù)集86
3.2.3廣義交和廣義并87
3.3有序?qū)εc笛卡兒積89
3.4關(guān)系及其表示91
3.4.1關(guān)系的基本概念91
3.4.2關(guān)系表示法92
3.5關(guān)系的運算94
3.5.1基本概念94
3.5.2復合關(guān)系95
3.5.3逆關(guān)系96
3.5.4關(guān)系冪98
3.5.5冪運算的性質(zhì)99
3.6關(guān)系的性質(zhì)101
3.6.1關(guān)系的五種基本性質(zhì)101
3.6.2關(guān)系性質(zhì)的等價描述102
3.7關(guān)系的閉包106
3.7.1閉包的基本概念106
3.7.2閉包的性質(zhì)110
3.8集合的劃分與覆蓋111
3.9等價關(guān)系和等價類112
3.9.1等價關(guān)系112
3.9.2等價類的性質(zhì)114
3.9.3商集與劃分115
3.10偏序關(guān)系116
3.11偏序集與哈斯圖117
3.12包含排斥原理120
習題121
第4章函數(shù)128
4.1函數(shù)的定義128
4.1.1函數(shù)和像128
4.1.2函數(shù)的性質(zhì)130
4.1.3常用函數(shù)131
4.2復合函數(shù)和反函數(shù)132
4.2.1復合函數(shù)132
4.2.2反函數(shù)134
4.3特征函數(shù)與模糊子集136
4.3.1特征函數(shù)136
4.3.2模糊集合137
4.4基數(shù)的概念138
4.4.1后繼與歸納集138
4.4.2自然數(shù)，有窮集，無窮集139
4.4.3基數(shù)144
4.5可數(shù)集與不可數(shù)集144
4.6數(shù)學歸納法146
4.6.1歸納法證明146
4.6.2數(shù)學歸納法第一原理146
4.6.3數(shù)學歸納法第二原理147
習題149
第5章圖論153
5.1圖的基本概念153
5.1.1圖的定義和表示153
5.1.2圖的同構(gòu)157
5.1.3完全圖與正則圖159
5.1.4子圖與補圖159
5.1.5通路與回路161
5.2圖的連通性163
5.2.1無向圖的連通性163
5.2.2有向圖的連通性165
5.3圖的矩陣表示165
5.3.1關(guān)聯(lián)矩陣165
5.3.2有向圖的鄰接矩陣166
5.3.3有向圖的可達矩陣168
5.4二部圖168
5.4.1二部圖及判別定理168
5.4.2完備匹配169
5.5歐拉圖171
5.6哈密頓圖174
5.7平面圖177
5.7.1平面圖及其判定定理177
5.7.2平面圖的對偶圖183
5.8帶權(quán)圖184
習題185
第6章樹及其應用193
6.1樹的術(shù)語和性質(zhì)193
6.1.1樹的定義及相關(guān)術(shù)語193
6.1.2樹的性質(zhì)195
6.2生成樹196
6.3最小生成樹199
6.4樹的遍歷202
6.5二叉樹204
6.5.1二叉樹的性質(zhì)204
6.5.2二叉搜索樹205
6.5.3赫夫曼樹206
6.6決策樹207
6.6.1決策樹的定義207
6.6.2最短時間排序209
6.7樹的同構(gòu)209
6.8博弈樹213
6.8.1博弈樹的概念213
6.8.2極大極小分析法213
6.8.3αβ剪枝技術(shù)216
習題218
第7章計數(shù)方法與鴿巢原理222
7.1基本原理222
7.1.1加法原理222
7.1.2乘法原理223
7.2排列與組合224
7.2.1排列224
7.2.2組合224
7.3排列組合生成算法225
7.3.1排列生成算法225
7.3.2組合生成算法226
7.4離散概率論229
7.4.1離散概率簡介229
7.4.2有限概率230
7.4.3條件概率與獨立性232
7.4.4Bayes定理233
7.5廣義的排列和組合234
7.6二項式系數(shù)和組合恒等式236
7.6.1二項式定理236
7.6.2組合恒等式238
7.7鴿巢原理239
7.7.1鴿巢原理的簡單形式239
7.7.2鴿巢原理的一般形式240
習題241
第8章數(shù)論與遞歸關(guān)系243
8.1素數(shù)243
8.2最大公約數(shù)與最小公倍數(shù)244
8.3同余247
8.4一次同余方程和中國剩余定理249
8.4.1一次同余方程249
8.4.2中國剩余定理250
8.5數(shù)論在密碼學中的應用251
8.5.1公鑰密碼學251
8.5.2RSA密碼252
8.6遞歸關(guān)系簡介252
8.6.1遞歸定義函數(shù)252
8.6.2遞歸定義集合254
8.6.3遞推關(guān)系模型255
8.7求解遞歸關(guān)系257
8.8遞歸在算法分析中的應用259
習題262
第9章代數(shù)系統(tǒng)264
9.1二元運算及其性質(zhì)264
9.1.1定義和表示264
9.1.2二元運算的性質(zhì)266
9.2代數(shù)系統(tǒng)268
9.2.1定義和實例268
9.2.2子代數(shù)系統(tǒng)270
9.2.3代數(shù)系統(tǒng)的同態(tài)與同構(gòu)270
9.3半群與獨異點271
9.3.1定義與性質(zhì)271
9.3.2子系統(tǒng)與直積272
9.4群273
9.4.1群的定義273
9.4.2群的性質(zhì)275
9.4.3子群的定義277
9.4.4正規(guī)子群與商群278
9.4.5群的同態(tài)與同構(gòu)實例281
9.4.6循環(huán)群與置換群284
9.5環(huán)與域286
9.5.1環(huán)286
9.5.2域287
9.6格與布爾代數(shù)288
9.6.1格288
9.6.2布爾代數(shù)292
9.7組合電路295
習題297
第10章自動機、文法和語言305
10.1串和語言305
10.2形式文法306
10.3有限狀態(tài)機309
10.4有限狀態(tài)自動機311
10.5不確定有限狀態(tài)自動機314
10.6語言和自動機之間的關(guān)系317
習題318
附錄A歷史注記322
參考文獻332