前言
教學(xué)建議
第一部分　數(shù)理邏輯
第1章　命題邏輯2
　1.1　命題與聯(lián)結(jié)詞2
　　1.1.1　命題的概念2
　　1.1.2　聯(lián)結(jié)詞3
　1.2　命題公式及其分類8
　1.3　命題演算的關(guān)系式10
　　1.3.1　等價(jià)關(guān)系式10
　　1.3.2　全功能聯(lián)結(jié)詞集13
　　1.3.3　對(duì)偶式14
　1.4　范式15
　　1.4.1　析取范式和合取范式15
　　1.4.2　主析取范式和主合取范式16
　1.5　命題演算的推理20
　　1.5.1　推理理論20
　　1.5.2　推理證明方法21
　習(xí)題25
第2章　謂詞邏輯29
　2.1　謂詞邏輯的基本概念29
　　2.1.1　個(gè)體詞和謂詞29
　　2.1.2　量詞31
　2.2　謂詞合式公式34
　2.3　謂詞公式的解釋和分類35
　　2.3.1　謂詞公式的解釋35
　　2.3.2　謂詞公式的分類36
　2.4　謂詞演算的關(guān)系式37
　2.5　前束范式40
　2.6　謂詞演算的推理41
　　2.6.1　推理理論41
　　2.6.2　推理問(wèn)題的證明43
　習(xí)題48
第二部分　集合、關(guān)系和函數(shù)
第3章　集合54
　3.1　集合及其表示54
　3.2　集合間的關(guān)系55
　3.3　集合的運(yùn)算57
　3.4　自然數(shù)62
　3.5　集合的特征函數(shù)63
　習(xí)題64
第4章　關(guān)系和函數(shù)67
　4.1　關(guān)系的概念67
　　4.1.1　有序?qū)�和有序n元組67
　　4.1.2　笛卡兒積67
　　4.1.3　關(guān)系的概念69
　4.2　關(guān)系的表示法71
　　4.2.1　用集合表示關(guān)系71
　　4.2.2　用關(guān)系圖表示關(guān)系72
　　4.2.3　用矩陣表示關(guān)系73
　4.3　關(guān)系的運(yùn)算73
　　4.3.1　關(guān)系的逆運(yùn)算74
　　4.3.2　關(guān)系的復(fù)合運(yùn)算75
　4.4　關(guān)系的性質(zhì)79
　4.5　關(guān)系的閉包85
　4.6　等價(jià)關(guān)系和等價(jià)類91
　　4.6.1　等價(jià)關(guān)系91
　　4.6.2　等價(jià)類92
　4.7　偏序關(guān)系96
　4.8　函數(shù)100
　　4.8.1　函數(shù)的定義100
　　4.8.2　特殊函數(shù)101
　　4.8.3　復(fù)合函數(shù)103
　　4.8.4　反函數(shù)105
　　4.8.5　集合的基數(shù)106
　習(xí)題108
第三部分　組合數(shù)學(xué)
第5章　計(jì)數(shù)114
　5.1　基本計(jì)數(shù)法則114
　　5.1.1　加法法則114
　　5.1.2　乘法法則115
　5.2　排列與組合117
　　5.2.1　排列117
　　5.2.2　組合118
　　5.2.3　多重集的排列與組合119
　　5.2.4　二項(xiàng)式定理120
　5.3　容斥原理121
　5.4　鴿巢原理125
　習(xí)題126
第6章　高級(jí)計(jì)數(shù)技術(shù)128
　6.1　遞推方程128
　　6.1.1　求解遞推方程130
　　6.1.2　常系數(shù)線性齊次遞推方程的求解130
　　6.1.3　常系數(shù)線性非齊次遞推方程的求解133
　6.2　生成函數(shù)136
　　6.2.1　牛頓二項(xiàng)式系數(shù)與牛頓二項(xiàng)式定理136
　　6.2.2　生成函數(shù)的定義及其性質(zhì)138
　　6.2.3　生成函數(shù)的應(yīng)用139
　　6.2.4　指數(shù)型生成函數(shù)142
　習(xí)題144
第四部分　圖　　論
第7章　圖論148
　7.1　圖的基本概念148
　　7.1.1　無(wú)向圖和有向圖148
　　7.1.2　度的概念150
　　7.1.3　圖的分類151
　　7.1.4　子圖與補(bǔ)圖155
　　7.1.5　圖的同構(gòu)157
　7.2　通路與回路、連通的概念158
　　7.2.1　通路與回路158
　　7.2.2　連通的概念160
　7.3　圖的表示164
　　7.3.1　鄰接表164
　　7.3.2　鄰接矩陣165
　　7.3.3　可達(dá)矩陣169
　　7.3.4　關(guān)聯(lián)矩陣169
　7.4　圖的運(yùn)算172
　習(xí)題172
第8章　特殊圖176
　8.1　歐拉圖與哈密頓圖176
　　8.1.1　歐拉圖176
　　8.1.2　哈密頓圖178
　8.2　帶權(quán)圖182
　　8.2.1　旅行商問(wèn)題182
　　8.2.2　最短路徑問(wèn)題182
　　8.2.3　中國(guó)郵路問(wèn)題184
　8.3　匹配和二分圖185
　　8.3.1　匹配185
　　8.3.2　二分圖186
　8.4　平面圖189
　　8.4.1　平面圖的定義189
　　8.4.2　平面圖的歐拉公式191
　　8.4.3　對(duì)偶圖與著色194
　習(xí)題197
第9章　樹(shù)200
　9.1　樹(shù)的定義和特性200
　9.2　生成樹(shù)202
　　9.2.1　生成樹(shù)的定義202
　　9.2.2　最小生成樹(shù)及其應(yīng)用203
　9.3　根樹(shù)205
　　9.3.1　有向根樹(shù)和有序根樹(shù)205
　　9.3.2　有序根樹(shù)的遍歷208
　9.4　根樹(shù)的應(yīng)用209
　　9.4.1　前綴碼209
　　9.4.2　最優(yōu)二元樹(shù)和赫夫曼編碼211
　　9.4.3　決策樹(shù)212
　習(xí)題213
第五部分　代數(shù)結(jié)構(gòu)
第10章　代數(shù)系統(tǒng)218
　10.1　代數(shù)系統(tǒng)的概念和性質(zhì)218
　　10.1.1　二元運(yùn)算及其性質(zhì)218
　　10.1.2　代數(shù)系統(tǒng)和子代數(shù)221
　　10.1.3　代數(shù)系統(tǒng)的性質(zhì)222
　　10.1.4　代數(shù)系統(tǒng)的分類224
　10.2　代數(shù)系統(tǒng)的同態(tài)和同構(gòu)225
　10.3　半群227
　10.4　群229
　　10.4.1　群及其基本性質(zhì)229
　　10.4.2　子群232
　10.5　循環(huán)群和置換群233
　　10.5.1　循環(huán)群233
　　10.5.2　置換群235
　10.6　環(huán)和域236
　習(xí)題238
第11章　格與布爾代數(shù)240
　11.1　格240
　　11.1.1　格的基本概念240
　　11.1.2　分配格243
　　11.1.3　有界格和有補(bǔ)格245
　11.2　布爾代數(shù)246
　　11.2.1　布爾代數(shù)的基本概念246
　　11.2.2　布爾表達(dá)式與布爾函數(shù)248
　　11.2.3　布爾代數(shù)和數(shù)字電路249
　習(xí)題251
參考文獻(xiàn)254