對位證明法[1](英語:proof by contrapositive,又或者proof by negation),或稱否定證明法逆否命題法[2],是邏輯數學的其中一個證明方法。其與反證法相似,但是是不同的概念。根據邏輯,「」等於「」,即取其逆否命題[3]

需要注意,對位證明法與反證法不同。

定義

編輯

給予給予初始實質條件命題「若P,則Q」: ,對位證明法證明其邏輯等價的逆否命題「若非Q,則非P」: 的真值。

邏輯上,對立證明法的可用性可以以比較逆否命題和原命題的真值表證明,即證明  的真值完全一樣:

           
T T F F T T
T F F T F F
F T T F T T
F F T T T T

例子

編輯
  • 「我的媽媽是女人。」需要證明的逆否命題是「不是女人就不是我的媽媽。」
  • 「若 是單數,則 是雙數。」需要證明的逆否命題是「若 不是雙數,則 不是單數。」

反證法與對立證明的分別

編輯

反證法:假設   正確, ,發現   不對,於是證明   正確。

否定證明:證明   正確,於是轉換證明   正確。

證明例子

編輯

證明「假設   是雙數,則  都會是雙數。」

證明:

逆否命題:「假設   不是雙數,則   也不是雙數。」

換句話講,即係「假設   是單數,則   也是單數。」

因為   是單數,所以   是整數。

 

因為   是整數,所以   是單數。

集合論例子

編輯

如果   都是set),而他們符合   。證明如果  ,則  

證明

如果用直接證明,會很麻煩。但是,如果利用對立證明,即假設  則會簡單得多。

因為  ,而  ,所以  

這樣   一定成立。

更多例子

編輯

以下命題都可以用對立證明證真:

  • 假設   都是自然數。如果  單數,則    都是單數。
  • 假設   都是實數。如果  無理數,則   或者   是無理數。

參見

編輯

參考

編輯
  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