離散數(shù)學及應用（第2版）

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

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