否定證明

否定證明（粵拼：Fau² ding⁶ zing³ ming⁴；英國話：Proof by negation，又或者 Proof by contrapositive）係數學入面其中一個證明方法。佢同矛盾證明好似，不過係兩個唔同嘅概念。根據邏輯，「$A\implies B$」係等於「${\text{not }}B\implies {\text{not }}A$」。呢個就係否定證明嘅核心概念。

否定句

一般數學句子都會有佢嘅相反，但係咩係一句句子嘅完全相反，就需要用到邏輯學幫手。

定義

一句句子「$A\implies B$」嘅否定（Contrapositive）係「${\text{not }}B\implies {\text{not }}A$」。

例子

• 「我阿媽係女人。」嘅否定係「唔係女人嘅就一定唔係我阿媽。」
• 「我食飯，就會飽。」嘅否定係「我唔飽，即係我冇食飯。」

理論

證明出「${\text{not }}B\implies {\text{not }}A$」，即係證明出「$A\implies B$」。

證明例子

證明「假設 $x^{2}$ 係雙數，$x$ 都會係雙數。」

證明：

否定句：「如果 $x$ 唔係雙數，咁 $x^{2}$ 都唔係雙數。」

換句話講，即係「如果 $x$ 係單數，咁 $x^{2}$ 都係單數。」

因為 $x$ 係單數，所以 $x=2k+1,k\in \mathbb {Z}$ 係個整數。

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

因為 $2k^{2}+2k$ 係個整數，所以 $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$ 一定成立。

反證法同否定證明嘅分別

反證法就係：假設 $A$ 啱，$A\implies B$，又發現 $B$ 唔啱。於是乎證明到 $A$ 唔啱。

否定證明就係：證明到 $A\implies B$ 啱。於是乎證明到 ${\text{not }}B\implies {\text{not }}A$ 啱。

更多例子

以下命題都係用否定證明證出嚟：

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

睇埋

• 直接證明
• 分類證明
• 數學歸納法
• 反證法

參考

• 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.