重言式与蕴含式.ppt

2020 2 8 1 离散数学 DiscreteMathematics 医学信息工程系 2020 2 8 第1章命题逻辑 PropositionalLogic 1 5重言式与蕴含式 TautologyandImplication 1 5 1命题公式的分类1 5 2重言式与矛盾式的性质1 5 3蕴含式 2020 2 8 复合命题 compoundpropositions 定义1 5 1设A为任一命题公式 1 若A在其各种赋值下的取值均为真 则称A是重言式或永真式 记为T或1 2 若A在其各种赋值下的取值均为假 则称A是矛盾式或永假式 记为F或0 3 若A不是矛盾式则称A为可满足式 satisfiable 注 由定义可知 重言式一定是可满足式 反之不真 1 5 1命题公式的分类 2020 2 8 判别命题公式的类型有两种方法 真值表法和等值演算法 等值演算法是将所给命题公式通过等值演算化为最简单的形式 然后再进行判别 例1 判别下列命题公式的类型 1 Q P Q P 2 P P Q Q R 3 P Q P 重言式 矛盾式 可满足式 2020 2 8 定理1 5 1 任何两个重言式的合取或析取 仍然是一重言式 由幂等律立得 证明 设A和B为两个重言式 则不论A和B的分量指派任何真值 总有A为T B为T 故A B T A B T定理1 5 2 一个重言式 矛盾式 对同一分量都用任何合式公式置换 其结果仍为一重言式 矛盾式 证明 由于重言式 矛盾式 的真值与对变元的赋值无关 故对同一变元以任何合式公式置换后 重言式 矛盾式 的真值仍永为T F 1 5 2重言式与矛盾式 2020 2 8 定理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为重言式 2020 2 8 它们之间具有如下关系 P Q Q P由P21表1 5 1Q P P Q可以得出因此 要证明P Q有三种方法 1 真值表法 即列出P Q的真值表 观察其是否永为真 2 直接证法 假定前件P是真 推出后件Q是真 3 间接证法 假定后件是假 推出前件是假 即证 Q P 1 5 3永真蕴含式 Implication 定义1 5 2 当且仅当P Q是一个重言式时 我们称 P永真蕴含Q 并记作P Q 2020 2 8 例 证明 Q P Q P1 法1 真值表2 法2 若 Q P Q 为真 则 Q P Q为真 所以Q为假 P为假 所以 P为真 3 法3 若 P为假 则P为真 再分二种情况 若Q为真 则 Q为假 从而 Q P Q 为假 若Q为假 则P Q为假 则 Q P Q 为假 根据 所以 Q P Q P 2020 2 8 基本永真蕴含式 2020 2 8 2020 2 8 等价式与蕴含式的关系 定理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 2020 2 8 蕴含的性质 设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 2020 2 8 3 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 B 2020 2 8 小结 本节介绍了命题公式