形式邏輯/命題邏輯/表達能力

← 有效性

↑ 命題邏輯

命題連線詞的性質 →

表達能力

公式真值表

一個包含 n 個命題字母的公式在其 真值表 中需要 $2^{n}\,\!$ 行。對於一個包含 m 行的真值表，存在 $2^{m}\,\!$ 種可能的公式。因此，對於一個包含 n 個字母的句子，$m=2^{n}$，可能的公式數量為 $2^{2^{n}}$。

例如，存在四個包含一個命題字母的可能公式（需要一個兩行真值表），以及 16 個包含兩個命題字母的可能公式（需要一個四行真值表）。我們用以下表格來說明這一點。編號的列代表主連線詞列的不同可能性。

$\mathrm {P} \,\!$ (i) (ii) (iii) (iv) T T T F F F T F T F

第 (iii) 列是 之前 提出的否定公式。

$\mathrm {P} \,\!$ $\mathrm {Q} \,\!$ (i) (ii) (iii) (iv) (v) (vi) (vii) (viii) (ix) (x) (xi) (xii) (xiii) (xiv) (xv) (xvi) T T T T T T T T T T F F F F F F F F T F T T T T F F F F T T T T F F F F F T T T F F T T F F T T F F T T F F F F T F T F T F T F T F T F T F T F

第 (ii) 列表示析取公式，第 (v) 列表示條件公式，第 (vii) 列表示雙條件公式，第 (viii) 列表示合取公式。

表達任意公式

問題出現了，我們是否有足夠的連線詞來表示任意數量的命題字母的所有公式。請記住，每一行都代表一種賦值。我們可以透過將該賦值下被賦值為真的命題字母與被賦值為假的命題字母的否定進行合取來表達該賦值。上面的第二個表格中的四個賦值可以表達為

$\mathrm {P} \land \mathrm {Q} \,\!$

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

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

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

現在我們可以透過對公式值為真的賦值進行析取來表達任意公式。例如，我們可以用以下公式表達第 (x) 列

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

您可以透過完成真值表來確認此公式是否產生了預期的結果。該公式在以下情況下為真： (a) $\mathrm {P} \,\!$ 為真且 $\mathrm {Q} \,\!$ 為假，或者 (b) $\mathrm {P} \,\!$ 為假且 $\mathrm {Q} \,\!$ 為真。有一個更簡單的方法來表達相同的公式： $\mathrm {P} \leftrightarrow \lnot \mathrm {Q} \,\!$。想出一個表達任意公式的簡單方法可能需要洞察力，但至少我們有一個自動機制來找到表達它的某些方法。

現在考慮第二個例子。我們想表達一個關於 $\mathrm {P} \,\!$，$\mathrm {Q} \,\!$ 和 $\mathrm {R} \,\!$ 的公式，我們希望該公式在以下三種賦值下（且僅在以下三種賦值下）為真。

			(i)		(ii)		(iii)
	$\mathrm {P} \,\!$		真		假		假
	$\mathrm {Q} \,\!$		真		真		假
	$\mathrm {R} \,\!$		假		假		真

我們可以將產生真值的三個條件表達為

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

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

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

現在我們需要說第一個條件或第二個條件或第三個條件成立。

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

您可以透過真值表驗證它是否產生了預期的結果，即該公式僅在上述解釋下為真。

這種表達任意公式的技術不適用於在所有解釋中都計算為 False 的公式。我們需要至少一個解釋得出 True，才能啟動公式。但是，我們可以使用任何永真假公式來表達這種公式。 $\mathrm {P} \land \lnot \mathrm {P} \,\!$ 就足夠了。

正規化

正規化提供了一種標準化的表達規則，任何公式都等效於符合該規則的公式。在以下內容中，將文字定義為句子字母或其否定（例如 $\mathrm {P}$ 和 $\mathrm {Q}$，以及 $\neg \mathrm {P}$ 和 $\neg \mathrm {Q}$）。

析取正規化

