離散數(shù)學(xué)(1.6其他聯(lián)接詞)

1離散數(shù)學(xué)(DiscreteMathematics)2第一章命題邏輯（PropositionalLogic）

1.6其它聯(lián)結(jié)詞(OtherConnectives)1.6.1不可兼析取(排斥或/異或)(exclusive

or)1.6.2與非聯(lián)結(jié)詞(Nand)1.6.3或非聯(lián)結(jié)詞(Nor)1.6.4條件否定聯(lián)結(jié)詞(Non-conditional)1.6.5最小聯(lián)結(jié)詞組(Theminimalsetofconnectives)3第一章命題邏輯（PropositionalLogic）

1.6其它聯(lián)結(jié)詞(OtherConnectives)

在第二節(jié)(1.2)中我們定義了五種基本的聯(lián)結(jié)詞┐，，，→，,但在命題邏輯中,這些聯(lián)結(jié)詞還不能很廣泛地直接表達(dá)命題之間的聯(lián)系(例如,“P異或Q”只能間接地表示為(P┐Q)(┐PQ)),為此本節(jié)再給出邏輯設(shè)計(jì)中常用的另外四種聯(lián)結(jié)詞.1.6.1不可兼析取(排斥或/異或)(exclusiveor)定義1.6.1:設(shè)P,Q為二命題，復(fù)合命題“P,Q之中恰有一個(gè)為真”稱(chēng)為P與Q的不可兼析取，記作PQ，符號(hào)“”

稱(chēng)為異或聯(lián)結(jié)詞.PQ為真當(dāng)且僅當(dāng)P和Q的真值不同.

4第一章命題邏輯（PropositionalLogic）

1.6其它聯(lián)結(jié)詞(OtherConnectives)聯(lián)結(jié)詞“”的定義真值表PQ

P

Q

FFFTTTTFTTTF定義了聯(lián)結(jié)詞“”后,命題邏輯中的有些命題就可以符號(hào)化為非常簡(jiǎn)捷的形式.例:派小王或小李中的一人去開(kāi)會(huì)。（排斥或）設(shè)P：派小王去開(kāi)會(huì)。Q：派小李去開(kāi)會(huì)。則上述命題可符號(hào)化為：(PQ)5第一章命題邏輯（PropositionalLogic）

1.6其它聯(lián)結(jié)詞(OtherConnectives)說(shuō)明：“”

屬于二元(binary)運(yùn)算符.聯(lián)結(jié)詞“”的性質(zhì):設(shè)P,Q,R為命題公式,則有(1)PQQP(交換律)(2)(PQ)RP(QR)(結(jié)合律)(3)P∧(QR)(P∧Q)(P∧R)(分配律)(4)(PQ)

(P∧

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

(PQ)(6)PPF,FPP,TP

P6第一章命題邏輯（PropositionalLogic）

1.6其它聯(lián)結(jié)詞(OtherConnectives)

定理1.6.1:設(shè)P,Q,R為命題公式,如果PQR,則PRQ,QRP,且PQR為一矛盾式.證:由PQR得PRP(PQ)(PP)QFQQQRQ(PQ)FPPPQRRRF7第一章命題邏輯（PropositionalLogic）

1.6其它聯(lián)結(jié)詞(OtherConnectives)1.6.2與非聯(lián)結(jié)詞(Nand↑)定義1.6.2設(shè)P,Q為二命題，復(fù)合命題“P與Q的否定”稱(chēng)為P與Q的與非式，記作P↑Q，符號(hào)“↑”

稱(chēng)為與非聯(lián)結(jié)詞.P↑Q為真當(dāng)且僅當(dāng)P和Q不同時(shí)為真.聯(lián)結(jié)詞“↑”的定義真值表PQ

P↑Q

FFTFTTTFTTTF8第一章命題邏輯（PropositionalLogic）

1.6其它聯(lián)結(jié)詞(OtherConnectives)說(shuō)明:(1)

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

屬于二元(binary)運(yùn)算符.聯(lián)結(jié)詞“↑”的性質(zhì):(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其它聯(lián)結(jié)詞(OtherConnectives)1.6.3或非聯(lián)結(jié)詞(Nor)定義1.6.3設(shè)P,Q為二命題，復(fù)合命題“P或Q的否定”稱(chēng)為P與Q的或非式，記作P↓Q，符號(hào)“↓”稱(chēng)為或非聯(lián)結(jié)詞.P↓Q為真當(dāng)且僅當(dāng)P與Q同為假.聯(lián)結(jié)詞“↓”的定義真值表PQP↓Q FFTFTFTFFTTF10第一章命題邏輯（PropositionalLogic）

1.6其它聯(lián)結(jié)詞(OtherConnectives)說(shuō)明:(1)

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

屬于二元(binary)運(yùn)算符.↓聯(lián)結(jié)詞“↓”的性質(zhì):(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其它聯(lián)結(jié)詞(OtherConnectives)1.6.4條件否定聯(lián)結(jié)詞(Non-conditional)定義1.6.4設(shè)P,Q為二命題，復(fù)合命題“PQ”稱(chēng)為命題P與Q的條件否定式,PQ為真當(dāng)且僅當(dāng)P為真且Q為假.

聯(lián)結(jié)詞“”的定義真值表PQP→

QFFFFTFTFTTTF12第一章命題邏輯（PropositionalLogic）

1.6其它聯(lián)結(jié)詞(OtherConnectives)說(shuō)明:(1)

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

屬于二元(binary)運(yùn)算符.有了聯(lián)結(jié)詞后，合式公式的定義1.3.2可加入這四個(gè)聯(lián)結(jié)詞.1.6.5最小聯(lián)結(jié)詞組(Theminimalsetofconnectives)至此,我們一共定義了9個(gè)聯(lián)結(jié)詞,為了直接表達(dá)命題之間的聯(lián)系,是否還需要定義其它聯(lián)結(jié)詞呢?回答是否定的.即含n個(gè)命題變?cè)乃袀€(gè)互不等價(jià)的命題公式,均可由這

9個(gè)聯(lián)結(jié)詞直接表達(dá).下面我們以含兩個(gè)命題變?cè)狿，Q的所有互等價(jià)的命題公式為例，來(lái)說(shuō)明這一問(wèn)題。13第一章命題邏輯（PropositionalLogic）

1.6其它聯(lián)結(jié)詞(OtherConnectives)由兩個(gè)命題變?cè)狿，Q所構(gòu)成的互不等價(jià)的個(gè)命題公式如下:PQFP∧QPQPQPQPQP∨QFFFFFFFFFFFTFFFFTTTTTFFFTTFFTTTTFTFTFTFT第一章命題邏輯（PropositionalLogic）

