第1章 數學語言與證明方法1
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分情況證明法和構造性證明法13
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
目錄離散數學（第4版）第3章 一階邏輯66
3.1一階邏輯基本概念66
3.1.1命題邏輯的局限性66
3.1.2個體詞、謂詞與量詞66
3.1.3一階邏輯命題符號化68
3.1.4一階邏輯公式與分類71
3.2一階邏輯等值演算76
3.2.1一階邏輯等值式與置換規則76
3.2.2一階邏輯前束範式79
習題81
第4章 關繫86
4.1關繫的定義及其表示86
4.1.1有序對與笛卡兒積86
4.1關繫的定義87
4.1關繫的表示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集合的劃分106
4.4.4偏序關繫107
4.4.5偏序集與哈斯圖 108
習題112
第5章 函數117
5.1函數的定義及其性質117
5.1.1函數的定義117
5.1.2函數的像與完全原像  119
5.1.3函數的性質   120
5.2函數的復合與反函數123
5.2.1函數的復合123
5.2.2反函數125
習題129
第6章 圖133
6.1圖的基本概念133
6.1.1無向圖與有向圖133
6.1.2頂點的度數與握手定理135
6.1.3簡單圖、完全圖、正則圖、圈圖、輪圖、方體圖137
6.1.4子圖、補圖139
6.1.5圖的同構140
6.2圖的連通性142
6.2.1通路與回路142
6.2.2無向圖的連通性與連通度142
6.2.3有向圖的連通性及其分類145
6.3圖的矩陣表示145
6.3.1無向圖的關聯矩陣145
6.3.2有向無環圖的關聯矩陣146
6.3.3有向圖的鄰接矩陣147
6.3.4有向圖的可達矩陣148
6.4幾種特殊的圖150
6.4.1二部圖150
6.4.2歐拉圖153
6.4.3哈密頓圖154
6.4.4平面圖158
習題167
第7章 樹及其應用174
7.1無向樹174
7.1.1無向樹的定義及其性質174
7.1.2生成樹177
7.2根樹及其應用178
7.2.1根樹及其分類178
7.2.2樹與哈夫曼算法179
7.2.3前綴碼180
7.2.4根樹的周遊及其應用182
習題183
第8章 組合計數基礎186
8.1基本計數規則187
8.1.1加法法則187
8.1.2乘法法則187
8.1.3分類處理與分步處理188
8.2排列與組合188
8.2.1集合的排列與組合189
8.2.2多重集的排列與組合192
8.3二項式定理與組合恆等式194
8.3.1二項式定理194
8.3.2組合恆等式195
8.3.3非降路徑問題200
8.4多項式定理與多項式繫數202
8.4.1多項式定理202
8.4.2多項式繫數203
習題204
第9章 容斥原理207
9.1容斥原理及其應用207
9.1.1容斥原理的基本形式207
9.1.2容斥原理的應用208
9.2對稱篩公式及其應用211
9.2.1對稱篩公式211
9.2.2棋盤多項式與有限制條件的排列213
習題216
第10章 遞推方程與生成函數218
10.1遞推方程及其應用218
10.1.1遞推方程的定義及實例218
10.1.2常繫數線性齊次遞推方程的求解220
10.1.3常繫數線性非齊次遞推方程的求解223
10.1.4遞推方程的其他解法225
10.1.5遞推方程與遞歸算法229
10.2生成函數及其應用234
10.2.1牛頓二項式定理與牛頓二項式繫數234
10.2.2生成函數的定義及其性質235
10.2.3生成函數的應用237
10.3指數生成函數及其應用242
10.4Catalan數與Stirling數244
習題249
第11章 初等數論252
11.1素數252
11.2公約數與小公倍數255
11.3同餘258
11.4一次同餘方程與中國剩餘定理260
11.4.1一次同餘方程260
11.4.2中國剩餘定理262
11.4.3大整數算術運算263
11.5歐拉定理和費馬小定理264
習題265
第12章 離散概率269
12.1隨機事件與概率、事件的運算269
12.1.1隨機事件與概率269
12.1.2事件的運算271
12.2條件概率與獨立性272
12.2.1條件概率272
12.2.2獨立性274
12.2.3伯努利概型與二項概率公式274
12.3離散型隨機變量275
12.3.1離散型隨機變量及其分布律275
12.3.2常用分布276
12.3.3數學期望278
12.3.4方差279
12.4概率母函數281
習題283
第13章 初等數論和離散概率的應用287
13.1密碼學287
13.1.1凱撒密碼287
13.1.2RSA公鑰密碼288
13.2產生偽隨機數的方法290
13.2.1產生均勻偽隨機數的方法290
13.2.2產生離散型偽隨機數的方法291
13.3算法的平均復雜度分析293
13.3.1排序算法293
13.3.2散列表的檢索和插入296
13.4隨機算法299
13.4.1隨機快速排序算法299
13.4.2多項式恆零測試300
13.4.3素數測試302
13.4.4蒙特卡羅法和拉斯維加斯法303
習題304
第14章 代數繫統307
14運算及其性質307
14.1運運算的定義307
14.1運算的性質309
14.2代數繫統312
14.2.1代數繫統的定義與實例312
14.2.2代數繫統的分類313
14.2.3子代數繫統與積代數繫統314
14.2.4代數繫統的同態與同構315
14.3幾個典型的代數繫統316
14.3.1半群與獨異點316
14.3.2群318
14.3.3環與域324
14.3.4格與布爾代數327
14.4皮亞諾繫統332
習題334
參考文獻338