我們說一個公式處於析取正規化，如果它是文字的合取的析取。例如 $(\mathrm {P} \land \mathrm {Q} )\lor (\lnot \mathrm {R} \land \mathrm {S} )$。為了這個定義的目的，我們承認所謂的退化析取和合取，它們只有一個析取項或合取項。因此，我們將 $\mathrm {P} \,\!$ 算作處於析取正規化，因為它是一個退化（單一位置）析取的退化（單一位置）合取。可以透過將其轉換為等效公式 $(\mathrm {P} \land \mathrm {P} )\lor (\mathrm {P} \land \mathrm {P} )\,\!$ 來消除這種退化。為了這個定義的目的，我們還承認多位置析取和合取，例如 $(\lnot \mathrm {P} \land \mathrm {Q} \land \lnot \mathrm {R} )\lor (\mathrm {S} \land \mathrm {R} )$。上面展示了一種找到任意公式的析取正規化的方法。

合取正規化

在命題邏輯中還有另一種常見的正規化，即合取正規化。一個公式處於合取正規化，如果它是文字的析取的合取。例如 $(\mathrm {P} \lor \lnot \mathrm {Q} )\land (\mathrm {R} \lor \mathrm {S} )$。同樣，我們可以用合取正規化表達任意公式。首先，取公式計算為 False 的賦值。對於每個這樣的賦值，形成一個析取，該析取包含賦值為 False 的句子字母以及賦值為 True 的句子字母的否定。對於賦值

$\mathrm {P} \,\!$   :    False

$\mathrm {Q} \,\!$   :    True

$\mathrm {R} \,\!$   :    假

我們形成析取

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

任意公式的合取正規化表示式是所有與公式計算為假的解釋相匹配的這種析取的合取。上面 (1) 的合取正規化等價形式是

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

上面 (2) 的合取正規化等價形式是

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

連線詞的互定義性

否定和合取足以表達其他三個連線詞，事實上可以表達任何任意公式。

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

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

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

否定和析取足以表達其他三個連線詞，實際上可以表達任何任意公式。

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

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

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

否定和條件句足以表達其他三個連線詞，實際上可以表達任何任意公式。

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

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

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

否定和雙條件句不足以表達其他三個連線詞。

聯合否定和選擇否定

我們已經看到，三對連線詞可以共同表達任何任意公式。於是就產生了疑問，是否可以透過僅僅一個連線詞來表達任何任意公式？答案是肯定的，但不能使用我們已有的任何連線詞。如果在${\mathcal {L_{S}}}\,\!$中新增一個新的連線詞，那麼會有兩個可能的二元連線詞，如果新增它們，則足以表達任何公式。

選擇否定

替代否定，有時也稱為NAND。這個的常用符號被稱為Sheffer 豎線，寫成 $\mid$（有些作者使用 ↑）。暫時將符號 $\mid \,\!$ 新增到 ${\mathcal {L_{S}}}\,\!$，並令 ${\mathfrak {v}}[(\varphi \mid \psi )]\,\!$ 在 $\varphi \,\!$ 或 $\psi \,\!$ 中至少有一個為假時為真。它具有如下真值表 

$\mathrm {P} \,\!$ $\mathrm {Q} \,\!$ $\mathrm {P} \mid \mathrm {Q} \,\!$ T T F T F T F T T F F T

現在我們有以下等價關係。

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

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

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

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

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

聯合否定

聯合否定，有時稱為NOR。暫時將符號 $\downarrow \,\!$ 新增到 ${\mathcal {L_{S}}}\,\!$，並讓 ${\mathfrak {v}}[(\varphi \downarrow \psi )]\,\!$ 在 $\varphi \,\!$ 和 $\psi \,\!$ 都為假時為真。它具有真值表 

$\mathrm {P} \,\!$ $\mathrm {Q} \,\!$ $\mathrm {P} \downarrow \mathrm {Q} \,\!$ T T F T F F F T F F F T

現在我們有以下等價關係。

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

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

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

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

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

← 有效性

↑ 命題邏輯

命題連線詞的性質 →