離散數學及其應用（原書第7版 本科教學版） pdf epub mobi txt 電子書 下載 2025

簡體網頁||繁體網頁

☆☆☆☆☆

[美] 肯尼思 H.羅森 著，徐六通 譯

齣版社： 機械工業齣版社

ISBN：9787111555391

版次：1

商品編碼：12035931

品牌：機工齣版

包裝：平裝

叢書名： 計算機科學叢書

開本：16開

齣版時間：2017-01-01

用紙：膠版紙

頁數：435

內容簡介

　　本書是經典的離散數學教材，為全球多所大學廣為采用。本書全麵而係統地介紹瞭離散數學的理論和方法，內容涉及邏輯和證明，集閤、函數、序列、求和與矩陣，計數，關係，圖，樹，布爾代數。全書取材廣泛，除包括定義、定理的嚴格陳述外，還配備大量的實例和圖錶說明、各種練習和題目。第7版在前六版的基礎上做瞭大量的改進，使其成為更有效的教學工具。本書可作為高等院校數學、計算機科學和計算機工程等專業的教材或參考書。

目錄

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

前言/序言

　　Discrete Mathematics and Its Applications,7E本書是根據我多年講授離散數學的經驗和興趣寫成的。對學生而言，我的目的是為他們提供準確且可讀性很強的教材，清晰地介紹並展示離散數學中的概念和技術。我的目標是嚮愛懷疑的學生們展示離散數學的相關性和實用性，希望為學習計算機科學的學生提供一切必需的數學基礎，也希望學數學的學生理解重要的數學概念，以及為什麼這些概念對應用來說很重要，最重要的是希望本書既能達到這些目標，又不含太多的水分。
　　對教師而言，我的目的是要利用數學中行之有效的教學技術來設計一個靈活而全麵的教學工具，希望為教師提供能夠以最適閤特定學生特點的方式高效地教授離散數學的教材。希望本書能夠達到這些目標。
　　我為本教材在過去所取得的巨大成功而感到非常欣慰。根據北美600多所學校以及全球各地許多大學成功采用瞭本書的大批師生的反饋和建議，此次第7版進行瞭許多改進。
　　本教材是為一至兩個學期的離散數學入門課程而設計的，適用於數學、計算機科學和工程等各類專業的學生。雖然唯一的先修課程要求是大學代數，但是要想真正學好離散數學還需要掌握更多的數學知識。
　　離散數學課程的目標離散數學課程有多個目標。學生不僅要學會一些特定的數學知識並知道怎樣應用，更重要的是，這樣一門課應培養學生的數學邏輯思維。為此，本教材特彆強調數學推理以及用不同的方法解題。本書中五個重要主題交織在一起：數學推理、組閤分析、離散結構、算法思維、應用與建模。成功的離散數學課程應該努力使這五個主題相互融閤、平衡。
　　1.數學推理：學生必須理解數學推理，以便閱讀、領會並構造數學論證。本書以數理邏輯開篇，在後麵證明方法的討論中，數理邏輯是基礎。本書描述瞭構造證明的方法與技巧。本書特彆強調數學歸納法，不僅給齣瞭這種證明的許多不同類型的實例，還詳細地解釋瞭數學歸納法為什麼是有效的證明技術。
　　2.組閤分析：一個重要的解題技巧就是計數或枚舉對象。本書中，對枚舉的討論從計數的基本技術著手，重點是用組閤分析方法來解決計數問題並分析算法，而不是簡單地應用公式。
　　3.離散結構：離散數學課程應該教會學生如何處理離散結構，即錶示離散對象以及對象之間關係的抽象數學結構。離散結構包括集閤、置換、關係、圖、樹和有限狀態機等。
　　4.算法思維：有些問題可以通過詳細說明其算法來求解。在清楚地描述算法後，就可以構造一個計算機程序來實現它。這一過程中涉及的數學部分包括算法的詳細說明、正確性驗證以及執行算法所需要的計算機內存和時間的分析等，這些內容在本書中均有介紹。算法是用英語�　∫脛�中采用漢語。——譯者注�『鴕恢忠子誒斫獾奈貝�碼來描述的。
　　5.應用與建模：離散數學幾乎在每個可以想象到的研究領域中都有應用，本書介紹瞭其在計算機科學和數據網絡中的許多應用，還介紹瞭在其他各種領域中的應用，如化學、植物學、動物學、語言學、地理學、商業以及因特網等。這些均是離散數學的實際而又重要的應用，而不是編造的。用離散數學來建模是十分重要的問題求解技巧，本書中的一些練習讓學生有機會通過自己構造模型掌握這一技巧。
　　本書特色易理解性：本書對於初學者來說已被實踐證明是易讀易懂的。絕大部分內容不需要讀者具備比大學代數更多的數學預備知識。需要額外幫助的學生可以在配套網站找到相應工具將數學水平提升到本書的水準。本書中少數幾個需要參考微積分的地方也已顯式注明。大多數學生應該很容易理解書中用來錶示算法的僞代碼，無論他們是否正式學過程序設計語言。本書不要求正規計算機科學方麵的預備知識。
　　每章都是從易於理解和領會的水平開始。一旦詳細介紹瞭基本數學概念，就會給齣稍難一些的內容以及在其他研究領域中的應用。
　　靈活性：本書為能靈活使用做瞭精心設計。各章對其前麵內容的依賴程度都降到最低。每章分成長度大緻相等的若乾節，每節又根據內容劃分成若乾小節以方便教學。教師可以根據這些分塊靈活地安排講課進度。
　　寫作風格：本書的寫作風格是直接而又實用的。使用準確的數學語言，但沒有采用過多的形式化與抽象。在數學命題中的記號和詞語錶達之間做瞭精心的平衡。
　　數學嚴謹性和準確性：本書中所有定義和定理的陳述都十分仔細，這樣學生可以欣賞語言的準確性和數學所需的嚴謹性。證明則先是動機再緩慢展開，每一步都經過瞭詳細論證。證明中用到的公理及其所導齣的基本性質在附錄中均有顯式描述，這呈現給學生一個清晰的概念，即在一個證明中他們能夠作何種假設。本書解釋並大量使用瞭遞歸定義。
　　實例：通過許多例子闡述概念、建立不同主題之間的關聯，並介紹應用。在大部分例子中，首先提齣問題，然後再以適量的細節給齣其解。
　　應用：本書中所含的應用展示瞭離散數學在解決現實世界中的問題時的實用性。本書包含的應用涉及廣泛的領域，包括計算機科學、數據網絡、心理學、化學、工程學、語言學、生物學、商業和因特網。
　　算法：離散數學的結論常常要用算法來錶述，因此本書每章都介紹一些關鍵算法。這些算法采用文字敘述，同時也采用一種易於理解的結構化僞代碼來描述。簡要分析瞭書中所有算法的計算復雜性。
　　關鍵術語和結論：每章最後列齣關鍵術語和結論。關鍵術語隻列齣學生必須掌握的那些，而非該章中定義的每個術語。
　　練習：書中包含很多練習題，涉及大量不同類型的問題。不僅提供瞭足夠多的簡單練習用於培養基本技能，還提供瞭大量的中等難度的練習和許多具有挑戰性的練習。練習的敘述清晰而無歧義，並按難易程度進行瞭分級。練習還包含一些特殊的討論來展開正文中沒有涉及的新概念，使得學生能夠通過自己的工作來發現新的想法。
　　那些比平均難度稍難的練習用單個星號*標記，而那些相當有挑戰性的練習則用兩個星號**標記。需要用微積分來求解的練習也明確指齣。而那些其結果要在正文中用到的練習則會明確地用指嚮右側的手形符號來標識。本書最後給齣瞭所有奇數編號練習的答案或解題綱要。解答通常包含那些大多數步驟寫得很清楚的證明。
　　復習題：每章最後都有一組復習題。設計這些問題是為瞭幫助學生重點學習該章最重要的概念和技術。要迴答這些問題，學生必須寫齣較長的答案，而不是僅做一些計算或一個簡答。
　　補充練習：每章後麵都有一組豐富而多樣的補充練習。這些練習通常比每節後的練習難度更大些。補充練習強化該章中的概念，並把不同主題更有效地綜閤起來。
　　計算機課題：每章後麵還有一組計算機課題，這些計算機課題將學生在計算和離散數學中所學到的內容聯係起來。對於那些從數學角度或程序設計角度來看其難度超過平均水平的計算機課題用一個星號*標記，而那些非常具有挑戰性的則用兩個星號**標記。
　　計算和探索：每章的最後都有一組計算和探索性的問題。完成這些練習需要藉助於現有的軟件工具，如學生或教師自己編寫的程序，或MapleTM或MathematicaTM這樣的數學計算軟件包。大部分這些練習為學生提供瞭通過計算來發現一些新事實或想法的機會（其中的一些練習在配套的在綫練習冊《探索離散數學》中也有討論）。
　　寫作課題：每章後麵都有一組寫作課題。要完成這類課題學生需要參考數學文獻。有些課題本質上是關於曆史的，需要學生查找原始資料。有些課題則是通往新內容和新思想的途徑。所有此類練習是要嚮學生展示正文中沒有深入探討的想法。這些課題把數學概念和寫作過程結閤起來，以幫助學生麵對未來可能的研究領域（在綫版或印刷版的《學生解題指南》中可以找到為這些課題準備的參考文獻）。
　　推薦讀物：在附錄後還提供瞭一組針對全書及各章的推薦讀物。這些推薦讀物包括難度不超過本書的書籍、更難些的書籍、闡述性的文章，以及發錶離散數學新發現的原始文章。其中一些是多年前齣版的經典讀物，而另一些是在最近幾年內纔齣版的。
　　輔助資料《學生解題指南》：這本可以單獨購買的學生手冊包含瞭所有奇數編號練習的完整解答。這些解答解釋瞭為什麼要用某種特定的方法以及為什麼這個方法管用。對於有些練習，還給齣瞭一兩種其他可能的解法以說明一個問題可以由多種不同方法來求解。本指南給齣瞭為每章後麵的寫作課題推薦的參考文獻，還包含撰寫證明指南、離散數學學習中學生常犯錯誤的一般性描述，以及為每章提供的考試樣例及解答以幫助學生準備考試。
　　（ISBN-10∶0-07-735350-1）　　　　（ISBN-13:978-0-07-735350-6）《教師資源手冊》：本手冊在網站上有提供，教師也可以申請印刷版的。手冊包含書中所有偶數編號練習的完整解答。給齣瞭如何講授本書每章內容的建議，包括每節中應強調的重點以及如何組織內容。手冊還為每章提供瞭考試樣例以及一個可供選擇的包含1500多道考試題目的試題庫。對於所有考試樣例及試題庫中的題目都給齣瞭解答。最後，還給齣瞭針對不同的側重點以及學生能力水平的課程教學大綱樣本。
　　（ISBN-10∶0-07-735349-8）　　　　（ISBN-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

評分☆☆☆☆☆

看起來不錯，很厚，任務重瞭，要學透那麼厚的書不容易呀

評分☆☆☆☆☆

如果猴子會飛，那麼我能找到女朋友。。

評分☆☆☆☆☆

買給入門計算機的人看的，離散數學是計算機的基礎知識，這本書應該不錯

評分☆☆☆☆☆

超級贊啊，兄 dei，簡直nice

評分☆☆☆☆☆

東西是全新的，不過我還沒看完，看瞭一部分，覺得挺好的，就先評價瞭，如果有不好的地方我會來追評

評分☆☆☆☆☆

Very Good

評分☆☆☆☆☆

用來學離散數學非常好的教科書。

評分☆☆☆☆☆

好書，描述清晰，證明推理詳實。一本好的教材。

評分☆☆☆☆☆

內容完全正版，馬上要去享受我的離散瞭?