形式邏輯/命題邏輯/替換和互換

← 命題聯結詞的性質

↑ 命題邏輯

翻譯 →

替換和互換

本頁面將使用在形式語法附加術語部分介紹的出現和子公式的概念。這些概念自從那時以來很少使用，因此你可能想回顧一下它們。

替換

重言式形式

我們已經介紹了一些重言式，其中一個例子是

(1)    $\mathrm {Q} \rightarrow (\mathrm {P} \rightarrow \mathrm {Q} )\,\!$

使用元變數$\psi$和$\varphi$來替換(1)中的$\mathrm {Q}$和$\mathrm {R}$。這將產生以下形式

(2)    $\psi \rightarrow (\varphi \rightarrow \psi )\,\!$

事實證明，任何與這種形式匹配的公式都是一個重言式。因此，例如，設$\psi =\mathrm {R} \land \mathrm {S}$和$\varphi =\mathrm {P} \lor \mathrm {Q}$。然後，

(3)    $\mathrm {R} \land \mathrm {S} \rightarrow (\mathrm {P} \lor \mathrm {Q} \rightarrow \mathrm {R} \land \mathrm {S} )\,\!$

是一個重言式。這個過程可以推廣到所有重言式：對於任何重言式，透過用不同的元變數（如(2)中所示的希臘字母）替換每個句子字母來找到它的顯式形式。我們可以稱之為重言式形式，它是一個元邏輯表示式，而不是一個公式。這種重言式形式的任何例項都是一個重言式。

替換例項

前面已經說明了如何透過重言式形式從舊的重言式中生成新的重言式。這裡，我們將展示如何在不訴諸重言式形式的情況下生成重言式。為此，我們定義一個公式的替換例項。任何重言式的替換例項也是一個重言式。

首先，我們定義一個公式對句子字母的簡單替換例項。設 $\varphi \,\!$ 和 $\psi \,\!$ 是公式，$\pi \,\!$ 是一個句子字母。簡單替換例項 $\varphi [\pi /\psi ]\,\!$ 是將 $\varphi \,\!$ 中所有出現的 $\pi \,\!$ 替換為一個出現的 $\psi \,\!$ 所得到的結果。對句子字母的公式替換例項 是簡單替換例項鏈的結果。特別是，從 $\varphi \,\!$ 開始的零個簡單替換例項鏈是一個替換例項，實際上就是 $\varphi \,\!$ 本身。因此，任何公式都是它自身的替換例項。

事實證明，如果 $\varphi \,\!$ 是一個重言式，那麼任何簡單替換例項 $\varphi [\pi /\psi ]\,\!$ 也是一個重言式。如果我們從一個重言式開始，生成一個簡單替換例項鏈，那麼鏈中的每個公式也是一個重言式。因此，任何（不一定是簡單的）重言式的替換例項也是一個重言式。

替換示例

再次考慮 (1)。我們將 $\mathrm {R} \land \mathrm {S} \,\!$ 替換為 (1) 中每個出現的 $\mathrm {Q} \,\!$。這給了我們 (1) 的以下簡單替換例項

(4)    $\mathrm {R} \land \mathrm {S} \rightarrow (\mathrm {P} \rightarrow \mathrm {R} \land \mathrm {S} )\,\!$

在本例中，我們將 $\mathrm {P} \lor \mathrm {Q} \,\!$ 代替 $\mathrm {P} \,\!$。這使得 (3) 成為 (4) 的一個簡單替換例項。由於 (3) 是兩個簡單替換例項鏈的結果，因此它是 (1) 的一個（非簡單）替換例項。由於 (1) 是一個永真式，因此 (3) 也是一個永真式。我們可以將替換連結串列示為

$\mathrm {Q} \rightarrow (\mathrm {P} \rightarrow \mathrm {Q} )[\mathrm {Q} /\mathrm {R} \land \mathrm {S} ][\mathrm {P} /\mathrm {P} \lor \mathrm {Q} ]\,\!$

再舉一個例子，同樣從 (1) 開始。我們想要得到

(5)    $\mathrm {P} \rightarrow (\mathrm {Q} \rightarrow \mathrm {P} )\,\!$

