數學證明和數學原理/邏輯/使用合取和析取的證明

我們已經瞭解了直接證明和間接證明，但到目前為止，我們還沒有討論合取和析取的推理規則。我們將在否定中定義這些，就像我們之前對否定的定義一樣。

析取

我們把非 $P$ 蘊含 $Q$ 作為 $P$ 或 $Q$ 的定義。

首先我們必須確保這與我們之前對 $P$ 或 $Q$ 的定義一致。根據那個定義，$P$ 或 $Q$ 僅在 $P$ 為假且 $Q$ 為假時才為假。但非 $P$ 蘊含 $Q$ 僅在非 $P$ 為真時，換句話說，$P$ 為假，且 $Q$ 為假時才為假。

我們可以透過將此定義與蘊含的推理規則結合，將此定義轉化為兩個新的推理規則。

如果透過假設非 $P$ 可以推匯出 $Q$，然後推匯出 $P$ 或 $Q$.

從非 $P$，$P$ 或 $Q$ 推斷 $Q$。

例證證明 #1

讓我們應用這些來證明關於析取的一個基本事實。

命題 1： $P$ 或 $Q$ 蘊含 $Q$ 或 $P$。

和之前一樣，我們先建立一個基本框架。

行	陳述	理由
1	$P$ 或 $Q$	假設
(某事)
n	$Q$ 或 $P$	?
n+1	$P$ 或 $Q$ 蘊含 $Q$ 或 $P$	從 1 和 n

從定義中引出的第一個推理規則來看，證明析取的方法是假設第一個陳述的否定並推匯出第二個陳述。另外，第二個規則給了我們一種使用假設的方法。將此新增到證明中

行	陳述	理由
1	$P$ 或 $Q$	假設
2	非 $P$ 蘊含 $Q$	從 1
3	非 $Q$	假設
(某事)
n−1	$P$	?
n	$Q$ 或 $P$	從 2 和 n−1
n+1	$P$ 或 $Q$ 蘊含 $Q$ 或 $P$	從 1 和 n

現在我們需要將非 $P$ 蘊含 $Q$ 與非 $Q$ 組合起來，但前一頁有幾種組合蘊含和否定的方法。最有用的是命題 4，由此可以完成證明的其餘部分。

行	陳述	理由
1	$P$ 或 $Q$	假設
2	非 $P$ 蘊含 $Q$	從 1
3	非 $Q$	假設
4	非 $Q$ 意味著非非 $P$	根據上一頁的命題 4 應用於 2。
5	非非 $P$	根據 3 和 4
6	$P$	根據 5
7	$Q$ 或 $P$	根據 2 和 6
8	$P$ 或 $Q$ 蘊含 $Q$ 或 $P$	根據 1 和 7

用散文形式表達

命題 1: $P$ 或 $Q$ 意味著 $Q$ 或 $P$

證明：假設 $P$ 或 $Q$。這意味著非 $P$ 蘊含 $Q$。現在假設非 $Q$。從上一頁的命題 4 我們有非 $Q$ 蘊含 非非 $P$，因此非非 $P$，所以 $P$。因此 $Q$ 或 $Q$。從原始假設 $P$ 或 $Q$ 可以得出 $Q$ 蘊含 $P$，因此我們可以得出結論，$P$ 或 $Q$ 蘊含 $Q$ 或 $P$。

將此命題與定義中的推理規則結合，我們得到另外兩個

如果假設不成立$Q$，可以推匯出$P$，然後推匯出$P$ 或 $Q$。

從不成立$Q$，$P$ 或 $Q$ 推匯出$P$。

留給讀者（析取）

命題 2: $P$ 蘊含 $P$ 或 $Q$。

命題 3: $Q$ 蘊含 $P$ 或 $Q$。

命題 4: 不成立（$P$ 或 $Q$）蘊含不成立 $P$。

命題 5: 不成立（$P$ 或 $Q$）蘊含不成立 $Q$。

命題 6: ($P$ 或 $Q$) 或 $R$ 蘊含 $P$ 或 ($Q$ 或 $R$).

合取

