2.3 范式

2.3 范　式

本节对应原书 PDF 第 58–68 页（原书 p39–49）。定义、定理、例题及其原解答逐字取自原书；原书的解释性文字为 AI 通俗化改写，标有「解读」的引用块为 AI 补充。

本节用等值演算把命题公式化成联结词集 \{\neg, \wedge, \vee\} 中的两种规范形式——主析取范式与主合取范式。它们的价值在于：一个公式的真值表所能提供的信息，这两种形式都能提供。

2.3.1 析取范式与合取范式

定义 2.15 命题变项及其否定统称作文字. 仅由有限个文字构成的析取式称作简单析取式. 仅由有限个文字构成的合取式称作简单合取式.

按所含文字的个数，简单析取式与简单合取式的例子如下：

单个文字同时算简单析取式和简单合取式，两种身份不冲突。后文统一用 A_1, A_2, \cdots, A_s 泛指 s 个简单析取式或 s 个简单合取式。

一个简单析取式里只要同时出现某个命题变项 p_j 和它的否定式 \neg p_j，就含了 p_j \vee \neg p_j 这一段，整个式子必为重言式。反过来也成立：若 A_i 里没有任何一对「变项 + 它的否定式」，就让不带否定号的变项全取 0、带否定号的变项全取 1，这组赋值使每个文字都为假，于是 A_i 为假，与它是重言式矛盾。简单合取式同理：它含一对「变项 + 它的否定式」时是矛盾式，反之亦然。

定理 2.3 （1）一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式.

（2）一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定式.

定义 2.16 （1）由有限个简单合取式构成的析取式称为析取范式.

（2）由有限个简单析取式构成的合取式称为合取范式.

（3）析取范式与合取范式统称为范式.

把 s 个简单合取式用 \vee 连起来，得到的 A = A_1 \vee A_2 \vee \cdots \vee A_s 就是析取范式。例如取 A_1 = p \wedge \neg q，A_2 = \neg q \wedge \neg r，A_3 = p，则

把 s 个简单析取式用 \wedge 连起来，得到的 A = A_1 \wedge A_2 \wedge \cdots \wedge A_s 就是合取范式。例如取 A_1 = p \vee q \vee r，A_2 = \neg p \vee \neg q，A_3 = r，则

同一个公式可以两种身份兼有。\neg p \wedge q \wedge r 既是一个简单合取式构成的析取范式，又是由 3 个简单析取式构成的合取范式；p \vee \neg q \vee r 既是含 3 个简单合取式的析取范式，又是含一个简单析取式的合取范式。

析取范式和合取范式的性质如下。

定理 2.4 （1）一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式.

（2）一个合取范式是重言式当且仅当它的每个简单析取式都是重言式.

任何公式都能化成等值的析取范式和合取范式。观察范式的形状，需要满足三件事。第一，范式里不出现联结词 \to 与 \leftrightarrow；由蕴涵等值式与等价等值式可知，

因而在等值的条件下，可消去任何公式中的联结词 \to 和 \leftrightarrow.

第二，范式里不出现下面这些形状的公式：

对它们用双重否定律和德摩根律，得到

第三，析取范式中不出现下面这种形状的公式：

合取范式中不出现这种形状的公式：

利用分配律，可得

有了式(2.4)～式(2.6)，任一公式都能化成与之等值的析取范式或合取范式，于是有下面定理。

定理 2.5（范式存在定理） 任一命题公式都存在与之等值的析取范式与合取范式.

求给定公式范式的步骤如下：

① 消去联结词 \to, \leftrightarrow.

② 消去否定号（利用双重否定律）或内移（利用德摩根律）.

③ 利用分配律：利用 \wedge 对 \vee 的分配律求析取范式，\vee 对 \wedge 的分配律求合取范式.

例 2.16 求下面公式的析取范式与合取范式：

解 为了清晰和无误，演算中利用交换律，使得每个简单析取式或简单合取式中命题变项的出现都是按字典顺序，这对下文中求主范式更为重要.

① 首先求析取范式.

经过两步演算，就得到了含 2 个简单合取式的析取范式.

② 求合取范式.

经过 3 步演算，得到了含 2 个简单析取式的合取范式.

在①与②的演算中，头两步是相同的. 演算中都用到蕴涵等值式和德摩根律. ②中用到了分配律.

把恒假的项、恒真的项往里塞，结果仍然合法：(p \wedge \neg q) \vee \neg r \vee (q \wedge \neg q) 和 (p \vee \neg r) \wedge (\neg q \vee \neg r) \wedge (r \vee \neg r) 同样分别是 \neg (p \to q) \vee \neg r 的析取范式和合取范式。可见一个公式的析取范式与合取范式并不唯一。

