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

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