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

《离散数学第二章 命题逻辑等值演算ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学第二章 命题逻辑等值演算ppt课件.ppt（37页珍藏版）》请在三一办公上搜索。

1、第二章 命题逻辑等值演算,第二章 命题逻辑等值演算,2.1 等值式与等值演算等值式与基本等值式真值表法与等值演算法2.2 范式析取范式与合取范式主析取范式与主合取范式,等值式,等值式:若等价式AB是重言式,则称A与B等值,记作AB,并称AB是等值式说明:(1)是元语言符号,不要混同于和=(2)A与B等值当且仅当A与B在所有可能赋值下的真值都相同,即A与B有相同的真值表(3)n个命题变项的真值表共有 个,故每个命题公式都有无穷多个等值的命题公式(4)可能有哑元出现.在B中出现,但不在A中出现的命题变项称作A的哑元.同样,在A中出现,但不在B中出现的命题变项称作B的哑元.哑元的值不影响命题公式的真

2、值.,真值表法,例1 判断(pq)与 pq 是否等值解,结论:(pq)(pq),真值表法(续),例2 判断下述3个公式之间的等值关系:p(qr),(pq)r,(pq)r解,p(qr)与(pq)r等值,但与(pq)r不等值,基本等值式,双重否定律 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,基本等值式(续),零律 A11,A00 同一律 A0A,A1A排中律 AA1矛盾律 AA0蕴涵等值式 ABAB等价等值式 AB(

3、AB)(BA)假言易位 ABBA等价否定等值式 ABAB归谬论(AB)(AB)A,等值演算,等值演算:由已知的等值式推演出新的等值式的过程置换规则:若AB,则(B)(A)例3 证明 p(qr)(pq)r证 p(qr)p(qr)（蕴涵等值式）(pq)r（结合律）(pq)r（德摩根律）(pq)r（蕴涵等值式）,实例,等值演算不能直接证明两个公式不等值.证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假.例4 证明:p(qr)(pq)r方法一 真值表法（见例2）方法二 观察法.容易看出000使左边成真,使右边成假.方法三 先用等值演算化简公式,再观察.,实例,例5 用等值演算法判断下列

4、公式的类型(1)q(pq)解 q(pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0（矛盾律）0（零律）该式为矛盾式.,实例(续),(2)(pq)(qp)解(pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1该式为重言式.,实例(续),(3)(pq)(pq)r)解(pq)(pq)r)(p(qq)r（分配律）p1r（排中律）pr（同一律）非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.,总结:A为矛盾式当且仅当A0;A为重言式当且仅当A1说明:演算步骤不惟一,应尽量使演算短些,2.2 范式,2.2.1 析取范式与合取范式简

5、单析取式与简单合取式析取范式与合取范式2.2.2 主析取范式与主合取范式极小项与极大项主析取范式与主合取范式主范式的用途,简单析取式与简单合取式,文字（letters）:命题变项及其否定的统称简单析取式:有限个文字构成的析取式(也叫子句（clause）)如 p,q,pq,pqr,简单合取式:有限个文字构成的合取式(也叫子句（phrase）)如 p,q,pq,pqr,注意：一个文字既是简单析取式、又是简单合取式。定理2.1(1)一个简单析取式是重言式当且仅当它同时含某个命题变项和它的否定(2)一个简单合取式是矛盾式当且仅当它同时含某个命题变项和它的否定,析取范式与合取范式,析取范式(disjun

6、ctive normal form):由有限个简单合取式组成的析取式 A1A2Ar,其中A1,A2,Ar是简单合取式合取范式(conjunctive normal form):由有限个简单析取式组成的合取式 A1A2Ar,其中A1,A2,Ar是简单析取式范式:析取范式与合取范式的统称定理2.2(1)一个析取范式是矛盾式当且仅当它的每一个简单合取式都是矛盾式(2)一个合取范式是重言式当且仅当它的每一个简单析取式都是重言式,范式存在定理,定理2.3 任何命题公式都存在着与之等值的析取范式与合取范式.证 求公式A的范式的步骤：(1)消去A中的,ABAB AB(AB)(AB)(2)否定联结词的内移或消

7、去 A A(AB)AB(AB)AB,范式存在定理(续),(3)使用分配律 A(BC)(AB)(AC)求合取范式 A(BC)(AB)(AC)求析取范式例1 求(pq)r 的析取范式与合取范式解(pq)r(pq)r(pq)r 析取范式(pr)(qr)合取范式注意:公式的析取范式与合取范式不惟一.,极小项与极大项,极小项(极大项):在含有n个命题变项的简单合取式(简单析取式)中,若每个命题变项均以文字的形式出现且仅出现一次，而且第i(1in)个文字(按下标或字母顺序排列)出现在左起第i位上,称这样的简单合取式(简单析取式)为极小项(极大项)说明:(1)n个命题变项产生2n个极小项和2n个极大项(2)

8、2n个极小项(极大项)均互不等值(3)用mi表示第i个极小项,其中i是该极小项成真赋值的十进制表示.用Mi表示第i个极大项,其中i是该极大项成假赋值的十进制表示,mi(Mi)称为极小项(极大项)的名称.,极小项与极大项(续),定理2.4 设mi 与Mi是由同一组命题变项形成的极小项和极大项,则 mi Mi,Mi mi,主析取范式与主合取范式,主析取范式:由极小项构成的析取范式主合取范式:由极大项构成的合取范式例如，n=3,命题变项为p,q,r时，(pqr)(pqr)m1m3 是主析取范式(pqr)(pqr)M1M5 是主合取范式定理2.5 任何命题公式都存在着与之等值的主析取范式和主合取范式,

9、并且是惟一的.,求主析取范式的步骤,设公式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)将极小项按下标从小到大排列,求主合取范式的步骤,设公式A含命题变项p1,p2,pn(1)求A的合取范式A=B1B2 Bs,其中Bj是简单析取式 j=1,2,s(2)若某个Bj既不含pi,又不含pi,则将Bj展开成 Bj Bj(pipi)(B

10、jpi)(Bjpi)重复这个过程,直到所有简单析取式都是长度为n的极大项为止(3)消去重复出现的极大项,即用Mi代替MiMi(4)将极大项按下标从小到大排列,实例,例1(续)求(pq)r 的主析取范式与主合取范式解(1)(pq)r(pq)r pq(pq)1 同一律(pq)(rr)排中律(pqr)(pqr)分配律 m4m5r(pp)(qq)r 同一律,排中律(pqr)(pqr)(pqr)(pqr)m0 m2 m4 m6 分配律得(pq)r m0 m2 m4 m5 m6可记作(0,2,4,5,6),实例(续),(2)(pq)r(pr)(qr)pr p0r 同一律 p(qq)r 矛盾律(pqr)(p

11、qr)分配律 M1M3 qr(pp)qr 同一律,矛盾律(pqr)(pqr)分配律 M3M7得(pq)r M1M3M7可记作(1,3,7),主析取范式的用途,(1)求公式的成真赋值和成假赋值设公式A含n个命题变项,A的主析取范式有s个极小项,则A有s个成真赋值,它们是极小项下标的二进制表示,其余2n-s个赋值都是成假赋值 例如(pq)r m0 m2 m4 m5 m6 成真赋值:000,010,100,101,110;成假赋值:001,011,111,主析取范式的用途(续),(2)判断公式的类型 设A含n个命题变项，则 A为重言式当且仅当A的主析取范式含2n个极小项A为矛盾式当且仅当 A的主析取

