离散数学 命题逻辑等值演算ppt课件.ppt

1/63,2.1 等值式,定义2.1 若等价式AB是重言式，则称A与B等值，记作AB，并称AB是等值式。几点说明：定义中，A,B,均为元语言符号用真值表可检查两个公式是否等值,2/63,等值式例题,例1 判断下列各组公式是否等值。(1)p(qr)与(pq)r,结论:p(qr)(pq)r,3/63,等值式例题,(2)p(qr)与(pq)r,结论:p(qr)与(pq)r 不等值,4/63,基本等值式,双重否定律 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,5/63,基本等值式,零律 A11,A00同一律 A0A.A1A排中律 AA1矛盾律 AA0蕴涵等值式 ABAB等价等值式 AB(AB)(BA)假言易位 ABBA等价否定等值式 ABAB归谬论(AB)(AB)A特别提示：必须牢记这16组等值式(24式)，这是继续学习的基础。,6/63,等值演算与置换规则,1.等值演算由已知的等值式推演出新的等值式的过程2.等值演算的基础：(1)等值关系的性质：自反性、对称性、传递性(2)基本的等值式(3)置换规则3.置换规则 设(A)是含公式 A 的命题公式，(B)是用公式 B 置换(A)中所有的 A 后得到的命题公式。若 BA，则(B)(A)。,7/63,等值演算的应用举例,证明两个公式等值例2 证明 p(qr)(pq)r证 p(qr)p(qr)（蕴涵等值式，置换规则）(pq)r（结合律，置换规则）(pq)r（德摩根律，置换规则）(pq)r（蕴涵等值式，置换规则）注意：用等值演算不能直接证明两个公式不等值,8/63,证明两个公式不等值例3 证明 p(qr)与(pq)r 不等值证 方法一 真值表法,见例1(2)方法二 观察法。观察到000,010是左边的成真 赋值，是右边的成假赋值 方法三 先用等值演算化简公式，然后再观察 p(qr)pqr(pq)r(pq)r(pq)r 更容易看出前面的两个赋值分别是左边的成真赋值和右边的成假赋值,等值演算的应用举例,9/63,判断公式类型:A为矛盾式当且仅当A 0 A为重言式当且仅当A 1例4 用等值演算法判断下列公式的类型(1)q(pq)(2)(pq)(qp)(3)(pq)(pq)r),等值演算的应用举例,10/63,等值演算的应用举例,解(1)q(pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0（矛盾律）0（零律）矛盾式,11/63,判断公式类型,(2)(pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1重言式,(3)(pq)(pq)r)(p(qq)r（分配律）p1r（排中律）pr（同一律）可满足式，101和111是成真赋值，000和010等是成假赋值.,12/63,2.2 析取范式与合取范式,基本概念(1)文字命题变项及其否定的总称(2)简单析取式仅由有限个文字构成的析取式 p,q,pq,pqr,(3)简单合取式仅由有限个文字构成的合取式 p,q,pq,pqr,(4)析取范式由有限个简单合取式组成的析取式 p,pq,pq,(pq)(pqr)(qr)(5)合取范式由有限个简单析取式组成的合取式 p,pq,pq,(pqp(pqr)(6)范式析取范式与合取范式的总称,13/63,说明：单个文字既是简单析取式，又是简单合取式形如 pqr,pqr 的公式既是析取范式，又是合取范式,定理2.1(1)一个简单析取式是重言式当且仅当它同时含有某个命题变项和它的否定式。(2)一个简单合取式是矛盾式当且仅当它同时含有某个命题变项和它的否定式。,14/63,范式的性质,定理2.2(1)一个析取范式是矛盾式当且仅当它每个简单合取式都是矛盾式。(2)一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。,定理2.3（范式存在定理）任何命题公式都存在与之等值的析取范式与合取范式。,15/63,命题公式的范式,求公式A的范式的步骤：(1)消去A中的,（若存在）ABAB AB(AB)(AB)(2)否定联结词的内移或消去 A A(AB)AB(AB)AB,(3)使用分配律 A(BC)(AB)(AC)求合取范式 A(BC)(AB)(AC)求析取范式公式范式的不足不惟一,16/63,求公式的范式,例5 求下列公式的析取范式与合取范式(1)(pq)r(2)(pq)r解(1)(pq)r(pq)r（消去）pqr（结合律）最后结果既是析取范式(由3个简单合取式组成的析取式)，又是合取范式(由一个简单析取式组成的合取式)。,17/63,(2)(pq)r(pq)r（消去第一个）(pq)r（消去第二个）(pq)r（否定号内移)析取范式(pr)(qr)（对分配律）合取范式,求公式的范式,18/63,极小项与极大项,定义2.4 在含有n个命题变项的简单合取式（简单析取式）中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第i个文字出现在左起第i位上（1in），称这样的简单合取式（简单析取式）为极小项（极大项）。几点说明：n个命题变项有2n个极小项和2n个极大项2n个极小项（极大项）均互不等值用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示.用Mi表示第i个极大项，其中i是该极大项成假赋值的十进制表示.mi（Mi）称为极小项（极大项）的名称。,19/63,实例,由两个命题变项 p,q 形成的极小项与极大项,20/63,实例,由三个命题变项 p,q,r 形成的极小项与极大项。,mi与Mi的关系：mi Mi,Mi mi,21/63,主析取范式与主合取范式,主析取范式由极小项构成的析取范式主合取范式由极大项构成的合取范式例如，n=3,命题变项为 p,q,r 时，(pqr)(pqr)m1m3 主析取范式(pqr)(pqr)M1M7主合取范式定理2.5(主范式的存在惟一定理)任何命题公式都存在与之等值的主析取范式和主合取范式,并且是惟一的。,22/63,求公式主范式的步骤,求公式主析取范式的步骤:设公式A含命题变项p1,p2,pn(1)求A的析取范式A=B1 B2 Bs,其中Bj是简单合取式 j=1,2,s(2)若某个Bj既不含pi,又不含pi,则将Bj展开成 Bj Bj(pipi)(Bjpi)(Bjpi)重复这个过程,直到所有简单合取式都是长度为n的极小项为止(3)消去重复出现的极小项,即用mi代替mimi(4)将极小项按下标从小到大排列,23/63,求公式主范式的步骤,求公式的主合取范式的步骤:设公式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的极大项为止(3)消去重复出现的极大项,即用Mi代替MiMi(4)将极大项按下标从小到大排列,24/63,实例,例6(1)求公式 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(主析取范式),25/63,实例,(pq)r(pr)(qr)（合取范式）pr p(qq)r(pqr)(pqr)M0M2 qr(pp)qr(pqr)(pqr)M0M4,代入 并排序，得(pq)r M0M2M4(主合取范式),26/63,主范式的应用,1.求公式的成真成假赋值 设公式A含n个命题变项,A的主析取范式有s个极小项,则A有s个成真赋值,它们是极小项下标的二进制表示,其余2n-s个赋值都是成假赋值 例如(pq)r m1m3m5 m6m7成真赋值为 001,011,101,110,111，成假赋值为 000,010,100.类似地，由主合取范式也立即求出成假赋值和成真赋值。,27/63,2.判断公式的类型 设A含n个命题变项.A为重言式 A的主析取范式含全部2n个极小项 A的主合取范式不含任何极大项,记为1.A为矛盾式 A的主合析取范式含全部2n个极大项 A的主析取范式不含任何极小项,记为0.A为非重言式的可满足式 A的主析取范式中至少含一个、但不是全部极小项.A的主合取范式中至少含一个、但不是全部极大项.,主范式的应用,28/63,例7 用主析取范式判断公式的类型:(1)A(pq)q(2)B p(pq)(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 非重言式的可满足式,主范式的应用,29/63,3.判断两个公式是否等值例8 用主析取范式判以下每一组公式是否等值 p(qr)与(pq)r p(qr)与(pq)r解 p(qr)=m0m1m2m3 m4m5 m7(pq)r=m0m1m2m3 m4m5 m7(pq)r=m1m3 m4m5 m7显见，中的两公式等值，而的不等值.,主范式的应用,30/63,4.解实际问题例9 某单位要从A,B,C三人中选派若干人出国考察,需满足下述条件:(1)若A去,则C必须去;(2)若B去,则C不能去;(3)A和B必须去一人且只能去一人.问有几种可能的选派方案?解 记 p:派A去,q:派B去,r:派C去(1)pr,(2)qr,(3)(pq)(pq)求下式的成真赋值 A=(pr)(qr)(pq)(pq),主范式的应用,31/63,求A的主析取范式 A=(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结论:方案1 派A与C去,方案2 派B去,主范式的应用,32/63,由主析取范式确定主合取范式例10 设A有3个命题变项,且已知A=m1m3m7,求A的主合取范式.解 A的成真赋值是1,3,7的二进制表示,成假赋值是在主析取范式中没有出现的极小项的下角标0,2,4,5,6的二进制表示,它们恰好是A的主合取范式的极大项的下角标,故 A M0M2M4M5M6,用成真和成假赋值确定主范式,说明：1)由主合取范式确定主析取范式 2)用真值表确定主范式,33/63,2.3 联结词的完备集,定义2.6 称F:0,1n 0,1 为n元真值函数。0,1n=000,001,111，包含 个长为n的0,1符号串.共有 个n元真值函数。,34/63,真值函数,2元真值函数,35/63,公式与真值函数,任何一个含n个命题变项的命题公式A都对应惟一的一个n元真值函数 F,F 恰好为A的真值表。等值的公式对应的真值函数相同。例如：pq,pq 都对应,说明：真值函数与主析取范式（主合取范式）,36/63,联结词完备集,定义2.7 设S是一个联结词集合，如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。若S是联结词完备集,则任何命题公式都可由S中的联结词表示。定理2.6 S=,是联结词完备集。证明 由范式存在定理可证。,37/63,联结词完备集,推论 以下都是联结词完备集(1)S1=,(2)S2=,(3)S3=,(4)S4=,(5)S5=,证明(1),(2)显然。(3)AB(AB)(4)AB(AB)(5)ABAB,不是联结词完备集,0不能用它表示；它的子集,等都不是。,38/63,复合联结词,定义2.8 设 p,q 为两个命题,(pq)称作p与q的与非式,记作pq,即 pq(pq),称为与非联结词。(pq)称作 p 与 q 的或非式,记作 pq,即 pq(pq),称为或非联结词。定理2.7 与为联结词完备集。证明,为完备集 p pp(pp)pp pq(pq)pq(pp)(qq)pq(pq)(pq)(pq)(pq)得证为联结词完备集。对类似可证。,39/63,2.4 可满足性问题与消解法,命题公式的可满足性问题任何一个命题公式都能化成等值的合取范式（由有限个简单析取式组成的合取式）约定：简单析取式不同时含某个命题变项和它的否定。不含任何文字的简单析取式称作空简单析取式,记作.规定：是不可满足的。,40/63,2.4 可满足性问题与消解法,S:合取范式,C:简单析取式,l:文字,:赋值.带下角标或 文字l的补lc:若l=p,则lc=p;若l=p,则lc=p.SS:S是可满足的当且仅当S 是可满足的.定义2.9 设C1=lC1,C2=lcC2,C1和C2不含l和lc,称C1C2为C1和C2(以l和lc为消解文字)的消解式或消解结果,记作Res(C1,C2)。亦即Res(C1,C2)=C1C2。例如,Res(pqr,pqs)=qrs,41/63,消解规则,定理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是可满足的,是它的满足赋值.C必有l 使得(l)=1,不妨设C1含l,于是满足C1.把扩张到l(和lc)上:若l=p,则令(p)=0;若lc=p,则令(p)=1.恒有(lc)=1,从而满足C2.得证C1C2是可满足的.注意:C1C2与Res(C1,C2)有相同的可满足性,但不一定等值.,42/63,消解序列与合取范式的否证,定义2.10 设S是一个合取范式,C1,C2,Cn是一个简单析取式序列.如果对每一个i(1in),Ci是S的一个简单析取式或者是Res(Cj,Ck)(1jki),则称此序列是由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的否证.,43/63,消解算法,输入:合式公式A输出:当A是可满足时,回答“Yes”;否则回答“No”.1.求A的合取范式S2.令S0,S2,S1S的所有简单析取式3.For C1S0和C2S14.If C1,C2可以消解 then5.计算CRes(C1,C2)6.If C=then7.输出“No”,计算结束 8.If CS0且C S1 then9.S2S2C,44/63,消解算法,10.For C1S1,C2S1且C1C211.If C1,C2可以消解 then12.计算CRes(C1,C2)13.If C=then14.输出“No”,计算结束 15.If CS0且C S1 then16.S2S2C17.If S2=then 18.输出“Yes”,计算结束19.Else S0S0S1,S1S2,S2,goto 3,45/63,消解算法例题,例12 用消解算法判断下述公式是否是可满足的: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,46/63,消解算法例题,Res(qr,pr)=pq Res(qr,pr)=pq Res(pr,pr)=p S2=输出“Yes”,循环2 S0=p,pq,pq,qr,qr,S1=pr,pr,q,S2=Res(pq,q)=p,47/63,练习1:概念,1.设A与B为含n个命题变项的公式，判断下列命题是否为真？(1)AB当且仅当A与B有相同的主析取范式(2)若A为重言式，则A的主合取范式为0(3)若A为矛盾式，则A的主析取范式为1(4)任何公式都能等值地化成,中的公式(5)任何公式都能等值地化成,中的公式,真,假,假,假,真,48/63,练习1:概念,说明:(2)重言式的主合取范式不含任何极大项，为1.(3)矛盾式的主合析范式不含任何极小项，为0.(4),不是完备集，如矛盾式不能写成,中的公式.(5),是完备集.,49/63,练习2:判断公式类型,解 用等值演算法求主范式(pq)(qp)(pq)(qp)(pq)(qp)(pq)(pq)(pq)(pq)m2 m1 m3 m0 m0 m1 m2 m3 主析取范式 1 主合取范式,2.判断下列公式的类型:(1)(pq)(qp),重言式,50/63,练习题2(续),解 用等值演算法求公式的主范式(pq)q(pq)q pqq 0 主析取范式 M0 M1 M2 M3 主合取范式,(2)(pq)q,矛盾式,51/63,解 用等值演算法求公式的主范式(pq)p(pq)p p(pq)(pq)m0 m1 主析取范式 M2 M3 主合取范式,(3)(pq)p,练习2(续),非重言式的可满足式,52/63,练习3：求公式的主范式,3已知命题公式A中含3个命题变项p,q,r，并知道它的成真赋值为001,010,111,求A的主析取范式和主合取范式，及A对应的真值函数.解,A的主析取范式为m1 m2 m7,A的主合取范式为M0 M3 M4 M5 M6,53/63,练习4：联结词完备集,4将A=(pq)r改写成下述各联结词集中的公式:(1),(2),(3),(4),(5)(6),解(1)(pq)r(pq)r(2)(pq)r(pq)r(3)(pq)r(pq)r(pq)r),54/63,练习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)说明：答案不惟一,55/63,练习5：应用题,5.某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习.选派必须满足以下条件：(1)若赵去，钱也去.(2)李、周两人中至少有一人去(3)钱、孙两人中去且仅去一人.(4)孙、李两人同去或同不去.(5)若周去，则赵、钱也去.用等值演算法分析该公司如何选派他们出国？,56/63,练习5解答,解此类问题的步骤：1.设简单命题并符号化2.用复合命题描述各条件3.写出由复合命题组成的合取式4.将合取式成析取式（最好是主析取范式）5.求成真赋值,并做出解释和结论,57/63,练习5解答,解1.设简单命题并符号化设 p:派赵去，q:派钱去，r:派孙去，s:派李去，u:派周去2.写出复合命题(1)若赵去，钱也去 pq(2)李、周两人中至少有一人去 su(3)钱、孙两人中去且仅去一人(qr)(qr)(4)孙、李两人同去或同不去(rs)(rs)(5)若周去，则赵、钱也去 u(pq),58/63,3.设(1)(5)构成的合取式为A A=(pq)(su)(qr)(qr)(rs)(rs)(u(pq)4.化成析取式 A(pqrsu)(pqrsu)结论：由上述析取式可知，A的成真赋值为00110与11001，派孙、李去（赵、钱、周不去）派赵、钱、周去（孙、李不去）,练习5解答,59/63,练习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),60/63,练习6:消解法,6.构造公式A=(pq)(qr)(pq)r的否证,从而证明它是矛盾式.解 消解序列:pq A的简单析取式 pq A的简单析取式 q,消解 qr A的简单析取式 r A的简单析取式 q,消解,消解这是A的一个否证,从而证明A是矛盾式.,61/63,练习7:消解法,7.用消解法判断下述公式是否是可满足的:(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”,计算结束.,62/63,总 结,主要内容等值式与等值演算基本等值式（16组，24个公式）主析取范式与主合取范式联结词完备集消解法基本要求,深刻理解等值式的概念牢记基本等值式的名称及它们的内容熟练地应用基本等值式及置换规则进行等值演算,63/63,总 结,理解文字、简单析取式、简单合取式、析取范式、合取范式的概念深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系，并理解简单析取式与极小项的关系熟练掌握求主范式的方法（等值演算、真值表等）会用主范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值会将公式等值地化成指定联结词完备集中的公式会用命题逻辑的概念及运算解决简单的应用问题掌握消解规则及其性质会用消解算法判断公式的可满足性,