1、第二章 命题逻辑等值演算 主要内容l 等值式与基本的等值式l 等值演算与置换规则l 析取范式与合取范式，主析取范式与主合取范式l 联结词完备集12.1 等值式定义 2.1 若等价式 AB是重言式，则称 A与 B等值 ，记作 AB，并称 AB是 等值式几点说明：l不要把 与 混为一谈 .l A或 B可以是任何命题公式 , 公式中还可能有哑元出现 . 例如 (pq) (pq)(rr) r为左边公式的哑元 l用真值表可检查两个公式是否等值2等值式例题例 1 判断下列各组公式是否等值 : (1) p(qr) 与 (pq) r 311111101 11111101 11011101 0 0 00 0 1
2、0 1 00 1 11 0 01 0 11 1 01 1 1 (pq)rp(qr)qr p q r pq00000011 结论 : p(qr) (pq) r 等值式例题 (2) p(qr) 与 (pq) r 401011101 11111101 11011101 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 (pq)rp(qr)qr p q r pq11110011 结论 : p(qr) 与 (pq) r 不等值基本等值式 双重否定律 AA 幂等律 AAA, AAA 交换律 ABBA, ABBA 结合律 (AB)CA(BC), (AB)CA(BC) 分配律
3、A(BC)(AB)(AC), A(BC)(AB)(AC) 德摩根律 (AB)AB (AB)AB 吸收律 A(AB)A, A(AB)A5基本等值式 零律 A11, A00 同一律 A0A. A1A 排中律 AA1 矛盾律 AA0 蕴涵等值式 ABAB 等价等值式 AB(AB)(BA) 假言易位 ABBA 等价否定等值式 ABAB 归谬论 (AB)(AB) A 特别提示：必须牢记这 16组等值式，这是继续学习的基础6等值演算与置换规则1. 等值演算 由已知的等值式推演出新的等值式的过程2. 等值演算的基础： (1) 等值关系的性质：自反性、对称性、传递性 (2) 基本的等值式 (3) 置换规则3.
4、 置换规则 设 (A) 是含公式 A 的命题公式， (B) 是用公式 B 置换 (A) 中所有的 A 后得到的命题公式 若 BA，则 (B)(A).7等值演算的应用举例 证明两个公式等值 例 2 证明 p(qr) (pq)r 证 p(qr) p(qr) （蕴涵等值式，置换规则） (pq)r （结合律，置换规则） (pq)r （德摩根律，置换规则） (pq)r （蕴涵等值式，置换规则） 今后在注明中省去置换规则 注意：用等值演算不能直接证明两个公式不等值8等值演算的应用举例证明两个公式不等值例 3 证明 p(qr) 与 (pq)r 不等值证 方法一 真值表法 , 见例 1(2)方法二 观察法 . 观察到 000, 010是左边的成真赋值，是右边的成假赋值 方法三 先用等值演算化简公式，然后再观察 p(qr) pqr (pq)r (pq)r(pq)r 更容易看出前面的两个赋值分别是 左边的成真赋 值和右边的成假赋值9等值演算的应用举例 判断公式类型 : A为矛盾式当且仅当 A 0 A为重言式当且仅当 A 1 例 4 用等值演算法判断下列公式的类型 (1) q(pq) (2) (pq)(qp) (3) (pq)(pq)r 10解 (1) q(pq) q(pq) （蕴涵等值式） q(pq) （德摩根律） p(qq) （交换律，结合律） p0 （矛盾律） 0 （零律）矛盾式
