計算機科學家邏輯/命題邏輯/等價和正規化

等價和正規化

到目前為止，我們只討論了單個公式及其語義屬性。在本節中，我們將開始研究公式是否可以轉換為另一種形式，而不會改變其語義。為此，我們引入了邏輯等價的概念，它可以用來研究將給定公式轉換為其正規化。

定義 6

公式 $F$ 和 $G$ 被稱為 (語義) 等價，當且僅當對於所有賦值 ${\mathcal {A}}$ 對於 $F$ 和 $G$，${\mathcal {A}}(F)={\mathcal {A}}(G)$。我們寫 $F\equiv G$。

包含不同子公式的公式可以是等價的，例如，所有重言式都是等價的。更有趣的是以下定理

定理 3 (可代入性)

令 $F\equiv G$ 且 $H$ 為至少包含一個子公式 $F$ 的公式。那麼成立 $H\equiv H'$，其中 $H'$ 是透過將 $H$ 中的任何一個 $F$ 替換為 $G$ 獲得的。

證明： 證明透過對子公式 $H$ 的結構進行歸納。

假設歸納起點，$H$ 為原子公式，因此 $H=F$ 成立，將 $F$ 唯一齣現的地方替換為 $G$ 的結果是 $H'=G$，因為 $F\equiv G$，所以我們有 $H\equiv H'$。假設該定理對 $H$ 的所有真子公式成立：如果 $F=H$，我們有與歸納起點相同的論證。如果 $F\neq H$，我們有三種情況。

• $H=\lnot h_{1}$：因為 $h_{1}$ 是 $H$ 的一個子公式，我們可以得出結論 $h_{1}\equiv h_{1}'$，其中 $h_{1}'$ 是透過將 $F$ 替換為 $G$ 構造的。從 $\lnot$ 語義的定義我們得出結論 $\lnot h_{1}\equiv \lnot h_{1}'$，因此 $H\equiv H_{1}'$。其中 H_1 是透過在 H 中將 F 替換為 G 構造的等價公式，得到 H_1
• $H=(h_{1}\lor h_{2})$: 假設不失一般性，$F$ 出現在 $h_{1}$ 中。那麼，根據歸納假設，我們可以得出結論，$h_{1}\equiv h_{1}'$，並且根據 $\lor$ 語義的定義，我們可以得出結論，$(h_{1}\lor h_{2})=(h_{1}'\lor h_{2})$.
• $H=(h_{1}\land h_{2})$ 類似。

定理 4

以下等價關係成立

$(F\land F)$ $\equiv$ $F$

$(F\lor F)$ $\equiv$ $F$ (冪等性)

$(F\land G)$ $\equiv$ $(G\land F)$

$(F\lor G)$ $\equiv$ $(G\lor F)$ (交換律)

$((F\land G)\land H)$ $\equiv$ $(F\land (G\land H))$

$((F\lor G)\lor H)$ $\equiv$ $(F\lor (G\lor H))$ (結合律)

$(F\land (F\lor G))$ $\equiv$ $F$

$(F\lor (F\land G))$ $\equiv$ $F$ (吸收律)

$(F\land (G\lor H))$ $\equiv$ $((F\land G)\lor (F\land H))$

$(F\lor (G\land H))$ $\equiv$ $((F\lor G)\land (F\lor H))$ (分配律)

$\lnot ~\lnot F$ $\equiv$ $F$ (雙重否定律)

$\lnot (F\land G)$ $\equiv$ $(\lnot F\lor \lnot G)$

