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

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

2、(结合律) P(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为一矛盾式。证明P254二、条件否定定义1-6.2 P255三、与非定义1.6.3 设P和Q是两个命题公式，复合命题PQ称作P和Q的“与非”。定义为：当且仅当P和Q真值都是真时，PQ才为假。联结词“”称为与非联结词。联结词“”的定义如表1-6.3可以看出，P Q （P Q）表1-6.3PQPQ0010111011106三、与非“”也可以看成逻辑运算，它是二元逻辑运算。联结词“

3、”还有以下几个性质： PP(PP) P (PQ)(PQ) (PQ) (PQ)PQ (PP)(QQ)(P)(Q) (PQ)PQ7四、或非定义1.6.4 设P和Q是两个命题，复合命题PQ称作P和Q的或非。定义为：当且仅当P、Q的真值都为假时，PQ的真值为真。联结词“”称为或非联结词。联结词“”的定义如表1-6.4由此定义可得到 PQ(PQ)表1-6.4PQPQ0010101001108四、或非“”也可以看成逻辑运算，它是二元逻辑运算。联结词还有下面的几个性质： PP(PP) P (PQ)(PQ) (PQ) (PQ)PQ (PP)(QQ) PQ(PQ)PQ9五、全功能联接词集与最小联结词组至此我们已

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