離散數學及套用（第3版）

成書過程

修訂情況

在對《離散數學及套用謎擔腿（第3版）》進行修訂時，將一些附錄作為獨立的線上PDF文檔（讀者可以在清華大學出版社網站下載），並精簡各章的習題，只保留較為基礎的習題，同時以線上文檔的形式提供難度和靈活性都較高的補充習題。除此之外，《離散數學及套用（第3版）》較《離散數學及套用（第2版）》主要有以下變化：

每章的開頭都增加了該章內容的微詞雲，每章的最後都增加了“擴展閱讀”一節，供有興趣的讀者參考。書中標有“*”號的節/小節更適合進階讀者；其他讀者可以跳過這些內容，不會影響學習的連貫性。
將習題從每章的最後調整至每節之後。
將原“4.7關係在計算機中的表示方法”改為線上附錄，將原“6.3.4信息流的格模型”移入附錄A。
增加了“6.2.3有限偏序集的高度與寬度”“8.9圖的連通度”和“10.7圖靈機”。
對“6.3.2特殊的格”“6.3.3布爾代數”“7.2.6循環群”“7.2.7變換群與置換群”“8.3哈密頓圖”“8.4平面圖”和“8.8.2網路流的套用”等節進行了增補或重寫。
附錄A離散數學綜合性研討專題”增加了波利亞的果園、國際標準刊號、15*謎題、博弈樹與決策樹、龍曲線、社會網路中的結構平衡、市場全旋清倉與單品拍賣、密碼算法簡介等內容。
第2版的“附錄B課程綜合實驗”移至《離散數學及套用學習指導與習題解析》中，並增加了4個實驗。
重寫了第2版的“附錄EProlog語言與邏輯推理”（作為線上附錄），使用SWI Prolog描述並增加了示例。
增加了“羅素悖論與公理化集合論簡介”“自然數、整數與數學歸納法”“模糊集合與模糊關係簡介”“排列與組合的生成算法”和“五色定理”5個附錄，均作為線上附錄。
此外，《離散數學及套用（第3版）》對各章都進行了一些文字表述與內容的調整。在《離散數學及套用（第3版）》的編寫過程中，作者參考了中國國內外文獻。

出版工作

2022年5月1日，《離散數學及套用（第3版）》由清華大學出版社出版發行。

責任編輯	封面設計	責任校對	責任印製
龍啟銘、戰曉雷妹乘付	劉乾	胡偉民	沈露

內容簡介

全書共10章，內容包括樸素集合論、數論基礎、計數基礎、命題邏輯、謂詞邏輯、二元關係、函式、偏序關係與格、代數結構、圖論、樹、形式語言、自動機與正則表達式。附錄給出了離散數朽諒己潤學綜合性研討專題。

教材目錄

第1章基礎知識/1

1.1集合與序列1

1.1.1集合的基本概念1

1.1.2集合的運算及性質4

1.1.3序列7

習題1.18

1.2數論基礎10

習題1.214

1.3計數基礎16

1.3.1加法法則與乘法法則16

1.3.2排列與組合17

1.3.3鴿巢原理23

1.3.4有限集合的計數——容戒牛員斥原理26

1.3.5遞推關係29

習題1.333

1.4布爾矩陣及其運算37

習題1.439

擴展閱讀39

第2章命題邏輯/41

2.1命題邏輯的基本概念42

習題2.146

2.2命題公式及其分類酷刪棵笑47

習題2.250

2.3命題邏輯的等值演算51

習題2.356

2.4對偶與範式57

2.4.1對偶57

2.4.2析取範式與合取範式58

2.4.3主範式60離散數學及套用(第3版)目錄習題2.466

2.5命題聯結詞的完備集68

習題2.569

2.6命題邏輯的推理69

習題2.676

擴展閱讀77

第3章謂詞邏輯/79

3.1謂詞與量詞80

3.1.1謂詞80

3.1.2量詞81

習題3.182

3.2謂詞公式及分類82

