命题逻辑等值演算

一、等值式

1.1 等值式的定义

定义：如果 $A \leftrightarrow B$ 为永真式（重言式），则称A和B等值，记作 $A \Leftrightarrow B$，并称 $A \Leftrightarrow B$ 为等值式。

要点：

• $\Leftrightarrow$ 是元语言符号，不是联结词
• $\Leftrightarrow$ 表示两个公式之间的一种关系，而不是一个新的公式
• 有些教材也记作 $A = B$ 或 $A \equiv B$

英文表达：

• 重言式：A compound proposition is called a tautology if no matter what truth values its atomic propositions have, its own truth value is T.
• 矛盾式：The opposite to a tautology, is a compound proposition that’s always false — a contradiction.

二、重言式与矛盾式相关定理

2.1 基本定理

定理1：任何两个重言式的合取和析取，仍然是一个重言式。

定理2：一个重言式，对同一分量都用相同的任意合式公式置换，其结果仍为一重言式。

理解：重言式的真值与分量的指派无关，而是由变元和逻辑运算符之间的关系决定

定理3：任意两个命题公式A、B：$A \Leftrightarrow B$ 当且仅当 $A \leftrightarrow B$ 是重言式。

2.2 重言式的证明方法

方法一：往证与T等价
方法二：列真值表
方法三：由已知的重言式置换而来

示例：证明 $[\neg P \land (P \lor Q)] \to Q$ 是重言式

方法一：真值表法

所有行结果都为T，因此是重言式。

方法二：等价变换法

$$\begin{aligned} &[\neg P \land (P \lor Q)] \to Q \\ \Leftrightarrow\ & [(\neg P \land P) \lor (\neg P \land Q)] \to Q \\ \Leftrightarrow\ & [F \lor (\neg P \land Q)] \to Q \\ \Leftrightarrow\ & [\neg P \land Q] \to Q \\ \Leftrightarrow\ & \neg[\neg P \land Q] \lor Q \\ \Leftrightarrow\ & [P \lor \neg Q] \lor Q \\ \Leftrightarrow\ & P \lor [\neg Q \lor Q] \\ \Leftrightarrow\ & P \lor T \\ \Leftrightarrow\ & T \end{aligned}$$

三、基本等值式（命题定律）

3.1 双否律

$\neg(\neg A) \Leftrightarrow A$

3.2 幂等律

$A \land A \Leftrightarrow A$
$A \lor A \Leftrightarrow A$

3.3 交换律

$A \land B \Leftrightarrow B \land A$
$A \lor B \Leftrightarrow B \lor A$

3.4 结合律

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

3.5 分配律

或对且的分配律：
$A \lor (B \land C) \Leftrightarrow (A \lor B) \land (A \lor C)$

且对或的分配律：
$A \land (B \lor C) \Leftrightarrow (A \land B) \lor (A \land C)$

3.6 德摩根律

$\neg(A \land B) \Leftrightarrow \neg A \lor \neg B$
$\neg(A \lor B) \Leftrightarrow \neg A \land \neg B$

口诀：否定进去，且变或，或变且

3.7 吸收律

$A \lor (A \land B) \Leftrightarrow A$
$A \land (A \lor B) \Leftrightarrow A$

3.8 零律

$A \lor 1 \Leftrightarrow 1$
$A \land 0 \Leftrightarrow 0$

3.9 同一律

$A \land 1 \Leftrightarrow A$
$A \lor 0 \Leftrightarrow A$

3.10 排中律

$A \lor \neg A \Leftrightarrow 1$

3.11 矛盾律

$A \land \neg A \Leftrightarrow 0$

3.12 蕴含等值式

$A \to B \Leftrightarrow \neg A \lor B$

应用：消除公式中的蕴含联结词

3.13 等价等值式

$A \leftrightarrow B \Leftrightarrow (A \to B) \land (B \to A)$

3.14 假言易位

$A \to B \Leftrightarrow \neg B \to \neg A$

说明：原命题等价于其逆否命题

3.15 等价否定等值式

$A \leftrightarrow B \Leftrightarrow \neg A \leftrightarrow \neg B$

3.16 归谬律

$(A \to B) \land (A \to \neg B) \Leftrightarrow \neg A$

四、子公式与置换规则

4.1 子公式

定义：如果X是合式公式A的一部分，且X本身也是一个合式公式，则称X为公式A的子公式。

4.2 置换规则

定义：设X是合式公式A的子公式，若 $X \Leftrightarrow Y$，如果将A中的X用Y来置换，所得到公式B与公式A等价，即 $A \Leftrightarrow B$。