12、范式不含任何极小项,记作0 A为可满足式当且仅当A的主析取范式中至少含一个极小项,实例,例2 用主析取范式判断公式的类型:(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 非重言式的可满足式,主析取范式的用途(续),(3)判断两个公式是否等值例3 用主析取范式判断下面2组公式是否等值:(1)p与(pq)(pq)解 p p(qq)(pq)(pq)m2m3(pq)(pq)(pq)(pq)(pq

13、)(pq)m2m3故 p(pq)(pq),实例(续),(2)(pq)r 与 p(qr)解(pq)r(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m1m3m5 m6m7 p(qr)(pq)(p r)(pqr)(pqr)(pqr)(pqr)m5 m6m7故(pq)r p(qr),实例,例4 某单位要从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)

14、(pq)(pq),实例(续),求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去,主合取范式,由主析取范式求主合取范式设,没有出现的极小项是,其中t=2n-s,于是,主合取范式(续),例6 求A=(pqr)(pqr)(pqr)的主合取范式解 A m1m3m7 M0M2M4M5M6矛盾式的主合取范式含全部2n个极大项重言式的主合取范式不

15、含任何极大项,记作1,基本要求,深刻理解等值式的概念牢记基本等值式的名称及它们的内容熟练地应用基本等值式及置换规则进行等值演算理解文字、简单析取式、简单合取式、析取范式、合取范式的概念深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系，并理解简单析取式与极小项的关系熟练掌握求主范式的方法（等值演算、真值表等）会用主范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值,练习题1:判断公式类型,1.判断下列公式的类型:(1)(pq)(qp),解 用等值演算法求主范式(pq)(qp)(pq)(qp)(pq)(qp)(pq)(pq)(pq)(pq)m2 m1 m3 m0 m0 m1 m2 m3 主析取范式 1 主合取范式,重言式,练习题1:判断公式类型（续）,(pq)q解 用等值演算法求公式的主范式(pq)q(pq)q pqq 0 主析取范式 M0 M1 M2 M3 主合取范式,矛盾式,解 用等值演算法求公式的主范式(pq)p(pq)p p(pq)(pq)m0 m1 主析取范式 M2 M3 主合取范式,(3)(pq)p,练习题1:判断公式类型（续）,非重言式的可满足式,