一、对偶原理
二、范式
三、主范式
对偶与范式
重点：(1) 掌握对偶式，对偶原理。
(2) 掌握析取范式和合取范式的定义和求法步骤。
(3) 掌握极小项，极大项的概念及主范式的求法。
1、对偶式。
定义：设公式 
仅含联结词 
，则将 
分别用 
替代，所得的公式 
称
的对偶式。
显然，
的对偶式为
，即 
，也就是说
与
互为对偶式。
例如： 
与 
， 
与 
， 
与 
等均为相互对偶式。
2、对偶原理。
对偶原理：设 
为两个命题公式，若 
，则 
。
例如：已知 
(分配律)，且 
与 
， 
与 
均为相互对偶式，所以可得： 
。
1、简单析取式，简单合取式。
简单析取式：由有限个命题变项或其否定构成的析取式。
例如： 
， 
，
， 
等都是简单析取式。
简单合取式：由有限个命题变项或其否定构成的合取式。
例如：
，
，
， 
等都是简单合取式。
2、析取范式，合取范式。
定义：由有限个简单合取式构成的析取式称作析取范式。
由有限个简单析取式构成的合取式称作合取范式。
例如： 
为析取范式；
为合取范式。
显然， 
为合取范式；
为析取范式。
范式存在定理：任一命题公式都存在与之等值的析取范式和合取范式。
求范式步骤：
(1) 消去联结词 
(即利用
）。
(2) 否定消去或内移。
(3) 利用分配律。
例1、求公式 
的析取范式和合取范式。
解：原式
消去 
内移
消去 
分配律( 
对 
分配)
上式即原式的析取范式，再利用第三步的结论，即：
原式
分配律(
对
分配)
即原式的合取范式。
由例1知一个命题公式的析取范式，合取范式不唯一，不能作为标准形式，为此，给出主析取范式和主合取范式的概念。
1、极小项，极大项。
定义：设命题公式含 
这 
个命题变项，则 
和 
分别称为极小项和极大项，其中 
为 
或 
。
例如，对只含变项 
的命题公式中，
都是极小项，但 
不是极小项。
都是极大项，但 
不是极大项。
又如，对只含变项 
的命题公式中，
等都是极小项，
但 
等都不是极小项。
由定义知， 
有两种选择，即 
或 
，所以
个命题变项的公式中，不同极大项，极小项的个数均为 
个，下面讨论 
，即 
个命题变项
的极大项，极小项。
|
以上表格的4列中，任二列都是一一对应的，要理解记熟对应关系，对于极大项有类似关系
|
思考：极小项和极大项两个表格，对比其相同点和不同点。
2、主析取范式和主合取范式。
主析取范式——每个简单合取式都是极小项的析取范式。
主合取范式——每个简单析取式都是极大项的合取范式。
每个命题公式
的主析取范式，主合取范式都存在，并且有两种求法，等值式法和真值表法。
定理：任何命题公式的主析取范式、主合取范式都存在且都唯一。
2.1、利用等值式法求命题公式
的主析取范式。
步骤：
(1) 求
的析取范式 
，
(2) 若
的某个简单合取式 
中不含某命题变项
或其否定
，利用 
补充变元
，
(3) 将重复出项的命题变项，矛盾式及重复出现的极小项都“消去”，(如 
用
代， 
用0代， 
用 
代)，
(4) 将极小项按从小到大的顺序排列，并用符号“ 
”表示，(如 
排序为 
，用 
表示)。
例2、求公式 
的主析取范式
解：由例1，
的析取范式为 
( 
吸收律)
由极小项的定义知，每个极小项与唯一的成真赋值一一对应，而主析取范式中未出现的极小项则对应着成假赋值。因此，知道
的主析取范式就可写出
的真值表，反之亦然。
2.2、利用真值表求命题公式
的主析取范式。
步骤：(1) 列出
的真值表，
(2) 找出
的所有成真赋值，
(3) 求每个成真赋值对应的十进制数，即极小项的角码，将极小项按序析取即成。
例3、用真值表求
的主析取范式。
解：(1) 列真值表
|
(2)
的成真赋值有010，100，101，110，111
(3) 对应的十进制数为2，4，5，6，7
所以
的主析取范式为 
由例2，例3，用两种办法求的主析取范式相同。
2.3、利用等值式法求命题公式
的主合取范式。
步骤：
(1) 求
的合取范式
，
(2) 利用 
补充变元
，
(3) 消去重复的及永真项，
(4) 按角码顺序排序，并用符号“ 
”表示，(如 
记为 
)。
例4、求公式
的主合取范式。
解：由例1
合取范式
2.4、利用真值表求命题公式的主合取范式
步骤：
(1) 列出
的真值表，
(2) 找出
的所有成假赋值，
(3) 求每个成假赋值对应的十进制数，即极大项的角码，将极大项按序合取即成。
例5、用真值表法求
的主合取范式。
解：(1) 由例3知
的真值表，
(2)
的成假赋值有000，001，011，
(3) 对应的十进制数为0，1，3。
所以
的主合取范式 
，由例4，例5，用两种不同方法求的主合取范式相同。
思考：命题公式
的主合取范式，主析取范式间有什么联系，能否通过其中一个求另一个？(观察例3，例5)
2.5、已知命题公式
的主析取范式(主合取范式)，求主合取范式(主析取范式)。
考虑极小项，极大项之间的关系。
注意到 
设命题公式
(含
个命题变项)的主析取范式含 
个极小项 
，则 
的主合取范式必含 
个极小项。
设 
则 
因此，可得由
的主析取范式求
的主合取范式步骤：
(1) 写出
的主析取范式未出现的极小项，
(2) 写出与(1)中极小项角码相同的极大项，
(3) 由以上极大项合取即成
的主合取范式。
例6、(1) 已知命题公式
(含3个命题变项)的主析取范式为
，求
的主合取范式。
解：
的主合取范式为：
。
(2)已知命题公式
(含2个命题变项)的主合取范式为：
，求
的主析取范式。
解：
的主析取范式为：
。
3、主范式的用途。
由任何公式的主析取范式，主合取范式都是唯一的特点，可用于：
(1) 判断两命题公式是否等值。
若两公式有相同的主析取范式(或主合取范式)，则两公式等值，反之亦然。
(2) 判断命题公式的类型。
设
是含
个命题变项的命题公式，
为重言式，当且仅当
的主析取范式中含全部
个极小项。
为矛盾式，当且仅当
的主析取范式中不含任何极小项，可设
的主析取范式为0。当然，若
的主析取范式中至少含一个极小项，则
是可满足式。
同样，主合取范式也可用于判断命题公式的类型。
(3) 求成真(假)赋值，将极小(大)项的角码转换成二进制数。
(4) 求真值表。由极小项对应成真赋值和极大项对应成假赋值。
例7、已知含3个命题变项的公式：
和
。
(1) 判断
的类型。
(2) 判断
是否等值。
(3) 求
的成真赋值和成假赋值。
(4) 求
的真值表。
解：(1)
为可满足式，
为矛盾式。
(2)
不等值。
(3)
的成真赋值有000，001，110，111。
的成假赋值有010，011，100，101。
(4) 真值表
|