離散數(shù)學（第二版）

目錄
第一篇 數(shù)理邏輯
第1章 命題邏輯 1
1.1 命題及命題聯(lián)結(jié)詞 1
1.1.1 命題的基本概念 2
1.1.2 命題聯(lián)結(jié)詞 4
1.1.3 命題符號化 8
1.2 命題公式及其類型 9
1.2.1 命題公式的概念 9
1.2.2 真值表 10
1.2.3 命題公式的類型 11
1.3 等價式與蘊涵式 11
1.3.1 命題公式的等價 11
1.3.2 蘊涵式 15
1.3.3 對偶式 16
1.4 命題公式標準型——范式 17
1.4.1 范式 17
1.4.2 主范式 18
1.5 推理與證明 23
1.5.1 有效推理的概念與形式 24
1.5.2 推理的構(gòu)造證明法 24
1.6 命題邏輯的應用 27
1.6.1 邏輯代數(shù) 27
1.6.2 程序設(shè)計 29
1.6.3 判斷推理 30
1.7 典型例題分析 31
小結(jié) 36
上機練習 37
習題1 38
第2章 謂詞邏輯 42
2.1 謂詞邏輯基本概念 42
2.1.1 個體和謂詞 42
2.1.2 量詞 43
2.2 謂詞公式及命題符號化 45
2.2.1 謂詞公式 45
2.2.2 量詞的轄域與變元的約束 45
2.2.3 量詞的消去規(guī)則 46
2.2.4 謂詞公式命題符號化 47
2.3 謂詞演算的等價式和蘊涵式 48
2.3.1 謂詞公式的解釋 48
2.3.2 謂詞公式的類型 49
2.3.3 謂詞公式的等價及蘊涵 49
2.4 謂詞公式的范式 52
2.4.1 前束范式 52
2.4.2 前束合取、析取范式 53
2.5 謂詞邏輯的推理理論 53
2.5.1 量詞消去與引入規(guī)則 53
2.5.2 推理方法 54
2.6 典型例題分析 57
小結(jié) 61
習題2 62
第二篇 集合論
第3章 集合論基礎(chǔ) 65
3.1 集合的基本概念 65
3.1.1 集合及元素 65
3.1.2 集合的表示 66
3.1.3 集合間的關(guān)系 67
3.1.4 特殊集合 67
3.2 集合的運算 68
3.2.1 交運算 68
3.2.2 并運算 69
3.2.3 差運算 69
3.2.4 對稱差運算 69
3.2.5 集合運算的性質(zhì) 69
3.3 集合的劃分與覆蓋 71
3.4 包含排斥原理 72
3.5 數(shù)學歸納法 73
3.6 集合的應用 75
3.6.1 集合的計算機表示 75
3.6.2 數(shù)學形態(tài)學 75
3.7 典型例題分析 78
小結(jié) 82
上機練習 82
習題3 83
第4章 二元關(guān)系 86
4.1 關(guān)系的概念 86
4.1.1 序偶及n 元有序組 86
4.1.2 笛卡兒積 87
4.1.3 二元關(guān)系的基本概念 87
4.1.4 二元關(guān)系的表示 88
4.2 關(guān)系的性質(zhì) 90
4.2.1 關(guān)系性質(zhì)的概念 90
4.2.2 關(guān)系性質(zhì)的判斷 91
4.3 關(guān)系的運算 92
4.3.1 關(guān)系的集合運算 92
4.3.2 逆關(guān)系 93
4.3.3 復合關(guān)系 93
4.3.4 關(guān)系的冪 95
4.3.5 關(guān)系運算的性質(zhì) 96
4.3.6 關(guān)系運算與關(guān)系性質(zhì) 96
4.3.7 關(guān)系的限制和擴充 97
4.4 關(guān)系的閉包運算 97
4.4.1 閉包的定義 97
4.4.2 閉包的計算 98
4.4.3 閉包的性質(zhì) 101
4.4.4 多重閉包 102
4.5 等價關(guān)系和等價類 102
4.5.1 等價關(guān)系的定義 102
4.5.2 等價類 103
4.5.3 等價關(guān)系與劃分 104
4.6 相容關(guān)系和相容類 106
4.6.1 相容關(guān)系的定義 106
4.6.2 相容類 107
4.6.3 相容關(guān)系與覆蓋 107
4.7 序關(guān)系和哈塞圖 108
4.7.1 偏序關(guān)系的定義 108
4.7.2 偏序關(guān)系的哈塞圖 109
4.7.3 偏序集中的特殊元素 110
4.7.4 鏈和全序關(guān)系 111
4.8 關(guān)系的應用——逾滲現(xiàn)象研究 111
4.8.1 問題描述 111
4.8.2 數(shù)學模型 113
4.8.3 等價類的求解方法 113
4.9 典型例題分析 115
小結(jié) 120
上機練習 121
習題4 121
第5章 函數(shù) 126
5.1 函數(shù)的概念 126
5.1.1 函數(shù)的定義 126
5.1.2 函數(shù)的性質(zhì) 128
5.2 函數(shù)的運算 128
5.2.1 逆函數(shù) 129
5.2.2 復合函數(shù) 129
5.3 集合的基數(shù) 130
5.3.1 等勢 130
5.3.2 有限集與無限集 131
5.3.3 可數(shù)集與不可數(shù)集 132
5.3.4 基數(shù)的比較 133
5.4 特征函數(shù) 134
5.5 典型例題分析 135
小結(jié) 138
上機練習 138
習題5 138
第三篇 圖論
第6章 圖論基礎(chǔ) 141
6.1 圖的基本概念 142
6.1.1 圖的定義 142
6.1.2 節(jié)點的度數(shù) 143
6.1.3 正則圖和完全圖 144
6.1.4 子圖和補圖 145
6.1.5 圖的同構(gòu) 146
6.2 路和圖的連通性 146
6.2.1 通路和回路 146
6.2.2 無向圖的連通性 148
6.2.3 有向圖的連通性 151
6.3 圖的矩陣表示 152
6.3.1 鄰接矩陣 153
6.3.2 可達性矩陣 155
6.3.3 完全關(guān)聯(lián)矩陣 156
6.3.4 圖的連通性判斷 157
6.4 歐拉圖和哈密頓圖 158
6.4.1 歐拉圖 158
6.4.2 哈密頓圖 160
6.5 平面圖與圖著色 162
6.5.1 平面圖 162
6.5.2 平面圖的對偶圖 166
6.5.3 平面圖的著色 166
6.6 二部圖與匹配 168
6.6.1 二部圖基本概念 168
6.6.2 匹配 168
6.7 樹與生成樹 169
6.7.1 樹的基本概念 169
6.7.2 生成樹 171
6.7.3 小生成樹 172
6.8 根樹及其應用 174
6.8.1 根樹的基本概念 174
6.8.2 二叉樹 176
6.8.3 優(yōu)二叉樹 177
6.8.4 根樹的遍歷 177
6.9 網(wǎng)絡(luò)優(yōu)化問題 178
6.9.1 短路徑問題 179
6.9.2 大流問題 182
6.9.3 小費用流及其求法 186
6.10 圖論的應用 188
6.10.1 公交站點可達性查詢 188
6.10.2 計算機鼓輪的設(shè)計——布魯英序列 193
6.10.3 資源分配圖 194
6.10.4 前綴碼 195
6.11 典型例題分析 197
小結(jié) 202
上機練習 203
習題6 203
第四篇 代數(shù)系統(tǒng)
第7章 代數(shù)結(jié)構(gòu) 210
7.1 代數(shù)系統(tǒng)的基本概念 210
7.1.1 n元運算及代數(shù)系統(tǒng) 210
7.1.2 二元運算的性質(zhì) 212
7.1.3 代數(shù)系統(tǒng)的特異元 213
7.2 半群與獨異點 215
7.2.1 半群 215
7.2.2 獨異點 217
7.3 群與子群 218
7.3.1 群的定義 218
7.3.2 群的性質(zhì) 220
7.3.3 子群 221
7.3.4 群中的冪運算 223
7.4 阿貝爾群與循環(huán)群 223
7.4.1 阿貝爾群 223
7.4.2 循環(huán)群 224
7.5 陪集與拉格朗日定理 226
7.5.1 陪集及其基本性質(zhì) 226
7.5.2 拉格朗日定理 227
7.5.3 正規(guī)子群 229
7.6 同態(tài)與同構(gòu) 229
7.6.1 同態(tài)與同構(gòu)的定義 230
7.6.2 同態(tài)和同構(gòu)的性質(zhì) 232
7.6.3 同余關(guān)系 233
7.7 環(huán)與域 234
7.7.1 環(huán)及其性質(zhì) 235
7.7.2 域及其性質(zhì) 237
7.8 代數(shù)系統(tǒng)的應用——糾錯碼 237
7.8.1 糾錯碼的糾錯能力 238
7.8.2 糾錯碼的選擇 239
7.8.3 群碼的校正 241
7.9 典型例題分析 242
小結(jié) 247
上機練習 248
習題7 248
第8章 格與布爾代數(shù) 251
8.1 格 251
8.1.1 格和子格 251
8.1.2 格的對偶原理和性質(zhì) 252
8.1.3 格的代數(shù)系統(tǒng)定義 253
8.1.4 格的同態(tài)和同構(gòu) 254
8.2 特殊格 255
8.2.1 分配格 255
8.2.2 有界格 256
8.2.3 有補格 256
8.3 布爾代數(shù) 257
8.3.1 布爾代數(shù)的定義及性質(zhì) 257
8.3.2 布爾代數(shù)的同構(gòu) 258
8.4 布爾表達式 259
8.4.1 布爾表達式的基本概念 259
8.4.2 布爾表達式的范式 260
8.5 布爾表達式在數(shù)字邏輯設(shè)計中的應用 263
8.6 典型例題分析 264
小結(jié) 266
習題8 267
第五篇 組合與計數(shù)
第9章 組合計數(shù) 270
9.1 基本計數(shù)法則 270
9.1.1 枚舉 270
9.1.2 計數(shù)原理 271
9.2 排列與組合 271
9.2.1 線排列、圓排列、單組合 271
9.2.2 重排列、重組合 273
9.2.3 排列組合生成算法 274
9.3 鴿巢原理 275
9.4 遞推關(guān)系 276
9.4.1 遞推關(guān)系的概念 276
9.4.2 遞推關(guān)系的求解 277
9.5 典型例題分析 281
小結(jié) 285
上機練習 285
習題9 286
參考文獻 288