數學證明和數學/邏輯/間接證明原理

在上一節中，我們研究了與蘊涵相關的推理規則。大多數數學定理都採用蘊涵的形式，因此這些規則非常重要。（從某種意義上說，所有數學定理都採用蘊涵的形式，但我們稍後會討論這一點。）

但邏輯不僅僅是蘊涵，所以我們需要一些額外的推理規則來處理其他邏輯連線詞。其中最基本的是反證法。

矛盾

我們首先介紹矛盾的概念。你可以把它想象成一個已知為假的陳述。具有諷刺意味的是，這樣的陳述在邏輯中起著重要的作用，邏輯的目的是證明某些陳述總是正確的。

有幾個邏輯符號表示矛盾；其中一個是 $\bot$，在這種情況下，始終為真的陳述的符號是 $\top$。也許 $\top$ 是因為它與字母“T”（表示 True）相似，將其倒置意味著相反。另一個符號是 $\Box$，在這種情況下，符號 $\blacksquare$ 代表始終為真的陳述。由於我們大多數情況下避免使用這些符號，因此我們將簡單地用文字拼寫出 $False$ 來表示表格格式的證明。對於以散文形式給出的證明，通常會寫類似“這是荒謬的”或“這是一個矛盾”之類的話。單詞“矛盾”本身來自拉丁語短語，意思是“反對”，指的是彼此含義相反的語句。

否定

可以使用蘊涵和矛盾來“定義”所有剩餘的邏輯連線詞。首先，我們可以取語句

$P$ 蘊涵 $False$

作為

非 $P$ 的定義。

我們已經在邏輯連線詞部分給出了“非 $P$”的定義，現在我們建立了一個新的、競爭的定義。只要我們可以確信這兩個定義相互一致，這就沒有問題。因此，我們需要確信語句

$P$ 蘊涵 $False$

當 $P$ 為真時，結果為假，當 $P$ 為假時，結果為真。但是語句 $P$ 蘊含 $Q$ 的定義是當 $P$ 為真時，結果為假，當 $P$ 為假且 $Q$ 為假時，結果為真。因此定義是吻合的。

給定這樣的定義，我們可以建立兩個新的推理規則。第一個用定義替換定義的表示式，第二個進行相反的替換。所以我們有

從非 $P$ 推匯出 $P$ 蘊含 $False$

和

從 $P$ 蘊含 $False$ 推匯出非 $P$.

透過將這些規則與上一頁的規則結合起來，我們得到了更實用的形式

從 $P$，非 $P$ 推匯出 $False$

和

如果透過假設 $P$ 可以推匯出 $False$，那麼推匯出非 $P$.

示例證明 #1

讓我們首先使用上述規則來證明

命題 1: $P$ 蘊含非非 $P$.

這是一個蘊含關係，因此我們從假設前提開始，推匯出結論。所以證明的結構如下：

行	語句	理由
1	$P$	前提
(某個東西)
n	非非 $P$	?
n+1	$P$ 蘊含非非 $P$	由 1 和 n 推出

現在的目標是證明非非 $P$，但我們可以透過假設非 $P$ 並推匯出矛盾來實現。證明的新形式是

行	語句	理由
1	$P$	前提
2	非 $P$	前提
(某個東西)
n−1	$False$	?
n	非非 $P$	由 2 和 n−1 推出
n+1	$P$ 蘊含非非 $P$	由 1 和 n 推出

現在我們需要證明 $False$，但語句 $P$ 和 非 $P$ 已經被假設，所以只需要進行最後的填充即可。

行	語句	理由
1	$P$	前提
2	非 $P$	前提
3	$P$	重複 1
4	$False$	2 和 3 之間的矛盾
5	非非 $P$	由 2 和 4 推出
6	$P$ 蘊含非非 $P$	由 1 和 5 推出

用散文形式表達

命題 1: $P$ 蘊含非非 $P$.

證明： 假設 $P$。現在假設不 $P$。根據原始假設，我們同時擁有不 $P$ 和 $P$，這是一個矛盾。所以假設不 $P$ 一定是假的，換句話說，不是不 $P$。從原始假設 $P$ 可以得出，不是不 $P$，因此我們可以得出結論 $P$ 蘊含不是不 $P$。

示例證明 #2

我們證明

