离散数学教学课件-ch2.pptVIP

第二章 命题逻辑等值演算 主要内容 等值式与基本的等值式 等值演算与置换规则 析取范式与合取范式，主析取范式与主合取范式 联结词完备集 2.1 等值式 若公式A与B有相同的真值表，则(A?B)为重言式. 反之亦然. 定义 设A,B是两个命题公式, 若A,B构成的等价式A?B为重言式, 则称A与B等值, 记作A?B. 注:（1）符号“ ?”不是联结词，只是A与B等值的记号. （2）公式A与B等值当且仅当A与B有相同的真值表. 例1. 判断(p?q)?r 与 p?(q?r)是否等值. 基本等值式 1. 双重否定律 ??A?A 2. 幂等律 A?A?A, A?A?A 3. 交换律 A?B?B?A, A?B?B?A 4. 结合律 (A?B)?C?A?(B?C), (A?B)?C?A?(B?C) 5. 分配律 A?(B?C)?(A?B)?(A?C), A?(B?C)?(A?B)?(A?C) 6. 德摩根律 ?(A?B)??A??B ?(A?B)??A??B 7. 吸收律 A?(A?B)?A, A?(A?B)?A 基本等值式 8. 零律 A?1?1, A?0?0 9. 同一律 A?0?A, A?1?A 10. 排中律 A??A?1 11. 矛盾律 A??A?0 12. 蕴涵等值式 A?B??A?B 13. 等价等值式 A?B?(A?B)?(B?A) 14. 假言易位 A?B??B??A 15. 等价否定等值式 A?B??A??B 16. 归谬论 (A?B)?(A??B) ??A 以上A,B,C代表任意公式 由已知的等值式推演出新的等值式的过程，称为等值演算. 等值演算的基础： (1) 等值关系的性质：自反性、对称性、传递性 (2) 基本的等值式 (3) 置换规则 等值演算的应用举例 例2 用等值演算法完成下列各题： （1）证明： p?(q?r) ? (p?q)?r （2）简化公式((p?q)?(p??q))?r, 要求最后结果只含一个联结词 （3）消去公式(p?q)?(p?r)中的联结词? （4）判断公式 (p?(q?p))?r 的类型. 等值演算的应用举例 （1）证: p?(q?r) ? ?p?(?q?r)（蕴涵等值式，置换规则） ? (?p??q)?r（结合律） ? ?(p?q)?r （德摩根律，置换规则） ? (p?q)?r （蕴涵等值式） （2）((p?q)?(p??q))?r ? ((p?(q??q))?r ? (p?1)?r ? p?r 等值演算的应用举例 （3） (p?q)?(p?r) ? ((p?q)?(q?p))?((p?r)?(r?p)) ? (?p?q)?(?q?p)?(?p?r)?(?r?p) （4）(p?(q?p))?r ? (?p?(q?p))?r ? (?p?(p?q))?r ? ((?p?p)?q)?r ? (1?q)?r ? 1?r ? 1 故(p?(q?p))?r 是重言式 等值演算还能帮助人们解决工作和生活中的实际问题. 例：在课间休息时，3名同学根据孙老师口音对她是哪个省的人进行了判断： 甲说孙老师不是湖南人，是湖北人； 乙说孙老师不是湖北人，是湖南人； 丙说孙老师既不是湖北人，也不是河南人； 甲、乙、丙三人中有一人说得全对，有一人说对了一半，另一人说得全不对. 试用逻辑演算法分析孙老师到底是哪里人