離散數學（第五版）

成書過程

修訂情況

該教材根據教育部計算機科學與技術專業教學指導委員會提出的《計算機科學與技術專業規範》和《高等學校計算機科學與技術專業核心課程教學實施方案》的建議，結合信息管理與信息系統專業的教學要求編寫而成。

主要修訂如下：

將代數結構部分的內容進行了整合，並調整到教材的最後；
圖論部分（第5～第7章）的敘述有較大的改動；
增添了一些內容，主要是與離散數學套用相關的內容，它們是組合電路（第1章），歐拉函式（第3章），著色問題（第5章），地圖著色與四色定理、格雷碼（第6章）等；
對部分習題做了補充和調整。

（第1、2、7、8、9章）由耿素雲編寫；集合論、代數結構、組合分析初步（第3、4、5、6、10章）由屈婉玲編寫；形式語言與自動機初步（第11章）由張立昂編寫。

出版工作

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

出版社工作人員

責任編輯	封面設計	責任校對	責任印製
白立軍	傅瑞學	時翠蘭	何芊

內容簡介

該教材共10章，內容包括命題邏輯，一階邏輯，集合的基本概念和運算，二元關係和函式，圖的基本概念，特殊的圖，樹，組合分析初步，代數系統簡介，形式語言和自動機初步。

教材目錄

第1章命題邏輯1

1.1命題符號化及聯結詞1

1.2命題公式及分類5

1.3等值演算8

1.4範式12

1.5聯結詞全功能集17

1.6組合電路19

1.7推理理論21

1.8題例分析26

習題31

第2章一階邏輯37

2.1一階邏輯基本概念37

2.2一階邏輯合式公式及解釋42

2.3一階邏輯等值式與前束範式46

2.4題例分析49

習題52

第3章集合的基本概念和運算56

3.1集合的基本概念56

3.2集合的基本運算58

3.3集合中元素的計數63

3.4題例分析67

習題71

第4章二元關係和函式76

4.1集合的笛卡兒積與二元關係76

4.2關係的運算80

4.3關係的性質85

4.4關係的閉包87

4.5等價關係和偏序關係89

4.6函式的定義和性質94

4.7函式的複合和反函式98

4.8題例分析106

習題112

第5章圖的基本概念118

5.1無向圖及有向圖118

5.2通路、迴路和圖的連通性123

5.3圖的矩陣表示125

5.4最短路徑、關鍵路徑和著色128

5.5題例分析134

習題137

第6章特殊的圖140

6.1二部圖140

6.2歐拉圖142

6.3哈密頓圖144

6.4平面圖146

6.5題例分析151

習題154

第7章樹157

7.1無向樹及生成樹157

7.2根樹及其套用161

7.3題例分析167

習題171

第8章組合分析初步174

8.1加法法則和乘法法則174

8.2基本排列組合的計數方法175

8.3遞推方程的求解與套用181

8.4題例分析187

習題192

第9章代數系統簡介196

9.1二元運算及其性質196

9.2代數系統202

9.3幾個典型的代數系統206

9.4題例分析218

習題223

第10章形式語言和自動機初步230

10.1形式語言和形式文法230

10.1.1字元串和形式語言230

10.1.2形式文法231

10.1.3形式文法的分類234

10.2有窮自動機237

10.2.1基本概念237

10.2.2非確定型有窮自動機238

10.2.3帶ε轉移的非確定型有窮自動機240

10.3有窮自動機和正則文法的等價性242

10.4圖靈機244

10.4.1圖靈機的基本模型245

10.4.2用圖靈機計算函式248

10.5題例分析250

習題254

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

教學資源

配套教材

該教材有配套教材——《離散數學題解（第五版）》。

書名	書號	出版社	作者
《離散數學題解（第五版）》	9787302325086	清華大學出版社	屈婉玲、耿素雲、張立昂

課程資源

該教材提供PPT電子教案。

教材特色

該教材著重於基本概念的論述和套用，而不著重於定理的證明。每章均給出了典型的題例分析，並配置了相當數量的習題，書後給出了大部分習題的提示或解答。

該教材第五版在保持原有寫作風格的基礎上，除了對文字做了進一步加工，糾正了某些疏漏以外，並對部分內容進行了調整。

作者簡介

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