命題 2： ($P$ 蘊含 $Q$) 蘊含 (不 $Q$ 蘊含不 $P$）。

對於任何蘊含 $P$ 蘊含 $Q$，蘊含不 $Q$ 蘊含不 $P$ 被稱為其“逆否命題”。正如我們將看到的，逆否命題在邏輯上等價於原始蘊含，這與逆命題不同。命題 2 是證明該等價性的第一步。

你可以從頭開始證明，這留作練習，但另一種方法是使用上一頁的命題 5 作為捷徑。改寫為推理規則，該命題指出

從 $P$ 蘊含 $Q$ 推匯出 ($Q$ 蘊含 $R$) 蘊含 ($P$ 蘊含 $R$）。

這產生了一個更簡單的證明

行	語句	理由
1	$P$ 意味著 $Q$	前提
2	非 $Q$	前提
3	$Q$ 意味著 $False$	“非”的定義
4	$P$ 意味著 $Q$	重複 1
5	($Q$ 意味著 $False$) 意味著 ($P$ 意味著 $False$).	上一頁命題5
6	$P$ 蘊涵 $False$	從3和5得出
7	非 $P$	“非”的定義
8	非 $Q$ 意味著 非 $P$	從2和7得出
9	($P$ 意味著 $Q$) 意味著 (非 $Q$ 意味著 非 $P$).	從1和8得出

間接證明方法

我們幾乎得到了一種非常有用和重要的證明方法，稱為反證法，或者對於喜歡拉丁語的人來說，稱為Reductio ad absurdum，大致翻譯成歸謬法。使用這種方法的證明被稱為間接證明，因為它不像所謂的直接證明那麼直接，直接證明依賴於目前為止使用的方法。

為了使用這種方法來證明一個命題 $P$，假設它是假的，然後推匯出矛盾。如果假設一個命題是假的會導致不可能的結果，那麼這個命題就必須是非假的，即為真的。換句話說，如果假設非 $P$ 你可以推匯出矛盾，也就是說，如果非非 $P$，那麼你可以推匯出 $P$.

我們將以新的推論規則的形式重新說明這一點

從非非 $P$ 推匯出 $P$.

另一種說法是

如果假設不為 $P$，可以推匯出 $False$，那麼可以推匯出 $P$.

這是最後一個推論規則，無法從定義或其他推論規則中推匯出。我們將像對否定一樣定義析取、合取和等價，這些定義會產生兩個推論規則，但可以透過像上一頁中的命題 2 一樣證明蘊涵來推匯出。

示例證明 #3 和 #4

為了使這個推論規則發揮作用，讓我們從命題 1 的逆命題開始

命題 3: 不不 $P$ 蘊涵 $P$.

這很容易推匯出，證明留作練習。

命題 4: (不 $Q$ 蘊涵 不 $P$) 蘊涵 ($P$ 蘊涵 $Q$)

從構建一個輪廓開始，就像之前一樣。

行	語句	理由
1	非 $Q$ 意味著 非 $P$	前提
2	$P$	前提
(某個東西)
n−1	$Q$	?
n	$P$ 意味著 $Q$	由 2 和 n−1 推出
n+1	(不 $Q$ 蘊涵 不 $P$) 蘊涵 ($P$ 蘊涵 $Q$)	由 1 和 n 推出

此時我們需要證明 $Q$，但直接證明似乎行不通，所以假設不為 $Q$ 並嘗試推匯出矛盾。

行	語句	理由
1	非 $Q$ 意味著 非 $P$	前提
2	$P$	前提
3	非 $Q$	前提
(某個東西)
n−2	$False$	?
n−1	$Q$	從 3 和 n−2
n	$P$ 意味著 $Q$	由 2 和 n−1 推出
n+1	(不 $Q$ 蘊涵 不 $P$) 蘊涵 ($P$ 蘊涵 $Q$)	由 1 和 n 推出

我們現在有足夠的假設來開始填充一些推理並完成證明。

行	語句	理由
1	非 $Q$ 意味著 非 $P$	前提
2	$P$	前提
3	非 $Q$	前提
4	非 $Q$ 意味著 非 $P$	重複 1
5	非 $P$	從 3 和 4
6	$P$	迭代 2
7	$False$	從 5 和 6
8	$Q$	從 3 和 7
9	$P$ 意味著 $Q$	從 2 和 8
10	(不 $Q$ 蘊涵 不 $P$) 蘊涵 ($P$ 蘊涵 $Q$)	從 1 和 9

用散文形式表達

命題 4: (不 $Q$ 蘊涵 不 $P$) 蘊涵 ($P$ 蘊涵 $Q$)

證明： 假設並非 $Q$ 蘊涵並非 $P$。現在假設 $P$。我們需要證明 $Q$，所以假設並非如此，換句話說，並非 $Q$。那麼根據第一個假設，並非 $P$。但這與第二個假設相矛盾。假設並非 $Q$ 導致了矛盾，所以 $Q$。因此，$P$ 蘊涵 $Q$。從最初的假設並非 $Q$ 蘊涵並非 $P$，可以得出結論： (並非 $Q$ 蘊涵並非 $P$) 蘊涵 ($P$ 蘊涵 $Q$)。

注意，雖然這不是嚴格必要的，但我們陳述了接下來要證明的內容，並以“假設並非如此”的形式插入了一個小小的路標，以表明接下來將使用間接論證。其他具有相同目的的短語可能包括“假設並非”和“如果錯誤，那麼”。

留給讀者

命題 5：並非 ($P$ 蘊涵 $Q$) 蘊涵並非 $Q$

命題 6：並非 ($P$ 蘊涵 $Q$) 蘊涵 $P$

命題 7: (($P$ 蘊含 $Q$) 蘊含 $P$) 蘊含 $P$

命題 8: 非 $P$ 蘊含 ($P$ 蘊含 $Q$)

命題 9: $False$ 蘊含 $Q$

命題 10: 非 $False$