01 / 導讀
導讀
引用
Levin, O. (2025). Discrete Mathematics: An Open Introduction (4th ed.). Chapman & Hall/CRC. Free official edition: https://discrete.openmathbooks.org/dmoi4.html
章節概要
第0章：導論與預備知識
簡短的開篇一章透過握手、數列和計數等小謎題說明數學中什麼是「離散」的，隨後對全書使用的離散結構——集合、函數、數列、關係和圖——做一次非正式的初步介紹。這些結構在這裡是「按需」引入的，第5章會給出更正式的處理。
第1章：邏輯與證明
本章是全書通往證明的橋樑。內容包括原子敘述與複合敘述、量詞與述詞、蘊涵及其逆敘述與逆否敘述、真值表、邏輯等價（包括量化敘述的等價）以及演繹推理。隨後講授直接證明、逆否證明和反證法，新增的一節把這些方法用於集合、函數、關係和圖。章末總結以哥德巴赫猜想為例，說明敘述的邏輯形式如何提示證明的結構。
第2章：圖論
本章從柯尼斯堡七橋等問題出發定義圖，研究樹（性質、生成樹和有根樹）、平面圖及歐拉公式與多面體的關聯、歐拉跡與歐拉迴路以及漢米頓路徑，還有頂點著色和邊著色。關於關係的一節說明如何把關係、等價關係和分割看作圖，章末討論二部圖的匹配和霍爾婚配定理。
第3章：計數
本章在這一版中重新組織，著重於考察結果的集合而不是套用規則。它從透過格子路徑、位元串和子集合來理解的巴斯卡三角形開始，接著展開加法原理和乘法原理、處理重疊結果的排容原理、帶商原理的組合與排列、多重集合（用位元串表示的「隔板法」）以及組合證明。新增的一節把計數應用於機率，包括條件機率；最後一節用排容原理處理多重集合、錯排和函數計數。
第4章：數列
本章用一般項公式和遞迴公式、部分和與差分來描述數列，並附上簡短的 Python 範例。它研究等差數列和等比數列、透過有限差分得到的多項式數列，以及求和技巧（「倒序相加」「乘、移、減」），並用特徵根法求解線性遞迴。最後討論數學歸納法和強歸納法，把數列的遞迴描述與歸納推理連結起來。
第5章：再論離散結構
這是自成一體的一章，對集合（記號、包含關係、運算和文氏圖）和函數（描述方式、嵌射、蓋射與雙射、像與原像）作更完整的討論。序言指出這一章可以獨立於全書其他部分學習。
第6章：補充專題
兩個補充專題為全書作結。生成函數透過差分、乘法和部分和來建構和運算，並用於求解遞迴關係。數論導引涵蓋整除、餘數類、同餘的性質、解同餘式以及解線性丟番圖方程式。
核心概念
第0章：導論與預備知識
- 離散結構：由彼此分離、各不相同的元素構成的數學對象——如集合、數列、關係或圖——用於為實際問題建模。
- 作為離散結構的函數：給定義域中每個元素指定對應域中恰好一個元素的規則，常在有限集合之間考慮。
第1章：邏輯與證明
- 蘊涵：「如果 P，那麼 Q」形式的敘述，僅當 P 真 Q 假時為假；其逆否敘述與之邏輯等價，而逆敘述則不然。
- 量詞：「對所有」和「存在」，它們的順序與否定決定了敘述的意義。
- 證明方式：根據敘述的邏輯形式選擇直接證明、逆否證明或反證法。
第2章：圖論
- 樹：沒有迴路的連通圖；有 n 個頂點的樹有 n − 1 條邊。
- 歐拉公式：對連通平面圖，頂點數減邊數加面數等於 2。
- 歐拉跡：恰好經過每條邊一次的路線，若且唯若圖連通且奇度頂點個數為 0 或 2 時存在。
- 色數：使相鄰頂點顏色不同所需的最少顏色數。
第3章：計數
- 加法原理與乘法原理：互斥的選擇相加，獨立的步驟相乘。
- 排容原理：透過交替加減各交集的大小來校正重疊部分。
- 組合證明：藉由說明等式兩邊計數的是同一集合來證明恆等式。
- 錯排：沒有不動點的排列，用排容原理計數。
第4章：數列
- 遞迴公式與一般項公式：由前面的項描述某一項，或直接由足標描述它。
- 特徵根法：利用相關多項式的根求解費氏數遞迴之類的線性遞迴。
- 數學歸納法：透過基礎情況和歸納步驟對所有 n 證明敘述；強歸納法使用此前所有情況。
第5章：再論離散結構
- 集合運算：聯集、交集、差集、補集和笛卡兒積，用文氏圖加以說明。
- 雙射：既是嵌射又是蓋射的函數，因而把兩個集合的元素一一配對。
第6章：補充專題
- 生成函數：以數列各項為係數的冪級數，用於運算和求解遞迴關係。
- 模 n 同餘：兩個整數除以 n 餘數相同，就稱它們同餘。
- 線性丟番圖方程式：求整數解的方程式 ax + by = c。
評析
優點
- 為探究式教學而設計。 每節都以開放性的「Investigate!」問題和結構化的預習活動開始，以閱讀問題結束，然後是練習題和補充習題。序言介紹了多種用法——課前預習、課堂小組活動等——這種結構同樣支持自學。
- 題庫大且類型多樣。 第四版新增近 300 道習題，總數超過 750 道，分為預習、閱讀、練習和補充習題，每章末還有章節複習；部分題目的提示和解答收在兩個附錄中。
- 互動式線上版。 線上版中許多預習活動和練習題可以即時回饋，有些還能隨機產生不同版本，並提供 Python 草稿區；第4章包含關於數列的簡短 Python 範例。
- 透過結果集合來計數。 改寫後的計數一章強調辨識結果的集合而不是死背公式，章末總結中的 Investigate! 要求學生按方法對表面相似的問題進行分類。
局限
- 選題服務於特定課程。 序言說明選題是針對北科羅拉多大學的學生；書中沒有演算法分析（漸近記號）、布林代數、有限狀態機或形式語言，資訊科學課程可能需要補充材料。
- 部分領域深度有限。 數論和生成函數只是簡短的「補充專題」，機率只佔一節，圖論止步於網路流或最短路徑演算法等內容之前。
- 歸納法出現較晚。 歸納法放在數列一章末尾，而不是與第1章的其他證明方法放在一起，有些教師可能希望提前講授。
- 印刷版和 PDF 失去互動性。 即時回饋、隨機練習和隱藏提示都是線上版的功能；使用 PDF 的讀者需要依靠附錄和自律來檢查答案。
書中的應用
應用融入在例題和習題之中，而不是集中在單獨的章節。圖論以柯尼斯堡七橋、地圖著色、多面體和匹配問題為動機；計數被應用於機率，包括條件機率；數列與現實情境的遞迴描述相連結，並用 Python 計算各項；強歸納法與分治思想相連結；數論部分則以解同餘式和線性丟番圖方程式收尾。
在課程中的定位
在這份離散數學書單中，Levin 的書與 Lovász、Pelikán、Vesztergombi 所著 Discrete Mathematics: Elementary and Beyond（一般被視為以問題驅動、更側重數論與組合的入門書）並列。Rosen 的 Discrete Mathematics and Its Applications 和 Epp 的 Discrete Mathematics with Applications 一般被描述為內容全面的教科書；它們涵蓋 Levin 未涉及的演算法與複雜度等主題，可以在以 Levin 作為易讀核心教科書的資訊科學課程中充當參考書。
Graham、Knuth、Patashnik 的 Concrete Mathematics 以及 van Lint 與 Wilson 的 A Course in Combinatorics 則走得更遠。Levin 的第3、4、6章（計數、數列與遞迴、生成函數）是通往這兩本書的良好準備；喜歡這些章節的學生可以轉向 Concrete Mathematics 學習求和與漸近技巧，或轉向 van Lint 與 Wilson 學習更深入的組合數學。
如何使用本書
本書針對數學和資訊科學系的一、二年級大學生，也包括未來的中小學教師；它同時可以作為通往證明的銜接課程。開始學習只需中學代數，不要求有證明經驗。
一學期課程可以按書中順序進行：第0章、第1章（邏輯與證明）、第2章（圖論）、第3章（計數）和第4章（數列與歸納法），第5章用作參考或複習，第6章作為延伸。序言指出各節相對獨立，教師可以調整順序。每一節都應在閱讀前先嘗試 Investigate! 問題和預習活動，讀後回答閱讀問題，然後做練習題——最好在線上完成以獲得即時回饋——再做補充習題和章末複習。按照作者的建議，盡量少看提示和解答。
版本與來源
本導讀依據 Discrete Mathematics: An Open Introduction 第四版（© 2013–2025 Oscar Levin，CC BY-NC-SA 4.0；序言日期為 2024 年，PDF 產生於 2025 年 9 月），閱讀的是官方版本頁面 https://discrete.openmathbooks.org/dmoi4.html 連結的免費 PDF。導讀參考了致謝、序言（目標、探究式設計和第四版的改動）、「如何使用本書」、細到小節的完整目錄、第0章全文、第1–4章的章末總結，以及全書各節的開篇和主要結論（包括霍爾婚配定理、鴿籠原理以及數列與歸納法的內容）。