離散數(shù)學(xué)及應(yīng)用（第2版）

　　
　　
　　
　　
　　
　　
　　　　　第1章?基礎(chǔ)知識(shí)??/ 1
　　1.1 集合與序列 1
1.1.1 集合的基本概念 1
1.1.2 集合的運(yùn)算及性質(zhì) 3
1.1.3 序列 6
　　1.2 數(shù)論基礎(chǔ) 7
　　1.3 計(jì)數(shù)基礎(chǔ) 10
1.3.1 加法法則與乘法法則 10
1.3.2 排列與組合 11
1.3.3 鴿巢原理 16
1.3.4 有限集的計(jì)數(shù)——容斥原理 19
1.3.5 遞推關(guān)系 22
　　1.4 布爾矩陣及其運(yùn)算 26
　　習(xí)題1 28
　　　　　第2章?命題邏輯??/ 41
　　2.1 命題邏輯的基本概念 41
　　2.2 命題公式及其分類 45
　　2.3 命題邏輯的等值演算 48
　　2.4 對(duì)偶與范式 53
2.4.1 對(duì)偶 53
2.4.2 析取范式和合取范式 54
2.4.3 主范式 56
　　2.5 命題聯(lián)結(jié)詞的完備集 63
　　2.6 命題邏輯的推理 64
　　習(xí)題2 70
　　　　　第3章?謂詞邏輯??/ 79
　　3.1 謂詞與量詞 79
3.1.1 謂詞 79
3.1.2 量詞 80
3.2 謂詞公式及分類 81
3.3 自然語(yǔ)言形式化 83
3.4 謂詞邏輯的等值演算 86
3.5 前束范式 90
3.6 謂詞邏輯的推理 91
習(xí)題3 98
第4章?二元關(guān)系??/ 104
4.1 關(guān)系及其表示 104
4.1.1 有序?qū)εc笛卡兒積 104
4.1.2 二元關(guān)系的定義 106
4.1.3 二元關(guān)系的表示 109
4.2 關(guān)系的運(yùn)算 110
4.2.1 關(guān)系的基本運(yùn)算 110
4.2.2 關(guān)系的冪和道路 113
4.3 關(guān)系的性質(zhì) 116
4.3.1 關(guān)系性質(zhì)的定義和判斷 116
4.3.2 關(guān)系運(yùn)算對(duì)性質(zhì)的保持 120
4.4 關(guān)系的閉包 122
4.5 等價(jià)關(guān)系和集合的劃分 127
4.5.1 等價(jià)關(guān)系、等價(jià)類和商集 127
4.5.2 集合的劃分 128
4.5.3 等價(jià)關(guān)系與劃分的一一對(duì)應(yīng) 129
*4.6 相容關(guān)系與集合的覆蓋 130
*4.7 關(guān)系在計(jì)算機(jī)中的表示方法 131
習(xí)題4 132
第5章?函數(shù)??/ 141
5.1 函數(shù)的定義 141
5.2 函數(shù)的性質(zhì) 142
5.3 函數(shù)的復(fù)合 144
5.4 逆函數(shù) 146
5.5 計(jì)算機(jī)科學(xué)中的常用函數(shù) 147
*5.6 雙射函數(shù)及集合的勢(shì) 152
習(xí)題5 156

