01 / 導讀
導讀
引用
Epp, S. S. (2020). Discrete Mathematics with Applications (5th ed.). Cengage Learning.
章節概要
全書共十二章，另有附錄；Cengage 對學生解答手冊的介紹中提到，部分習題的答案在附錄B中。前四章建立語言、邏輯和證明技巧；第5–8章討論歸納法、集合、函數和關係；第9–12章討論計數與機率、圖與樹、演算法效率和自動機。Cengage 對第五版的介紹說，字串和圖在第1章引入，並在全書中結合應用展開，握手定理從第12章移到了第4章。
第1章：Speaking Mathematically（用數學的語言表達）
開篇一章透過四節教授後面各章使用的詞彙：變數、集合的語言、關係與函數的語言、圖的語言。
第2–3章：The Logic of Compound Statements（複合命題的邏輯）；The Logic of Quantified Statements（量化命題的邏輯）
第2章涵蓋邏輯形式與邏輯等價、條件命題、有效與無效論證，並以兩個應用結尾：數字邏輯電路，以及數制與加法電路。第3章對量詞重複這一結構：謂詞與量化命題（兩節）、帶多個量詞的命題，以及含量化命題的論證。
第4章：Elementary Number Theory and Methods of Proof（初等數論與證明方法）
這一章是本書講授證明的核心。關於直接證明與反例的六節，依次介紹引言、寫作建議、有理數、整除性、分情形討論與帶餘除法定理，以及取整函數（下取整與上取整）。關於間接論證的兩節講反證法與逆否命題，以及兩個著名的定理；本章最後是應用：握手定理和演算法。
第5章：Sequences, Mathematical Induction, and Recursion（序列、數學歸納法與遞歸）
第5章從序列開始，隨後依次是用歸納法證明公式、歸納法的應用，以及強歸納法與良序原理，接着是演算法的正確性。後半部分轉向遞歸：序列的遞歸定義、用疊代法解遞推關係、常係數二階線性齊次遞推關係，以及一般遞歸定義與結構歸納法。
第6–8章：Set Theory（集合論）；Properties of Functions（函數的性質）；Properties of Relations（關係的性質）
第6章涵蓋證明的元素法、集合的性質、反證與代數證明，最後一節講布爾代數、羅素悖論和停機問題。第7章研究一般集合上的函數、單射、滿射與反函數、複合，以及帶有可計算性應用的基數。第8章處理集合上的關係、自反性、對稱性與傳遞性、等價關係、帶有密碼學應用的模算術，以及偏序關係。
第9章：Counting and Probability（計數與機率）
第9章從引言出發，依次講到可能性樹與乘法法則、加法法則、鴿籠原理、組合、允許重複的 r 組合、巴斯卡公式與二項式定理、機率公理與期望值，以及條件機率、貝氏公式與獨立事件。
第10–12章：Theory of Graphs and Trees（圖與樹的理論）；Analysis of Algorithm Efficiency（演算法效率分析）；Regular Expressions and Finite-State Automata（正則表達式與有限狀態自動機）
第10章涵蓋跡、路徑與迴路，圖的矩陣表示，同構，樹與有根樹，以及包含最短路徑演算法的生成樹。第11章介紹實變數實值函數及其圖像、O、Ω 和 Θ 記號、指數函數與對數函數，以及兩個分析演算法效率的應用。第12章涵蓋形式語言與正則表達式、有限狀態自動機，以及有限狀態自動機的化簡。
核心概念
第1–4章：語言、邏輯與證明
- 邏輯形式與邏輯等價：第2章分析複合命題的基礎。
- 量化命題：第3章對謂詞、多個量詞和含量詞的論證的處理。
- 直接證明、反例與間接論證：第4章藉助數論教授的證明方法。
- 帶餘除法定理：4.5節引入的除法結果。
第5–8章：歸納法、集合、函數、關係
- 數學歸納法與強歸納法：5.2–5.4節的證明技巧，5.9節還有結構歸納法。
- 遞推關係：用疊代法求解（5.7），二階線性齊次情形則用一般方法求解（5.8）。
- 證明的元素法：第6章中證明集合性質的方式。
- 等價關係與偏序：第8章的關係類型。
第9–12章：計數、圖、演算法與自動機
- 鴿籠原理、組合與二項式定理：第9章的計數工具。
- 貝氏公式與期望值：第9章末尾的機率主題。
- 大 O、Omega 與 Theta 記號：第11章的記號。
- 有限狀態自動機：第12章的機器。
評析
優點
- 證明是教出來的，而不是預設的。 第1章從數學的語言開始，第2–3章講邏輯，第4章用十節的篇幅展開直接證明、寫作建議和間接論證。Cengage 的介紹稱本書「以易懂而精確的方法著稱」，並強調數學思維背後的推理。第五版修訂了關於量詞使用、證明概念、證明寫作建議和集合論證明的各節。
- 兩步式結構的例題。 據 Cengage 的特點列表，本書有500多個問題–解答形式的例題，證明的解答分兩步展開：先討論如何着手證明，再給出解答概要。學生可以選擇較快或較慢的節奏。
- 大量習題。 出版社稱習題超過2500道，包括應用題，以及線上系統中引導學生完成證明的新型習題。
- 電腦科學應用。 Cengage 稱書中有大量電腦科學應用，目錄也印證了這一點：數字邏輯電路與二進制加法（2.4–2.5）、演算法的正確性（5.5）、利用模算術的密碼學（8.4）、演算法效率分析（11.3、11.5）和自動機（第12章）。第五版的新內容包括二元搜尋樹、密碼學雜湊函數和消息認證。
侷限
- 計數與圖出現得較晚。 計數、機率和圖要到第9–10章纔出現（第1章簡要介紹了圖的語言），因此以組合數學或圖論為中心的課程需要跳着讀；出版社稱其組織方式允許把核心與選學內容混合。
- 沒有專門的數論或密碼學章節。 數論在第4章作為證明的載體出現，密碼學在8.4節作為模算術的應用出現；想要更完整論述的讀者需要其他資料。
- 篇幅。 亞洲版標註為984頁，對一門入門課程來說內容很多；教師需要選擇章節，而書的組織就是為此而設計的。
在課程中的定位
Epp 是本課程書單中以證明為中心的教材。Rosen 的《Discrete Mathematics and Its 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》留待以後學習：前者講演算法分析所需的求和、遞推式和生成函數，後者是研究生水平的組合數學教材。
如何使用本書
Epp 面向需要學習如何閱讀和寫作數學論證、同時接觸電腦科學所用離散結構的學生。它假定具備中學代數和對符號的基本熟悉，不要求微積分。
實用的學習安排如下：
- 核心（第1–5章）： 按順序閱讀。證明的習慣在第2–4章中養成，在做任何證明寫作作業之前，4.2節（寫作建議）值得一讀。
- 結構（第6–8章）： 集合、函數和關係；它們為後面幾乎所有內容提供詞彙。
- 計數與圖（第9–10章）： 本書的組合數學核心。
- 選學（第11–12章）： 演算法分析和自動機適合準備學習電腦科學課程的學生。
請做每一節的習題，並把例題當作自己書寫證明時的結構範本。