形式陈述

若情形 $C_1,\ldots,C_k$$C_1,\dots ,C_k$ 穷尽所有可能，即 $C_1\lor\cdots\lor C_k$$C_1\vee \cdots \vee C_k$，并且对每个 $i$$i$ 都证明 $C_i\Rightarrow P$$C_i\Rightarrow P$，则可推出 $P$$P$。各情形可以重叠，但必须覆盖全部论域。

直觉

分类讨论先把复杂对象空间切成结构统一的小块，再在每块使用最适合的论证。正确性取决于穷尽性，不取决于分类是否看起来自然。

例子与边界

证明任意整数 $n$$n$ 的 $n(n+1)$$n(n+1)$ 为偶数，可分 $n$$n$ 偶与 $n$$n$ 奇两种情形。按模 $m$$m$ 余数分类时必须覆盖 $0,1,\ldots,m-1$$0,1,\dots ,m-1$；只讨论正、负会漏掉零。

推论与应用

绝对值、奇偶性、符号、图局部结构和算法分支都常用分类讨论。复杂证明可先给出分类引理，避免重复边界条件。

参考资料

• Richard Hammack, Book of Proof, 3rd ed., 2018, Chapter 5。
• Daniel J. Velleman, How to Prove It: A Structured Approach, 3rd ed., Cambridge University Press, 2019, Proof Strategies chapter。