1、1,(Discrete Mathematics),2,第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊含式(Tautology and Implication),1.5.1 命題公式的分類 1.5.2 重言式(Tautology)與矛盾式 (contradictory)的性質(zhì) 1.5.3 蘊含式( Implication),3,第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊含式(Tautology and Implication),1.5.1 命題公式的分類 復(fù)合命題 (compound propositions) 定義1.5.1 設(shè)A

2、為任一命題公式， （1）若A在其各種賦值下的取值均為真，則稱A是重言式或永真式, 記為T或1。 （2）若A在其各種賦值下的取值均為假，則稱A是矛盾式或永假式, 記為F或0。 （3）若A不是矛盾式則稱A為可滿足式(satisfiable)。注: 由定義可知,重言式一定是可滿足式,反之不真.,4,第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊含式(Tautology and Implication),判別命題公式的類型有兩種方法: 真值表法和等值 演算法. 等值演算法是將所給命題公式通過等值演算化為最 簡單的形式, 然后再進行判別. 例1.判別下列命題公式的類型. (

3、1). Q(PQ)P) (重言式) (2). (PP) (QQ)R (矛盾式) (3). (P Q)P. (可滿足式),5,第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊含式(Tautology and Implication),1.5.2 重言式(Tautology)與矛盾式(contradictory)的性質(zhì)定理1.5.1:任何兩個重言式的合取或析取,仍然是一重言式.（由冪等律立得） 證明:設(shè)A和B為兩個重言式,則不論A和B的分量指派任何真值,總有A為T,B為T,故A B T,A B T 定理1.5.2:一個重言式(矛盾式),對同一分量都用任何合式公式置換,其

4、結(jié)果仍為一重言式(矛盾式). 證明: 由于重言式(矛盾式)的真值與對變元的賦值無關(guān)，故對同一變元以任何合式公式置換后，重言式(矛盾式)的真值仍永為T（F）。,6,第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊含式(Tautology and Implication),定理1.5.3： A,B是兩個命題公式，A B的充要條件是A B為重言式。 證明: 若AB為重言式，則AB永為T，即A，B的真 值表相同，所以AB。 反之，若A B，則A，B真值表相同， 所以 AB永為T，所以AB為重言式。 1.5.3 蘊含式( Implication) 定義1.5.2：當(dāng)且僅當(dāng)P

5、Q是一個重言式時，我們稱“P蘊含Q”，并記作P Q.,7,第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊含式(Tautology and Implication),它們之間具有如下關(guān)系: PQ Q P 由P21 表1-5.1 QP P Q 可以得出 因此, 要證明P Q有三種方法: 1)真值表法:即列出PQ的真值表,觀察其是否為永真。 2)直接證法:假定前件P是真，推出后件Q是真。 3)間接證法:假定后件是假，推出前件是假,即證 Q P 。,8,第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊含式(Tautology and Impli

6、cation),例: 證明Q（PQ）P 1) 法1：真值表 2) 法2：若 Q(PQ)為真，則 Q，PQ為真， 所以Q為假，P為假，所以P為真。 3) 法3：若P為假，則P為真，再分二種情況： 若Q為真，則Q為假,從而Q（PQ） 為假. 若Q為假，則PQ為假，則Q（PQ）為假. 根據(jù) ，所以 Q（PQ）P P21 表1-5.2給出了14個蘊含式, 它們都可以用上述方法加以推證.,9,第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊含式(Tautology and Implication),等價式與蘊含式的關(guān)系: 定理1.5.4: 設(shè)P,Q為任意兩個命題公式,PQ的充

7、要條件為PQ且QP. 證：若PQ，則PQ為永真式 因為 PQ （PQ）（QP） 所以 PQ，QP為永真式,從而 PQ，QP. 反之，若PQ，QP，則PQ，QP為永真式, 所以（PQ）（QP）為永真式， 從而 PQ為永真式，即PQ.,10,第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊含式(Tautology and Implication),蘊含的性質(zhì): 設(shè)A，B，C為任意wff, 1) 若AB，且A為永真式，則B必為永真式. 2) 若AB，BC，則AC. 3) 若AB，AC，則ABC. 4) 若AB且CB，則ACB. 證：1)因為AB，A永為T,所以B必永為T.

8、 2)由I11 （AB)(BC）AC,所以若AB， BC，則（AB)(BC）永為T,從而AC永 為T, 故AC.,11,第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊含式(Tautology and Implication),3) （AB）（AC） （AB）（AC） A（BC） ABC 4) （AB）（CB） （AB）（CB） （AC）B （AC）B ACB,12,第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊含式(Tautology and Implication),小結(jié)：本節(jié)介紹了命題公式的分類，重言式、矛盾式與蘊含式的概念及其性質(zhì)，等價式與蘊涵式的關(guān)系。 重