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

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

1、1/15/2023 7:06 PM,Discrete Math.,Chen Chen,1,离散数学Discrete Mathematics,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,2,第二章 命题逻辑等值演算Chapter TwoProposition Logic,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,3,2.1 等值式,2.2 析取范式与合取范式,2.3 联结词的完备集,等值式定义基本等值式等值演算（置换规则）,简单析取（合取）式极大（小）项（主）析（合）取范式,真值函数联结词完备集,2.4 可满足

2、性问题与消解法,第二章内容,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,4,设公式、中总共含有命题变项p1,p2,pn，但或并不全含有这些变项。如果某个变项未在公式中出现，则称该变项为的哑元。同样可定义的哑元。在讨论与是否有相同的真值表时，应将哑元考虑在内，即将、都看成含所有p1,p2,pn的命题公式，如果在所有2n个赋值下，与的真值相同，则为重言式。,哑元,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,5,定义2.1 设A,B 是两个命题公式，若A,B构成的等价式A B为重言式，则称A与B是等值的,记为AB。例

3、2.1 判断公式(pq)与 pq是否等值。解：用真值表法判断,如下：,注：A与B等值当且仅当A与B的真值表相同。因此，检验A与B是否等值，也可通过检查A与B的真值表是否相同来实现。,从表中可见，(pq)与pq等值。,定义,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,6,(1)p(qr)与(pq)r;(2)(pq)r 与(pq)r。解：所给的4个公式的真值表如下：,由真值表可见，p(qr)(pq)r,例2.2 判断下列两组公式是否等值：,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,7,当命题公式中变项较多时，用上

4、述方法判断两个公式是否等值计算量很大。为此，人们将一组经检验为正确的等值式作为等值式模式，通过公式间的等值演算来判断两公式是否等值。常用的等值式模式如下：1.双重否定律：A(A)2.幂等律：AAA,AAA 3.交换律:ABBA,ABBA 4.结合律:(AB)CA(BC),(AB)CA(BC)5.分配律：A(BC)(AB)(AC)(对的分配律)A(BC)(AB)(AC)(对的分配律)6.德摩根律：(AB)AB,(AB)AB 7.吸收律：A(AB)A,A(AB)A,等值式模式,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,8,8.零律：A11,A009.同一

5、律：A0A,A1A10.排中律：AA111.矛盾律：AA012.蕴含等值式：ABAB13.等价等值式:(AB)(AB)(BA)14.假言易位:AB BA15.等价否定等值式:ABAB16.归谬论:(AB)(AB)A,等值式模式（续）,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,9,利用这16组24个等值式可以推演出更多的等值式。由已知的等值式推演出另一些等值式的过程称为等值演算。在等值演算中,经常用到如下置换规则。置换规则:设(A)是含公式A的命题公式，(B)是用公式B置换了(A)中所有的A后所得的公式。若BA,则(B)(A)。,等值演算,1/15/2