要点：

• 置换规则是等值演算的基础
• 置换可以对子公式进行，不需要对整个公式进行
• 置换后的公式与原公式等价

五、等值演算

5.1 基本方法

思路：用基本等值式将公式逐步变形，消除蕴含、等价等联结词，最终化为只含 ¬、∧、∨ 的形式。

步骤：

1. 用蕴含等值式消除 →
2. 用等价等值式消除 ↔
3. 用德摩根律将否定符号深入
4. 用分配律、吸收律等进一步化简

5.2 判断公式类型

方法：通过等值演算，将公式化简：

• 若最终化为 1，则为重言式
• 若最终化为 0，则为矛盾式
• 若无法化为常量，则为可满足式

示例：判断 $(P \land R) \land \neg(Q \to P)$ 的类型

$$\begin{aligned} &(P \land R) \land \neg(Q \to P) \\ \Leftrightarrow\ & (P \land R) \land \neg(\neg Q \lor P) \\ \Leftrightarrow\ & (P \land R) \land (Q \land \neg P) \\ \Leftrightarrow\ & P \land \neg P \land Q \land R \\ \Leftrightarrow\ & 0 \land Q \land R \\ \Leftrightarrow\ & 0 \end{aligned}$$

结论：该公式为矛盾式。

5.3 证明公式等值

方法一：列真值表

方法二：利用置换规则进行等价变换

示例：证明 $Q \to (P \to R) \Leftrightarrow (P \land Q) \to R$

$$\begin{aligned} &Q \to (P \to R) \\ \Leftrightarrow\ & \neg Q \lor (\neg P \lor R) \\ \Leftrightarrow\ & \neg P \lor \neg Q \lor R \\ \Leftrightarrow\ & \neg(P \land Q) \lor R \\ \Leftrightarrow\ & (P \land Q) \to R \end{aligned}$$

六、范式

6.1 基本概念

定义：

• 文字：命题变元 $P$ 或其否定 $\neg P$
• 析取式：有限个文字的析取，如 $P \lor \neg Q$
• 合取式：有限个文字的合取，如 $\neg P \land Q$
• 析取范式：有限个合取式的析取
• 合取范式：有限个析取式的合取

形式：

• 析取范式：$(\cdots) \lor (\cdots) \lor (\cdots)$，括号内为合取式
• 合取范式：$(\cdots) \land (\cdots) \land (\cdots)$，括号内为析取式

6.2 求范式的方法

步骤：

1. 消除蕴含和等价联结词
2. 将否定符号深入到文字前
3. 使用分配律展开

示例：求 $P \lor Q \leftrightarrow P$ 的析取范式和合取范式

$$\begin{aligned} &(P \lor Q) \leftrightarrow P \\ \Leftrightarrow\ & ((P \lor Q) \to P) \land (P \to (P \lor Q)) \\ \Leftrightarrow\ & (\neg(P \lor Q) \lor P) \land (\neg P \lor (P \lor Q)) \\ \Leftrightarrow\ & ((\neg P \land \neg Q) \lor P) \land (\neg P \lor P \lor Q) \\ \Leftrightarrow\ & ((\neg P \lor P) \land (\neg Q \lor P)) \land 1 \\ \Leftrightarrow\ & 1 \land (\neg Q \lor P) \\ \Leftrightarrow\ & \neg Q \lor P \quad \text{（析取范式）} \\ \Leftrightarrow\ & P \lor \neg Q \quad \text{（也是合取范式）} \end{aligned}$$

注意：一个公式的析取范式和合取范式不唯一。

七、主范式

7.1 极小项（小项）

定义：含 $n$ 个命题变元的合取式，如果每个变元或其否定出现且仅出现一次，且按脚标顺序排列，则称为一个极小项（小项）。

示例（2个变元P、Q的小项）：

性质1：

• $n$ 个变元共有 $2^n$ 个小项
• 小项的脚标对应其成真赋值的二进制表示
• 不同小项的合取为 0（矛盾式）
• 所有小项的析取为 1（重言式）

通常，在讨论极小项之前，我们会先给定命题变元的集合，并且它们天然带有某种顺序：

• 如果用下标表示，就是 $P_1, P_2, \dots, P_n$，顺序就是下标从小到大：第1个是 $P_1$，第2个是 $P_2$……
• 如果用字母表示，比如 $P, Q, R$，习惯上按字母表顺序（或书写先后）约定：$P$ 排第1，$Q$ 排第2，$R$ 排第3。

这个顺序一旦约定好，后面所有极小项的书写都必须严格遵守。

