合取范式
-
2023年3月4日发(作者：电视的英文单词)第四节主析取范式与主合取范式
n个命题变项虽然可以构成无穷多个形式各异的命题公式，但就其真值而言，只有22n
种。对应每种真值情况虽然又有无穷多个等值的公式，但这些公式却有相同的标准形式。本
节将给出规范公式的概念，这种规范的公式能表达真值表所能给出的一切信息。
定义4.1命题变项及其否定统称为文字。
如p，q，¬p，¬q，L都是文字，即每个命题变项产生两个文字。
（1）仅由有限个文字构成的合取式称为简单合取式。
（2）仅由有限个文字构成的析取式称为简单析取式。
例如，p∧q，p∧¬q∧r，L都是简单合取式。p∨q，¬p∨q∨r，L都是
简单析取式。单个文字既是简单析取式，又是简单合取式。
定义4.2（1）仅由有限个简单合取式构成的析取式称为析取范式；
（2）仅由有限个简单析取式构成的合取式称为合取式。
例如，p，¬q，p∧q，（p∧¬q）∨（p∧q），L都是析取范式。p，¬r，p
∨q，（p∨q）∧（q∨¬r），L都是合取范式。注意，两个文字构成的简单合取式与析
取式都既是析取范式又是合取范式。例如，p∨q是析取范式，它是由两个简单的合取式p
与q析取而成。同时它也是合取范式，看成是一个简单析取式构成的合取范式。
定义4.3（1）n个命题变项
1
p，
2
p，L，
n
p（1n≥）构成的简单合取式中，若
每个
i
p（1,2,,in=L）都以文字的形式出现一次且仅出现一次，而且出现在左起的第i位
上，则称它为极小项。
（2）n个命题变项
1
p，
2
p，L，
n
p（1n≥）构成的简单析取式中，若每个
i
p
（1,2,,in=L）以文字的形式出现一次且仅出现一次，而且出现在左起的第i位上，则称
它为极大项。
两个命题变项p，q共可形成4个极小项：¬p∧¬q，¬p∧q，p∧¬q，p∧q。
同样地，共可形成4个极大项：p∨q，p∨¬q，¬p∨q，¬p∨¬q。
一般地，n个命题变项共可生成2n个极小项和2n个极大项。n个命题变项共有2n个赋
值（解释）。这些赋值作为2n个极小项和2n个极大项的赋值有这样的特点：对于每个极小
项来说，均有且仅有一个成真赋值。而对每个极大项来说，均有且仅有一个成假赋值。
把极小项的成真赋值看成一个二进制数，再把这个二进制数转化为十进制数。设这个
十进制数为i，我们用
i
m作为该极小项的名称。类似地，一个极大项的名称为
j
M，其中j
是该极大项的成假赋值（作为二进制数）所表示的十进制数。如表4.1和表4.2所示。
表4.1,pqr形成的极小项与成真赋值
极小项成真赋值名称
¬p∧¬q∧¬r
000
0
m
¬p∧¬q∧r
001
1
m
¬p∧q∧¬r
010
2
m
¬p∧q∧r
011
3
m
p∧¬q∧¬r
100
4
m
p∧q∧¬r
101
5
m
p∧¬q∧r
110
6
m
p∧q∧r
111
7
m
表4.2,pqr形成的极大项与成假赋值
极大项成假赋值名称
p∨q∨r
000
0
M
p∨q∨¬r
001
1
M
p∨¬q∨r
010
2
M
p∨¬q∨¬r
011
3
M
¬p∨q∨r
100
4
M
¬p∨q∨¬r
101
5
M
¬p∨¬q∨r
110
6
M
¬p∨¬q∨¬r
111
7
M
定义4.4（1）由极小项构成的析取范式称为主析取范式；
（2）由极大项构成的合取范式称为主合取范式。
n个命题变项共可生成22n个主析取范式，每个主析取范式对应一个n维真值函数。
定理4.1任何命题公式都存在与之等值的主析取范式与主合取范式，并且是唯一的。
注：对任何一个含有n个命题变项的命题公式A有:
12
()
k
iii
Ammm⇔∨∨∨L主析取范式
12
()
r
jjj
MMM⇔∧∧∧L主合取范式，其中k等于公式A的成真赋值的个数，r等
于公式A的成假赋值的个数，k+r=2n。也就是说，A有多少个成真赋值，那么它的主析取范
式就有多少个极小项；A有多少个成假赋值，那么它的主合取范式就有多少个极大项。由于
公式的赋值除了成真赋值就是成假赋值，所以，若A的主析取范式用了k个极小项（对应k
个成真赋值），那么其余的2n-k个成假赋值（对应2n-k个极大项）就用来形成主合取范式。
求给定命题公式的主析取范式可用两种方法，即等值演算法和真值表法。
等值演算法求主析取范式的步骤如下：
(1)求给定公式的析取范式：
①消去联结词→，↔；
②内移（利用德