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

1、1,第一章 命题逻辑,1-6 其它联结词,2,其它联结词,目前已经学习了、五种联结词，但这些联结词不能很广泛地直接表达命题间的联系（如不可兼析取），为此我们再定义一些命题联结词。,3,一、不可兼析取（异或）,定义1-6.1 设P和Q是两个命题，复合命题P Q称作P和Q的不可兼析取（也叫异或）。定义为：P Q为1当且仅当P和Q的真值不相同时。 联结词“ ”的定义如表1-6.1,4,一、不可兼析取（异或）,“ ”也可以看成逻辑运算，它是二元逻辑运算。它在程序设中有广泛的引用。 不可兼析取有下列的性质(P、Q、R为命题公式)： P QP Q (交换律) (P Q) RP (Q R) (结合律) P(

2、Q R)(PQ) (PR) (合取对异或的分配律) P Q(PQ)(PQ) P Q(PQ) P P0，0 PP，1 PP 定理1-6.1 设P，Q，R为命题公式，如果P QR，则P RQ，Q RP，P Q R为一矛盾式。 证明P25,5,二、条件否定,定义1-6.2 P25,6,三、与非,定义1.6.3 设P和Q是两个命题公式，复合命题PQ称作P和Q的“与非”。定义为：当且仅当P和Q真值都是真时，PQ才为假。联结词“”称为与非联结词。 联结词“”的定义如表1-6.3 可以看出，P Q （P Q）,7,三、与非,“”也可以看成逻辑运算，它是二元逻辑运算。 联结词“”还有以下几个性质： PP(PP

3、) 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

4、 定义（补充） 设S是一个联结词集合，如果任何n(n1)个变元组成的公式，都可以由S中的联结词来表示，则称S是全功能联结词集。 除T，F及命题变元本身外，命题联结词一共九个就足够了，它们组成了一个全功能联结词集。但并不是所有联结词都是必要的，有些联结词的公式可用另外的一些联结词的公式等价代换。,11,五、全功能联接词集与最小联结词组,利用下列3个等价式可将任何命题公式中的命题联结词 “ ”、“”和 “”去掉。 P Q(PQ) PQ(PQ) PQ(PQ) 所以，是全功能联结词集 利用下列2个等价式可将任何命题公式中的命题联结词 “”和“”去掉。 PQPQ PQ(PQ)(QP)(PQ)(QP) 所以，是全功能联结词集。 用德摩根律可证明，和，是全功能联结词集 可以证明，和，的任何子集都不是全功能联结词集。,12,五、全功能联接词集与最小联结词组,定义（补充）设S是全功能联结词集，如果去掉其中的任何联结词后，就不是全功能联结词集，则称S是最小联结词组。 可以证明，是最