第一章：什麼是證明？
歡迎來到《計算機科學中的數學》互動教程。本章基於原文書第一章內容，探討數學證明的核心概念。
定義：數學證明
一個命題的數學證明是指從一組基本公理出發，經過一連串的邏輯推導，最終得出該命題的過程。
一個命題的數學證明是指從一組基本公理出發，經過一連串的邏輯推導，最終得出該命題的過程。
1.1 命題
定義： 命題是一個非真即假的陳述（通訊）。
命題必須有明確的真值，例如：
- ✅ "2 + 3 = 5" (真命題)
- ✅ "1 + 1 = 3" (假命題)
- ❌ "羅密歐，你在哪裡？" (疑問句，非命題)
- ❌ "給我一個 A！" (命令句，非命題)
🧠 隨堂測驗：這是命題嗎？
問題： "明天股票市場會上漲。"
1.2 述詞
述詞可以被理解為一個命題，但其真假取決於一個或多個變數的值。
例如："n 是一個完全平方數"。
- 當 n = 4 時，命題為真。
- 當 n = 5 時，命題為假。
我們通常寫作 P(n) 來表示。
1.3 公理化方法與推論
數學證明建立在公理之上，並透過推論規則來擴展知識。
肯定前件律 是最基本的一條推論規則：
若 P 為真，且 P 蘊含 Q (P IMPLIES Q)
則 Q 為真。
則 Q 為真。
這表示如果你已經證明了 P，也證明了 P 蘊含 Q，那麼你就可以斷言 Q 為真。
1.5 證明蘊含
形式為 "若 P，則 Q" 的命題稱為蘊含。有兩種主要證明方法：
方法一：直接證明
1. 寫下 "假設 P 為真"。
2. 利用邏輯推導出 Q。
方法二：證明逆否命題
蘊含 "P IMPLIES Q" 在邏輯上等價於其逆否命題 "NOT(Q) IMPLIES NOT(P)"。
有時證明逆否命題會更容易。
定理： 若 $r$ 是無理數，則 $\sqrt{r}$ 也是無理數。
證明策略： 我們證明其逆否命題：
若 $\sqrt{r}$ 是有理數，則 $r$ 是有理數。
證明過程：
假設 $\sqrt{r}$ 是有理數，則存在整數 $m, n$ 使得 $\sqrt{r} = m/n$。
兩邊平方得 $r = m^2 / n^2$。
因為 $m^2$ 和 $n^2$ 是整數，所以 $r$ 是兩整數之比，即 $r$ 是有理數。
證畢。
證明策略： 我們證明其逆否命題：
若 $\sqrt{r}$ 是有理數，則 $r$ 是有理數。
證明過程：
假設 $\sqrt{r}$ 是有理數，則存在整數 $m, n$ 使得 $\sqrt{r} = m/n$。
兩邊平方得 $r = m^2 / n^2$。
因為 $m^2$ 和 $n^2$ 是整數，所以 $r$ 是兩整數之比，即 $r$ 是有理數。
證畢。
1.6 證明 "若且唯若"
"P 若且唯若 Q" (P IFF Q) 意味著 P 蘊含 Q 且 Q 蘊含 P。
另一種方法是構造一連串的邏輯等價鏈。
1.7 分況證明
將複雜的證明分解為幾個不同的情況，並逐一證明。
經典範例：派對問題
定理： 在任何 6 人的群體中，總是存在 3 人互相認識，或者 3 人互不認識。
證明：
任選一人 x。剩下 5 人分為兩組：
情況一： 至少有 3 人認識 x。
- 若這 3 人中有一對互不認識，則他們與 x 構成 "3人互不認識"。
- 若這 3 人兩兩認識，則他們構成 "3人互相認識"。
情況二： 至少有 3 人不認識 x。
- 類似邏輯推導...
無論哪種情況，定理皆成立。
任選一人 x。剩下 5 人分為兩組：
情況一： 至少有 3 人認識 x。
- 若這 3 人中有一對互不認識，則他們與 x 構成 "3人互不認識"。
- 若這 3 人兩兩認識，則他們構成 "3人互相認識"。
情況二： 至少有 3 人不認識 x。
- 類似邏輯推導...
無論哪種情況，定理皆成立。
1.8 反證法
透過假設命題為假，進而推導出矛盾（如假的事實），以此證明命題必須為真。
證明：
1. 假設 $\sqrt{2}$ 是有理數。
2. 則 $\sqrt{2} = n/d$，且 $n, d$ 互質（不可約分）。
3. 平方得 $2d^2 = n^2$。這意味 $n$ 是偶數。
4. 設 $n=2k$，代回得 $2d^2 = 4k^2 \implies d^2 = 2k^2$。
5. 這意味 $d$ 也是偶數。
6. $n$ 和 $d$ 都是偶數，這與 "互質" 矛盾。
7. 故假設錯誤，$\sqrt{2}$ 是無理數。
1. 假設 $\sqrt{2}$ 是有理數。
2. 則 $\sqrt{2} = n/d$，且 $n, d$ 互質（不可約分）。
3. 平方得 $2d^2 = n^2$。這意味 $n$ 是偶數。
4. 設 $n=2k$，代回得 $2d^2 = 4k^2 \implies d^2 = 2k^2$。
5. 這意味 $d$ 也是偶數。
6. $n$ 和 $d$ 都是偶數，這與 "互質" 矛盾。
7. 故假設錯誤，$\sqrt{2}$ 是無理數。
1.9 好的證明實踐
寫出一個好的證明就像寫出一個好的程式碼，需要清晰與結構：
- 📝 陳述計畫： 一開始就說明你的證明策略（如：我們使用反證法）。
- ➡️ 保持線性流： 步驟應該按邏輯順序排列，不要跳躍。
- 🧩 使用句子： 證明是一篇文章，不僅僅是一串算式。
- 🧠 小心 "顯然"： 不要用 "顯然" 來掩蓋你無法證明的細節。
🧪 互動：Modus Ponens 推論機器
選擇一個情境，切換「P 為真/假」，觀察 Modus Ponens 是否能推導出結論 Q。
前提 1 — P
前提 2 — P → Q
—— modus ponens ⟹ ——
⚠️ 常見無效推論
肯定後件謬誤
「地是濕的→下雨了？」不，也可能是灑水車！
P→Q, Q ⊢ P ❌「地是濕的→下雨了？」不，也可能是灑水車！
否定前件謬誤
「沒下雨→地不濕？」不，灑水車還在呢！
P→Q, ¬P ⊢ ¬Q ❌「沒下雨→地不濕？」不，灑水車還在呢！
✅ 有效推導規則
假言三段論
若下雨就帶傘，若帶傘就不淋濕 → 若下雨就不淋濕
P→Q, Q→R ⊢ P→R ✓若下雨就帶傘，若帶傘就不淋濕 → 若下雨就不淋濕
逆否規則
若下雨則帶傘 ≡ 若沒帶傘則沒下雨
P→Q ≡ ¬Q→¬P ✓若下雨則帶傘 ≡ 若沒帶傘則沒下雨
🧪 互動：即時完整真值表
切換 P 和 Q 的真假值，下方所有連接詞的計算結果即時更新。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)