目錄
第一部分 數(shù)理邏輯
第1章 命題邏輯 3
1.1 命題及聯(lián)結詞 3
1.1.1 命題的概念 3
1.1.2 命題聯(lián)結詞 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 推理的形式結構及推理規(guī)則 26
1.4.2 證明方法和策略 30
習題1 31
拓展練習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 推理的形式結構及推理規(guī)則 45
2.4.2 證明方法和策略 46
習題2 48
拓展練習2 50
第二部分 集 合 論
第3章 集合論基礎 53
3.1 集合的基本概念 53
3.1.1 集合的概念及特征 53
3.1.2 集合間的關系 55
3.1.3 冪集合 56
3.2 集合的運算與恒等式 57
3.2.1 集合的運算 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 計算機表示集合的方法 64
習題3 66
拓展練習3 68
第4章 關系 69
4.1 關系的概念 69
4.1.1 有序對 69
4.1.2 笛卡兒積 70
4.1.3 關系的定義 71
4.2 關系的表示、性質及運算 72
4.2.1 關系的表示方法 72
4.2.2 關系的性質 74
4.2.3 關系的運算 75
4.3 等價關系與劃分 82
4.3.1 等價關系 82
4.3.2 等價類及其性質 82
4.3.3 商集和劃分 83
4.4 偏序關系 84
4.4.1 偏序關系的定義 84
4.4.2 哈斯圖 85
4.4.3 偏序集中的特殊元素 87
4.4.4 拓撲排序 88
習題4 88
拓展練習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ù)的運算 95
5.2.1 函數(shù)的復合 95
5.2.2 函數(shù)的逆運算 96
5.3 集合的勢 97
5.3.1 集合的等勢 98
5.3.2 可數(shù)集合與不可數(shù)集合 99
5.3.3 集合的優(yōu)勢 101
習題5 102
拓展練習5 102
第三部分 代數(shù)系統(tǒng)
第6章 代數(shù)系統(tǒng)的基本概念 107
6.1 運算 107
6.1.1 運算的定義與表示方法 107
6.1.2 二元運算的性質 110
6.1.3 二元運算的特殊元素和消去律 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)與同構 116
習題6 117
拓展練習6 119
第7章 幾個典型的代數(shù)系統(tǒng) 120
7.1 半群和群 120
7.1.1 半群與獨異點 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
習題7 132
拓展練習7 134
第四部分 圖論
第8章 圖論基礎 139
8.1 圖的基本概念 139
8.1.1 圖的定義 139
8.1.2 頂點的度與握手定理 141
8.1.3 完全圖與正則圖 145
8.1.4 圖的同構 146
8.1.5 子圖、補圖與圖的運算 147
8.2 圖的連通性 148
8.2.1 通路與回路 149
8.2.2 無向圖的連通性 151
8.2.3 有向圖的連通性 152
8.3 圖的矩陣表示 153
8.3.1 關聯(lián)矩陣 153
8.3.2 鄰接矩陣 154
8.3.3 可達矩陣 157
8.4 圖的應用 157
8.4.1 渡河問題 158
8.4.2 均分問題 158
8.4.3 賦權圖的最短通路問題 159
8.4.4 通信網(wǎng)絡問題 160
習題8 160
拓展練習8 161
第9章 樹 163
9.1 無向樹及其應用 163
9.1.1 無向樹的定義和性質 163
9.1.2 生成樹 165
9.1.3 最小生成樹 167
9.2 根樹及其應用 168
9.2.1 根樹的定義及分類 168
9.2.2 根樹的遍歷 170
9.2.3 最優(yōu)二元樹與哈夫曼編碼 172
9.2.4 根樹的應用 174
習題9 177
拓展練習9 178
第10章 幾種特殊的圖 180
10.1 歐拉圖 180
10.1.1 歐拉圖的定義 180
10.1.2 歐拉圖的判定及歐拉回路的求解算法 181
10.1.3 歐拉圖的應用 182
10.2 哈密頓圖 186
10.2.1 哈密頓圖的定義 186
10.2.2 哈密頓圖的判定 187
10.2.3 哈密頓圖的應用 188
10.3 二部圖 189
10.3.1 二部圖的定義 189
10.3.2 二部圖的判定 190
10.3.3 二部圖的匹配及其應用 191
10.4 平面圖 193
10.4.1 平面圖的定義及性質 193
10.4.2 平面圖的判定 195
10.4.3 平面圖的應用——著色問題 197
習題10 199
拓展練習10 203
參考文獻 204