形式邏輯/命題邏輯/子推導和放縮規則

← 構造一個簡單推導

↑ 命題邏輯

構造一個複雜推導 →

子推導和放縮規則

如前所述，我們需要三個額外的推理規則：條件引入 (CI)、否定引入 (NI) 和否定消去 (NE)。這些規則需要子推導。

推導條件語句

示例推導

我們從一個示例推導開始，它說明了條件引入，然後進行解釋。一個推匯出以下論證的推導：

$\mathrm {Q} \land \mathrm {R} \!$   ∴   $\mathrm {P} \rightarrow \mathrm {Q}$

如下所示

1.   $\mathrm {Q} \land \mathrm {R} \,\!$   前提   2.     $\mathrm {P} \,\!$   假設 3.     $\mathrm {Q} \,\!$   1 KE   4.   $\mathrm {P} \rightarrow \mathrm {Q} \,\!$   2–3 CI

第 2 行和第 3 行構成了一個子推導。它從假設所需公式的前件開始，以推匯出所需公式的後件結束。在行號和公式之間有兩個垂直分隔符，將它與推導的其餘部分隔開，並指示它的從屬地位。第 2 行下面有一個水平分隔符，將假設與子推導的其餘部分隔開。第 4 行是條件引入的應用。它不是來自一兩行，而是來自整個子推導（第 2 行到第 3 行）整體。

條件引入是一個放縮規則。它放縮（使無效）該假設，實際上使整個子推導無效。一旦應用放縮規則，子推導中的任何行（這裡，第 2 行和第 3 行）都不能在推導中進一步使用。

條件引入規則

要推匯出公式 $(\varphi \rightarrow \psi )\,\!$，條件引入 (CI) 規則透過首先在子推導中假設前件 $\varphi$ 為真，然後推匯出 $\psi$ 作為子推導的結論而應用。符號上，CI 寫作

${\underline {{\text{Assume }}\varphi {\text{, derive }}\psi }}$

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

這裡，後續行不是從一個或多個前件行推斷出來的，而是從整個子推導中推斷出來的。註釋是子推導所佔行的範圍和縮寫 CI。與之前介紹的推理規則不同，條件引入不能透過真值表來證明。而是由在命題聯結詞性質中介紹的演繹原理來證明。我們假設$\varphi$以推匯出$(\varphi \rightarrow \psi )\,\!$背後的直覺是，如果$\varphi$為假，則根據定義$(\varphi \rightarrow \psi )\,\!$為真。因此，如果我們證明了每當$\varphi$碰巧為真時，$\psi$為真，那麼$(\varphi \rightarrow \psi )\,\!$必須為真。

請注意，前件子推導可以包含一個單行，該行既作為假設的$\varphi \,\!$，也作為推匯出的$\psi \,\!$，如下面的推導所示

∴   $\mathrm {P} \rightarrow \mathrm {P} ,$

1.     $\mathrm {P} \,\!$   假設   2.   $\mathrm {P} \rightarrow \mathrm {P} \,\!$   1 CI

否定

示例推導

為了說明否定引入，我們將提供一個關於以下論證的推導

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

1.   $\lnot (\mathrm {P} \rightarrow \mathrm {Q} )\rightarrow \mathrm {R} \,\!$   前提 2.   $\mathrm {P} \land \lnot \mathrm {Q} \,\!$   前提   3.     $\mathrm {P} \rightarrow \mathrm {Q} \,\!$   假設 4.     $\mathrm {P} \,\!$   2 KE 5.     $\mathrm {Q} \,\!$   3, 4 CE 6.     $\lnot \mathrm {Q} \,\!$   2 KE   7.   $\lnot (\mathrm {P} \rightarrow \mathrm {Q} )\,\!$   3–6 NI 8.   $\mathrm {R} \,\!$   1, 7 CE 9.   $\mathrm {Q} \lor \mathrm {R} \,\!$   8 DI

第 3 行到第 6 行構成一個子推導。它首先假設所需公式的相反，最後假設一個矛盾（一個公式及其否定）。和以前一樣，行號和公式之間有兩個垂直的柵欄，將它與推導的其餘部分隔開，並表明它的從屬狀態。第 3 行下的水平柵欄再次將假設與子推導的其餘部分隔開。第 7 行是從整個子推導得出的，是否定引入的應用。

在第 9 行，請注意註釋“5 DI”是不正確的。雖然根據 DI 從 $\mathrm {Q} \,\!$ 推斷出 $\mathrm {Q} \lor \mathrm {R} \,\!$ 是有效的，當我們到達第 9 行時，第 5 行不再處於活動狀態。因此，我們不允許在那個時候從第 5 行推匯出任何東西。

否定引入規則

否定引入 (NI)

${\underline {{\text{Assume }}\varphi {\text{, derive }}\psi {\text{ and }}\lnot \psi }}$

$\lnot \varphi \,\!$

推論結果行是從整個子推導推斷出的。註釋是子推導所佔行的範圍，縮寫是 NI。否定引入有時用拉丁語名稱Reductio ad Absurdum，有時用反證法。

與條件引入一樣，否定引入不能用真值表來證明。相反，它是透過在 命題連線詞的性質 中介紹的歸謬原理來證明的。

另一個示例推導

為了說明否定消去，我們將為以下論證提供一個推導

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

1.   $\lnot (\lnot \mathrm {P} \lor \lnot \mathrm {Q} )\land \mathrm {R} \,\!$   前提   2.     $\lnot \mathrm {P} \,\!$   假設 3.     $\lnot \mathrm {P} \lor \lnot \mathrm {Q} \,\!$   2 DI 4.     $\lnot (\lnot \mathrm {P} \lor \lnot \mathrm {Q} )\,\!$   1 KE   5.   $\mathrm {P} \,\!$   2–4 NE

第 2 行到第 4 行構成一個子推導。正如前面例子中一樣，它從假設所需公式的反面開始，並以假設矛盾（公式及其否定）結束。第 5 行緊隨整個子推導，是否定消除的應用。

否定消除規則

否定消除 (NE)

${\underline {{\text{Assume }}\lnot \varphi {\text{, derive }}\psi {\text{ and }}\lnot \psi }}$

$\varphi \,\!$

後面的行從整個子推導中推斷出來。註釋是子推導所佔行的範圍，縮寫是 NE。像否定引入一樣，否定消除有時被稱為拉丁名字 Reductio ad Absurdum，有時被稱為 反證法。

像否定引入一樣，否定消除是根據在 命題連線詞的性質 中介紹的歸謬原則來證明的。這個規則在引入/消除命名約定中的位置有點尷尬，不像其他消除規則，這個規則消除的否定並沒有出現在已經推匯出的行中。而是消除的否定出現在子推導的假設中。

術語

在本模組中介紹的推理規則，條件引入和否定引入，都是放縮規則。為了避免使用更好的術語，我們可以將 推理規則 中介紹的推理規則稱為“標準規則”。標準規則 是推理規則，其前件是一組行。放縮規則 是推理規則，其前件是一個子推導。

推導中一行深度 是該行號與公式之間隔開的籬笆數量。推導的所有行都至少有 1 的深度。每個臨時假設都會將深度增加 1。每個放縮規則都會將深度減少 1。

活動行 是一行，可作為標準推理規則的前件行使用。特別是，它是一行，其深度小於或等於當前行的深度。非活動行是不活動的行。

放縮規則被稱為放縮 假設。它使前件子推導中的所有行都變為非活動行。