2.3 范式

本节对应原书 PDF 第 54–64 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

2.3.1 析取范式与合取范式

本节通过等值演算将命题公式等值地化成联结词集 \{\neg,\wedge,\vee\} 中两种规范化的形式，即主析取范式与主合取范式。这种规范形式能给出公式的真值表所给出的一切信息。

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

p,\neg q 等为 1 个文字构成的简单析取式，p\vee\neg p,\neg p\vee q 等为 2 个文字构成的简单析取式，\neg p\vee\neg q\vee r,p\vee\neg p\vee r 等为 3 个文字构成的简单析取式。

\neg p,q 等为 1 个文字构成的简单合取式，\neg p\wedge p,p\wedge\neg q 等为 2 个文字构成的简单合取式，p\wedge q\wedge\neg r,\neg p\wedge p\wedge q 等为 3 个文字构成的简单合取式。

应该注意，一个文字既是简单析取式，又是简单合取式。为方便起见，有时用 A_1,A_2,\cdots,A_s 表示 s 个简单析取式或 s 个简单合取式。

解读：「文字」是最小单位——一个变项或者它的否定，不能再拆。把它们用 \vee 串起来就是简单析取式，用 \wedge 串起来就是简单合取式。单个文字两边都算，这是后面范式能互相转化的原因。

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

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

解读：这条定理的作用是给了一个不用列真值表就能判重言/矛盾的判据。比如 \neg p\vee q\vee p 含 p 与 \neg p，立刻知道是重言式；\neg p\wedge q\wedge p 含 p 与 \neg p，立刻知道是矛盾式。反过来，一个简单析取式若不含任何互补对，就取赋值让每个文字都假——它就成了成假赋值，所以它不是重言式。

定义 2.16 (1) 由有限个简单合取式构成的析取式称为析取范式。

(2) 由有限个简单析取式构成的合取式称为合取范式。

(3) 析取范式与合取范式统称为范式。

设 A_i(i=1,2,\cdots,s) 为简单合取式，则 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，则由 A_1,A_2,A_3 构成的析取范式为

类似地，设 A_i(i=1,2,\cdots,s) 为简单析取式，则 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，则由 A_1,A_2,A_3 构成的合取范式为

形如 \neg p\wedge q\wedge r 的公式既是一个简单合取式构成的析取范式，又是由 3 个简单析取式构成的合取范式。类似地，形如 p\vee\neg q\vee r 的公式既是含 3 个简单合取式的析取范式，又是含一个简单析取式的合取范式。

解读：注意析取范式和合取范式不是互斥的两类，同一个公式可能同时是两者。判断只看外层：外层是 \vee 串起来的简单合取式 → 析取范式；外层是 \wedge 串起来的简单析取式 → 合取范式。单个文字是两者的退化情形。

定理 2.4 (1) 一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。

(2) 一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。

解读：由定理 2.3 可知，简单合取式是矛盾式 \Leftrightarrow 它含互补对。所以判一个析取范式是不是矛盾式，就是逐项查有没有互补对——全是，才是矛盾式。这正是"范式能读出真值表信息"的第一步。

任何公式都可以化成等值的析取范式和合取范式。首先，我们观察到在范式中不出现联结词 \rightarrow 与 \leftrightarrow。由蕴涵等值式与等价等值式可知

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

其次，在范式中不出现如下形式的公式：

对其利用双重否定定律和德摩根律，可得

再次，在析取范式中不出现如下形式的公式：

在合取范式中不出现如下形式的公式：

利用分配律，可得

由式(2.4)~式(2.6)3 步，可将任一公式化成与之等值的析取范式或合取范式。于是，下面定理是正确的。

解读：这三步就是求范式的固定流水线——① 消 \rightarrow,\leftrightarrow；② 否定号内移（把 \neg 一路推到变项上）；③ 用分配律把不该出现的外层结构换掉。第③步用哪个分配律，决定了你得到析取范式还是合取范式：\wedge 对 \vee 分配得析取范式，\vee 对 \wedge 分配得合取范式。注意式(2.6)两条方向相反，用错方向就得到另一种范式。

定理 2.5(范式存在定理) 任一命题公式都存在着与之等值的析取范式与合取范式。

下面给出求给定公式范式的步骤。

① 消去联结词 \rightarrow,\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\rightarrow q)\vee\neg r 的析取范式和合取范式，这说明公式的析取范式与合取范式是不唯一的。

解读：最后一句是本节的动机所在。同一个公式的析取范式有无穷多个（可以随意塞进矛盾式或重言式而不改变等值性），所以"析取范式"这个形式不够规范——两个等值的公式可能给出完全不同的范式，没法当"标准形"用。下一节要做的，就是加两个约束（每项长度必须等于变项总数、每项必须含每个变项恰好一次），把不唯一变成唯一。

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

1. 概念

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

由于每个命题变项在极小项中以原形或否定式形式出现且仅出现一次，因而 n 个命题变项共可产生 2^n 个不同的极小项。其中每个极小项都有且仅有一个成真赋值。若成真赋值所对应的二进制数转化为十进制数为 i，就将所对应极小项记作 m_i。类似地，n 个命题变项共可产生 2^n 个不同的极大项，每个极大项只有一个成假赋值，将其对应的十进制数 i 作极大项的角标，记作 M_i。