6、023 7:06 PM,Discrete Math.,Chen Chen,10,例如，对公式(pq)r,如果用pq置换其中的pq,则得(pq)r.由于pqpq，故(pq)r(pq)r。类似地，可进行如下等值演算：,(pq)r(pq)r(pq)r(pq)r(pr)(qr),为简便起见,以后凡用到置换规则时,均不必标出。,(蕴含等值式，置换规则）(蕴含等值式，置换规则）(德摩根律，置换规则）(分配律，置换规则）,等值演算-例子,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,11,例2.3 用等值演算证明:(pq)r(pr)(qr),注：用等值演算证明等值式时

7、，既可以从左向右推演，也可以从右向左推演。,证：(pr)(qr),(pr)(qr)(pq)r(pq)r(pq)r,(蕴含等值式)(分配律)(德摩根律)(蕴含等值式),例2.3,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,12,证明：(pq)r p(qr）.,方法三:记A=(pq)r,B=p(qr)。先将A,B等值演算 化成易于观察真值的公式，再进行判断。A=(pq)r(pq)r(pq)r(pq)r B=p(qr)p(qr)pqr易见，000，010是A的成假赋值，而它们是B的成真赋值。,方法二：观察法。,证 方法一：真值表法。,故,(蕴含等值式)(蕴含

8、等值式)(德摩根律)(蕴含等值式)(结合律),例24,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,13,(1)（pq)pq;(2)(p(pq)r;(3)p(pq)p)q).解:(1)（pq)pq(pq)pq(pq)p)q(pq)p)q(pq)p)q(pp)(qp)q(1(qp)q(qp)q(qq)p 1p 1 故(pq)pq是重言式。,用等值演算判断下列公式的类型,(蕴含等值式)(蕴含等值式)(德摩根律)(德摩根律)(分配律)(排中律)(同一律）(交换律，结合律）（排中律）（零律）,例2.5,1/15/2023 7:06 PM,Discrete Mat

9、h.,Chen Chen,14,(2)(p(pq)r(ppq)r(pp q)r(0q)r 0r 0 故(p(pq)r是矛盾式。,(蕴含等值式，结合律）(德摩根律）(矛盾律）(零律)(零律）,例2.5（续）,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,15,p(pq)p)q)p(pq)p)q)(蕴含等值式)p(pp)(qp)q)(分配律)p(0(qp)q)(矛盾律)p(qp)q)(同一律)p(qp)q)(德摩根律，双重否定律)p(qq)p)(交换律，结合律)p(1p)（排中律）p1（零律）p（同一律）可见，（3）中公式不是重言式，因为00，01 都是成假

10、赋值；它也不是矛盾式，因为10，11 都是其成真赋值，故它是可满足式。,例2.5（续）,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,16,例2.6 在某次研讨会的休息时间，3名与会者根据王教授的口音对他是哪个省市的人进行了判断：甲说王教授不是苏州人，是上海人。乙说王教授不是上海人，是苏州人。丙说王教授不是上海人，也不是杭州人。听完3人的判断，王教授笑着说，他们3人中有一人说得全对，有一人说对了一半，有一人说得全不对。试用逻辑演算法分析王教授到底是哪里的人？解：设命题 p,q,r分别表示：王教授是苏州、上海、杭州人。则p,q,r中必有一个真命题，两个假命

11、题。要通过逻辑演算将真命题找出来。设：甲的判断为：A1=pq;乙的判断为：A2=pq;丙的判断为：A3=qr。,例2.6,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,17,那么甲的判断全对：B1=A1=pq 甲的判断对一半：B2=(pq)(pq)甲的判断全错：B3=pq 乙的判断全对：C1=A2=pq 乙的判断对一半：C2=(pq)(pq)乙的判断全错：C3=pq 丙的判断全对：D1=A3=qr 丙的判断对一半：D2=(qr)(qr)丙的判断全错：D3=qr 由王教授所说 E=(B1C2D3)(B1C3D2)(B2C1D3)(B2C3D1)(B3C1D

12、2)(B3C2D1)为真命题.,例2.6（续）,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,18,B1C2D3=(pq)(pq)(pq)(qr)(pqqr)(pqpr)0B1C3D2=(pq)(pq)(qr)(qr)(pqr)(pqqr)pqrB2C1D3=(pq)(pq)(pq)(qr)(pppqqr)(pqqr)0类似可得 B2C3D10,B3C1D2pqr,B3C2D10于是，由同一律可知 E(pqr)(pqr)但因为王教授不能既是苏州人，又是杭州人，因而p,r必有一个为假命题，即pqr0。于是 Epqr 为真命题，因而必有p,r为假命题，q为真

13、命题，即王教授为上海人，甲说得全对，丙说对了一半，而乙全说错啦。,例2.6（续）,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,19,定义2.2 命题变项及其否定统称作文字。仅由有限个文字构成的析取式称作简单析取式；仅由有限个文字构成的合取式称作简单合取式。,2.2 析取范式与合取范式,例如：p;p;qq;pq;pqr都是简单析取式.p;p;qq;pqr;ppr都是简单合取式。注：单个文字既是简单析取式又是简单合取式。,定理2.1(1)一个简单析取式是重言式当且仅当它同时含有某个命题变项及它的否定式；(2)一个简单合取式是矛盾式当且仅当它同时含有某个命题

14、变项及其否定式。,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,20,例如：(pq)(qr)r是一个析取范式，而(pqr)(pq)r是一个合取范式。注：单个文字既是简单析取式又是简单合取式。因此形如pqr的公式既是由一个简单合取式构成的析取范式，又是由三个简单析取式构成的合取范式。类似地，形如pqr的公式既可看成析取范式也可看成合取范式。,定义2.3 由有限个简单合取式构成的析取式称为析取范式；由有限个简单析取式构成的合取式成为合取范式；析取范式与合取范式统称为范式。,定义,1/15/2023 7:06 PM,Discrete Math.,Chen Ch

15、en,21,析取范式的一般形式：AA1 A2 An,其中 Ai(i=1,n)是简单合取式；合取范式的一般形式：AA1 A2 An,其中 Ai(i=1,n)是简单析取式。定理2.2（1）一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式；（2）一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。,范式的一般形式,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,22,定理2.3（范式存在定理）任一命题公式都存在着与之等值的析取范式与合取范式。证明：首先由蕴含等值式和等价等值式可知：ABAB,AB(AB)(AB)。由双重否定律和德摩根律可知：AA,(

16、AB)AB,(AB)AB。利用分配律，可得:A(BC)(AB)(AC)，A(BC)(AB)(AC)。使用这些等值式，便可将任一公式化成与之等值的析取范式或合取范式。,范式存在定理,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,23,求给定公式的范式的步骤：(1)消去联结词和；(2)否定号的消去(双重否定)或内移(德摩根律)；(3)利用对的分配律求合取范式；利用对的分配律求析取范式。,求范式的步骤,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,24,解:(1)合取范式：(pq)r(pq)r(pq)r)(r(pq)(p

17、q)r)(r(pq)(pq)r)(pqr)(pr)(qr)(pqr)(2)析取范式(pq)r(pq)r)(pqr)(pqp)(pqq)(pqr)(rp)(rq)(rr)(pqr)(pr)(qr),(消去),(消去),(消去),(否定号内移,结合律,交换律),(对的分配律),(见上述第一至四步),(对的分配律),(矛盾律和同一律),例2.7,求公式(pq)r的析取范式与合取范式。,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,25,注：在演算过程中，利用交换律，可使每个简单析取式或简单合取式中命题变项都按字典序出现。上述求析取范式的过程中，第二步和第三步结

