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)