对位证明法

Template:Expert needed 对位证明法（Template:Lang-en，又或者Template:Lang），或称否定证明法、逆否命题法，是逻辑數學的其中一個證明方法。其与反证法相似，但是是不同的概念。根據邏輯，「$A\to B$」等於「$\mathrm{\neg }B\to \mathrm{\neg }A$」，即取其逆否命题。

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

定義

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

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

$A$	$B$	$\mathrm{\neg }A$	$\mathrm{\neg }B$	$A\to B$	$\mathrm{\neg }B\to \mathrm{\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$不是单数。」

反證法与对立證明的分別

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

否定證明：證明 $A\to B$ 正确，於是转换證明 $\mathrm{\neg }B\to \mathrm{\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$ 都是集（Template:Lang），而他们符合 $C\mathrm{\setminus }D\subset A\cap B$ 和 $x\in C$。證明如果 $x\notin A$，则 $x\in D$。

證明：

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

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

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

更多例子

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

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

参见

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