離散數學(1.6其他聯接詞)

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

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

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

4、(交換律交換律)(2) (P Q) R P (Q R) (結合律結合律)(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:設設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 與非聯結詞與非聯結詞(Nand定義定義1.6.2 設設P,Q為二命題，復合命題為二命題，復合命題“P與與Q的否定的否定” 稱稱為為P與與Q的與非式，記作的與非式，記作PQ，符號，符號“” 稱為與非聯結稱為與非聯結詞詞. PQ PQ 為真當且僅當為真當且僅當P P和和Q Q不同時為真不同時為真. . 聯結詞聯結詞“”的定義真值表的定義真值表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)運算符運算符.聯結詞聯結詞“”的性質的性質: (1) PP ( PPP) P (2) (PQ)(PQ) ( PQ Q)(PQQ) (3)(3)(PP)(QQ) P Q ( P Q) PQ 91.6.3 或非聯結詞或非聯結詞(Nor定義定義1.6.3 設設P,Q為二命題，復合命題為二命題，復合命題“P或或Q的否定的否定” 稱為稱為P與與Q的或非式，記作的或非式，記作PQ ，符號，符號“”稱為或非聯結詞稱為或非聯結詞. PQ為真當且僅當為真當且僅當 P與與Q同為假同為假. 聯結詞聯結詞“”的定義真值表的定義真值表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)運算符運算符.聯結詞聯結詞“”的性質的性質: (1) PP ( PP P) P (2) (PQ)(PQ) (PQ) (PQ Q)(3)(3)(PP)(QQ) P Q ( P Q)PQ 111.6.4 條件否定聯結詞條件否定聯結詞(Non-conditional定義定義1.6.4 設設P,Q為二命題，復合命題為二命題，復合命題“P Q” 稱為命稱為命題題P與與Q的條件否定式的條件否定式, P Q為真當且僅當為真當且僅當P為真且為真且Q為假為假. 聯結詞聯結詞“

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)運算符運算符.有了聯結詞有了聯結詞 后，合式公式的定義后，合式公式的定義1.3.2可加入這可加入這四個聯結詞四個聯結詞.1.6.5 最小聯結詞組最小聯結詞組(The minimal set of connectives 至此至此,我們一共定義了我們一共定義了9 9個聯結詞個聯結詞,為了直接表達命題之間為了直接表達命題之間的聯系的聯系, ,是否還需要定義

9、其它聯結詞呢是否還需要定義其它聯結詞呢? ? 回答是否定的回答是否定的. .即即含含n n個命題變元的所有個命題變元的所有 個互不等價的命題公式個互不等價的命題公式, ,均可由這均可由這 9 9個聯結詞直接表達個聯結詞直接表達. .下面我們以含兩個命題變元下面我們以含兩個命題變元P P，Q Q的所的所有互等價的命題公式為例，來說明這一問題。有互等價的命題公式為例，來說明這一問題。ccc,n2213由兩個命題變元由兩個命題變元P P，Q Q所構成的互不等價的所構成的互不等價的 個命題公式個命題公式如下如下: :42P QFPQPQP QPQ PQP Q PQF F FFFFFFFFF T FFF

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

11、結詞否則稱為獨立聯結詞. 不含冗余聯結詞的聯結詞組不含冗余聯結詞的聯結詞組稱為稱為最小聯結詞組最小聯結詞組. .說明說明: :最小聯結詞組中的聯結詞構成的式子足以把一切最小聯結詞組中的聯結詞構成的式子足以把一切命題公式等價的表達出來。命題公式等價的表達出來。對于對于9 9個聯結詞的集合個聯結詞的集合, , , , , , , , , , , 由于由于 (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)故任意命題公式都可由僅包含故任意命題公式都可由僅包含, 或或, 的命題的命題公式等價代換公式等價代換.即即9 9個聯結詞的集合中至少有七個個聯結詞的集合中至少有七個冗余聯冗余聯結詞結詞. 又注意到聯結詞又注意到聯結詞, 和和, 不再有冗余聯結不再有冗余聯結詞詞, 故故, 或或, 為最小聯結詞組為最小聯結詞組.但實際中為了使但實際中為了使用方便用方便, 命題公式常常同時包含命題公式常常同時包含, , , . c17例例1:試證試證是最小聯結詞組是最小聯結詞組. .證：證：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.試證試證，是最小聯結詞組是最小聯結詞組 證：證：P P Q Q(P(P Q)Q)(PQ)(PQ) P P Q Q(P)(P) Q QPQPQ小結小結:本節(jié)主要介紹了四種新的聯結詞本節(jié)主要介紹了四種新的聯結詞 及最及最小聯結詞組小聯結詞組. 作業(yè)作業(yè): 1. P29 (1), (2), (4) c,182. 預習預習1.7思考題思考題: 1. 何謂命題公式的何