$\lnot (F\lor G)$ $\equiv$ $(\lnot F\land \lnot G)$ (deMorgan's rule)

$(F\lor G)$ $\equiv$ $F$, if $F$ is a tautology

$(F\land G)$ $\equiv$ $G$, if $F$ is a tautology (Rule of Tautology)

$(F\lor G)$ $\equiv$ $G$, if $F$ is unsatisfiable

$(F\land G)$ $\equiv$ $F$, if $F$ is unsatisfiable (Rule of Unsatisfiability)

證明： 所有等價關係都可以透過真值表來證明。這裡以第二條吸收定律為例進行證明

$F$	$G$	($F\land G$)	($F\lor (F\land G$))
false	false	false	false
false	true	false	false
true	false	false	true
true	true	true	true

現在讓我們使用這些等價關係以及代入定理 (TS) 來證明以下等價關係

$((A\lor (B\lor C))\land (C\lor \lnot A))\equiv ((B\land \lnot A)\lor C)$

$((A\lor (B\lor C))\land (C\lor \lnot A))$

$\equiv$ $((A\lor B)\lor C)\land (C\lor \lnot A))$ 結合律和 TS

$\equiv$ $((C\lor (A\lor B))\land ((C\lor \lnot A))$ 交換律和 TS

$\equiv$ $(C\lor ((A\lor B)\land \lnot A))$ 分配律

$\equiv$ $(C\lor (\lnot A\land (A\lor B)))$ 交換律和 TS

$\equiv$ $(C\lor ((\lnot A\land A)\lor (\lnot A\land B))$ 分配律和 TS

$\equiv$ $(C\lor (\lnot A\land B))$ 不可滿足性和 TS

$\equiv$ $(C\lor (B\land \lnot A))$ 交換律和 TS

$\equiv$ $((B\land \lnot A)\lor C)$ 交換律和 TS

問題

問題 9（命題）

二元連線詞 ${\stackrel {\cdot }{\vee }}$ 用於異或，定義為 $F{\stackrel {\cdot }{\vee }}G=F\leftrightarrow (\lnot G)$。證明以下命題邏輯公式成立 $F$, $G$ 和 $H$

1. $F{\stackrel {\cdot }{\vee }}G\equiv G{\stackrel {\cdot }{\vee }}F$ （交換律）。
   
   
2. $(F{\stackrel {\cdot }{\vee }}G){\stackrel {\cdot }{\vee }}H\equiv F{\stackrel {\cdot }{\vee }}(G{\stackrel {\cdot }{\vee }}H)$ （結合律）

$\Box$

問題 10（命題）

使用等價變換證明以下結論。請為所有重構步驟提供所用規則！

1. $(A\to (B\lor C))\equiv (A\to B)\lor (A\to C)$
2. $(A\to B)\to A\equiv (B\to A)\land (B\lor A)$
3. $A\leftrightarrow \lnot B\equiv \lnot (A\leftrightarrow B)$
4. $(A\to (B\land C))\equiv (A\to B)\land (A\to C)$
5. $(A\to B)\to (B\to A)\equiv B\to A$
6. $(A\lor \lnot B)\lor ((\lnot A\land \lnot C)\land B)\equiv (A\lor \lnot C)\lor \lnot B$

$\Box$

問題 11 (命題)

用等價關係證明

1. $p\lor \lnot (p\land q)$ 是一個永真式。
2. $(p\lor \lnot q)\land (\lnot p\land q)$ 是不可滿足的。

$\Box$

問題 12 (命題)

二元連線詞 $\downarrow$，其含義為“非此即彼”，由 $F\downarrow G=\lnot (F\lor G)$ 定義。設 $F$ 為一個命題邏輯公式，它只包含運算子 $\land$ $\lor$ 和 $\lnot$。證明對每個公式 $F$ 都存在一個公式 ${\mathcal {T}}(F)$，使得 $F\equiv {\mathcal {T}}(F)$ 並且 ${\mathcal {T}}(F)$ 僅使用連線詞 $\downarrow$ 建立。

$\Box$

問題 13（命題邏輯）

設 $F$ 是一個命題邏輯公式，它只包含運算子 $\land$，$\lor$ 和 $\lnot$。證明對於每個公式 $F$，都存在一個公式 ${\mathcal {T}}(F)$，使得 $F\equiv {\mathcal {T}}(F)$ 並且 ${\mathcal {T}}(F)$ 是透過僅使用連線詞 $\to$ 和 ${\stackrel {\cdot }{\vee }}$ 建立的。

$\Box$

問題 14 (命題邏輯)

給出以下公式：

• $A\equiv D\lor B$
• $B\equiv \lnot B\lor \lnot D\lor \lnot S$
• $C\equiv (\lnot S\land D)\lor \lnot B$

1. 使用 $B\land C\equiv C$ 簡化 $A\land B\land C$。
2. 使用等價關係但不用 $B\land C\equiv C$ 簡化 $A\land B\land C$。

$\Box$

定義 7 (正規化)

文字是原子公式或原子公式的否定（分別為正或負）。公式 $F$ 處於合取正規化 (CNF) 當且僅當

$F=(\bigwedge _{i=1}^{n}(\bigvee _{j=1}^{m_{i}}L_{i,j}))$

其中 $L_{ij}$ 是一個文字。

公式 $F$ 處於析取正規化 (DNF) 當且僅當

$F=(\bigvee _{i=1}^{n}(\bigwedge _{j=1}^{m_{i}}L_{i,j}))$

其中 $L_{ij}$ 是一個文字

定理 5

對於每個公式 $F$ 存在一個等價公式處於 DNF，也存在一個等價公式處於 CNF。

讓我們設計一個演算法來將給定的公式 F 轉化為等價的正規化

給定: 公式 $F$

1. 在 $F$ 中用以下形式替換每個子公式

$\lnot ~\lnot ~G{\text{ by }}G$

$\lnot ~(G~\land ~H){\text{ by }}(\lnot ~G~\lor ~\lnot ~H)$

$\lnot ~(G~\lor ~H){\text{ by }}(\lnot ~G~\land ~\lnot ~H)$

直到不再存在這種形式的子公式。

2. 在上述步驟的結果中，用以下形式替換每個子公式

$(F~\lor ~(G~\land ~H)){\text{ by }}((F~\lor ~G)~\land ~(F~\lor ~H))$

$((F~\land ~G)~\lor ~H){\text{ by }}((F~\lor ~H)~\land ~(G~\lor ~H))$

直到不再存在這種形式的子公式。

結果: 一個等價的 CNF 公式

到目前為止，我們研究瞭如何將命題公式轉化為等價的正規化。正規化中的另一個問題是，從給定的真值表構造正規化公式；也就是說，公式本身是未知的，但它的行為由真值表給出。讓我們從真值表中讀取正規化公式：假設一個公式 $F$，它由以下真值表給出。

A	B	C	F
false	false	false	true
false	false	true	false
false	true	false	false
false	true	true	false
true	false	false	true
true	false	true	true
true	true	false	false
true	true	true	false

為了構建一個與 $F$ 等價的 DNF 公式，我們必須考慮到，真值表中每一行導致真值 $true$ 的結果，都會得到一個合取式：如果文字 $A_{i}$ 的賦值為 $true$，它被包含為 $\ldots \land A_{i}\land \ldots$，如果賦值為 $false$，我們就包含 $\ldots \land \lnot A_{i}\ldots \land \ldots$。對於上面的例子，我們得到一個 DNF

$(\lnot A\land \lnot B\land \lnot C)\lor$

$(A\land \lnot B\land \lnot C)\lor$

$(A\land \lnot B\land C)$

如果我們在上面的過程中交換 $true$ 和 $false$ 以及 $\lor$ 和 $\land$ 的角色，我們得到一個 CNF

$(A\lor B\lor \lnot C)\land$

$(A\lor \lnot B\lor C)\land$

$(A\lor \lnot B\lor \lnot C)\land$

$(\lnot A\lor \lnot B\lor C)\land$

$(\lnot A\lor \lnot B\lor \lnot C)$

我們介紹一種用於表示規範形式公式的特殊表示法。在引言中，我們已經使用了一種非常特殊的規範形式，即 CNF 公式的蘊涵形式：連線詞$F_{1},\cdots ,F_{l}$ 的每個子公式$F_{i}$ 都寫成

$A_{1}\land \cdots \land A_{n}\to B_{1}\lor \cdots \lor B_{m}$

不難看出，該蘊涵等價於析取式$\lnot A_{1}\lor \cdots \lor \lnot A_{n}\lor B_{1}\lor \cdots \lor B_{m}$。有時，蘊涵寫成

$A_{1},\cdots ,A_{n}\to B_{1};\cdots ;B_{m}$

在某些情況下，甚至使用以下含糊的表示法，其中前提中的逗號代表連線詞，結論中的逗號代表析取詞

$A_{1},\cdots ,A_{n}\to B_{1},\cdots ,B_{m}$

對於邏輯推理的一些重要步驟，必須不僅以上述規範形式之一表示公式，而且必須使用以下定義中的所謂子句形式。

定義 8

如果$F$ 是一個 CNF 公式，即

$F=(L_{1,1}\lor \ldots \lor L_{1,{n_{1}}})\land \ldots \land (L_{k,1}\lor \ldots \lor L_{k,{n_{k}}})$

那麼它在子句形式中的對應表示為

$F=\{\{L_{1,1},\ldots ,L_{1,{n_{1}}}\},\ldots ,\{L_{k,1},\ldots ,L_{k,{n_{k}}}\}\}$

集合$\{L_{i,1},\ldots ,L_{i,{n_{i}}}\}$ 稱為子句。

這種文字集合表示法具有以下優點：文字的出現順序無關緊要，並且文字在析取式中的多次出現將在其子句形式中“合併”。請注意，作為結果，我們在表示法中引入了結合律、交換律和冪等律。

$((A_{1}\lor \lnot A_{2})\land (A_{3}\land A_{3}))$             $\{\{A_{1},\lnot A_{2}\},\{A_{3}\}\}$

$(A_{3}\land (\lnot A_{2}\lor A_{1}))$

問題

問題 15（命題邏輯）

建立等價於以下公式的（a）合取正規化或（b）析取正規化公式：

$A{\stackrel {\cdot }{\vee }}B{\stackrel {\cdot }{\vee }}C$

其中 ${\stackrel {\cdot }{\vee }}$ 表示異或。

$\Box$

問題 16（命題邏輯）

定理證明器 OTTER 對子句集使用以下最佳化規則：

子句包含：如果子句 $K$ 的文字是另一個子句 $K'$ 的子集，則從子句集中刪除 $K'$。
透過單元子句刪除：如果子句集包含一個單元子句 $L$ -這裡 $L$ 是單個文字的單元子句- 子句中每個互補文字 ${\overline {L}}$ 都被刪除。

哪些邏輯定律證明了這些過程？

$\Box$

問題 17（命題邏輯）

為以下公式生成真值表。給出公式的合取正規化和析取正規化。哪一個關係 $F\models G$， $G\models F$， $F\equiv G$ 和 $F=G$ 成立？

1. $F=(A\land \lnot (B\lor C)){\stackrel {\cdot }{\vee }}((A\to B)\lor (A\to C),)$ 而 $F{\stackrel {\cdot }{\vee }}G=F\leftrightarrow (\lnot G)$ 適用。
2. $G=((A\lor (B\land A))\to \lnot A)\lor C$

$\Box$

問題 18（命題邏輯）

從以下公式 $F$ 的真值表生成 CNF 和 DNF。

A	B	C	F
0	0	0	0
1	0	0	1
0	1	0	0
1	0	0	1
1	1	0	1
1	0	1	0
0	1	1	1
1	1	1	0

$\Box$

問題 19（命題邏輯）

從公式 $(P\land (Q\to R)\to S)$ 生成 CNF。

$\Box$