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

1、121.6.1 不可兼析取不可兼析取(排斥或排斥或/異或異或)(exclusive or)1.6.2 與非聯(lián)結(jié)詞與非聯(lián)結(jié)詞(Nand1.6.3 或非聯(lián)結(jié)詞或非聯(lián)結(jié)詞(Nor1.6.4 條件否定聯(lián)結(jié)詞條件否定聯(lián)結(jié)詞(Non-conditional1.6.5 最小聯(lián)結(jié)詞組最小聯(lián)結(jié)詞組(The minimal set of connectives3 在第二節(jié)在第二節(jié)(1.2)中我們定義了五種基本的聯(lián)結(jié)詞中我們定義了五種基本的聯(lián)結(jié)詞， ， ， ，, ,但在但在命題邏輯中命題邏輯中,這些聯(lián)結(jié)詞還不能很廣泛這些聯(lián)結(jié)詞還不能很廣泛地直接表達(dá)命題之間的聯(lián)系地直接表達(dá)命題之間的聯(lián)系(例如例如, “P異或異或Q”

2、只能間接地只能間接地表示為表示為(P Q)Q) (P Q),Q),為此本節(jié)再給出邏輯設(shè)計(jì)中為此本節(jié)再給出邏輯設(shè)計(jì)中常用的另外四種常用的另外四種聯(lián)結(jié)詞聯(lián)結(jié)詞.1.6.1 不可兼析取不可兼析取(排斥或排斥或/異或異或)(exclusive or)定義定義1.6.1:設(shè)設(shè)P,Q為二命題，復(fù)合命題為二命題，復(fù)合命題“P,Q之中之中恰有一恰有一個(gè)個(gè)為真為真” 稱為稱為P與與Q的的不可兼析取不可兼析取，記作，記作P Q，符號(hào)，符號(hào)“ ” 稱為稱為異或異或聯(lián)結(jié)詞聯(lián)結(jié)詞. P Q P Q 為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)P P和和Q Q的的真值不同真值不同. . 4 聯(lián)結(jié)詞聯(lián)結(jié)詞“ ”的定義真值表的定義真值表P PQ

3、 Q P P Q Q F FF FF FT TT TT TT TF FT TT TT TF F定義了定義了聯(lián)結(jié)詞聯(lián)結(jié)詞“ ”后后, 命題邏輯中的有些命題就可命題邏輯中的有些命題就可以符號(hào)化為非常簡(jiǎn)捷的形式以符號(hào)化為非常簡(jiǎn)捷的形式.例例: 派小王或小李中的一人去開會(huì)。派小王或小李中的一人去開會(huì)。（） 設(shè)設(shè)P：派小王去開會(huì)。派小王去開會(huì)。Q：派小李去開會(huì)。派小李去開會(huì)。 則上述命題可符號(hào)化為：則上述命題可符號(hào)化為：(P Q)5說明：說明：“ ” 屬于二元屬于二元(binary)運(yùn)算符運(yùn)算符.聯(lián)結(jié)詞聯(lián)結(jié)詞“ ”的性質(zhì)的性質(zhì): 設(shè)設(shè)P, Q, R為命題公式為命題公式, 則有則有(1) P Q Q P

4、(交換律交換律)(2) (P Q) R P (Q R) (結(jié)合律結(jié)合律)(3) P(Q R) (PQ ) (PR) (分配律分配律)(4) (P Q) (P Q) ( PQ)(5) (P Q) (PQ)(6) P P F, F P P, T P P6 定理定理1.6.1:設(shè)設(shè)P, Q, R為命題公式為命題公式, 如果如果 P QR,R,則則 P RQ ,Q RP, P, 且且P Q R P Q R 為一矛盾式為一矛盾式. . 證證: : 由由 P QR R 得得 P RP RP (P Q)P (P Q)(P P) Q(P P) QF QF QQ Q Q R Q RQ (P Q)Q (P Q)F

5、 PF PP P P Q R P Q RR RR RF F71.6.2 與非聯(lián)結(jié)詞與非聯(lián)結(jié)詞(Nand定義定義1.6.2 設(shè)設(shè)P,Q為二命題，復(fù)合命題為二命題，復(fù)合命題“P與與Q的否定的否定” 稱稱為為P與與Q的與非式，記作的與非式，記作PQ，符號(hào)，符號(hào)“” 稱為與非聯(lián)結(jié)稱為與非聯(lián)結(jié)詞詞. PQ PQ 為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)P P和和Q Q不同時(shí)為真不同時(shí)為真. . 聯(lián)結(jié)詞聯(lián)結(jié)詞“”的定義真值表的定義真值表P PQ Q P PQ Q F FF FT TF FT TT TT TF FT TT TT TF F8說明說明: (1) 由定義可知由定義可知, PQ (PQ) (2)“” 屬于二元屬于二

6、元(binary)運(yùn)算符運(yùn)算符.聯(lián)結(jié)詞聯(lián)結(jié)詞“”的性質(zhì)的性質(zhì): (1) PP ( PPP) P (2) (PQ)(PQ) ( PQ Q)(PQQ) (3)(3)(PP)(QQ) P Q ( P Q) PQ 91.6.3 或非聯(lián)結(jié)詞或非聯(lián)結(jié)詞(Nor定義定義1.6.3 設(shè)設(shè)P,Q為二命題，復(fù)合命題為二命題，復(fù)合命題“P或或Q的否定的否定” 稱為稱為P與與Q的或非式，記作的或非式，記作PQ ，符號(hào)，符號(hào)“”稱為或非聯(lián)結(jié)詞稱為或非聯(lián)結(jié)詞. PQ為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng) P與與Q同為假同為假. 聯(lián)結(jié)詞聯(lián)結(jié)詞“”的定義真值表的定義真值表P PQ Q PQ PQ F FF FT TF FT TF FT T

7、F FF FT TT TF F10說明說明: (1) 由定義可知由定義可知, PQ (PQ) (2)“” 屬于二元屬于二元(binary)運(yùn)算符運(yùn)算符.聯(lián)結(jié)詞聯(lián)結(jié)詞“”的性質(zhì)的性質(zhì): (1) PP ( PP P) P (2) (PQ)(PQ) (PQ) (PQ Q)(3)(3)(PP)(QQ) P Q ( P Q)PQ 111.6.4 條件否定聯(lián)結(jié)詞條件否定聯(lián)結(jié)詞(Non-conditional定義定義1.6.4 設(shè)設(shè)P,Q為二命題，復(fù)合命題為二命題，復(fù)合命題“P Q” 稱為命稱為命題題P與與Q的條件否定式的條件否定式, P Q為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)P為真且為真且Q為假為假. 聯(lián)結(jié)詞聯(lián)結(jié)詞“

8、 ”的定義真值表的定義真值表P PQ QP P Q QF FF FF FF FT TF FT TF FT TT TT TF Fccc12說明說明: (1) 由定義可知由定義可知, P Q (P Q) (2)“ ” 屬于二元屬于二元(binary)運(yùn)算符運(yùn)算符.有了聯(lián)結(jié)詞有了聯(lián)結(jié)詞 后，合式公式的定義后，合式公式的定義1.3.2可加入這可加入這四個(gè)聯(lián)結(jié)詞四個(gè)聯(lián)結(jié)詞.1.6.5 最小聯(lián)結(jié)詞組最小聯(lián)結(jié)詞組(The minimal set of connectives 至此至此,我們一共定義了我們一共定義了9 9個(gè)聯(lián)結(jié)詞個(gè)聯(lián)結(jié)詞,為了直接表達(dá)命題之間為了直接表達(dá)命題之間的聯(lián)系的聯(lián)系, ,是否還需要定義

9、其它聯(lián)結(jié)詞呢是否還需要定義其它聯(lián)結(jié)詞呢? ? 回答是否定的回答是否定的. .即即含含n n個(gè)命題變?cè)乃袀€(gè)命題變?cè)乃?個(gè)互不等價(jià)的命題公式個(gè)互不等價(jià)的命題公式, ,均可由這均可由這 9 9個(gè)聯(lián)結(jié)詞直接表達(dá)個(gè)聯(lián)結(jié)詞直接表達(dá). .下面我們以含兩個(gè)命題變?cè)旅嫖覀円院瑑蓚€(gè)命題變?cè)狿 P，Q Q的所的所有互等價(jià)的命題公式為例，來說明這一問題。有互等價(jià)的命題公式為例，來說明這一問題。ccc,n2213由兩個(gè)命題變?cè)蓛蓚€(gè)命題變?cè)狿 P，Q Q所構(gòu)成的互不等價(jià)的所構(gòu)成的互不等價(jià)的 個(gè)命題公式個(gè)命題公式如下如下: :42P QFPQPQP QPQ PQP Q PQF F FFFFFFFFF T FFF

