對位證明法[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),而他們符合
和
。證明如果
,則
。
證明:
如果用直接證明,會很麻煩。但是,如果利用對立證明,即假設
則會簡單得多。
因為
,而
,所以
。
這樣
一定成立。
更多例子
以下命題都可以用對立證明證真:
- 假設
都是自然數。如果
是單數,則
和
都是單數。
- 假設
都是實數。如果
是無理數,則
或者
是無理數。
參見
參考
- ^ 【学习笔记】离散数学(Discrete Math) - 证明 Proof 3. blog.csdn.net. [2021-11-18]. (原始內容存檔於2021-11-18).
- ^ 反證法與逆否命題法. 線代啟示錄. 2016-03-17 [2021-11-18]. (原始內容存檔於2021-11-18) (英語).
- ^ 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