離散數(shù)學(xué)第一章第三節(jié)

1、1第1-3講 蘊(yùn)含式1. 蘊(yùn)含式2.證明蘊(yùn)含式的方法3.證明蘊(yùn)含式的例子4.基本蘊(yùn)含式5.蘊(yùn)含式的性質(zhì)6.等價(jià)式和蘊(yùn)含式的聯(lián)系7.其它聯(lián)結(jié)詞8.最小聯(lián)結(jié)詞集9. 作業(yè)21、蘊(yùn)含式定義設(shè)、為命題公式，當(dāng)且僅當(dāng)是一個(gè)重言式，稱“蘊(yùn)含”，記作。n 對(duì)而言，稱為逆換式，為反換式，為逆反式。P Q0 0 1 1 1 1 1 10 1 1 0 1 0 0 11 0 0 1 0 1 1 01 1 0 0 1 1 1 1由上表中可以看出：由上表中可以看出：PQQP；QPPQ。n 如同等價(jià)如同等價(jià)一樣，一樣，也不是邏輯聯(lián)結(jié)詞。也不是邏輯聯(lián)結(jié)詞。僅僅表僅僅表示示是永真式。是永真式。32、證明蘊(yùn)含式的方法n分析：要

2、證分析：要證，即要證，即要證為重言式。對(duì)為重言式。對(duì)來(lái)說(shuō)，除為真、為假時(shí)，來(lái)說(shuō)，除為真、為假時(shí)，的真值為假外，其的真值為假外，其余情況余情況的真值皆為真。故要證的真值皆為真。故要證，只須對(duì)條，只須對(duì)條件命題件命題的前提指定其真值為真，若由此推出后的前提指定其真值為真，若由此推出后件亦為真，則件亦為真，則 為重言式。即為重言式。即成立。另一成立。另一方面，由方面，由 ，要證，要證為重言式，只為重言式，只需證需證 為重言式。即證為重言式。即證 為真時(shí)，為真時(shí)， 為真。為真。亦即證為假時(shí)，為假。亦即證為假時(shí)，為假。n 證明給定的蘊(yùn)含式的正確性的方法： .假定前件是真,若能推出后件是真,則此蘊(yùn)含式為真

3、。 .假設(shè)后件是假,若能推出前件亦假,則此蘊(yùn)含式為真。4例例 證明證明 () 證：設(shè)證：設(shè) () )為真，則為真，則 和和皆為真，那皆為真，那麼為假。再由麼為假。再由為真為真, ,得知應(yīng)為真。得知應(yīng)為真。 或證為：設(shè)為假（那麼或證為：設(shè)為假（那麼等值于），那麼，等值于），那麼， () )(F)F), ,即前件即前件為假。為假。例例 2 證明證明(PQ)(QR) (PQ)(QR) PRPR證：證：設(shè)設(shè)PR為假，則為真，為假，則為真，R為假。如為假。如Q為真，則為真，則QR為假；若為假；若Q為假，則為假，則PQ為假。為假。 故故(PQ)(QR)為假。為假。3、證明蘊(yùn)含式的例子54、基本蘊(yùn)含式(1)

4、 PQ(1) PQP ( PQP ( PQQ) Q) (2) P(2) PPQ ( QPQ ( QPQ) PQ) (3) (3) P PPQ PQ ( (因?yàn)橐驗(yàn)?P PPQPQPQ )PQ )(4) Q(4) QPQ PQ ( (因?yàn)橐驗(yàn)镼 QPQPQPQ )PQ )(5) (5) (PQ)(PQ)P P ( (因?yàn)橐驗(yàn)?(PQ)(PQ)PP Q QP)P)(6) (6) (PQ) (PQ) Q Q(7) P(PQ) (7) P(PQ) Q Q(8) (8) Q(PQ) Q(PQ) P P(9) (9) P(PQ) P(PQ) Q Q (10) (PQ)(QR) (10) (PQ)(QR)

