數學證明和數學/邏輯/邏輯等價原理

我們將介紹最後一個邏輯連線詞。

等價

再次，我們用其他連線詞來“定義”它，並驗證它與之前給出的定義相匹配。在這種情況下，我們取

($P$ 蘊含 $Q$) 並且 ($Q$ 蘊含 $P$)

作為

$P$ 當且僅當 $Q$ 的定義。

這個定義就是“當且僅當”表示式的由來，因為

$Q$ 蘊含 $P$

可以表述為 $P$ 如果 $Q$，並且

$P$ 蘊含 $Q$

可以表述為 $P$ 僅當 $Q$。

為了確認這與先前的定義相符，請注意 $P$ 蘊含 $Q$ 為假時，$P$ 為真，而 $Q$ 為假，同時 $Q$ 蘊含 $P$ 為假時，$Q$ 為真，而 $P$ 為假，因此表示式 ($P$ 蘊含 $Q$) 和 ($Q$ 蘊含 $P$) 只有當 $P$ 和 $Q$ 同時為真或同時為假時才為真。

將此定義與其他推理規則結合，我們可以得到以下結論

從 $P$ 蘊含 $Q$，$Q$ 蘊含 $P$ 推匯出 $P$ 當且僅當 $Q$.

如果假設不為 $P$，可以推匯出 $Q$，並且如果假設不為 $Q$，可以推匯出 $P$，那麼推匯出 $P$ 當且僅當 $Q$。

從 $P$，$P$ 當且僅當 $Q$ 推匯出 $Q$。

從 $Q$，$P$ 當且僅當 $Q$ 推匯出 $P$。

因此，您可以像使用蘊涵一樣使用等價關係，只是它雙向有效，而證明等價關係與證明蘊涵相同，只是您需要雙向進行。

示例證明#1

命題 1：$P$ 或 $Q$ 當且僅當 $Q$ 或 $P$

在這種情況下，我們已經有了 $P$ 或 $Q$ 意味著 $Q$ 或 $P$，如上一頁的命題 1。透過交換字母 $Q$ 和 $P$ 在命題中，我們得到 $Q$ 或 $P$ 意味著 $P$ 或 $Q$。因此，證明只是將這兩個先前結果組合在一起的問題。

行	陳述	證明
1	$P$ 或 $Q$ 意味著 $Q$ 或 $P$	上一頁的命題 1。
2	$Q$ 或 $P$ 意味著 $P$ 或 $Q$	同樣是上一頁的命題 1。
3	$Q$ 或 $P$ 當且僅當 $P$ 或 $Q$	來自 1 和 2

示例證明 #2

對於更復雜的示例，我們需要使用子證明。

命題 2： $P$ 或 $Q$ 當且僅當 ($P$ 蘊含 $Q$) 蘊含 $Q$

我們要證明兩個方向的蘊含，所以證明的結構看起來像這樣

行	陳述	證明
1	$P$ 或 $Q$	假設
(某些東西)
n	($P$ 蘊含 $Q$) 蘊含 $Q$	?
n+1	($P$ 蘊含 $Q$) 蘊含 $Q$	假設
(某些東西)
n+p	$P$ 或 $Q$	?
n+p+1	$P$ 或 $Q$ 當且僅當 ($P$ 蘊含 $Q$) 蘊含 $Q$	從 1 和 n，n+1 和 n+p

在這一點上，我們已經將證明分解成可以單獨處理的部分。在第一種情況下，我們需要證明一個蘊含，但這似乎比通常的做法更容易。在第二種情況下，我們需要證明一個析取，有兩種方法可以做到。看起來更容易的方法是假設不是 $P$ 並證明 $Q$。現在，我們已經有了幾種證明方法，可能有些方法比其他方法更簡單，但沒有足夠的經驗來體會這一點，你可能需要使用試錯法來找到最簡單的方法。不過請記住，當你看到書本或文章中的證明時，作者可能在找到有效的證明之前嘗試了很多失敗的嘗試，但你無法看到這些失敗。

填充更多結構，我們有

