離散數學：電腦數學基礎教程（簡體書）

自然界廣泛地存在著離散事物，離散數學就是用適當的數學工具來描述和研究離散對象以及離散對象(Discrete Objects)之間各種相互關系的數學分支。尤其在計算機科學迅速發展的今天，離散數學的研究就更重要了。離散數學的內容很廣，如集合論、組合論、圖論、群論、數理邏輯等，由于概率論，算法論等也研究離散對象，有人把它們也歸納到離散數學之中。通常，概率論，算法分析已單獨列為一門課，此教材中就不包括這些內容了。作為一門計算機專業的基礎課，我們著重介紹集合論(集合，自然數集，二元關系)，組合論(離散函數，計數與生成)，圖論(圖，樹)，群論(群，環，域)以及數理邏輯(命題邏輯，謂詞邏輯)中較基本的及與計算機科學有較密切聯系的內容。本教材是按本人上課用的講稿寫的。最早參考的是金廷贊老師的離散數學講義，素材主要取自Liu，Chung Laung在美國E11inois大學計算機科學系任教時的講義基礎上寫的課本：“Elements of Discete mathematics”，同時參考了J．P．Trembley和R．Manohar著的“離散數學結構及其在計算機科學中的應用”，以及Leon S．Levy著的“Discr-ete Structures of Computer Science”，還有BobrOW和Arbib著的“Discrete Mathematics”等書。后來，又參考左孝凌、張一立、周以銓、洪帆等老師在國內出版的離散數學教材，補充了內容，增加了例子，添上了數理邏輯一章，并在每章后附上了習題。經過1993年、1996年、1997年三次膠印，每次都作了修改和補充，張三元老師參加了修改工作。為了引導學生開闊思路，盡量把自己學習的體會貫穿在教材中。例如：把看上去似乎很簡單的概念進行深入一些的講解；增加一些例子以增強感性認識；指出某些常見的錯誤；加強前后知識之間的聯系等。教材自始至終保持數學的嚴格性，對于如何證明命題的成立，每一章都有一些示范。編入了不少結合計算機應用的啟蒙算法，為學生學以致用搭起了橋梁。編此書的愿望是使學生能學到離散數學的思想方法與處理問題的技巧，且希望達到深入淺出，更便于自學的目的。按講稿寫數學教材是一種嘗試，教學效果怎樣有待試驗，各種缺點在所難免，歡迎大家批評指正。

第一章　集合
　1 集合
　2　集合的運算及文氏圖
　3　笛卡兒積
　4　集合的基數
　習題
第二章　歸納方法
　1　自然數集與皮亞諾公理
　2　數學歸納法
　習題
第三章　二元關系
　1　二元關系
　2　二元關系的運算
　3　A上各類二元關系的性質
　4　等價關系
　5　半序關系
　習題
第四章　離散函數
　1　鴿洞原理
　2　離散數值函數
　3　離散數值函數的生成函數
　4　離散數值函數的遞推關系
　習題
第五章　計數與生成
　1　事件及計數原則
　2　典型計數問題
　3　生成函數與排列組合
　4　利用遞推關系計數
　5　排列與組合的生成算法
　習題
第六章　數理邏輯基礎
　1　命題邏輯
　習題
　2　謂詞邏輯
習題
第七章　圖論
　1 圖的概念
　2　圖的矩陣表示
　3　加權圖中的最短道路問題
　4　歐拉道路與歐拉回路
　5　哈密頓道路
　6　平面圖
　7 圖的著色
　習題
第八章　樹
　1　樹的概念和性質
　2　有根樹
　3　前綴碼
　4　二元檢索樹
　5　生成樹
　習題
第九章　群和環
　1　代數系統
　2　群
　3　陪集及其應用
　4　同構與同態
　5　環和域
　6　多項式環與循環瑪
　習題
離散數學習題參考答案