離散數學（第3版）(屈婉玲、耿素雲、張立昂編著的書籍)

成書過程

修訂情況

該教材是參照ACM和IEEE推出的Computing Curricula，根據教育部高等學校計算機科學與技術教學指導委員會編制的“高等學校計算機科學與技術專業規範”中制定的關於離散數學的知識結構和體系撰寫的。

該教材對第1章“數學語言與證明方法”做了部分重寫，對重要的數學證明方法進行了分類和較詳細的闡述，補充了有關遞歸定義的內容。第5章補充了關係與函式在資料庫及軟體工程建模中的套用實例。第6章增加了二部圖的匹配、著色和四色定理。第7章刪除了基本迴路與基本割集系統。第10章對遞推方程在算法設計與分析中的套用加以補充。

出版工作

2014年1月1日，該教材由清華大學出版社出版。

出版社工作人員

責任編輯	封面設計	責任校對	責任印製
張瑞慶	傅瑞學	焦麗麗	何芊

內容簡介

全書共14章，內容包含數學語言與證明方法、證明技巧、數理邏輯、集合與關係、函式、組合計數、圖和樹、容斥原理、遞推方程與生成函式、初等數論、離散機率、代數系統等。此外，每一章節末尾都配有習題。

教材目錄

1.1常用的數學符號1

1.1.1集合符號1

1.1.2運算符號2

1.1.3邏輯符號2

1.2集合及其運算3

1.2.1集合及其表示法3

1.2.2集合之間的包含與相等4

1.2.3集合的冪集5

1.2.4集合的運算6

1.2.5基本集合恆等式及其套用8

1.3證明方法概述11

1.3.1直接證明法和歸謬法12

1.3.2分情況證明法和構造性證明法12

1.3.3數學歸納法14

1.4遞歸定義16

習題17

第2章命題邏輯22

2.1命題邏輯基本概念22

2.1.1命題與聯結詞22

2.1.2命題公式及其分類28

2.2命題邏輯等值演算33

2.2.1等值式與等值演算33

2.2.2聯結詞完備集37

2.3範式39

2.3.1析取範式與合取範式39

2.3.2主析取範式與主合取範式42

2.4推理49

2.4.1推理的形式結構49

2.4.2推理的證明51

2.4.3歸結證明法57

2.4.4對證明方法的補充說明60

習題60

第3章一階邏輯66

3.1一階邏輯基本概念66

3.1.1命題邏輯的局限性66

3.1.2個體詞、謂詞與量詞66

3.1.3一階邏輯命題符號化68

3.1.4一階邏輯公式與分類71

3.2一階邏輯等值演算75

3.2.1一階邏輯等值式與置換規則75

3.2.2一階邏輯前束範式79

習題81

第4章關係86

4.1關係的定義及其表示86

4.1.1有序對與笛卡兒積86

4.1.2二元關係的定義87

4.1.3二元關係的表示89

4.2關係的運算90

4.2.1關係的基本運算90

4.2.2關係的冪運算93

4.3關係的性質96

4.3.1關係性質的定義和判別96

4.3.2關係的閉包100

4.4等價關係與偏序關係104

4.4.1等價關係104

4.4.2等價類和商集104

4.4.3集合的劃分105

4.4.4偏序關係107

4.4.5偏序集與哈斯圖108

習題112

第5章函式116

5.1函式的定義及其性質116

5.1.1函式的定義116

5.1.2函式的像與完全原像118

5.1.3函式的性質119

5.2函式的複合與反函式122

5.2.1函式的複合122

5.2.2反函式124

習題128

第6章圖132

6.1圖的基本概念132

6.1.1無向圖與有向圖132

6.1.2頂點的度數與握手定理134

6.1.3簡單圖、完全圖、正則圖、圈圖、輪圖、方體圖136

6.1.4子圖、補圖138

6.1.5圖的同構139

6.2圖的連通性141

6.2.1通路與迴路141

6.2.2無向圖的連通性與連通度141

6.2.3有向圖的連通性及其分類144

6.3圖的矩陣表示144

6.3.1無向圖的關聯矩陣144

6.3.2有向無環圖的關聯矩陣145

6.3.3有向圖的鄰接矩陣146

6.3.4有向圖的可達矩陣147

6.4幾種特殊的圖149

6.4.1二部圖149

6.4.2歐拉圖152

6.4.3哈密頓圖154

6.4.4平面圖157

習題166

第7章樹及其套用173

7.1無向樹173

7.1.1無向樹的定義及其性質173

7.1.2生成樹176

7.2根樹及其套用177

7.2.1根樹及其分類177

7.2.2最優樹與哈夫曼算法178

7.2.3最佳前綴碼179

7.2.4根樹的週遊及其套用181

