譯者序

　　離散數(shù)學(xué)以研究離散量的結(jié)構(gòu)和相互間的關(guān)系為主要目標(biāo)， 包括數(shù)理邏輯、集合論、數(shù)論、圖論、組合學(xué)和計(jì)算幾何等，是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門重要基礎(chǔ)課。
　　本書的第一版出版于上個(gè)世紀(jì)80年代，那時(shí)許多大學(xué)需要一門涉及組合數(shù)學(xué)、算法和圖論等內(nèi)容的課程來拓寬學(xué)生的數(shù)學(xué)知識(shí)和處理抽象概念的能力。該書的出版滿足了這種需求，并對(duì)以后離散數(shù)學(xué)課程的發(fā)展產(chǎn)生了深遠(yuǎn)的影響。本版本的離散數(shù)學(xué)教材，不僅包括了算法、組合數(shù)學(xué)、集合、函數(shù)、數(shù)學(xué)歸納法等內(nèi)容，同時(shí)還涉及證明的理解和構(gòu)造技術(shù)，通過學(xué)習(xí)，學(xué)生可提高數(shù)學(xué)涵養(yǎng)，能更好理解后序課程的內(nèi)容。
　　自本書第4版引進(jìn)國內(nèi)，本書譯者就一直使用該教材于離散數(shù)學(xué)課程的教學(xué)。從內(nèi)容上看，這是一本深入淺出的好教材，不要求學(xué)生具備任何預(yù)備知識(shí)，可廣泛應(yīng)用于普通高 譯者序

　　離散數(shù)學(xué)以研究離散量的結(jié)構(gòu)和相互間的關(guān)系為主要目標(biāo)， 包括數(shù)理邏輯、集合論、數(shù)論、圖論、組合學(xué)和計(jì)算幾何等，是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門重要基礎(chǔ)課。
　　本書的第一版出版于上個(gè)世紀(jì)80年代，那時(shí)許多大學(xué)需要一門涉及組合數(shù)學(xué)、算法和圖論等內(nèi)容的課程來拓寬學(xué)生的數(shù)學(xué)知識(shí)和處理抽象概念的能力。該書的出版滿足了這種需求，并對(duì)以后離散數(shù)學(xué)課程的發(fā)展產(chǎn)生了深遠(yuǎn)的影響。本版本的離散數(shù)學(xué)教材，不僅包括了算法、組合數(shù)學(xué)、集合、函數(shù)、數(shù)學(xué)歸納法等內(nèi)容，同時(shí)還涉及證明的理解和構(gòu)造技術(shù)，通過學(xué)習(xí)，學(xué)生可提高數(shù)學(xué)涵養(yǎng)，能更好理解后序課程的內(nèi)容。
　　自本書第4版引進(jìn)國內(nèi)，本書譯者就一直使用該教材于離散數(shù)學(xué)課程的教學(xué)。從內(nèi)容上看，這是一本深入淺出的好教材，不要求學(xué)生具備任何預(yù)備知識(shí)，可廣泛應(yīng)用于普通高等院校、成人教育、遠(yuǎn)程教育和高等�？茖W(xué)校計(jì)算機(jī)相關(guān)專業(yè)的離散數(shù)學(xué)教學(xué)�？梢哉f這是國內(nèi)目前可見的最明了、簡單的離散數(shù)學(xué)教材，可適用于任何層次的學(xué)生以不同的途徑學(xué)習(xí)，包括自學(xué)和網(wǎng)絡(luò)教學(xué)。
　　本書由上海交通大學(xué)計(jì)算機(jī)系的黃林鵬教授、陳俊清博士和王欣博士共同翻譯，由黃林鵬審校。此外還要感謝彭沖、王德俊、徐小輝、伍建焜、張迎春、馮志宇、楊歡和林海源等的幫助。
　　這里還要提一下我的研究生導(dǎo)師左孝凌教授，他在上個(gè)世紀(jì)80年代撰寫的離散數(shù)學(xué)教材曾再版30余次，影響了幾代學(xué)子。譯者在1986至1988年間作為他的研究生，在他指導(dǎo)下開始學(xué)習(xí)離散數(shù)學(xué)知識(shí)，再此飲水思源，并表示感謝。
　　由于譯者水平所限，錯(cuò)誤難免，譯文不當(dāng)不周之處難免，敬請讀者將意見寄到lphuang@sjtu.edu.cn，不勝感激。