1.6其它聯(lián)結(jié)詞(OtherConnectives)

由上表可知,9個(gè)聯(lián)結(jié)詞足以直接表達(dá)命題之間的各種聯(lián)系.二元運(yùn)算中，9個(gè)聯(lián)結(jié)詞并不都是必要的。PQPQPQ┓Q(chēng)Q→P┓PP→QPQTFFTTTTTTTTFTFFFFTTTTTFFFTTFFTTTTFTFTFTFT第一章命題邏輯（PropositionalLogic）

1.6其它聯(lián)結(jié)詞(OtherConnectives)定義1.6.5：在一個(gè)聯(lián)結(jié)詞的集合中,如果一個(gè)聯(lián)結(jié)詞可由該集合中的其它聯(lián)結(jié)詞定義,則稱(chēng)此聯(lián)結(jié)詞為冗余聯(lián)結(jié)詞,否則稱(chēng)為獨(dú)立聯(lián)結(jié)詞.不含冗余聯(lián)結(jié)詞的聯(lián)結(jié)詞組稱(chēng)為最小聯(lián)結(jié)詞組.說(shuō)明:最小聯(lián)結(jié)詞組中的聯(lián)結(jié)詞構(gòu)成的式子足以把一切命題公式等價(jià)的表達(dá)出來(lái)。對(duì)于9個(gè)聯(lián)結(jié)詞的集合{┐,,,→,,

,

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

16第一章命題邏輯（PropositionalLogic）

1.6其它聯(lián)結(jié)詞(OtherConnectives)

(5)

(PQ)

(PQ)(6)P↑Q(P∧Q)(7)P↓Q(P∨Q)(8)PQ(PQ)故任意命題公式都可由僅包含{┐,}或{┐,}的命題公式等價(jià)代換.即9個(gè)聯(lián)結(jié)詞的集合中至少有七個(gè)冗余聯(lián)結(jié)詞.又注意到聯(lián)結(jié)詞{┐,}和{┐,}不再有冗余聯(lián)結(jié)詞,故{┐,}或{┐,}為最小聯(lián)結(jié)詞組.但實(shí)際中為了使用方便,命題公式常常同時(shí)包含{┐,,}.17第一章命題邏輯（PropositionalLogic）

1.6其它聯(lián)結(jié)詞(OtherConnectives)例1:試證{↑}是最小聯(lián)結(jié)詞組. 證：┐P┐(PP)P↑PPQ┐┐(PQ)┐(P↑Q)(P↑Q)↑(P↑Q)PQ┐(┐P┐Q)┐((P↑P)(Q↑Q))

(P↑P)↑(Q↑Q)例2.試證{┐，→}是最小聯(lián)結(jié)詞組

證：PQ┐(┐P┐Q)┐(P→┐Q)PQ┐(┐P)Q┐P→Q小結(jié):本節(jié)主要介紹了四種新的聯(lián)結(jié)詞及最小聯(lián)結(jié)詞組.

作業(yè):1.P29(1),(2),(4)