[文学]22命题逻辑的等值演算.pptVIP

. 武汉大学国际软件学院唐存琛 刘峰 2.2 命题逻辑等值演算 1.2.1 等值式与基本等值式 1.2.2 真值表法与等值演算法 1.2.3 联结词完备集 真值函数 联结词完备集 与非联结词和或非联结词 2.2.1 等值式与基本等值式 1、等值式的定义 2、性质 3、常用的基本逻辑恒等式 1.2.2 真值表法与等值演算法 1、真值表法 例题 2、等值演算法 3、永真公式的基本运算规律 例题 例题 新例1：验证下列等值式 (1) (2) 新例2：判断下列公式的类型 新例3：应用题 新例4 例5 用等值演算法判断下列公式的类型 (1) q??(p?q) 解 q??(p?q) ? q??(?p?q) （蕴涵等值式） ? q?(p??q) （德摩根律） ? p?(q??q) （交换律，结合律） ? p?0 （矛盾律） ? 0 （零律） 该式为矛盾式. (2) (p?q)?(?q??p) 解 (p?q)?(?q??p) ? (?p?q)?(q??p) （蕴涵等值式） ? (?p?q)?(?p?q) （交换律） ? 1 该式为重言式. (3) ((p?q)?(p??q))?r) 解 ((p?q)?(p??q))?r) ? (p?(q??q))?r （分配律） ? p?1?r （排中律） ? p?r （同一律） 非重言式的可满足式.如101是它的成真赋值,000是它的 成假赋值. 1.2.3 联结词完备集 1、真值函数 2、联结词完备集 定理2.1 下述联结词集合都是完备集: (1) S1={?, ?, ?, ? , ?} (2) S2={?, ?, ?, ?} (3) S3={?, ? , ?} (4) S4={?, ?} (5) S5={?, ?} (6) S6={?, ?} 举例 与非、或非 与非式: p?q??(p?q), ?称作与非联结词 或非式: p?q??(p?q), ?称作或非联结词 p?q为真当且仅当p,q不同时为真 p?q为真当且仅当p,q同时为假 定理2.2 {?},{?}是联结词完备集 证 ? p ? ?(p?p) ? p?p p?q ? ? ?(p?q) ? ?(p?q) ? (p?q)?(p?q) 得证{?}是联结词完备集. 对于{?}可类似证明. 本节习题 等值演算不能直接证明两个公式不等值. 证明两个公式不 等值的基本思想是找到一个赋值使一个成真, 另一个成假. 例4 证明: p?(q?r) (p?q) ?r 方法一 真值表法（见例2） 方法二 观察法. 容易看出000使左边成真, 使右边成假. 方法三 先用等值演算化简公式, 再观察. 总结:A为矛盾式当且仅当A?0; A为重言式当且仅当A?1 说明:演算步骤不惟一，应尽量使演算短些 n元真值函数共有 个 每一个命题公式对应于一个真值函数 每一个真值函数对应无穷多个命题公式 1元真值函数 p 0 0 0 1 1 1 0 1 0 1 定义2.12 称F:{0,1}n?{0,1}为n元真值函数 2元真值函数 p q 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 p q 0 0 1 1 1 1 1 1 1 1 0 1 0