　　這本新版的離散數(shù)學(xué)書籍，是基于作者多年來的教學(xué)經(jīng)驗(yàn)并根據(jù)讀者意見修改而成，可作為一個(gè)或兩個(gè)學(xué)期的離散數(shù)學(xué)課程的教材，本書不需要作者先期掌握形式化方法，也不需要具備微積分的知識(shí)，當(dāng)然更不需要計(jì)算機(jī)科學(xué)的前期知識(shí)。本書包括例題、練習(xí)、圖表、問題求解要點(diǎn)，每個(gè)章節(jié)還包括復(fù)習(xí)、注釋、自測題和上機(jī)練習(xí)等，這些豐富的材料可幫助讀者快速掌握離散數(shù)學(xué)的基本知識(shí)。與本書配套的材料還包括教學(xué)參考書和Web站點(diǎn)。
在20世紀(jì)80年代初期，幾乎沒有離散數(shù)學(xué)入門課程的合適教材。但那時(shí)許多大學(xué)需要一門涉及組合數(shù)學(xué)、算法和圖論等內(nèi)容的課程來拓寬學(xué)生的數(shù)學(xué)知識(shí)和處理抽象概念的能力。本書第一版（1984）的出版滿足了這種需求，并對(duì)離散數(shù)學(xué)課程的發(fā)展產(chǎn)生了深遠(yuǎn)的影響。此后，離散數(shù)學(xué)課程得到了包括數(shù)學(xué)和計(jì)算機(jī)等專業(yè)的許多學(xué)科的認(rèn)可。美國數(shù)學(xué)學(xué)會(huì)（MAA）的一個(gè)專門小組曾提議離散數(shù)學(xué)應(yīng)作為一學(xué)年的課程講授。電氣和電子工程師協(xié)會(huì)（IEEE）的教育委員會(huì)也建議在大學(xué)一年級(jí)開設(shè)離散數(shù)學(xué)課程。隨后，美國計(jì)算機(jī)學(xué)會(huì)（ACM）和IEEE給出了離散數(shù)學(xué)課程的推薦性大綱。本版和前面各版一樣，不僅包括了算法、組合數(shù)學(xué)、集合、函數(shù)、數(shù)學(xué)歸納法等被這些組織所認(rèn)可的內(nèi)容，同時(shí)還涉及證明的理解和構(gòu)造技術(shù)，學(xué)生通過學(xué)習(xí)可提高數(shù)學(xué)上的涵養(yǎng)。

邏輯和證明發(fā)方面的修改
　　本書第7版的修改來自于許多讀者對(duì)本書先前版本的意見和要求。對(duì)第6版的最大修改是第1章到第3章。本書第6版的第1章，邏輯和證明，在第7版中被分為兩章，集合與邏輯（第1章）和證明（第2章）。除了集合一節(jié)，第6版中的第2章（數(shù)學(xué)的語言）和第3章（關(guān)系）被合并為第7版中的第3章（函數(shù)、序列和關(guān)系）。從本書預(yù)印版已經(jīng)看出讀者對(duì)于這些修改的熱切期望。
　　集合一節(jié)現(xiàn)在是本書的第一節(jié)。這種改變使本書可以自始至終使用與集合相關(guān)的術(shù)語�，F(xiàn)在可以在例子和練習(xí)的證明中使用集合的概念，由此可以給出比先前版本更有意思的例子。甚至可以在完整討論證明和證明技術(shù)之前就可以使用集合來引入證明的概念（例如，證明兩個(gè)集合是相等的，證明一個(gè)集合是另一個(gè)集合的子集）。
　　對(duì)于證明構(gòu)造技術(shù)的內(nèi)容也大大拓廣了。2.1和2.2節(jié)是和數(shù)學(xué)系統(tǒng)、證明技術(shù)相關(guān)的新章節(jié)。除此之外，還有關(guān)于等價(jià)性證明和存在性證明（包括構(gòu)造和非構(gòu)造存在性證明）的擴(kuò)展內(nèi)容。幾乎每一個(gè)證明都有前導(dǎo)性的討論章節(jié)和/或伴隨的圖解。問題求解部分包括了如何進(jìn)行證明，如何書寫證明以及證明中常見的錯(cuò)誤等額外的建議和例子。有兩個(gè)新的問題求解段落，一是關(guān)于量詞的，另一個(gè)與證明有關(guān)（參見證明實(shí)數(shù)的若干性質(zhì)）。
　　關(guān)于證明的論據(jù)和規(guī)則的討論則被移到關(guān)于命題的討論之后。與量詞有關(guān)的推理規(guī)則被整合進(jìn)量詞一節(jié)。
　　例子和習(xí)題的數(shù)量也有了大量的提升。在第6版，前3章大約有1370個(gè)例子和習(xí)題。而在第7版，前3章大約有1640個(gè)例子和習(xí)題。當(dāng)然，不僅數(shù)量增加了，質(zhì)量也得到了提高。對(duì)于第6版中的大部分例子，第7版都進(jìn)行了討論并增加了分析。

