资源描述
,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1.3 命题逻辑等值演算,等值式,基本等值式,等值演算,置换规则,1,等值式,定义 若等价式,A,B,是重言式，则称,A,与,B,等值，,记作,A,B,，并称,A,B,是等值式,说明：定义中，,A,B,均为元语言符号,A,或,B,中,可能有哑元出现.,例如，在 (,p,q,),(,p,q,),(,r,r,)中，,r,为左边,公式的哑元.,用真值表可验证两个公式是否等值,请验证：,p,(,q,r,),(,p,q,),r,p,(,q,r,) (,p,q,),r,2,基本等值式,双重否定律,:,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,),3,基本等值式(续),德,摩根律,:,(,A,B,),A,B,(,A,B,),A,B,吸收律,:,A,(,A,B,),A,A,(,A,B,),A,零律,:,A,1,1,A,0,0,同一律,:,A,0,A,A,1,A,排中律,:,A,A,1,矛盾律,:,A,A,0,4,基本等值式(续),蕴涵等值式,:,A,B,A,B,等价等值式,:,A,B,(,A,B,),(,B,A,),假言易位,:,A,B,B,A,等价否定等值式,:,A,B,A,B,归谬论,: (,A,B,),(,A,B,),A,注意,:,A,B,C,代表任意的命题公式,牢记这些等值式是继续学习的基础,5,等值演算与置换规则,等值演算,:,由已知的等值式推演出新的等值式的过程,置换规则：若,A,B, 则,(,B,),(,A,),等值演算的基础：,(,1),等值关系的性质：自反、对称、传递,(,2),基本的等值式,(,3),置换规则,6,应用举例,证明两个公式等值,例,1,证明,p,(,q,r,),(,p,q,),r,证,p,(,q,r,),p,(,q,r,),（蕴涵等值式，置换规则）,(,p,q,),r,（结合律，置换规则）,(,p,q,),r,（德摩根律，置换规则）,(,p,q,),r,（蕴涵等值式，置换规则）,说明:也可以从右边开始演算（请做一遍）,因为每一步都用置换规则，故可不写出,熟练后，基本等值式也可以不写出,7,应用举例,证明两个公式不等值,例2 证明:,p,(,q,r,) (,p,q,),r,用等值演算不能直接证明两个公式不等值,证明两,个公式不等值的基本思想是找到一个赋值使一个成,真,另一个成假.,方法一 真值表法（自己证）,方法二 观察赋值法. 容易看出000, 010等是左边的,成真赋值，是右边的成假赋值.,方法三 用等值演算先化简两个公式，再观察.,8,应用举例,判断公式类型,例3,用等值演算法判断下列公式的类型,(1),q,(,p,q,),解,q,(,p,q,),q,(,p,q,),（蕴涵等值式）,q,(,p,q,),（德摩根律）,p,(,q,q,),（交换律，结合律）,p,0,（矛盾律）,0,（零律）,由最后一步可知，该式为矛盾式,.,9,例3 (续),(,2) (,p,q,),(,q,p,),解,(,p,q,),(,q,p,),(,p,q,),(,q,p,),（蕴涵等值式）,(,p,q,),(,p,q,),（交换律）,1,由最后一步可知，该式为重言式,.,问：最后一步为什么等值于,1,？,10,例3 (续),(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,1.4,联结词全功能集,复合联结词,排斥或,与非式,或非式,真值函数,联结词全功能集,12,复合联结词,排斥或,:,p,q,(,p,q,),(,p,q,),与非式,:,p,q,(,p,q,),或非式,:,p,q,(,p,q,),13,真值函數,问题：含,n,个命题变项的所有公式共产生多少个互,不相同的真值表？,答案为 个，为什么？,定义,称定义域为,000, 001, , 111,，值域,为,0,1,的函数是,n,元真值函数，定义域中的元素是,长为,n,的,0,1,串,.,常用,F,:0,1,n,0,1,表示,F,是,n,元真值,函数,.,共有 个,n,元真值函数,.,例如,F,:0,1,2,0,1,，且,F,(00)=,F,(01)=,F,(11)=0,，,F,(01)=1,，则,F,为一个确定的,2,元真值函数,.,14,命题公式与真值函数,对于任何一个含,n,个命题变项的命题公式,A,，都存在,惟一的一个,n,元真值函数,F,为,A,的真值表.,等值的公式对应的真值函数相同,.,下表给出所有,2,元真值函数对应的真值表,每一个含,2个命题变项的公式的真值表都可以在下表中找到,.,例如：,p,q,p,q, (,p,q,),(,(,p,q,),q,),等,都对应,表中的,15,2元真值函数对应的真值表,16,联结词的全功能集,定义,在一个联结词的集合中，如果一个联结词可,由集合中的其他联结词定义，则称此联结词为冗余,的联结词，否则称为独立的联结词,.,例如,在联结词集,中，由于,p,q,p,q,所以，,为冗余的联结词,;,类似地，,也是冗余的,联结词,.,又在,中，由于,p,q,(,p,q,),，,所以，,是冗余的联结词,.,类似地，,也是冗余的联,结词,.,17,联结词的全功能集(续),定义,设,S,是一个联结词集合，如果任何,n,(,n,1),元,真值函数都可以由仅含,S,中的联结词构成的公式表,示，则称,S,是联结词全功能集,.,说明：,若,S,是联结词全功能集，则任何命题公式都可用,S,中的联结词表示,.,若,S,1,S,2,是两个联结词集合，且,S,1,S,2,.,若,S,1,是全,功能集，则,S,2,也是全功能集,.,18,联结词的全功能集实例,(1),S,1,=,(2),S,2,=,(,3),S,3,=,(4),S,4,=,(5),S,5,=,(6) S,6,=,(7) S,8,=,而,等则不是联结词全功能集,.,19,
展开阅读全文