第二章命题逻辑等值演算.ppt

,漳州师范学院计算机科学与工程系,第二章命题逻辑等值演算,2020年6月11日12时42分,第二章命题逻辑等值演算,等值式析取范式与合取范式联结词完备集可满足性问题与消解法知识点：等值式、置换规则、等值演算、(主)析取范式、(主)合取范式、联结词完备集、其它联结词、可满足性问题、消解法教学要求：深刻理解和掌握命题逻辑中的基本概念教学重点：等值演算、(主)析取范式、(主)合取范式学时:4,2020年6月11日12时42分,2.1等值式,定义2.1设A,B是两个命题公式,若A,B构成的等价式AB为重言式,则称A与B是等值的,记为AB16组(24个)重要的等值式双重否定律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,2020年6月11日12时42分,2.1等值式,同一律A0A，A1A排中律AA1矛盾律AA0蕴涵等值式ABAB等价等值式(AB)(AB)(BA)假言易位ABBA等价否定等值式ABAB归谬论(AB)(AB)A代入实例：例如在蕴涵等值式中1.取A=p,B=q时，得到等值式pqpq2.取A=pq,B=p时，得到等值式(pq)p(pq)p,2020年6月11日12时42分,2.1等值式,判别两个公式是否等值的方法真值表法等值演算以一组基本的又是重要的重言式为基础进行公式之间的演算置换规则：设(A)是含公式A的命题公式(B)是用公式B置换了(A)中的A后得到的命题公式若BA,则(B)(A)代入规则：在一个重言式(矛盾式)中，将同一命题变项全部用同一个命题公式替换后，得到的公式仍是重言式(矛盾式),2020年6月11日12时42分,2.1等值式,例1用等值演算法验证等值式(pq)r(pr)(qr)证：(pr)(qr)(pr)(qr)(蕴涵等值式,替换规则)(pq)r(分配律)(pq)r(德摩根律)(pq)r(蕴涵等值式)例6用等值演算法判断公式的类型(1)(pq)pq(2)(p(pq)r(3)p(pq)p)q),2020年6月11日12时42分,2.2析取范式与合取范式,每种数字标准形都能提供很多信息，如代数式的因式分解可判断代数式的根情况。逻辑公式在等值演算下也有标准形-范式范式有两种析取范式合取范式文字:命题变项及其否定统称作文字。简单析取式:仅有有限个文字构成的析取式。简单合取式:仅有有限个文字构成的合取式。析取范式:由有限个简单合取式构成的析取式。合取范式:由有限个简单析取式构成的合取式。注意:一个文字既是简单析取式，又是简单合取式。一个公式的析取范式或合取范式不是唯一的。,p,p,pqr,pqr,(pq)(pr),(pq)(pr),2020年6月11日12时42分,2.2析取范式与合取范式,一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式一个合取范式是重言式当且仅当它的每个简单析取式都是重言式范式存在定理:任一命题公式都存在着与之等值的析取范式与合取范式求范式可使用如下步骤:1.消去联结词,2.否定号的消去（利用双重否定律）或内移（利用德摩根）3.利用分配律：利用对的分配律求析取范式利用对的分配律求合取范式,2020年6月11日12时42分,2.2析取范式与合取范式,极小项:在含有n个命题变项的简单合取式中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变项或它的否定式出现在从左算起的第i位上,称这样的简单合取式为极小项。极大项:在含有n个命题变项的简单析取式中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变项或它的否定式出现在从左算起的第i位上,称这样的简单析取式为极大项。主析取范式:设由n个命题变项构成的析取范式中所有的简单合取式都是极小项，则称该析取范式为主析取范式。主合取范式:设由n个命题变项构成的合取范式中所有的简单析取式都是极大项，则称该合取范式为主合取范式。,2020年6月11日12时42分,2.2析取范式与合取范式,p,q,r形成的极小项与极大项,设mi与Mi是命题变项p1,p2,pn形成的极小项和大项，则miMi，Mimi,2020年6月11日12时42分,2.2析取范式与合取范式,任何命题公式都存在与之等值的主析取范式和主合取范式并且是唯一的。注意：由公式的主析取范式求主合取范式反之，也可以由公式的主合取范式确定主析取范式矛盾式无成真赋值，因而矛盾式的主合取范式含2n（n为公式中命题变项个数）个极大项而重言式无成假赋值，因而主合取范式不含任何极大项重言式的主合取范式记为1。矛盾式的主析取范式为0可满足式的主析取范式中至少含有一个极小项,主合取范式中极大项的个数一定小于2n,2020年6月11日12时42分,2.2析取范式与合取范式,含n个命题变项的所有无穷多合式公式中，和它们等值的主析取范式（主合取范式）共有多少种不同的情况。n个命题变项可产生2n个极小项（极大项），因而共可产生种不同的主析取范式（主合取范式）真值表和主析取范式的关系(1)(2)m0m1m2m3m4m5m7(3)m1m3m4m5m7真值表和主合取范式的关系(1)(2)M6(3)M0M2M6,2020年6月11日12时42分,2.3联结词完备集,联结词完备集:设S是一个联结词集合，如果任何n(n1)元命题公式都可以由仅含S中的联结词构成的公式等价地表示,则称S是联结词完备集。S=,是联结词完备集以下联结词集都是完备集：(1)S1=,(2)S2=,(3)S3=,(4)S4=,(5)S5=,根据需要，人们还可构造形式上更为简单的联结词完备集。例如，在计算机硬件设计中，用与非门或者或非门来设计逻辑线路时，就需要构造新联结词完备集。,2020年6月11日12时42分,2.3联结词完备集,例2：某电路中有一个灯泡和三个开关A，B，C。已知在且仅在下述四种情况下灯亮：(1)C的扳键向上，A,B的扳键向下(2)A的扳键向上，B,C的扳键向下(3)B,C的扳键向上，A的扳键向下(4)A,B的扳键向上，C的扳键向设F为1表示灯亮，p,q,r分别表示A,B,C的扳键向上(a)用命题公式构造F(b)在联结词完备集,上构造F(c)在联结词完备集,上构造F解：F=(pqr)(pqr)(pqr)(pqr)(b)(c)留作课后练习,2020年6月11日12时42分,2.3联结词完备集,F=(pqr)(pqr)(pqr)(pqr),当且仅当p、q、r的输入为0,0,1或1,0,0或0,1,1或1,1,0时输出F为1,2020年6月11日12时42分,2.4可满足性问题与消解法,命题公式的可满足性问题是算法理论的核心问题之一解决方法:真值表法、主析取范式或主合取范式缺点:计算量大新方法:消解法命题公式的可满足性问题可以归结为合取范式的可满足性问题例1判断下列公式是否是可满足式p(pq)(pq)(qr)(qr),2020年6月11日12时42分,2.4可满足性问题与消解法,消解法永真式可以从合取范式中消去不含任何文字的简单析取式为空简单析取式,规定它是不可满足的含有空简单析取式的合取范式是不可满足的设l是一个文字,称作文字l的补定义2.9设C1,C2是两个简单析取式,C1含文字l,C2含文字lc.从C1中删去l,从C2中删去lc,然后再将所得到的结果析取成一个简单析取式,称这样得到的简单析取式为C1,C2的消解式或消解结果,记为Res(C1,C2)定理2.8C1C2Res(C1,C2)定理2.10(消解的完全性)如果合取范式S是不可满足的,则S有否证合取范式S是不可满足的当且仅当S有否证,2020年6月11日12时42分,2.4可满足性问题与消解法,消解算法举例p(pq)(pq)(qr)(qr)初始化:记S0=,S1=p,pq,