离散数学(1.6其他联接词)

1离散数学(DiscreteMathematics)2第一章命题逻辑（PropositionalLogic）

1.6其它联结词(OtherConnectives)1.6.1不可兼析取(排斥或/异或)(exclusive

or)1.6.2与非联结词(Nand)1.6.3或非联结词(Nor)1.6.4条件否定联结词(Non-conditional)1.6.5最小联结词组(Theminimalsetofconnectives)3第一章命题逻辑（PropositionalLogic）

1.6其它联结词(OtherConnectives)

在第二节(1.2)中我们定义了五种基本的联结词┐，，，→，,但在命题逻辑中,这些联结词还不能很广泛地直接表达命题之间的联系(例如,“P异或Q”只能间接地表示为(P┐Q)(┐PQ)),为此本节再给出逻辑设计中常用的另外四种联结词.1.6.1不可兼析取(排斥或/异或)(exclusiveor)定义1.6.1:设P,Q为二命题，复合命题“P,Q之中恰有一个为真”称为P与Q的不可兼析取，记作PQ，符号“”

称为异或联结词.PQ为真当且仅当P和Q的真值不同.

4第一章命题逻辑（PropositionalLogic）

1.6其它联结词(OtherConnectives)联结词“”的定义真值表PQ

P

Q

FFFTTTTFTTTF定义了联结词“”后,命题逻辑中的有些命题就可以符号化为非常简捷的形式.例:派小王或小李中的一人去开会。（排斥或）设P：派小王去开会。Q：派小李去开会。则上述命题可符号化为：(PQ)5第一章命题逻辑（PropositionalLogic）

1.6其它联结词(OtherConnectives)说明：“”

属于二元(binary)运算符.联结词“”的性质:设P,Q,R为命题公式,则有(1)PQQP(交换律)(2)(PQ)RP(QR)(结合律)(3)P∧(QR)(P∧Q)(P∧R)(分配律)(4)(PQ)

(P∧

Q)∨(P∧Q)(5)(PQ)

(PQ)(6)PPF,FPP,TP

P6第一章命题逻辑（PropositionalLogic）

1.6其它联结词(OtherConnectives)

定理1.6.1:设P,Q,R为命题公式,如果PQR,则PRQ,QRP,且PQR为一矛盾式.证:由PQR得PRP(PQ)(PP)QFQQQRQ(PQ)FPPPQRRRF7第一章命题逻辑（PropositionalLogic）

1.6其它联结词(OtherConnectives)1.6.2与非联结词(Nand↑)定义1.6.2设P,Q为二命题，复合命题“P与Q的否定”称为P与Q的与非式，记作P↑Q，符号“↑”

称为与非联结词.P↑Q为真当且仅当P和Q不同时为真.联结词“↑”的定义真值表PQ

P↑Q

FFTFTTTFTTTF8第一章命题逻辑（PropositionalLogic）

1.6其它联结词(OtherConnectives)说明:(1)

由定义可知,P↑Q(P∧Q)(2)“↑”

属于二元(binary)运算符.联结词“↑”的性质:(1)P↑P(P∧P)P(2)(P↑Q)↑(P↑Q)(P↑Q)(P∧Q)

(3)(P↑P)↑(Q↑Q)P↑Q(P∧Q)P∨Q9第一章命题逻辑（PropositionalLogic）

1.6其它联结词(OtherConnectives)1.6.3或非联结词(Nor)定义1.6.3设P,Q为二命题，复合命题“P或Q的否定”称为P与Q的或非式，记作P↓Q，符号“↓”称为或非联结词.P↓Q为真当且仅当P与Q同为假.联结词“↓”的定义真值表PQP↓Q FFTFTFTFFTTF10第一章命题逻辑（PropositionalLogic）

1.6其它联结词(OtherConnectives)说明:(1)

由定义可知,P↓Q(P∨Q)(2)“↓”

属于二元(binary)运算符.↓联结词“↓”的性质:(1)P↓P(P∨P)P(2)(P↓Q)↓(P↓Q)(P↓Q)(P∨Q)(3)(P↓P)↓(Q↓Q)P↓Q(P∨Q)P∧Q11第一章命题逻辑（PropositionalLogic）

1.6其它联结词(OtherConnectives)1.6.4条件否定联结词(Non-conditional)定义1.6.4设P,Q为二命题，复合命题“PQ”称为命题P与Q的条件否定式,PQ为真当且仅当P为真且Q为假.

联结词“”的定义真值表PQP→

QFFFFTFTFTTTF12第一章命题逻辑（PropositionalLogic）

1.6其它联结词(OtherConnectives)说明:(1)

由定义可知,PQ(PQ)(2)“”

属于二元(binary)运算符.有了联结词后，合式公式的定义1.3.2可加入这四个联结词.1.6.5最小联结词组(Theminimalsetofconnectives)至此,我们一共定义了9个联结词,为了直接表达命题之间的联系,是否还需要定义其它联结词呢?回答是否定的.即含n个命题变元的所有个互不等价的命题公式,均可由这

9个联结词直接表达.下面我们以含两个命题变元P，Q的所有互等价的命题公式为例，来说明这一问题。13第一章命题逻辑（PropositionalLogic）

1.6其它联结词(OtherConnectives)由两个命题变元P，Q所构成的互不等价的个命题公式如下:PQFP∧QPQPQPQPQP∨QFFFFFFFFFFFTFFFFTTTTTFFFTTFFTTTTFTFTFTFT第一章命题逻辑（PropositionalLogic）

1.6其它联结词(OtherConnectives)

由上表可知,9个联结词足以直接表达命题之间的各种联系.二元运算中，9个联结词并不都是必要的。PQPQPQ┓QQ→P┓PP→QPQTFFTTTTTTTTFTFFFFTTTTTFFFTTFFTTTTFTFTFTFT第一章命题逻辑（PropositionalLogic）

1.6其它联结词(OtherConnectives)定义1.6.5：在一个联结词的集合中,如果一个联结词可由该集合中的其它联结词定义,则称此联结词为冗余联结词,否则称为独立联结词.不含冗余联结词的联结词组称为最小联结词组.说明:最小联结词组中的联结词构成的式子足以把一切命题公式等价的表达出来。对于9个联结词的集合{┐,,,→,,

,

,,}由于(1)PQ(P→Q)(Q→P)(2)PQ┐PQ(3)PQ┐(┐P┐Q)(4)PQ┐(┐P┐Q)

16第一章命题逻辑（PropositionalLogic）

1.6其它联结词(OtherConnectives)

(5)

(PQ)

(PQ)(6)P↑Q(P∧Q)(7)P↓Q(P∨Q)(8)PQ(PQ)故任意命题公式都可由仅包含{┐,}或{┐,}的命题公式等价代换.即9个联结词的集合中至少有七个冗余联结词.又注意到联结词{┐,}和{┐,}不再有冗余联结词,故{┐,}或{┐,}为最小联结词组.但实际中为了使用方便,命题公式常常同时包含{┐,,}.17第一章命题逻辑（PropositionalLogic）

1.6其它联结词(OtherConnectives)例1:试证{↑}是最小联结词组. 证：┐P┐(PP)P↑PPQ┐┐(PQ)┐(P↑Q)(P↑Q)↑(P↑Q)PQ┐(┐P┐Q)┐((P↑P)(Q↑Q))

(P↑P)↑(Q↑Q)例2.试证{┐，→}是最小联结词组

证：PQ┐(┐P┐Q)┐(P→┐Q)PQ┐(┐P)Q┐P→Q小结:本节主要介绍了四种新的联结词及最小联结词组.

作业:1.P29(1),(2),(4)