對(duì)第6版所進(jìn)行的其他修改
對(duì)第6版所進(jìn)行的其他修改如下：
* 在本書前頭就引入了整數(shù)（Z，Z#+，Z#-，Z＃nonneg）、有理數(shù)（用Q代替Z）、實(shí)數(shù)（用R代替Z）的概念描述和記法（見1.1節(jié)，集合）。
* 給出定理5.1.17和定理5.1.22的證明，本書第6版只是給出證明概要，這兩個(gè)定理描述了從給定的兩個(gè)整數(shù)的素因子表示法中得出最大公因子和最小公倍數(shù)的過程。
* 給出計(jì)算兩個(gè)整數(shù)a和b的最大公因子的遞歸算法gcd(a,b)，以及如何計(jì)算滿足gcd(a,b)=sa+tb的整數(shù)s和t的算法。
* 6.1節(jié)增加了包含排斥原理。
* 6.1節(jié)增加了幾個(gè)實(shí)例以說明乘法原理和加法原理的應(yīng)用。這些例子所處的位置在讀者了解該使用何種原理或混合使用兩種原理之前。
* 和廣義排列組合有關(guān)的章節(jié)（第6版中的6.6節(jié)）現(xiàn)在放在6.1節(jié)和6.2節(jié)之后（基本原理、排列和組合），因?yàn)閺V義排列組合的概念和6.1節(jié)、6.2節(jié)中的材料較為相近。
* 在介紹鴿巢（6.9節(jié)）之前給出了一些簡單、直接的“熱身”練習(xí)。
* 加入更多的（8.6節(jié)）圖同構(gòu)的練習(xí)，練習(xí)分為3類，一類要求給出兩個(gè)給定的圖是同構(gòu)的證明，另一類要求給出兩個(gè)給定的圖不是同構(gòu)的說明，還有一類是要求讀者確定是否兩個(gè)給定的圖是同構(gòu)的并給出證明。
* 9.3節(jié)新增了一些使用回溯法的練習(xí)，包括流行的數(shù)獨(dú)智力游戲。
* 給出更多的例子和練習(xí)以提示常見的錯(cuò)誤（例如，在2.1節(jié)復(fù)習(xí)和練習(xí)前的“常見錯(cuò)誤”部分就給出了一些證明中常見的錯(cuò)誤，例6.2.24也說明了一個(gè)常見的計(jì)數(shù)錯(cuò)誤）。
* 在參考文獻(xiàn)中加入了近期的一些書籍和文章。一些參考書籍被更新為最新的版本。
* 例子的數(shù)量增加到650（第6版大概有600個(gè)例子）。
* 練習(xí)的數(shù)量增加到4200左右（第6版大概有4000個(gè)例子）。