编码规则：含有 $n$ 个变元的小项，其角标用 $n$ 位二进制码表示：

• 将命题变元按约定顺序排列（如 $P_1, P_2, \dots, P_n$）
• 每一位对应一个变元：1 表示该变元以本身形式出现，0 表示该变元以否定形式出现
• 将这个 $n$ 位二进制码转换为十进制，即为小项的角标

示例（3 个变元 $P, Q, R$，约定 $P$ 为第 1 位、$Q$ 为第 2 位、$R$ 为第 3 位）：

• $m_3$（二进制 011）：$\neg P \land Q \land R$ — 第 1 位为 0 所以 $P$ 取否定，第 2、3 位为 1 所以 $Q, R$ 取本身
• $m_5$（二进制 101）：$P \land \neg Q \land R$

性质2：每个小项当且仅当其赋值与编码相同时，其真值为 $T$；而其余 $2^n - 1$ 组赋值均使该小项的真值为 $F$。由此可知，全体小项的析取式为永真式——无论变元取何值，总有且仅有一个小项为真。

7.2 极大项（大项）

定义：含 $n$ 个命题变元的析取式，如果每个变元或其否定出现且仅出现一次，且按脚标顺序排列，则称为一个极大项（大项）。

示例（2个变元P、Q的大项）：

性质：

• $n$ 个变元共有 $2^n$ 个大项
• 大项的脚标对应其成假赋值的二进制表示
• 不同大项的析取为 1（重言式）
• 所有大项的合取为 0（矛盾式）

7.3 主析取范式

定义：若一个命题公式的析取范式为 $A_1 \lor A_2 \lor \dots \lor A_n\ (n \geq 1)$，其中每个 $A_i\ (i = 1, 2, \dots, n)$ 都是小项，则称之为该命题公式的主析取范式。

简言之：由若干小项的析取组成的范式称为主析取范式。每个公式的主析取范式是唯一的。

求法一：真值表法

1. 列出公式的真值表，同时列出所有小项
2. 找出公式真值为 $1$ 的行
3. 将对应的小项析取起来，即得主析取范式

求法二：等值演算法

1. 将公式化为析取范式
2. 对每个合取式，若缺少某个变元，则利用 $P \lor \neg P \Leftrightarrow 1$ 补充该变元
3. 展开，并用幂等律、同一律化简，去掉重复的小项

7.4 主合取范式

定义：由若干大项的合取组成的范式称为主合取范式。

求法一：真值表法

1. 列出公式和所有大项的真值表
2. 找出公式真值为 0 的行
3. 将对应的大项合取起来

求法二：等值演算法

1. 将公式化为合取范式
2. 对每个析取式，补充缺少的变元（用 $P \land \neg P = 0$ 构造）
3. 展开并用幂等律去重

快速转换：

• 已知主析取范式，求主合取范式：用未出现的小项脚标对应的大项合取
• 已知主合取范式，求主析取范式：用未出现的大项脚标对应的小项析取

示例：求 $P \to Q$ 的主析取范式和主合取范式

$P \to Q \Leftrightarrow \neg P \lor Q$

真值表法：

• 主析取范式：$m_0 \lor m_1 \lor m_3 = (\neg P \land \neg Q) \lor (\neg P \land Q) \lor (P \land Q)$
• 主合取范式：$M_2 = \neg P \lor Q$

八、联结词的完备集

8.1 定义

定义：设 $S$ 是一个联结词集合，如果任何命题公式都可以仅用 $S$ 中的联结词表示，则称 $S$ 为联结词的完备集。

8.2 常见的完备集

以下集合都是联结词的完备集：

1. $S_1 = \{\neg, \land, \lor, \to, \leftrightarrow\}$（全体五个联结词）
2. $S_2 = \{\neg, \land, \lor\}$
3. $S_3 = \{\neg, \land\}$
4. $S_4 = \{\neg, \lor\}$
5. $S_5 = \{\neg, \to\}$
6. $S_6 = \{\to, F\}$（F表示恒假命题）
7. $S_7 = \{\uparrow\}$（与非，Sheffer竖线）
8. $S_8 = \{\downarrow\}$（或非，Peirce箭头）

8.3 与非和或非

与非（$\uparrow$）：
$P \uparrow Q \Leftrightarrow \neg(P \land Q)$

或非（$\downarrow$）：
$P \downarrow Q \Leftrightarrow \neg(P \lor Q)$

8.4 完备集间的转换

示例：将 $P \to Q$ 表示为 $S_4 = \{\downarrow\}$ 上的公式

