譯者序

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

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

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

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

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


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