附錄 B：證明技巧總覽#

離散數學是「學如何證明」的最佳訓練場：定理短、物件具體、反例好找。本附錄彙整本書各章使用過的證明模式，供寫作與複習時對照。

B.1 直接證明（Direct Proof）#

從前提出發，用定義與已知定理逐步推到結論。

範例（第 7 章）：若 \(a \equiv b \pmod n\) 且 \(c \equiv d \pmod n\) ，則 \(a+c \equiv b+d \pmod n\) 。 證明： \(a-b = kn\) ， \(c-d = \ell n\) ，相加得 \((a+c)-(b+d) = (k+\ell)n\) 。 \(\blacksquare\)

B.2 反證法（Proof by Contradiction）#

假設結論為假，推出矛盾。適用於「不存在性」與「不可數性」。

範例（第 2 章）： \(\mathbb R\) 不可數——Cantor 1891 對角線法：假設可列出所有實數 \(r_1, r_2, \dots\) ，構造 \(x\) 使第 \(n\) 位與 \(r_n\) 第 \(n\) 位不同， \(x\) 不在列表中，矛盾。 \(\blacksquare\)

範例（第 7 章）：質數有無窮多個（Euclid 約 300 BC）：假設 \(p_1,\dots,p_k\) 是全部，令 \(N = p_1\cdots p_k + 1\) ， \(N\) 除以任何 \(p_i\) 餘 1，故有新質數。 \(\blacksquare\)

B.3 數學歸納法（Mathematical Induction）#

1. 基底：證 \(P(1)\) 。
2. 歸納步：由 \(P(k)\) 推 \(P(k+1)\) 。

範例（第 4 章）：漢諾塔需 \(2^n - 1\) 步。基底 \(n=1\) 顯然；歸納步：先移 \(n-1\) 個（ \(2^{n-1}-1\) 步）、移最大盤（1 步）、再移 \(n-1\) 個（ \(2^{n-1}-1\) 步），合計 \(2^n - 1\) 。 \(\blacksquare\)

強歸納（Strong Induction）：由所有 \(P(1),\dots,P(k)\) 推 \(P(k+1)\) ，用於 Fibonacci、質因數分解等「分解成任意小件」的場合。

B.4 若且唯若的雙向證明#

證 \((\Rightarrow)\) 與 \((\Leftarrow)\) 兩方向，缺一不可。

範例（第 5 章）：連通圖有尤拉迴路 \(\iff\) 每個頂點度數為偶數（Euler 1736）——必要方向靠「進出配對」，充分方向靠構造。

B.5 構造法（Constructive Proof）#

直接給出物件，而非只證存在。

範例（第 6 章）：Kruskal 演算法不只證明最小生成樹存在，還給出 \(O(|E|\log|E|)\) 的建構程序。

B.6 反例法（Counterexample）#

證明一個「全稱命題」為假，只需一個反例。

範例（第 5 章）：「所有連通正則圖都有漢米頓迴路」——Petersen 圖（3-正則、10 頂點）無漢米頓迴路，反例即駁。

B.7 對角線法（Diagonalization）#

在無限列表上「沿對角線取反」， Cantor 1891 原創，後被 Gödel 1931（不完備定理）與 Turing 1936（停機問題）繼承。

範例（第 8 章）：停機問題不可判定：假設有判定器 \(H\) ，構造程式 \(Q\) ：「若 \(H\) 說 \(Q\) 會停，就無限迴圈；反之停機」， \(H\) 對 \(Q\) 必答錯。 \(\blacksquare\)

B.8 分類證明（Proof by Cases / Exhaustion）#

把情況枚舉完。

範例（第 5 章）：平面圖五色定理（Heawood 1890）對 6 度以上頂點分類，配合 Kempe 鏈交換。

B.9 對偶與映射（Bijection Proof）#

把「數 \(A\) 的個數」化為「數 \(B\) 的個數」，透過雙射。

範例（第 3 章）：Catalan 數 \(C_n = \frac{1}{n+1}\binom{2n}{n}\) 有十幾種雙射證明（括號配對、二叉樹、格路徑反射法）。

小結#

離散數學的證明能力，本質上是「策略庫 + 物件感」的結合——本書各章的證明都刻意標注所屬模式，建議讀者讀完每個證明後問自己：「這招還能用在哪裡？」