2.2.1 等值式与等值演算
本节对应原书 PDF 第 52–57 页（原书 p33–38）。定义、定理、例题及其原解答逐字取自原书；标有「解读」的引用块为 AI 补充。
设公式 A, B 共同含有 n 个命题变项，可能对 A 或 B 有哑元，若 A 与 B 有相同的真值表，则说明在 2^n 种赋值的每个赋值下，A 与 B 的真值都相同。于是等价式 A \leftrightarrow B 应为重言式。
定义 2.11 设 A, B 是两个命题公式，若 A, B 构成的等价式 A \leftrightarrow B 为重言式，则称 A 与 B 是等值的，记作 A \Leftrightarrow B。
定义中给出的符号 \Leftrightarrow 不是联结词，它是用来说明 A 与 B 等值（A \leftrightarrow B 是重言式）的一种记法，因而 \Leftrightarrow 是元语言符号。此记号在下文中频繁出现，千万不要将它与 \leftrightarrow 混为一谈，同时也要注意它与一般等号（=）的区别。
解读：\Leftrightarrow 说的是「两个公式真值表完全一样」这件事本身，它是一个关于公式的判断；\leftrightarrow 是一个联结词，它把两个公式拼成一个新公式。所以 A \Leftrightarrow B 是一个待证明的命题，而 A \leftrightarrow B 只是一个公式。前者写在推导的「元」层面，后者写在公式里面。
下面讨论判断两个公式 A 与 B 是否等值的方法，其中最直接的方法是用真值表法判断 A \leftrightarrow B 是否为重言式。
例 2.11 判断两个公式是否等值：\neg(p \vee q) 与 \neg p \wedge \neg q。
解 用真值表法判断 \neg(p \vee q) \leftrightarrow (\neg p \wedge \neg q) 是否为重言式。此等价式的真值表如表 2.7 所示，从表可知它是重言式，因而 \neg(p \vee q) 与 \neg p \wedge \neg q 等值，即 \neg(p \vee q) \Leftrightarrow (\neg p \wedge \neg q)。
表 2.7
| p | q | \neg p | \neg q | p \vee q | \neg(p \vee q) | \neg p \wedge \neg q | \neg(p \vee q) \leftrightarrow (\neg p \wedge \neg q) |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
其实，在用真值表法判断 A \leftrightarrow B 是否为重言式时，真值表的最后一列（即 A \leftrightarrow B 的真值表的最后结果）可以省略。若 A 与 B 的真值表相同，则 A \Leftrightarrow B；否则，A \not\Leftrightarrow B（用来表示 A 与 B 不等值，\not\Leftrightarrow 也是常用的元语言符号）。
例 2.12 判断下列各组公式是否等值.
(1) p \to (q \to r) 与 (p \wedge q) \to r.
(2) (p \to q) \to r 与 (p \wedge q) \to r.
解 表 2.8 列出了 p \to (q \to r), (p \wedge q) \to r, (p \to q) \to r 的真值表，不难看出 p \to (q \to r) 与 (p \wedge q) \to r 等值，即
而 (p \to q) \to r 与 (p \wedge q) \to r 的真值表不同，因而它们不等值，即
解读：把 \to 理解成「先算括号里的」。左边是先算 p \to q 得到一个值再参与外层的 \to；右边是先把 p 和 q 与起来再推 r。两者的结合顺序不同，所以结果不同——这也是为什么 \to 不满足结合律。
表 2.8
| p | q | r | p \to (q \to r) | (p \wedge q) \to r | (p \to q) \to r |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 |
证明两个命题公式等值的另一种方法是等值演算. 根据已知的等值式推演出与原命题公式等值的新的命题公式的过程称作等值演算. 下面给出 24 个重要的等值式，希望读者牢牢记住它们. 在下面公式中出现的 A, B, C 仍然是元语言符号，它们代表任意的命题公式.
(1) \neg\neg A \Leftrightarrow A. 双重否定律
(2) A \Leftrightarrow A \vee A. } 幂等律
(3) A \Leftrightarrow A \wedge A.
(4) A \vee B \Leftrightarrow B \vee A. } 交换律
(5) A \wedge B \Leftrightarrow B \wedge A.
(6) (A \vee B) \vee C \Leftrightarrow A \vee (B \vee C). } 结合律
(7) (A \wedge B) \wedge C \Leftrightarrow A \wedge (B \wedge C).
(8) A \vee (B \wedge C) \Leftrightarrow (A \vee B) \wedge (A \vee C). } 分配律
(9) A \wedge (B \vee C) \Leftrightarrow (A \wedge B) \vee (A \wedge C).
(10) \neg(A \vee B) \Leftrightarrow \neg A \wedge \neg B. } 德摩根律
(11) \neg(A \wedge B) \Leftrightarrow \neg A \vee \neg B.
(12) A \vee (A \wedge B) \Leftrightarrow A. } 吸收律
(13) A \wedge (A \vee B) \Leftrightarrow A.
(14) A \vee 1 \Leftrightarrow 1. } 零律
(15) A \wedge 0 \Leftrightarrow 0.
(16) A \vee 0 \Leftrightarrow A. } 同一律
(17) A \wedge 1 \Leftrightarrow A.
(18) A \vee \neg A \Leftrightarrow 1. 排中律
(19) A \wedge \neg A \Leftrightarrow 0. 矛盾律
(20) A \to B \Leftrightarrow \neg A \vee B. 蕴涵等值式
(21) A \leftrightarrow B \Leftrightarrow (A \to B) \wedge (B \to A). 等价等值式
(22) A \to B \Leftrightarrow \neg B \to \neg A. 假言易位
(23) A \leftrightarrow B \Leftrightarrow \neg A \leftrightarrow \neg B. 等价否定等值式
(24) (A \to B) \wedge (A \to \neg B) \Leftrightarrow \neg A. 归谬论
解读：这 24 条不用背成 24 个孤立事实。记住三条主线就够推：①\to 和 \leftrightarrow 都能消掉（(20)(21)）；②\neg 进括号要换 \wedge/\vee（(10)(11)）；③1 和 0 有吞噬/恒等两种行为（(14)–(17)）。剩下的多半是名字在提示内容——「幂等」「交换」「结合」「分配」跟算术里的同名规律一致。
上述 24 个等值式都不难用真值表验证，这里略去，请读者自己验证. 在以上给出的 24 个重要等值式中，由于 A, B, C 可以代表任意的公式，因而以上各等值式都是用元语言符号书写的，称这样的等值式为等值式模式，每个等值式模式都给出了无穷多个同类型的具体等值式. 例如，在蕴涵等值式中，取 A = p, B = q 时，得等值式
当取 A = p \vee q \vee r, B = p \wedge q 时，得等值式
还可以构造蕴涵等值式的其他具体的等值式. 这些具体的等值式被称为原来的等值式模式的代入实例.
解读：等值式模式里的 A, B, C 是「占位符」，代入实例就是把占位符换成具体公式。所以 (20) 一条其实覆盖了无穷多条等值式——包括那些看起来完全不同、但结构相同的式子。
在等值演算过程中，要不断地使用一条重要的规则，其内容如下.
置换规则 设 \Phi(A) 是含公式 A 的命题公式，\Phi(B) 是用公式 B 置换了 \Phi(A) 中所有的 A 后得到的命题公式，若 B \Leftrightarrow A，则 \Phi(B) \Leftrightarrow \Phi(A).
例如，在公式 (p \to q) \to r 中，可用 \neg p \vee q 置换其中的 p \to q，由蕴涵等值式可知，p \to q \Leftrightarrow \neg p \vee q，所以，
在这里，使用了置换规则. 如果再一次地用蕴涵等值式及置换规则，又会得到
如果再用德摩根律及置换规则，又会得到
再用分配律及置换规则，又会得到
将以上过程连在一起，得到
解读：置换规则是等值演算的「合法性依据」。它保证：只要某处子公式被换成了一个与它等值的公式，整个大公式仍然与原来等值。所以演算时你只管找一处能套用 24 条等值式的地方去改，不用担心中间步骤改变原意。原书说「以下演算中置换规则均不标出」，正是因为每一步都默认在用它。
公式之间的等值关系具有自反性、对称性和传递性，所以上述演算中得到的 5 个公式彼此之间都是等值的. 在演算的每一步都用到了置换规则，因而在以下演算中，置换规则均不标出.
下面用实例说明等值演算的用途.
例 2.13 用等值演算法验证等值式：
证明 可以从左边开始演算，也可以从右边开始演算. 现在从右边开始演算.
所以，原等值式成立. 读者也可以从左边开始演算.
解读：这条演算的关键是第二步——两个「或」式相乘时用分配律把 r 提出来。为什么要提出来？因为右边的目标里 r 只出现一次，而左边出现了两次，必须先把重复的 r 合并掉，才可能变回 (p \vee q) \to r。
例 2.13 说明，用等值演算法可以验证两个公式等值. 但一般情况下，不能用等值演算法直接验证两个公式不等值.
例 2.14 证明：
证明 方法一：真值表法. 读者自己证明.
方法二：观察法. 易知，010（p = 0, q = 1, r = 0）是 (p \to q) \to r 的成假赋值，而 010（p = 0, q = 1, r = 0）是 p \to (q \to r) 的成真赋值，所以原不等值式成立.
方法三：设 A = (p \to q) \to r, B = p \to (q \to r).
先将 A, B 通过等值演算化成容易观察真值的情况，再进行判断.
容易观察到，000, 010 是 A 的成假赋值，而它们是 B 的成真赋值.
解读：证明「不等值」只要找到一个反例赋值即可——这正是观察法比真值表法省事的原因。A 化成 (p \wedge \neg q) \vee r 后一眼能看出：要让 A 为假，需要 r = 0 且 p \wedge \neg q = 0；而 B 化成三个项相或后，只要有一项为真就为真。取 p=0,q=1,r=0 时 A 为假、B 为真，反例成立。
例 2.15 用等值演算法判断下列公式的类型.
(1) (p \to q) \wedge p \to q.
(2) \neg(p \to (p \vee q)) \wedge r.
(3) p \wedge (((p \vee q) \wedge \neg p) \to q).
解 在以下演算中没有写出所用的基本等值式，请读者自己填上.
(1) (p \to q) \wedge p \to q
最后结果说明(1)中公式是重言式.
(2) \neg(p \to (p \vee q)) \wedge r
最后结果说明(2)中公式是矛盾式.
(3) p \wedge (((p \vee q) \wedge \neg p) \to q)
最后结果说明(3)中公式不是重言式，00, 01 都是成假赋值. 并且也不是矛盾式，因为 10, 11 都是成真赋值.
解读：这三小问演示了等值演算判断类型的套路——一路化简到底，最后得到 1 就是重言式，得到 0 就是矛盾式，得到既不是 1 也不是 0 的式子（这里是 p）就是可满足式。最后一问化简成 p 后，还要回头说明它既可假又可真，才能排除另外两种类型。
等值演算中各步得出的等值式所含命题变项可能不一样多，如(3)中最后一步不含 q，此时将 q 看成它的哑元，考虑赋值时将哑元也算在内，因而赋值的长度为 2，这样，可将(3)中各步的公式都看成含命题变项 p, q 的公式，在写真值表时已经讨论过类似的问题.
解读：哑元的意思是「公式里没出现，但真值表里仍要占一列」。如果不把 q 算进去，(3) 最后得到 p 就只有 1 位赋值，会被误判成「只有 0 是成假赋值」；补上哑元后才有 00、01 两个成假赋值，与 (3) 的结论一致。