1.4.2 主析取范式和主合取范式

定义1.4.3 含有n个命题变元的合取式中，若每个命题变元与其否定不同时出现，而二者之一必出现且仅出现一次，这样的合取式称为极小项。

定义1.4.4 含有n个命题变元的析取式中，若每个命题变元与其否定不同时出现，而二者之一必出现且仅出现一次，这样的析取式称为极大项。

一般来说，极大项和极小项中的各个变元按下标由小到大的顺序排列，若无下标，则按字母顺序排列。例如，对于三个命题变元p、q和r，p∧q∧r、都是极小项，p∨q∨r、都是极大项，而p∧q和都不是极小项，因为它们没有包含所有的命题变元。同理，p∨q和也不是极大项。

含n个命题变元p₁，p₂，…，p_n的极小项可表示为，极大项可表示为，其中每一个为p_i或。由n个命题变元产生的不同的极大项和极小项的个数均为2n个。每个极小项在它的2n个赋值中只有一个成真赋值，例如，含三个变元的极小项p∧q∧r的成真赋值只有111。每个极大项在它的2n个赋值中只有一个成假赋值，例如，含三个变元的极大项的成假赋值只有011。因而每个极小项可以简记为m_i，其中，下标i为该极小项的成真赋值；每个极大项可以简记为M_i，其中，下标i为该极大项的成假赋值。

例如，3个命题变元可形成8个极小项，如表1.4.1所示。

一般地，n个命题变元形成的极小项可表示为

3个命题变元形成的8个极大项如表1.4.2所示。

一般地，n个命题变元形成的极大项可表示为

定义1.4.5 如果含n个命题变元的命题公式的析取范式的每个合取式全是极小项，则称该析取范式为主析取范式。

定理1.4.2 任何命题公式的主析取范式都是存在的，并且是唯一的。

证明 给定命题公式A。

1）求A的析取范式A′，A′的形式为A₁∨A₂∨…∨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₀∨m₁∨m₂∨m₇⇔∑（0，1，2，7）

一个命题公式的主析取范式中的每一个极小项的成真赋值就是该公式的一个成真赋值。因而根据命题公式的真值表可以立即写出公式的主析取范式。

例1.4.3 试由p∧q∨r的真值表（表1.4.3）求它的主析取范式。

解 由表1.4.3知，公式p∧q∨r的成真赋值为001、011、101、110、111，对应的十进制数下标的极小项为m₁、m₃、m₅、m₆、m₇。因此，p∧q∨r的主析取范式为

p∧q∨r⇔∑（1，3，5，6，7）

利用表1.4.1，p∧q∨r的主析取范式还可写为

设G是含n个命题变项的命题公式，当且仅当G的主析取范式含全部2n个极小项时，G为重言式；若G为矛盾式，G的主析取范式不含任何极小项，记G的主析取范式为0；当G的主析取范式中至少含有一个极小项时，G为可满足式。

类似地可以给出主合取范式的定义。

定义1.4.6 如果含n个命题变元的命题公式的合取范式的每个析取式全是极大项，则称该合取范式为主合取范式。

定理1.4.3 任何命题公式的主合取范式都是存在的，并且是唯一的。

证明 给定命题公式A。

1）求A的合取范式B′，B′的形式为B₁∧B₂∧…∧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₃∧M₄∧M₅∧M₆⇔∏（3，4，5，6）

一个命题公式的主合取范式中的每一个极大项的成假赋值就是该公式的一个成假赋值。因而根据命题公式的真值表可以立即写出公式的主合取范式。又因为，公式的主析取范式中没有出现的极小项的赋值就是公式的成假赋值，因而主合取范式中的极大项的下标码和主析取范式中没有出现的极小项的下标码相同。因此，只要求出了命题公式的主析取范式，就可以立即写出它的主合取范式，反之亦然。

例如，已知公式G的主析取范式

G⇔m₀∨m₁∨m₂∨m₇⇔∑（0，1，2，7）

其中没有出现的极小项的下标码3、4、5、6就是主合取范式极大项的下标码，因此可以直接写出主合取范式

G⇔M₃∧M₄∧M₅∧M₆⇔∏（3，4，5，6）

重言式的主合取范式不含任何极大项，用1表示重言式；矛盾式的主合取范式包含全部2n个极大项。

利用主析取范式或主合取范式可以判断公式是否等价及求命题公式的成真赋值和成假赋值。

例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.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不去。

◀