18、果都是析取范式。这说明命题公式的析取范式是不唯一的。同样，合取范式也是不唯一的。为了得到唯一的规范化形式的范式，需要定义主析取范式和主合取范式。为此，先引入如下极小项和极大项概念。,范式的注解,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,26,定义2.4 在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项和它的否定式恰好出现一个且仅出现一次，并且命题变项或其否定式按下标从小到大或按字典序排列)，则称该简单合取式(简单析取式)为极小项(极大项)。注：由于每个命题变项在极小项中以原形或否定式形式出现且仅出现一次，因而n个命题变项共可产生2n 个

19、不同的极小项。每个极小项仅有一个成真赋值，若一个极小项的成真赋值对应的二进制数转化为十进制数为i，则将该极小项记为mi。类似地，n个命题变项可产生2n 个不同的极大项。每个极大项只有一个成假赋值。若一个极大项的成假赋值对应的十进制数为i，则将该极大项记为Mi。,极大、小项定义,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,27,两个变项p、q形成的极小项与极大项,pq,pq,pq,pq,pq,pq,pq,pq,极大、小项真值表,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,28,三个变项p,q,r形成的极小项与极大

20、项,极大、小项真值表（续）,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,29,定理2.4 设mi 与Mi 是命题变项p1,p2,pn形成的极小项和极大项，则 mi Mi，Mi mi。证明：略，可从以上两表验证该定理。定义2.5 如果由n个命题变项构成的析取范式（合取范式）中所有的简单合取式(简单析取式)都是极小项（极大项),则称该析取式（合取式）为主析取范式（主合取范式）。定理2.5 任何命题公式都存在着与之等值的主析取范式和主合取范式，并且是唯一的。证明：见教材26页。,主范式定义,1/15/2023 7:06 PM,Discrete Math.,C

