下载掌阅APP，畅读海量书库
立即打开
范式是命题公式的规范表示形式，又称为 标准形 。一个命题公式可以有不同的等价式，因而为命题公式的研究带来一定的困难。把命题公式化成规范的标准形可为命题公式的研究和应用带来方便。
定义1.4.1 一个命题公式具有形式 A 1 ∨ A 2 ∨…∨ A n （ n ≥1），其中 A 1 ， A 2 ，…， A n 都是由命题变元或其否定所组成的合取式，则称该命题公式为 析取范式 。
例如，给定命题变元
p
、
q
和
是析取范式。
定义1.4.2 一个命题公式具有形式 B 1 ∧ B 2 ∧…∧ B n （ n ≥1），其中 B 1 ， B 2 ，…， B n 都是由命题变元或其否定所组成的析取式，则称该命题公式为 合取范式 。
例如，给定命题变元
p
、
q
和
r
，
是合取范式。
定理1.4.1（范式存在定理） 任意一个命题公式都存在着与之等价的析取范式和合取范式。
证明 设 G 为任意一个公式。
1）消去
、∧、∨以外的联结词。
2）将否定联结词内移或消去。
3）利用分配律、交换律和结合律等将公式归纳为析取范式和合取范式。
通过上面的3个步骤可以求出与 G 等价的析取范式和合取范式。因此，任意一个命题公式都存在着与之等价的析取范式和合取范式。以上也是求析取范式和合取范式的步骤。
◀
例1.4.1 求命题公式（ p ∧（ p → q ））∨ q 的析取范式和合取范式。
解
按析取范式的定义，
、（
p
∧
q
）∨
q
、
q
都是原公式的析取范式，也就是说，与某个命题公式等值的析取范式是不唯一的。同理，与某个命题公式等值的合取范式也是不唯一的，如上例中，（
p
∨
q
）∧
q
、
和
q
都是合取范式。因而析取范式和合取范式不能作为命题公式的标准形。下面介绍主范式的概念。可以证明任意命题公式的主范式都是唯一的，因而可以用与命题公式等值的主范式作为它的标准形。
定义1.4.3 含有 n 个命题变元的合取式中，若每个命题变元与其否定不同时出现，而二者之一必出现且仅出现一次，这样的合取式称为 极小项 。
定义1.4.4 含有 n 个命题变元的析取式中，若每个命题变元与其否定不同时出现，而二者之一必出现且仅出现一次，这样的析取式称为 极大项 。
一般来说，极大项和极小项中的各个变元按下标由小到大的顺序排列，若无下标，则按字母顺序排列。例如，对于三个命题变元
p
、
q
和
r
，
p
∧
q
∧
r
、
都是极小项，
p
∨
q
∨
r
、
都是极大项，而
p
∧
q
和
都不是极小项，因为它们没有包含所有的命题变元。同理，
p
∨
q
和
也不是极大项。
含
n
个命题变元
p
1
，
p
2
，…，
p
n
的极小项可表示为
，极大项可表示为
，其中每一个
为
p
i
或
。由
n
个命题变元产生的不同的极大项和极小项的个数均为2
n
个。每个极小项在它的2
n
个赋值中只有一个成真赋值，例如，含三个变元的极小项
p
∧
q
∧
r
的成真赋值只有111。每个极大项在它的2
n
个赋值中只有一个成假赋值，例如，含三个变元的极大项
的成假赋值只有011。因而每个极小项可以简记为
m
i
，其中，下标
i
为该极小项的成真赋值；每个极大项可以简记为
M
i
，其中，下标
i
为该极大项的成假赋值。
例如，3个命题变元可形成8个极小项，如表1.4.1所示。
表1.4.1 极小项表
一般地， n 个命题变元形成的极小项可表示为
3个命题变元形成的8个极大项如表1.4.2所示。
表1.4.2 极大项表
一般地， n 个命题变元形成的极大项可表示为
定义1.4.5 如果含 n 个命题变元的命题公式的析取范式的每个合取式全是极小项，则称该析取范式为 主析取范式 。
定理1.4.2 任何命题公式的主析取范式都是存在的，并且是唯一的。
证明 给定命题公式 A 。
1）求 A 的析取范式 A′ ， A′ 的形式为 A 1 ∨ A 2 ∨…∨ A n （ n ≥1）。
2）若
A′
中的某个简单合取式
A
i
不是极小项，则补入在
A
i
中没有出现的变元。例如，若
p
i
和
都不在
A
i
中，则将
A
i
展开成如下形式：
。
3）重复步骤2，直到所有的简单合取式都含有所有的命题变元或它的否定式。
4）消去重复出现的命题变项、矛盾式及重复出现的极小项。
按上述步骤求得的就是 A 的主析取范式。所以，任何命题公式的主析取范式都是存在的，而且是唯一的（唯一性证明略）。
◀
例1.4.2 求命题公式（ p ∨（ q ∧ r ））→（ p ∧ q ∧ r ）的主析取范式。
解
在（
p
∨（
q
∧
r
））→（
p
∧
q
∧
r
）的析取范式中含有两个合取式
和
，均不是极小项，因而要补入没有出现的变元，
用
代换，并用分配律展开，使得每个合取式都是极小项。对
同样补入没有出现的变元
q
。消去重复出现的极小项，就得到原公式的主析取范式。极小项可以用简记
m
i
表示，按
m
i
的下标由小到大的顺序排列后可用∑表示主析取范式，如
（ p ∨（ q ∧ r ））→（ p ∧ q ∧ r ）
⇔ m 0 ∨ m 1 ∨ m 2 ∨ m 7 ⇔∑（0，1，2，7）
一个命题公式的主析取范式中的每一个极小项的成真赋值就是该公式的一个成真赋值。因而根据命题公式的真值表可以立即写出公式的主析取范式。
例1.4.3 试由 p ∧ q ∨ r 的真值表（表1.4.3）求它的主析取范式。
表1.4.3 p ∧ q ∨ r 的真值表
解 由表1.4.3知，公式 p ∧ q ∨ r 的成真赋值为001、011、101、110、111，对应的十进制数下标的极小项为 m 1 、 m 3 、 m 5 、 m 6 、 m 7 。因此， p ∧ q ∨ r 的主析取范式为
p ∧ q ∨ r ⇔∑（1，3，5，6，7）
利用表1.4.1， p ∧ q ∨ r 的主析取范式还可写为
设 G 是含 n 个命题变项的命题公式，当且仅当 G 的主析取范式含全部2 n 个极小项时， G 为重言式；若 G 为矛盾式， G 的主析取范式不含任何极小项，记 G 的主析取范式为0；当 G 的主析取范式中至少含有一个极小项时， G 为可满足式。
类似地可以给出主合取范式的定义。
定义1.4.6 如果含 n 个命题变元的命题公式的合取范式的每个析取式全是极大项，则称该合取范式为 主合取范式 。
定理1.4.3 任何命题公式的主合取范式都是存在的，并且是唯一的。
证明 给定命题公式 A 。
1）求 A 的合取范式 B′ ， B′ 的形式为 B 1 ∧ B 2 ∧…∧ B n （ n ≥1）。
2）若
B′
中的某个析取式
B
i
不是极大项，则补入在
B
i
中没有出现的变元。例如，若
p
i
和
都不在
B
i
中，则将
B
i
展成如下形式：
。
3）重复步骤2，直到所有的简单析取式都含有所有的命题变元或它的否定式。
4）消去重复出现的命题变项、重言式及重复出现的极大项。
按上述步骤求得的就是 A 的主合取范式。所以，任何命题公式的主合取范式都是存在的，而且是唯一的（唯一性证明略）。
◀
例1.4.4 求命题公式（ p ∨（ q ∧ r ））→（ p ∧ q ∧ r ）的主合取范式。
解
将极大项按下标由小到大的顺序排列后可用∏表示，如
（ p ∨（ q ∧ r ））→（ p ∧ q ∧ r ）⇔ M 3 ∧ M 4 ∧ M 5 ∧ M 6 ⇔∏（3，4，5，6）
一个命题公式的主合取范式中的每一个极大项的成假赋值就是该公式的一个成假赋值。因而根据命题公式的真值表可以立即写出公式的主合取范式。又因为，公式的主析取范式中没有出现的极小项的赋值就是公式的成假赋值，因而主合取范式中的极大项的下标码和主析取范式中没有出现的极小项的下标码相同。因此，只要求出了命题公式的主析取范式，就可以立即写出它的主合取范式，反之亦然。
例如，已知公式 G 的主析取范式
G ⇔ m 0 ∨ m 1 ∨ m 2 ∨ m 7 ⇔∑（0，1，2，7）
其中没有出现的极小项的下标码3、4、5、6就是主合取范式极大项的下标码，因此可以直接写出主合取范式
G ⇔ M 3 ∧ M 4 ∧ M 5 ∧ M 6 ⇔∏（3，4，5，6）
重言式的主合取范式不含任何极大项，用1表示重言式；矛盾式的主合取范式包含全部2 n 个极大项。
利用主析取范式或主合取范式可以判断公式是否等价及求命题公式的成真赋值和成假赋值。
例1.4.5
判断
和
是否等价。
解
所以，
和
等价。
◀
例1.4.6
判断公式
是否为重言式。
解
公式
是重言式，因为主析取范式包含了所有的极小项。
◀
例1.4.7 设计一个集成学习系统，该系统综合三个基学习器的分类预测（正类或负类），以投票的方式决定输入样本的预测类别，即在超过半数基学习器给出正类的情况下判定该样本为正类，否则为负类。设计满足上述条件的集成学习分类器，并尝试以逻辑电路图的方式画出该分类器。
解 三个基学习器的预测类别分别为 p 、 q 、 r ，集成学习器的最终预测类别为 A 。正类为1，负类为0。
根据题意，可将真值表列出，见表1.4.4。
由上述真值表可写出 A 的表达式
化简 A 的表达式得
分类器的逻辑电路图如图1.4.1所示。
◀
表1.4.4 分类器的真值表
图1.4.1 分类器的逻辑电路图
例1.4.8 某单位选派A、B、C三位业务骨干去进修，由于工作需要，选派要满足如下条件。
1）若A去，则C同去。
2）若B去，则C不能去。
3）若C不去，则A或B可以去。
问可以有哪些选派方案？
解 设 p 表示“派A去”， q 表示“派B去”， r 表示“派C去”。
由已知条件可得
该公式的成真赋值就是可行的选派方案。写出该公式的主析取范式
有3个成真赋值，所以有3种选派方案：
1）A和B不去，C去；
2）A和C不去，B去；
3）A和C去，B不去。
◀