第3版前言
　　作為清華大學(xué)出版社的21世紀(jì)大學(xué)本科計(jì)算機(jī)專業(yè)系列教材之一，《離散數(shù)學(xué)》(第2版)已經(jīng)出版5年了.在這5年里，一些新的教育理念、教學(xué)模式不斷提出并加以實(shí)踐，其中最重要的是“計(jì)算思維（computational thinking）”和“大規(guī)模開放式在線課程(massive open online course,MOOC)”.計(jì)算思維是數(shù)學(xué)思維與工程思維的互補(bǔ)與融合，不但是從事計(jì)算機(jī)科學(xué)技術(shù)工作的人所需要的專業(yè)素質(zhì)，也對(duì)其他學(xué)科的發(fā)展產(chǎn)生了深遠(yuǎn)的影響，計(jì)算思維的培養(yǎng)已經(jīng)成為大學(xué)計(jì)算機(jī)專業(yè)的重要目標(biāo)之一.MOOC教學(xué)模式近年來(lái)在國(guó)外迅速增長(zhǎng)，已經(jīng)產(chǎn)生了巨大的影響；國(guó)內(nèi)也把優(yōu)質(zhì)教學(xué)資源共享列入國(guó)家計(jì)劃并給予了大力支持. 這些新的教育理念和教學(xué)模式對(duì)教材的修訂有著重要的影響.
　　離散數(shù)學(xué)是研究離散結(jié)構(gòu)及其性質(zhì)的學(xué)科，大量用于計(jì)算機(jī)系統(tǒng)及其應(yīng)用領(lǐng)域的建模及分析. 離散數(shù)學(xué)對(duì)培養(yǎng)計(jì)算思維起著重要的作用，不但被列入計(jì)算機(jī)專業(yè)的核心課程，而且近年來(lái)電子工程、經(jīng)濟(jì)學(xué)等專業(yè)領(lǐng)域也開始在教學(xué)中加入一些離散數(shù)學(xué)的內(nèi)容. 如何在離散系統(tǒng)建模中體現(xiàn)計(jì)算思維是本教材修訂的指導(dǎo)思想. 本著對(duì)讀者負(fù)責(zé)的精神，我們?cè)谶@次修訂工作中認(rèn)真地審閱了原書，對(duì)其中的部分內(nèi)容做了調(diào)整，更正了某些錯(cuò)誤和疏漏之處，并對(duì)文字做了進(jìn)一步的精細(xì)加工. 內(nèi)容上主要做了如下改動(dòng)：
　　對(duì)第1章“數(shù)學(xué)語(yǔ)言與證明方法”做了部分重寫，對(duì)重要的數(shù)學(xué)證明方法進(jìn)行了分類和較詳細(xì)的闡述，補(bǔ)充了有關(guān)遞歸定義的內(nèi)容. 第5章補(bǔ)充了關(guān)系與函數(shù)在數(shù)據(jù)庫(kù)及軟件工程建模中的應(yīng)用實(shí)例. 第6章增加了二部圖的匹配、著色和四色定理. 第7章刪除了基本回路與基本割集系統(tǒng). 第10章對(duì)遞推方程在算法設(shè)計(jì)與分析中的應(yīng)用加以補(bǔ)充.
　　與本教材同步更新的有配套的教學(xué)輔導(dǎo)用書《離散數(shù)學(xué)習(xí)題解答與學(xué)習(xí)指導(dǎo)》（第3版）和用于課堂上教學(xué)的PPT演示文稿. 更多的后續(xù)教學(xué)資源正在開發(fā)，并將上傳到清華大學(xué)出版社的在線數(shù)字資源平臺(tái)上，為使用本書的讀者提供更大的支持.
　　對(duì)廣大讀者所提出的建議和意見，我們表示衷心的感謝！
　　作者
　　2013年8月于北京大學(xué)

