本書是經典的離散數學教材，為全球多所大學廣為采用。本書全面而系統地介紹了離散數學的理論和方法，內容涉及邏輯和證明，集合、函數、序列、求和與矩陣，計數，關系，圖，樹，布爾代數。全書取材廣泛，除包括定義、定理的嚴格陳述外，還配備大量的實例和圖表說明、各種練習和題目。第7版在前六版的基礎上做了大量的改進，使其成為更有效的教學工具。本書可作為高等院校數學、計算機科學和計算機工程等專業的教材或參考書。
Discrete Mathematics and Its Applications,7E本書是根據我多年講授離散數學的經驗和興趣寫成的。對學生而言，我的目的是為他們提供準確且可讀性很強的教材，清晰地介紹并展示離散數學中的概念和技術。我的目標是向愛懷疑的學生們展示離散數學的相關性和實用性，希望為學習計算機科學的學生提供一切必需的數學基礎，也希望學數學的學生理解重要的數學概念，以及為什么這些概念對應用來說很重要，最重要的是希望本書既能達到這些目標，又不含太多的水分。
對教師而言，我的目的是要利用數學中行之有效的教學技術來設計一個靈活而全面的教學工具，希望為教師提供能夠以最適合特定學生特點的方式高效地教授離散數學的教材。希望本書能夠達到這些目標。
我為本教材在過去所取得的巨大成功而感到非常欣慰。根據北美600多所學校以及全球各地許多大學成功采用了本書的大批師生的反饋和建議，此次第7版進行了許多改進。
本教材是為一至兩個學期的離散數學入門課程而設計的，適用于數學、計算機科學和工程等各類專業的學生。雖然唯一的先修課程要求是大學代數，但是要想真正學好離散數學還需要掌握更多的數學知識。
離散數學課程的目標離散數學課程有多個目標。學生不僅要學會一些特定的數學知識并知道怎樣應用，更重要的是，這樣一門課應培養學生的數學邏輯思維。為此，本教材特別強調數學推理以及用不同的方法解題。本書中五個重要主題交織在一起：數學推理、組合分析、離散結構、算法思維、應用與建模。成功的離散數學課程應該努力使這五個主題相互融合、平衡。
1.數學推理：學生必須理解數學推理，以便閱讀、領會并構造數學論證。本書以數理邏輯開篇，在后面證明方法的討論中，數理邏輯是基礎。本書描述了構造證明的方法與技巧。本書特別強調數學歸納法，不僅給出了這種證明的許多不同類型的實例，還詳細地解釋了數學歸納法為什么是有效的證明技術。
2.組合分析：一個重要的解題技巧就是計數或枚舉對象。本書中，對枚舉的討論從計數的基本技術著手，重點是用組合分析方法來解決計數問題并分析算法，而不是簡單地應用公式。
3.離散結構：離散數學課程應該教會學生如何處理離散結構，即表示離散對象以及對象之間關系的抽象數學結構。離散結構包括集合、置換、關系、圖、樹和有限狀態機等。
4.算法思維：有些問題可以通過詳細說明其算法來求解。在清楚地描述算法后，就可以構造一個計算機程序來實現它。這一過程中涉及的數學部分包括算法的詳細說明、正確性驗證以及執行算法所需要的計算機內存和時間的分析等，這些內容在本書中均有介紹。算法是用英語 譯著中采用漢語�！g者注和一種易于理解的偽代碼來描述的。
5.應用與建模：離散數學幾乎在每個可以想象到的研究領域中都有應用，本書介紹了其在計算機科學和數據網絡中的許多應用，還介紹了在其他各種領域中的應用，如化學、植物學、動物學、語言學、地理學、商業以及因特網等。這些均是離散數學的實際而又重要的應用，而不是編造的。用離散數學來建模是十分重要的問題求解技巧，本書中的一些練習讓學生有機會通過自己構造模型掌握這一技巧。
本書特色易理解性：本書對于初學者來說已被實踐證明是易讀易懂的。絕大部分內容不需要讀者具備比大學代數更多的數學預備知識。需要額外幫助的學生可以在配套網站找到相應工具將數學水平提升到本書的水準。本書中少數幾個需要參考微積分的地方也已顯式注明。大多數學生應該很容易理解書中用來表示算法的偽代碼，無論他們是否正式學過程序設計語言。本書不要求正規計算機科學方面的預備知識。
每章都是從易于理解和領會的水平開始。一旦詳細介紹了基本數學概念，就會給出稍難一些的內容以及在其他研究領域中的應用。
靈活性：本書為能靈活使用做了精心設計。各章對其前面內容的依賴程度都降到最低。每章分成長度大致相等的若干節，每節又根據內容劃分成若干小節以方便教學。教師可以根據這些分塊靈活地安排講課進度。
寫作風格：本書的寫作風格是直接而又實用的。使用準確的數學語言，但沒有采用過多的形式化與抽象。在數學命題中的記號和詞語表達之間做了精心的平衡。
數學嚴謹性和準確性：本書中所有定義和定理的陳述都十分仔細，這樣學生可以欣賞語言的準確性和數學所需的嚴謹性。證明則先是動機再緩慢展開，每一步都經過了詳細論證。證明中用到的公理及其所導出的基本性質在附錄中均有顯式描述，這呈現給學生一個清晰的概念，即在一個證明中他們能夠作何種假設。本書解釋并大量使用了遞歸定義。
實例：通過許多例子闡述概念、建立不同主題之間的關聯，并介紹應用。在大部分例子中，首先提出問題，然后再以適量的細節給出其解。
應用：本書中所含的應用展示了離散數學在解決現實世界中的問題時的實用性。本書包含的應用涉及廣泛的領域，包括計算機科學、數據網絡、心理學、化學、工程學、語言學、生物學、商業和因特網。
算法：離散數學的結論常常要用算法來表述，因此本書每章都介紹一些關鍵算法。這些算法采用文字敘述，同時也采用一種易于理解的結構化偽代碼來描述。簡要分析了書中所有算法的計算復雜性。
關鍵術語和結論：每章最后列出關鍵術語和結論。關鍵術語只列出學生必須掌握的那些，而非該章中定義的每個術語。
練習：書中包含很多練習題，涉及大量不同類型的問題。不僅提供了足夠多的簡單練習用于培養基本技能，還提供了大量的中等難度的練習和許多具有挑戰性的練習。練習的敘述清晰而無歧義，并按難易程度進行了分級。練習還包含一些特殊的討論來展開正文中沒有涉及的新概念，使得學生能夠通過自己的工作來發現新的想法。
那些比平均難度稍難的練習用單個星號*標記，而那些相當有挑戰性的練習則用兩個星號**標記。需要用微積分來求解的練習也明確指出。而那些其結果要在正文中用到的練習則會明確地用指向右側的手形符號來標識。本書最后給出了所有奇數編號練習的答案或解題綱要。解答通常包含那些大多數步驟寫得很清楚的證明。
復習題：每章最后都有一組復習題。設計這些問題是為了幫助學生重點學習該章最重要的概念和技術。要回答這些問題，學生必須寫出較長的答案，而不是僅做一些計算或一個簡答。
補充練習：每章后面都有一組豐富而多樣的補充練習。這些練習通常比每節后的練習難度更大些。補充練習強化該章中的概念，并把不同主題更有效地綜合起來。
計算機課題：每章后面還有一組計算機課題，這些計算機課題將學生在計算和離散數學中所學到的內容聯系起來。對于那些從數學角度或程序設計角度來看其難度超過平均水平的計算機課題用一個星號*標記，而那些非常具有挑戰性的則用兩個星號**標記。
計算和探索：每章的最后都有一組計算和探索性的問題。完成這些練習需要借助于現有的軟件工具，如學生或教師自己編寫的程序，或MapleTM或MathematicaTM這樣的數學計算軟件包。大部分這些練習為學生提供了通過計算來發現一些新事實或想法的機會（其中的一些練習在配套的在線練習冊《探索離散數學》中也有討論）。
寫作課題：每章后面都有一組寫作課題。要完成這類課題學生需要參考數學文獻。有些課題本質上是關于歷史的，需要學生查找原始資料。有些課題則是通往新內容和新思想的途徑。所有此類練習是要向學生展示正文中沒有深入探討的想法。這些課題把數學概念和寫作過程結合起來，以幫助學生面對未來可能的研究領域（在線版或印刷版的《學生解題指南》中可以找到為這些課題準備的參考文獻）。
推薦讀物：在附錄后還提供了一組針對全書及各章的推薦讀物。這些推薦讀物包括難度不超過本書的書籍、更難些的書籍、闡述性的文章，以及發表離散數學新發現的原始文章。其中一些是多年前出版的經典讀物，而另一些是在最近幾年內才出版的。
輔助資料《學生解題指南》：這本可以單獨購買的學生手冊包含了所有奇數編號練習的完整解答。這些解答解釋了為什么要用某種特定的方法以及為什么這個方法管用。對于有些練習，還給出了一兩種其他可能的解法以說明一個問題可以由多種不同方法來求解。本指南給出了為每章后面的寫作課題推薦的參考文獻，還包含撰寫證明指南、離散數學學習中學生常犯錯誤的一般性描述，以及為每章提供的考試樣例及解答以幫助學生準備考試。
�。↖SBN-10∶0-07-735350-1） �。↖SBN-13:978-0-07-735350-6）《教師資源手冊》：本手冊在網站上有提供，教師也可以申請印刷版的。手冊包含書中所有偶數編號練習的完整解答。給出了如何講授本書每章內容的建議，包括每節中應強調的重點以及如何組織內容。手冊還為每章提供了考試樣例以及一個可供選擇的包含1500多道考試題目的試題庫。對于所有考試樣例及試題庫中的題目都給出了解答。最后，還給出了針對不同的側重點以及學生能力水平的課程教學大綱樣本。
（ISBN-10∶0-07-735349-8） �。↖SBN-13:978-0-07-735349-0）致謝感謝各類學校中使用本書并向我提供有價值的反饋和有益的建議的許多教師和學生，他們的反饋才有可能使得本書更出色。特別感謝Jerrold Grossman、Jean-Claude Evard和Georgia Mederer，他們作為第7版的技術審閱，以其“鷹眼”般敏銳的目光確保了本書的準確性。我也很感激那些通過網站提交評論的人們所提供的幫助。
感謝第7版以及前六版的評閱人，這些評閱人給予我許多有益的批評和鼓勵，希望這一版不會辜負他們的期望。
第7版評閱人 Philip Barry 美國明尼蘇達大學明尼阿波里斯分校Miklos Bona 美國佛羅里達大學Kirby Brown 美國皇后學院John Carter 加拿大多倫多大學Narendra Chaudhari 新加坡南洋理工大學Allan Cochran 美國阿肯色大學Daniel Cunningham 美國布法羅州立學院George Davis 美國佐治亞州立大學Andrzej Derdzinski 美國俄亥俄州立大學Ronald Dotzel 美國密蘇里大學圣路易斯分校T.J.Duda 美國哥倫布州立社區學院Bruce Elenbogen 美國密歇根大學迪爾本分校Norma Elias 美國普渡大學卡魯梅分校（哈蒙德） Herbert Enderton 美國加州大學洛杉磯分校Anthony Evans 美國萊特州立大學Kim Factor 美國馬凱特大學Margaret
查看全部↓
Discrete Mathematics and Its Applications,7E
出版者的話
改編者序
譯者序
前言
配套網站
致學生
關于作者
符號表
第1章 基礎：邏輯和證明1
1.1 命題邏輯1
1.1.1 引言1
1.1.2 命題1
1.1.3 條件語句4
1.1.4 復合命題的真值表7
1.1.5 邏輯運算符的優先級7
1.1.6 邏輯運算和位運算7
練習8
1.2 命題邏輯的應用11
1.2.1 引言11
1.2.2 語句翻譯11
1.2.3 系統規范說明12
1.2.4 布爾搜索12
1.2.5 邏輯謎題13
1.2.6 邏輯電路14
練習15
1.3 命題等價式16
1.3.1 引言16
1.3.2 邏輯等價式17
1.3.3 德·摩根律的運用19
1.3.4 構造新的邏輯等價式19
1.3.5 命題的可滿足性20
1.3.6 可滿足性的應用20
1.3.7 可滿足性問題求解22
練習22
1.4 謂詞和量詞24
1.4.1 引言24
1.4.2 謂詞24
1.4.3 量詞25
1.4.4 約束論域的量詞28
1.4.5 量詞的優先級29
1.4.6 變量綁定29
1.4.7 涉及量詞的邏輯等價式29
1.4.8 量化表達式的否定30
1.4.9 語句到邏輯表達式的翻譯31
1.4.10 系統規范說明中量詞的使用32
1.4.11 選自路易斯·卡羅爾的例子33
1.4.12 邏輯程序設計33
練習34
1.5 嵌套量詞37
1.5.1 引言37
1.5.2 理解涉及嵌套量詞的語句37
1.5.3 量詞的順序38
1.5.4 數學語句到嵌套量詞語句的翻譯39
1.5.5 嵌套量詞到自然語言的翻譯40
1.5.6 漢語語句到邏輯表達式的翻譯40
1.5.7 嵌套量詞的否定41
練習42
1.6 推理規則45
1.6.1 引言45
1.6.2 命題邏輯的有效論證45
1.6.3 命題邏輯的推理規則46
1.6.4 使用推理規則建立論證48
1.6.5 消解律49
1.6.6 謬誤49
1.6.7 量化命題的推理規則50
1.6.8 命題和量化命題推理規則的組合使用51
練習52
1.7 證明導論53
1.7.1 引言53
1.7.2 一些專用術語53
1.7.3 理解定理是如何陳述的54
1.7.4 證明定理的方法54
1.7.5 直接證明法54
1.7.6 反證法55
1.7.7 歸謬證明法57
1.7.8 證明中的錯誤59
1.7.9 良好的開端60
練習60
1.8 證明的方法和策略61
1.8.1 引言61
1.8.2 窮舉證明法和分情形證明法61
1.8.3 存在性證明65
1.8.4 唯一性證明66
1.8.5 證明策略66
1.8.6 尋找反例68
1.8.7 證明策略實踐68
1.8.8 拼接68
1.8.9 開放問題的作用71
1.8.10 其他證明方法71
練習72
關鍵術語和結論73
復習題75
補充練習75
計算機課題78
計算和探索78
寫作課題78
第2章 基本結構：集合、函數、序列、求和與矩陣79
2.1 集合79
2.1.1 引言79
2.1.2 文氏圖81
2.1.3 子集81
2.1.4 集合的大小82
2.1.5 冪集83
2.1.6 笛卡兒積83
2.1.7 使用帶量詞的集合符號84
2.1.8 真值集和量詞84
練習85
2.2 集合運算86
2.2.1 引言86
2.2.2 集合恒等式88
2.2.3 擴展的并集和交集90
2.2.4 集合的計算機表示91
練習92
2.3 函數94
2.3.1 引言94
2.3.2 一對一函數和映上函數96
2.3.3 反函數和函數組合98
2.3.4 函數的圖100
2.3.5 一些重要的函數101
2.3.6 部分函數103
練習103
2.4 序列與求和106
2.4.1 引言106
2.4.2 序列106
2.4.3 遞推關系107
2.4.4 特殊的整數序列109
2.4.5 求和111
練習114
2.5 集合的基數116
2.5.1 引言116
2.5.2 可數集116
2.5.3 不可數集合118
練習120
2.6 矩陣121
2.6.1 引言121
2.6.2 矩陣算術122
2.6.3 矩陣的轉置和冪123
2.6.4 0-1矩陣124
練習125
關鍵術語和結論126
復習題128
補充練習129
計算機課題131
計算和探索131
寫作課題131
第3章 計數132
3.1 計數的基礎132
3.1.1 引言132
3.1.2 基本的計數原則132
3.1.3 比較復雜的計數問題136
3.1.4 減法法則（兩個集合的容斥原理）137
3.1.5 除法法則138
3.1.6 樹圖138
練習139
3.2 鴿巢原理141
3.2.1 引言141
3.2.2 廣義鴿巢原理142
3.2.3 鴿巢原理的幾個簡單應用144
練習145
3.3 排列與組合146
3.3.1 引言146
3.3.2 排列146
3.3.3 組合148
練習150
3.4 二項式系數和恒等式151
3.4.1 二項式定理151
3.4.2 帕斯卡恒等式和三角形153
3.4.3 其他的二項式系數恒等式154
練習155
3.5 排列與組合的推廣157
3.5.1 引言157
3.5.2 有重復的排列157
3.5.3 有重復的組合157
3.5.4 具有不可區別物體的集合的排列160
3.5.5 把物體放入盒子161
練習163
3.6 生成排列和組合165
3.6.1 引言165
3.6.2 生成排列165
3.6.3 生成組合166
練習167
關鍵術語和結論168
復習題169
補充練習170
計算機課題173
計算和探索173
寫作課題174
第4章 高級計數技術175
4.1 遞推關系的應用175
4.1.1 引言175
4.1.2 用遞推關系構造模型176
4.1.3 算法與遞推關系180
練習181
4.2 求解線性遞推關系184
4.2.1 引言184
4.2.2 求解常系數線性齊次遞推關系184
4.2.3 常系數線性非齊次的遞推關系188
練習190
4.3 分治算法和遞推關系191
4.3.1 引言191
4.3.2 分治遞推關系192
練習197
4.4 生成函數198
4.4.1 引言198
4.4.2 關于冪級數的有用事實198
4.4.3 計數問題與生成函數201
4.4.4 使用生成函數求解遞推關系204
4.4.5 使用生成函數證明恒等式205
練習206
4.5 容斥208
4.5.1 引言208
4.5.2 容斥原理208
練習211
4.6 容斥原理的應用212
4.6.1 引言212
4.6.2 容斥原理的另一種形式212
4.6.3 埃拉托色尼篩213
4.6.4 映上函數的個數213
4.6.5 錯位排列214
練習216
關鍵術語和結論216
復習題217
補充練習218
計算機課題221
計算和探索221
寫作課題221
第5章 關系223
5.1 關系及其性質223
5.1.1 引言223
5.1.2 函數作為關系224
5.1.3 集合的關系224
5.1.4 關系的性質225
5.1.5 關系的組合227
練習228
5.2 n元關系及其應用230
5.2.1 引言230
5.2.2 n元關系231
5.2.3 數據庫和關系231
5.2.4 n元關系的運算232
5.2.5 SQL234
練習235
5.3 關系的表示236
5.3.1 引言236
5.3.2 用矩陣表示關系236
5.3.3 用圖表示關系238
練習239
5.4 關系的閉包240
5.4.1 引言240
5.4.2 閉包241
5.4.3 有向圖中的路徑241
5.4.4 傳遞閉包242
5.4.5 沃舍爾算法245
練習247
5.5 等價關系247
5.5.1 引言247
5.5.2 等價關系248
5.5.3 等價類249
5.5.4 等價類與劃分250
練習253
5.6 偏序255
5.6.1 引言255
5.6.2 字典順序256
5.6.3 哈塞圖257
5.6.4 極大元與極小元259
5.6.5 格260
5.6.6 拓撲排序261
練習263
關鍵術語和結論265
復習題267
補充練習268
計算機課題271
計算和探索272
寫作課題272
第6章 圖273
6.1 圖和圖模型273
6.1.1 圖模型276
練習279
6.2 圖的術語和幾種特殊的圖281
6.2.1 引言281
6.2.2 基本術語281
6.2.3 一些特殊的簡單圖283
6.2.4 二分圖284
6.2.5 二分圖和匹配286
6.2.6 特殊類型圖的一些應用288
6.2.7 從舊圖構造新圖289
練習291
6.3 圖的表示和圖的同構293
6.3.1 引言293
6.3.2 圖的表示293
6.3.3 鄰接矩陣293
6.3.4 關聯矩陣295
6.3.5 圖的同構296
6.3.6 判定兩個簡單圖是否同構296
練習298
6.4 連通性301
6.4.1 引言301
6.4.2 通路301
6.4.3 無向圖的連通性303
6.4.4 圖是如何連通的304
6.4.5 有向圖的連通性306
6.4.6 通路與同構307
6.4.7 計算頂點之間的通路數308
練習308
6.5 歐拉通路與哈密頓通路311
6.5.1 引言311
6.5.2 歐拉通路與歐拉回路311
6.5.3 哈密頓通路與哈密頓回路315
6.5.4 哈密頓回路的應用316
練習318
6.6 最短通路問題320
6.6.1 引言320
6.6.2 最短通路算法322
6.6.3 旅行商問題325
練習326
6.7 平面圖328
6.7.1 引言328
6.7.2 歐拉公式329
6.7.3 庫拉圖斯基定理332
練習333
6.8 圖著色334
6.8.1 引言334
6.8.2 圖著色的應用337
練習338
關鍵術語和結論340
復習題343
補充練習344
計算機課題348
計算和探索349
寫作課題349
第7章 樹351
7.1 樹的概述351
7.1.1 有根樹352
7.1.2 樹作為模型355
7.1.3 樹的性質356
練習358
7.2 樹的應用360
7.2.1 引言360
7.2.2 二叉搜索樹360
7.2.3 決策樹362
7.2.4 前綴碼364
7.2.5 博弈樹365
練習369
7.3 樹的遍歷371
7.3.1 引言371
7.3.2 通用地址系統371
7.3.3 遍歷算法372
7.3.4 中綴、前綴和后綴記法377
練習379
7.4 生成樹380
7.4.1 引言380
7.4.2 深度優先搜索382
7.4.3 寬度優先搜索384
7.4.4 回溯的應用385
7.4.5 有向圖中的深度優先搜索387
練習388
7.5 最小生成樹390
7.5.1 引言390
查看全部↓
新書資訊