目　錄

第1章　命題邏輯　1
1.1　命題和聯(lián)結(jié)詞　1
1.1.1　命題的概念　1
1.1.2　聯(lián)結(jié)詞　2
1.2　合式公式與真值表　6
1.2.1　合式公式　6
1.2.2　真值表　6
1.3　永真式和等價(jià)式　7
1.3.1　永真式　7
1.3.2　等價(jià)式　8
1.3.3　代入規(guī)則和替換規(guī)則　9
1.4　對(duì)偶式與蘊(yùn)涵式　11
1.4.1　對(duì)偶式　11 目　錄

第1章　命題邏輯　1
1.1　命題和聯(lián)結(jié)詞　1
1.1.1　命題的概念　1
1.1.2　聯(lián)結(jié)詞　2
1.2　合式公式與真值表　6
1.2.1　合式公式　6
1.2.2　真值表　6
1.3　永真式和等價(jià)式　7
1.3.1　永真式　7
1.3.2　等價(jià)式　8
1.3.3　代入規(guī)則和替換規(guī)則　9
1.4　對(duì)偶式與蘊(yùn)涵式　11
1.4.1　對(duì)偶式　11
1.4.2　蘊(yùn)涵式　12
1.5　范式和判定問題　13
1.5.1　析取范式和合取范式　13
1.5.2　主析取范式和主合取范式　15
1.6　命題演算的推理理論　18
習(xí)題　21

第2章　謂詞邏輯　25
2.1　基本概念和表示　25
2.1.1　個(gè)體、謂詞和謂詞形式　25
2.1.2　量詞　26
2.1.3　合式謂詞公式　28
2.1.4　自由變?cè)�和約束變?cè)��?8
2.2　謂詞邏輯的翻譯與解釋　29
2.2.1　謂詞邏輯的翻譯　29
2.2.2　謂詞公式的解釋　30
2.3　謂詞邏輯的等價(jià)式與蘊(yùn)涵式　31
2.4　謂詞邏輯中的推論理論　32
2.4.1　推理規(guī)則　33
2.4.2　推理實(shí)例　34
2.5　謂詞邏輯中公式范式　37
2.5.1　前束范式　37
2.5.2　斯柯林范式　38
習(xí)題　39

第3章　集合論　41
3.1　集合的概念及其表示　41
3.2　集合的運(yùn)算及恒等式　43
3.3　有窮集的計(jì)數(shù)和包含排斥原理　49
習(xí)題　51

第4章　二元關(guān)系　55
4.1　多重序元與笛卡兒乘積　55
4.2　關(guān)系的基本概念　57
4.3　關(guān)系的運(yùn)算　58
4.4　關(guān)系的性質(zhì)　63
4.5　關(guān)系的表示　66
4.6　關(guān)系的閉包運(yùn)算　70
4.7　特殊關(guān)系　73
4.7.1　集合的劃分和覆蓋　73
4.7.2　等價(jià)關(guān)系　75
4.7.3　相容關(guān)系　79
4.7.4　次序關(guān)系　82
4.7.5　偏序集合與哈斯圖　84
4.8*　關(guān)系型數(shù)據(jù)庫(kù)　87
習(xí)題　88

第5章　函數(shù)　94
5.1　函數(shù)的基本概念和性質(zhì)　94
5.2　函數(shù)的合成和合成函數(shù)的性質(zhì)　97
5.3　特殊函數(shù)　99
5.4　反函數(shù)　101
5.5　特征函數(shù)　103
5.6　基數(shù)　105
5.7*　不可解問題　108
5.7.1　不可解問題的存在性　108
5.7.2　停機(jī)問題　108
習(xí)題　109

第6章　代數(shù)系統(tǒng)　112
6.1　代數(shù)系統(tǒng)的一般概念　113
6.1.1　二元運(yùn)算　113
6.1.2　代數(shù)系統(tǒng)　114
6.2　代數(shù)系統(tǒng)的基本性質(zhì)　115
6.3　同態(tài)與同構(gòu)　122
6.3.1　同態(tài)　122
6.3.2　同構(gòu)　124
6.3.3　同態(tài)與同構(gòu)的性質(zhì)　127
6.4　同余關(guān)系　128
6.5　商代數(shù)　129
6.6　積代數(shù)　130
6.7　代數(shù)系統(tǒng)實(shí)例　131
習(xí)題　132

第7章　群與環(huán)　134
7.1　半群與群的定義　134
7.2　群的性質(zhì)　136
7.3　子群與群的陪集分解　139
7.3.1　子群的概念　139
7.3.2　群的陪集與拉格朗日定理　139
7.4　循環(huán)群與置換群　140
7.4.1　循環(huán)群　140
7.4.2　置換群　141
7.5　環(huán)與域　142
7.5.1　環(huán)的概念與性質(zhì)　142
7.5.2　域的概念　143
7.6　應(yīng)用：群與網(wǎng)絡(luò)安全　144

第8章　格與布爾代數(shù)　146
8.1　格的定義與性質(zhì)　147
8.2　分配格、有補(bǔ)格與布爾代數(shù)　148
8.3　應(yīng)用　150
習(xí)題　151
　　
第9章　圖的基本概念及其矩陣表示　152
9.1　圖的基本概念　152
9.1.1　圖的定義及相關(guān)概念　152
9.1.2　節(jié)點(diǎn)的度　154
9.2　子圖和圖的運(yùn)算　157
9.2.1　子圖和補(bǔ)圖　157
9.2.2　圖的運(yùn)算　158
9.3　路徑、回路和連通性　160
9.3.1　路徑和回路　160
9.3.2　圖的連通性　162
9.4　圖的矩陣表示　165
9.4.1　鄰接矩陣　165
9.4.2　可達(dá)性矩陣　169
9.4.3　關(guān)聯(lián)矩陣　172
習(xí)題　174

第10章　幾種圖的介紹　179
10.1　歐拉圖　179
10.2　哈密爾頓圖　181
10.3　二部圖及匹配　184
10.3.1　二部圖的概念及性質(zhì)　184
10.3.2　二部圖匹配　185
10.4　平面圖　187
10.4.1　平面圖的概念及性質(zhì)　187
10.4.2　多邊形圖、對(duì)偶圖及平面圖著色　189
10.5　網(wǎng)絡(luò)　192
10.5.1　網(wǎng)絡(luò)的基本概念　192
10.5.2　網(wǎng)絡(luò)流　193
10.5.3　網(wǎng)絡(luò)最大流求解　194
10.5.4　開關(guān)網(wǎng)絡(luò)　201
10.6　圖的實(shí)例分析　208
10.6.1　中國(guó)郵遞員問題　208
10.6.2　旅行售貨員問題　210
10.6.3　排課問題　211
10.6.4　延時(shí)容忍網(wǎng)絡(luò)問題　213
10.6.5　最短路徑問題　214
習(xí)題　216

第11章　樹　221
11.1　樹與生成樹　221
11.1.1　樹及其性質(zhì)　221
11.1.2　生成樹與最小生成樹　223
11.2　有向樹及其應(yīng)用　224
11.2.1　有向樹　224
11.2.2　m叉樹　225
11.2.3　有序樹　227
11.2.4　二叉樹的遍歷　228
11.2.5　搜索樹　230
習(xí)題　232

參考文獻(xiàn)　235