離散結(jié)構(gòu)

第1章 命題邏輯1
1.1 命題和邏輯運算1
1.1.1 命題1
1.1.2 邏輯聯(lián)結(jié)詞和復(fù)合命題2
1.2 合式公式6
1.2.1 語法6
1.2.2 語義（semantics）7
1.3 邏輯等價8
1.4 范式12
1.4.1 析取范式12
1.4.2 合取范式13
1.4.3 用等價替換方法構(gòu)造主范式14
1.5 聯(lián)結(jié)詞的完備集及應(yīng)用15
1.5.1 聯(lián)結(jié)詞的完備集15
1.5.2 一些計算機(jī)應(yīng)用16
1.6 蘊涵和演繹19
1.7 本章小結(jié)22
習(xí)題23
第2章 一階邏輯26
2.1 謂詞和量詞26
2.1.1 謂詞26
2.1.2 量詞27
2.2 合式公式29
2.2.1 語法29
2.2.2 語義31
2.3 邏輯等價和蘊涵33
2.4 范式37
2.5 數(shù)學(xué)歸納法39
2.5.1 歸納推理和演繹推理39
2.5.2 數(shù)學(xué)歸納法41
2.5.3 數(shù)學(xué)歸納法的應(yīng)用43
2.6 本章小結(jié)44
習(xí)題45第3章 集合48
3.1 集合及子集48
3.1.1 集合及其表示48
3.1.2 子集49
3.1.3 冪集50
3.1.4 多重集合51
3.2 集合上的運算51
3.2.1 集合的并51
3.2.2 集合的交52
3.2.3 集合的差53
3.2.4 集合的對稱差53
3.3 集合的笛卡兒乘積54
3.3.1 有序?qū)?4
3.3.2 集合的笛卡兒乘積55
3.4 本章小結(jié)56
習(xí)題56
第4章 關(guān)系60
4.1 關(guān)系的基本概念60
4.1.1 二元關(guān)系的定義60
4.1.2 關(guān)系矩陣62
4.1.3 關(guān)系圖63
4.1.4 n元關(guān)系及其應(yīng)用64
4.2 復(fù)合關(guān)系和逆關(guān)系64
4.2.1 復(fù)合關(guān)系65
4.2.2 逆關(guān)系67
4.3 關(guān)系的性質(zhì)69
4.4 等價關(guān)系和集合的劃分72
4.4.1 等價關(guān)系73
4.4.2 集合的劃分75
4.5 關(guān)系的閉包76
4.6 本章小結(jié)79
習(xí)題80
第5章 函數(shù)84
5.1 函數(shù)的基本概念84
5.2 特殊函數(shù)86
5.3 函數(shù)的運算88
5.4 一些常見的函數(shù)91
5.5 本章小結(jié)92
習(xí)題93
第6章 計數(shù)初步95
6.1 計數(shù)的兩個基本原理95
6.1.1 加法原理(addition principle of counting)95
6.1.2 乘法原理(multiplication principle of counting)96
6.2 排列與組合97
6.2.1 排列97
6.2.2 組合99
6.3 鴿籠原理101
6.4 容斥原理及其應(yīng)用103
6.4.1 容斥原理103
6.4.2 容斥原理的應(yīng)用104
6.5 遞歸關(guān)系106
6.5.1 遞歸關(guān)系模型106
6.5.2 遞歸關(guān)系的基本解法109
6.6 本章小結(jié)114
習(xí)題115
第7章 圖論118
7.1 圖的基本概念118
7.1.1 圖的定義、表示和一些術(shù)語118
7.1.2 圖的同構(gòu)120
7.1.3 關(guān)聯(lián)矩陣和鄰接矩陣122
7.1.4 子圖122
7.1.5 頂點的度123
7.1.6 路和連通124
7.1.7 回路126
7.1.8 最短路問題127
7.2 歐拉圖130
7.2.1 基本概念130
7.2.2 中國郵遞員問題133
7.3 哈密爾頓圖134
7.3.1 基本概念134
7.3.2 巡回售貨員問題(TSP)137
7.4 可平面性137
7.4.1 平面圖和可平面圖137
7.4.2 平面圖的歐拉公式及其應(yīng)用139
7.4.3 可平面圖的判定140
7.4.4 平面圖的對偶圖141
7.5 本章小結(jié)142
習(xí)題143
第8章 樹147
8.1 無向樹147
8.1.1 無向樹的定義和基本性質(zhì)147
8.1.2 生成樹和最小生成樹149
8.2 有向樹及根樹151
8.2.1 有向樹及根樹的定義151
8.2.2 有序樹153
8.2.3 樹搜索155
8.2.4 前綴碼和最優(yōu)樹158
8.3 本章小結(jié)161
習(xí)題162
部分習(xí)題的提示與解答165
參考文獻(xiàn)176