表 2.6 列出 4 个公式的真值表，中间过程省略了.从表中看出，(1)与(3)有相同的真值表，(2)与(4)有相同的真值表.
表 2.6
| p | q | r | p\rightarrow q | \neg q\vee r | (\neg p\vee q)\wedge((p\wedge r)\rightarrow p) | (q\rightarrow r)\wedge(p\rightarrow p) |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
本节对应原书 PDF 第 48–54 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。
2.2.1 等值式与等值演算
设公式 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 混为一谈，同时也要注意它与一般等号 = 的区别.
下面讨论判断两个公式 A 与 B 是否等值的方法，其中最直接的方法是用真值表法判断 A\leftrightarrow B 是否为重言式.
解读：\leftrightarrow 是公式内部的联结词，写出来仍是公式；\Leftrightarrow 是讨论公式时的断言符号，表示"两边的真值表逐行相同"。所以 A\leftrightarrow 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\nLeftrightarrow B(用来表示 A 与 B 不等值，\nLeftrightarrow 也是常用的元语言符号).
例 2.12 判断下列各组公式是否等值.
(1) p\rightarrow(q\rightarrow r) 与 (p\wedge q)\rightarrow r.
(2) (p\rightarrow q)\rightarrow r 与 (p\wedge q)\rightarrow r.
解 表 2.8 中列出了 p\rightarrow(q\rightarrow r)，(p\wedge q)\rightarrow r，(p\rightarrow q)\rightarrow r 的真值表，不难看出 p\rightarrow(q\rightarrow r) 与 (p\wedge q)\rightarrow r 等值，即
而 (p\rightarrow q)\rightarrow r 与 (p\wedge q)\rightarrow r 的真值表不同，因而它们不等值，即
表 2.8
| p | q | r | p\rightarrow(q\rightarrow r) | (p\wedge q)\rightarrow r | (p\rightarrow q)\rightarrow 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. \Big\} 幂等律
(3) A\Leftrightarrow A\wedge A.
(4) A\vee B\Leftrightarrow B\vee A. \Big\} 交换律
(5) A\wedge B\Leftrightarrow B\wedge A.
(6) (A\vee B)\vee C\Leftrightarrow A\vee(B\vee C). \Big\} 结合律
(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). \Big\} 分配律
(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. \Big\} 德摩根律
(11) \neg(A\wedge B)\Leftrightarrow\neg A\vee\neg B.
(12) A\vee(A\wedge B)\Leftrightarrow A. \Big\} 吸收律
(13) A\wedge(A\vee B)\Leftrightarrow A.
(14) A\vee 1\Leftrightarrow 1. \Big\} 零律
(15) A\wedge 0\Leftrightarrow 0.
(16) A\vee 0\Leftrightarrow A. \Big\} 同一律
(17) A\wedge 1\Leftrightarrow A.
(18) A\vee\neg A\Leftrightarrow 1. 排中律
(19) A\wedge\neg A\Leftrightarrow 0. 矛盾律
(20) A\rightarrow B\Leftrightarrow\neg A\vee B. 蕴涵等值式
(21) A\leftrightarrow B\Leftrightarrow(A\rightarrow B)\wedge(B\rightarrow A). 等价等值式
(22) A\rightarrow B\Leftrightarrow\neg B\rightarrow\neg A. 假言易位
(23) A\leftrightarrow B\Leftrightarrow\neg A\leftrightarrow\neg B. 等价否定等值式
(24) (A\rightarrow B)\wedge(A\rightarrow\neg B)\Leftrightarrow\neg A. 归谬论
解读：这 24 条是按"名字"成组记的，记住组名比逐条背更省力：幂等、交换、结合、分配管的是 \wedge/\vee 的代数性质；零律、同一律、排中律、矛盾律管的是与常元 0、1 的运算；蕴涵等值式、等价等值式、假言易位、归谬论则是消去 \rightarrow 和 \leftrightarrow 的通道。
上述 24 个等值式都不难用真值表验证.这里略去，请读者自己验证.在以上给出的 24 个重要等值式中，由于 A,B,C 可以代表任意的公式，因而以上各等值式都是用元语言符号书写的，称这样的等值式为等值式模式，每个等值式模式都给出了无穷多个同类型的具体等值式.例如，在蕴涵等值式中，取 A=p,B=q 时，得等值式
当取 A=p\vee q\vee r,B=p\wedge q 时，得等值式
还可以构造蕴涵等值式的其他具体的等值式.这些具体的等值式被称为原来的等值式模式的代入实例.
在等值演算过程中，要不断地使用一条重要的规则，它的内容如下.
置换规则 设 \Phi(A) 是含公式 A 的命题公式，\Phi(B) 是用公式 B 置换了 \Phi(A) 中所有的 A 后得到的命题公式，若 B\Leftrightarrow A，则 \Phi(B)\Leftrightarrow\Phi(A).
例如，在公式 (p\rightarrow q)\rightarrow r 中，可用 \neg p\vee q 置换其中的 p\rightarrow q，由蕴涵等值式可知，p\rightarrow q\Leftrightarrow\neg p\vee q，所以，
在这里，使用了置换规则.如果再一次地用蕴涵等值式及置换规则，又会得到
如果再用德摩根律及置换规则，又会得到
再用分配律及置换规则，又会得到
将以上过程连在一起，得到
公式之间的等值关系具有自反性、对称性和传递性，所以上述演算中得到的 5 个公式彼此之间都是等值的.在演算的每一步都用到了置换规则，因而在以下的演算中，置换规则均不标出.
下面用实例说明等值演算的用途.
例 2.13 用等值演算法验证等值式：
证明 可以从左边开始演算，也可以从右边开始演算.现在从右边开始演算.
所以，原等值式成立.读者亦可以从左边开始演算验证.
例 2.13 说明，用等值演算法可以验证两个公式等值.但一般情况下，不能用等值演算法直接验证两个公式不等值.
例 2.14 证明：
证明 方法一：真值表法.读者自己证明.
方法二：观察法.易知，010 是 (p\rightarrow q)\rightarrow r 的成假赋值，而 010 是 p\rightarrow(q\rightarrow r) 的成真赋值，所以原不等式成立.
方法三：设 A=(p\rightarrow q)\rightarrow r,B=p\rightarrow(q\rightarrow r).
先将 A,B 通过等值演算化成容易观察真值的情况，再进行判断.
容易观察到，000,010 是 A 的成假赋值，而它们是 B 的成真赋值.
解读：等值演算只能证明"相等"，不能证明"不等"。要断定两个公式不等值，得先把两边都化简到便于观察的形式，再指出一个具体赋值使两边真值不同——例 2.14 的方法三正是这条思路。
例 2.15 用等值演算法判断下列公式的类型.
(1) (p\rightarrow q)\wedge p\rightarrow q.
(2) \neg(p\rightarrow(p\vee q))\wedge r.
(3) p\wedge(((p\vee q)\wedge\neg p)\rightarrow q).
解 在以下的演算中没有写出所用的基本等值式，请读者自己填上.
(1)
最后结果说明(1)中公式是重言式.
(2) \neg(p\rightarrow(p\vee q))\wedge r
最后结果说明(2)中公式是矛盾式.
(3) p\wedge(((p\vee q)\wedge\neg p)\rightarrow q)
最后结果说明(3)中公式不是重言式，00,01 都是成假赋值.并且也不是矛盾式，因为 10,11 都是成真赋值.
等值演算中各步得出的等值式所含命题变项可能不一样多，如(3)中最后一步不含 q，此时将 q 看成它的哑元，考虑赋值时将哑元也算在内，因而赋值的长度为 2，这样，可将(3)中各步的公式都看成含命题变项 p,q 的公式，在写真值表时已经讨论过类似的问题.
解读：化简结果只含 p 并不说明 q 消失了，而是说明公式的真值不再依赖 q——q 成了哑元。判类型时仍要按"含哪些变项"统一赋值长度，否则会把哑元误当成自由变项。
2.2.2 联结词完备集
1. 真值函数
定义 2.12 称 F:\{0,1\}^n\rightarrow\{0,1\} 为 n 元真值函数.
在这个定义中，F 的自变量为 n 个命题变项，定义域为 \{0,1\}^n=\{00\cdots 0,00\cdots 1,\cdots,11\cdots 1\}，即所有由 0,1 组成的长度为 n 的符号串，值域为 \{0,1\}.n 个命题变项共可构成 2^{2^n} 个不同的真值函数.1 元真值函数共有 4 个，见表 2.9 所示.2 元真值函数共有 16 个，见表 2.10 所示.3 元真值函数共有 2^{2^3}=256 个.
表 2.9
| p | F_0^{(1)} | F_1^{(1)} | F_2^{(1)} | F_3^{(1)} |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
表 2.10
| p | q | F_0^{(2)} | F_1^{(2)} | F_2^{(2)} | F_3^{(2)} | F_4^{(2)} | F_5^{(2)} | F_6^{(2)} | F_7^{(2)} |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| p | q | F_8^{(2)} | F_9^{(2)} | F_{10}^{(2)} | F_{11}^{(2)} | F_{12}^{(2)} | F_{13}^{(2)} | F_{14}^{(2)} | F_{15}^{(2)} |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
对于每个真值函数，都可找到许多与之等值的命题公式.以 2 元真值函数为例，所有矛盾式都与 F_0^{(2)} 等值，所有的重言式都与 F_{15}^{(2)} 等值，又如 F_{13}^{(2)}\Leftrightarrow p\rightarrow q\Leftrightarrow(\neg p\vee q)\Leftrightarrow\neg(p\wedge\neg q)\Leftrightarrow(\neg p\wedge\neg q)\vee(\neg p\wedge q)\vee(p\wedge q)\Leftrightarrow\cdots.
2. 联结词完备集
定义 2.13 设 S 是一个联结词集合，如果任何 n(n\geqslant 1) 元真值函数都可以由仅含 S 中的联结词构成的公式表示，则称 S 是联结词完备集.
定理 2.1 S=\{\neg,\wedge,\vee\} 是联结词完备集.
证明 用数学归纳法证明：任意的 n 元真值函数都可以用仅含 \{\neg,\wedge,\vee\} 中联结词的公式表示.
归纳基础：当 n=1 时，有 4 个 1 元真值函数：F_0^{(1)}\Leftrightarrow\neg p\wedge p，F_1^{(1)}\Leftrightarrow p，F_2^{(1)}\Leftrightarrow\neg p，F_3^{(1)}\Leftrightarrow\neg p\vee p，它们都可以用仅含 \{\neg,\wedge,\vee\} 中联结词的公式表示.
归纳步骤：假设任何 n(n\geqslant 1) 元真值函数都可以用仅含 \{\neg,\wedge,\vee\} 中联结词的公式表示，设 G 是任意一个 n+1 元真值函数.令 G_0(p_1,p_2,\cdots,p_n)=G(p_1,p_2,\cdots,p_n,0)，G_1(p_1,p_2,\cdots,p_n)=G(p_1,p_2,\cdots,p_n,1).G_0 和 G_1 是两个 n 元真值函数，根据归纳假设，它们都可以用仅含 \{\neg,\wedge,\vee\} 中联结词的公式表示，即存在仅含 \{\neg,\wedge,\vee\} 中联结词的公式 \alpha 和 \beta，使得 G_0\Leftrightarrow\alpha，G_1\Leftrightarrow\beta.于是
因此，任何 n+1 元真值函数都可以用仅含 \{\neg,\wedge,\vee\} 中联结词的公式表示.得证 \{\neg,\wedge,\vee\} 是联结词完备集.
推论 以下联结词集都是完备集：
(1) S_1=\{\neg,\wedge,\vee,\rightarrow\}.
(2) S_2=\{\neg,\wedge,\vee,\rightarrow,\leftrightarrow\}.
(3) S_3=\{\neg,\wedge\}.
(4) S_4=\{\neg,\vee\}.
(5) S_5=\{\neg,\rightarrow\}.
证明 (1)和(2)的成立是显然的.
(3) 由于 S=\{\neg,\wedge,\vee\} 是联结词完备集，因而任何真值函数都可以由仅含 S 中的联结词的公式表示.同时对于任意公式 A,B，A\vee B\Leftrightarrow\neg\neg(A\vee B)\Leftrightarrow\neg(\neg A\wedge\neg B)，因而任意真值函数都可以由仅含 S_3=\{\neg,\wedge\} 中的联结词的公式表示，所以 S_3 是联结词完备集.
类似可以证明(4)与(5)。
解读：完备集的意义是"这个联结词集合的表达能力已经够用"。由 \{\neg,\wedge\} 完备推出 \{\neg,\vee\}、\{\neg,\rightarrow\} 完备，靠的都是先把其中一个联结词用另一个表示出来；而 \{\wedge,\vee\} 不完备，正是因为它无论如何都表示不出 \neg p.
现在考虑联结词集 {\wedge,\vee} 是不是完备的。对于 {\wedge,\vee} 上的命题公式，若公式中含有常元 0 或 1，总可以用同一律和零律消去 0 和 1，最后得到的等值的公式只有 3 种可能：
(1) 0；
(2) 1；
(3) 不含 0 和 1 的仅含联结词 \wedge 和 \vee 的公式。
前两种显然不与 F_2^{(1)}\Leftrightarrow\neg p 等值。对于(3)，给所有的变元赋值 0，公式的值为 0；给所有的变元赋值 1，公式的值为 1，因此它也不可能与 F_2^{(1)} 等值。可见，F_2^{(1)} 不能用仅含 \{\wedge,\vee\} 中联结词的公式表示。所以，\{\wedge,\vee\} 不是联结词完备集。显然 \{\wedge\} 和 \{\vee\} 也不是联结词完备集。
在实际应用中，必须采用联结词完备集。可以根据不同的需要选择不同的联结词完备集，甚至专门设计出所需要的联结词完备集。例如，在计算机硬件设计中用与非门或者用或非门设计逻辑线路，它们对应两个新的联结词——与非联结词和或非联结词。
定义 2.14 设 p,q 为两个命题，复合命题"p 与 q 的否定式"("p 或 q 的否定式")称作 p,q 的与非式(或非式)，记作 p\uparrow q(p\downarrow q)。符号 \uparrow(\downarrow) 称作与非联结词(或非联结词)。p\uparrow q 为真当且仅当 p 与 q 不同时为真(p\downarrow q 为真当且仅当 p 与 q 同时为假)。
由定义不难看出
定理 2.2 \{\uparrow\},\{\downarrow\} 都是联结词完备集。
证明 已知 \{\neg,\wedge\} 为联结词完备集，因而只需证明 \neg 和 \wedge 都可以由 \uparrow 表示即可。而
得证 \{\uparrow\} 是联结词完备集。此外
类似可证 \{\downarrow\} 是联结词完备集。
解读：定理 2.2 只证 \neg 和 \wedge 都能用 \uparrow 表示，就足以断言 \{\uparrow\} 完备——因为 \{\neg,\wedge\} 已经是完备集，能表示它们俩就等于能表示一切。\uparrow 与 \downarrow 的这种"单个联结词打天下"的性质，正是硬件里只用一种门电路搭出全部逻辑线路的依据。