　　第2版前言
　　作為清華大學(xué)出版社和中國(guó)計(jì)算機(jī)學(xué)會(huì)共同規(guī)劃的“21世紀(jì)大學(xué)本科計(jì)算機(jī)專業(yè)系列教材”之一，這本《離散數(shù)學(xué)》已經(jīng)出版兩年多了.在這兩年多的時(shí)間里，教育部高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會(huì)編制了“高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)規(guī)范”，教育部更推出了一系列為提高本科生教育質(zhì)量的重要舉措，特別是2007年1月和2月分別發(fā)布的《教育部、財(cái)政部關(guān)于實(shí)施高等學(xué)校本科教學(xué)質(zhì)量與教學(xué)改革工程的意見》（教高\(yùn)[2007\]1號(hào)）和《教育部關(guān)于進(jìn)一步深化本科教學(xué)改革.全面提高教學(xué)質(zhì)量的若干意見》（教高\(yùn)[2007\]2號(hào)），對(duì)專業(yè)設(shè)置、教學(xué)模式、課程建設(shè)、師資隊(duì)伍等各個(gè)方面不但提出了更高的建設(shè)目標(biāo)，也為保證這一工程的順利執(zhí)行提供了有力的保證.
　　好的教師和好的教材是保證教學(xué)質(zhì)量的前提條件.本著對(duì)讀者負(fù)責(zé)的精神，我們?cè)谶@次修訂工作中認(rèn)真地審閱了原書，根據(jù)教學(xué)要求對(duì)其中的部分內(nèi)容做了調(diào)整，更正了某些錯(cuò)誤和疏漏之處，并對(duì)文字做了進(jìn)一步的精細(xì)加工.
本版在內(nèi)容上主要做了如下改動(dòng)： 去掉了數(shù)理邏輯中有關(guān)“一階邏輯推理理論”的內(nèi)容.主要原因是這部分內(nèi)容涉及形式系統(tǒng).形式系統(tǒng)在系統(tǒng)定義和推理中應(yīng)該采用完全形式化的方法，通常包含形式語(yǔ)言以及用形式語(yǔ)言表述的公理和推理規(guī)則.在形式系統(tǒng)中，符號(hào)串本身是沒(méi)有語(yǔ)義的，只能通過(guò)解釋賦予它們一定的語(yǔ)義，但在討論系統(tǒng)的公理或推理規(guī)則時(shí)應(yīng)該與語(yǔ)義無(wú)關(guān).本書在第1版的敘述中沒(méi)有完全采用這種形式化的方法.如果從知識(shí)體系的嚴(yán)謹(jǐn)性出發(fā)，應(yīng)該采用這種完全形式化的表述方法.但是，這不但與本書的整體寫作風(fēng)格不夠協(xié)調(diào)，而且內(nèi)容也偏深，超出本教材的要求，因此本次修訂決定刪掉這部分內(nèi)容.
　　為了進(jìn)一步提高本書的質(zhì)量，我們懇切地歡迎讀者繼續(xù)提出建議和意見.
　　作者
　　2007年11月于北京大學(xué)

