分類證明

分類證明（粵拼：Fan¹ leoi⁶ zing³ ming⁴；英文：Proof by exhaustion，或者 Proof by cases）係咁多種證明方法之一。當一個命題出現多個可能嘅時候，就可以將佢分做個案（Case），再睇下每個個案出嚟嘅結果。利用分類證明嘅定理包括咗四色問題（Four Colour Problem）。

好多好有用嘅定理都需要用到分類證明嚟證明，例如三角形不等式、絕對值等。

例子

要求：證明「任何整數 $n\in \mathbb {Z}$，$n^{2}+3n+7$ 係一個單數。」

如果 $n$ 係雙數

如果 $n$ 係雙數，咁就有一個整數 $k\in \mathbb {Z}$ 符合 $n=2k$。

${\begin{aligned}n^{2}+3n+7&=(2k)^{2}+3(2k)+7\\&=4k^{2}+6k+7\\&=2(2k^{2}+3k+3)+1\end{aligned}}$

因此，$n^{2}+3n+7$ 係一個單數。

如果 $n$ 係單數

如果 $n$ 係單數，咁就有一個整數 $k\in \mathbb {Z}$ 符合 $n=2k+1$。

${\begin{aligned}n^{2}+3n+7&=(2k+1)^{2}+3(2k+1)+7\\&=4k^{2}+10k+11\\&=2(2k^{2}+5k+5)+1\end{aligned}}$

因此，$n^{2}+3n+7$ 係一個單數。

因為整數一係單數一係雙數，而喺以上兩個個案入面 $n^{2}+3n+7$ 都係一個單數，所以「任何整數 $n\in \mathbb {Z}$，$n^{2}+3n+7$ 係一個單數。」呢句命題成立。

更多例子

以下嘅定理可以用分類證明簡單咁證出嚟。

• 任何一個平方都係，對應某啲 $k\in \mathbb {Z}$，「$3k$」或者「$3k+1$」是但一個樣。
• 任何一個三次方都係，對應某啲 $k\in \mathbb {Z}$，「$9k$」、「$9k+1$」或者「$9k+8$」是但一個樣。
• 設 $A$、$B$ 做一個集。「$A\cup B=(A\cap B)\cup (A\backslash B)\cup (B\backslash A)$」
• $|xy|=|x||y|$
• ${\bigl |}{\frac {x}{y}}{\bigr |}={\frac {|x|}{|y|}}$
• $||x|-|y||\leq |x-y|$
• $|x|={\sqrt {x^{2}}}$
• 證明最高值函數（Maximum Function），$\max(x,y)$，係 ${\frac {x+y+|x-y|}{2}}$。
• 證明最低值函數（Minimum Function），$\min(x,y)$，係 ${\frac {x+y-|x-y|}{2}}$。

睇埋

• 直接證明
• 否定證明
• 數學歸納法
• 矛盾證明

參考

• Kleene, S. C. (1934). Proof by cases in formal logic. Annals of Mathematics, 529-544.