$$\begin{aligned} &P \to Q \\ \Leftrightarrow\ & \neg P \lor Q \\ \Leftrightarrow\ & \neg\neg(\neg P \lor Q) \\ \Leftrightarrow\ & \neg(\neg P \lor Q) \downarrow \text{（整体）} \\ \Leftrightarrow\ & (P \downarrow Q) \downarrow \text{（整体）} \end{aligned}$$

具体推导：

$$\neg P \Leftrightarrow P \downarrow P$$

所以：

$$\begin{aligned} &\neg P \lor Q \\ \Leftrightarrow\ & (P \downarrow P) \lor Q \\ \Leftrightarrow\ & \neg\neg((P \downarrow P) \lor Q) \\ \Leftrightarrow\ & \neg((P \downarrow P) \downarrow Q) \\ \Leftrightarrow\ & ((P \downarrow P) \downarrow Q) \downarrow ((P \downarrow P) \downarrow Q) \end{aligned}$$

九、对偶式

9.1 对偶式的定义

定义：在给定的命题公式A中，将联结词∧换成∨，∨换成∧，特殊变元F和T互换，所得公式A*称为A的对偶式。

性质：A也是A*的对偶式（对偶是相互的）。

9.2 对偶式定理

定理1：设A和A是对偶式，P1,P2,…,Pn是出现在A和A中的原子变元，则：
$A(P_1, P_2, ..., P_n) \Leftrightarrow \neg A^*(\neg P_1, \neg P_2, ..., \neg P_n)$
$A(\neg P_1, \neg P_2, ..., \neg P_n) \Leftrightarrow \neg A^*(P_1, P_2, ..., P_n)$

定理2：设P1,P2,…,Pn是所有出现在命题公式A和B中的原子变元，如果 $A \Leftrightarrow B$，则 $A^* \Leftrightarrow B^*$。

推论：$A \Leftrightarrow T$ 当且仅当 $A^* \Leftrightarrow F$

9.3 利用对偶式求命题的非

步骤（依据定理1）：

1. 消去其他逻辑运算符，只留下¬、∧、∨（T、F）
2. 用括号表示优先级
3. 把A变为A*（∧∨互换、T F互换）
4. 所有变元Pi用¬Pi代入，得到¬A

示例：求 $\neg(P \to Q)$ 的对偶式

$\neg(P \to Q) \Leftrightarrow \neg(\neg P \lor Q) \Leftrightarrow P \land \neg Q$

十、蕴含式

10.1 蕴含式的定义

定义：当且仅当 $P \to Q$ 是一个重言式时，我们称"P蕴含Q"，并记作 $P \Rightarrow Q$。

要点：

• $\Rightarrow$ 是元语言符号，表示蕴含关系
• $P \Rightarrow Q$ 表示 $P \to Q$ 为永真式

10.2 蕴含式的形式

给定蕴含式 $P \to Q$：

等价关系：

• $(P \to Q) \Leftrightarrow (\neg Q \to \neg P)$（原命题等价于逆否命题）
• $(Q \to P) \Leftrightarrow (\neg P \to \neg Q)$（逆命题等价于否命题）

注意：$P \to Q$ 与 $Q \to P$ 不等价（原命题与逆命题不等价）

10.3 蕴含式的定理与证明方法

证明蕴含式 $A \Rightarrow B$ 的方法：

1. 方法一：往证 $A \to B$ 是重言式
2. 方法二：往证 $\neg B \to \neg A$（逆否命题）
3. 方法三：设A为T，往证B为T
4. 方法四：设B为F，往证A为F
5. 方法五：利用蕴含式定理推导
6. 方法六：利用蕴含式性质
7. 方法七：列真值表

注：可以多种方法结合使用

10.4 蕴含式的性质

1. 重言式蕴含重言式：若A为重言式，B为重言式，则 $A \Rightarrow B$
2. 蕴含关系可传递：若 $A \Rightarrow B$ 且 $B \Rightarrow C$，则 $A \Rightarrow C$
3. 结论的合并：若 $A \Rightarrow B$ 且 $A \Rightarrow C$，则 $A \Rightarrow B \land C$
4. 前提的合并：若 $B \Rightarrow A$ 且 $C \Rightarrow A$，则 $B \lor C \Rightarrow A$

十一、最小联结词组

11.1 基本概念

冗余联结词：在一个联结词的集合中，如果一个联结词可以由集合中的其他联结词定义，则称此联结词为冗余联结词。

独立联结词：不是冗余联结词的联结词。

最小联结词组（极小全功能集）：既能表示任意真值函数（不少），又不含冗余联结词（不多）的联结词集合。

