1、东北石油大学离散数学Discrete Mathematics(第 2章 )School of Software, Northeast Petroleum University2Northeast Petroleum University计算机学院School of computer & information technology本章主要内容第二章 命题逻辑等值演算v等值式与基本的等值式v等值演算与置换规则v析取范式与合取范式，主析取范式与主合取范式v联结词完备集v可满足性问题与消解法本章 10个定义， 10个定理。本章与其他章的关系v是第一章的抽象与延伸v是后续各章的先行准备3Northea
2、st Petroleum University计算机学院School of computer & information technology2.1 等值式几点说明：(1) 定义中， A, B, 均为元语言符号(一 ) 等值式概念p, q, r, , (p q) (p q) 对象语言A B 元语言(2) A或 B中可能有哑元出现 . 例如 pq (pq)(rr) r为左边公式的哑元.定义 2.1 若等价式 AB是重言式，则称 A 与 B 等值 , 记作AB，并称 AB是 等值式(3) 判断两个公式是否等值可用真值表。AB等价式 等值式AB重言式-4Northeast Petroleum Uni
3、versity计算机学院School of computer & information technology例题例 1 判断下列各组公式是否等值 :结论 : p(qr) (pq) r (2) p(qr) 与 (pq) r (1) p(qr) 与 (pq)r结论 : p(qr) 与 (pq) r 不等值5Northeast Petroleum University计算机学院School of computer & information technology(二 ) 基本等值式(1) 双重否定律(2) 幂等律(3) 交换律(4) 结合律(5) 分配律(6) 德摩根律(7) 吸收律 AAAAA,
4、 AAAABBA, ABBA(AB)CA(BC), (AB)CA(BC)A(BC)(AB)(AC), A(BC)(AB)(AC)(AB)AB(AB)ABA(AB)A, A(AB)A6Northeast Petroleum University计算机学院School of computer & information technology(二 ) 基本等值式(8) 零律(9) 同一律(10) 排中律(11) 矛盾律(12) 蕴涵等值式(13) 等价等值式(14) 假言易位(15) 等价否定等值式(16) 归谬论A11, A00A0A. A1AAA1AA0ABABAB(AB)(BA)ABBAABA
5、B(AB)(AB) A特别提示：必须牢记这 16组等值式，这是继续学习的基础。7Northeast Petroleum University计算机学院School of computer & information technology(三 ) 等值演算与置换规则1. 等值演算 :2. 置换规则 :由已知的等值式推演出新的等值式的过程假设 : (A) 是含公式 A 的命题公式(B) 是用公式 B置换 (A)中所有的 A后得到的命题公式 .若 BA，则 (B)(A).AB AB(AB) = (AB)C(AB)C (AB) C(AB) = (AB)C8Northeast Petroleum Uni
6、versity计算机学院School of computer & information technology(四 ) 等值演算应用举例1 证明两个公式等值例 2 证明 (p q)r (pr)(qr)注意：用等值演算不能直接证明两个公式不等值例 3 证明 (pq)r 与 p(qr)不等值2 判断公式类型 A为矛盾式当且仅当 A 0A为重言式当且仅当 A 1例 4 用等值演算法判断下列公式的类型(1) (p q) p q (2) (p( p q) r (3) p (p q) p) q) 重言式矛盾式可满足式易知 000, 010是左边成真赋值，右边成假赋值。9Northeast Petroleu
7、m University计算机学院School of computer & information technology2.2 析取范式与合取范式1 文字 :2 简单析取式 :3 简单合取式 :4 析取范式 :5 合取范式 :6 范式 :(一 ) 范式定义说明：v单个文字既是简单析取式，又是简单合取式v形如 pqr, pqr 的 公式既是析取范式，又是合取范式命题变项及其否定的总称有限个文字构成的析取式有限个文字构成的合取式由有限个简单合取式组成的析取式由有限个简单析取式组成的合取式析取范式与合取范式的总称10Northeast Petroleum University计算机学院School of computer & information technology(二 ) 范式性质定理 2.1(1) 一个简单析取式是重言式当且仅当它同时含有某个命题变项和它的否定式 .(2) 一个简单合取式是矛盾式当且仅当它同时含有某个命题变项和它的否定式 .定理 2.2 (1) 一个析取范式是矛盾式当且仅当它每个简单合取式都是矛盾式 .(2) 一个合取范式是重言式当且仅当它的每个简单析取式都是重言式 .