我們第一次嘗試可能是將 $\mathrm {P} \,\!$ 代替 $\mathrm {Q} \,\!$，

(6)    $\mathrm {P} \rightarrow (\mathrm {P} \rightarrow \mathrm {P} )\,\!$

這確實是一個永真式，但它不是我們想要的那個。相反，我們將 $\mathrm {R} \,\!$ 代替 $\mathrm {P} \,\!$ 在 (1) 中，得到

$\mathrm {Q} \rightarrow (\mathrm {R} \rightarrow \mathrm {Q} )\,\!$

現在將 $\mathrm {P} \,\!$ 代替 $\mathrm {Q} \,\!$，得到

$\mathrm {P} \rightarrow (\mathrm {R} \rightarrow \mathrm {P} )\,\!$

最後，用 $\mathrm {Q} \,\!$ 替換 $\mathrm {R} \,\!$，我們得到了我們想要的結果，即 (5)。由於 (1) 是一個重言式，所以 (5) 也是一個重言式。我們可以將替換連結串列示為

$\mathrm {Q} \rightarrow (\mathrm {P} \rightarrow \mathrm {Q} )[\mathrm {P} /\mathrm {R} ][\mathrm {Q} /\mathrm {P} ][\mathrm {R} /\mathrm {Q} ]\!$

同時替換

我們可以將一系列簡單替換壓縮成一個複雜的替換。設 $\varphi \,\!$，$\psi _{1}\,\!$，$\psi _{2}\,\!$，... 是公式；設 $\pi _{1}\,\!$，$\pi _{2}\,\!$，... 是句子字母。我們定義 _對句子字母的公式的**同時替換例項**_ $\varphi [\pi _{1}/\psi _{1},\ \pi _{2}/\psi _{2},\ ...]\,\!$ 為從 $\varphi \,\!$ 開始，並同時用 $\psi _{1}\,\!$ 替換 $\pi _{1}\,\!$，用 $\psi _{2}\,\!$ 替換 $\pi _{2}\,\!$，.... 我們可以重新生成我們的示例。

之前生成的公式 (3) 為

$\mathrm {Q} \rightarrow (\mathrm {P} \rightarrow \mathrm {Q} )[\mathrm {P} /\mathrm {P} \lor \mathrm {Q} ,\mathrm {Q} /\mathrm {R} \land \mathrm {S} ]\,\!$

類似地，(5) 為

$\mathrm {Q} \rightarrow (\mathrm {P} \rightarrow \mathrm {Q} )[\mathrm {P} /\mathrm {Q} ,\ \mathrm {Q} /\mathrm {P} ]\,\!$

最後（6）是

$\mathrm {Q} \rightarrow (\mathrm {P} \rightarrow \mathrm {Q} )[\mathrm {Q} /\mathrm {P} ]\,\!$

當我們進入謂詞邏輯時，將不再可以使用同時替換例項。這就是為什麼我們透過參考一系列簡單替換例項來定義替換例項，而不是作為同時替換例項。

互換

等效子公式的互換

我們之前在命題連線詞的性質中看到了以下等價性

(7)    $\mathrm {P} \,\!$       $\lnot \lnot \mathrm {P} \,\!$

然後你可能會期待以下等價性

$\mathrm {P} \rightarrow \mathrm {Q} \land \mathrm {R} \,\!$       $\lnot \lnot (\mathrm {P} \rightarrow \mathrm {Q} \land \mathrm {R} )\,\!$

這個期望是正確的；這兩個公式是等價的。令 $\varphi \,\!$ 和 $\psi \,\!$ 是等價的公式。令 $\chi _{1}\,\!$ 是一個公式，其中 $\varphi \,\!$ 作為子公式出現。最後，令 $\chi _{2}\,\!$ 是在 $\chi \,\!$ 中至少用一次（不一定是全部） $\varphi \,\!$ 替換 $\psi \,\!$ 所得到的結果。那麼 $\chi _{1}\,\!$ 和 $\chi _{2}\,\!$ 是等價的。這種替換被稱為替換。

舉個例子，假設我們想要生成等價性

(8)    $\mathrm {P} \rightarrow \mathrm {Q} \land \mathrm {R} \,\!$       $\mathrm {P} \rightarrow \lnot \lnot (\mathrm {Q} \land \mathrm {R} )\,\!$

