离散数学02省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,第2章 命题逻辑等值演算,聊城大学重点课程,离散数学,1/60,本章说明,本章主要内容,等值式与基本等值式,等值演算与置换规则,析取范式与合取范式、主析取范式与主合取范式,联结词完备集(不讲,),本章与后续各章关系,是第一章抽象与延伸,是后续各章现行准备,2/60,两公式什么时候代表了同一个命题呢？,抽象地看，它们真假取值完全相同时即代表了相同命题。,设公式,A,B,共同含有,n,个命题变项，可能对,A,或,B,有哑元，若,A,与,B,有相同真值表，则说明在2,n,个赋值每个赋值下，,A,与,B,真值都相同。于是等价式,A,B,应为重言式。,2.1 等值式,3/60,定义2.1,设,A,B,是两个命题公式，若,A,B,组成等价式,A,B,为重言式,，则称,A,与,B,是,等值,，记作,A,B。,说明,定义中,A,B,都是,元语言符号,。,A,或,B,中可能有哑元出现。,pq,(,pq)(,rr)r,为左边公式中哑元。,用真值表能够验证两个公式是否等值。,等值定义及说明,4/60,例2.1,判断下面两个公式是否等值(,pq),与,pq,解答,说明,在用真值表法判断,A,B,是否为重言式时，真值表最终一列能够省略,。,等值,例题,5/60,例题2.2,判断以下各组公式是否等值,(1)p(qr),与(,pq)r,(2)(,pq)r,与(,pq)r,解答,等值,不等值,例题,6/60,1.双重否定律,A,A,2.,幂等律,A,AA,A,AA,3.交换律,AB,BA，AB,BA,4.结合律(,AB)C,A(BC)(AB)C,A(BC),5.分配律,A(BC),(AB)(AC)（,对分配律）,A(BC),(AB)(AC)（,对分配律）,6.德,摩根律(,AB),AB(AB),AB,7.吸收律,A(AB),A，A(AB),A,基本等值式,7/60,基本等值式,8.,零律,A1,1,A0,0,9.,同一律,A0,A，A1,A10.,排中律,AA,1,11.,矛盾律,AA,0,12.蕴涵等值式,AB,AB,13.等价等值式,A,B,(AB)(BA),14.假言易位,AB,BA,15.等价否定等值式,A,B,A,B,16.,归谬论(,AB)(AB),A,8/60,一个逻辑等值式，假如只含有、,、0、1,那么同时,把,和交换把0和1交换,得到还是等值式。,对偶原理,9/60,各等值式都是用元语言符号书写，其中,A,B,C,能够代表任意公式，称这么等值式为,等值式模式,。,每个等值式模式都给出了无穷多个同类型详细等值式。比如，在蕴涵等值式,AB,AB,中，取,A=p，B=q,时，得等值式,pq,pq,取,A=pqr，Bpq,时，得等值式,(,pqr)(pq),(pqr)(pq),这些详细等值式都被称为原来等值式模式,代入实例,。,由已知等值式推演出另外一些等值式过程为,等值演算,。,置换规则,设,(A),是含公式,A,命题公式，,(B),是用公式,B,置换了,(A),中全部,A,后得到命题公式，若,B,A，,则,(B),(A)。,等值演算与置换规则,10/60,等值演算基础,等值关系性质：自反性：,A,A。,对称性：若,A,B,，,则,B,A。,传递性：若,A,B,且,BC，,则,A,C。,基本等值式,置换规则,等值演算应用,证实两个公式等值,判断公式类型,解判定问题,关于等值演算说明,11/60,证实两个公式等值(,pq)r,(,pr)(qr),(,pq,)r,(pq),r,（,蕴含等值式、置换规则）,(,pq),r（,蕴含等值式、置换规则）,(,pq),r,（,德摩根律、置换规则）,(,pr)(qr)（,分配律、置换规则）,说明,也能够从右边开始演算,因为每一步都用置换规则，故可不写出,熟练后，基本等值式也能够不写出,通常不用等值演算直接证实两个公式不等值,解答,等值演算应用举例,12/60,例2.3,用等值演算法验证等值式,(pq)r,(pr)(qr),(p,r)(q,r),(p,r,)(q,r,)(,蕴含等值式,),(,pq,)r(,分配律,),(pq)r,(,德摩根律,),(pq)r蕴含等值式,),解答,例题,13/60,例2.4,证实：,(pq)r,与,p(qr),不等值,方法一、,真值表法。,方法二、,观察法。,易知，,010,是,(pq)r,成假赋值，而,010,是,p(qr),成真赋值，所以原不等值式成立。,方法三、,经过等值演算化成轻易观察真值情况，再进行判断。,A=(p,q)r,(pq),r,（蕴涵等值式）,(pq),r,（蕴涵等值式）,(pq)r,（德摩根律）,B=p,(q,r),p,(,qr,),（蕴涵等值式）,pqr,（结合律）,000,，,010,是,A,成假赋值，而它们是,B,成真赋值。,解答,例题,14/60,例题2.5,用等值演算判断以下公式类型：,（,1,）,(pq)pq,（,2,）,(p(pq)r,（,3,）,p(pq)p)q),例题,15/60,(1)(p,q)pq,(pq)p,q（,蕴涵等值式）,(,pq)p),q（,蕴涵等值式）,(,(,pq),p)q（,德摩根律）,(,pq),p,)q（,德摩根律）,(,pp,)(qp)q（,分配律）,(,1,(,q,p),q,（,排中律）,(,qq,)p（,同一律）,1,p（,排中律）,1（零律）,例2.5 解答,16/60,例2.5 解答,(2)(p,(pq)r,(ppq)r,(,pp,q)r,0,r,0,(3),p(pq)p),q),p(pq),p,)q),p(,(pp),(qp)q),p(,(,0,(qp)q),p(,q,p,q,),p1 p,17/60,在某次研讨会中间休息时间，3名与会者依据王教授口音对他是哪个省市人进行了判断：,甲说王教授不是苏州人，是上海人。,乙说王教授不是上海人，是苏州人。,丙说王教授既不是上海人，也不是杭州人。,听完以上3人判断后，王教授笑着说，他们3人中有一人说全对，有一人说对了二分之一，另一人说全不对。试用逻辑演算法分析王教授到底是哪里人？,2.6 应用题,18/60,设命题,p：,王教授是苏州人。,q：,王教授是上海人。,r：,王教授是杭州人。,p,q,r,中必有一个真命题，两个假命题，要经过逻辑演算将真命题找出来。,设甲判断为,A1,=pq,乙判断为,A,2,=pq,丙判断为,A,3,=qr,例2.6 解答,19/60,甲判断全对,B,1,=A,1,=pq,甲判断对二分之一,B,2,=(pq)(pq),甲判断全错,B,3,=pq,乙判断全对,C,1,=A,2,=pq,乙判断对二分之一,C,2,=(pq)(pq),乙判断全错,C,3,=pq,丙判断全对,D,1,=A,3,=qr,丙判断对二分之一,D,2,=(qr)(qr),丙判断全错,D,3,=qr,例2.6 解答,20/60,由王教授所说,E=(B,1,C,2,D,3,)(B,1,C,3,D,2,)(B,2,C,1,D,3,),(B,2,C,3,D,1,)(B,2,C,1,D,2,)(B,3,C,2,D,1,),为真命题。,经过等值演算后,可得,E,(pqr)(pqr),由题设，王教授不能既是上海人，又是杭州人，因而,p,r,中必有一个假命题，即,pqr,0,，于是,E,pqr,为真命题，因而必有,p,r,为假命题，,q,为真命题，即王教授是上海人。甲说全对，丙说对了二分之一，而乙全说错了。,例2.6 解答,21/60,王教授只可能是其中一个城市人或者三个城市都不是。,所以，丙最少说对了二分之一。,所以，可得甲或乙必有一人全错了。,又因为，若甲全错了，则有,pq，,所以乙全对。,同理，乙全错则甲全对。,所以丙必是一对一错。,依据上述推理，可对公式,E,进行简化，方便等值演算。,(怎样简化，请同学们课后思索,),例2.6深入思索,22/60,定义2.2,命题变项及其否定统称作,文字（,letters,）,。仅由有限个文字组成析取式称作,简单析取式,。仅由有限个文字组成合取式称作,简单合取式,。,简单析取式举例：,p,qpp，pq,pqr,pqr,简单合取式举例：,p,q,pp，pqpqr,ppq,说明,一个文字既是简单析取式，又是简单合取式。,2.2 析取范式和合取范式,23/60,为讨论方便，有时用,A,1,A,2,A,s,表示,s,个简单析取式或,s,个简单合取式。,设,A,i,是含,n,个文字简单析取式，若,A,i,中既含某个命题变项,pj,，,又含它否定式,p,j,，,即,p,j,p,j,，则,A,i,为重言式。,反之，若,A,i,为重言式，则它必同时含某个命题变项和它否定式，不然，若将,A,i,中不带否定符号命题变项都取0值，带否定号命题变项都取1值，此赋值为,A,i,成假赋值，这与,A,i,是重言式相矛盾。,类似讨论可知，若,A,i,是含,n,个命题变项简单合取式，且,A,i,为矛盾式，则,A,i,中必同时含某个命题变项及它否定式，反之亦然。,2.2 析取范式和合取范式,24/60,定理2.1,(1)一个简单析取式是重言式当且仅当它同时含有某个命题变项及它否定式。,(2)一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及它否定式。,定义2.3,(1)由有限个简单合取式组成析取式称为,析取范式（,disjunctive normal form,）,。,(2)由有限个简单析取式组成合取式称为,合取范式（,conjunctive normal form,）,。,(3)析取范式与合取范式统称为,范式,。,2.2 析取范式和合取范式,25/60,设,A,i,(i=1,2,s),为简单合取式，则,A=A,1,A,2,A,s,为析取范式。比如，,A,1,=pq，A,2,=qr，A,3,=p，,则由,A,1,A,2,A,3,结构析取范式为,A=A,1,A,2,A,3,=(pq)(qr)p,设,A,i,(i=1,2,s)为简单析取式，则,A=A,1,A,2,A,s,为合取范式。比如，取,A,1,=pqr，A,2,=pq，A,3,=r，,则由,A,1,A,2,A,3,组成合取范式为,A=A,1,A,2,A,3,=(pqr)(pq)r,说明,形如,pqr,公式既是一个简单合取式组成析取范式，又是由三个简单析取式组成合取范式。,形如,pqr,公式既是含三个简单合取式析取范式，又是含一个简单析取式合取范式。,2.2 析取范式和合取范式,26/60,定理2.2,(1)一个析取范式是矛盾式当且仅当它每个简单合取式都是矛盾式。,(2)一个合取范式是重言式当且仅当它每个简单析取式都是重言式。,说明,研究范式目标在于，将给定公式化成与之等值析取范式或合取范式，进而将公式化成与之等值主析取范式或主合取范式。,析取范式和合取范式性质,27/60,在范式中不会出现联结词与,，,不然可使用等值式消除,AB ABA,B (AB)(AB),在范式中不会出现形如,A,(AB),(AB),公式：,A A,(,AB)AB,(,AB)AB,在析取范式中不会出现形如,A(BC),公式：,A(BC)(AB)(AC),在合取范式中不出现形,A(BC),公式：,A(BC)(AB)(AC),定理2.3,任一命题公式都存在着与之等值析取范式与合取范式。,范式存在讨论,28/60,(1,),消去联结词、,(,若存在),。,AB ABA,B (AB)(AB),(2)否定号消去(利用双重否定律)或内移(利用德摩根律)。,A A,(,AB)AB,(,AB)AB,(3)利用分配律：利用对分配律求析取范式，对分配律求合取范式。,A(BC)(AB)(AC)A(BC)(AB)(AC),给定公式范式步骤,29/60,例题2.7,求下面公式析取范式与合取范式：,(,pq),r,(1),求合取范式,(,p,q),r,(pq),r （,消去）,(,pq),r)(r,(pq)（,消去,）,(,(,pq)r)(rpq)（,消去）,(,pq),r,)(pqr)（,否定号内移）,(,pr)(qr)(pqr)（,对分配律）,解答,例题,30/60,例题,(2),求析取范式,(,pq),r,(,(,pq),r),(p,q,r),(,pqp)(pqq)(pqr)(rp)(rq)(rr),(,pqr)(pr)(qr),说明,由此例可知,，,命题公式析取范式不唯一。,一样,，,合取范式也是不唯一。,31/60,定义2.4,在含有,n,个命题变项简单合取式（简单析取式）中，若每个命题变项和它否定式不一样时出现，而二者之一必出现且仅出现一次，且第,i,个命题变项或它否定式出现在从左算起第,i,位上（若命题变项无角标，就按字典次序排列），称这么简单合取式（简单析取式）为,极小项,（,极大项,）,。,n,个命题变项共可产生2,n,个不一样极小项。其中每个极小项都有且仅有一个成真赋值。若成真赋值所对应二进制数转换为十进制数,i，,就将所对应极小项记作,m,i,。,类似地，,n,个命题变项共可产生2,n,个极大项，每个极大项只有一个成假赋值，将其对应十进制数,i,做极大项角标，记作,M,i,。,范式规范化形式,32/60,表2.3 p,q形成极小项与极大项,33/60,表2.4 p,q,r形成极小项与极大项,34/60,范式规范化形式,定理2.4,设,m,i,与,M,i,是命题变项,p,1,p,2,p,n,形成极小项和极大项，则,m,i,M,i,，M,i,m,i,定义2.5,设由,n,个命题变项组成析取范式（合取范式）中全部简单合取式（简单析取式）都是极小项（极大项），则称该析取范式（合取范式）,为主析取范式,（,主合取范式,）,。,定理2.5,任何命题公式都存在着与之等值主析取范式和主合取范式，而且是唯一。,35/60,定理2.5证实,(只证主析取范式存在和唯一性),(1)证实存在性。,设,A,是任一含,n,个命题变项公式。,由定理2.3可知，存在与,A,等值析取范式,A,，,即,A,A,，,若,A,某个简单合取式,A,i,中既不含命题变项,p,j,，,也不含它否定式,p,j,，,则将,A,i,展成以下形式：,A,i,A,i,1,A,i,(p,j,p,j,),(A,i,p,j,)(A,j,p,j,),继续这个过程，直到全部简单合取式都含任意命题变项或它否定式。,若在演算过程中出现重复命题变项以及极小项和矛盾式时，都应“消去”：如用,p,代替,pp，m,i,代替,m,i,m,i,，0,代替矛盾式等。最终就将,A,化成与之等值主析取范式,A。,36/60,定理2.5,(2)证实唯一性。,假设某一命题公式,A,存在两个与之等值主析取范式,B,和,C，,即,A,B,且,A,C，,则,B,C。,因为,B,和,C,是不一样主析取范式，不妨设极小项,m,i,只出现在,B,中而不出现在,C,中。,于是，角标,i,二进制表示为,B,成真赋值，而为,C,成假赋值。这与,B,C,矛盾，因而,B,与,C,必相同。,37/60,求公式A主析取范式方法与步骤,方法一、等值演算法,(1)化归为析取范式。,(2)除去析取范式中全部永假析取项。,(3)将析取式中重复出现合取项和相同变元合并。,(4)对合取项补入没有出现命题变元，即添加如(,pp),式，然后应用分配律展开公式。,方法二、真值表法,(1)写出,A,真值表。,(2)找出,A,成真赋值。,(3)求出每个成真赋值对应极小项（用名称表示），按角标从小到大次序析取。,38/60,求公式A主合取范式方法与步骤,方法一、等值演算法,(1)化归为合取范式。,(2)除去合取范式中全部永真合取项。,(3)将合取式中重复出现析取项和相同变元合并。,(4)对析取项补入没有出现命题变元，即添加如(,pp),式，然后应用分配律展开公式。,方法二、真值表法,(1)写出,A,真值表。,(2)找出,A,成假赋值。,(3)求出每个成假赋值对应极大项（用名称表示），按角标从小到大次序析取。,39/60,例题,例2.9,求命题公式,pq,主析取范式和主合取范式。,(1)求主合取范式,pq,pq,M,2,(2)求析取范式,pq,pq,（p（,qq,）（(,pp,)q）,(,pq)(pq)(pq)(pq),(pq)(pq)(pq),m,0,m,1,m,3,解答,p,q,p,q,0,0,1,0,1,1,1,0,0,1,1,1,40/60,例2.8 求例2.7中公式主析取范式和主合取范式。,(1)求主析取范式,(,pq),r,(,pqr)(pr)(qr),pqr,m,4,pr,p（qq）r,(,pqr)(pqr),m,1,m,3,qr,(pp)qr,(,pqr)(pqr),m,3,m,7,(,pq),r,m,1,m,3,m,4,m,7,41/60,例2.8 求例2.7中公式主析取范式和主合取范式。,(2)求主合取范式,(,pq),r,(pr)(qr)(pqr),pqr,M,5,pr,p(qq)r,(,pqr)(pqr),M,0,M,2,qr,(pp)qr,(,pqr)(pqr),M,2,M,6,(,pq),r,M,0,M,2,M,5,M,6,42/60,主析取范式用途,求公式成真赋值与成假赋值,判断公式类型,判断两个命题公式是否等值,应用主析取范式分析和处理实际问题,43/60,求公式成真赋值与成假赋值,若公式,A,中含,n,个命题变项，,A,主析取范式含,s(0s2,n,),个极小项，则,A,有,s,个成真赋值，它们是所含极小项角标二进制表示，其余2,n,-s,个赋值都是成假赋值。,在例2.8中，(,pq),r,m,1,m,3,m,4,m,7,各极小项均含三个文字，因而各极小项角标均为长为3二进制数，它们分别是001，011，100，111，这四个赋值为该公式成真赋值,其余为成假赋值。,在例2.9中，,pq,m,0,m,1,m,3,，,这三个极小项均含两个文字，它们角标二进制表示00，01，11为该公式成真赋值，10是它成假赋值。,44/60,判断公式类型,设公式,A,中含,n,个命题变项，轻易看出：,A,为,重言式,当且仅当,A,主析取范式含全部2,n,个极小项。,A,为,矛盾式,当且仅当,A,主析取范式不含任何极小项。此时，记,A,主析取范式为0。,A,为,可满足式,当且仅当,A,主析取范式最少含一个极小项。,45/60,判断公式类型,例2.10,用公式主析取范式判断公式类型：,(1)(,pq)q,(2),p(pq),(3)(,pq)r,解答,(1)(,pq)q,（pq）q,(pq)q,0,(2)p(pq),m,0,m,1,m,2,m,3,(3)(,pq)r,m,0,m,1,m,3,m,5m,7,矛盾式,重言式,可满足式,46/60,判断两个命题公式是否等值,设公式,A,B,共含有,n,个命题变项，按,n,个命题变项求出,A,与,B,主析取范式,A,与,B。,若,AB,则,A,B；,不然，,A,与,B,不等值。,例2.11,判断下面两组公式是否等值：,(1),p,与(,pq)(pq),(2)(,pq)r,与(,q)r,(1),p,p(qq),(pq)(pq),m,2,m,3,(,pq)(pq),m,2,m,3,两公式等值。,(2),(,pq)r,m,1,m,3,m,4,m,5,m,7,(,q)r,m,0,m,1,m,2,m,3,m,4,m,5,m,7,两公式不等值。,解答,47/60,应用主析取范式分析和处理实际问题,例2.12,某科研所要从3名科研骨干,A,B,C,中挑选12名出国进修。因为工作原因，选派时要满足以下条件：,(1)若,A,去，则,C,同去。(2)若,B,去，则,C,不能去。(3)若,C,不去，则,A,或,B,能够去。问应怎样选派他们去？,分析：,(1)将简单命题符号化,(2)写出各复合命题,(3)写出由(2)中复合命题组成合取式（前提）,(4)将(3)中公式化成析取式（最好是主析取范式）,(5)这么每个小项就是一个可能产生结果。去掉不符合题意小项，即得结论。,48/60,应用主析取范式分析和处理实际问题,设,p:,派,A,去，,q:,派,B,去，r:,派,C,去,由已知条件可得公式,(,pr)(qr)(r(pq),经过演算可得,(,pr)(qr)(r(pq),m,1,m,2,m,5,因为,m,1,=pqr,m,2,=pqr,m,5,=pqr,可知，选派方案有3种：,(,a)C,去，而,A,B,都不去。(,b)B,去，而,A,C,都不去。(,c)A,C,去，而,B,不去。,解答,49/60,由公式主析取范式求主合取范式,设公式,A,含,n,个命题变项。,A,主析取范式含,s(0s2,n,),个极小项，即,没有出现极小项设为,它们角标二进制表示为,A,成真赋值，因而,A,主析取范式为,50/60,例题,例2.13,由公式主析取范式，求主合取范式：,(1),A,m,1,m,2,(A,中含两个命题变项,p,q),(2)B,m,1,m,2,m,3,(B,中含两个命题变项,p,q,r),解答,(1),A,M,0,M,3,(2)B,M,0,M,4,M,5,M,6,M,7,51/60,重言式与矛盾式主合取范式,设,n,为公式中命题变项个数,矛盾式无成真赋值，因而矛盾式主合取范式含2,n,个极大项。,重言式无成假赋值，因而主合取范式不含任何极大项。,将重言式主合取范式记为1。,可满足式主合取范式中极大项个数一定小于2,n,。,52/60,真值表与范式关系,A,B,当且仅当,A,与,B,有相同真值表，又当且仅当,A,与,B,有相同主析取范式主合取范式）。,真值表与主析取范式（主合取范式）是描述命题公式标准形式两种不一样等价形式。,n,个命题变项共可产生2,n,个极小项（极大项）,能够产生,主析取范式（主合取范式）数目为：,53/60,本章主要内容,等值式与等值演算。,基本等值式，其中含：双重否定律、幂等律、交换律、结合律、分配律、德摩根律、吸收律、零律、同一律、排中律、矛盾律、蕴含等值式、等价等值式、假言易位、等价否定等值式、归谬论。,与主析取范式及主合取范式相关概念：简单合取式、简单析取式、析取范式、合取范式、极小项、极大项、主析取范式、主合取范式。,54/60,本章学习要求,深刻了解等值式概念。,切记24个基本等值式，这是等值演算基础；能熟练地应用它们进行等值演算。,了解简单析取式、简单合取式、析取范式、合取范式概念。,深刻了解极小项及极大项定义及它们名称，及名称下角标与成真赋值关系。,熟练掌握求公式主析取范式方法。,熟练掌握由公式主析取范式求公式主合取范式方法。,会用公式主析取范式（主合取范式）求公式成真赋值、成假赋值。,55/60,本章经典习题,用等值演算法证实重言式和矛盾式,用等值演算法证实等值式,求公式主析取范式和主合取范式,用主范式判断两个公式是否等值,求解实际问题,56/60,例题,求公式(,pq)(pr),主析取范式和主合取范式。,解答,p,q,r,(,pq)(pr),0,0,0,0,0,0,1,1,0,1,0,0,0,1,1,1,1,0,0,0,1,0,1,0,1,1,0,1,1,1,1,1,主析取范式为,(,p,qr)(,pqr)(pq,r),(,pqr),主合取范式为,(pqr)(p,qr)(,pqr),(,pq,r),57/60,例题,甲、乙、丙、丁四个人有且只有两个人参加围棋比赛。关于谁参加比赛，以下四个判断都是正确：(1)甲和乙只有一人参加比赛。(2)丙参加，丁必参加。(3)乙或丁至多参加一人。(4)丁不参加，甲也不会参加。请推断出哪两个人参加围棋比赛。,设,a：,甲参加了比赛。,b：,乙参加了比赛。,c：,丙参加了比赛。,d：,丁参加了比赛。,(1)(,a,b)(,ab),(2),cd,(3),(,bd)(4),d,a,解答,58/60,(,(,a,b)(,ab),)(,cd,)(,(bd),)(,d,a,),(,a,b,cd,)(,a,bd,)(,ab,c,d,),依据题意条件，有且仅有两人参赛，,故,abcd,为0,，,所以,(,abcd,)(,abd,),为1，,即甲和丁参加了比赛。,(,ab)(cd),(,ac)(bc)(ad)(bd),说明,59/60,本章作业,习题二,4、7、8、9、10、23、29、30,60/60,