解读：不唯一的根源在于「化简到什么程度」没有硬性要求。析取范式只要求每一项都是简单合取式，既不要求每项都是极小项，也不要求删掉多余的项——\vee (q \wedge \neg q) 是恒假的累赘，加上它仍然满足定义。

2.3.2 主析取范式与主合取范式

2.3.1 节给出的范式不唯一。本小节要找的是唯一的范式形式，这就是主析取范式与主合取范式。

1. 概念

定义 2.17 在含有 n 个命题变项的简单合取式（简单析取式）中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第 i 个命题变项或它的否定式出现在从左算起的第 i 位上（若命题变项无角标，就按字典顺序排列），称这样的简单合取式（简单析取式）为极小项（极大项）.

n 个命题变项一共能造出 2^n 个不同的极小项：每个变项在极小项里要么以原形出现、要么以否定式出现，逐项各选一种，组合起来正好 2^n 种。每个极小项只在一组赋值下为真，把这组赋值对应的二进制数转成十进制记作 i，该极小项就记作 m_i。极大项完全对称：同样是 2^n 个，每个只在唯一一组赋值下为假，那组赋值的十进制数就是它的角标，记作 M_i。

p, q 与 p, q, r 造出的极小项、极大项分别列在表 2.11 和表 2.12 中，便于对照记忆。

表 2.11（原书左右两栏，此处合并为一张表）

表 2.12（同上）

极小项与极大项之间的对应关系由下面定理给出。

定理 2.6 设 m_i 与 M_i 是命题变项 p_1, p_2, \cdots, p_n 形成的极小项和极大项，则

定义 2.18 若由 n 个命题变项构成的析取范式（合取范式）中所有的简单合取式（简单析取式）都是极小项（极大项），则称该析取范式（合取范式）为主析取范式（主合取范式）.

主析取范式与主合取范式的求法如下。

设所给定公式为含 n 个命题变项的公式 A，求 A 的主析取范式，按下面步骤进行：

① 求 A 的析取范式 A' = B_1 \vee B_2 \vee \cdots \vee B_s，其中 B_j 为简单合取式，j = 1, 2, \cdots, s.

② 若 A' 中的某简单合取式 B_j 中既不含命题变项 p_i，又不含 \neg p_i，则将 B_j 如下展开：

继续这一过程，直到 B_1, B_2, \cdots, B_s 都被展成长度为 n 的极小项的析取式为止.

③ 将重复出现的命题变项、矛盾式、重复出现的极小项都按幂等律、同一律等「消去」. 即用 p 代替 p \vee p，0 代替 p \wedge \neg p，m_i 代替 m_i \vee m_i.

④ 将极小项按角标从小到大的顺序排列，并可以用 \sum 表示，如 m_1 \vee m_3 \vee m_5 记为 \sum(1,3,5)，当然也可以不用 \sum 表示.

求主合取范式的步骤与上面完全对称，简述如下：

① 求 A 的合取范式 A' = B_1 \wedge B_2 \wedge \cdots \wedge B_r，其中 B_j 为简单析取式，j = 1, 2, \cdots, r.

② 利用 B_j = B_j \vee 0 \Leftrightarrow B_j \vee (p_i \wedge \neg p_i)

将 B_1, B_2, \cdots, B_r 都转化成长度为 n 的极大项的合取式.

③ 将重复出现的命题变项、重言式、重复出现的极大项按幂等律、排中律等「消去」.

④ 将极大项按角标从小到大顺序排序，并可以用 \prod 简单表示. 例如，M_0 \wedge M_3 \wedge M_7 可简记为 \prod(0,3,7).

定理 2.7 任何命题公式都存在与之等值的主析取范式和主合取范式，并且是唯一的.

证明 上面叙述的求主析取范式和求主合取范式的方法实际上已经证明了主析取范式和主合取范式的存在性. 现在证明主析取范式的唯一性. 注意到公式 A 的主析取范式中的每一个极小项 m_i 的下标 i 的二进制表示是 A 的一个成真赋值. 假设 A 有两个不同的主析取范式 D_1 和 D_2，不妨设 D_1 中包含极小项 m_i，而 D_2 中不包含极小项 m_i. 那么，i 的二进制表示是 D_1 的成真赋值和 D_2 的成假赋值. 这与 D_1 和 D_2 都是 A 的主析取范式矛盾，所以公式 A 只可能有唯一的一个主析取范式. 主合取范式的唯一性可以类似证明，只需把极小项换成极大项，并交换成真赋值与成假赋值.

