计算机科学家逻辑/命题逻辑/等价和范式

等价和范式

到目前为止，我们只讨论了单个公式及其语义属性。在本节中，我们将开始研究公式是否可以转换为另一种形式，而不会改变其语义。为此，我们引入了逻辑等价的概念，它可以用来研究将给定公式转换为其范式。

定义 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$