行	陳述	證明
1	$P$ 或 $Q$	假設
2	$P$ 蘊含 $Q$	假設
(某些東西)
n−1	$Q$	?
n	($P$ 蘊含 $Q$) 蘊含 $Q$	從 2 和 n−1
n+1	($P$ 蘊含 $Q$) 蘊含 $Q$	假設
n+2	不是 $P$	假設
(某些東西)
n+p−1	$Q$	?
n+p	$P$ 或 $Q$	從 n+2 和 n+p−1
n+p+1	$P$ 或 $Q$ 當且僅當 ($P$ 蘊含 $Q$) 蘊含 $Q$	從 1 和 n，n+1 和 n+p

(為了節省空間，我們同時構造證明的兩半；通常你一次只做一半。)

在前半部分，我們需要證明 $Q$，看起來最好的方法是使用反證法。在後半部分，我們已經從前面的頁面獲得了足夠的結果來填補其餘內容。像往常一樣，我們鼓勵你在檢視最終結果之前嘗試自己填補其餘內容。透過不同的方法，你甚至可能找到比給出的證明更簡單的證明。

行	陳述	證明
1	$P$ 或 $Q$	假設
2	$P$ 蘊含 $Q$	假設
3	非 $Q$	假設
4	$P$	從 1 和 3
5	不是 $P$	從 2 和 3
6	$False$	從 4 和 5
7	$Q$	從 3 和 6
8	($P$ 蘊含 $Q$) 蘊含 $Q$	從 2 和 7
9	($P$ 蘊含 $Q$) 蘊含 $Q$	假設
10	不是 $P$	假設
11	$P$ 蘊含 $Q$	關於間接證明頁面的命題 8。
12	$Q$	從 9 和 11
13	$P$ 或 $Q$	從 10 和 12
14	$P$ 或 $Q$ 當且僅當 ($P$ 蘊含 $Q$) 蘊含 $Q$	從 1 和 8，9 和 13

以散文形式，最好對語句進行標記，並清楚地標記正在證明哪個蘊含，以便讀者可以輕鬆地理解證明。

命題 2： $P$ 或 $Q$ 當且僅當 ($P$ 蘊含 $Q$) 蘊含 $Q$

Proof: We first prove that $P$ or $Q$ implies (($P$ implies $Q$) implies $Q$). Assume $P$ or $Q$. Now assume $P$ implies $Q$. We need to proof $Q$, so suppose not $Q$. Then $P$ by the first assumption and not $P$ by the second assumption. This is a contradiction so we have $Q$. Therefore ($P$ implies $Q$) implies $Q$. From the original assumption $P$ or $Q$ it follows that ($P$ implies $Q$) implies $Q$, so we can conclude that $P$ or $Q$ implies (($P$ implies $Q$) implies $Q$).

現在我們證明 (($P$ 蘊含 $Q$) 蘊含 $Q$) 蘊含 $P$ 或 $Q$。假設 ($P$ 蘊含 $Q$) 蘊含 $Q$。現在假設非 $P$。那麼 $P$ 蘊含 $Q$，因此 $Q$，所以 $P$ 或 $Q$。

留給讀者

我們現在已經涵蓋了幾乎所有常用的推理規則，所以現在可以證明的語句並不缺乏。以下是一些之前結果的相對簡單的擴充套件，一些需要一個或多個子證明，但由你來判斷哪個是哪個。

命題 3: ($P$ 或 $Q$) 或 $R$ 當且僅當 $P$ 或 ($Q$ 或 $R$)

命題 4: $P$ 且 $Q$ 當且僅當 $Q$ 且 $R$

命題 5: ($P$ 且 $Q$) 且 $R$ 當且僅當 $P$ 且 ($Q$ 且 $R$)

命題 6: ($P$ 且 $Q$) 或 $R$ 當且僅當 ($P$ 或 $R$) 且 ($Q$ 或 $R$)

命題 7: ($P$ 或 $Q$) 且 $R$ 當且僅當 ($P$ 且 $R$) 或 ($Q$ 且 $R$).

命題 8: ($P$ 當且僅當 $Q$) 蘊涵 ($Q$ 當且僅當 $P$)

命題 9: ($P$ 當且僅當 $Q$) 且 ($Q$ 當且僅當 $R$) 蘊涵 ($P$ 當且僅當 $R$)

