《離散數學及套用（第2版）》是2018年9月清華大學出版社出版的圖書，作者是劉鐸。
基本介紹
- 書名：離散數學及套用（第2版）
- 作者：劉鐸
- 出版社：清華大學出版社
- 出版時間：2018年9月
- 定價：59 元
- ISBN：9787302496632
內容簡介,圖書目錄,
離散數學是現代數學的一個重要分支，是計算機專業和軟體工程專業的基礎主幹課程，是進一步學習後續課程以及進行研究和開發的基礎。本書根據作者多年教學經驗編寫而成，著重講解離散數學的基本概念、基本方法及其套用，給出了大量的典型例題和習題，以及若干綜合專題、套用案例和實驗項目。全書共10章，內容包括樸素集合論、數論基礎、計數基礎、命題邏輯、謂詞邏輯、二元關係、函式、偏序關係與格、代數結構、圖論與樹、形式語言、自動機與正則表達式等。附錄給出綜合性研討專題、綜合實驗、名詞中英文對照表等。
第1章?基礎知識??/ 1
1.1 集合與序列 1
1.1.1 集合的基本概念 1
1.1.2 集合的運算及性質 3
1.1.3 序列 6
1.2 數論基礎 7
1.3 計數基礎 10
1.3.1 加法法則與乘法法則 10
1.3.2 排列與組合 11
1.3.3 鴿巢原理 16
1.3.4 有限集的計數——容斥原理 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 命題聯結詞的完備集 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章?函式??/ 141
5.1 函式的定義 141
5.2 函式的性質 142
5.3 函式的複合 144
5.4 逆函式 146
5.5 計算機科學中的常用函式 147
*5.6 雙射函式及集合的勢 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 格與布爾代數 171
6.3.1 格的定義 171
6.3.2 特殊的格 174
*6.3.3 布爾代數 177
*6.3.4 信息流的格模型 179
習題6 181
第7章?代數結構??/ 187
7.1 代數結構 187
7.1.1 運算與代數結構的定義 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 循環群與置換群 199
7.2.6 陪集與拉格朗日定理 200
7.3 環與域 203
7.3.1 環 203
7.3.2 域 205
7.4 作為代數結構的格與布爾代數 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 335
第10章?形式語言、自動機與正則表達式??/ 342
10.1 語言 342
10.2 文法 346
10.3 巴科斯-諾爾範式和語法圖 351
10.4 有限狀態自動機 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 格雷碼、超立方體的哈密頓迴路和九連環 420
A.13.1 格雷碼 420
A.13.2 超立方體圖中的哈密頓迴路 421
A.13.3 九連環與格雷碼 423
A.14 謝爾賓斯基三角 426
附錄B?課程綜合實驗??/ 433
B.1 實驗一：漢諾塔問題的變體 433
B.1.1 實驗內容 433
B.1.2 實驗要求 434
B.1.3 擴展閱讀 435
B.2 實驗二：命題演算的計算機實現 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 實驗八：綠色健康城市規劃 446
B.9 實驗九：羽毛球雙打配對和住宿安排 446
附錄C?名詞英漢對照表??/ 448
附錄D?使用Mathematica學習離散數學??/ 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
離散數學及套用（第2版）
IX
