對位證明法

對位證明法（英語：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$ 是無理數。

參見

• 直接證明
• 窮舉法
• 數學歸納法
• 反證法
• 歸謬法