逆否证明法

逆否法改变的是进入证明的入口。有时从 $P$ 出发难以取得信息，而 $\mathrm{\neg }Q$ 能立即写成具体形式。要从“平方是偶数”推出“数是偶数”，平方的条件不直接告诉我们原数的写法；若原数不是偶数，却可以马上写成 $2k+1$。

这仍是在直接证明理路直接证明Direct proof从假设和已知事实经有效推理直接导出结论。一个蕴含：从新的前提走向新的结论。它与反证法理路反证法Proof by contradiction · Reductio ad absurdum假设目标命题为假并推出矛盾，从而证明目标。的写法不同，后者通常同时假设 $P$ 与 $\mathrm{\neg }Q$，再推出矛盾。两种方法可以转换，但逆否路线经常让中间目标更明确。

平方的奇偶性 ​

设 $n\in \mathbb{Z}$，证明 $n^2$ 为偶数蕴含 $n$ 为偶数。逆否命题为“$n$ 为奇数蕴含 $n^2$ 为奇数”。写 $n=2k+1$，其中 $k$ 为整数，则

括号中的量为整数，所以 $n^2$ 确为奇数。到这里证明的是“$n$ 不偶 $\Rightarrow n^2$ 不偶”；再由逆否等价回到原目标“$n^2$ 偶 $\Rightarrow n$ 偶”。若遗漏最后的目标对应，容易把正确的代数计算误配到错误命题上。

这里“不是偶数即奇数”依赖论域是整数；若没有写清论域，这种否定转换就缺少依据。另证“$n$ 偶数则 $n^2$ 偶数”虽然正确，却只证了原命题的逆命题。

余数为何帮助处理否定 ​

符号 $3\mid n$ 表示 $n$ 是 $3$ 的整数倍，$3\nmid n$ 则表示不是。要证明 $3\mid n^2\Rightarrow 3\mid n$，逆否路线从 $3\nmid n$ 出发。整数除以 $3$ 只可能余 $1$ 或 $2$，平方后分别余 $1$ 或 $4\equiv 1(\mathrm{mod}3)$，所以 $3\nmid n^2$。这段论证对模 $3$ 有效，不能仅改数字就推广到所有除数：$4\mid 2^2$，但 $4\nmid 2$。

否定复合条件 ​

若结论为 $Q\wedge R$，其否定是 $\mathrm{\neg }Q\vee \mathrm{\neg }R$，不是 $\mathrm{\neg }Q\wedge \mathrm{\neg }R$。若结论为 $\mathrm{\forall }xQ(x)$，其否定是 $\mathrm{\exists }x\mathrm{\neg }Q(x)$，所以逆否证明的临时假设提供的是某个反例见证，不能假设所有对象都不满足 $Q$。若目标是 $A\Rightarrow \mathrm{\forall }xQ(x)$，具体做法是选取这个失败见证，用它推出 $\mathrm{\neg }A$；不能把原结论中的“每个”原封不动保留在否定中。

经典逻辑的限制也要说明。从 $P\Rightarrow Q$ 推出 $\mathrm{\neg }Q\Rightarrow \mathrm{\neg }P$ 在直觉主义逻辑中仍成立；反过来，给定逆否式并假设 $P$，一般只能排除 $\mathrm{\neg }Q$，得到 $\mathrm{\neg }\mathrm{\neg }Q$。恢复 $Q$ 需要双重否定消去，或需要 $Q$ 可判定等额外条件。

逻辑等价理路逻辑等价Logical equivalence两个公式在指定语义类的每个结构与赋值下具有相同真值。保证经典语境中转换后没有丢失原来的证明任务。整除性质、集合包含、结构必要条件都常适合这种转换；是否省力取决于否定后的条件能否给出更明确的对象或计算。

对全称蕴含 $\mathrm{\forall }x(P(x)\Rightarrow Q(x))$，反例恰是一个满足 $P(x)\wedge \mathrm{\neg }Q(x)$ 的对象。逆否法说明这样的对象不可能存在；寻找反例时，这个形式也能准确提示应该同时检查哪两项条件。