反證法粵拼:Faan2 zing3 faat3英國話:Proof by contradiction),又叫做證偽法矛盾證明,係一個數學上一個攞嚟證明啲嘢唔啱嘅方法。係拉丁話入面,反證法畀人嗌做「reductio ad absurdum」(英國話:reduction to the absurd),意思係「推斷出荒謬嘅嘢」。

呢個方法嘅橋妙係咁:首先整一個命題(Proposition),然後就假設(Assume) 呢個命題係啱嘅;跟住就推一啲只要 係啱,就一定會發生嘅結果出嚟,最後就指出呢個結果係唔成立或者係喺邏輯上矛盾嘅,咁就可以證明 係錯嘅。

真值表

反證法可以用真值表嚟證明:因為如果「 」係(True;T)但係  (False;F)嘅,咁   嘅值只可能係假。

推論
      
T T T
T F F
F T T
F F T

簡單例子

要求

證明「如果   係一個單數,咁   都會係一個單數」。

證明

假設有個情況,   係一個單數,但係   係一個雙數

即係對應某啲   。計吓

 

好明顯呢個情況下   唔係一個雙數,所以同前提矛盾。所以   佢一定係個單數。「如果   係一個單數,咁   有可能係一個雙數」呢句嘢唔成立-「如果   係一個單數,咁   都會係一個單數」。

進階例子

要求

證明冇任何兩個正整數(Positive integer)  可以乎合   呢條式。呢個證明需要用到分類證明(Proof by exhaustion)。

證明

假設有兩個正整數   符合   呢條式。(假設)

利用  ,得知  

如果淨係睇整數  只可以係    嗰度嚟。

如果係  ,即係   

因此, 。(由假設推出個矛盾-因為唔可能有一個正整數係比一更細。)

如果係  ,即係   

因此, 。(又試由假設推出個矛盾:更冇可能,因為要求正整數。)

總括所有可能,個假設都係唔成立,所以一定唔存在  -冇任何兩個正整數可以乎合   呢條式。

係非有理數

要求

利用矛盾證明嚟證明「 非有理數(Irrational number;冇辦法用整數寫做分數嘅數字)。」

證明

假設   可以係個有理數(Rational number;可以用整數寫做分數嘅數字)。咁即係喺至少一個情況下  ,而    都係整數。

喺呢度,進一步假設   係已經約咗簡,費事有約數嘅撈絞。

 

由上面得出,  係雙數。

假設   係單數,利用簡單例子嘅定理,咁   一定係單數。(矛盾:因為   係雙數。)

所以,  係雙數,而且可以寫成    係某個整數。

 

利用上面,再總結得出   係雙數,而且可以寫成    係某個整數。

 

因為,假設   係已經約咗簡,所以唔可以有另一個  

所以   唔可以用整數寫做分數。

可以利用呢個步驟推出     質數,都唔係有理數

反證法嘅步驟

  1. 寫低要證明嘅命題。
  2. 再寫低頭先嗰句命題嘅相反,再假設呢句新命題係啱。
  3. 利用呢條假設,推斷啲野出嚟。
  4. 搵下有咩矛盾。
  5. 如果個假設引致矛盾,咁就可以話個假設係錯。咁嘅話個假設嘅相反-即係想證明嗰句命題-就會係啱。

更多例子

以下命題係可以用反證法嚟證明:

  •   嘅值係一定少過  
  • 對所以嘅整數   ,如果   係單數,咁    都係單數。

睇埋

參考

  • Beth, E. W. (1970). Proof by Contradiction. In Aspect of Modern Logic (pp. 30-41). Springer Netherlands.
  • Antonini, S., & Mariotti, M. A. (2006). Reasoning in an absurd world: difficulties with proof by contradiction. In Proceedings of the 30th PME Conference, Prague, Czech Republic (Vol. 2, pp. 65-72).