《重言式与蕴含式》PPT课件

《《重言式与蕴含式》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学(DiscreteMathematics)医学信息工程系8/6/20211第1章命题逻辑（PropositionalLogic）1.5重言式与蕴含式(TautologyandImplication)1.5.1命题公式的分类1.5.2重言式与矛盾式的性质1.5.3蕴含式8/6/2021复合命题(compoundpropositions)定义1.5.1设A为任一命题公式，（1）若A在其各种赋值下的取值均为真，则称A是重言式或永真式,记为T或1。（2）若A在其各种赋值下的取值均为假，则称A是矛盾式或永假式,记为F或0。（3）若A不是矛盾式则称A为可满足式(sat

2、isfiable)。注:由定义可知,重言式一定是可满足式,反之不真.1.5.1命题公式的分类8/6/2021判别命题公式的类型有两种方法:真值表法和等值演算法.等值演算法是将所给命题公式通过等值演算化为最简单的形式,然后再进行判别.例1.判别下列命题公式的类型.(1).Q∨┓((┓P∨Q)∧P)(2).(P∨┓P)(Q∧┓Q)∧R(3).(PQ)∧┓P(重言式)(矛盾式)(可满足式)8/6/2021定理1.5.1:任何两个重言式的合取或析取,仍然是一重言式.（由幂等律立得）证明:设A和B为两个重言式,则不论A和B的分量指派任何真值,总有A为T,B为T,故A∧B

3、T,A∨BT定理1.5.2:一个重言式(矛盾式),对同一分量都用任何合式公式置换,其结果仍为一重言式(矛盾式).证明:由于重言式(矛盾式)的真值与对变元的赋值无关，故对同一变元以任何合式公式置换后，重言式(矛盾式)的真值仍永为T（F）。1.5.2重言式与矛盾式8/6/2021定理1.5.3：A,B是两个命题公式，AB的充要条件是AB为重言式。证明:若AB为重言式，则AB永为T，即A，B的真值表相同，所以AB。反之，若AB，则A，B真值表相同，所以AB永为T，所以AB为重言式。8/6/2021它们之间具有如下关系:PQQP由P21表1-

4、5.1QPPQ可以得出因此,要证明PQ有三种方法:1)真值表法:即列出PQ的真值表,观察其是否永为真。2)直接证法:假定前件P是真，推出后件Q是真。3)间接证法:假定后件是假，推出前件是假,即证QP原命题逆换式反换式逆反式PQQPPQQP1.5.3永真蕴含式(Implication)定义1.5.2：当且仅当PQ是一个重言式时，我们称“P永真蕴含Q”，并记作PQ.8/6/2021例:证明┐Q（P→Q）┐P1)法1：真值表2)法2：若┐Q(P→Q)为真，则┐Q，P→Q为真，所以Q为假，P为假，所以┐P为真。3)法3：若┐P

5、为假，则P为真，再分二种情况：①若Q为真，则┐Q为假,从而┐Q（P→Q）为假.②若Q为假，则P→Q为假，则┐Q（P→Q）为假.根据①②，所以┐Q（P→Q）┐P8/6/2021基本永真蕴含式8/6/20218/6/2021等价式与蕴含式的关系:定理1.5.4:设P,Q为任意两个命题公式,PQ的充要条件为PQ且QP.证：若PQ，则PQ为永真式因为PQ（P→Q）（Q→P）所以P→Q，Q→P为永真式,从而PQ，QP.反之，若PQ，QP，则P→Q，Q→P为永真式,所以（P→Q）（Q→P）为永真式，从而PQ为永真式，即PQ.8/6/202

6、1蕴含的性质:设A，B，C为任意wff,1)若AB，且A为永真式，则B必为永真式.2)若AB，BC，则AC.3)若AB，AC，则ABC.4)若AB且CB，则ACB.证：1)因为A→B，A永为T,所以B必永为T.2)由假言三段论（A→B)(B→C）A→C,所以若AB，BC，则（A→B)(B→C）永为T,从而A→C永为T,故AC.8/6/20213)（A→B）（A→C）（┐AB）（┐AC）┐A（BC）A→BC4)（A→B）（C→B）（┐AB）（┐CB）（┐A┐C）B┐（AC）BAC→B8

7、/6/2021小结：本节介绍了命题公式的分类，重言式、矛盾式与蕴含式的概念及其性质，等价式与蕴涵式的关系。重点掌握:（1）用等值演算法判别命题公式的类型。（2）重言式、矛盾式与蕴涵式的性质。（3）等价式与蕴涵式的关系。8/6/2021