21、hen Chen,30,注：主析取范式和主合取范式的求法：(1)先通过等值推演将所给的命题公式化为析取范式（合取范式）；(2)若某个简单合取式（简单析取式）A中既不含变项pi,又不含变 项pi,则通过：AA1 A(pipi)(Api)(Api)或：AA0 A(pipi)(Api)(Api)补齐变项。(3)消去重复变项和矛盾式，如用p,mi,0 分别代替pp，mi mi 和矛盾式，等。,主范式求法,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,31,解:(1)主析取范式 由例 2.7 知，(pq)r(pqr)(pr)(qr)(pr)p(qq)r(pqr)(

22、pqr)m1m3(qr)(pp)qr(pqr)(pqr)m3m7（pq r)m4(pq)r m1m3m4m7,求公式(pq)r的主析(合)取范式。,例2.8,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,32,(2)主合取范式由例2.7 知，(pq)r(pr)(qr)(pqr)(pr)p(qq)r(pqr)(pqr)M0M2(qr)(pp)qr(pqr)(pqr)M2M6(pqr)M5(pq)r M0M2 M5M6,例2.8（续）,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,33,例 2.9 求pq 的主析取范式

23、和主合取范式解:(1)主合取范式 pq pq M2(2)主析取范式 pq(pq)(p(qq)(pp)q)(pq)(pq)(pq)(pq)(pq)(pq)(pq)m0m1m3,例2.9,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,34,主析取范式和主合取范式的用途（以主析取范式为例)。1.求公式的成真与成假赋值 对含有n个变项的命题公式A，若其主析取范式含s(0s2n)个极小项，则A有s个成真赋值，它们是极小项下标的二进制表示，其余2n s个赋值都是成假赋值。例如，在例2.8中，(pq)rm1m3m4m7,因各极小项含三个文字，故各极小项下标的长为3的二

24、进制数 001，011，100，111为该公式的成真赋值，而其余赋值000，010，101，110为成假赋值。,范式的用途1,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,35,2.判断公式的类型设公式A中含n个变项，则(1)A为重言式当且仅当A的主析取范式含全部2n 个极小项；(2)A为矛盾式当且仅当A的主析取范式不含任取极小项。(此时，记A的主析取范式为0)。(3)A为可满足式当且仅当A的主析取范式中至少含一个极小项。,范式的用途2,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,36,(1)(pq)q;(2)p