我們對合取的定義比對析取的定義更復雜。具體來說，我們把語句非（非 $P$ 或 非 $Q$) 定義為 $P$ 與 $Q$ 的定義。

同樣，我們需要確保這個定義與之前給出的定義一致。語句 $P$ 與 $Q$ 為真，當且僅當 $P$ 為真且 $Q$ 為真。另一方面，語句非（非 $P$ 或 非 $Q$) 為真，當且僅當 非 $P$ 或 非 $Q$ 為假。這等同於說非 $P$ 為假且非 $Q$ 為假，這等同於說 $P$ 為真且 $Q$ 為真，這與之前的定義相符。

這個定義在生成推理規則方面相當繁瑣，但它意味著一些可以替代使用的其他語句。我們只給出證明的提示，並將細節留給讀者補充。

命題 7: $P$ 和 $Q$ 蘊含 $P$.

(應用定義和命題 4.)

這產生推理規則

從 $P$ 和 $Q$ 推匯出 $P$.

命題 8: $P$ 和 $Q$ 蘊含 $Q$.

(應用定義和命題 5.)

這產生推理規則

從 $P$ 和 $Q$ 推匯出 $Q$.

命題 9: $P$ 蘊含 ($Q$ 蘊含 $P$ 和 $Q$.

(為了證明 $P$ 和 $Q$, 假設非 $P$ 或者 非 $Q$, 然後推匯出矛盾.)

這產生推理規則

從 $P$, $Q$ 推匯出 $P$ 和 $Q$.

連線詞在列出陳述所需的多項假設時非常有用，例如 $P$ 和 $Q$ 意味著 $R$。到目前為止，我們一直使用 $P$ 意味著 ($Q$ 意味著 $R$) 來做到這一點。我們留給讀者證明 

命題 10：($P$ 意味著 ($Q$ 意味著 $R$)) 意味著 ($P$ 和 $Q$ 意味著 $R$).

和

命題 11：($P$ 和 $Q$ 意味著 $R$) 意味著 ($P$ 意味著 ($Q$ 意味著 $R$)).

留給讀者（連線詞）

命題 12：$P$ 和 $Q$ 意味著 $Q$ 和 $P$.

命題 13： ($P$ 和 $Q$) 並且 $R$ 蘊含 $P$ 並且 ($Q$ 並且 $R$).

命題 14： ($P$ 和 $Q$) 或 $R$ 蘊含 ($P$ 或 $R$) 並且 ($Q$ 或 $R$).

命題 15： ($P$ 或 $R$) 並且 ($Q$ 或 $R$) 蘊含 ($P$ 並且 $Q$) 或 $R$.

命題 16: ($P$ 或 $Q$) 且 $R$ 蘊涵 ($P$ 且 $R$) 或 ($Q$ 且 $R$).

命題 17: ($P$ 且 $R$) 或 ($Q$ 且 $R$) 蘊涵 ($P$ 或 $Q$) 且 $R$.

情況證明

這是一種重要的證明方法，雖然它只是我們已經見過的證明方法的應用。其思想是，當你試圖證明一個陳述 $R$ 時，有時如果有假設可以利用，就會更容易。換句話說，證明 $P$ 蘊涵 $R$ 比直接證明 $R$ 更容易。假設你已經證明了 $P$ 或 $Q$。如果你能證明 $P$ 蘊涵 $R$，然後證明 $Q$ 蘊涵 $R$，那麼 $R$ 似乎就隨之得證了。

在證明中，這可能類似這樣表達:

我們有 $P$ 或 $Q$

情況一: $P$

(某事)

$R$

情況二: $Q$

(某事)

$R$

所以 $R$.

將這個想法寫成一個命題，得到

命題 18: ($P$ 或 $Q$) 且 (($P$ 蘊涵 $R$) 且 ($Q$ 蘊涵 $R$)) 蘊涵 $R$

我們可以使用其他推理規則來證明這一點。這留作間接證明的練習。

將此作為推理規則來表述

如果透過假設$P$可以推匯出$R$，並且透過假設$Q$可以推匯出$R$，並且$P$或$Q$，$R$.

作為一個練習，應用這條推理規則來構造命題 14 到 17 的更簡單的證明。