命题逻辑等值演算(离散数学)课案.ppt

* 第二章 命题逻辑等值演算 * 本章主要内容 等值式 范式 合取范式 析取范式 联结词的完备集 重点内容： 等值演算 范式 消解法 * 2.1 等值式 等值式 基本等值式 等值演算和置换规则 * 一、等值式 定义1：设A和B是两个命题公式，如果A、B在任意指派下，其真值都是相同的，则称A和B是等值的，或逻辑相等，记作A?B，称A?B为等值式。 p ? q ? q ? ?p ? p ? q (p ? q) ?(q ? p) ? * 一、等值式 p ? q ? q ? ?p 1 1 1 1 0 0 1 1 (p ? q) ? (?q??p) 1 1 1 1 * 一、等值式 p ? q (p ? q) ?(q ? p) 1 1 0 0 0 0 1 1 (p ? q) ?((p ? q) ?(q ? p)) 1 1 1 1 * 一、等值式 定义2： 若A?B是重言式，则称A与B等值，记作A?B，并称A?B是等值式。 例如， (p?q) ? ((?p?q)? (?r?r)) 说明：定义中，A、B、?均为元语言符号, A或B中可能有哑元出现。 r是哑元 * 一、等值式 等值式的性质： 自反性，即对任意公式A，有A ? A。 对称性，即对任意公式A和B，若A ? B，则B ? A。 传递性，即对任意公式A、B和C，若 A ? B、B ? C，则A ? C。 * 一、等值式 例1：“除非有时间，我才去看电影。” 上面这句话的意思相当于 “如果没有时间，我就不去看电影。” 令：p：我有时间；q：我去看电影 * p q p ? q ? p ? q ? q ? ? p 0 0 1 1 1 1 0 1 1 1 0 1 1 0 0 0 1 0 1 1 1 0 0 1 p ? q 和 ? q ? ? p是等值的。 判断两个公式是否为等值式的基本方法是：通过两个公式的真值表进行验证。 * 二、基本等值式 双重否定律 : ? ? 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 * A?B??A?B (p?q) A B 等值式模式：由元语言符号表示的等值式称作等值式模式。 p A B (r?s) A B r ? ? ?(p?q) ? r q ? ??p?q (?s) ?? (r?s) ? (?s) ? 代入实例 每一个等值模式都可以对应于无穷多个同类型的具体等值式。 * 三、等值演算与置换规则 等值演算: 由已知的等值式推演出新的等值式的过程。 例：由基本等值式可知p?q??p?q 所以：当用?p?q替换p?q时， 公式A 公式B * 三、等值演算与置换规则 置换规则：设?(A)是含有公式A的命题公式，用公式B置换?(A)中所有的A后得到新的命题公式?(B)，若A?B, 则?(B)??(A) 。 * 三、等值演算与置换规则 等值演算的基础： (1) 等值关系的性质：自反、对称、传递 (2) 基本的等值式 (3) 置换规则 * 例2 ：证明 三、等值演算与置换规则 *