離散數學（第2版）（簡體書）

本教材是參照ACM和IEEE最新推出的Computing Curricula 2005，根據教育部高等學校計算機科學與技術教學指導委員會最新編制的“高等學校計算機科學與技術專業規范”中制定的關于離散數學的知識結構和體系撰寫的。全書共14章，內容包含證明技巧、數理邏輯、集合與關系、函數、組合計數、圖和樹、初等數論、離散概率、代數系統等。本書體系嚴謹，選材精煉，講解翔實，例題豐富，注重與計算機科學技術的實際問題相結合，并選配了大量難度適當的習題，適合教學，另外，本書有配套的習題解答與學習指導等教學輔導用書，以滿足教學需要。 本書適合作為高等學校計算機及相關專業本科生“離散數學”課程的教材，也可以作為對離散數學感興趣的人員的入門參考書。

屈婉玲，1969年畢業于北京大學物理系物理學專業，現任北京大學信息科學技術學院教授、博士生導師，中國人工智能學會離敞數學專委會委員。主要研究方向是算法設計與分析，發表論文20多篇，出版教材、數學參考書、譯著20多部，其中包含多部國家級規劃教材和北京市精品教材。所講授的離散數學課程被評為國家級精品課程，兩次被評為北京大學十佳教師，獲得北京市優秀教師稱號。曾主持過多項國家級教材和課程建設項日，并獲得北京市教育教學成果（高等教育）一等獎。

第1章　數學語言與證明方法
　1.1　常用的數學符號
1.1.1　集合符號
1.1.2　運算符號
1.1.3　邏輯符號
　1.2　集合及其運算
1.2.1　集合及其表示法
1.2.2　集合之間的包含與相等　
1.2.3　集合的冪集
1.2.4　集合的運算
1 2.5　基本集合恒等式及其應用
　1.3　證明方法概述
1.3.1　邏輯推理的形式結構
1.3.2　公理、定理與證明
1.3.3　證明方法
1.3.4　數學歸納法
　習題
第2章　命題邏輯
　2.1　命題邏輯基本概念
2.1.1　命題與聯結詞
2.1.2　命題公式及其分類
　2.2　命題邏輯等值演算
2.2.1　等值式與等值演算
2.2.2　聯結詞完備集
　2.3　范式
2.3.1　析取范式與合取范式
2.3.2　主析取范式與主合取范式
　2.4　命題邏輯推理理論
2.4.1　推理的形式結構
2.4.2 自然推理系統P
2.4.3　歸結證明法
　習題
第3章　一階邏輯
　3.1　一階邏輯基本概念
3.1.1　命題邏輯的局限性
3.1.2　個體詞、謂詞與量詞
3.1.3　一階邏輯命題符號化
3.1.4　一階邏輯公式與分類
　3.2　一階邏輯等值演算
3.2.1　一階邏輯等值式與置換規則
3.2.2　一階邏輯前束范式
　習題
第4章　關系
　4.1　關系的定義及其表示
4.1.1　有序對與笛卡兒積
4.1.2　二元關系的定義
4.1.3　二元關系的表示
　4.2　關系的運算
4.2.1　關系的基本運算
4.2.2　關系的冪運算
　4.3　關系的性質
4.3.1　關系性質的定義和判別
4.3.2　關系的閉包
　4.4　等價關系與偏序關系
4.4.1　等價關系
4.4.2　等價類和商集
4.4.3　集合的劃分
4.4.4　偏序集與哈斯圖
4.4.5　偏序集與哈斯圖
　習題
第5章　函數
第6章　圖
第7章　樹及其應用
第8章　組合計數基礎
第9章　容斥原理
第10章　遞推方程與生成函數
第11章　初等數論
第12章　離散概率
第13章　初等數論和離散概率的應用
第14章　代數系統
參考文獻