重复这个过程, 直到所有简单析取式都是长度为n的极 大项为止
(3) 消去重复出现的极大项, 即用Mi代替Mi?Mi (4) 将极大项按下标从小到大排列
例6 (1) 求公式 A=(p??q)?r的主析取范式和主合取范式 解 (p??q)?r
? (p?q)?r （析取范式） ①
(p?q) ? (p?q)?(?r?r)
? (p?q??r)?(p?q?r)
? m6?m7 ② 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 （主析取范式） (p??q)?r
? (p?r)?(q?r) （合取范式） ④ p?r
? p?(q??q)?r
? (p?q?r)?(p??q?r) ? ⑤
q?r ? (p??p)?q?r
? (p?q?r)?(?p?q?r)
? M0?M4 ⑥ ⑤, ⑥代入④ 并排序，得
(p??q)?r ? M0?M2?M4 （主合取范式） 1.求公式的成真成假赋值
设公式A含n个命题变项, A的主析取范式有s个极小项, 则A 有s个成真赋值, 它们是极小项下标的二进制表示, 其余2n-s 个赋值都是成假赋值
例如 (p??q)?r ? m1?m3?m5? m6?m7 成真赋值为 001, 011, 101, 110, 111， 成假赋值为 000, 010, 100.
类似地，由主合取范式也立即求出成假赋值和成真赋值. 2. 判断公式的类型
设A含n个命题变项.
A为重言式 ? A的主析取范式含全部2n个极小项
? A的主合取范式不含任何极大项, 记为1. A为矛盾式 ? A的主合析取范式含全部2n个极大项
M0?M2
? A的主析取范式不含任何极小项, 记为0. A为非重言式的可满足式
? A的主析取范式中至少含一个、但不是全 部极小项
? A的主合取范式中至少含一个、但不是全 部极大项. 例7 用主析取范式判断公式的类型:
(1) A? ?(p?q)?q (2) B? p?(p?q) (3) C? (p?q)?r 解
(1) A ? ?(? p?q)?q ? ( p??q)?q ? 0 矛盾式 (2) B ? ? p?(p?q) ? 1 ? m0?m1?m2?m3 重言式 (3) C ? ?(p?q)?r ? (?p??q)?r
? (?p??q?r)?(?p??q??r)?(?p??q?r) ?(?p?q?r)?(p??q?r)?(p?q?r)
? m0?m1?m3? m5?m7 非重言式的可满足式 3. 判断两个公式是否等值
例8 用主析取范式判以下每一组公式是否等值 ⑴ 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 显见，⑴中的两公式等值，而⑵的不等值. 4. 解实际问题
例9 某单位要从A,B,C三人中选派若干人出国考察, 需满足下 述条件:
(1) 若A去, 则C必须去; (2) 若B去, 则C不能去;
(3) A和B必须去一人且只能去一人. 问有几种可能的选派方案?
解 记 p:派A去, q:派B去, r:派C去
(1) p?r, (2) q??r, (3) (p??q)?(?p?q) 求下式的成真赋值
A=(p?r)?(q??r)?((p??q)?(?p?q)) 求A的主析取范式
A=(p?r)?(q??r)?((p??q)?(?p?q)) ? (?p?r)?(?q??r)?((p??q)?(?p?q)) ? ((?p??q)?(?p??r)?(r??q)?(r??r)) ?((p??q)?(?p?q))
? ((?p??q)?(p??q))?((?p??r)?(p??q)) ?((r??q)?(p??q))?((?p??q)?(?p?q)) ?((?p??r)?(?p?q))?((r??q)?(?p?q)) ? (p??q?r)?(?p?q??r) 成真赋值:101,010
结论: 方案1 派A与C去, 方案2 派B去 由主析取范式确定主合取范式
例10 设A有3个命题变项, 且已知A= m1?m3?m7, 求A的主合取 范式.
解 A的成真赋值是1,3,7的二进制表示, 成假赋值是在主析取 范式中没有出现的极小项的下角标0,2,4,5,6的二进制表示, 它 们恰好是A的主合取范式的极大项的下角标, 故 A ? M0?M2?M4?M5?M6 由主合取范式确定主析取范式 用真值表确定主范式
4. 联结词完备集
定义2.6 称F:{0,1}n? {0,1} 为n元真值函数.
{0,1}n={00…0, 00…1, …, 11…1}，包含 个长为n的0,1符号串. 共有 个n元真值函数. 1元真值函数 p
1元真值函数
p F0(1)F1(1)F2(1)F3(1) 0 0 0 1 1 1 0 1 0 1
2元真值函数 p q 0 0 0 1 1 0 1 1 p q 0 0 0 1 1 0 1 1 F0(2)F1(2)F2(2)F3(2)F4(2)F5(2)F6(2)F7(2)0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 F8(2)F9(2)(2)F10(2) (2)F11F12(2)F13(2)F14(2)F151 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 任何一个含n个命题变项的命题公式A都对应惟一的一个n元
真值函数 F , F 恰好为A的真值表. 等值的公式对应的真值函数相同. 例如：p?q, ?p?q 都对应
定义2.7 设S是一个联结词集合，如果任何n(n?1) 元真值函 数都可以由仅含S中的联结词构成的公式表示，则称S是联结 词完备集
若S是联结词完备集, 则任何命题公式都可由S中的联结词表示 定理2.6 S = {?, ?, ?}是联结词完备集 证明 由范式存在定理可证 推论 以下都是联结词完备集
(1) S1 = {?, ?, ?, ?} (2) S2 = {?, ?, ?, ?, ?} (3) S3 = {?, ?} (4) S4 = {?, ?} (5) S5 = {?, ?} 证明
(1),(2) 在联结词完备集中加入新的联结词后仍为完备集 (3) A?B ? ?(?A??B) (4) A?B ? ?(?A??B) (5) A?B??A?B
{?,?,?,?}不是联结词完备集, 0不能用它表示
它的子集{?},{?},{?},{?},{?,?},{?,?,?}等都不是
定义2.8 设 p, q 为两个命题, ?(p?q)称作p与q的与非式, 记作 p?q, 即 p?q ? ?(p?q), ?称为与非联结词
?(p?q) 称作 p 与 q 的或非式, 记作 p?q, 即 p?q ? ?(p?q), ? 称为或非联结词
定理2.7 {?}与{?}为联结词完备集. 证明 {?, ?, ?}为完备集
?p ? ?p??p ? ?(p?p) ? p?p p?q ? ?(?p??q) ? ?p??q ? (p?p)?(q?q) p?q ? ??(p?q) ? ?(p?q) ? (p?q)?(p?q) 得证{?}为联结词完备集. 对{?}类似可证
5. 可满足性问题与消解法
不含任何文字的简单析取式称作空简单析取式,记作?. 规定?是不可满足的.
约定:简单析取式不同时含某个命题变项和它的否定
S:合取范式, C:简单析取式, l:文字, ?:赋值, 带下角标或 ? 文字l的补lc:若l=p,则lc=?p;若l=?p,则lc=p. S?S?:S是可满足的当且仅当S? 是可满足的
定义2.9 设C1=l?C1?, C2=lc?C2?, C1?和C2?不含l和lc, 称C1??C2?为 C1和C2(以l和lc为消解文字)的消解式或消解结果, 记作 Res(C1,C2)
例如, Res(?p?q?r, p?q??s)= q?r??s 定理2.8 C1?C2?Res(C1,C2)
证 记C= Res(C1,C2)=C1??C2?, 其中l和lc为消解文字, C1=l?C1?, C2=lc?C2?, 且
C1?和C2?不含l和lc.
假设C1?C2是可满足的, ?是它的满足赋值, 不妨设?(l)=1. C2必含有文字l? ?l, lc且?(l? )=1. C中含有l?, 故?满足C.
反之, 假设C是可满足的, ?是它的满足赋值. C必有l? 使得 ?(l? )=1, 不妨设C1?含l?, 于是?满足C1. 把扩张到l(和lc)上: 若l=p, 则令?(p)=0; 若lc=p, 则令?(p)=1. 恒有?(lc)=1, 从而? 满足C2. 得证C1?C2是可满足的.
注意: C1?C2与Res(C1,C2)有相同的可满足性, 但不一定等值. 定义2.10 设S是一个合取范式, C1,C2,?,Cn是一个简单析取式 序列. 如果对每一个i(1?i?n), Ci是S的一个简单析取式或者是 Res(Cj,Ck)(1?j 定理2.9 一个合取范式是不可满足的当且仅当它有否证. 例11 用消解规则证明S=(?p?q)?(p?q??s)?(q?s)??q是不可 满足的. 证 C1=?p?q, C2= p?q??s, C3=Res(C1,C2)=q??s, C4=q?s, C5=Res(C3,C4)=q, C6=?q, C7=Res(C5,C6)=?, 这是S的否证. 消解算法 输入: 合式公式A 输出: 当A是可满足时, 回答“Yes”; 否则回答“No”. 1. 求A的合取范式S 2. 令S0??, S2??, S1?S的所有简单析取式 3. For C1?S0和C2?S1 4. If C1, C2可以消解 then 5. 计算C?Res(C1,C2) 6. If C=? then 7. 输出“No”, 计算结束 8. If C?S0且C? S1 then 9. S2?S2?{C} 10. For C1?S1, C2?S1且C1?C2 11. If C1, C2可以消解 then 12. 计算C?Res(C1,C2) 13. If C=? then 14. 输出“No”, 计算结束 15. If C?S0且C? S1 then 16. S2?S2?{C} 17. If S2=? then 18. 输出“Yes”, 计算结束 19. Else S0?S0?S1, S1?S2, S2??, goto 3 例12 用消解算法判断下述公式是否是可满足的: p?(p?q)?(p??q)?(q??r)?(q?r) 解 S= p?(p?q)?(p??q)?(q??r)?(q?r)