5、PR PR (11) (PQ)(PR)(QR) (11) (PQ)(PR)(QR) R R( (設(shè)前件為真去證設(shè)前件為真去證) ) (12) (P(12) (PQ)(QQ)(QR) R) P PR R (設(shè)前件為真，分設(shè)前件為真，分P為真和為假兩種情況討論為真和為假兩種情況討論 ) 65、蘊(yùn)含式的性質(zhì)若且是重言式，則必為重言式。證明：因?yàn)樽C明：因?yàn)闉橛勒媸?，?dāng)為永真時(shí)，如果對(duì)為永真式，當(dāng)為永真時(shí)，如果對(duì)某一指派，的真值為假，則與某一指派，的真值為假，則與為永真相矛為永真相矛盾，故永真。盾，故永真。若，則。證明：因證明：因，所以，所以，為永真為永真式，那麼（式，那麼（）（）亦為永真式。另外，）亦

6、為永真式。另外，由由I I1010，可知，可知(AB)(BC) (AB)(BC) (AC) (AC)那麼由性質(zhì)那麼由性質(zhì)是永真式，亦即是永真式，亦即。75、蘊(yùn)含式的性質(zhì)（續(xù)） 若且，則。證明：設(shè)的真值為真，由于證明：設(shè)的真值為真，由于，則，則，的真值亦為真，從而的真值亦為真，從而的真值為真，故的真值為真，故為永真，從而為永真，從而。 若且，則。證明：因證明：因和和為永真，那麼為永真，那麼永真。而永真。而(AB)(CB)(AB)(CB)( ( AB)(AB)( CB) CB) ( ( AA C)B C)B (AC)B(AC)B (AC)B (AC)B。 故故為永真，從而為永真，從而。86、等價(jià)式

7、和蘊(yùn)含式的聯(lián)系n聯(lián)結(jié)詞聯(lián)結(jié)詞“”和和“”有如下關(guān)系：有如下關(guān)系： A AB B(A(A B)(B B)(BA)A)， 等價(jià)式和蘊(yùn)含式之間也有著緊密的聯(lián)系，如下所述。等價(jià)式和蘊(yùn)含式之間也有著緊密的聯(lián)系，如下所述。定理 設(shè)、為任意兩個(gè)命題公式，的充分必要條件是且。證明：若證明：若，則，則為重言式，因?yàn)闉橹匮允剑驗(yàn)椋ǎǎ?，故），故和和皆為真，皆為真，即即和和成立。成立?反之，若反之，若且且，則，則和和皆為皆為真，從而真，從而為真，即為真，即為重言式，亦即為重言式，亦即。97、其它聯(lián)結(jié)詞n給定個(gè)命題變?cè)疵}公式的形成規(guī)則可以得到給定個(gè)命題變?cè)?，按命題公式的形成規(guī)則可以得到無(wú)數(shù)多個(gè)命題公式。但

8、在這些無(wú)窮盡的命題公式之中，無(wú)數(shù)多個(gè)命題公式。但在這些無(wú)窮盡的命題公式之中，是否其真值都不同（指真值表最后一列不同）呢是否其真值都不同（指真值表最后一列不同）呢? ?或者或者說(shuō)它們都是彼此不等價(jià)的呢說(shuō)它們都是彼此不等價(jià)的呢? ?n回答是否定的回答是否定的! !這是因?yàn)閷?duì)個(gè)變?cè)荒苡羞@是因?yàn)閷?duì)個(gè)變?cè)荒苡? 2N N個(gè)不同的個(gè)不同的真值指派，在每一種真值指派下該命題公式只有真假真值指派，在每一種真值指派下該命題公式只有真假兩個(gè)可能，對(duì)于兩個(gè)可能，對(duì)于2 2N N個(gè)不同的真值指派就只有個(gè)不同的真值指派就只有2 2的的2 2N N個(gè)不個(gè)不同的真假二值的排列。一個(gè)排列相當(dāng)于某一個(gè)由個(gè)同的真假二值的排列

