數學證明（Mathematical Proofs）

窮舉法（exhaustion）

直接把所有可能性列出來。

例如要證明「北一女中的一年善班全部都是女生」，就依序證明一年善班的 1 號同學是女生、2 號同學是女生...一路到最後一號同學都是女生，這樣就可以知道「北一女中的一年善班全部都是女生」這個命題為真。

在數學上，假設要證明「(∀X)[(x<5)→(x²<25)]，x∈N」，則 x 有下列四種可能：

1. x=1 → (x²=1) → (x²<25) 為真
2. x=2 → (x²=4) → (x²<25) 為真
3. x=3 → (x²=9) → (x²<25) 為真
4. x=4 → (x²=16) → (x²<25) 為真

將 x 每一種可能的情況都列出來並一一檢視，這就是「窮舉法」，但因為窮舉法只能用在有限的情形，在數學上的應用相對較為少見。

直接法（direct proof）

即「(P→Q)」，不另做假設，從公認事實直接推出結果，常用謂詞邏輯，如肯定前件、全稱實例化等，上個段落的「窮舉法」也屬於直接法。

例如要證明「若 x 為偶數，則 x² 也是偶數」，可採用下列方式：

1. 設 x=2k，k∈Z
2. x²=(2k)²=4k²=2(2k²)
3. 令 j=2k²，因 x²=2j，而 2j 必為偶數，因此 x² 為偶數

逆否命題法（contraposition）

當 (P→Q) 證明較為困難時，可改證「(Q'→P')」，根據「離散數學學習筆記（一）」的內容可知「(P→Q)↔(Q'→P')」。

以上述「若 x 為偶數，則 x² 也是偶數」為例，其實也能改證「若 x² 不是偶數，則 x 不是偶數」。

1. 設 x=2k+1，k∈Z
2. x²=(2k+1)²=(4k²+4k+1)=2(2k²+2k)+1
3. 令 j=(k²+2k)，因 (2j+1) 必不為偶數，因此 x² 不是偶數

反證法（contradiction）

跟「逆否證明法」不同，反證法是先假設一個命題成立，最後推出跟該假設矛盾的結果。

例如要證明「這家公司營運狀況不好」，則可以先假設「這家公司營業額很高」，但事實上卻是財政赤字，因為「財政赤字」與「營業額很高」這個假設矛盾，因此可說明「這家公司營運狀況不好」。

在數學上來說，常被用來證明「√2 為無理數」：

假設 √2 為有理數，則根據有理數的定義，√2=q/p，其中 p、q∈Z 且 p、q 互質

1. 將 √2 平方得 2=q²/p²，因此 q²=2p²
2. 根據「若 q² 為偶數，則 q 為偶數」，可設 q=2k，k∈Z
3. 將第 2. 步所得 q²=2p² 的 q 代換為 2k，可得 (2k)²=2p²
4. 將 (2k)²=2p² 展開後得 4k²=2p²，化簡得 2k²=p²
5. 令 k²=j，j∈Z，則 p²=2j，由此可知 p² 為偶數
6. 根據「若p²為偶數，則p為偶數」，可知 p 為偶數
7. 因 p 為偶數，可設 p=2a，其中 a∈Z
8. 綜合第 3. 步與第 8. 步結果，可知 p 與 q 兩者同為偶數，必有一公因數「2」，因此 p、q 不互質，與第 1. 步假設矛盾

看起來有些複雜，但核心概念就是先提出一個跟原命題概念相反的假設，經過一系列推理過程，得出與該假設矛盾之結果，則可說明欲證明的命題為真。

數學歸納法（mathematical induction）

相信對於所有在臺灣讀高中的人來說，「數學歸納法」這個名詞並不陌生，一般常以「骨牌效應」做類比。

在「骨牌效應」中，有這樣的概念：

1. 第一張骨牌先倒下
2. 若第二張開始的第 n 張骨牌倒下，則第 n+1 張骨牌必倒下

「數學歸納法」共有三步驟：

1. 證明「n=1」時成立
2. 假設「n=k」成立
3. 將「n=k」代入推理出「n=k+1」的過程，若仍成立則原命題為真

例如要證明等差級數公式「1+2+...+n=[n(n+1)]/2」，可用數學歸納法證明如下：

1. n=1 時，1=[1(1+1)/2]，成立
2. 設 n=k 時，1+2+...+k=[k(k+1)]/2] 成立
3. 當 n=k+1 時，總和為 1+2+…+k+(k+1)
4. 第 3. 步粗體部分以 [k(k+1)]/2] 代換，得 [k(k+1)]/2+(k+1)
5. 將 [k(k+1)]/2+(k+1) 通分，得 [k(k+1)+2(k+1)]/2
6. 展開分子，得 (k²+3k+2)/2
7. 將分子因式分解，得 (k+1)(k+2)/2
8. 將 (k+2) 改寫為 (k+1)+1，得 (k+1)[(k+1)+1]/2，得證

小結

1. 窮舉法：列出所有可能狀況。
2. 直接法：證明 (P→Q)。
3. 逆否命題法：證明 (Q'→P')，多用於 (P→Q) 不易證明時。
4. 反證法：提出與原命題相反的假設後，證明該假設矛盾，推得原命題為真。
5. 數學歸納法：先假設 n=1 成立，再假設 n=k 成立，最後將 n=k 的假設代入 n=k+1 中，若 n=k+1 時成立，則原命題為真。