習題182

8.1基本計數規則186

8.1.1加法法則186

8.1.2乘法法則186

8.1.3分類處理與分步處理187

8.2排列與組合187

8.2.1集合的排列與組合188

8.2.2多重集的排列與組合191

8.3二項式定理與組合恆等式193

8.3.1二項式定理193

8.3.2組合恆等式194

8.3.3非降路徑問題198

8.4多項式定理與多項式係數201

8.4.1多項式定理201

8.4.2多項式係數202

習題203

第9章容斥原理206

9.1容斥原理及其套用206

9.1.1容斥原理的基本形式206

9.1.2容斥原理的套用207

9.2對稱篩公式及其套用210

9.2.1對稱篩公式210

9.2.2棋盤多項式與有限制條件的排列212

習題215

第10章遞推方程與生成函式217

10.1遞推方程及其套用217

10.1.1遞推方程的定義及實例217

10.1.2常係數線性齊次遞推方程的求解219

10.1.3常係數線性非齊次遞推方程的求解222

10.1.4遞推方程的其他解法224

10.1.5遞推方程與遞歸算法228

10.2生成函式及其套用233

10.2.1牛頓二項式定理與牛頓二項式係數233

10.2.2生成函式的定義及其性質234

10.2.3生成函式的套用236

10.3指數生成函式及其套用241

10.4Catalan數與Stirling數243

習題248

第11章初等數論251

11.1素數251

11.2最大公約數與最低公倍數254

11.3同餘257

11.4一次同餘方程與中國剩餘定理259

11.4.1一次同餘方程259

11.4.2中國剩餘定理260

11.4.3大整數算術運算262

11.5歐拉定理和費馬小定理263

習題264

第12章離散機率268

12.1隨機事件與機率、事件的運算268

12.1.1隨機事件與機率268

12.1.2事件的運算270

12.2條件機率與獨立性271

12.2.1條件機率271

12.2.2獨立性273

12.2.3伯努利概型與二項機率公式273

12.3離散型隨機變數274

12.3.1離散型隨機變數及其分布律274

12.3.2常用分布275

12.3.3數學期望276

12.3.4方差278

12.4機率母函式280

習題282

第13章初等數論和離散機率的套用286

13.1密碼學286

13.1.1愷撒密碼286

13.1.2RSA公鑰密碼287

13.2產生偽隨機數的方法289

13.2.1產生均勻偽隨機數的方法289

13.2.2產生離散型偽隨機數的方法290

13.3算法的平均複雜度分析292

13.3.1排序算法292

13.3.2散列表的檢索和插入295

13.4隨機算法298

13.4.1隨機快速排序算法298

13.4.2多項式恆零測試299

13.4.3素數測試301

13.4.4蒙特卡羅法和拉斯維加斯法302

習題303

第14章代數系統306

14.1二元運算及其性質306

14.1.1二元運算與一元運算的定義306

14.1.2二元運算的性質308

14.2代數系統311

14.2.1代數系統的定義與實例311

14.2.2代數系統的分類312

14.2.3子代數系統與積代數系統313

14.2.4代數系統的同態與同構314

14.3幾個典型的代數系統315

14.3.1半群與獨異點315

14.3.2群317

14.3.3環與域323

14.3.4格與布爾代數325

習題330

參考文獻335

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

教學資源

配套教材

該教材有配套的習題解答與學習指導等教學輔導用書——《離散數學習題解答與學習指導（第3版）》。

書名	書號	出版社	作者
《離散數學習題解答與學習指導（第3版）》	9787302339908	清華大學出版社	屈婉玲、耿素雲、張立昂

課程資源

該教材提供用於課堂教學的PPT演示文稿和線上數字資源等。

教材特色

該教材注重與計算機科學技術的實際問題相結合，並選配了難度適當的習題。

在教材編寫過程中，作者在素材組織上更加注重在計算機科學技術中的套用。

作者簡介

屈婉玲，1969年畢業於北京大學物理系物理學專業，北京大學信息科學技術學院教授、博士生導師，中國人工智慧學會離散數學專委會委員，主要研究方向是算法設計與分析，所講授的離散數學課程被評為國家級精品課程，兩次被評為北京大學十佳教師。

耿素雲，1965年畢業於北京大學數學力學係數學專業，北大信息科學技術學院教授。一直從事數學教學。獲北京市教育教學成果（高等教育）一等獎，北京大學教學成果一等獎、大眾電腦獎教金、桐山獎教金及教學優秀獎等。

張立昂，1965年畢業於北京大學數學力學係數學專業，北京大學信息科學技術學院教授、博士生導師。一直從事數學和理論計算機科學的教學與研究，主要研究方向是計算複雜性理論和算法設計與分析。