習題3.285

3.3自然語言形式化85

習題3.388

3.4謂詞邏輯的等值演算89

習題3.494

3.5前束範式94

習題3.596

3.6謂詞邏輯的推理96

習題3.6103

擴展閱讀104

第4章二元關係/107

4.1關係及其表示107

4.1.1有序對與笛卡兒積107

4.1.2二元關係的定義109

4.1.3二元關係的表示112

習題4.1114

4.2關係的運算115

4.2.1關係的基本運算115

4.2.2關旬蜜協系的冪和道路119

習題4.2121

4.3關係的性質122

4.3.1關係性質的定義和判斷122

4.3.2關係運算對性質的保持126

習題4.3127

4.4關係的閉包129

習題4.4134

4.5等價關係和集合的劃分135

4.5.1等價關係、等價類和商集135

4.5.2集合的劃分137

4.5.3等價關係與劃分的一一對應137

習題4.5138

*4.6相容關係與集合的覆蓋140

習題4.6141

擴展閱讀142

第5章函式/143

5.1函式的定義143

習題5.1145

5.2函式的性質146

習題5.2147

5.3函式的複合148

習題5.3150

5.4逆函式151

習題5.4152

5.5計算機科學中的常用函式153

習題5.5159

*5.6雙射函式及集合的勢160

習題5.6165

擴展閱讀165

第6章偏序關係、偏序集與格/167

6.1偏序關係和偏序集167

6.1.1偏序關係和偏序集的定義與性質167

6.1.2積偏序和字典序169

6.1.3哈斯圖170

習題6.1172

6.2偏序集中的特殊元素173

6.2.1偏序集中的特殊元素173

6.2.2拓撲排序176

*6.2.3有限偏序集的高度與寬度178

習題6.2180

6.3格與布爾代數181

6.3.1格的定義181

6.3.2特殊的格185

*6.3.3布爾代數190

習題6.3193

擴展閱讀196

第7章代數結構/197

7.1運算與代數結構198

7.1.1運算與代數結構的定義198

7.1.2二元運算的性質200

習題7.1204

7.2群206

7.2.1半群與亞群206

7.2.2群的概念207

7.2.3群的性質209

7.2.4子群210

7.2.5群的同態與同構211

7.2.6循環群213

7.2.7變換群與置換群215

7.2.8陪集與拉格朗日定理217

習題7.2220

*7.3環與域224

7.3.1環224

7.3.2域226

習題7.3227

*7.4作為代數結構的格與布爾代數228

習題7.4231

擴展閱讀231

第8章圖論/232

8.1基本概念233

8.1.1無向圖、有向圖和握手定理233

8.1.2圖的同構與子圖240

8.1.3道路、迴路與連通性242

8.1.4圖的矩陣表示244

習題8.1246

8.2歐拉圖250

習題8.2254

8.3哈密頓圖255

習題8.3261

8.4平面圖262

習題8.4269

8.5頂點支配、獨立與覆蓋271

習題8.5275

8.6匹配275

8.6.1匹配與最大匹配275

8.6.2霍爾定理及其套用280

*8.6.3匹配與邊覆蓋283

8.6.4匹配與點覆蓋285

*8.6.5二部圖中的最佳匹配289

習題8.6292

8.7圖的著色295

習題8.7301

8.8網路與流302

8.8.1最大流與最小割302

8.8.2網路流的套用317

習題8.8322

*8.9圖的連通度324

習題8.9325

擴展閱讀325

第9章樹及其套用/328

9.1無向樹328

習題9.1332

9.2支撐樹及其套用333

習題9.2346

9.3最短道路樹347

習題9.3351

9.4根樹及其套用352

9.4.1根樹的定義和基本概念352

9.4.2二叉樹的遍歷357

9.4.3最優二叉樹與霍夫曼編碼361

習題9.4364

擴展閱讀366

第10章形式語言、自動機與正則表達式/367

10.1語言368

習題10.1371

10.2文法372

