离散数学-1-6 其它联接词

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第一章 命题逻辑,1-6 其它联结词,1,其它联结词,目前已经学习了、,、,五种联结词，但这些联结词不能很广泛地直接表达命题间的联系（如不可兼析取），为此我们再定义一些命题联结词。,2,一、,不可兼析取（异或）,定义1-6.1,设,P,和,Q,是两个命题，复合命题,P Q,称作,P,和,Q,的,不可兼析取（也叫异或）,。定义为：,P Q,为1当且仅当,P,和,Q,的真值不相同时。,联结词,“ ”,的定义如表1-6.1,表1-6.1,P,Q,0,0,0,0,1,1,1,0,1,1,1,0,P,Q,3,一、,不可兼析取（异或）,“ ”,也可以看成逻辑运算，它是二元逻辑运算。它在程序设中有广泛的引用,。,不可兼析取有下列的性质(,P、Q、R,为命题公式),：,P Q,P Q,(,交换律,),(,P Q,),R,P,(,Q R,) (,结合律,),P,(,Q R,),(,P,Q,) (,P,R,) (,合取对异或的分配律,),P Q,(,P,Q,),(,P,Q,),P Q,(,P,Q,),P P,0,，,0,P,P,，,1,P,P,定理1-6.1,设,P，Q，R,为命题公式，如果,P Q,R，,则,P R,Q，Q R,P，P Q R,为一矛盾式。,证明,P25,4,二、条件否定,定义1-6.2 P25,5,三、与非,定义1.6.3,设,P,和,Q,是两个命题公式，复合命题,PQ,称作,P,和,Q,的“与非”,。定义为：当且仅当,P,和,Q,真值都是真时，,PQ,才为假。联结词“”称为与非联结词。,联结词,“,”,的定义如表1-6.3,可以看出，,P,Q,（,P,Q）,表1-6.3,P,Q,P,Q,0,0,1,0,1,1,1,0,1,1,1,0,6,三、与非,“,”,也可以看成逻辑运算，它是二元逻辑运算。,联结词,“,”,还有以下几个性质：,P,P,(,P,P,),P,(,P,Q,)(,P,Q,),(,P,Q,),(,P,Q,),P,Q, (,P,P,)(,Q,Q,),(,P,)(,Q,),(,P,Q,),P,Q,7,四、或非,定义1.6.4,设,P,和,Q,是两个命题，复合命题,PQ,称作,P,和,Q,的或非。定义为：当且仅当,P、Q,的真值都为假时，,PQ,的真值为真。联结词“”称为或非联结词。,联结词,“,”,的定义如表1-6.4,由此定义可得到,P,Q,(,P,Q,),表1-6.4,P,Q,P,Q,0,0,1,0,1,0,1,0,0,1,1,0,8,四、或非,“”也可以看成逻辑运算，它是二元逻辑运算。,联结词还有下面的几个性质：,PP,(PP),P,(PQ)(PQ),(PQ),(PQ),PQ,(PP)(QQ),PQ,(PQ),PQ,9,五、全功能联接词集与最小联结词组,至此我们已学习了九个联结词，是否还需要定义其它联结词？,P26,定义,（,补充）,设,S,是一个联结词集合，如果任何,n,(,n,1),个变元组成的公式，都可以由,S,中的联结词来表示，则称,S,是,全功能联结词集,。,除,T，F,及命题变元本身外，命题联结词一共九个就足够了，它们组成了一个,全功能联结词集,。但并不是所有联结词都是必要的，有些联结词的公式可用另外的一些联结词的公式等价代换。,10,五、全功能联接词集与最小联结词组,利用下列3个等价式可将任何命题公式中的命题联结词,“ ”,、,“,”和 “,”,去掉。,P Q,(,P,Q,),P,Q,(,P,Q,),P,Q,(,P,Q,),所以,，,是全功能联结词集,利用下列,2,个等价式可将任何命题公式中的,命题,联结词,“,”,和“,”去掉。,P,Q,P,Q,P,Q,(,P,Q,)(,Q,P,),(,P,Q,)(,Q,P,),所以,，,是全功能联结词集。,用德摩根律可证明,，,和,，,是全功能联结词集,可以证明,，,和,，,的任何子集都不是全功能联结词集。,11,五、全功能联接词集与最小联结词组,定义,（,补充）,设,S,是全功能联结词集，如果去掉其中的任何联结词后，就不是全功能联结词集，则称,S,是,最小联结词组,。,可以证明,，,，,，,，,，,是最小全功能联结词集。,12,内容小结,四个新联结词,全功能联接词集与最小联结词组,13,课后作业,P23（3）(8) (b),(d),(f),14,