　　第1版前言
　　科學(xué)技術(shù)的發(fā)展離不開基礎(chǔ)研究和創(chuàng)新.19世紀(jì)至20世紀(jì)是人類科學(xué)技術(shù)飛速發(fā)展的時(shí)代，其中作為數(shù)學(xué)基礎(chǔ)的微積分為促進(jìn)物理學(xué)和其他工程學(xué)科的發(fā)展起到至關(guān)重要的作用.21世紀(jì)是信息時(shí)代，作為信息科學(xué)和計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)，離散數(shù)學(xué)受到越來(lái)越多的關(guān)注.在美國(guó)ACM和IEEE最新推出的Computing Curricula 2005課程體系和我國(guó)教育部高等教育司組織評(píng)審?fù)ㄟ^(guò)的《中國(guó)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科教程 2002》（CCC2002）中,離散數(shù)學(xué)都被列入核心課程.
　　離散數(shù)學(xué)研究各種離散形式的對(duì)象，研究它們的結(jié)構(gòu)及其關(guān)系，在數(shù)據(jù)結(jié)構(gòu)、算法設(shè)計(jì)與分析、操作系統(tǒng)、編譯系統(tǒng)、人工智能、軟件工程、網(wǎng)絡(luò)與分布式計(jì)算、計(jì)算機(jī)圖形學(xué)、人機(jī)交互、數(shù)據(jù)庫(kù)以及計(jì)算機(jī)體系結(jié)構(gòu)等領(lǐng)域都得到了廣泛的應(yīng)用.除了計(jì)算機(jī)科學(xué)以外，在自動(dòng)化、化學(xué)工程、生物學(xué)、經(jīng)濟(jì)學(xué)等各個(gè)學(xué)科領(lǐng)域中，都廣泛使用數(shù)學(xué)建模，而離散數(shù)學(xué)是數(shù)學(xué)建模的重要工具之一.離散數(shù)學(xué)已經(jīng)成為計(jì)算機(jī)科學(xué)技術(shù)和相關(guān)專業(yè)的必修課程.
　　除了作為多門課程必需的數(shù)學(xué)基礎(chǔ)之外，離散數(shù)學(xué)中所體現(xiàn)的現(xiàn)代數(shù)學(xué)思想對(duì)于加強(qiáng)學(xué)生的素質(zhì)教育，培養(yǎng)學(xué)生的抽象思維和邏輯表達(dá)能力，提高發(fā)現(xiàn)問(wèn)題、分析問(wèn)題、解決問(wèn)題的能力也有著不可替代的作用.
　　國(guó)內(nèi)外現(xiàn)已出版了各種版本的《離散數(shù)學(xué)》教材，取材差異很大，深淺不一，風(fēng)格各異.本教材是以《中國(guó)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科教程2002》中制定的關(guān)于離散數(shù)學(xué)的知識(shí)結(jié)構(gòu)和體系為依據(jù)撰寫的，主要內(nèi)容包含證明技巧、數(shù)理邏輯、集合與關(guān)系、函數(shù)、圖和樹、組合計(jì)數(shù)、初等數(shù)論、離散概率和代數(shù)系統(tǒng)等.在教材編寫過(guò)程中，作者力求體系嚴(yán)謹(jǐn)、選材適當(dāng)、適于教學(xué)，同時(shí)在素材組織上更加注重在計(jì)算機(jī)科學(xué)技術(shù)中的應(yīng)用.
　　全書共分14章.第1章介紹全書使用的數(shù)學(xué)語(yǔ)言（主要是命題邏輯符號(hào)和集合運(yùn)算）與證明方法.第2章和第3章分別介紹命題邏輯和一階邏輯的基本概念、等值演算和推理理論.第4章和第5章介紹離散結(jié)構(gòu)的集合表示——關(guān)系和函數(shù)，討論關(guān)系和函數(shù)的各種運(yùn)算、性質(zhì)、表示方法以及應(yīng)用.第6章和第7章介紹離散結(jié)構(gòu)的圖形表示——圖和樹，包括圖的基本概念、圖的矩陣表示、特殊圖、無(wú)向樹和有向樹及其應(yīng)用.第8章到第10章介紹組合計(jì)數(shù)技術(shù)及其在計(jì)算機(jī)科學(xué)技術(shù)中的應(yīng)用.第11章到第13章介紹初等數(shù)論和離散概率及其在密碼學(xué)和算法分析中的應(yīng)用.第14章簡(jiǎn)要介紹離散系統(tǒng)的代數(shù)模型.每章除了闡述相關(guān)的概念和定理之外，還配有典型的例題，并且選用或編寫了數(shù)十道難度適當(dāng)?shù)牧?xí)題供課后練習(xí)使用.
　　為了更好地為使用本教材的讀者服務(wù)，作者還撰寫和開發(fā)了與本教材配套的教學(xué)輔助用書和電子教案.[]離散數(shù)學(xué)（第3版）[]本書的第1章至第3章和第6章、第7章由耿素云編寫；第4章、第5章、第8章至第10章和第14章由屈婉玲編寫；第11章至第13章由張立昂編寫.
　　在編寫過(guò)程中，作者參考了國(guó)內(nèi)外多種版本的《離散數(shù)學(xué)》教材和相關(guān)的文獻(xiàn)資料，從中吸取了許多好的思想，摘取了不少有用的素材，在此一并向有關(guān)作者致謝.感謝“21世紀(jì)大學(xué)本科計(jì)算機(jī)專業(yè)系列教材”編委會(huì)和清華大學(xué)出版社對(duì)本書出版的大力支持，特別要感謝李曉明教授，他在百忙之中認(rèn)真地審閱了全稿，并提出了寶貴的修改意見，使作者受益匪淺.我們更期待著廣大讀者，特別是用本書作教材的老師和學(xué)生，對(duì)本書的批評(píng)、指正、建議和評(píng)論.
　　作者
　　2005年2月于北京大學(xué)