習題10.2378

10.3巴科斯*諾爾範式和語法圖379

習題10.3381

10.4有限狀態自動機382

習題10.4388

10.5語言與自動機的關係391

習題10.5393

10.6正則表達式393

習題10.6395

*10.7圖靈機396

習題10.7399

擴展閱讀399

附錄A離散數學綜合性研討專題/402

A.1郵資、分油、登階、檯球與波利亞的果園402

A.1.1郵資問題402

A.1.2分油問題404

A.1.3登階問題408

A.1.4檯球問題410

A.1.5波利亞的果園問題412

A.2基於模運算的校驗碼415

A.2.1EAN13碼415

A.2.2國際標準書號416

A.2.3第二代居民身份證416

A.2.4國際標準刊號418

A.3套用鴿巢原理的兩個紙牌魔術418

A.3.1紙牌魔術A419

A.3.2紙牌魔術B421

A.4完美洗牌法421

A.5百囚犯問題424

A.615謎題427

A.7Chomp遊戲428

A.8安全信息流的格模型431

A.9麻花辮434

A.10伯恩賽德引理與波利亞定理438

A.11頓時錯亂問題443

A.12博弈樹與決策樹447

A.12.1博弈樹447

A.12.2決策樹449

A.13抽芽遊戲與抱子甘藍遊戲453

A.13.1抽芽遊戲453

A.13.2抱子甘藍遊戲456

A.14存儲器輪458

A.14.1存儲器輪及解決方法458

A.14.2德布魯因序列460

A.15中國郵路問題464

A.16格雷碼、超立方體圖中的哈密頓道路、九連環和龍曲線467

A.16.1格雷碼467

A.16.2超立方體圖中的哈密頓道路469

A.16.3九連環與格雷碼471

A.16.4龍曲線474

A.17社會網路中的結構平衡475

A.18市場清倉與單品拍賣477

A.19漢諾塔雜談480

A.19.1漢諾塔圖480

A.19.2漢諾塔的非遞歸算法483

A.19.3漢諾塔與格雷碼484

A.19.4漢諾塔與普通二進制碼487

A.20謝爾賓斯基三角形488

A.21密碼算法簡介495

線上附錄列表/500

註：目錄排版順序為從左列至右列

教學資源

配套教材

《離散數學及套用（第3版）》有配套學習指導書《離散數學及套用學習指導與習題解析》。

名稱	出版社	出版時間	ISBN	作者
離散數學及套用學習指導與習題解析	清華大學出版社	2022.5.1	9787302592624	劉鐸

課程資源

《離散數學及套用（第3版）》為慕課“離散數學”的指定教材。

課程名稱	類別	建設院校	授課平台	授課教師
離散數學	國家精品線上開放課程	北京交通大學	中國大學MOOC	劉鐸、趙宏、陳旭東、張順利

教材特色

該教材著重講解基本概念、基本方法及其套用，減少需要記憶的內容。除嚴謹系統的理論闡述和細緻詳盡的內容講解外，該書給出了典型例題、套用實例和難易程度不同的習題，而且還設計了幾個綜合的套用案例和實驗項目，學生可以利用這些內容加深對基本內容的理解和掌握，更可以動手體會分析問題和解決問題的過程，提高學習的興趣和效果。

該教材的內容由淺入深，可讀性較強，部分內容比較抽象的章節在標題前加了*號，教師可根據實際情況選擇使用。

作者簡介

劉鐸，博士畢業於清華大學計算機科學與技術系，北京交通大學軟體學院副教授。研究方向：軟體工程理論與技術、人工智慧與大數據、軟體服務工程、智慧型交通領域軟體工程、軟體工程。

離散數學及套用（第3版）

基本介紹

成書過程

修訂情況

出版工作

內容簡介

教材目錄

教學資源

配套教材

課程資源

教材特色

作者簡介

教材目錄

教學資源

配套教材

課程資源

教材特色

作者簡介

相關詞條

熱門詞條