離散數學及其應用

引用

Rosen, K. H. (2025). Discrete Mathematics and Its Applications (2025 release). McGraw Hill.

章節概要

McGraw Hill 為2025年版列出了十三章和附錄；出版社提供的第七版目錄中也列有相同的十三個章節主題。公開的目錄只給出章節標題，因此下面的細節中，凡來自出版社的第八版（2019年）修訂說明或第七版（2012年）前言的，都會註明出處。

第1–2章：Foundations: Logic and Proofs（邏輯與證明基礎）；Basic Structures: Sets, Functions, Sequences, Sums, Matrices（基本結構：集合、函數、序列、求和、矩陣）

第1章以邏輯開篇，隨後討論證明方法。出版社的第八版修訂說明提到了邏輯謎題，以及一個把 n 皇后問題建模為可滿足性問題的例子。第2章彙集貫穿全書的基本結構：集合、函數、序列、求和與矩陣；同一份說明還記錄了多重集從習題移入正文的變化。

第3–4章：Algorithms（演算法）；Number Theory and Cryptography（數論與密碼學）

第3章討論演算法；根據第八版修訂說明，其中包括字串匹配問題及其暴力演算法。第4章涵蓋數論與密碼學；該說明提到擴展歐幾里得演算法、關於素數的最新發現與未解決的猜想，以及同態加密。

第5–6章：Induction and Recursion（歸納與遞歸）；Counting（計數）

第5章專門講歸納與遞歸；第八版的修訂包括擴充了數學歸納法證明的模板，並把它放在例題之前。第6章引入計數，同一份說明記錄了對除法原理講解的擴充。

第7–8章：Discrete Probability（離散機率）；Advanced Counting Techniques（高級計數技巧）

第7章涵蓋離散機率，第8章涵蓋超出基礎的計數技巧。公開的目錄對兩章都沒有更詳細的說明。

第9–11章：Relations（關係）；Graphs（圖）；Trees（樹）

第9章討論關係；第八版修訂說明指出，資料探勘中的關聯規則在 n 元關係一節中討論。第10章關於圖，據同一份說明，包含一個把人工智能中的語義網路建模為圖的新例子。第11章轉向樹。

第12–13章：Boolean Algebra（布爾代數）；Modeling Computation（計算建模）

最後兩章涵蓋布爾代數和計算的建模。第七版前言把這兩章都列為偏重電腦科學時的選學內容。

附錄

第七版前言描述了三個附錄：實數和正整數的公理、指數函數與對數函數，以及用來表達演算法的虛擬碼。第八版修訂說明補充道，有一章關於抽象代數（羣、環和域），作為單獨的線上資源提供，可以加入定製版教材。

核心概念

第1–6章：邏輯、結構、演算法、數論、計數

• 邏輯與證明：第1章標題中點出的基礎，前言稱之為後面討論證明方法的基石。
• 集合、函數、序列、求和與矩陣：第2章的基本結構。
• 演算法：第3章的主題；前言說，演算法用文字和虛擬碼描述，並在初等層面上分析其計算複雜度。
• 數論與密碼學：第4章的主題。
• 歸納與遞歸：第5章；前言強調了數學歸納法。

第7–13章：機率、關係、圖、樹與計算

• 離散機率與高級計數：第7–8章。
• 關係：第9章。
• 圖與樹：第10–11章。
• 布爾代數與計算建模：第12–13章。

評析

優點

• 一冊涵蓋廣泛。 目錄從邏輯與證明一直到圖、布爾代數和計算模型，出版社表示本書面向數學、電腦科學和工程專業的學生，因此一本書可以服務多種類型的課程。
• 明確的教學主題。 第七版前言列出貫穿全書的五條線索：數學推理、組合分析、離散結構、演算法思維，以及應用與建模。前言報告書中有800多個例題、4000多道按難度分級的習題（奇數題附有答案或解法提綱）、每章後的關鍵術語表和複習題，以及可選的電腦項目和寫作項目（均為該版的數字）。
• 為靈活的課程設計。 同一份前言說章節之間的依賴被降到最低，並提供了核心與選學小節的表格，因此一學期的二年級課程、兩學期的課程和偏電腦科學的課程可以各自選擇不同的部分。
• 前提條件明確。 前言稱唯一明確的先修要求是大學代數，涉及微積分的少數地方都有標註，所以沒有學過微積分也可以使用。

侷限

• 公開目錄中的細節很少。 出版社只展示了2025年版的章節標題，沒有列出相對第八版有哪些變化；在不同版本之間選擇時，應當比較實際的目錄。
• 證明是手段而非核心主題。 前言把數學推理作為五個主題之一。想要更系統地學習如何寫證明的學生，可能更適合以證明寫作為組織原則的教材，例如本課程書單中的 Epp 一書。
• 讀者羣體混合。 由於本書面向數學、電腦科學和工程專業的讀者，第七版的表格把演算法、布爾代數、計算建模等章在偏數學的課程中列為選學；而第5、6、9、10章包含對所有課程都屬核心的小節。

在課程中的定位

Rosen 是一本內容寬泛、帶有參考書性質的教材，一冊之中涵蓋證明方法、演算法、數論、計數、機率、圖和計算模型。Epp 的《Discrete Mathematics with Applications》涵蓋相近的內容，但以學習推理和證明寫作為組織主線，因此更適合在邏輯和證明寫作上需要更多幫助的學生。Oscar Levin 的《Discrete Mathematics: An Open Introduction》是一門圍繞計數、序列、圖論和邏輯、以探究為主的免費入門課程；László Lovász、József Pelikán 和 Katalin Vesztergombi 的《Discrete Mathematics: Elementary and Beyond》則是一本以問題為主線的簡短入門書。Graham、Knuth 和 Patashnik 的《Concrete Mathematics》以及 van Lint 和 Wilson 的《A Course in Combinatorics》應該在其後閱讀：前者講演算法分析中的求和、遞推式、二項式係數和生成函數，後者是研究生水平的組合數學教材。

如何使用本書

Rosen 適合修讀一到兩學期離散數學課程的電腦科學、數學和工程專業一、二年級學生；前言只要求大學代數。它最適合作為課程教材，課後繼續當作參考書使用。

實用的學習安排如下：

• 核心： 先學第1章和證明方法各節，再學第2章的基本結構、歸納與遞歸（第5章）、計數（第6章）和圖（第10章）。第七版的表格把第1、2、4、5、6、9、10章的大部分小節列為核心。
• 演算法與數論（第3–4章）： 第七版的表格把第3章列為偏電腦科學的選學內容，第4章只有開頭幾節屬於核心；電腦科學課程會希望完整學習這兩章。
• 機率、高級計數與關係（第7–9章）： 第七版的表格在每章中只把一到三節列為核心，因此短課程可以只學這些，兩學期課程則可學完其餘部分。
• 選學（第11–13章）： 第七版的表格只把樹這一章的開頭一節列為核心，第12–13章（布爾代數、計算建模）則為偏電腦科學的選學內容，因此適合有這類側重的課程。

請持續使用習題：據前言所述，奇數題附有答案或解法，章末的複習題要求用完整的文字回答，而不是做一個簡短的計算。