我們注意到以下等價性

(9)    $\mathrm {Q} \land \mathrm {R} \,\!$       $\lnot \lnot (\mathrm {Q} \land \mathrm {R} )\,\!$

這兩個公式可以透過真值表來確認是等價的，或者更簡單的方法是，在 (7) 的兩個公式中用 $\mathrm {Q} \land \mathrm {R} \,\!$ 替換 $\mathrm {P} \,\!$。

這種替換確實將 (9) 建立為等價。我們已經注意到 $\varphi \,\!$ 和 $\psi \,\!$ 等價當且僅當 $\varphi \leftrightarrow \psi \,\!$ 是重言式。根據 (7)，我們得到重言式

$\mathrm {P} \leftrightarrow \lnot \lnot \mathrm {P} \,\!$

然後我們的替換得到

$\mathrm {Q} \land \mathrm {R} \leftrightarrow \lnot \lnot (\mathrm {Q} \land \mathrm {R} )\,\!$

這也是一個重言式。相應的等價式就是 (9)。

基於 (9)，我們現在可以將 $\mathrm {P} \rightarrow \mathrm {Q} \land \mathrm {R} \,\!$ 的後件替換為等價式。這將生成我們需要的等價式，即 (8)。

每個等價於重言式的公式也是重言式。因此，在重言式中交換等價子公式會導致重言式。例如，我們可以使用 (7) 的替換例項

$\mathrm {Q} \,\!$       $\lnot \lnot \mathrm {Q} \,\!$

以及之前在 命題連線詞性質 中看到的重言式

$(\mathrm {P} \rightarrow \mathrm {Q} )\lor (\mathrm {Q} \rightarrow \mathrm {R} )\,\!$

得到

$(\mathrm {P} \rightarrow \lnot \lnot \mathrm {Q} )\lor (\mathrm {Q} \rightarrow \mathrm {R} )\,\!$

作為一個新的重言式。

交換示例

例如，我們將使用 連線詞的可互定義性 來表達

(10)    $\mathrm {P} \leftrightarrow \mathrm {Q} \lor \mathrm {R} \,\!$

只使用條件語句和否定。

基於

$\mathrm {P} \lor \mathrm {Q} \,\!$       $\lnot \mathrm {P} \rightarrow \mathrm {Q} \,\!$

我們得到替換例項

$\mathrm {Q} \lor \mathrm {R} \,\!$       $\lnot \mathrm {Q} \rightarrow \mathrm {R} \,\!$

這反過來讓我們能夠替換(10)中相應的子公式，得到

(11)    $\mathrm {P} \leftrightarrow \lnot \mathrm {Q} \rightarrow \mathrm {R} \,\!$

等價

$\mathrm {P} \leftrightarrow \mathrm {Q} \,\!$ $(\mathrm {P} \rightarrow \mathrm {Q} )\land (\mathrm {Q} \rightarrow \mathrm {P} )\,\!$

以及相應的替換，為我們提供了

(12)    $(\mathrm {P} \rightarrow (\lnot \mathrm {Q} \rightarrow \mathrm {R} ))\land ((\lnot \mathrm {Q} \rightarrow \mathrm {R} )\rightarrow \mathrm {P} )\,\!$

與(11)等價。

最後，應用

$\mathrm {P} \land \mathrm {Q} \,\!$       $\lnot (\mathrm {P} \rightarrow \lnot \mathrm {Q} )\,\!$

以及相應的替換，產生了我們的最終結果

$\lnot (\mathrm {P} \rightarrow (\lnot \mathrm {Q} \rightarrow \mathrm {R} )\rightarrow \lnot ((\lnot \mathrm {Q} \rightarrow \mathrm {R} )\rightarrow \mathrm {P} ))\,\!$

摘要

本頁介紹了兩個論點。

• 重言式的替換例項也是重言式。

• 給定一個公式，用等價的子公式替換子公式的結果是一個等價於給定公式的公式。

這些論點並非微不足道的觀察結果，也非簡單真值表的結論。它們是需要證明的實質性論點。許多標準元邏輯教科書中提供了證明，但此處未給出。

← 命題聯結詞的性質

↑ 命題邏輯

翻譯 →