11.2 最小联结词组的证明

证明一个联结词集合是最小联结词组：

第一步：证明该集合是完备集

• 其他联结词都可用此集合中的联结词代替（即能表示任意真值函数，不少）

第二步：证明该集合中的联结词不可相互代替

• 该集合中的联结词不可相互代替（即没有冗余，不多）

11.3 常见的最小联结词组

以下联结词集合是最小联结词组：

1. $\{\neg, \land\}$
2. $\{\neg, \lor\}$
3. $\{\neg, \to\}$
4. $\{\uparrow\}$（与非）
5. $\{\downarrow\}$（或非）

证明示例：证明 $\{\neg, \land\}$ 是最小联结词组

第一步：证明是完备集

• $A \lor B \Leftrightarrow \neg(\neg A \land \neg B)$（用¬和∧表示∨）
• 因此 $\{\neg, \land, \lor\}$ 可用 $\{\neg, \land\}$ 表示
• 而 $\{\neg, \land, \lor\}$ 是完备集，所以 $\{\neg, \land\}$ 也是完备集

第二步：证明无冗余

• ¬不能用∧表示（∧是二元联结词，¬是一元联结词）
• ∧不能用¬表示（¬只能改变真值，不能连接两个命题）
• 因此 $\{\neg, \land\}$ 中没有冗余联结词

结论：$\{\neg, \land\}$ 是最小联结词组。

本节小结

• 等值式：$A \Leftrightarrow B$ 表示 $A \leftrightarrow B$ 为重言式
• 重言式与矛盾式相关定理：重言式的合取和析取仍是重言式，置换规则
• 16组基本等值式：必须熟记，特别是蕴含等值式和德摩根律
• 子公式与置换规则：置换规则是等值演算的基础
• 等值演算：通过等值式逐步变形，可判断公式类型、证明等值
• 范式：析取范式和合取范式不唯一
• 主范式：主析取范式和主合取范式唯一，可用真值表法或等值演算法求解
• 对偶式：∧∨互换、T F互换，对偶式定理可用于求命题的非
• 蕴含式：$P \Rightarrow Q$ 表示 $P \to Q$ 为重言式，有7种证明方法
• 蕴含式性质：可传递、结论可合并、前提可合并
• 联结词完备集：$\{\neg, \land\}$、$\{\neg, \lor\}$、$\{\uparrow\}$、$\{\downarrow\}$ 等都是完备集
• 最小联结词组：既是完备集又无冗余联结词的集合

练习题

练习1：证明重言式

题目：证明 $[\neg P \land (P \lor Q)] \to Q$ 是重言式。

证明（等价变换法）：

$$\begin{aligned} &[\neg P \land (P \lor Q)] \to Q \\ \Leftrightarrow\ & \neg[\neg P \land (P \lor Q)] \lor Q \\ \Leftrightarrow\ & [P \lor \neg(P \lor Q)] \lor Q \\ \Leftrightarrow\ & [P \lor (\neg P \land \neg Q)] \lor Q \\ \Leftrightarrow\ & [(P \lor \neg P) \land (P \lor \neg Q)] \lor Q \\ \Leftrightarrow\ & [T \land (P \lor \neg Q)] \lor Q \\ \Leftrightarrow\ & (P \lor \neg Q) \lor Q \\ \Leftrightarrow\ & P \lor (\neg Q \lor Q) \\ \Leftrightarrow\ & P \lor T \\ \Leftrightarrow\ & T \end{aligned}$$

练习2：主析取范式与主合取范式

题目：求公式 $P \to Q$ 的主析取范式和主合取范式。

解：

$P \to Q \Leftrightarrow \neg P \lor Q$

• 成真赋值：00, 01, 11（对应 $m_0, m_1, m_3$）
• 成假赋值：10（对应 $M_2$）

主析取范式：$m_0 \lor m_1 \lor m_3 = (\neg P \land \neg Q) \lor (\neg P \land Q) \lor (P \land Q)$

主合取范式：$M_2 = \neg P \lor Q$

练习3：用与非表示公式

题目：将 $P \to Q$ 用与非联结词 $\uparrow$ 表示。

解：

$P \uparrow Q \Leftrightarrow \neg(P \land Q)$

$\neg P \Leftrightarrow P \uparrow P$

$P \to Q \Leftrightarrow \neg P \lor Q \Leftrightarrow \neg\neg(\neg P \lor Q) \Leftrightarrow \neg(P \land \neg Q)$

$\Leftrightarrow P \uparrow \neg Q \Leftrightarrow P \uparrow (Q \uparrow Q)$

关键术语速查