解读：定理 2.7 的两半证明难度不同。存在性由求法本身给出——步骤①②③④对任何公式都能执行完。唯一性才需要证明，用的正是极小项下标与成真赋值的一一对应：同一个公式不可能既在 i 行取真又取假。

例 2.17 求例 2.16 中公式 \neg(p \to q) \vee \neg r 的主析取范式与主合取范式.

解 先求主析取范式.

由例 2.16 已求出该公式的析取范式为

其中简单合取式 p \wedge \neg q 与 \neg r 都不是极小项. 按步骤②将它们都化成极小项的析取式：

由此可知，(p \wedge \neg q) 派生两个长度为 3（A 中命题变项数）的极小项 m_4 与 m_5.

而

于是，按步骤③和④可得

由例 2.16 中②可知，公式的合取范式已求出，即

其中的简单析取式都不是极大项，求主合取范式，应将它们派生成极大项.

于是，主合取范式为

由上面的计算可以看出，长度为 k（含 k 个文字）的简单合取式派生出主析取范式中的 2^{n-k} 个极小项. 例如，n = 3 时，由 q，(p \wedge \neg r) 派生的极小项分别为

上面的演算省略了同一律、排中律这些中间步骤；熟悉之后可以更快地写出主析取范式，主合取范式同理。

例 2.18 （1）已知公式 A 含两个命题变项 p, q，且析取范式为 p \vee \neg q，求主析取范式.

（2）已知公式 B 含两个命题变项 p, q，且合取范式为 \neg p \wedge q，求主合取范式.

（3）已知公式 C 含 3 个命题变项 p, q, r，且析取范式为 (\neg p \wedge q) \vee (\neg p \wedge \neg q \wedge r) \vee r，求主析取范式.

（4）已知公式 D 含 3 个命题变项 p, q, r，且合取范式为 \neg p \wedge (p \vee q \vee \neg r)，求主合取范式.

解 用快速方法求解.

（1）

（2）

（3）

（4）

2. 讨论

下面看主析取范式能派什么用场（主合取范式完全对称，不再重复）。真值表能表达的关于公式以及公式之间关系的信息，主析取范式都能表达。

1）求公式的成真与成假赋值

若公式 A 中含 n 个命题变项，A 的主析取范式含 s（0 \leqslant s \leqslant 2^n）个极小项，则 A 有 s 个成真赋值，它们是所含极小项角标的二进制表示，其余 2^n - s 个赋值都是成假赋值.

例如，在例 2.18 中，A 的成真赋值为 00, 10, 11，当然成假赋值为 01. C 的成真赋值为 001, 010, 011, 101 和 111，而成假赋值为 000, 100 和 110.

2）判断公式的类型

设公式 A 中含 n 个命题变项，容易看出：

（1）A 为重言式当且仅当 A 的主析取范式含全部 2^n 个极小项.

（2）A 为矛盾式当且仅当 A 的主析取范式不含任何极小项，此时，规定 A 的主析取范式为 0.

（3）A 为可满足式当且仅当 A 的主析取范式中至少含一个极小项.

例 2.19 用公式的主析取范式判断下面公式的类型.

（1）\neg(p \to q) \wedge q.

（2）p \to (p \vee q).

（3）(p \vee q) \to r.

解 注意，（1）和（2）中公式含两个命题变项，演算中极小项含两个文字，而（3）中公式含 3 个命题变项，因而极小项中应含 3 个文字.

（1）

这说明（1）中公式是矛盾式.

（2）

含两个命题变项的公式的主析取范式含全部（2^2 个）极小项，这说明该公式为重言式.

其实演算到第一步就已经知道该公式等值于 1，可以直接断定它是重言式，再按命题变项个数把全部极小项写出来即可。即

（3）

易知，该公式是可满足的，但不是重言式，因为它的主析取范式没含全部（8 个）极小项.

3）判断两个命题公式是否等值

设公式 A, B 共含有 n 个命题变项，按 n 个命题变项求出 A 与 B 的主析取范式 A' 与 B'. 若 A' = B'，则 A \Leftrightarrow B，否则 A \not\Leftrightarrow B.

例 2.20 判断下面两组公式是否等值.

（1）p 与 (p \wedge q) \vee (p \wedge \neg q).

（2）(p \to q) \to r 与 (p \wedge q) \to r.

解 （1）两公式共含两个命题变项，因而极小项含两个文字.

另一公式

所以

（2）两公式都含命题变项 p, q, r，因而极小项含 3 个文字. 经过演算可知

所以

4）应用主析取范式分析和解决实际问题