10、FTTTTT F FFTTFFTTT T FTFTFTFT c c 由上表可知由上表可知, 9 9個(gè)聯(lián)結(jié)詞足以直接表達(dá)命題之間的各種聯(lián)個(gè)聯(lián)結(jié)詞足以直接表達(dá)命題之間的各種聯(lián)系系. .二元運(yùn)算中，二元運(yùn)算中，9 9個(gè)聯(lián)結(jié)詞并不都是必要的。個(gè)聯(lián)結(jié)詞并不都是必要的。P QP QPQQQP P PQ P QTF FTTTTTTTTF TFFFFTTTTT FFFTTFFTTT TFTFTFTFT定義定義1.6.5：在一個(gè)聯(lián)結(jié)詞的集合中在一個(gè)聯(lián)結(jié)詞的集合中,如果一個(gè)聯(lián)結(jié)詞可如果一個(gè)聯(lián)結(jié)詞可由該集合中的其它聯(lián)結(jié)詞定義由該集合中的其它聯(lián)結(jié)詞定義,則則稱此稱此聯(lián)結(jié)詞為冗余聯(lián)聯(lián)結(jié)詞為冗余聯(lián)結(jié)詞結(jié)詞,否則稱為獨(dú)立聯(lián)

11、結(jié)詞否則稱為獨(dú)立聯(lián)結(jié)詞. 不含冗余聯(lián)結(jié)詞的聯(lián)結(jié)詞組不含冗余聯(lián)結(jié)詞的聯(lián)結(jié)詞組稱為稱為最小聯(lián)結(jié)詞組最小聯(lián)結(jié)詞組. .說明說明: :最小聯(lián)結(jié)詞組中的聯(lián)結(jié)詞構(gòu)成的式子足以把一切最小聯(lián)結(jié)詞組中的聯(lián)結(jié)詞構(gòu)成的式子足以把一切命題公式等價(jià)的表達(dá)出來。命題公式等價(jià)的表達(dá)出來。對(duì)于對(duì)于9 9個(gè)聯(lián)結(jié)詞的集合個(gè)聯(lián)結(jié)詞的集合, , , , , , , , , , , 由于由于 (1) PQ (PQ)(PQ) (QP)(QP) (2) P (2) PQ QPP Q Q (3) P P Q Q(P(P Q)Q) (4) P P Q Q(P(P Q)Q) c16 (5)(5) (P Q) (PQ) (6) PQ (PQ) (

12、7) PQ (PQ) (8) P Q (P Q)故任意命題公式都可由僅包含故任意命題公式都可由僅包含, 或或, 的命題的命題公式等價(jià)代換公式等價(jià)代換.即即9 9個(gè)聯(lián)結(jié)詞的集合中至少有七個(gè)個(gè)聯(lián)結(jié)詞的集合中至少有七個(gè)冗余聯(lián)冗余聯(lián)結(jié)詞結(jié)詞. 又注意到聯(lián)結(jié)詞又注意到聯(lián)結(jié)詞, 和和, 不再有冗余聯(lián)結(jié)不再有冗余聯(lián)結(jié)詞詞, 故故, 或或, 為最小聯(lián)結(jié)詞組為最小聯(lián)結(jié)詞組.但實(shí)際中為了使但實(shí)際中為了使用方便用方便, 命題公式常常同時(shí)包含命題公式常常同時(shí)包含, , , . c17例例1:試證試證是最小聯(lián)結(jié)詞組是最小聯(lián)結(jié)詞組. .證：證：PP(P(P P)P)PP PP P P Q Q(P(P Q)Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ) P P Q Q(P(P Q)Q)(PP)(PP) (QQ)(QQ) (PP)(QQ)(PP)(QQ)例例2.2.試證試證，是最小聯(lián)結(jié)詞組是最小聯(lián)結(jié)詞組 證：證：P P Q Q(P(P Q)Q)(PQ)(PQ) P P Q Q(P)(P) Q QPQPQ小結(jié)小結(jié):本節(jié)主要介紹了四種新的聯(lián)結(jié)詞本節(jié)主要介紹了四種新的聯(lián)結(jié)詞 及最及最小聯(lián)結(jié)詞組小聯(lián)結(jié)詞組. 作業(yè)作業(yè): 1. P29 (1), (2), (4) c,182. 預(yù)習(xí)預(yù)習(xí)1.7思考題思考題: 1. 何謂命題公式的何