內(nèi)容和結(jié)構(gòu)
本書內(nèi)容包括
* 集合和邏輯（包括量詞）。實(shí)例包括Google搜索引擎的使用（例 1.2.13）等。本書使用程序邏輯來討論自然語言到符號(hào)表達(dá)式的翻譯。例1.6.15討論了邏輯游戲，該游戲給出了一種確定量化命題函數(shù)的值是否為真的方法。
* 討論了證明技術(shù)（第2章），包括直接證明、反例、反證法、逆否證明法、分情況證明法、（構(gòu)造和非構(gòu)造）存在性證明和數(shù)學(xué)歸納法。使用循環(huán)不變式做為數(shù)學(xué)歸納法的應(yīng)用例子之一。包括了一節(jié)可選的，簡短的對(duì)歸結(jié)證明方法（自動(dòng)證明技術(shù)的基礎(chǔ)）的討論。
* 函數(shù)、序列、和與積的記法、串和關(guān)系（第3章），包括新的13位國際標(biāo)準(zhǔn)書號(hào)（ISBN）的構(gòu)造、Hash函數(shù)和偽隨機(jī)數(shù)發(fā)生器（3.1節(jié)）的介紹、偏序關(guān)系在任務(wù)調(diào)度中的應(yīng)用（3.3節(jié)）和關(guān)系數(shù)據(jù)庫（3.6節(jié)）等。
* 詳細(xì)討論了算法、遞歸算法和算法分析技術(shù)（第4章）。在說明“大O”和相關(guān)記法之前列舉了若干例子（4.1節(jié)和4.2節(jié)），對(duì)引入該記法的動(dòng)機(jī)進(jìn)行了簡要的介紹。算法的使用將貫穿全書。本書將提到許多現(xiàn)代算法可能沒有傳統(tǒng)算法的許多特征（如許多現(xiàn)代算法不是通用、確定的、甚至有的不是有限的）。為了說明這點(diǎn)，本章給出了一個(gè)隨機(jī)算法作為例子（例4.2.4）。算法以偽代碼的靈活形式書寫，其和目前流行的程序設(shè)計(jì)語言如C、C＋＋和Java相似（本書不要求讀者預(yù)先具有計(jì)算機(jī)科學(xué)的知識(shí)，所使用的偽代碼的描述在附錄C中給出）。本身介紹的算法包括覆蓋算法（4.4節(jié)）、計(jì)算最大公約數(shù)的歐幾里德算法（5.3節(jié)）、RSA公共密鑰算法（5.4節(jié)）、排列組合生成算法（6.4節(jié)）、歸并排序算法（7.3節(jié)）、Dijkstra最短路徑算法（8.4節(jié)）、回溯算法（9.3節(jié)）、深度優(yōu)先和廣度優(yōu)先算法（9.3節(jié)）、樹的遍歷算法（9.6節(jié)）、博弈樹求值算法（9.9節(jié)）、網(wǎng)絡(luò)最大流量算法（10.2節(jié)）、尋找最小距點(diǎn)對(duì)算法（13.1節(jié)）和凸包計(jì)算算法（13.2節(jié)）等。
* 關(guān)于函數(shù)增長的“大O”、Ω、Θ記法的討論（4.3節(jié)）。使用這些記法可以準(zhǔn)確地描述函數(shù)的增長以及算法的時(shí)間和空間復(fù)雜度問題。
* 數(shù)論的介紹（第5章）。包括一些傳統(tǒng)的結(jié)論（如整除性、素?cái)?shù)個(gè)數(shù)是無限的、基本的算術(shù)定理）和數(shù)論算法（如尋找最大公約數(shù)的歐幾里德算法、基于重復(fù)平方法計(jì)算數(shù)的指數(shù)的算法，計(jì)算滿足gcd(a,b)=sa+tb的整數(shù)s和t的算法，計(jì)算一個(gè)整數(shù)針對(duì)某個(gè)模的逆的算法等。本章介紹的方法可應(yīng)用于RSA公共密鑰算法（5.4節(jié)）中涉及的計(jì)算。
* 排列、組合、離散概率和鴿巢原理（第6章）�？蛇x章節(jié)（6.4節(jié)和6.5節(jié)）介紹了離散概率。
* 遞推關(guān)系及其在算法分析中的應(yīng)用（第7章）。
* 圖，包括并行計(jì)算機(jī)體系結(jié)構(gòu)的圖型表示和映射、騎士旅行、Hamilton回路、圖的同構(gòu)、平面圖（第8章）等。定理8.4.3給出了Dijkstra算法正確性的簡短優(yōu)美的證明。
* 樹，包括二叉樹、樹的遍歷、最小生成樹、決策樹、排序的時(shí)間下界、樹的同構(gòu)（第9章）等。
* 網(wǎng)絡(luò)最大流量算法和匹配問題（第10章）。
* Boole代數(shù)，重點(diǎn)是Boole代數(shù)與組合電路的關(guān)系（第11章）。
* 介紹了基于有限自動(dòng)機(jī)的建模技術(shù)和應(yīng)用（第12章）。例12.1.11討論了SR觸發(fā)電路。例12.3.19以von Koch雪花為例，給出了分形的語法描述。
* 第13章介紹