单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,课件,*,2.2,命题逻辑等值演算,2.2.1 等值式与等值演算,等值式与基本等值式,真值表法与等值演算法,2.2.2 联结词完备集,真值函数,联结词完备集,与非联结词和或非联结词,1,课件,2.2 命题逻辑等值演算2.2.1 等值式与等值演算1课件,等值式,定义2.11,若等价式,A,B,是重言式,则称,A,与,B,等值,记作,A,B,并称,A,B,是,等值式,说明:(1),是,元语言符号,不要混同于,和=,(2),A,与,B,等值当且仅当,A,与,B,在所有可能赋值下的真值都相,同,即,A,与,B,有相同的真值表,(3),n,个命题变项的真值表共有 个,故每个命题公式都有,无穷多个等值的命题公式,(4)可能有哑元出现.在,B,中出现,但不在,A,中出现的命题变项称作,A,的,哑元,.同样,在,A,中出现,但不在,B,中出现的命题变项称作,B,的哑元.哑元的值不影响命题公式的真值.,2,课件,等值式定义2.11 若等价式AB是重言式,则称A与B等值,真值表法,例1,判断,(,p,q,),与,p,q,是否等值,解,结论:,(,p,q,),(,p,q,),p q,p,q,p,q,(,p,q,),p,q,(,p,q,),(,p,q,),0 0 1 1 0 1 1 1,0 1 1 0 1 0 0 1,1 0 0 1 1 0 0 1,1 1 0 0 1 0 0 1,3,课件,真值表法例1 判断(pq)与 pq 是否等值结,真值表法(续),例2,判断下述3个公式之间的等值关系:,p,(,q,r,),(,p,q,),r,(,p,q,),r,解,p q r,p,(,q,r,)(,p,q,),r,(,p,q,),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,p,(,q,r,),与,(,p,q,),r,等值,但与,(,p,q,),r,不等值,4,课件,真值表法(续)例2 判断下述3个公式之间的等值关系:p,基本等值式,双重否定律,A,A,幂等律,A,A,A,A,A,A,交换律,A,B,B,A,A,B,B,A,结合律,(,A,B,),C,A,(,B,C,),(,A,B,),C,A,(,B,C,),分配律,A,(,B,C,),(,A,B,),(,A,C,),A,(,B,C,),(,A,B,),(,A,C,),德摩根律,(,A,B,),A,B,(,A,B,),A,B,吸收律,A,(,A,B,),A,A,(,A,B,),A,5,课件,基本等值式双重否定律 AA5课件,基本等值式(续),零律,A,1,1,A,0,0,同一律,A,0,A,A,1,A,排中律,A,A,1,矛盾律,A,A,0,蕴涵等值式,A,B,A,B,等价等值式,A,B,(,A,B,),(,B,A,),假言易位,A,B,B,A,等价否定等值式,A,B,A,B,归谬论,(,A,B,),(,A,B,),A,6,课件,基本等值式(续)零律,等值演算,等值演算,:,由已知的等值式推演出新的等值式的过程,置换规则,:,若,A,B,则,(,B,),(,A,),例,3,证明,p,(,q,r,),(,p,q,),r,证,p,(,q,r,),p,(,q,r,),（,蕴涵等值式）,(,p,q,),r,（,结合律）,(,p,q,),r,（,德摩根律）,(,p,q,),r,（,蕴涵等值式）,7,课件,等值演算等值演算:由已知的等值式推演出新的等值式的过程7课,实例,等值演算不能直接证明两个公式不等值.证明两个公式不,等值的基本思想是找到一个赋值使一个成真,另一个成假.,例4,证明:,p,(,q,r,)(,p,q,),r,方法一 真值表法（见例2）,方法二 观察法.容易看出000使左边成真,使右边成假.,方法三 先用等值演算化简公式,再观察.,8,课件,实例等值演算不能直接证明两个公式不等值.证明两个公式不8课,实例,例,5,用等值演算法判断下列公式的类型,(1),q,(,p,q,),解,q,(,p,q,),q,(,p,q,),（,蕴涵等值式）,q,(,p,q,),（,德摩根律）,p,(,q,q,),（,交换律，结合律）,p,0,（,矛盾律）,0,（零律）,该式为矛盾式,.,9,课件,实例例5 用等值演算法判断下列公式的类型9课件,实例(续),(,2)(,p,q,),(,q,p,),解,(,p,q,),(,q,p,),(,p,q,),(,q,p,),（,蕴涵等值式）,(,p,q,),(,p,q,),（,交换律）,1,该式为重言式,.,10,课件,实例(续)(2)(pq)(qp)10课件,实例(续),(3)(,p,q,),(,p,q,),r,),解,(,p,q,),(,p,q,),r,),(,p,(,q,q,),r,（,分配律）,p,1,r,（,排中律）,p,r,（,同一律）,非重言式的可满足式.,如,101,是它的成真赋值,000,是它的,成假赋值,.,总结,:,A,为矛盾式当且仅当,A,0;,A,为重言式当且仅当,A,1,说明,:,演算步骤不惟一,应尽量使演算短些,11,课件,实例(续)(3)(pq)(pq)r)总结,真值函数,定义2.12,称,F,:0,1,n,0,1,为,n,元,真值函数,n,元真值函数共有 个,每一个命题公式对应于一个真值函数,每一个真值函数对应无穷多个命题公式,1元真值函数,p,0 0 0 1 1,1 0 1 0 1,12,课件,真值函数定义2.12 称F:0,1n0,1为n元真,2元真值函数,p q,0 0 0 0 0 0 0 0 0 0,0 1 0 0 0 0 1 1 1 1,1 0 0 0 1 1 0 0 1 1,1 1 0 1 0 1 0 1 0 1,p q,0 0 1 1 1 1 1 1 1 1,0 1 0 0 0 0 1 1 1 1,1 0 0 0 1 1 0 0 1 1,1 1 0 1 0 1 0 1 0 1,13,课件,2元真值函数 p q13课件,联结词完备集,定义,2.13,设,S,是一个联结词集合,如果任何,n,(,n,1),元真值,函数都可以由仅含,S,中的联结词构成的公式表示,则称,S,是,联结词完备集,定理2.1,下述联结词集合都是完备集:,(1),S,1,=,(2),S,2,=,(,3),S,3,=,(4),S,4,=,(5),S,5,=,(6)S,6,=,A,B,(,A,B,)(,B,A,),A,B,A,B,A,B,(,A,B,),(,A,B,),A,B,(,A,B,),A,B,(,A,),B,A,B,14,课件,联结词完备集定义2.13 设S是一个联结词集合,如果任何n,复合联结词,与非式,:,p,q,(,p,q,),称作,与非联结词,或非式,:,p,q,(,p,q,),称作,或非联结词,p,q,为真当且仅当,p,q,不同时为真,p,q,为真当且仅当,p,q,不同时为假,定理2.2,是联结词完备集,证,p,(,p,p,),p,p,p,q,(,p,q,)(,p,q,),(,p,q,),(,p,q,),得证,是联结词完备集.对于,可类似证明.,15,课件,复合联结词与非式:pq(pq),称作与非联结,2.3,范式,2.3.1 析取范式与合取范式,简单析取式与简单合取式,析取范式与合取范式,2.3.2 主析取范式与主合取范式,极小项与极大项,主析取范式与主合取范式,主范式的用途,16,课件,2.3 范式2.3.1 析取范式与合取范式16课件,简单析取式与简单合取式,文字,:命题变项及其否定的统称,简单析取式,:有限个文字构成的析取式,如,p,q,p,q,p,q,r,简单合取式,:有限个文字构成的合取式,如,p,q,p,q,p,q,r,定理2.3,(1)一个简单析取式是重言式当且仅当它同时含,某个命题变项和它的否定,(2)一个简单合取式是矛盾式当且仅当它同时含某个命题,变项和它的否定,17,课件,简单析取式与简单合取式文字:命题变项及其否定的统称17课件,析取范式与合取范式,析取范式,:由有限个简单合取式组成的析取式,A,1,A,2,A,r,其中,A,1,A,2,A,r,是,简单合取式,合取范式,:由有限个简单析取式组成的合取式,A,1,A,2,A,r,其中,A,1,A,2,A,r,是,简单析取式,范式,:析取范式与合取范式的统称,定理2.4,(1)一个析取范式是矛盾式当且仅当它的每一个,简单合取式都是矛盾式,(2)一个合取范式是重言式当且仅当它的每一个简单析取,式都是重言式,18,课件,析取范式与合取范式析取范式:由有限个简单合取式组成的析取式1,范式存在定理,定理,2.5,任何命题公式都存在着与之等值的析取范式与合,取范式.,证 求公,式,A,的范式的步骤：,(1)消去,A,中的,A,B,A,B,A,B,(,A,B,),(,A,B,),(2)否定联结词,的内移或消去,A,A,(,A,B,),A,B,(,A,B,),A,B,19,课件,范式存在定理定理2.5 任何命题公式都存在着与之等值的析取范,范式存在定理(续),(3),使用分配律,A,(,B,C,),(,A,B,),(,A,C,),求合取范式,A,(,B,C,),(,A,B,),(,A,C,),求析取范式,例1,求,(,p,q,),r,的析取范式与合取范式,解,(,p,q,),r,(,p,q,),r,(,p,q,),r,析取范式,(,p,r,),(,q,r,),合取范式,注意:公式的析取范式与合取范式不惟一.,20,课件,范式存在定理(续)(3)使用分配律20课件,极小项与极大项,定义,2.17,在含有,n,个命题变项的简单合取式(简单析取式),中,若每个命题变项均以文字的形式出现且仅出现一次，,而且第,i,(,1,i,n,),个文字(按下标或字母顺序排列)出现在左,起第,i,位上,称这样的简单合取式(简单析取式)为,极小项,(极大项),说明,:,(1),n,个命题变项产生,2,n,个极小项和,2,n,个极大项,(2)2,n,个极小项(极大项)均互不等值,(3),用,m,i,表示第,i,个极小项,其中,i,是该极小项成真赋值的十,进制表示,.,用,M,i,表示第,i,个极大项,其中,i,是该极大项成假赋,值的十进制表示,m,i,(,M,i,),称为极小项(极大项)的名称,.,21,课件,极小项与极大项定义2.17 在含有n个命题变项的简单合取式(,极小项与极大项(续),定理2.6,设,m,i,与,M,i,是由同一组命题变项形成的极小项和极,大项,则,m,i,M,i,M,i,m,i,极小项 极大项,公式 成真赋值 名称 公式 成假赋值 名称,p,q,0 0,m,0,p,q,0 0,M,0,p,q,0 1,m,1,p,q,0 1,M,1,p,q,1 0,m,2,p,q,1 0,M,2,p,q,1 1,m,3,p,q,1 1,M,3,p,q,形成的极小项与极大项,22,课件,极小项与极大项(续)定理2.6 设mi 与Mi是由同一组命题,主析取范式与主合取范式,主析取范式,:由极小项构成的析取范式,主合取范式,:由极大项构成的合取范式,例如，,n,=3,命题变项为,p,q,r,时，,(,p,q,r,),(,p,q,r,),m,1,m,3,是,主析取范式,(,p,q,r,),(,p,q,r,),M,1,M,5,是,主合取范式,定理,2.7,任何命题公式都存在着与之等值的主析取范式和,主合取范式,并且是惟一的.,23,课件,主析取范式与主合取范式主析取范式:由极小项构成的析取范式23,求主析取范式的步骤,设公式,A,含命题变项,p,1,p,2,p,n,(1)求,A,的析取范式,A,=B,1,B,2,B,s,其中,B,j,是简单合取,式,j,=1,2,s,(2)若某个,B,j,既不含,p,i,又不含,p,i,则将,B,j,展开成,B,j,B,j,(,p,i,p,i,)(,