第1章 集 合 1

1.1 集合的概念及表示 2
1.1.1 集合的表示 2
1.1.2 集合與集合的關系 3
1.1.3 幾個特殊集合 4
1.2 集合的運算 4
1.3 有限集與無限集 5
1.3.1 有限集 5
1.3.2 無限集 6
1.4 與集合相關的應用 7
1.4.1 集合的計算機表示 7
1.4.2 計數問題 8
1.5 本章練習 8

第2章 二元關系 11

2.1 二元關系及其表示 12
2.1.1 序偶和笛卡兒積 12
2.1.2 關系的定義 14
2.1.3 關系的表示法 15
2.2 關系的運算 19
2.2.1 關系的復合運算 20
2.2.2 關系的逆運算 21
2.2.3 關系的冪運算 23
2.3 關系的性質 24
2.3.1 關系性質的定義 24

離散數學

2.3.2 關系性質的判定定理 28
2.3.3 關系性質的保守性 30
2.4 關系的閉包 31
2.4.1 閉包的概念 31
2.4.2 關系矩陣角度的閉包應用 33
2.5 關系運算的應用 34
2.5.1 關系的應用 34
2.5.2 二元關系及表示的應用 36
2.5.3 關系運算的具體應用 38
2.6 等價關系 39
2.6.1 等價關系的基礎 39
2.6.2 集合的劃分 41
2.6.3 等價關系與劃分 42
2.7 偏序關系 43
2.8 本章練習 47

第3章 函 數 49

3.1 函數的概念 50
3.1.1 函數的定義 50
3.1.2 函數的類型 51
3.2 特殊函數 52
3.3 函數的運算 53
3.3.1 函數的復合運算 53
3.3.2 函數的逆運算 55
3.3.3 關系的冪運算 56
3.4 本章練習 57

第4章 命題邏輯 59

4.1 命題符號化及聯結詞 60
4.2 命題公式及分類 65
4.3 等值演算 69

目錄

4.4 范式 74
4.5 聯結詞全功能集 82
4.6 推理理論 83
4.7 典型應用 89
4.8 本章練習 91

第5章 謂詞邏輯 94

5.1 謂詞邏輯基本概念 95
5.1.1 個體詞和謂詞 95
5.1.2 量詞 97
5.1.3 函 詞 100
5.2 謂詞邏輯公式及解釋 101
5.2.1 謂詞邏輯公式 101
5.2.2 解釋 105
5.3 謂詞邏輯等值式與前束范式 107
5.3.1 謂詞邏輯等值式 107
5.3.2 前束范式 110
5.4 謂詞邏輯推理 111
5.4.1 謂詞邏輯推理的基本概念 111
5.4.2 謂詞邏輯的推理規則 112
5.5 典型應用 115
5.6 本章練習 117

第6章 圖論基礎 119

6.1 圖的基本概念 121
6.1.1 圖的定義 122
6.1.2 圖的表示 123
6.1.3 圖的分類 124
6.1.4 圖的操作 127
6.1.5 圖的同構 128
6.1.6 圖的基本定理 132

離散數學

6.1.7 圖的應用 135
6.2 路與回路 136
6.2.1 通路與回路 137
6.2.2 無向圖的連通性 139
6.2.3 有向圖的連通性 142
6.2.4 知識點小結 144
6.3 圖的表示 144
6.4 典型應用 148
6.5 本章練習 150

第 7 章 特 殊 圖 153

7.1 歐拉圖 154
7.1.1 歐拉圖的定義 154
7.1.2 歐拉圖的判定 154
7.1.3 歐拉回路求取算法： Fleury 算法 156
7.2 哈密頓圖 157
7.2.1 哈密頓圖的定義 157
7.2.2 哈密頓圖的判定 158
7.3 二部圖 160
7.3.1 二部圖的定義 160
7.3.2 二部圖的判定 161
7.4 平面圖 162
7.4.1 平面圖的定義 162
7.4.2 平面圖的判定 164
7.5 特殊圖的應用 166
7.5.1 歐拉圖的應用 166
7.5.2 哈密頓圖的應用 168
7.5.3 二部圖的應用 169
7.5.4 平面圖的應用 170
7.6 本章練習 171

目錄

第 8 章 樹與根樹 174

8.1 樹的定義及性質 175
8.1.1 基本概念 175
8.1.2 無向樹的性質 175
8.2 生成樹 177
8.2.1 定義 177
8.2.2 *小生成樹 178
8.3 根樹 181
8.3.1 根樹的定義 181
8.3.2 根樹的分類 183
8.4 二叉樹 183
8.4.1 二叉樹的基本類型 184
8.4.2 二叉樹的特殊類型 184
8.4.3 二叉樹的性質及證明 184
8.4.4 前序、中序和后序遍歷 185
8.4.5 *優二叉樹和哈夫曼編碼 187
8.5 典型應用 189
8.5.1 無向樹的應用：煤氣管道鋪設設計問題 189
8.5.2 根樹的應用：博弈樹 189
8.6 本章練習 191

第 9 章 Petri網 193

9.1 網與子網 194
9.1.1 網的定義 194
9.1.2 前集和后集 195
9.1.3 網的分類 195
9.1.4 子網的定義 197
9.2 標識網與網系統 198
9.2.1 標識網 198
9.2.2 網系統 198
9.3 庫所/變遷系統與加權 Petri網 200

離散數學

9.3.1 庫所/變遷系統 201
9.3.2 加權Petri網 202
9.4 典型應用 203
9.5 本章練習 205

第 1 0 章 代數系統 207

10.1 代數系統的基本概念 208
10.1.1 代數運算的概念 208
10.1.2 代數系統的概念 211
10.1.3 子代數 211
10.1.4 商代數 212
10.2 代數運算的性質 213
10.2.1 二元運算的運算性質 213
10.2.2 二元運算的特殊元素 215
10.3 代數系統間的關系 217
10.3.1 同態與同構的概念及性質 217
10.3.2 同余 219
10.4 典型應用 220
10.4.1 邏輯電路 220
10.4.2 關系代數 221
10.5 本章練習 224

第 1 1 章 典型代數系統 227

11.1 半群和群 228
11.1.1 半群及其性質 228
11.1.2 群及其性質 230
11.1.3 子群及其性質 234
11.1.4 特殊群 237
11.1.5 例題 239
11.2 環與域、陪集與拉格朗日定理 240
11.2.1 環 240

目錄

11.2.2 域 242
11.2.3 陪集 244
11.2.4 拉格朗日定理 245
11.3 格和布爾代數 249
11.3.1 格 249
11.3.2 特殊格 254
11.3.3 布爾代數 259
11.4 典型應用 261
11.5 本章練習 264

參考文獻 266
附錄 習題參考答案 268