1
1.5 对偶与范式
?对偶式与对偶原理
?析取范式与合取范式
?主析取范式与主合取范式
2
对偶式和对偶原理
定义 在仅含有联结词 ?,∧,∨ 的命题公式 A中, 将
∨ 换成 ∧,∧ 换成 ∨, 若 A中含有 0或 1,就将 0换成
1,1换成 0,所得命题公式称为 A的 对偶式, 记为 A*,
从定义不难看出, (A*)* 还原成 A
定理 设 A和 A*互为对偶式, p1,p2,…,pn是出现在 A和
A*中的全部命题变项, 将 A和 A*写成 n元函数形式,
则 (1) ? A(p1,p2,…,pn) ? A* (? p1,? p2,…,? pn)
(2) A(? p1,? p2,…,? pn) ? ? A* (p1,p2,…,pn)
定理（对偶原理） 设 A,B为两个命题公式,
若 A ? B，则 A* ? B*,
3
析取范式与合取范式
文字,命题变项及其否定的总称
简单析取式,有限个文字构成的析取式
如 p,?q,p??q,p?q?r,…
简单合取式,有限个文字构成的合取式
如 p,?q,p??q,p?q?r,…
析取范式,由有限个简单合取式组成的析取式
A1?A2??? Ar,其中 A1,A2,?,Ar是 简单合取式
合取范式,由有限个简单析取式组成的合取式
A1?A2??? Ar,其中 A1,A2,?,Ar是 简单析取式
4
析取范式与合取范式 (续 )
范式,析取范式与合取范式的总称
公式 A的析取范式, 与 A等值的析取范式
公式 A的合取范式, 与 A等值的合取范式
说明,
单个文字既是简单析取式, 又是简单合取式
形如 p??q?r,?p?q??r 的公式既是析取范式,
又是合取范式 (为什么?)
5
命题公式的范式
定理 任何命题公式都存在着与之等值的析取范式
与合取范式,
求公 式 A的范式的步骤,
(1) 消去 A中的 ?,?（ 若存在 ）
(2) 否定联结词 ?的内移或消去
(3) 使用分配律
?对 ?分配 （ 析取范式 ）
?对 ?分配 （ 合取范式 ）
公式的范式存在，但不惟一，这是它的局限性
6
求公式的范式举例
例 求下列公式的析取范式与合取范式
(1) A=(p??q)??r
解 (p??q)??r
? (?p??q)??r （ 消去 ?）
? ?p??q??r （ 结合律 ）
这既是 A的析取范式 （ 由 3个简单合取式组成的析
取式 ）, 又是 A的合取范式 （ 由一个简单析取式
组成的合取式 ）
7
求公式的范式举例 (续 )
(2) B=(p??q)?r
解 (p??q)?r
? (?p??q)?r （ 消去第一个 ?）
? ?(?p??q)?r （ 消去第二个 ?）
? (p?q)?r （ 否定号内移 —— 德摩根律 ）
这一步已为析取范式 （ 两个简单合取式构成 ）
继续,(p?q)?r
? (p?r)?(q?r) （ ?对 ?分配律 ）
这一步得到合取范式（由两个简单析取式构成）
8
极小项与极大项
定义 在含有 n个命题变项的简单合取式 (简单析取式 )中,
若每个命题变项均以文字的形式在其中出现且仅出现一
次, 而且第 i（ 1?i?n） 个文字出现在左起第 i位上, 称这样
的简单合取式 （ 简单析取式 ） 为 极小项 （ 极大项 ）,
说明,n个命题变项产生 2n个极小项和 2n个极大项
2n个极小项 （ 极大项 ） 均互不等值
用 mi表示第 i个极小项，其中 i是该极小项成真赋值的十
进制表示, 用 Mi表示第 i个极大项，其中 i是该极大项成假
赋值的十进制表示,mi(Mi)称为极小项 (极大项 )的名称,
mi与 Mi的关系, ?mi ? Mi,?Mi ? mi
9
极小项与极大项 (续 )
由 p,q两个命题变项形成的极小项与极大项
公式 成真赋值 名称 公式 成假赋值 名称
?p ? ?q
?p ? q
p ? ?q
p ? q
0 0
0 1
1 0
1 1
m0
m1
m2
m3
p ? q
p ? ?q
?p ? q
?p ? ?q
0 0
0 1
1 0
1 1
M0
M1
M2
M3
极小项 极大项
10
由 p,q,r三个命题变项形成的极小项与极大项
极小项 极大项
公式 成真 赋值 名称 公式 成假 赋值 名称
?p ??q ??r
?p ??q ? r
?p ? q ??r
?p ? q ? r
p ??q ? ?r
p ??q ? r
p ?q ??r
p ?q ? r
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
m0
m1
m2
m3
m4
m5
m6
m7
p ? q ? r
p ? q ??r
p ? ?q ? r
p ? ?q ??r
?p ? q ? r
?p ? q ??r
?p ? ?q ? r
?p ? ?q ??r
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
M0
M1
M2
M3
M4
M5
M6
M7
11
主析取范式与主合取范式
主析取范式, 由极小项构成的析取范式
主合取范式, 由极大项构成的合取范式
例如, n=3,命题变项为 p,q,r时,
(?p??q?r)?(?p?q?r) ? m1?m3 是 主析取范式
(p?q??r)?(?p?q??r) ? M1?M5 是 主合取范式
A的主析取范式, 与 A等值的主析取范式
A的主合取范式, 与 A等值的主合取范式,
12
主析取范式与主合取范式 (续 )
定理 任何命题公式都存在着与之等值的主析取范
式和主合取范式,并且是惟一的,
用等值演算法求公式的主范式的步骤,
(1) 先求析取范式 （ 合取范式 ）
(2) 将不是极小项 （ 极大项 ） 的简单合取式 （ 简
单析取式 ） 化成与之等值的若干个极小项的析
取 （ 极大项的合取 ）, 需要利用同一律 （ 零
律 ）, 排中律 （ 矛盾律 ）, 分配律, 幂等律等,
(3) 极小项（极大项）用名称 mi（ Mi）表示，并
按角标从小到大顺序排序,
13
求公式的主范式
例 求公式 A=(p??q)?r的主析取范式与主合
取范式,
(1) 求主析取范式
(p??q)?r
? (p?q)?r,（ 析取范式 ） ①
(p?q)
? (p?q)?(?r?r)
? (p?q??r)?(p?q?r)
? m6?m7,②
14
求公式的主范式 (续 )
r
?(?p?p)?(?q?q)?r
?(?p??q?r)?(?p?q?r)?(p??q?r)?(p?q?r)
? m1?m3?m5?m7 ③
②,③ 代入 ① 并排序, 得
(p??q)?r ? m1?m3?m5? m6?m7（ 主析取范式）
15
求公式的主范式 (续 )
(2) 求 A的主合取范式
(p??q)?r
? (p?r)?(q?r),（ 合取范式 ） ①
p?r
? p?(q??q)?r
? (p?q?r)?(p??q?r)
? M0?M2,②
16
求公式的主范式 (续 )
q?r
? (p??p)?q?r
? (p?q?r)?(?p?q?r)
? M0?M4 ③
②,③ 代入 ① 并排序, 得
(p??q)?r ? M0?M2?M4 （主合取范式）
17
主范式的用途 —— 与真值表相同
(1) 求公式的成真赋值和成假赋值
例如 (p??q)?r ? m1?m3?m5? m6?m7,
其成真赋值为 001,011,101,110,111,
其余的赋值 000,010,100为 成假赋值,
类似地，由主合取范式也可立即求出成
假赋值和成真赋值,
18
主范式的用途 (续 )
(2) 判断公式的类型
设 A含 n个命题变项, 则
A为重言式 ?A的主析取范式含 2n个极小项
?A的主合取范式为 1,
A为矛盾式 ? A的主析取范式为 0
? A的主合析取范式含 2n个极大项
A为非重言式的可满足式
?A的主析取范式中至少含一个且不含全部极小项
?A的主合取范式中至少含一个且不含全部极大项
19
主范式的用途 (续 )
例 用主析取范式判断下述两个公式是否等值,
⑴ p?(q?r) 与 (p?q)?r
⑵ p?(q?r) 与 (p?q)?r
解 p?(q?r) = m0?m1?m2?m3? m4?m5? m7
(p?q)?r = m0?m1?m2?m3? m4?m5? m7
(p?q)?r = m1?m3? m4?m5? m7
显见, ⑴ 中的两公式等值, 而 ⑵ 的不等值,
(3) 判断两个公式是否等值
说明,
由公式 A的主析取范式确定它的主合取范式, 反之亦然,
用公式 A的真值表求 A的主范式,
20
主范式的用途 (续 )
例 某公司要从赵, 钱, 孙, 李, 周五名新毕
业的大学生中选派一些人出国学习, 选派必须
满足以下条件,
(1)若赵去, 钱也去；
(2)李, 周两人中至少有一人去；
(3)钱, 孙两人中有一人去且仅去一人；
(4)孙, 李两人同去或同不去；
(5)若周去, 则赵, 钱也去,
试用主析取范式法分析该公司如何选派他们出
国？
21
例 (续 )
解此类问题的步骤为,
① 将简单命题符号化
② 写出各复合命题
③ 写出由②中复合命题组成的合取式
④ 求 ③中所得公式的主析取范式
22
例 (续 )
解 ① 设 p：派赵去, q：派钱去, r：派孙去,
s：派李去, u：派周去,
② (1) (p?q)
(2) (s?u)
(3) ((q??r)?(?q?r))
(4) ((r?s)?(?r??s))
(5) (u?(p?q))
③ (1) ~ (5)构成的合取式为
A=(p?q)?(s?u)?((q??r)?(?q?r))?
((r?s)?(?r??s))?(u?(p?q))
23
例 (续 )
④ A ? (?p??q?r?s??u)?(p?q??r??s?u)
结论：由 ④ 可知, A的成真赋值为 00110与 11001,
因而派孙, 李去 （ 赵, 钱, 周不去 ） 或派赵, 钱,
周去 （ 孙, 李不去 ）,
A的演算过程如下,
A ? (?p?q)?((q??r)?(?q?r))?(s?u)?(?u?(p?q))?
((r?s)?(?r??s)) （ 交换律 )
B1= (?p?q)?((q??r)?(?q?r))
? ((?p?q??r)?(?p??q?r)?(q??r)) （ 分配律 ）
24
例 (续 )
B2= (s?u)?(?u?(p?q))
? ((s??u)?(p?q?s)?(p?q?u)) （分配律）
B1?B2 ? (?p?q??r?s??u)?(?p??q?r?s??u)
?(q??r?s??u)?(p?q??r?s)?(p?q??r?u)
再令 B3 = ((r?s)?(?r??s))
得 A ? B1?B2?B3
? (?p??q?r?s??u)?(p?q??r??s?u)
注意：在以上演算中多次用矛盾律
要求：自己演算一遍