离散数学(1.5重言式与蕴含式)

1、1,(Discrete Mathematics),2,第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implication),1.5.1 命题公式的分类 1.5.2 重言式(Tautology)与矛盾式 (contradictory)的性质 1.5.3 蕴含式( Implication),3,第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implication),1.5.1 命题公式的分类 复合命题 (compound propositions) 定义1.5.1 设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)的性质定理1.5.1:任何两个重言式的合取或析取,仍然是一重言式.（由幂等律立得） 证明:设A和B为两个重言式,则不论A和B的分量指派任何真值,总有A为T,B为T,故A B T,A B T 定理1.5.2:一个重言式(矛盾式),对同一分量都用任何合式公式置换,其

4、结果仍为一重言式(矛盾式). 证明: 由于重言式(矛盾式)的真值与对变元的赋值无关，故对同一变元以任何合式公式置换后，重言式(矛盾式)的真值仍永为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：当且仅当P

5、Q是一个重言式时，我们称“P蕴含Q”，并记作P Q.,7,第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implication),它们之间具有如下关系: 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）为假. 根据 ，所以 Q（PQ）P P21 表1-5.2给出了14个蕴含式, 它们都可以用上述方法加以推证.,9,第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implication),等价式与蕴含式的关系: 定理1.5.4: 设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),蕴含的性质: 设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),小结：本节介绍了命题公式的分类，重言式、矛盾式与蕴含式的概念及其性质，等价式与蕴涵式的关系。 重