目錄
第一部分 數(shù)理邏輯
第1章 命題邏輯 3
1.1 命題及聯(lián)結(jié)詞 3
1.1.1 命題的概念 3
1.1.2 命題聯(lián)結(jié)詞 5
1.1.3 命題的符號化 9
1.2 命題公式 9
1.2.1 命題公式的定義 9
1.2.2 命題公式的賦值與真值表 11
1.2.3 命題公式的類型 12
1.3 命題公式等值演算 13
1.3.1 等值式與等值演算 13
1.3.2 范式 17
1.3.3 主范式 19
1.4 命題邏輯的推理理論 26
1.4.1 推理的形式結(jié)構(gòu)及推理規(guī)則 26
1.4.2 證明方法和策略 30
習(xí)題1 31
拓展練習(xí)1 34
第2章 謂詞邏輯 36
2.1 謂詞邏輯命題符號化 36
2.1.1 個體詞、謂詞 36
2.1.2 量詞 37
2.2 謂詞公式及解釋 38
2.2.1 基本定義 38
2.2.2 謂詞公式的解釋 39
2.2.3 謂詞公式的類型 41
2.3 謂詞邏輯等值演算 42
2.3.1 等值式與等值演算 42
2.3.2 前束范式 44
2.4 謂詞邏輯的推理理論 45
2.4.1 推理的形式結(jié)構(gòu)及推理規(guī)則 45
2.4.2 證明方法和策略 46
習(xí)題2 48
拓展練習(xí)2 50
第二部分 集 合 論
第3章 集合論基礎(chǔ) 53
3.1 集合的基本概念 53
3.1.1 集合的概念及特征 53
3.1.2 集合間的關(guān)系 55
3.1.3 冪集合 56
3.2 集合的運(yùn)算與恒等式 57
3.2.1 集合的運(yùn)算 57
3.2.2 集合恒等式 58
3.3 有限集合的計數(shù)問題 61
3.3.1 兩個有限集合的計數(shù)問題 61
3.3.2 三個有限集合的計數(shù)問題 62
3.3.3 n個有限集合的計數(shù)問題 63
3.4 計算機(jī)表示集合的方法 64
習(xí)題3 66
拓展練習(xí)3 68
第4章 關(guān)系 69
4.1 關(guān)系的概念 69
4.1.1 有序?qū)?69
4.1.2 笛卡兒積 70
4.1.3 關(guān)系的定義 71
4.2 關(guān)系的表示、性質(zhì)及運(yùn)算 72
4.2.1 關(guān)系的表示方法 72
4.2.2 關(guān)系的性質(zhì) 74
4.2.3 關(guān)系的運(yùn)算 75
4.3 等價關(guān)系與劃分 82
4.3.1 等價關(guān)系 82
4.3.2 等價類及其性質(zhì) 82
4.3.3 商集和劃分 83
4.4 偏序關(guān)系 84
4.4.1 偏序關(guān)系的定義 84
4.4.2 哈斯圖 85
4.4.3 偏序集中的特殊元素 87
4.4.4 拓?fù)渑判?88
習(xí)題4 88
拓展練習(xí)4 90
第5章 函數(shù)與集合的勢 91
5.1 函數(shù) 91
5.1.1 函數(shù)的定義 91
5.1.2 函數(shù)的類型 92
5.1.3 常用函數(shù) 94
5.2 函數(shù)的運(yùn)算 95
5.2.1 函數(shù)的復(fù)合 95
5.2.2 函數(shù)的逆運(yùn)算 96
5.3 集合的勢 97
5.3.1 集合的等勢 98
5.3.2 可數(shù)集合與不可數(shù)集合 99
5.3.3 集合的優(yōu)勢 101
習(xí)題5 102
拓展練習(xí)5 102
第三部分 代數(shù)系統(tǒng)
第6章 代數(shù)系統(tǒng)的基本概念 107
6.1 運(yùn)算 107
6.1.1 運(yùn)算的定義與表示方法 107
6.1.2 二元運(yùn)算的性質(zhì) 110
6.1.3 二元運(yùn)算的特殊元素和消去律 111
6.2 代數(shù)系統(tǒng)簡介 114
6.2.1 代數(shù)系統(tǒng)的定義 114
6.2.2 代數(shù)系統(tǒng)的分類 114
6.2.3 子代數(shù)和積代數(shù) 115
6.2.4 代數(shù)系統(tǒng)的同態(tài)與同構(gòu) 116
習(xí)題6 117
拓展練習(xí)6 119
第7章 幾個典型的代數(shù)系統(tǒng) 120
7.1 半群和群 120
7.1.1 半群與獨(dú)異點(diǎn) 120
7.1.2 群 121
7.2 環(huán)與域 126
7.2.1 環(huán) 126
7.2.2 域 127
7.3 格與布爾代數(shù) 128
7.3.1 格 128
7.3.2 布爾代數(shù) 132
習(xí)題7 132
拓展練習(xí)7 134
第四部分 圖論
第8章 圖論基礎(chǔ) 139
8.1 圖的基本概念 139
8.1.1 圖的定義 139
8.1.2 頂點(diǎn)的度與握手定理 141
8.1.3 完全圖與正則圖 145
8.1.4 圖的同構(gòu) 146
8.1.5 子圖、補(bǔ)圖與圖的運(yùn)算 147
8.2 圖的連通性 148
8.2.1 通路與回路 149
8.2.2 無向圖的連通性 151
8.2.3 有向圖的連通性 152
8.3 圖的矩陣表示 153
8.3.1 關(guān)聯(lián)矩陣 153
8.3.2 鄰接矩陣 154
8.3.3 可達(dá)矩陣 157
8.4 圖的應(yīng)用 157
8.4.1 渡河問題 158
8.4.2 均分問題 158
8.4.3 賦權(quán)圖的最短通路問題 159
8.4.4 通信網(wǎng)絡(luò)問題 160
習(xí)題8 160
拓展練習(xí)8 161
第9章 樹 163
9.1 無向樹及其應(yīng)用 163
9.1.1 無向樹的定義和性質(zhì) 163
9.1.2 生成樹 165
9.1.3 最小生成樹 167
9.2 根樹及其應(yīng)用 168
9.2.1 根樹的定義及分類 168
9.2.2 根樹的遍歷 170
9.2.3 最優(yōu)二元樹與哈夫曼編碼 172
9.2.4 根樹的應(yīng)用 174
習(xí)題9 177
拓展練習(xí)9 178
第10章 幾種特殊的圖 180
10.1 歐拉圖 180
10.1.1 歐拉圖的定義 180
10.1.2 歐拉圖的判定及歐拉回路的求解算法 181
10.1.3 歐拉圖的應(yīng)用 182
10.2 哈密頓圖 186
10.2.1 哈密頓圖的定義 186
10.2.2 哈密頓圖的判定 187
10.2.3 哈密頓圖的應(yīng)用 188
10.3 二部圖 189
10.3.1 二部圖的定義 189
10.3.2 二部圖的判定 190
10.3.3 二部圖的匹配及其應(yīng)用 191
10.4 平面圖 193
10.4.1 平面圖的定義及性質(zhì) 193
10.4.2 平面圖的判定 195
10.4.3 平面圖的應(yīng)用——著色問題 197
習(xí)題10 199
拓展練習(xí)10 203
參考文獻(xiàn) 204