对位证明法

对位证明法（英语：proof by contrapositive，又或者proof by negation），或称否定证明法、逆否命题法，是逻辑数学的其中一个证明方法。其与反证法相似，但是是不同的概念。根据逻辑，“$A\to B$”等于“$\neg B\to \neg A$”，即取其逆否命题。

需要注意，对位证明法与反证法不同。

定义

给予给予初始实质条件命题“若P，则Q”：$A\to B$，对位证明法证明其逻辑等价的逆否命题“若非Q，则非P”：$\neg B\to \neg A$的真值。

逻辑上，对立证明法的可用性可以以比较逆否命题和原命题的真值表证明，即证明$A\to B$和$\neg B\to \neg A$的真值完全一样：

$A$	$B$	$\neg A$	$\neg B$	$A\to B$	$\neg B\to \neg A$
T	T	F	F	T	T
T	F	F	T	F	F
F	T	T	F	T	T
F	F	T	T	T	T

例子

• “我的妈妈是女人。”需要证明的逆否命题是“不是女人就不是我的妈妈。”
• “若$x$是单数，则$x+1$是双数。”需要证明的逆否命题是“若$x+1$不是双数，则$x$不是单数。”

反证法与对立证明的分别

反证法：假设 $\neg A$ 正确，$\neg A\to B$，发现 $B$ 不对，于是证明 $A$ 正确。

否定证明：证明 $A\to B$ 正确，于是转换证明 $\neg B\to \neg A$ 正确。

证明例子

证明“假设 $x^{2}$ 是双数，则$x$ 都会是双数。”

证明：

逆否命题：“假设 $x$ 不是双数，则 $x^{2}$ 也不是双数。”

换句话讲，即系“假设 $x$ 是单数，则 $x^{2}$ 也是单数。”

因为 $x$ 是单数，所以 $x=2k+1,k\in \mathbb {Z}$ 的$k$是整数。

$x^{2}=(2k+1)^{2}=4k^{2}+2k+1=2(2k^{2}+k)+1$

因为 $2k^{2}+k$ 是整数，所以 $x^{2}$ 是单数。

集合论例子

如果 $A,B,C,D$ 都是集（set），而他们符合 $C\backslash D\subset A\cap B$ 和 $x\in C$。证明如果 $x\notin A$，则 $x\in D$。

证明：

如果用直接证明，会很麻烦。但是，如果利用对立证明，即假设 $x\notin D$则会简单得多。

因为 $x\in C$，而 $C\backslash D\subset A\cap B$，所以 $x\in A\cap B$。

这样 $x\in A$ 一定成立。

更多例子

以下命题都可以用对立证明证真：

• 假设 $x,y\in \mathbb {N}$ 都是自然数。如果 $xy$ 是单数，则 $x$ 和 $y$ 都是单数。
• 假设 $x,y\in \mathbb {R}$ 都是实数。如果 $x+y$ 是无理数，则 $x$ 或者 $y$ 是无理数。

参见

• 直接证明
• 穷举法
• 数学归纳法
• 反证法
• 归谬法