《左孝凌离散数学课件1.5重言式与蕴含式》由会员分享，可在线阅读，更多相关《左孝凌离散数学课件1.5重言式与蕴含式（24页珍藏版）》请在金锄头文库上搜索。
1、1离散数学离散数学( (Discrete MathematicsDiscrete Mathematics) )第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic）1.51.5重言重言 式与式与蕴含式式(Tautology and Implication)(Tautology and Implication)一、命题公式的分类二、蕴含式三、蕴含式的性质3第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic）1.51.5重言式重言式 与与蕴含式式(Tautology and Impli
2、cation)(Tautology and Implication)1.5.1 命题公式的分类 1.5.2 重言式与矛盾式的性质 1.5.3 蕴含蕴含式式4第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic）1.51.5重言式重言式 与蕴含式与蕴含式(Tautology and Implication)(Tautology and Implication)1.5.1 命题公式的分类定义1.5.1 设A为任一命题公式， （1）若A在其各种赋值下的取值均为真，则称A是重言 式或永真式, 记为T或1。 （2）若A在其各种赋值下的取值均为假，则
3、称A是矛盾 式或永假式, 记为F或0。 （3）若A不是矛盾式则称A为可满足式(satisfiable)。注: 由定义可知,重言式一定是可满足式,反之不真.5第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic）1.51.5重言式重言式 与蕴含式与蕴含式(Tautology and Implication)(Tautology and Implication)判别命题公式的类型有两种方法: 真值表法和等值 演算法.等值演算法是将所给命题公式通过等值演算化为最 简单的形式, 然后再进行判别. 例1.判别下列命题公式的类型. (1). Q(PQ
4、)P) (重言式) (2). (PP) (QQ)R (矛盾式) (3). (P Q)P. (可满足式)6第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic）1.51.5重言式重言式 与蕴含式与蕴含式(Tautology and Implication)(Tautology and Implication)1.5.2 重言式与矛盾式的性质 定理1.5.1: 任何两个重言式的合取或析取,仍然是一重言式.（由幂等律立得 ）证明:设A和B为两个重言式,则不论A和B的分量指派任何真值,总有A为T,B为 T,故A B T,A B T 定理1.5.2
5、: 一个重言式(矛盾式),对同一分量都用任何合式公式置换,其结果 仍为一重言式(矛盾式).证明: 由于重言式(矛盾式)的真值与对变元的赋值无关，故对同一变元以 任何合式公式置换后，重言式(矛盾式)的真值仍永为T（F）。举例例题1 证明(PS)R)V(PS)R)为重言式。证明：因为PVPT（否定律，）为重言式，根据定理1.5.2如以(PS)R)置换P即得(PS)R)V(PS)R) T8第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic）1.51.5重言式重言式 与蕴含式与蕴含式(Tautology and Implication)(Tau
6、tology and Implication) 定理1.5.3： A,B是两个命题公式，A B的充要条件是A B为 重言式。证明: 若AB为重言式，则AB永为T，即A，B的真值表相同，所以AB。反之，若A B，则A，B真值表相同， 所以AB永为T，所以AB为重言式。举例例2 ：证明（Q P） （ PQ ） （QQ） ） P T T 证明： 直接证明该式T T 很长很长 根据定理根据定理1.5.31.5.3，只需证，只需证 （Q P） （ PQ ） （QQ） ） P 左 （ Q P） （ P Q ） T （ Q P） （ Q P ） P P （ Q Q） P F P小结： 证明A B B的方法的
7、方法u按定义。即根据真值表，二者具有相同真值 u要证明 A B T T 只需证明只需证明A B 即可，反之亦然即可，反之亦然 u用等价代换推导法A B B1.5.3 蕴含式蕴含式( ( Implication)Implication)（一（一类类类类特殊的重言式）特殊的重言式）定义1.5.2：当且仅当P Q是一个重言式时，我们称“P蕴含Q”， 并记作P Q.例如：（P Q ）Q （P Q ） Q P （ Q Q） P T T T，故，故（P Q ） Q第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic）1.51.5重言重言 式与蕴含式式
8、与蕴含式(Tautology and Implication)(Tautology and Implication)13第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic）1.51.5重言式重言式 与蕴含式与蕴含式(Tautology and Implication)(Tautology and Implication) 它们之间具有如下关系:PQ Q P 由P21 表1-5.1QP P Q 可以得出 因此, 要证明P Q有四种方法: 1)真值表法:即列出PQ的真值表,观察其是否为永真。 2)直接证法:假定前件P是真，推出后件Q是真。
9、3)间接证法:假定后件是假，推出前件是假,即证 Q P 。 4）等价代换法：即利用等价代换证明PQ为永真原命题逆换式反换式逆反式 PQQP P Q Q P直接证法： 要想让P Q 为永真，那 么当P为真时 ，Q只能为真间接证法：要 想让P Q为永 真，那么当Q 为假时，只能 P只能为假15第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic）1.51.5重言式重言式 与蕴含式与蕴含式(Tautology and Implication)(Tautology and Implication)例: 证明Q（PQ）P 1) 法1：真值表 即证明
10、（Q（PQ） P为永真 2) 法2：若 Q(PQ)为真，则 Q，PQ均为真，所以Q为假，P为假，所以P为真。 3) 法3：若P为假，则P为真，再分二种情况：若Q为真，则Q为假, （PQ）为真从而Q（PQ）为假. 若Q为假，则Q为真，PQ为假，从而Q（PQ）为假. 根据 ，所以 Q（PQ）P 4）法4： （Q（PQ） P （Q（ P Q） P（Q （P Q） P（Q P） （Q Q ） P（Q P） P Q T T P21 表 1-5.2 常用的蕴含重言式 PQ P1PQ Q2P PQ3P PQ4Q PQ5(PQ） P6(PQ） Q7P(PQ） Q8Q(PQ） P9P(PQ） Q10(PQ）(Q
11、R） PR11(PQ）(PR）(QR） R12(PQ）(RS） (PR)(QS)13(P Q)(Q R) (P R)1418第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic）1.51.5重言重言 式与蕴含式式与蕴含式(Tautology and Implication)(Tautology and Implication) 定理1.5.4: 设P,Q为任意两个命题公式,PQ的充要条 件为PQ且QP.证：若PQ，则PQ为永真式因为 PQ （PQ）（QP）所以 PQ，QP为永真式,从而 PQ，QP.反之，若PQ，QP，则PQ，QP为永真式
12、,所以（PQ）（QP）为永真式，从而 PQ为永真式，即PQ.等价式与蕴含式的关系:19第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic）1.51.5重言重言 式与蕴含式式与蕴含式(Tautology and Implication)(Tautology and Implication)蕴含的性质: 设A，B，C为任意命题公式（合式公式） 1)A A； 2）若A B，则B A 3）若A B，B C，则A C 4）若AB，且A为永真式，则B必为永真式. 5) 若AB，BC，则AC. 6) 若AB，AC，则ABC. 7) 若AB，CB，则A
13、CB. 证：4)因为AB，A永为T,所以B必永为T.5)若AB，BC，则（AB)为永真且(BC）为永真所以 （AB)(BC）永为T,由I11 （AB)(BC）AC,根据4）所以从而AC永为T, 故AC.20第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic）1.51.5重言重言 式与蕴含式式与蕴含式(Tautology and Implication)(Tautology and Implication)6) 由已知，（AB)(AC）永为T （AB）（AC） （AB）（AC） A（BC） A（BC）为永真 7) 由已知，（AB）（CB）
14、为永真 （AB）（CB） （AB）（CB） （AC）B （AC）B （AC）B为永真21第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic）1.51.5重言重言 式与蕴含式式与蕴含式(Tautology and Implication)(Tautology and Implication) 小结：本节介绍了命题公式的分类，重言式、矛盾式与蕴 含式的概念及其性质，等价式与蕴涵式的关系。 重点掌握:（1）用等值演算法判别命题公式的类型。（2）重言式、矛盾式与蕴涵式的性质。（3）等价式与蕴涵式的关系。 作业: P23 (1)c,d ,(2) a ,(8). 预习:1.6 思考题:1) 为什么要引入联结词? 2) 什么是最小联结词组?小小 结结1.真值表指派 2.真值表及其构成方法 3.等价公式及等价置换 4.命题公式的分类 5.蕴含式判定及其性质（1）若A在其各种赋值下的取值均为真，则称A是重言式或永真式, 记 为T或1。 （2）若A在
