)命题逻辑等值演算.ppt

第二章 命题逻辑等值演算 第二章 命题逻辑等值演算 等值式 析取范式与合取范式 联结词完备集 可满足性问题与消解法 知 识 点：等值式、置换规则、等值演算、(主)析取范式、 (主)合取范式、联结词完备集、其它联结词、 可满足性问题、消解法 教学要求：深刻理解和掌握命题逻辑中的基本概念 教学重点：等值演算、(主)析取范式、(主)合取范式 学时: 4 §2.1 等值式 定义2.1 设A,B是两个命题公式,若A,B构成的等价 式 A?B 为重言式,则称A与B是等值的, 记为　A ? B 注意: 　　? 是元语言符号，不是联结词 §2.1 等值式 16组(24个)重要的等值式 双重否定律 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 §2.1 等值式 同一律 ??????? 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 §2.1 等值式 代入实例：例如在蕴涵等值式中 1. 取A=p, B=q时，得到等值式　p→q ? ┐p∨q 2. 取A=p→q , B= ┐p 时，得到等值式 (p →q) → ┐p ? ┐ (p →q) ∨ ┐ p §2.1 等值式 判别两个公式是否等值的方法 真值表法 等值演算 : ? 以一组基本的又是重要的重言式为基础进 行公式之间的演算 置换规则： 设Ф(A)是含公式A的命题公式 Ф(B) 是用公式B置换了Ф(A)中的A后得到的命题公式 若 B ? A ,则Ф(B) ? Ф(A) 代入规则： 在一个重言式(矛盾式)中，将同一命题变项全部用同一个命题公式替换后,得到的公式仍是重言式 (矛盾式) §2.1 等值式 例1　用等值演算法验证等值式 (p∨q)→ r ? (p→r) ∧(q →r ) 证： (p→r) ∧( q → r ) ? (┐p∨r)∧ (┐q∨ r ) (蕴涵等值式,替换规则) ? ( ┐p ∧┐q) ∨r (分配律) ? ┐(p ∨q) ∨r (德摩根律) ? (p∨q)→ r (蕴涵等值式) 用等值演算法判断公式的类型 (1) ( p→q) ∧p → q (2) ┐( p→(p∨q ) ) ∧r (3) p∧(((p∨q)∧p ) → q ) §2.2 析取范式与合取范式 每种数字标准形都能提供很多信息，如代数式的因式分解可判断代数式的根情况。逻辑公式在等值演算下也有标准形--范式 范式有两种 析取范式 合取范式 §2.2 析取范式与合取范式 文字: 命题变项及其否定统称作文字。 简单析取式: 仅有有限个文字构成的析取式。 简单合取式: 仅有有限个文字构成的合取式。 析取范式: 由有限个简单合取式构成的析取式。 合取范