1-5重言式與蘊(yùn)含式.ppt

1、1-5重言式與蘊(yùn)含式,1-5.1重言式（tautology）,定義1-5.1 重言式: 給定一個(gè)命題公式，若無論對分量作怎樣的指派，其對應(yīng)的真值永為T，則稱該命題公式為重言式或永真公式。,1-5重言式與蘊(yùn)含式,1-5.1重言式（tautology）,定義1-5.2 矛盾式: 給定一個(gè)命題公式，若無論對分量作怎樣的指派，其對應(yīng)的真值永為F，則稱該命題公式為矛盾式或永假公式。,1-5.1重言式（tautology）,性質(zhì)1-5.1 若A和B均為重言式，則AB及AB也為重言式。 性質(zhì)1-5.2 若A是一個(gè)重言式，則對A的同一個(gè)分量都用另外一個(gè)合式公式置換，所得公式仍為重言式。 例：(PQ) (PQ)

2、 是重言式(P14) P用RT 替換，還是重言式。,1-5.1重言式（tautology）,定理1-5.3 設(shè)A、B為兩個(gè)命題，AB當(dāng)且僅當(dāng)A B 為一個(gè)重言式。,證明：若AB，則A、B有相同的真值， 由雙條件定義 A B 永為T。,上例是重言式，則(PQ) (PQ) 德.摩根律得證,若A B為重言式，則A B永為T， 故A、B有相同的真值，即AB。,1-5.2蘊(yùn)含式(implication),定義1-5.3 蘊(yùn)含式當(dāng)且僅當(dāng)是一個(gè)重言式時(shí)，我們稱“蘊(yùn)含”，并記作。 對于來說，逆換式為： 反換式為： 逆反式為： 有與不等價(jià)， ， （命題與逆否命題等價(jià)）,1-5.2蘊(yùn)含式(implication)

3、,證明AB的方法： 要證AB，即證AB是重言式，或證其逆反式B A是重言式即可。 要證AB是重言式： （推理法） （1）假設(shè)A為T時(shí)，說明B也為T。 因?yàn)楫?dāng)A為T，B為F時(shí)，AB為F 或（2）假設(shè)B為F時(shí)，說明A也為F。 因?yàn)榭傻肂為T時(shí)，A也為T，即 B A是重言式 （此方法是命題邏輯中的一個(gè)基本證明方法） 可使用表1-5.2的蘊(yùn)含式,1-5.2蘊(yùn)含式(implication),例：n是整數(shù)，證明若n2是奇數(shù)，n也是奇數(shù)。 證明：（反證法）若n是偶數(shù)，n2也是偶數(shù)。 設(shè)n=2k，k是一個(gè)整數(shù)， 則n2=(2k)2=2(2k2), 所以n2是偶數(shù)。 所以原命題得證。,1-5.2蘊(yùn)含式(impl

4、ication),例：見P21 例1 課上做表1-5.2的11式 看表1-5.2，記住常用的蘊(yùn)含式。,1-5.2蘊(yùn)含式(implication),定理1-5.4：設(shè)P、Q為任意兩個(gè)命題公式，PQ的充分必要條件是PQ且QP 。 證明：由定理 1-5.3 ，P Q，則P Q為重言式，因?yàn)橛杀?-4.7 P Q (PQ)(QP)，故(PQ)為T且 (Q P)為T，即PQ且QP 成立。 反之，若PQ且QP 成立，則(PQ)為T且 (QP)為T，因此P Q為T， P Q為重言式，即PQ。 這個(gè)定理也可作為兩個(gè)公式等價(jià)的定義。,1-5.3蘊(yùn)含的性質(zhì),*（1）設(shè)A、B、C是合式公式，若A B且A是重言式，則

5、B必是重言式。 *（2）若A B，B C，則A C（傳遞性） *（3）若A B，A C ，則A BC （4）若A B，C B ，則AC B 以上性質(zhì)在推理中常用。 特別說明：如果推導(dǎo)蘊(yùn)含，則可以用等價(jià)的式子替換，因?yàn)椤暗葍r(jià)”比“蘊(yùn)含”強(qiáng)，好比“大于等于”與“等于”的關(guān)系。,作業(yè)（1-5）,P23. (1) b) c) (2) b) 說明： （6）（8）先不做，因?yàn)橛行缘诎斯?jié)講。,1-6其它聯(lián)結(jié)詞,定義1-6.1不可兼析取(Exclusive OR)： 設(shè)P和Q是兩個(gè)命題公式，復(fù)合命題PQ稱作P和Q的不可兼析取。 PQ的真值為T，當(dāng)且僅當(dāng)P與Q的真值不相同時(shí)為T，否則， PQ的真值為F。真值表

6、如下：,1-6.1 不可兼析取的性質(zhì),設(shè)P、Q、R為命題公式，則有 （1）P Q Q P 交換性 （2）（PQ）R P（QR） 結(jié)合性 （3）P(QR)(PQ)(PR) 分配性 （4） PQ （PQ ）（PQ） （5） PQ （P Q）由定義得到 （6） PP F，F(xiàn)P P，TP P,1-6.2 條件否定,定義1-6.2 條件否定 設(shè)P和Q是兩個(gè)命題公式，復(fù)合命題PQ稱作P和Q的條件否定。 PQ的真值為T，當(dāng)且僅當(dāng)P的真值為T，Q的真值為F，否則， PQ的真值為F。真值表如下：,C,C,C,C,1-6.2 條件否定的性質(zhì),由定義可知： P Q （P Q）,C,1-6.3 與非,定義1-6.3

7、與非 設(shè)P和Q是兩個(gè)命題公式，復(fù)合命題P Q稱作P和Q的“與非”。當(dāng)且僅當(dāng)P和Q的真值都為T時(shí)， P Q的真值為 F ，否則P Q的真值都為T 。真值表如下：,1-6.3 與非的性質(zhì),（1）P Q （PQ） （2）P P （P P）P （3）（P Q）（P Q）（P Q） P Q （4）（P P）（ Q Q）P Q （PQ）PQ,1-6.4 或非,定義1-6.4 或非 設(shè)P和Q是兩個(gè)命題公式，復(fù)合命題P Q稱作P和Q的“或非”。當(dāng)且僅當(dāng)P和Q的真值都為F 時(shí)，PQ的真值為T ，否則， PQ的真值都為F。真值表如下：,1-6.4 或非的性質(zhì),（1）P Q （PQ） （2）P P （PP）P （3）（PQ）（PQ）（PQ） PQ （4）（PP）（ Q Q）P Q （P Q） P Q,1-6.5 聯(lián)結(jié)詞是否夠用,每種聯(lián)結(jié)詞對應(yīng)一種四個(gè)T或F的組合，總共可以有24=16種組合，似乎需要16種聯(lián)結(jié)詞才夠用。 事實(shí)上，我們定義的這九種就夠用了。 請看P27 表1-6.5,1-6.6 最小聯(lián)結(jié)詞組,最小聯(lián)結(jié)詞組應(yīng)為，或，亦可以為或。 證明：1）用這些聯(lián)結(jié)詞組可以表示其它的聯(lián)結(jié)詞。 2）用，以及，不能表示其它的聯(lián)結(jié)詞。 不能表示 ， ， 因?yàn)楹卸?lián)結(jié)詞的命題公式不能用僅含一元聯(lián)結(jié)詞的命題公式等價(jià)代換。