例 2.21 某科研所要从 3 名科研骨干 A, B, C 中挑选 1~2 名出国进修. 由于工作需要，选派时要满足以下条件：

（1）若 A 去，则 C 同去.

（2）若 B 去，则 C 不能去.

（3）若 C 不去，则 A 或 B 可以去.

问所里应如何选派他们？

解 设 p：派 A 去

q：派 B 去

r：派 C 去

由已知条件可得公式

经过演算可得

这是主析取范式，根据它的成真赋值，选派方案有以下 3 种：

（1）p = 0, q = 0, r = 1，即 C 去，而 A, B 都不去.

（2）p = 0, q = 1, r = 0，即 B 去，而 A, C 都不去.

（3）p = 1, q = 0, r = 1，即 A, C 都去，而 B 不去.

下面再看命题公式在设计控制电路中的应用。逻辑运算可以用电子元件物理实现，把这些元件搭成电路，就实现了对应的命题公式，这样的电路称作组合电路。实现 \wedge, \vee, \neg 的元件分别称为与门、或门、非门，图形表示如图 2.1 所示。设计组合电路的路子是：先按需求列出输入输出的真值表，由真值表写出逻辑表达式，再照表达式画出电路；为了让电路尽量简单，最后还要化简表达式。

例 2.22 楼梯有一盏灯，由上、下 2 个开关控制，要求按动任何一个开关都能打开或关闭灯. 试设计一个这样的线路.

解 用 x, y 分别表示这 2 个开关的状态，开关的 2 个状态分别用 1 和 0 表示. 用 F 表示灯的状态，打开为 1，关闭为 0. 不妨设当 2 个开关都为 0 时灯是打开的. 根据题目的要求，开关的状态与灯的状态的关系如表 2.13 所示. 根据它可以写出 F 的主析取范式

根据这个公式，控制楼梯电灯的组合电路如图 2.2 所示.

解读：上面 m_0 与 m_3 之间的符号原书印作 \wedge。按表 2.13，F 在 00 与 11 两行取 1，应当是把这两个极小项或起来，即 F = m_0 \vee m_3；而 (\neg x \wedge \neg y) \vee (x \wedge y) 写的正是这个或式。

表 2.13

以上讨论的都是主析取范式的求法与用途，主合取范式与它完全对称，不再重复。还有几点需要说明。

（1）由公式的主析取范式求主合取范式.

设公式 A 含 n 个命题变项. A 的主析取范式含 s（0 < s < 2^n）个极小项，即

没出现的极小项为 m_{j_1}, m_{j_2}, \cdots, m_{j_{2^n - s}}，它们的角标的二进制表示为 \neg A 的成真赋值，因而 \neg A 的主析取范式为

由定理 2.6 可知

即主析取范式中没有出现的极小项的下标恰好是主合取范式中极大项的下标. 于是，由公式的主析取范式即可求出它的主合取范式.

例 2.23 由公式的主析取范式求主合取范式.

① A \Leftrightarrow m_1 \vee m_2（A 中含两个命题变项 p, q）.

② B \Leftrightarrow m_1 \vee m_2 \vee m_3（B 中含命题变项 p, q, r）.

解 ① 由题可知，没出现在主析取范式中的极小项为 m_0 和 m_3，所以 A 的主合取范式中含两个极大项 M_0 与 M_3，故

② B 的主析取范式中没出现的极小项为 m_0, m_4, m_5, m_6, m_7，因而

反之，由公式的主合取范式，也可以确定主析取范式.

（2）重言式与矛盾式的主合取范式.

矛盾式无成真赋值，因而矛盾式的主合取范式含 2^n（n 为公式中命题变项个数）个极大项. 而重言式无成假赋值，因而主合取范式不含任何极大项. 将重言式的主合取范式规定为 1. 至于可满足式，它的主合取范式中极大项的个数一定小于 2^n.

（3）n 个命题变项共可产生 2^n 个极小项（极大项），因而共可产生 2^{2^n} 个不同的主析取范式（主合取范式）. 每一个主析取范式（主合取范式）对应无穷多个等值的命题公式.

（4）真值表和主析取范式（主合取范式）是描述命题公式的两种标准形式. 公式 A 的主析取范式（主合取范式）中的极小项（极大项）的下标的二进制表示恰好是 A 的成真赋值（成假赋值），因而 A 的主析取范式（主合取范式）恰好对应于 A 的真值表. 由公式 A 的主析取范式（主合取范式）可以立刻写出 A 的真值表；反之，由 A 的真值表也可以立刻写出 A 的主析取范式（主合取范式）.