命題 10: $P$ 蘊涵 $Q$ 當且僅當 非 $P$ 或 $Q$

命題 11: 非 ($P$ 蘊涵 $Q$) 當且僅當 $P$ 且 非 $Q$

命題 11: 非 ($P$ 或 $Q$) 當且僅當 非 $P$ 且 非 $Q$

命題 12: 非 ($P$ 且 $Q$) 當且僅當 非 $P$ 或 非 $Q$

命題 13: ($P$ 當且僅當 $Q$) 蘊涵 ($P$ 蘊涵 $R$) 當且僅當 ($Q$ 蘊涵 $R$)

命題 14: ($P$ 當且僅當 $Q$) 蘊含 ($R$ 蘊含 $P$ 當且僅當 $R$ 蘊含 $Q$)

命題 15: $P$ 當且僅當 非非 $P$

等價陳述組

在某些情況下，一個定理可能表明幾個陳述的組彼此等價。例如，定理的陳述可能以以下形式：

定理： 以下是等價的

1. 陳述 1

2. 陳述 2

3. 陳述 3

4. 陳述 4

這意味著陳述 1 當且僅當陳述 2，陳述 1 當且僅當陳述 3，... 陳述 3 當且僅當陳述 4，共 6 種可能的變體。證明這種定理的通常方法是證明一個迴圈中的蘊含關係。在這種情況下，您將證明：

P1: 陳述 1 蘊含陳述 2

P2: 陳述 2 蘊含陳述 3

P3: 陳述 3 蘊含陳述 4

P4: 陳述 4 蘊含陳述 1

這是非常有效的，因為透過證明僅僅四個蘊含關係，您實際上證明了四個陳述中的任意兩個之間的所有 12 種可能的蘊含關係。之所以能這樣做，是因為反覆應用了以下公式：

命題 13: ($P$ 蘊含 $Q$) 並且 ($Q$ 蘊含 $R$) 蘊含 ($P$ 蘊含 $R$)

證明：（這是對先前結果的簡單應用，留作練習。）

作為進一步的練習，證明以下結論：

P1 並且 P2 並且 P3 並且 P4 蘊含（陳述 1 當且僅當陳述 3）

替換

當兩個陳述在邏輯上等價時，它們具有相同的真值。因此，聲稱如果 $P$ 等價於 $Q$ 並且 $E(P)$ 是包含 $P$ 的表示式，則 $E(P)$ 等價於 $E(Q)$，其中 $E(Q)$ 是透過用 $Q$ 替換 $P$ 從 $E(P)$ 中獲得的。

作為此應用方式的示例，我們從上面第 15 條推論得知 $P$ 等價於非非 $P$。然後，我們希望得出結論：

非非 $P$ 蘊涵 $R$ 或 ($Q$ 當且僅當 $S$)

等價於

$P$ 蘊涵 $R$ 或 ($Q$ 當且僅當 $S$)

無需進行單獨的證明。

這是一個有效的結論，但證明它的工具屬於數學邏輯的範疇，超出了本書的範圍。然而，我們可以針對具體情況進行證明，一些示例表明瞭如何構建這些證明。如果表示式 $E(P)$ 僅涉及蘊涵和邏輯常數 $False$，那麼我們可以重複應用上面第 13 和 14 條推論。

例如，如果 $E(P)$ 是

$Q$ 蘊涵 ($P$ 蘊涵 $R$)

那麼我們可以證明

$Q$ 蘊涵 ($P$ 蘊涵 $R$)

等價於

$Q$ 蘊涵 (非非 $P$ 蘊涵 $R$)

如下所示

非非 $P$ 等價於 $P$ (根據命題 15)

非非 $P$ 蘊涵 $R$ 等價於 $P$ 蘊涵 $R$ (根據命題 13)

$Q$ 蘊涵 (非非 $P$ 蘊涵 $R$) 等價於 $Q$ 蘊涵 ($P$ 蘊涵 $R$) (根據命題 14)

對於涉及其他邏輯連線詞的表示式，我們可以使用我們根據蘊涵給出的定義，將表示式轉換為之前型別中的一個表示式。