2.2.2 联结词完备集

2.2.2 联结词完备集

本节对应原书 PDF 第 56–58 页（原书 p37–39）。定义、定理、推论及其证明逐字取自原书；标有「解读」的引用块为 AI 补充。

1. 真值函数

定义 2.12 称 F: \{0, 1\}^n \to \{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^{2^n} 这个指数套指数容易记混。它是这样来的：n 个变项一共有 2^n 行赋值，每一行上的函数值可取 0 或 1，所以函数总数是 2 的「行数」次方，即 2^{2^n}。代进去：1 元 2^2 = 4 个，2 元 2^4 = 16 个，3 元 2^8 = 256 个。

表 2.9

表 2.10（2 元真值函数共 16 个）

解读：表 2.10 的列不是随便排的——把每一列从上往下读成一个 4 位二进制数，它的值正好等于下标。比如 F_5^{(2)} 那一列读作 0101，二进制就是 5。所以这张表不用记，需要哪一列按二进制展开即可。

对于每个真值函数，都可找到许多与之等值的命题公式. 以 2 元真值函数为例，所有矛盾式都与 F_0^{(2)} 等值，所有重言式都与 F_{15}^{(2)} 等值，又如 F_{13}^{(2)} \Leftrightarrow p \to 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\} 是联结词完备集.

解读：这个归纳法的关键在于「把 n+1 元拆成两个 n 元」。G_0 和 G_1 分别是把最后一个变项固定成 0 和 1 得到的结果。最后的公式 (\alpha \wedge \neg p_{n+1}) \vee (\beta \wedge p_{n+1}) 就是「当 p_{n+1} 为 0 时用 \alpha，为 1 时用 \beta」——本质上是在用 \neg、\wedge、\vee 写一个二选一开关。

推论 以下联结词集都是完备集.

(1) S_1 = \{\neg, \wedge, \vee, \to\}.

(2) S_2 = \{\neg, \wedge, \vee, \to, \leftrightarrow\}.

(3) S_3 = \{\neg, \wedge\}.

(4) S_4 = \{\neg, \vee\}.

(5) S_5 = \{\neg, \to\}.

证明 (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).

现在考虑联结词集 \{\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\} 也不是联结词完备集.

解读：这里用的是一个「反证式」的排除法：\{\wedge, \vee\} 只能造出三类公式，而 \neg p 不属于任何一类，所以它表达不出来。注意第三类的论证方式——只用 \wedge 和 \vee 且不含常元的公式是单调的：全 0 赋值得 0，全 1 赋值得 1。而 \neg p 恰好相反（全 0 得 1），因此不可能等值。

在实际应用中，必须采用联结词完备集. 可以根据不同的需要选择不同的联结词完备集，甚至专门设计出所需要的联结词完备集. 例如，在计算机硬件设计中用与非门或者用或非门设计逻辑线路，它们对应两个新的联结词——与非联结词和或非联结词.

定义 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\} 是联结词完备集.

解读：证明思路是「先归约，再表示」。\{\neg, \wedge\} 已经知道是完备集，所以只要证明 \neg 和 \wedge 都能用 \uparrow 单独表达出来，\{\uparrow\} 自然就是完备集。式(2.1) 是核心——它把 \neg 变成了「自己与非自己」，后面两式都要引用它。