清華大學出版社“21世紀大學本科計算機專業繫列教材”《離散數學（第3版）》已經出版8年了. 在這8年裡，計算機科學技術又有了長足的發展，新的技術不斷湧現，從人機對弈，到人臉識別和自動駕駛，新技術的應用場景不斷擴大. 對計算機專業的需求也不斷擴大，在全球範圍內，學習計算機專業的學生人數不斷增加. 因此，為高等學校計算機專業的師生提供好的教材，就成了很有意義的工作. 
作為計算機專業的基礎課之一，離散數學的內容相對穩定，傳統上主要包括數理邏輯、集合論、圖論、組合數學、代數結構等. 本書在這些內容之外，還覆蓋了初等數論和離散概率、算法的平均情況復雜度分析、隨機算法等內容. 書中還舉例說明了離散數學中的各種概念和結論在關繫數據庫、工作流模型、密碼學、算法分析等領域的應用. 本書有大量難度適當的習題，並有配套的習題解答和電子教案，既方便師生的課堂教學，也方便對離散數學感興趣的讀者自學. 
從本書初版到現在已經有十幾個年頭了，經過之前的兩次修訂改版和多年的實際使用，內容已經相當成熟. 這次修訂在內容上沒有做大的改動，除了更正一些錯誤，以及對文字做了進一步的精細加工外，主要是在第14章代數繫統的內容裡增加了後一節，介紹了皮亞諾繫統，補充了相應的習題. 皮亞諾繫統給出了自然數集的嚴格定義，在此基礎上，可以定義自然數的各種運算並證明這些運算的性質. 在這個過程裡，要綜合運用本課程前面學過的集合、函數、遞歸定義、歸納證明、代數繫統的同構等概念和技巧. 
作者衷心感謝廣大讀者和清華大學出版社的支持和鼓勵. 此次修訂主要由劉田完成. 不當之處，歡迎廣大讀者批評指正.作者
2022年3月於北京大學第3版前言FOREWORD作為清華大學出版社和中國計算機學會共同規劃的“21世紀大學本科計算機專業繫列教材”之一，《離散數學(第2版)》已經出版5年了. 在這5年裡，一些新的教育理念、教學模式不斷提出並加以實踐，其中重要的是“計算思維（computational thinking）”和“大規模開放式在線課程(massive open online course,MOOC)”. 計算思維是數學思維與工程思維的互補與融合，不但是從事計算機科學技術工作的人所需要的專業素質，也對其他學科的發展產生了深遠的影響，計算思維的培養已經成為大學計算機專業的重要目標之一. MOOC教學模式近年來在國外迅速增長，已經產生了巨大的影響；國內也把優質教學資源共享列入國家計劃並給予了大力支持.  這些新的教育理念和教學模式對教材的修訂有著重要的影響.  
離散數學是研究離散結構及其性質的學科，大量用於計算機繫統及其應用領域的建模及分析.  離散數學對培養計算思維起著重要的作用，不但被列入計算機專業的核心課程，而且近年來電子工程、經濟學等專業領域也開始在教學中加入一些離散數學的內容.  如何在離散繫統建模中體現計算思維是本教材修訂的指導思想.  本著對讀者負責的精神，我們在這次修訂工作中認真地審閱了原書，對其中的部分內容做了調整，更正了某些錯誤和疏漏之處，並對文字做了進一步的精細加工. 
本版在內容上主要做了如下改動：   對第1章“數學語言與證明方法”做了部分重寫，對重要的數學證明方法進行了分類和較詳細的闡述，補充了有關遞歸定義的內容.  第5章補充了關繫與函數在數據庫及軟件工程建模中的應用實例.  第6章增加了二部圖的匹配、著色和四色定理.  第7章刪除了基本回路與基本割集繫統.  第10章對遞推方程在算法設計與分析中的應用加以補充.   
與本教材同步更新的有配套的教學輔導用書《離散數學習題解答與學習指導（第3版）》和用於課堂上教學的PPT演示文稿.  更多的後續教學資源正在開發，並將上傳到清華大學出版社的在線數字資源平臺上，為使用本書的讀者提供更大的支持.  
對廣大讀者所提出的建議和意見，我們表示衷心的感謝！作者
2013年8月於北京大學第2版前言FOREWORD作為清華大學出版社和中國計算機學會共同規劃的“21世紀大學本科計算機專業繫列教材”之一，《離散數學》已經出版兩年多了. 在這兩年多的時間裡，教育bu高等學校計算機科學與技術教學指導委員會編制了“高等學校計算機科學與技術專業規範”，教育bu更推出了一繫列為提高本科生教育質量的重要舉措，特別是2007年1月和2月分別發布的《教育bu、財政部關於實施高等學校本科教學質量與教學改革工程的意見》（教高\\[2007\\]1號）和《教育bu關於進一步深化本科教學改革，全面提高教學質量的若干意見》（教高\\[2007\\]2號），對專業設置、教學模式、課程建設、師資隊伍等各個方面不但提出了更高的建設目標，也為保證這一工程的順利執行提供了有力的保證. 
好的教師和好的教材是保證教學質量的前提條件. 本著對讀者負責的精神，我們在這次修訂工作中認真地審閱了原書，根據教學要求對其中的部分內容做了調整，更正了錯誤和疏漏之處，並對文字做了進一步的精細加工. 
本版在內容上主要做了如下改動： 去掉了數理邏輯中有關“一階邏輯推理理論”的內容. 主要原因是這部分內容涉及形式繫統. 形式繫統在繫統定義和推理中應該采用完全形式化的方法，通常包含形式語言以及用形式語言表述的公理和推理規則. 在形式繫統中，符號串本身是沒有語義的，隻能通過解釋賦予它們一定的語義，但在討論繫統的公理或推理規則時應該與語義無關. 本書在第1版的敘述中沒有完全采用這種形式化的方法. 如果從知識體繫的嚴謹性出發，應該采用這種完全形式化的表述方法. 但是，這不但與本書的整體寫作風格不夠協調，而且內容也偏深，超出本教材的要求，因此本次修訂決定刪掉這部分內容. 
為了進一步提高本書的質量，我們懇切地歡迎讀者繼續提出建議和意見. 作者
2007年11月於北京大學第1版前言FOREWORD科學技術的發展離不開基礎研究和創新. 19世紀至20世紀是人類科學技術飛速發展的時代，其中作為數學基礎的微積分為促進物理學和其他工程學科的發展起到至關重要的作用. 21世紀是信息時代，作為信息科學和計算機科學的數學基礎，離散數學受到越來越多的關注. 在美國ACM和IEEE推出的Computing Curricula 2005課程體繫和我國教育bu高等教育司組織評審通過的《中國計算機科學與技術學科教程 2002》（CCC2002）中,離散數學都被列入核心課程. 
離散數學研究各種離散形式的對像，研究它們的結構及其關繫，在數據結構、算法設計與分析、操作繫統、編譯繫統、人工智能、軟件工程、網絡與分布式計算、計算機圖形學、人機交互、數據庫以及計算機體繫結構等領域都得到了廣泛的應用. 除了計算機科學以外，在自動化、化學工程、生物學、經濟學等各個學科領域中，都廣泛使用數學建模，而離散數學是數學建模的重要工具之一. 離散數學已經成為計算機科學技術和相關專業的必修課程. 
除了作為多門課程必需的數學基礎之外，離散數學中所體現的現代數學思想對於加強學生的素質教育，培養學生的抽像思維和邏輯表達能力，提高發現問題、分析問題、解決問題的能力也有著不可替代的作用. 
國內外現已出版了各種版本的《離散數學》教材，取材差異很大，深淺不一，風格各異. 本教材是以《中國計算機科學與技術學科教程2002》中制定的關於離散數學的知識結構和體繫為依據撰寫的，主要內容包含證明技巧、數理邏輯、集合與關繫、函數、圖和樹、組合計數、初等數論、離散概率和代數繫統等. 在教材編寫過程中，作者力求體繫嚴謹、選材適當、適於教學，同時在素材組織上更加注重在計算機科學技術中的應用. 
全書共14章. 第1章介紹全書使用的數學語言（主要是命題邏輯符號和集合運算）與證明方法. 第2章和第3章分別介紹命題邏輯和一階邏輯的基本概念、等值演算和推理理論. 第4章和第5章介紹離散結構的集合表示——關繫和函數，討論關繫和函數的各種運算、性質、表示方法以及應用. 第6章和第7章介紹離散結構的圖形表示——圖和樹，包括圖的基本概念、圖的矩陣表示、特殊圖、無向樹和有向樹及其應用. 第8章到第10章介紹組合計數技術及其在計算機科學技術中的應用. 第11章到第13章介紹初等數論和離散概率及其在密碼學和算法分析中的應用. 第14章簡要介紹離散繫統的代數模型. 每章除了闡述相關的概念和定理之外，還配有典型的例題，並且選用或編寫了數十道難度適當的習題供課後練習使用. 
為了更好地為使用本教材的讀者服務，作者還撰寫和開發了與本教材配套的教學輔助用書和電子教案. 離散數學（第4版）本書的第1章至第3章和第6章、第7章由耿素雲編寫，第4章、第5章、第8章至第10章和第14章由屈婉玲編寫，第11章至第13章由張立昂編寫.
在編寫過程中，作者參考了國內外多種版本的《離散數學》教材和相關的文獻資料，從中吸取了許多好的思想，摘取了不少有用的素材，在此一並向有關作者致謝. 感謝“21世紀大學本科計算機專業繫列教材”編委會和清華大學出版社對本書出版的大力支持，特別要感謝李曉明教授，他在百忙之中認真地審閱了全稿，並提出了寶貴的修改意見，使作者受益匪淺. 我們更期待著廣大讀者，特別是使用本書作為教材的老師和學生對本書的批評、指正、建議和評論.

作者
2005年2月於北京大學