9、。一個(gè)排列相當(dāng)于某一個(gè)由個(gè)變?cè)傻拿}公式的真值表中的最后一列。變?cè)傻拿}公式的真值表中的最后一列。n 例如包含兩個(gè)命題變?cè)?、的不同命題公式只有例如包含兩個(gè)命題變?cè)?、的不同命題公式只有2 2的的2 22 2個(gè)，即個(gè)。其它命題公式必定與這個(gè)之個(gè)，即個(gè)。其它命題公式必定與這個(gè)之中的某一個(gè)有相同的真值。或者說(shuō)與這十六個(gè)命題之中的某一個(gè)有相同的真值?；蛘哒f(shuō)與這十六個(gè)命題之一等價(jià)。一等價(jià)。10 P Q 0 0 1 1 0 1 0 1 代表性的命題公式 1 0 0 0 0 F(永假式) 2 0 0 0 1 PQ 3 0 0 1 0 (PQ), 或 PQ 或 PQ 4 0 0 1 1 P 5 0 1

10、0 0 (QP) 或 PQ 或 QP 6 0 1 0 1 Q 7 0 1 1 0 (PQ), 或 PQ 8 0 1 1 1 PQ 9 1 0 0 0 (PQ), 或 PQ 或 PQ 10 1 0 0 1 PQ 或 PQ 11 1 0 1 0 Q 12 1 0 1 1 QP 或 PQ 13 1 1 0 0 P 14 1 1 0 1 PQ 或 PQ 15 1 1 1 0 (PQ), 或 PQ 或 PQ 16 1 1 1 1 T(永真式)包含兩個(gè)命題變?cè)狿和Q的不同命題公式117、其它聯(lián)結(jié)詞（續(xù)1）n從包含兩個(gè)命題變?cè)⒌牟煌}公式表不難看從包含兩個(gè)命題變?cè)?、的不同命題公式表不難看出，表示這個(gè)真值

11、不同的公式，如果每個(gè)公式只出，表示這個(gè)真值不同的公式，如果每個(gè)公式只準(zhǔn)用一個(gè)聯(lián)結(jié)詞，則定義九個(gè)聯(lián)結(jié)詞已足夠使用?；驕?zhǔn)用一個(gè)聯(lián)結(jié)詞，則定義九個(gè)聯(lián)結(jié)詞已足夠使用。或者說(shuō)對(duì)一個(gè)或兩個(gè)命題進(jìn)行運(yùn)算（連接），有九個(gè)運(yùn)者說(shuō)對(duì)一個(gè)或兩個(gè)命題進(jìn)行運(yùn)算（連接），有九個(gè)運(yùn)算符就足夠了。當(dāng)然，這并不是必須的。算符就足夠了。當(dāng)然，這并不是必須的。定義 設(shè)、是兩個(gè)命題公式，復(fù)合命題 稱為與的不可兼析取。 為真，當(dāng)且僅當(dāng)、真值不同。127、其它聯(lián)結(jié)詞（續(xù)2）n聯(lián)結(jié)詞有以下性質(zhì)：(1) P(1) P Q Q(P(PQ) Q) （雙條件否定）（雙條件否定）(2) P(2) P Q Q (P (P Q)(Q)( PQ)PQ)(

12、3) P(3) P Q Q Q Q P (4) (PP (4) (P Q)Q) R RP P (Q(Q R)R)(5) P(Q(5) P(Q R) R) (PQ) (PQ) (PR)(PR)(6) P(6) P P PF (7) FF (7) F P PP (8) TP (8) T P PP Pn 關(guān)于聯(lián)結(jié)詞的定理定理定理 設(shè)、是命題公式，如果設(shè)、是命題公式，如果 ，則，則 ， ，且，且 。證明：證明： 如果如果 ，則，則 = = 137、其它聯(lián)結(jié)詞（續(xù)3）定義 設(shè)、是兩個(gè)命題公式，復(fù)合命題設(shè)、是兩個(gè)命題公式，復(fù)合命題 稱為稱為與的條件否定，與的條件否定， 為真，當(dāng)且僅當(dāng)?shù)恼嬷禐檎?，為真，?dāng)且

