分类讨论证明

一个结论可能没有对所有输入都同样方便的证明。遇到绝对值时，正数与负数的公式不同；遇到整数整除时，不同余数带来不同表达式。分类把一个问题拆成几条较短的路线，每条路线都通向同一终点。

分支条件是暂时增加的信息。例如在“$n$ 为偶数”分支里可以写 $n=2k$，但出了这个分支便不能继续沿用这一表示。若一条证明最后还依赖某个未撤销的分支条件，它只证明了条件结论，并未完成全体情形。

奇偶分类为何覆盖全部整数 ​

证明每个整数 $n$ 的 $n(n+1)$ 都是偶数。任意整数除以 $2$ 的余数只能为 $0$ 或 $1$，所以只有以下两类：

• 若 $n=2k$，则 $n(n+1)=2k(2k+1)$，是 $2$ 的整数倍。
• 若 $n=2k+1$，则 $n(n+1)=(2k+1)(2k+2)=2(2k+1)(k+1)$，仍是 $2$ 的整数倍。

两个分支中的 $k$ 均为整数，负整数也包括在内；例如 $-3=2(-2)+1$。证明的覆盖范围由除法的余数性质保证，并非由检查几个正整数保证。

按余数分类 ​

符号 $3\mid m$ 表示 $m$ 是 $3$ 的整数倍。要证明 $3\mid n^3-n$，写 $n=3k+r$，其中 $r$ 为 $0,1,2$ 之一。为什么只算余数就足够？展开得

前半部分已经是 $3$ 的倍数，所以只剩 $r^3-r$ 需要检查：

三种结果都被 $3$ 整除，连同前半部分便证明了整个表达式被 $3$ 整除。也可将 $n^3-n$ 写成三个连续整数的乘积 $(n-1)n(n+1)$，再指出其中必有一个是 $3$ 的倍数；后一条路线把分类隐藏在“必有一个”中。

重叠不碍事，遗漏才会失效 ​

证明实数恒等式 $|x{|}^2=x^2$ 时，可分为 $x\ge 0$ 与 $x\le 0$。前一支由 $|x|=x$ 得出，后一支由 $|x|=-x$ 得出。$0$ 同时出现在两支中，但两支都证明了目标，所以重叠不影响结论。这里不是计数，不存在重复计算导致答案翻倍的问题。

最常见的漏洞是漏边界：按正负讨论实数却漏掉 $0$，或按模 $m$ 分类漏掉一个余数。另一种漏洞是各分支证明了不同结论；例如一个分支得到 $P$，另一个只得到 $Q$，至多能合并为 $P\vee Q$，不能直接宣称 $P$。

自然演绎理路自然演绎Natural deduction用引入规则与消去规则直接刻画逻辑联结词推理行为的证明演算。中的析取消去规则形式化了这个过程：已知一个析取式，并从每个析取支分别推出目标，就可以推出目标。反过来，只有分支证明而没有析取前提，并不能启动这条规则。

反证法理路反证法Proof by contradiction · Reductio ad absurdum假设目标命题为假并推出矛盾，从而证明目标。和归纳证明中也可嵌入分类。验证算法时，程序的分支条件经常给出分类标准；证明者仍须检查输入是否全部被覆盖、各分支是否保持同一目标性质。分类过细只会重复劳动，通常应按真正改变论证方式的条件分组。