第一命题逻辑等值演算.ppt

*
第一页，共19页
等值式
定义 若等价式AB是重言式，则称A与B等值，
记作AB，并称AB是等值式
说明：定义中，A,B,均为元语言符号, A或B中
可能有哑元出现.
例如，在 (pq)  ((pq) (rr))中，r为左边
公式的哑元.
用真值表可验证两个公式是否等值
请验证：p(qr)  (pq) r
p(qr) (pq) r
第二页，共19页
基本等值式
双重否定律 : 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)
第三页，共19页
基本等值式(续)
德·摩根律: (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
第四页，共19页
基本等值式(续)
蕴涵等值式: 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,C代表任意的命题公式
牢记这些等值式是继续学习的基础
第五页，共19页
等值演算与置换规则
等值演算:
由已知的等值式推演出新的等值式的过程
置换规则：若AB, 则(B)(A)
等值演算的基础：
(1) 等值关系的性质：自反、对称、传递
(2) 基本的等值式
(3) 置换规则
第六页，共19页
应用举例——证明两个公式等值
例1 证明 p(qr)  (pq)r
证 p(qr)
p(qr) （蕴涵等值式，置换规则）
(pq)r （结合律，置换规则）
(pq)r （德摩根律，置换规则）
(pq) r （蕴涵等值式，置换规则）
说明:也可以从右边开始演算（请做一遍）
因为每一步都用置换规则，故可不写出
熟练后，基本等值式也可以不写出
第七页，共19页
应用举例——证明两个公式不等值
例2 证明: p(qr) (pq) r
用等值演算不能直接证明两个公式不等值,证明两
个公式不等值的基本思想是找到一个赋值使一个成
真,另一个成假.
方法一 真值表法（自己证）
方法二 观察赋值法. 容易看出000, 010等是左边的
的成真赋值，是右边的成假赋值.
方法三 用等值演算先化简两个公式，再观察.
第八页，共19页
应用举例——判断公式类型
例3 用等值演算法判断下列公式的类型
(1) q(pq)
解 q(pq)
 q(pq) （蕴涵等值式）
 q(pq) （德摩根律）
 p(qq) （交换律，结合律）
 p0 （矛盾律）
 0 （零律）
由最后一步可知，该式为矛盾式.
第九页，共19页
例3 (续)
(2) (pq)(qp)
解 (pq)(qp)
 (pq)(qp) （蕴涵等值式）
 (pq)(pq) （交换律）
 1
由最后一步可知，该式为重言式.
问：最后一步为什么等值于1？
第十页，共19页