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

目錄
第一篇 數(shù)理邏輯
第1章 命題邏輯 1
1.1 命題及命題聯(lián)結(jié)詞 1
1.1.1 命題的基本概念 2
1.1.2 命題聯(lián)結(jié)詞 4
1.1.3 命題符號(hào)化 8
1.2 命題公式及其類(lèi)型 9
1.2.1 命題公式的概念 9
1.2.2 真值表 10
1.2.3 命題公式的類(lèi)型 11
1.3 等價(jià)式與蘊(yùn)涵式 11
1.3.1 命題公式的等價(jià) 11
1.3.2 蘊(yùn)涵式 15
1.3.3 對(duì)偶式 16
1.4 命題公式標(biāo)準(zhǔn)型——范式 17
1.4.1 范式 17
1.4.2 主范式 18
1.5 推理與證明 23
1.5.1 有效推理的概念與形式 24
1.5.2 推理的構(gòu)造證明法 24
1.6 命題邏輯的應(yīng)用 27
1.6.1 邏輯代數(shù) 27
1.6.2 程序設(shè)計(jì) 29
1.6.3 判斷推理 30
1.7 典型例題分析 31
小結(jié) 36
上機(jī)練習(xí) 37
習(xí)題1 38
第2章 謂詞邏輯 42
2.1 謂詞邏輯基本概念 42
2.1.1 個(gè)體和謂詞 42
2.1.2 量詞 43
2.2 謂詞公式及命題符號(hào)化 45
2.2.1 謂詞公式 45
2.2.2 量詞的轄域與變?cè)募s束 45
2.2.3 量詞的消去規(guī)則 46
2.2.4 謂詞公式命題符號(hào)化 47
2.3 謂詞演算的等價(jià)式和蘊(yùn)涵式 48
2.3.1 謂詞公式的解釋 48
2.3.2 謂詞公式的類(lèi)型 49
2.3.3 謂詞公式的等價(jià)及蘊(yùn)涵 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
習(xí)題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 集合的運(yùn)算 68
3.2.1 交運(yùn)算 68
3.2.2 并運(yùn)算 69
3.2.3 差運(yùn)算 69
3.2.4 對(duì)稱(chēng)差運(yùn)算 69
3.2.5 集合運(yùn)算的性質(zhì) 69
3.3 集合的劃分與覆蓋 71
3.4 包含排斥原理 72
3.5 數(shù)學(xué)歸納法 73
3.6 集合的應(yīng)用 75
3.6.1 集合的計(jì)算機(jī)表示 75
3.6.2 數(shù)學(xué)形態(tài)學(xué) 75
3.7 典型例題分析 78
小結(jié) 82
上機(jī)練習(xí) 82
習(xí)題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)系的運(yùn)算 92
4.3.1 關(guān)系的集合運(yùn)算 92
4.3.2 逆關(guān)系 93
4.3.3 復(fù)合關(guān)系 93
4.3.4 關(guān)系的冪 95
4.3.5 關(guān)系運(yùn)算的性質(zhì) 96
4.3.6 關(guān)系運(yùn)算與關(guān)系性質(zhì) 96
4.3.7 關(guān)系的限制和擴(kuò)充 97
4.4 關(guān)系的閉包運(yùn)算 97
4.4.1 閉包的定義 97
4.4.2 閉包的計(jì)算 98
4.4.3 閉包的性質(zhì) 101
4.4.4 多重閉包 102
4.5 等價(jià)關(guān)系和等價(jià)類(lèi) 102
4.5.1 等價(jià)關(guān)系的定義 102
4.5.2 等價(jià)類(lèi) 103
4.5.3 等價(jià)關(guān)系與劃分 104
4.6 相容關(guān)系和相容類(lèi) 106
4.6.1 相容關(guān)系的定義 106
4.6.2 相容類(lèi) 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)系的應(yīng)用——逾滲現(xiàn)象研究 111
4.8.1 問(wèn)題描述 111
4.8.2 數(shù)學(xué)模型 113
4.8.3 等價(jià)類(lèi)的求解方法 113
4.9 典型例題分析 115
小結(jié) 120
上機(jī)練習(xí) 121
習(xí)題4 121
第5章 函數(shù) 126
5.1 函數(shù)的概念 126
5.1.1 函數(shù)的定義 126
5.1.2 函數(shù)的性質(zhì) 128
5.2 函數(shù)的運(yùn)算 128
5.2.1 逆函數(shù) 129
5.2.2 復(fù)合函數(shù) 129
5.3 集合的基數(shù) 130
5.3.1 等勢(shì) 130
5.3.2 有限集與無(wú)限集 131
5.3.3 可數(shù)集與不可數(shù)集 132
5.3.4 基數(shù)的比較 133
5.4 特征函數(shù) 134
5.5 典型例題分析 135
小結(jié) 138
上機(jī)練習(xí) 138
習(xí)題5 138
第三篇 圖論
第6章 圖論基礎(chǔ) 141
6.1 圖的基本概念 142
6.1.1 圖的定義 142
6.1.2 節(jié)點(diǎn)的度數(shù) 143
6.1.3 正則圖和完全圖 144
6.1.4 子圖和補(bǔ)圖 145
6.1.5 圖的同構(gòu) 146
6.2 路和圖的連通性 146
6.2.1 通路和回路 146
6.2.2 無(wú)向圖的連通性 148
6.2.3 有向圖的連通性 151
6.3 圖的矩陣表示 152
6.3.1 鄰接矩陣 153
6.3.2 可達(dá)性矩陣 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 平面圖的對(duì)偶圖 166
6.5.3 平面圖的著色 166
6.6 二部圖與匹配 168
6.6.1 二部圖基本概念 168
6.6.2 匹配 168
6.7 樹(shù)與生成樹(shù) 169
6.7.1 樹(shù)的基本概念 169
6.7.2 生成樹(shù) 171
6.7.3 小生成樹(shù) 172
6.8 根樹(shù)及其應(yīng)用 174
6.8.1 根樹(shù)的基本概念 174
6.8.2 二叉樹(shù) 176
6.8.3 優(yōu)二叉樹(shù) 177
6.8.4 根樹(shù)的遍歷 177
6.9 網(wǎng)絡(luò)優(yōu)化問(wèn)題 178
6.9.1 短路徑問(wèn)題 179
6.9.2 大流問(wèn)題 182
6.9.3 小費(fèi)用流及其求法 186
6.10 圖論的應(yīng)用 188
6.10.1 公交站點(diǎn)可達(dá)性查詢 188
6.10.2 計(jì)算機(jī)鼓輪的設(shè)計(jì)——布魯英序列 193
6.10.3 資源分配圖 194
6.10.4 前綴碼 195
6.11 典型例題分析 197
小結(jié) 202
上機(jī)練習(xí) 203
習(xí)題6 203
第四篇 代數(shù)系統(tǒng)
第7章 代數(shù)結(jié)構(gòu) 210
7.1 代數(shù)系統(tǒng)的基本概念 210
7.1.1 n元運(yùn)算及代數(shù)系統(tǒng) 210
7.1.2 二元運(yùn)算的性質(zhì) 212
7.1.3 代數(shù)系統(tǒng)的特異元 213
7.2 半群與獨(dú)異點(diǎn) 215
7.2.1 半群 215
7.2.2 獨(dú)異點(diǎn) 217
7.3 群與子群 218
7.3.1 群的定義 218
7.3.2 群的性質(zhì) 220
7.3.3 子群 221
7.3.4 群中的冪運(yùn)算 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)的應(yīng)用——糾錯(cuò)碼 237
7.8.1 糾錯(cuò)碼的糾錯(cuò)能力 238
7.8.2 糾錯(cuò)碼的選擇 239
7.8.3 群碼的校正 241
7.9 典型例題分析 242
小結(jié) 247
上機(jī)練習(xí) 248
習(xí)題7 248
第8章 格與布爾代數(shù) 251
8.1 格 251
8.1.1 格和子格 251
8.1.2 格的對(duì)偶原理和性質(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 有補(bǔ)格 256
8.3 布爾代數(shù) 257
8.3.1 布爾代數(shù)的定義及性質(zhì) 257
8.3.2 布爾代數(shù)的同構(gòu) 258
8.4 布爾表達(dá)式 259
8.4.1 布爾表達(dá)式的基本概念 259
8.4.2 布爾表達(dá)式的范式 260
8.5 布爾表達(dá)式在數(shù)字邏輯設(shè)計(jì)中的應(yīng)用 263
8.6 典型例題分析 264
小結(jié) 266
習(xí)題8 267
第五篇 組合與計(jì)數(shù)
第9章 組合計(jì)數(shù) 270
9.1 基本計(jì)數(shù)法則 270
9.1.1 枚舉 270
9.1.2 計(jì)數(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
上機(jī)練習(xí) 285
習(xí)題9 286
參考文獻(xiàn) 288