《ch命题逻辑等值演算实用实用教案》由会员分享，可在线阅读，更多相关《ch命题逻辑等值演算实用实用教案（63页珍藏版）》请在金锄头文库上搜索。
1、12.1等值式定义2.1 若等价式AB是重言式，则称A与B等值，记作AB，并称AB是等值式几点说明：定义中，A, B, 均为元语言符号 A或B中可能有哑元出现(chxin). 例如 (pq) (pq)(rr) r为左边公式的哑元. 用真值表可检查两个公式是否等值请验证： p(qr) (pq) r p(qr) 不与 (pq) r 等值第1页/共62页第一页，共63页。2等值式例题(lt)例1 判断下列各组公式(gngsh)是否等值: (1) p(qr) 与 (pq) r 11111101 11111101 11011101 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01
2、 1 1 (p q)rp(qr)qr p q rp q00000011 结论(jiln): p(jiln): p(q(qr) r) (p (p q) q) r r 第2页/共62页第二页，共63页。3等值式例题(lt) (2) p(qr) 与 (pq) r 01011101 11111101 11011101 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 (pq)rp(qr)qr p q rpq11110011 结论(jiln): p(jiln): p(q(qr) r) 与 (p (pq) q) r r 不等值第3页/共62页第三页，共63页。4基本(jbn
3、)等值式双重(shungchng)否定律 AA幂等律 AAA, AAA交换律 ABBA, ABBA结合律 (AB)CA(BC), (AB)CA(BC)分配律 A(BC)(AB)(AC), A (BC)(AB)(AC)德摩根律 (AB)AB (AB)AB吸收律 A(AB)A, A(AB)A第4页/共62页第四页，共63页。5基本(jbn)等值式零律 A 11, A00同一律 A 0A. A1A排中律 A A1矛盾律 A A0蕴涵(ynhn)等值式 ABAB等价等值式 AB(AB)(BA)假言易位 ABBA等价否定等值式 ABAB归谬论 (AB)(AB) A特别提示：必须牢记这16组等值式，这是继
4、续学习的基础第5页/共62页第五页，共63页。6等值演算(ynsun)与置换规则1. 等值演算由已知的等值式推演出新的等值式的过程2. 等值演算的基础： (1) 等值关系的性质：自反性、对称性、传递性 (2) 基本(jbn)的等值式 (3) 置换规则（见3）3. 置换规则 设 (A) 是含公式 A 的命题公式，(B) 是用公式 B 置换 (A) 中所有的 A 后得到的命题公式 若 BA，则 (B)(A)第6页/共62页第六页，共63页。7等值演算的应用(yngyng)(yngyng)举例证明两个公式等值例2 证明 p(qr) (pq)r证 p(qr) p(qr) （蕴涵等值式，置换规则） (p
5、q)r （结合律，置换规则） (pq)r （德摩根律，置换规则） (pq)r （蕴涵等值式，置换规则）今后在注明中省去置换规则注意(zh y)：用等值演算不能直接证明两个公式不等值第7页/共62页第七页，共63页。8证明两个公式不等值例3 证明 p(qr) 与 (pq)r 不等值证 方法一 真值表法, 见例1(2)方法二 观察法. 观察到000, 010是左边的成真赋值，是右边的成假赋值 方法三 先用等值演算化简公式，然后再观察 p(qr) pqr (pq)r (pq)r(pq)r 更容易(rngy)看出前面的两个赋值分别是左边的成真赋 值和右边的成假赋值等值演算的应用(yngyng)举例第8
6、页/共62页第八页，共63页。9判断公式类型(lixng): A为矛盾式当且仅当A 0 A 为重言式当且仅当A 1例4 用等值演算法判断下列公式的类型(lixng) (1) q(pq) (2) (pq)(qp) (3) (pq)(pq)r) 等值演算(ynsun)的应用举例解 (1) q(pq) q( p q) （蕴涵(ynhn)等值式） q (pq) （德摩根律） p (qq) （交换律，结合律） p 0 （矛盾律） 0 （零律）矛盾式第9页/共62页第九页，共63页。10判断(pndun)公式类型(2) (pq)(qp) (pq)(qp) （蕴涵(ynhn)等值式） (pq)(pq) （交
7、换律） 1重言式(3) (p q) (pq) r) (p (qq) r （分配律） p 1 r （排中律） p r （同一律）可满足(mnz)式，101和111是成真赋值，000和010等是成假赋值. 第10页/共62页第十页，共63页。112.2析取范式与合取范式基本概念(1)文字命题变项及其否定的总称(2)简单析取式有限(yuxin)个文字构成的析取式p,q,pq,pqr,(3)简单合取式有限(yuxin)个文字构成的合取式p,q,pq,pqr,(4)析取范式由有限(yuxin)个简单合取式组成的析取式p,pq,pq,(pq)(pqr)(qr)(5)合取范式由有限(yuxin)个简单析取式
8、组成的合取式p,pq,pq,(pq)p(pqr)(6)范式析取范式与合取范式的总称第11页/共62页第十一页，共63页。12范式(fnsh)概念说明：单个文字既是简单( jindn)析取式，又是简单( jindn)合取式形如pqr,pqr的公式既是析取范式，又是合取范式第12页/共62页第十二页，共63页。13范式(fnsh)的性质定理2.1 (1) 一个简单析取式是重言式当且仅当它同时含有某个命题变项和它的否定(fudng)式.(2) 一个简单合取式是矛盾式当且仅当它同时含有某个命题变项和它的否定(fudng)式.定理2.2 (1) 一个析取范式是矛盾式当且仅当它每个简单合取式都是矛盾式.(
9、2) 一个合取范式是重言式当且仅当它的每个简单析取式都是重言式.第13页/共62页第十三页，共63页。14命题(mngt)公式的范式定理2.3（范式存在定理） 任何命题公式(gngsh)都存在与之等值的析取范式与合取范式公式(gngsh)A的析取(合取)范式与A等值的析取(合取)范式求公式(gngsh)A的范式的步骤： (1) 消去A中的, （若存在） ABAB AB(AB)(AB) (2) 否定联结词的内移或消去 A A (AB)AB (AB)AB第14页/共62页第十四页，共63页。15命题(mngt)公式的范式 (3) 使用分配律 A(BC)(AB)(AC) 求合取范式(fn sh) A
10、(BC) (AB)(AC) 求析取范式(fn sh)公式范式(fn sh)的不足不惟一第15页/共62页第十五页，共63页。16求公式(gngsh)的范式例5求下列公式的析取范式与合取范式(1)(pq)r(2)(pq)r解(1)(pq)r(pq)r（消去）pqr（结合律）最后结果既是析取范式(由3个简单( jindn)合取式组成的析取式)，又是合取范式(由一个简单( jindn)析取式组成的合取式)第16页/共62页第十六页，共63页。17 (2) (pq)r (pq)r （消去第一个） (pq)r （消去第二个） (pq)r （否定(fudng)号内移德摩根律) 析取范式 (pr)(qr)
11、（对分配律） 合取范式求公式(gngsh)的范式第17页/共62页第十七页，共63页。18极小(j xio)(j xio)项与极大项定义2.4 在含有n个命题变项的简单合取式（简单析取式）中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第i个文字出现在左起第i位上（1in），称这样的简单合取式（简单析取式）为极小项（极大项）.几点说明：n个命题变项有2n个极小项和2n个极大项2n个极小项（极大项）均互不等值用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示. 用Mi表示第i个极大项，其中i是该极大项成假赋值的十进制表示. mi（Mi）称为(chn wi)极小项（极大项）的
12、名称. 第18页/共62页第十八页，共63页。19实例(shl)由两个命题(mngt)变项p,q形成的极小项与极大项极小项极小项极大项极大项公式公式成真赋值成真赋值名称名称公式公式成假赋值成假赋值名称名称 pq p qpqp q 0 0 0 1 1 0 1 1 m0m1m2m3 p q pq p q pq 0 0 0 1 1 0 1 1M0M1M2M3第19页/共62页第十九页，共63页。20实例(shl)极小项极小项极大项极大项公式公式成真赋值成真赋值名称名称公式公式成假赋值成假赋值名称名称 p q r p q r p q r p q rp q rp q rp q rp q r0 0 00
13、0 10 1 00 1 11 0 01 0 11 1 01 1 1 m0m1m2m3m4m5m6m7 p q r p q r p q r p q r p q r p q r p q r p q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 M0M1M2M3M4M5M6M7由三个命题(mng t)变项 p, q, r 形成的极小项与极大项. mi与Mi的关系(gun x)： mi Mi, Mi mi 第20页/共62页第二十页，共63页。21主析取范式与主合取范式主析取范式由极小项构成的析取范式主合取范式由极大项构成的合取范式例如，n=3,命题变项为p,q,
14、r时，(pqr)(pqr)m1m3主析取范式(pqr)(pqr)M1M7主合取范式公式A的主析取(合取)范式与A等值的主析取(合取)范式定理2.5(主范式的存在(cnzi)惟一定理)任何命题公式都存在(cnzi)与之等值的主析取范式和主合取范式,并且是惟一的第21页/共62页第二十一页，共63页。22求公式主范式(fn sh)(fn sh)的步骤求公式主析取范式的步骤(bzhu):设公式A含命题变项p1,p2,pn(1) 求A的析取范式A =B1 B2 Bs , 其中Bj是简单合取 式 j=1,2, ,s (2) 若某个Bj既不含pi, 又不含 pi, 则将Bj展开成 Bj Bj (pipi)
15、 (Bj pi) (Bjpi) 重复这个过程, 直到所有简单合取式都是长度为n的极 小项为止(3) 消去重复出现的极小项, 即用mi代替mi mi(4) 将极小项按下标从小到大排列第22页/共62页第二十二页，共63页。23求公式主范式(fn sh)(fn sh)的步骤求公式的主合取范式的步骤(bzhu):设公式A含命题变项p1,p2,pn(1) 求A的合取范式A=B1B2 Bs , 其中Bj是简单析取 式 j=1,2, ,s (2) 若某个Bj既不含pi, 又不含pi, 则将Bj展开成 Bj Bj(pipi) (Bjpi)(Bjpi) 重复这个过程, 直到所有简单析取式都是长度为n的极 大项
16、为止(3) 消去重复出现的极大项, 即用Mi代替MiMi(4) 将极大项按下标从小到大排列第23页/共62页第二十三页，共63页。24实例(shl)例6 (1) 求公式(gngsh) A=(pq)r的主析取范式和主合取范式 解 (pq)r (pq)r （析取范式） (pq) (pq)(rr) (pqr)(pqr) m6m7 r (pp)(qq)r (pqr)(pqr)(pqr)(pqr) m1m3m5m7 , 代入并排序，得 (pq)r m1m3m5 m6m7 （主析取范式）第24页/共62页第二十四页，共63页。25实例(shl) (pq)r (pr)(qr) （合取范式） pr p(qq)
17、r (pqr)(pqr) M0M2 qr (pp)qr (pqr)(pqr) M0M4 , 代入 并排序(pi x)，得 (pq)r M0M2M4 （主合取范式）第25页/共62页第二十五页，共63页。26主范式(fn sh)(fn sh)的应用1.求公式的成真成假赋值 设公式A含n个命题变项, A的主析取范式有s个极小(j xio)项, 则A 有s个成真赋值, 它们是极小(j xio)项下标的二进制表示, 其余2n-s 个赋值都是成假赋值 例如 (pq)r m1m3m5 m6m7成真赋值为 001, 011, 101, 110, 111，成假赋值为 000, 010, 100. 类似地，由主
18、合取范式也立即求出成假赋值和成真赋值. 第26页/共62页第二十六页，共63页。272. 判断公式(gngsh)的类型 设A含n个命题变项. A为重言式 A的主析取范式含全部2n个极小项 A的主合取范式不含任何极大项, 记为1. A为矛盾式 A的主合析取范式含全部2n个极大项 A的主析取范式不含任何极小项, 记为0. A为非重言式的可满足式 A的主析取范式中至少含一个、但不是全 部极小项 A的主合取范式中至少含一个、但不是全 部极大项.主范式(fnsh)的应用第27页/共62页第二十七页，共63页。28例7 用主析取范式判断公式(gngsh)的类型:(1) A (pq)q (2) B p(pq
19、) (3) C (pq)r解 (1) A ( pq)q ( pq)q 0 矛盾式(2) B p(pq) 1 m0m1m2m3 重言式(3) C (pq)r (pq)r (pqr)(pqr)(pqr) (pqr)(pqr)(pqr) m0m1m3 m5m7 非重言式的可满足式主范式(fnsh)的应用第28页/共62页第二十八页，共63页。293. 判断(pndun)两个公式是否等值例8 用主析取范式判以下每一组公式是否等值 p(qr) 与 (pq)r p(qr) 与 (pq)r解 p(qr) = m0m1m2m3 m4m5 m7 (pq)r = m0m1m2m3 m4m5 m7 (pq)r =
20、m1m3 m4m5 m7显见，中的两公式等值，而的不等值.主范式(fnsh)的应用第29页/共62页第二十九页，共63页。304. 解实际问题例9 某单位要从A,B,C三人中选派若干人出国考察, 需满足下 述条件: (1) 若A去, 则C必须去; (2) 若B去, 则C不能去; (3) A和B必须去一人且只能(zh nn)去一人. 问有几种可能的选派方案?解 记 p:派A去, q:派B去, r:派C去(1) pr, (2) qr, (3) (pq)(pq)求下式的成真赋值 A=(pr)(qr)(pq)(pq)主范式(fnsh)的应用第30页/共62页第三十页，共63页。31求A的主析取范式 A
21、=(pr)(qr)(pq)(pq) (pr)(qr)(pq)(pq) (pq)(pr)(rq)(rr) (pq)(pq) (pq)(pq)(pr)(pq) (rq)(pq)(pq)(pq) (pr)(pq)(rq)(pq) (pqr)(pqr)成真赋值:101,010结论(jiln): 方案1 派A与C去, 方案2 派B去主范式(fnsh)的应用第31页/共62页第三十一页，共63页。32由主析取范式确定(qudng)主合取范式例10 设A有3个命题变项, 且已知A= m1m3m7, 求A的主合取范式.解 A的成真赋值是1,3,7的二进制表示, 成假赋值是在主析取范式中没有出现的极小项的下角标
22、0,2,4,5,6的二进制表示, 它们恰好是A的主合取范式的极大项的下角标, 故 A M0M2M4M5M6用成真赋值和成假赋值确定(qudng)主范式由主合取范式确定(qudng)主析取范式用真值表确定(qudng)主范式 第32页/共62页第三十二页，共63页。332.3 联结词的完备(wnbi)集定义定义2.6 称称F:0,1n 0,1 为为n元真值函数元真值函数. 0,1n=000, 001, , 111，包含，包含 个长为个长为n的的0,1符号串符号串. 共有共有 个个n元真值函数元真值函数. 1元真值函数元真值函数 p 0 0 0 1 1 1 0 1 0 1 第33页/共62页第三十
23、三页，共63页。34真值函数(hnsh)p q0 00 11 01 1 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 1p q0 00 11 01 1 1 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 12元真值函数(hnsh)第34页/共62页第三十四页，共63页。35公式(gngsh)与真值函数任何一个含任何一个含n个命题变项的命题公式个命题变项的命题公式A都对应惟一的一个都对应惟一的一个n元元真值函数真值函数 F , F 恰好为恰好为A的
24、真值表的真值表. 等值的公式对应的真值函数相同等值的公式对应的真值函数相同. 例如：例如：pq, p q 都对应都对应第35页/共62页第三十五页，共63页。36联结词完备(wnbi)集定义2.7设S是一个(y)联结词集合，如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集若S是联结词完备集,则任何命题公式都可由S中的联结词表示定理2.6S=,是联结词完备集证明由范式存在定理可证第36页/共62页第三十六页，共63页。37联结词完备(wnbi)集推论 以下都是联结词完备集 (1) S1 = , , , (2) S2 = , , , , (3) S3 = ,
25、 (4) S4 = , (5) S5 = , 证明(zhngmng)(1),(2) 在联结词完备集中加入新的联结词后仍为完备集(3) AB (AB)(4) AB (AB)(5) ABAB , ,不是不是(b shi)联结词完备集联结词完备集, 0不能用它表示不能用它表示它的子集它的子集 , , , , , ,等都不是等都不是(b shi)第37页/共62页第三十七页，共63页。38复合(fh)联结词定义2.8 设 p, q 为两个(lin )命题, (pq)称作p与q的与非式, 记作pq, 即 pq (pq), 称为与非联结词(pq) 称作 p 与 q 的或非式, 记作 pq, 即 pq (p
26、q), 称为或非联结词定理2.7 与为联结词完备集. 证明 , , 为完备集 p pp (pp) pp pq (pq) pq (pp)(qq) pq (pq) (pq) (pq)(pq) 得证为联结词完备集. 对类似可证第38页/共62页第三十八页，共63页。392.4 可满足(mnz)性问题与消解法不含任何文字的简单析取式称作空简单析取式,记作.规定是不可满足的. 约定:简单析取式不同时含某个命题变项和它的否定S:合取范式, C:简单析取式, l:文字, :赋值, 带下(dixi)角标或 文字l的补lc:若l=p,则lc=p;若l=p,则lc=p.SS :S是可满足的当且仅当S 是可满足的定
27、义2.9 设C1=lC1, C2=lcC2, C1和C2不含l和lc, 称C1C2为C1和C2(以l和lc为消解文字)的消解式或消解结果, 记作Res(C1,C2)例如, Res(pqr, pqs)= qrs第39页/共62页第三十九页，共63页。40消解(xioji)规则定理2.8 C1C2Res(C1,C2)证 记C= Res(C1,C2)=C1C2, 其中l和lc为消解文字, C1=lC1, C2=lcC2, 且C1和C2不含l和lc. 假设C1C2是可满足的, 是它的满足赋值, 不妨设(l)=1. C2必含有文字l l, lc且(l )=1. C中含有l, 故满足C. 反之, 假设C是
28、可满足的, 是它的满足赋值. C必有l 使得(l )=1, 不妨设C1含l, 于是满足C1. 把扩张(kuzhng)到l(和lc)上:若l=p, 则令(p)=0; 若lc=p, 则令(p)=1. 恒有(lc)=1, 从而满足C2. 得证C1C2是可满足的.注意: C1C2与Res(C1,C2)有相同的可满足性, 但不一定等值.第40页/共62页第四十页，共63页。41消解(xioji)序列与合取范式的否证定义2.10 设S是一个合取范式, C1,C2,Cn是一个简单(jindn)析取式序列. 如果对每一个i(1in), Ci是S的一个简单(jindn)析取式或者是Res(Cj,Ck)(1jki
29、), 则称此序列是由S导出Cn的消解序列. 当Cn=时, 称此序列是S的一个否证.定理2.9 一个合取范式是不可满足的当且仅当它有否证.例11 用消解规则证明S=(pq)(pqs)(qs)q是不可满足的.证 C1=pq, C2= pqs, C3=Res(C1,C2)=qs, C4=qs, C5=Res(C3,C4)=q, C6=q, C7=Res(C5,C6)=, 这是S的否证.第41页/共62页第四十一页，共63页。42消解(xioji)算法消解算法输入: 合式公式A输出: 当A是可满足时, 回答“Yes”; 否则回答“No”.1. 求A的合取范式S2. 令S0, S2, S1S的所有简单析
30、取式3. For C1S0和C2S14. If C1, C2可以消解 then5. 计算(j sun)CRes(C1,C2)6. If C= then7. 输出“No”, 计算(j sun)结束 8. If CS0且C S1 then9. S2S2C第42页/共62页第四十二页，共63页。43消解(xioji)算法10. For C1S1, C2S1且C1C211. If C1, C2可以消解(xioji) then12. 计算CRes(C1,C2)13. If C= then14. 输出“No”, 计算结束 15. If CS0且C S1 then16. S2S2C17. If S2= th
31、en 18. 输出“Yes”, 计算结束19. Else S0S0S1, S1S2, S2, goto 3第43页/共62页第四十三页，共63页。44消解算法(sunf)例题例12 用消解算法判断(pndun)下述公式是否是可满足的: p(pq)(pq)(qr)(qr)解 S= p(pq)(pq)(qr)(qr)循环1 S0=, S1=p, pq, pq, qr, qr, S2= Res(pq, pq)=p Res(pq, qr)=pr Res(pq, qr)= pr Res(qr, qr)=q S2=pr, pr, q循环2 S0=p, pq, pq, qr, qr, S1=pr, pr,
32、q, S2= Res(pq, q)=p第44页/共62页第四十四页，共63页。45消解算法(sunf)例题 Res(qr, pr)=pq Res(qr, pr)=pq Res(pr, pr)=p S2= 输出(shch)“Yes”第45页/共62页第四十五页，共63页。46第二章习题课作业：P42 4 (1),(3); 5 (1),(3) ;8 (3);12 ;27(1);30主要内容等值式与等值演算基本等值式（16组，24个公式(gngsh)）主析取范式与主合取范式联结词完备集消解法第46页/共62页第四十六页，共63页。47基本(jbn)要求l深刻理解等值式的概念深刻理解等值式的概念l牢记
33、基本等值式的名称及它们的内容牢记基本等值式的名称及它们的内容l熟练地应用基本等值式及置换规则进行等值演算熟练地应用基本等值式及置换规则进行等值演算l理解文字、简单析取式、简单合取式、析取范式、合取范理解文字、简单析取式、简单合取式、析取范式、合取范式的概念式的概念l深刻理解极小项、极大项的概念、名称及下角标与成真、深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系，并理解简单析取式与极小项的关系成假赋值的关系，并理解简单析取式与极小项的关系l熟练掌握求主范式的方法（等值演算、真值表等）熟练掌握求主范式的方法（等值演算、真值表等）l会用主范式求公式的成真赋值、成假赋值、判断公式的类
34、会用主范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值型、判断两个公式是否等值l会将公式等值地化成指定联结词完备集中的公式会将公式等值地化成指定联结词完备集中的公式l会用命题逻辑的概念及运算解决简单的应用问题会用命题逻辑的概念及运算解决简单的应用问题(wnt)l掌握消解规则及其性质掌握消解规则及其性质l会用消解算法判断公式的可满足性会用消解算法判断公式的可满足性第47页/共62页第四十七页，共63页。48练习(linx)1:概念1. 设A与B为含n个命题变项的公式，判断下列(xili)命题是否为真？(1) AB当且仅当A与B有相同的主析取范式(2) 若A为重言式，则A的主合
35、取范式为0(3) 若A为矛盾式，则A的主析取范式为1(4) 任何公式都能等值地化成, 中的公式(5) 任何公式都能等值地化成, , 中的公式说明:(2) 重言式的主合取范式不含任何极大项，为1. (3) 矛盾(modn)式的主合析范式不含任何极小项, 为0. (4) , 不是完备集，如矛盾(modn)式不能写成 , 中的公式. (5) , 是完备集. 真真假假假假假假真真第48页/共62页第四十八页，共63页。49练习2: 判断公式(gngsh)类型解用等值演算法求主范式(fnsh)(pq)(qp)(pq)(qp)(pq)(qp)(pq)(pq)(pq)(pq)m2m1m3m0m0m1m2m3
36、主析取范式(fnsh)1 主合取范式(fnsh)2. 判断下列(xili)公式的类型: (1) (pq)( qp)重言式重言式第49页/共62页第四十九页，共63页。50练习题2(续)解用等值演算法求公式(gngsh)的主范式(pq)q(pq)qpqq0 主析取范式M0M1M2M3主合取范式(2) (pq) q矛盾矛盾(modn)式式第50页/共62页第五十页，共63页。51解用等值演算法求公式(gngsh)的主范式(pq)p(pq)pp(pq)(pq)m0m1主析取范式M2M3主合取范式(3) (pq)p练习(linx)2(续)非重言式的可满足非重言式的可满足(mnz)式式第51页/共62页
37、第五十一页，共63页。52练习(linx)3：求公式的主范式3已知命题(mng t)公式A中含3个命题(mng t)变项p, q, r，并知道它的成真赋值为001, 010, 111, 求A的主析取范式和主合取范式，及A对应的真值函数.解 A的主析取范式为m1 m2 m7A的主合取范式为M0 M3 M4 M5 M6 p q r F p q r F0 0 0 0 1 0 0 00 0 1 1 1 0 1 00 1 0 1 1 1 0 00 1 1 0 1 1 1 1第52页/共62页第五十二页，共63页。53练习(linx)4：联结词完备集4将A=(pq)r改写(gixi)成下述各联结词集中的公
38、式:(1),(2),(3),(4),(5)(6)解解 (1) (pq) r ( pq) r (2) (pq) r (p q) r (3) (pq) r ( pq) r ( ( pq)r)第53页/共62页第五十三页，共63页。54练习(linx)4解答(4)(pq)r(pq)r)(pq)r)(5)(pq)r(pq)r(pq)r(pq)r)(pq)r)(pq)r)(6)(pq)r(pq)r(pq)r)(pq)r(pp)(qq)(rr)说明(shumng)：答案不惟一第54页/共62页第五十四页，共63页。55练习(linx)5：应用题5. 某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些
39、人出国学习(xux). 选派必须满足以下条件：(1) 若赵去，钱也去.(2) 李、周两人中至少有一人去(3) 钱、孙两人中去且仅去一人.(4) 孙、李两人同去或同不去.(5) 若周去，则赵、钱也去. 用等值演算法分析该公司如何选派他们出国？第55页/共62页第五十五页，共63页。56练习(linx)5解答解此类问题的步骤：1.设简单命题并符号化2.用复合命题描述各条件3.写出由复合命题组成的合取式4.将合取式成析取式（最好是主析取范式）5.求成(qichn)真赋值,并做出解释和结论第56页/共62页第五十六页，共63页。57练习(linx)5解答解1.设简单命题并符号化设p:派赵去，q:派钱去
40、，r:派孙去，s:派李去，u:派周去2.写出复合(fh)命题(1)若赵去，钱也去pq(2)李、周两人中至少有一人去su(3)钱、孙两人中去且仅去一人(qr)(qr)(4)孙、李两人同去或同不去(rs)(rs)(5)若周去，则赵、钱也去u(pq)第57页/共62页第五十七页，共63页。583. 设(1)(5)构成的合取式为A A = (p q)(su)(qr)(qr) (rs)(rs)(u(pq)4. 化成(hu chn)析取式 A (pqrsu)(pqrsu)结论：由上述析取式可知，A的成真赋值为00110与11001， 派孙、李去（赵、钱、周不去） 派赵、钱、周去（孙、李不去）练习(linx
41、)5解答第58页/共62页第五十八页，共63页。59练习(linx)5解答A (pq)(qr)(qr) (su)(u(pq) (rs)(rs) B1=(pq)(qr)(qr) (pqr)(pqr)(qr) （分配律） B2=(su)(u(pq) (su)(pqs)(pqu) （分配律） B1B2 (pqrsu)(pqrsu) (qrsu)(pqrs)(pqru)再令 (rs)(rs)=B3，则 B1B2B3 (pqrsu)(pqrsu)第59页/共62页第五十九页，共63页。60练习(linx)6:消解法6. 构造(guzo)公式A=(pq)( qr) (pq)r的否证, 从而证明它是矛盾式.
42、解 消解序列: pq A的简单析取式 pq A的简单析取式 q ,消解 qr A的简单析取式 r A的简单析取式 q ,消解 ,消解这是A的一个否证, 从而证明A是矛盾式. 第60页/共62页第六十页，共63页。61练习(linx)7:消解法7. 用消解法判断(pndun)下述公式是否是可满足的: (pq)(qr)(qr)解 S=(pq)(qr)(qr)第1次循环 S0=,S1=pq, qr, qr, S2=pq, qr 消解得到pr qr, qr消解得到rS2=pr,r第2次循环 S0=pq, qr, qr,S1=pr,r, S2=S2=输出“Yes”,计算结束. 第61页/共62页第六十一页，共63页。62感谢您的欣赏(xnshng)！第62页/共62页第六十二页，共63页。内容(nirng)总结1。p, q, pq, pqr,。p, q, pq, pqr,。p, pq, pq, (pq)(pqr)(qr)。p, pq, pq, (pq)p(pqr)。(1) A ( pq)q ( pq)q 0 矛盾(modn)式第六十三页，共63页。
