对位证明法

对位证明法^[1]（英語：proof by contrapositive，又或者proof by negation），或称否定证明法、逆否命题法^[2]，是逻辑數學的其中一個證明方法。其与反证法相似，但是是不同的概念。根據邏輯，「${\displaystyle A\to B}$」等於「${\displaystyle \neg B\to \neg A}$」，即取其逆否命题。^[3]

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

定義

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

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

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle \neg A}$	${\displaystyle \neg B}$	${\displaystyle A\to B}$	${\displaystyle \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

例子

• 「我的妈妈是女人。」需要证明的逆否命题是「不是女人就不是我的妈妈。」
• 「若${\displaystyle x}$ 是单数，则${\displaystyle x+1}$ 是双数。」需要证明的逆否命题是「若${\displaystyle x+1}$ 不是双数，则${\displaystyle x}$ 不是单数。」

反證法与对立證明的分別

反證法：假設 ${\displaystyle \neg A}$  正确，${\displaystyle \neg A\to B}$ ，發現 ${\displaystyle B}$  不对，於是證明 ${\displaystyle A}$  正确。

否定證明：證明 ${\displaystyle A\to B}$  正确，於是转换證明 ${\displaystyle \neg B\to \neg A}$  正确。

證明例子

證明「假設 ${\displaystyle x^{2}}$  是雙數，则${\displaystyle x}$  都會是雙數。」

證明：

逆否命题：「假設 ${\displaystyle x}$  不是雙數，则 ${\displaystyle x^{2}}$  也不是雙數。」

換句話講，即係「假設 ${\displaystyle x}$  是單數，则 ${\displaystyle x^{2}}$  也是單數。」

因為 ${\displaystyle x}$  是單數，所以 ${\displaystyle x=2k+1,k\in \mathbb {Z} }$  的${\displaystyle k}$ 是整数。

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

因為 ${\displaystyle 2k^{2}+k}$  是整数，所以 ${\displaystyle x^{2}}$  是單數。

集合論例子

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

證明：

如果用直接證明，會很麻烦。但是，如果利用对立證明，即假設 ${\displaystyle x\notin D}$ 则会简单得多。

因為 ${\displaystyle x\in C}$ ，而 ${\displaystyle C\backslash D\subset A\cap B}$ ，所以 ${\displaystyle x\in A\cap B}$ 。

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

更多例子

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

• 假設 ${\displaystyle x,y\in \mathbb {N} }$  都是自然數。如果 ${\displaystyle xy}$  是單數，则 ${\displaystyle x}$  和 ${\displaystyle y}$  都是單數。
• 假設 ${\displaystyle x,y\in \mathbb {R} }$  都是實數。如果 ${\displaystyle x+y}$  是無理數，则 ${\displaystyle x}$  或者 ${\displaystyle y}$  是無理數。

参见

• 直接證明
• 穷举法
• 數學歸納法
• 反證法
• 歸謬法

參考

1. 【学习笔记】离散数学（Discrete Math） - 证明 Proof 3. blog.csdn.net. [2021-11-18]. （原始内容于2021-11-18）. 
2. 反證法與逆否命題法. 線代啟示錄. 2016-03-17 [2021-11-18]. （原始内容于2021-11-18） （英语）. 
3. Mariotti, M. A. (2006). Proof and proving in mathematics education. Handbook of research on the psychology of mathematics education: Past, present and future, 173-204