13、僅當(dāng)?shù)恼嬷禐檎?，的真值為假。的真值為假?從上述定義可知，從上述定義可知，P Q(PQ)，故聯(lián)結(jié)詞，故聯(lián)結(jié)詞 稱為稱為“條件否條件否定定”。定義 設(shè)、是兩個(gè)命題公式，復(fù)合命題設(shè)、是兩個(gè)命題公式，復(fù)合命題稱為稱為與的與的“與非與非”。當(dāng)且僅當(dāng)和真值皆為真時(shí)，。當(dāng)且僅當(dāng)和真值皆為真時(shí)，為假，否則為假，否則為真。為真。 從上述定義可知，從上述定義可知， PQ(PQ)，故聯(lián)結(jié)詞，故聯(lián)結(jié)詞稱為稱為“與非與非”n 聯(lián)結(jié)詞聯(lián)結(jié)詞有以下性質(zhì)有以下性質(zhì)：(1) PP (PP) P(2) (PQ)(PQ) (PQ) PQ(3) (PP)(QQ) P Q ( P Q) PQ147、其它聯(lián)結(jié)詞（續(xù)4）定義4 設(shè)、是兩

14、個(gè)命題公式，復(fù)合命題設(shè)、是兩個(gè)命題公式，復(fù)合命題稱為稱為與的與的“或非或非”。當(dāng)且僅當(dāng)和真值皆為假時(shí)，。當(dāng)且僅當(dāng)和真值皆為假時(shí)，為真，否則為真，否則為假。為假。 從上述定義可知，從上述定義可知， PQ (PQ)，故聯(lián)結(jié)詞，故聯(lián)結(jié)詞稱為稱為“或非或非”。n 聯(lián)結(jié)詞聯(lián)結(jié)詞有以下性質(zhì)有以下性質(zhì)：(1) PP (1) PP (PP)(PP) P P(2) (PQ)(PQ) (2) (PQ)(PQ) (PQ)(PQ) PQPQ(3) (3) (PP)(QQ) (PP)(QQ) PP Q Q ( ( PP Q)Q)PQPQn 包含包含 、 、的復(fù)合命題，其合式公式的定義與的復(fù)合命題，其合式公式的定義與以前

15、的定義類似。以前的定義類似。158、最小聯(lián)結(jié)詞集n從基本恒等式可以發(fā)現(xiàn)，九個(gè)聯(lián)結(jié)詞并不都是必需的。從基本恒等式可以發(fā)現(xiàn)，九個(gè)聯(lián)結(jié)詞并不都是必需的。n 由由PQPQ( ( PP Q)Q)，PQPQ( ( PP Q)Q)可知，可知， 和和可以互相替代可以互相替代。 由由P PQ QPQPQ可知，可知，可用可用 和和替代替代； 由由PQ(PQ)(QP)可知，可知，可用可用和和替代替代； 所以所以 、可用可用 ，或或 ，代替代替。n由于由于P P Q Q(P(PQ)Q)，P P Q Q(P(PQ)Q)， PQPQ(PQ)(PQ)，PQPQ(PQ)(PQ)， 所以所以、可用可用 、替代。替代。結(jié)論：結(jié)論：任意命題公式都可由僅包含任意命題公式都可由僅包含 、或或 、的命題公式等價(jià)地表示出來(lái)的命題公式等價(jià)地表示出來(lái)。 168、最小聯(lián)結(jié)詞集(續(xù))n聯(lián)結(jié)詞組聯(lián)結(jié)詞組 ，或或 ，能否再歸結(jié)為能否再歸結(jié)為 、呢？呢？設(shè)設(shè) P(.(PR).) 對(duì)右邊所出現(xiàn)的變?cè)贾概烧嬷?，則右邊命題公式的對(duì)右邊所出現(xiàn)的變?cè)贾概烧嬷?，則右邊命題公式的真值必為，但此時(shí)左邊命題公式的真值為。這一矛真值必為，但此時(shí)左邊命題公式