25、(pq);(3)(pq)r解：(1)(pq)q(pq)q pqq 0.(2)p(pq)ppq(p(qq)(p(qq)(pp)q)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)m0m1m2m3,利用公式的主析取范式判断公式的类型：,注：另一种推演：p(pq)ppq 1q 1 m0m1m2m3,该主析取范式含全部22 个极小项，故p(pq)是重言式。,故(pq)q 是矛盾式。,例2.10,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,37,(3)（pq)r(pq)r(pq)r(pq(rr)(pp)(qq)r)(pqr)(pq

26、r)(pqr)(pqr)(pqr)(pqr)m0 m1 m3 m5m7 故该公式是可满足式,但不是重言式。,例2.10（续）,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,38,3.判断两公式是否等值 设公式A,B共有n个变项。按n个变项求出A,B的主析取范式。若A与B有相同的主析取范式，则AB;否则 AB。例 2.11 判断下面两组公式是否等值。(1)p与(pq)(pq);(2)(pq)r 与(pq)r解:(1)pp(qq)(pq)(pq)m2m3 而(pq)(pq)m2m3，故 p(pq)(pq）(2)因(pq)rm1m3m4m5m7 而(pq)rm

27、0m1m2m3m4m5m7 故(pq)r(pq)r,范式的用途3,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,39,例2.12 某单位欲从三人A,B,C中挑选12人出国进修。由于工作需要选派时要满足以下条件(1)若A去，则C同去；(2)若B去，则C不能去；(3)若C不去，则A或B可以去。问应如何选派？解：设p:派A去；q：派B去；r:派C去。由条件得：(pr)(q r)(r(pq)经演算得其主析取范式为：m1m2m5 m1=pqr;m2=pqr;m5=pqr由此可知,有3种选派方案：(1)C去，A,B都不去；(2)B去，A,C都不去；(3)A,C同去，

28、B不去。,4.利用主析取范式和主合取式解决应用问题,范式的用途4,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,40,1主合取范式可由主析取范式直接得到。设公式A含有n个变项，A的主析取范式为,未在主析取范式中出现的极小项设为,事实上，因,则A的主合取范式为：,故,关于主合取范式的两点说明1,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,41,例2.13 由公式的主析取范式，求主合取范式：(1)Am1 m2,(A含两个变项p,q);(2)Bm1m2m3，(B含三个变项p,q,r)。解：(1)主析取范式中未出现的极小

29、项为：m0,m3,故A的主合取范式为：A M0M3。(2)主析取范式中未出现的极小项为m0,m4,m5,m6,m7，故A的主合取范式为：AM0M4M5M6M7。,2.重言式与矛盾式的主合取范式 重言式无成假赋值，因而其主合取范式不含任何极大项。重言式的主合取范式记为1。矛盾式无成真赋值，故其主合取范式含有所有2n 个极大项。,关于主合取范式的两点说明2,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,42,含n个变项的所有公式，共有22n种不同的主析取范式(主合取范式)。这是因为n个变项共可产生2n个极小项(极大项)，因而可产生22n种主析取范式(主合取范

30、式)(因每个极小项可以在主析取范式中出现或不出现)。AB当且仅当A与B有相同的真值表，又当且仅当A与B有相同的主析取范式(主合取范式)。可见，真值表与主析取范式(主合取范式)是描述命题公式标准形式的两种不同的等价形式。,本节结束语,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,43,定义2.6 称映射F:0,1n 0,1为n元真值函数。其中 0,1n 表示由0，1组成的长为 n 的字符串集合。注：1元真值函数有22=4个；2元真值函数有 222=16个；3元真值函数有223=256个。4个一元真值函数,2.3 联结词的完备集,1/15/2023 7:06

31、 PM,Discrete Math.,Chen Chen,44,真值函数,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,45,注：每个真值函数与唯一的主析取范式(主合取范式)）等值，而每个主析取范式(主合取范式)对应无穷多个与之等值的命题公式。因此每个真值函数对应无穷多个与之等值的命题公式。另一方面，由定理2.5，每个命题公式都有唯一一个真值函数与之等值。定义2.7 设S是一个联结词集合。如果任何n元(n1)）真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。定理 2.6 S=，是联结词完备集。证：因任何n元真值函数都与唯一一个主析取

32、范式等值，而主析取范式中仅含联结词,故结论成立。,联结词完备集,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,46,S1=,;S2=,;S3=,;S4=,;S5=,.证:(1)、(2)显然(3)因任何真值函数都可由只用完备集S=,中的联结词表示，而对任意公式A和B，AB(AB)(AB)。故任意真值函数都可用S3=,中的联结词的公式表示。因此S3=,是联结词完备集。(4)、(5)的证明留作练习。,推论：以下联结词集都是完备集：,推论,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,47,注：可以证明,不是联结词完备集，

33、其任何子集，如，,，,，,等也不是联结词完备集。设S1和S2是两个不同的联结词完备集。用S1中联结词构成的任何公式，必可等值转化成用S2中联结词构成的公式，反之亦然。因此，在某一特定的系统中，只需采用一种联结词完备集即可。但在不同的应用中，人们往往采用不同的联结词完备集。例如，在计算机硬件设计中，常用如下的“与非门”或者“或非门”来设计逻辑线路。,联结词完备集注解,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,48,定义 2.8.设p,q为两个命题。复合命题“p与q的否定式”(“p或q的否定式”)称为p,q的“与非式”(“或非式”），记作pq(pq)。符号称作与非联结词(称作或非联结词)。pq为真当且仅当p与q不同时为真，(pq为真当且仅当p与q同时为假)。定理2.7 和都是联结词完备集。证明：由定义，pq=(pq),pq=(pq)由于,是联结词完备集，故只需证明其中每个联结词都可以由表示即可。事实上，p(pp)pp;pq(pq)(pq)(pq)(pq);(利用前一式)pq(pq)(p q)pq(pp)(qq).,与非、或非式,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,49,2.4 可满足性问题与消解法,