《1.5重言式与蕴含式》由会员分享，可在线阅读，更多相关《1.5重言式与蕴含式（14页珍藏版）》请在金锄头文库上搜索。
1、离散数学离散数学(Discrete Mathematics)医学信息工程系医学信息工程系7/22/20241第第1章章 命题逻辑命题逻辑（Propositional LogicPropositional Logic） 1.5重言式与重言式与蕴含蕴含式式(Tautology and Implication)(Tautology and Implication)1.5.1 命题公式的分类命题公式的分类1.5.2 重言式与矛盾式的性质重言式与矛盾式的性质1.5.3 蕴含式蕴含式7/22/2024复合命题复合命题(compound propositions)定义定义1.5.1 设设A为任一命题公式，为
2、任一命题公式，（1）若若A在在其其各各种种赋赋值值下下的的取取值值均均为为真真，则则称称A是是重重言式言式或或永真式永真式, 记为记为T或或1。（2）若若A在在其其各各种种赋赋值值下下的的取取值值均均为为假假，则则称称A是是矛矛盾式盾式或或永假式永假式, 记为记为F或或0。（ 3） 若若 A不不 是是 矛矛 盾盾 式式 则则 称称 A为为 可可 满满 足足 式式(satisfiable)。注注: 由由定定义义可可知知,重重言言式式一一定定是是可可满足式满足式,反之不真反之不真. 1.5.1 1.5.1 命题公式的分类命题公式的分类7/22/2024 判别命题公式的类型有两种方法判别命题公式的类
3、型有两种方法: 真值表法和等值真值表法和等值演算法演算法. 等值演算法等值演算法是将所给命题公式通过等值演算化为最是将所给命题公式通过等值演算化为最简单的形式简单的形式, 然后再进行判别然后再进行判别.例例1.判别下列命题公式的类型判别下列命题公式的类型.(1). Q(PQ)P)(2). (PP) (QQ)R(3). (P Q)P(重言式重言式)(矛盾式矛盾式)(可满足式可满足式)7/22/2024定定理理1.5.1:任任何何两两个个重重言言式式的的合合取取或或析析取取,仍仍然然是是一一重言式重言式.（由幂等律立得）（由幂等律立得）n证明证明:设设A和和B为两个重言式为两个重言式,则不论则不论
4、A和和B的分量指的分量指派任何真值派任何真值,总有总有A为为T,B为为T,故故A B T,A T,A B B T Tn定理定理1.5.2:1.5.2:一个重言式一个重言式( (矛盾式矛盾式), ,对同一分量都用对同一分量都用任何合式公式置换任何合式公式置换, ,其结果仍为一重言式其结果仍为一重言式( (矛盾式矛盾式). .n证明证明: 由于由于重言式重言式( (矛盾式矛盾式)的真值与对变元的赋值的真值与对变元的赋值无关，故对同一变元以任何无关，故对同一变元以任何合式公式置换后，重言合式公式置换后，重言式式( (矛盾式矛盾式)的真值仍永为的真值仍永为T（F）。）。1.5.2 1.5.2 重言式与
5、矛盾式重言式与矛盾式7/22/2024n定理定理1.5.3： A,B是两个命题公式，是两个命题公式，A B的充要条件是的充要条件是A B为重言式。为重言式。证明证明: : 若若A AB B为重言式，则为重言式，则A AB B永为永为T T，即，即A A，B B的真值表相同，所以的真值表相同，所以A AB B。 反之，反之，若若A A B B，则，则A A，B B真值表相同，真值表相同， 所以所以A AB B永为永为T T，所以所以A AB B为重言式。为重言式。7/22/2024n它们之间具有如下关系它们之间具有如下关系: PQ Q P 由由P21 表表1-5.1 QP P Q 可以得出可以得
6、出n因此因此, 要证明要证明P Q有三种方法有三种方法:n1)1)真值表法真值表法: :即列出即列出PQ的的真值表真值表, ,观察其是否永为真。观察其是否永为真。n2)2)直接证法直接证法: :假定前件假定前件P P是真，推出后件是真，推出后件Q Q是真。是真。n3)3)间接证法间接证法: :假定后件是假，推出前件是假假定后件是假，推出前件是假, ,即证即证 Q P原原命题命题逆换式逆换式反换式反换式逆反式逆反式PQQP P Q Q P1.5.3 1.5.3 永真蕴含式永真蕴含式( ( Implication)Implication)定义定义1.5.2：当且仅当：当且仅当P Q是一个重言式时，
7、我们是一个重言式时，我们称称“P永真蕴含永真蕴含Q”，并记作，并记作P Q.7/22/2024例例: : 证明证明Q Q （PQPQ）P P1) 1) 法法1 1：真值表：真值表2) 2) 法法2 2：若：若 Q Q ( (PQ)PQ)为真，则为真，则 Q Q，PQPQ为真，为真， 所以所以Q Q为假，为假，P P为假，所以为假，所以P P为真。为真。3) 3) 法法3 3：若：若P P为假，则为假，则P P为真，再分二种情况：为真，再分二种情况： 若若Q Q为真，则为真，则Q Q为假为假, ,从而从而Q Q （PQPQ） 为假为假. .若若Q Q为假，则为假，则PQPQ为假，则为假，则Q Q
8、 （PQPQ）为假为假. .根据根据 ，所以，所以 Q Q （PQPQ）P P7/22/2024n基本永真蕴含式基本永真蕴含式7/22/20247/22/2024n等价式与蕴含式的关系等价式与蕴含式的关系:n定理定理1.5.4:1.5.4: 设设P,QP,Q为为任意两个命题公式任意两个命题公式,P,PQ Q的充的充要条件为要条件为P PQ Q且且Q QP.P.n证：若证：若P PQ Q，则，则P PQ Q为永真式为永真式 因为因为 P PQ Q （PQPQ） （QPQP） 所以所以 PQPQ，QPQP为永真式为永真式, ,从而从而 P PQ Q，Q QP.P. 反之，若反之，若P PQ Q，Q
9、 QP P，则，则PQPQ，QPQP为永真式为永真式, , 所以所以（PQPQ） （QPQP）为永真式，为永真式， 从而从而 P PQ Q为永真式，即为永真式，即P PQ.Q.7/22/2024n蕴含的性质蕴含的性质:n设设A A，B B，C C为任意为任意wffwff, ,1) 1) 若若A AB B，且，且A A为永真式，则为永真式，则B B必为永真式必为永真式. .2) 2) 若若A AB B，B BC C，则，则A AC.C.3) 3) 若若A AB B，A AC C，则，则A AB B C.C.4) 4) 若若A AB B且且C CB B，则，则A A C CB.B.证：证：1)1)
10、因为因为 ABAB，A A永为永为T,T,所以所以B B必永为必永为T.T. 2) 2)由由假言三段论假言三段论（AB)AB) ( (BCBC）AC,AC,所以若所以若A AB B，B BC C，则（则（AB)AB) ( (BCBC）永为永为T,T,从而从而ACAC永永 为为T, T, 故故A AC.C. 7/22/20243) 3) （ABAB） （ACAC） （A A B B） （A A C C） A A （B B C C） ABAB C C4) 4) （ABAB） （CBCB） （A A B B） （C C B B） （A A CC） B B （A A C C） B B A A CBCB7/22/2024n小小结结：本本节节介介绍绍了了命命题题公公式式的的分分类类，重重言言式式、矛矛盾盾式式与与蕴蕴含含式式的的概概念念及及其其性性质质，等等价价式式与与蕴蕴涵式的关系。涵式的关系。n重点掌握重点掌握: （1 1）用等值演算法判别命题公式的类型。）用等值演算法判别命题公式的类型。 （2 2）重言式、矛盾式与蕴涵式的性质。）重言式、矛盾式与蕴涵式的性质。 （3 3）等价式与蕴涵式的关系。）等价式与蕴涵式的关系。7/22/2024
