离散数学-命题逻辑等值演算.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 命题逻辑等值演算,2.1 等值式,2.2 析取范式与合取范式,2.3 联结词完备集,2.4 可满足性问题与消解法,重点,难点,第1页,2.1 等值式,定义2.1,设A、B是任意两个命题公式，若等价式,A,B,为重言式，则称A与B是,等值,，,记作：,A,B,自反性,，即对任意命题公式A，A,A,对称性,，即对任意命题公式A和B，,若A,B，则B,A,传递性,，即对任意命题公式A，B和C，,若A,B，B,C，则A,C,第2页,两点注意,“,”,与“,=,”,“A=B”表示,两公式一样,，,“A,B”表示两公式,真值一样,与,是两类完全不一样符号,是,联结词、运算符,，A,B是一个公式。,不是联结词，,而是两个公式之间,关系符,第3页,真值表判断等值,p,q,r,p,(q,r,）,(p,q),r,(pq),r,0,0,0,1,0,1,0,0,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,0,0,1,1,1,1,0,1,1,1,1,1,1,0,0,0,0,1,1,1,1,1,1,第4页,十六组主要等值式（模式）,1.双重否定律,A,A,2.幂等律,AA,A，AA,A,3.交换律,AB,BA，AB,BA,4.结合律,(AB)C,A(BC),(AB)C,A(BC),第5页,十六组主要等值式,5.分配律(提取公因式）,A(BC),(,A,B)(,A,C),A(BC),(,A,B)(,A,C),6.德摩根律,(AB),AB,(AB),AB,第6页,德摩根律,例子,“地大物博”否定,：,地不大,或,物不博,(AB),AB,“用人民币或港币支付”否定：,既,不能用人民币支付，,也,不能用港币支付,(AB),AB,第7页,十六组主要等值式,7.吸收律,A(AB),A，A(AB),A,8.零律,A1,1，A0,0,9.同一律,A0,A，A1,A,10.排中律,AA,1,11.矛盾律,AA,0,第8页,十六组主要等值式,12.,蕴涵等值式,AB,AB,13.等价等值式,A,B,(AB)(BA),14.假言易位,AB,BA,15.等价否定等值式,A,B,A,B,16.归谬论,(AB)(AB),A,第9页,蕴涵等值式例子,蕴涵等值式：,AB,AB,否定形式：并非（p,q),(pq),p q,例：,并非招手即停,招手且不停车,第10页,归谬论应用,归谬论,(AB)(AB),A,反证法,假如非p，则q,假如非p，则非q,所以，p,第11页,归谬论例子,亚理士多德：物体下落速度与物体重量成正比。,伽利略思想试验：,A快B慢，AB比A快；,A快B慢，AB比A慢。,第12页,归谬论例子,一个岛上有一个风俗，凡是外乡人都要作为祭品被杀掉。,但允许被杀人在临死前说一句话。,假如这句话是真，则死在真理之神面前。,假如这句话是假，则死在错误之神面前。,一个,哲学家,说了一句话，而免于一死。,第13页,等值演算与置换规则,由已知等值式推演出另外等值式过程称为,等值演算。,置换规则,设,（A）是一个含有公式A命题公式，,（B）是用公式B置换了,（A）中公式A后得到公式，,假如A,B，那么,（A）,（B）。,第14页,等值演算例子,【例2.1】用等值演算验证等值式,p（qr）,（pq）r,第15页,等值演算例子,【例2.2】,用等值演算法判断以下公式类型。,q(pq)p),(pp)(q,q)r),(pq)p,第16页,等值演算例子,解：q(,(pq)p,),q(,(pp)(qp),)(,分配律,),q(0(qp)(,矛盾律,),q,(qp),(,同一律,),q,(qp),(,德摩根律,),(qq)p (,结合律,),1p (,排中律,),1 (,零律,),由此可知，为,重言式,。,第17页,等值演算例子,解：(pp)(qq)r),1(qq)r)(排中律),1(0r)(矛盾律),10 (零律),0 (条件联结词定义),由此可知，为,矛盾式,。,(pq)p,(pq)p (蕴涵等值式),p (吸收律),由此可知，是,可满足式,。,第18页,练习,1.,用等值演算验证等值式,（1）(pq)r,(pr)(qr),（2）（(pq)（pq）,（p,q）,2.,判断公式类型,（1）（pq）p q,（2）（,（pq）,q）r,第19页,判断问题,【例2.6】,判断王教授是哪里人：,甲说王教授不是苏州人，是上海人,乙说王教授不是上海人，是苏州人,丙说不是上海人，也不是杭州人,王教授说三个人中一个说全对，一个说对了二分之一，另一个全不对。,解：,p：王教授是苏州人,q：王教授是上海人,r：王教授是杭州人,第20页,解题思绪,p q r,0 0 1,0 1 0,1 0 0,王教授话是正确，写出公式,A（p,q,r)，找出它成真赋值,依据实际情况，,只有,3,个赋值，,而不是,8,个,第21页,作业,习题二 3839页,题目：3，4,17，18,19，20,第22页,2.2 析取范式与合取范式,定义2.2,将命题变元及其否定统称为,文字（literal）,。,简单析取式,（基本和）：,仅由有限个文字组成析取式，也称为,子句（clause）,。,简单合取式,（基本积）：,仅由有限个文字组成合取式。,比如：,p、q既是一个文字简单析取式，又是一个文字简单合取式。,pq，p,r均是有两个文字简单析取式，即子句。,pqr，pq,q均是有三个文字简单合取式。,第23页,定理 2.1,(1)一个简单析取式是重言式，当且仅当它,同时含有一个命题变元及其否定,。,(2)一个简单合取式是矛盾式，当且仅当它,同时含有一个命题变元及其否定,。,比如，,p,q,p,是重言式,p,q q,是矛盾式,第24页,范式（normal form）定义,定义2.3,析取范式,由有限个简单合取式组成析取式，简称,DNF,（disjunctive normal form）。,合取范式,由有限个简单析取式组成合取式，简称,CNF,（conjunctive normal form）。,析取范式例子：,A=A1,A2,An,=(pqr),(,pq,q),p,第25页,范式存在定理,定理2.3,任一命题公式都,存在,着与之等值析取范式,任一命题公式都,存在,着与之等值合取范式,求范式步骤以下：,消去联结词“”和“,”,利用双重否定律消去否定联结词“”或利用德摩根律将否定联结词“”移到各命题变元前(内移)。,利用分配律，结合律将公式归约为合取范式和析取范式。,第26页,例题,【例2.7】,求(pq)p合取范式和析取范式。,(pq)p,(pq)p)(p(pq),(pq)p)(p(pq),(pq)p)(p(pq),(pp)(qp)(ppq),1(qp)(1q),1(qp)1,(qp),第27页,练习,求析取范式与合取范式：,(p,q)r,合取范式,（p,r)(qr)(pqr),析取范式,（pqr）（pr）（qr）,第28页,极小项与极大项,定义2.4,极小项,：在含有n个命题变元,简单合取式,中，若每个命题变元和它否定式不一样时出现，而二者之一必出现且仅出现一次，且第i个命题变元（或它否定式）出现在从左算起第i位上。,极大项：,简单析取式中满足如上条件。,第29页,极小（大）项,关键性质,定理：n个命题变元共有,2,n,个极小项（极大项）。,每个极小（大）项只有,一个成真（假）赋值,，且各极小项成真赋值,互不相同,。,极小项和它成真赋值组成了,一一对应,关系,。,p,q,p,q,p,q,p,q,p,q,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,1,0,0,1,1,1,0,0,0,第30页,极小项性质,可用成真赋值,为极小项进行编码,，并把编码作为m下标来表示该极小项，叫做该极小项名称。,极小项与其成真赋值对应关系为：,变元对应1，而变元否定对应0,。,极小项,成真赋值,名称,p,q,00,m,0,p,q,01,m,1,p,q,10,m,2,p,q,11,m,3,第31页,极小项性质,极小项,成真赋值,名称,p,q,r,000,m,0,p,q,r,001,m,1,p,q,r,010,m,2,p,q,r,011,m,3,p,q,r,100,m,4,p,q,r,101,m,5,p,q,r,110,m,6,p,q,r,111,m,7,第32页,极大项,成假赋值,名称,p,q,00,M,0,p,q,01,M,1,p,q,10,M,2,p,q,11,M,3,极大项,成假赋值,名称,p,q,r,000,M,0,p,q,r,001,M,1,p,q,r,010,M,2,p,q,r,011,M,3,p,q,r,100,M,4,p,q,r,101,M,5,p,q,r,110,M,6,p,q,r,111,M,7,极大项,第33页,练习,写出极小项公式：,m,4,m,6,m,7,当变元个数分别为3、4时。,写出极大项公式：,M,4,M,6,M,7,当变元个数分别为3、4时。,第34页,定理：极小项与极大项,定理2.4,m,i,M,i,m,i,M,i,第35页,定义：主范式,定义2.5,主析取范式,：析取范式中全部简单合取式都是极小项。,主合取范式,：合取范式中全部简单析取式都是极大项。,问题：,对于n个命题变元，,有多少个主析（合）取范式？,例：m,0,m,1,m,7,（n3）,M,0,M,2,M,6,（,n3）,第36页,主范式存在性与唯一性,定理2.5,任何命题公式都,存在,与之等值主析取范式和主合取范式，而且是,唯一,。,证实：,（1）存在性：等值演算,（2）,唯一性,：反证法,第37页,例题与练习,【例2.8】,求主析取范式与主合取范式：,(p,q)r,练习：,p,q,合取范式,（p,r)(qr)(pqr),析取范式,（pqr）（pr）（qr）,第38页,主范式与真值表,定理：,若公式A中含n个命题变元，A主析取范式含s（0s2,n,）个,极小项,，则A有s个,成真赋值,，它们是所含极小项编号二进制表示，其余2,n,s个赋值都是成假赋值。,反之也成立。,对主合取范式有相同结果（对应成假赋值）,第39页,从真值表求主范式,【例】用真值表法，求(pq)r主范式。,m,001,m,011,m,100,m,101,m,111,m,1,m,3,m,4,m,5,m,7,p,q,r,p,q,(,p,q,),r,0,0,0,1,0,0,0,1,1,1,0,1,0,1,0,0,1,1,1,1,1,0,0,0,1,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,第40页,“排斥或”公式,排斥或,p,q,排斥或,0,0,0,0,1,1,1,0,1,1,1,0,排斥或：,(pq)(p q),m1,m2,第41页,经过主范式判别公式类型,定理,A为,重言式,当且仅当A主析取范式含全部2,n,个极小项（主合取范式0个极大项）,A为,矛盾式,当且仅当A主析取范式不含任何极小项（主合取范式含全部极大项）,A为,可满足式,当且仅当A主析取范式最少含一个极小项。,第42页,主析取范式与主合取范式关系,定理：,同一公式主析取范式中极小项m下标和主合取范式中极大项M,下标是互补,。,换言之，对于任一公式，在它2,n,个赋值中，非0即1，所以其,主析取范式中极小项和其主合取范式中极大项个数之和恰为2,n,，且其下标不会相同,。,第43页,练习,由主析取范式，求主合取范式,（1）A,m,1,m,2,（两个变元）,（2）B,m,1,m,2,m,3,（三,个变元）,第44页,作业,习题二 3840页,题目：5，6,7，8,9，10,11，12,13，14,25，26,第45页,2.3 联结词完备集,定义2.6,n元真值函数F,：0,1,n,0,1,定理,每个真值函数，都一一对应一个真值表。每个真值函数，都存在许多与之等值命题公式。反之，每个命题公式对应唯一与之等值真值函数。,定义2.7,设S是联结词集合，假如任何n元真值函数都能够由仅含S中联结词组成公式表示，则称S是,联结词完备集,。,第46页,联结词完备集,定理2.6,S,，,联结词完备集。,推论,以下集合都是完备集,，,，,，,，,，,第47页,联结词完备集,定义2.8,与非联结词：pq,(pq),或非联结词：pq,(pq),定理2.7,，,是联结词完备集。,第48页,2.4 可满足性问题与消解法,命题公式,可满足性问题,（,SAT问题,，satisfiability problem）是算法理论关键问题之一。,真值表、主范式计算量大。,从算法复杂度上讲，SAT是第一个被证实为NP难问题。,第49页,SAT问题,很多问题能够转化为SAT问题,著名八皇后问题,鸽笼问题,图着色问题等,第50页,合取范式可满足性问题,S表示合取范式，C表示,简单析取式（子句）,，L表示文字,合取范式：,SC1,C2,C3,Cn,S是可满足当且仅当每个Ci都是可满足。,或者，,只要一个子句不可满足，则S不可满足,深入，只要一部分不满足，则整体不满足,第51页,简单析取式（子句）,C,i,L,1,L,2,L,3,L,k,一个简单析取式中同时出现文字L（如p）及它补Lc（如p），则它为永真式。,永真式能够从合取范式中除去，是多出,。,所以，,假设简单析取式中不一样时出现某个命题变项和它否定,。,第52页,空子句不可满足,C,i,L,1,L,2,L,3,L,k,文字越多，越轻易满足,文字越少，越难满足,空子句，记为，不可满足。（没有极小项，无成真赋值）。,所以，,含有空子句合取范式是不可满足。,如子句 p，在p1时被满足，,而子句,p,q，在p0时也能满足,（q0）。,第53页,经过“消解规则”产生“空子句”,定义,2.9,C,1,与C,2,是两个简单析取式,C,1,C,1,L,（,p,q r）,C,2,C,2,Lc,（,p,r s t）,消解式（消解规则）,Res（C,1,C,2,）,C,1,C,2,消解式：,Res（C1,C2）q r r s t,p,q,p,s t,Res(p,p)=,第54页,经过消解规则化简合取式,定理,2.8,C,1,C,2,Res（C,1,，C,2,）,即，C,1,C,2,可满足当且仅当,消解式Res（C,1,，C,2,）可满足,若 C,1,p,q,r,C,2,p,r,则,C,1,C,2,（,p,q r,）,（,p,r,）,Res（C1,C2）,p,q,第55页,消解序列是否证,定义2.10,设S是一个合取范式，C,1,，C,2,，C,n,是一个以下生成子句序列：,对每一个i（1in），C,i,是S中一个简单析取式；,或者C,i,是它之前某两个简单析取式C,j,，C,k,（1jki）消解结果，,则称此序列是由S导出,消解序列,。,当C,n,时，称此序列是S一个,否证,。,第56页,消解完全性,推论,假如合取范式S有否证，则S是不可满足。,定理2.10（消解完全性）,假如合取范式S是不可满足，则S有否证。,推论,合取范式S是不可满足当且仅当S有否证,。,第57页,消解算法,输入,：合式公式A,输出,：当A是可满足，回答“yes”；,不然回答“no”。,步骤以下：,求A合取范式S,S,1,为S全部子句集合，S,0,与S,2,为空集,第58页,利用消解规则,3.,对S,0,中每一个子句C,1,与S,1,中每一个子句C,2,假如C,1,、C,2,能够消解，则计算CRes（C,1,，C,2,）,假如C,则输出“no”，计算结束,不然，,假如S,0,与S,1,都不包含C,则将C加入,S,2,第59页,利用消解规则,4.,对S,1,中每一对子句C,1,与C,2,假如C,1,、C,2,能够消解，则计算CRes（C,1,，C,2,）,假如C,则输出“no”，计算结束,不然，,假如S,0,与S,1,都不包含C,则将C加入,S,2,第60页,5,.假如S,2,中没有任何元素则,输出“yes”，计算结束,不然把S,1,加入S,0,，令S,1,等于S,2,，清空S,2,，返回3。,第61页,【例2.14】经过消解法判断公式是否是可满足。,（1）,（,p,q,）,（,p,q）,（,q）,（2）p,（,p,q）,（,p,q,）,（,q,r,）,（,q,r）,第62页,（,p,q,）,（,p,q）,（,q）,S,0,，S,1,p,q,p,q，,q,=C,1,C,2,C,3,，,S,2,Res(,C,1,C,2,)=q,Res(,C,1,C,3,)=,p,Res(,C,2,C,3,)=,p,S,2,p,p,q,第63页,S,0,p,q,p,q，,q,=C,1,C,2,C,3,S,1,p,p,q,S,2,Res(,q,q,)=,则输出“no”，计算结束,第64页,p,（,p,q）,（,p,q,）,（,q,r,）,（,q,r）,S,0,，S,1,p,p,q,p,q，,q,r,q,r,=C,1,C,2,C,3,C,4,C,5,，,S,2,Res(,C,2,C,3,)=p 重复,Res(,C,3,C,4,)=p,r,Res(,C,3,C,5,)=,p,r,Res(,C,4,C,5,)=,q,S,2,p,r,p,r,q,第65页,S,0,p,p,q,p,q，,q,r,q,r,=C,1,C,2,C,3,C,4,C,5,，,S,1,p,r,p,r,q,，,S,2,p,q，,q消解得到p 重复,q,r,p,r消解得到p,q，重复,q,r,p,r消解得到p,q，重复,p,r,p,r,消解得到p 重复,S,2,输出“yes”，计算结束,第66页,作业,习题二 3840页,题目：5，6,7，8,9，10,11，12,13，14,25，26,第67页,