第6章?偏序關(guān)系??/ 162
6.1 偏序關(guān)系和偏序集 162
6.1.1 偏序關(guān)系和偏序集的定義與性質(zhì) 162
6.1.2 積偏序和字典序 164
6.1.3 哈斯圖 164
6.2 偏序集中的特殊元素 166
6.2.1 偏序集中的特殊元素 166
6.2.2 拓?fù)渑判? 169
6.3 格與布爾代數(shù) 171
6.3.1 格的定義 171
6.3.2 特殊的格 174
*6.3.3 布爾代數(shù) 177
*6.3.4 信息流的格模型 179
習(xí)題6 181
第7章?代數(shù)結(jié)構(gòu)??/ 187
7.1 代數(shù)結(jié)構(gòu) 187
7.1.1 運(yùn)算與代數(shù)結(jié)構(gòu)的定義 187
7.1.2 二元運(yùn)算的性質(zhì) 189
7.2 群 192
7.2.1 半群與亞群 192
7.2.2 群的概念 193
7.2.3 群的性質(zhì) 196
7.2.4 子群 198
7.2.5 循環(huán)群與置換群 199
7.2.6 陪集與拉格朗日定理 200
7.3 環(huán)與域 203
7.3.1 環(huán) 203
7.3.2 域 205
7.4 作為代數(shù)結(jié)構(gòu)的格與布爾代數(shù) 206
習(xí)題7 208
第8章?圖論??/ 218
8.1 基本概念 218
8.1.1 無(wú)向圖、有向圖和握手定理 218
8.1.2 圖的同構(gòu)與子圖 224
8.1.3 道路、回路與連通性 227
8.1.4 圖的矩陣表示 228
8.2 歐拉圖 230
8.3 哈密頓圖 234
8.4 平面圖 238
8.5 頂點(diǎn)支配、獨(dú)立與覆蓋 244
8.6 匹配 247
8.6.1 匹配與最大匹配 247
8.6.2 霍爾定理及其應(yīng)用 252
8.6.3 匹配與覆蓋 254
*8.6.4 二部圖中的最佳匹配 258
8.7 圖的著色 263
8.8 網(wǎng)絡(luò)與流 267
習(xí)題8 282
第9章?樹(shù)及其應(yīng)用??/ 306
9.1 無(wú)向樹(shù) 306
9.2 支撐樹(shù)及其應(yīng)用 310
9.3 最短道路樹(shù) 321
9.4 根樹(shù)及其應(yīng)用 325
9.4.1 根樹(shù)的定義和基本概念 325
9.4.2 二叉樹(shù)的遍歷 330
9.4.3 最優(yōu)二叉樹(shù)與赫夫曼編碼 332
習(xí)題9 335
第10章?形式語(yǔ)言、自動(dòng)機(jī)與正則表達(dá)式??/ 342
10.1 語(yǔ)言 342
10.2 文法 346
10.3 巴科斯-諾爾范式和語(yǔ)法圖 351
10.4 有限狀態(tài)自動(dòng)機(jī) 353
10.5 語(yǔ)言與自動(dòng)機(jī)的關(guān)系 359
10.6 正則表達(dá)式 361
習(xí)題10 362
附錄A?綜合性研討專題??/ 371
A.1 湊郵資、分油、爬臺(tái)階與臺(tái)球桌 371
A.1.1 郵資問(wèn)題 371
A.1.2 分油問(wèn)題 373
A.1.3 登階問(wèn)題 376
A.1.4 臺(tái)球問(wèn)題 378
A.2 基于模運(yùn)算的校驗(yàn)碼 379
A.2.1 EAN-13碼 379
A.2.2 新版國(guó)際標(biāo)準(zhǔn)書號(hào)ISBN-13 380
A.2.3 第二代身份證 380
A.3 應(yīng)用鴿巢原理的紙牌魔術(shù)二則 382
A.3.1 紙牌魔術(shù)A 382
A.3.2 紙牌魔術(shù)B 384
A.4 完美洗牌法 385
A.5 Chomp游戲 388
A.6 麻花辮 390
A.7 伯恩賽德引理與波利亞定理 394
A.8 頓時(shí)錯(cuò)亂問(wèn)題 398
A.9 抽芽游戲與抱子甘藍(lán)游戲 402
A.9.1 抽芽游戲 402
A.9.2 抱子甘藍(lán)游戲 405
A.10 漢諾塔雜談 407
A.10.1 漢諾塔圖 407
A.10.2 漢諾塔的非遞歸算法 410
A.10.3 漢諾塔與普通二進(jìn)制碼 411
A.11 存儲(chǔ)器輪 412
A.11.1 存儲(chǔ)器輪及解決方法 412
A.11.2 德·布魯因序列 414
A.12 中國(guó)郵路問(wèn)題 417
A.13 格雷碼、超立方體的哈密頓回路和九連環(huán) 420
A.13.1 格雷碼 420
A.13.2 超立方體圖中的哈密頓回路 421
A.13.3 九連環(huán)與格雷碼 423
A.14 謝爾賓斯基三角 426
附錄B?課程綜合實(shí)驗(yàn)??/ 433
B.1 實(shí)驗(yàn)一：漢諾塔問(wèn)題的變體 433
B.1.1 實(shí)驗(yàn)內(nèi)容 433
B.1.2 實(shí)驗(yàn)要求 434
B.1.3 擴(kuò)展閱讀 435
B.2 實(shí)驗(yàn)二：命題演算的計(jì)算機(jī)實(shí)現(xiàn) 435
B.3 實(shí)驗(yàn)三：二元關(guān)系及其應(yīng)用 436
B.3.1 準(zhǔn)備工作 436
B.3.2 等價(jià)關(guān)系及其應(yīng)用 436
B.3.3 偏序關(guān)系及其應(yīng)用 437
B.3.4 連通性和歐拉道路/回路 439
B.4 實(shí)驗(yàn)四：村莊修引水渠問(wèn)題 440
B.4.1 實(shí)驗(yàn)內(nèi)容（一） 441
B.4.2 實(shí)驗(yàn)內(nèi)容（二） 442
B.4.3 討論與思考 442
B.5 實(shí)驗(yàn)五：考場(chǎng)安排問(wèn)題 443
B.5.1 實(shí)驗(yàn)內(nèi)容 443
B.5.2 實(shí)驗(yàn)要求 444
B.6 實(shí)驗(yàn)六：展覽館的參觀與維護(hù) 444
B.7 實(shí)驗(yàn)七：導(dǎo)師和研究生的自動(dòng)分配 445
B.8 實(shí)驗(yàn)八：綠色健康城市規(guī)劃 446
B.9 實(shí)驗(yàn)九：羽毛球雙打配對(duì)和住宿安排 446
附錄C?名詞英漢對(duì)照表??/ 448
附錄D?使用Mathematica學(xué)習(xí)離散數(shù)學(xué)??/ 459
D.1 集合、序列與矩陣 459
D.2 排列、組合、遞推關(guān)系與劃分 462
D.3 關(guān)系與有向圖 463
D.4 圖 467
D.5 樹(shù) 471
附錄E?Prolog語(yǔ)言與邏輯推理??/ 473
E.1 Prolog基礎(chǔ) 473
E.2 典型邏輯問(wèn)題 479
參考文獻(xiàn)??/ 483
　　
　　
VIII
離散數(shù)學(xué)及應(yīng)用（第2版）
　　
IX
目錄