第二章-命题逻辑等值演算.ppt

第二章 命题逻辑等值演算 本章的主要内容： 等值式与重言蕴涵式 公式的标准型--范式 联结词完备集 本章与其他各章的联系 是第一章的抽象与延伸 是后续各章的先行准备 2.1等值式和重言蕴涵式 一、等值式与基本的等值式 2. 基本的等值式 双重否定律 ??A?A 幂等律 A?A?A, A?A?A 交换律 A?B?B?A, A?B?B?A 结合律 (A?B)?C?A?(B?C), (A?B)?C?A?(B?C) 分配律 A?(B?C)? (A?B)?(A?C), A?(B?C)? (A?B)?(A?C) 德摩根律 ?(A?B)??A??B ?(A?B)??A??B 吸收律 A?(A?B)?A, A?(A?B)?A 零律 A?1?1, A?0?0 同一律 A?0?A. A?1?A 排中律 A??A?1 矛盾律 A??A?0 蕴涵等值式 A?B??A?B 等价等值式 A?B?(A?B)?(B?A) 假言易位 A?B??B??A 等价否定等值式 A?B??A??B 归谬论 (A?B)?(A??B) ??A 注意：要牢记各个等值式，这是继续学习的基础 例：将下面程序语言进行化简：if A then if B then X else Y if B then X else Y 练习： 用等值演算法证明下列等值式： (1)q?(p?r) ?(p∧q)? r (2)?（p?q）?（p∧? q）∨（?p∧q） 2.基本重言蕴涵式 附加律 A ? (A?B) B ? (A?B) 化简律 (A?B) ? A (A?B) ? B 假言推理 (A?B)?A ? B 拒取式 (A?B)??B ? ?A 析取三段论 (A?B)??B ? A 假言三段论 (A?B)?(B?C) ? (A?C) 等价三段论 (A?B)?(B?C) ? (A?C) 构造性二难 (A?B)?(C?D)?(A?C) ? (B?D) (A?B)?(?A?B)?(A??A) ? B 破坏性二难 (A?B)?(C?D)?( ?B??D) ? (?A??C) (1)真值表法: 令F=p?（q?r） ? （p?q）?（p?r） (2)等值演算法 等值和重言蕴涵的关系： 证明等值式A?B的方法： 练习： 不构造真值表证明下式： (1) (a∧b)∨(b∧c)∨(c∧a)?(a∨b)∧(b∨c)∧(c∨a) (2) (p?q) ?q?p∨q 由等值式可知，同一命题公式可以有各种相互等值的表达形式，为了把命题公式规范化，需要研究公式的范式问题。 如果公式中的变元数目较大时，对于公式的判定问题，真值表将非常繁琐。每增加一个变元，计算将增加一倍。研究公式的标准型问题变得十分重要。 给定任意一个命题公式，我们希望寻找其某种一般的标准的形式，即范式(normal form) 。 1.基本概念 （1）文字——命题变项及其否定的总称 （2）简单析取式——有限个文字构成的析取式p, ?q, p??q, p?q?r, … （3）简单合取式——有限个文字构成的合取式p, ?q, p??q, p?q?r, … （4）析取范式——由有限个简单合取式组成的析取式 A1?A2???Ar (r?1) （5）合取范式——由有限个简单析取式组成的合取式 A1?A2???Ar (r?1) （6）范式——析取范式与合取范式的总称 说明：（1）单个文字既是简单析取式，又是简单合取式（2）形如p??q?r, ?p?q??r的公式既是析取范式，又是合取范式. 2.主要性质 定理2.1 （1）一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式。 （2）一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定式。 定理2.2 （1）一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。 （2）一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。 3．定理2.3 (范式存在定理) 任何命题公式都存在着与之等值的析取范式与合取范式. 例:求下列公式的析取范式、合取范式 （1） ( p?(q?r) ) ? s 解：( p?(q?r) ) ? s ? ( p?(?q?r) ) ?s ? ?(p ? (?