解读：极小项与极大项是对偶的一对。区别只有三点：极小项是"合取式、看成真赋值、记 m_i"；极大项是"析取式、看成假赋值、记 M_i"。角标怎么来的：把变项按顺序排好，极小项中原形记 1、否定记 0，读出来就是 i；极大项中原形记 0、否定记 1，读出来才是 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.6 是"由主析取范式求主合取范式"这条捷径的全部依据。直观理解：m_i 在赋值 i 处为真、其余处为假，那么 \neg m_i 就恰好在赋值 i 处为假、其余处为真——这正好是极大项 M_i 的定义（唯一的成假赋值是 i）。所以取反一个极小项就直接得到同角标的极大项。

定义 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 的合取范式 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_6\wedge M_3\wedge M_7 可简记为 \prod(0,3,7)。

解读（原书此处疑似笔误）：步骤④的示例中，M_6\wedge M_3\wedge M_7 按角标从小到大排列应是 M_3\wedge M_6\wedge M_7，简记为 \prod(3,6,7)，而原书写的是 \prod(0,3,7)，角标与公式对不上。此处照原书逐字保留，并提请读者以"角标取自极大项本身"为准。对照本节后文例 2.17 的 \prod(1,3,7) 与例 2.18 的 \prod(0,2,3)，记法本身是"角标即极大项下标"。

定理 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 只可能有唯一的一个主析取范式。主合取范式的唯一性可以类似证明，只需把极小项换成极大项，并交换成真赋值与成假赋值。

解读：唯一性证明的关键一步是"极小项的下标 i 的二进制表示就是 A 的一个成真赋值"。也就是说主析取范式等价于真值表——它把真值表中所有取值为 1 的行编码成了一串角标。既然真值表是唯一的，主析取范式自然唯一。这也解释了为什么定理 2.5（范式存在）不带"唯一"，而定理 2.7 带。

例 2.17 求例 2.16 中公式 \neg(p\rightarrow 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.17 里两处"派生"是同一件事的两种规模。p\wedge\neg q 缺 1 个变项 r，补 r 时用 (\neg r\vee r) 展开成 2 项；\neg r 缺 2 个变项，就要用 (p\vee\neg p)\wedge(q\vee\neg q) 展开成 4 项。一般规律就是 2^{n-k}：缺 n-k 个变项，每个变项一分为二，所以派生 2^{n-k} 项。记住这个数，可以检验展开有没有漏项。

例 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\rightarrow q)\wedge q.

(2) p\rightarrow(p\vee q).

(3) (p\vee q)\rightarrow 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\nLeftrightarrow B。

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

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

(2) (p\rightarrow q)\rightarrow r 与 (p\wedge q)\rightarrow r.

解 (1) 两公式共含两个命题变项，因而极小项含两个文字。

另一公式

所以

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

所以

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

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

(1) 若 A 去，则 C 同去。

(2) 若 B 去，则 C 不能去。

(3) 若 C 不去，则 A 或 B 可以去。

问所里应如何选派他们？

解 设 p:派 A 去

\qquad q:派 B 去

\qquad 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 不去。

解读：这类"条件 → 方案"的应用题，做法是固定的三步：① 把每个条件翻译成蕴涵式；② 全部合取，再化成主析取范式；③ 每个极小项就是一种可行方案，角标的二进制就是各变量取值。本题主析取范式是 m_1\vee m_2\vee m_5，角标 1,2,5 的二进制 001,010,101 正好对应上面 3 种方案。

下面再举一个命题公式在设计控制电路中的应用。可以用电子元件物理实现逻辑运算，用这些元件组合成的电路物理实现命题公式，这样的电路称作组合电路。实现 \wedge,\vee,\neg 的元件分别称为与门、或门、非门。它们的图形表示如图 2.1 所示。设计组合电路，首先要根据需要写出输入输出的真值表，然后根据真值表写出逻辑表达式，再按照逻辑表达式画出组合电路。为了使组合电路尽可能的简单，还需要对表达式进行化简。

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

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

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

表 2.13

解读（原书此处疑似笔误）：原文写"F=m_0\wedge m_3"，但 m_0 与 m_3 之间应为析取（\vee）才是主析取范式，\wedge 会得到矛盾式。后接等号右边的 (\neg x\wedge\neg y)\vee(x\wedge y) 也证实应为 \vee。此处照原书逐字保留。

图 2.1 逻辑门、图 2.2 两个开关控制的灯具电路：见原书 PDF 第 63 页插图。

以上主要讨论了主析取范式的求法与用途，主合取范式的用途和主析取范式的一样，不再赘述，但还要说明以下几点。

(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 可知

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

解读：这是最省力的一条捷径——主析取范式的补集角标 = 主合取范式的角标。例如 A\Leftrightarrow\sum(0,2,4,5,6)（变项数 3，共 8 个极小项），没出现的是 1,3,7，于是直接得 A\Leftrightarrow\prod(1,3,7)，与例 2.17 的演算结果一致。

例 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 的主析取范式(主合取范式)。

解读：补全三种极端情形——重言式的主析取范式含全部 2^n 个极小项、主合取范式规定为 1；矛盾式的主析取范式规定为 0、主合取范式含全部 2^n 个极大项；可满足式（非重言）两种范式的项数都严格小于 2^n。这三条合起来，就能只看范式写出公式类型。