1.3命题逻辑等值演算 等值式 ■基本等值式 ■等值演算 ■置换规则
1 1.3 命题逻辑等值演算 ▪等值式 ▪基本等值式 ▪等值演算 ▪置换规则
等值式 定义若等价式4<>B是重言式,则称A与B等值, 记作A分→B,并称A<>B是等值式 说明:定义中,A,B,分均为元语言符号,A或B中 可能有哑元出现 例如,在(→>q)兮(yVqy(-r)中,r为左边 公式的哑元 用真值表可验证两个公式是否等值 请验证:p->(q-n)兮(∧q)→r p→>(q)r)台(P→q)→>r
2 等值式 定义 若等价式AB是重言式,则称A与B等值, 记作AB,并称AB是等值式 说明:定义中,A,B,均为元语言符号, A或B中 可能有哑元出现. 例如,在 (p→q) ((pq) (rr))中,r为左边 公式的哑元. 用真值表可验证两个公式是否等值 请验证:p→(q→r) (pq) →r p→(q→r) (p→q) →r
基本等值式 双重否定律:--4A 交换律: AvB<→BvA,AAB<→BA 结合律: (4vB)VC分→Av(BvC (4∧B)C分A入(B∧C 分配律:VB∧O)→(AB)(C A∧(BvC冷(4入B)v(A入C)
3 基本等值式 双重否定律 : AA 等幂律: AAA, AAA 交换律: ABBA, ABBA 结合律: (AB)CA(BC) (AB)CA(BC) 分配律: A(BC)(AB)(AC) A(BC) (AB)(AC)
基本等值式(续) 德摩根律:_(vB)分→-4∧B ( AAB-Av-B 吸收律:(AAB)台A,AA(B)分A 零律 Av10
4 基本等值式(续) 德·摩根律 : (AB)AB (AB)AB 吸收律: A(AB)A, A(AB)A 零律: A11, A00 同一律: A0A, A1A 排中律: AA1 矛盾律: AA0
基本等值式(续) 蕴涵等值式:A→>B台AvB 等价等值式:AB兮(A-→>B)(B→4) 假言易位: A→B今-B→4 等价否定等值式:AB分_AB 归谬论: (4->B)(4→>-B)冷A 注意: A,B,C代表任意的命题公式 牢记这些等值式是继续学习的基础
5 基本等值式(续) 蕴涵等值式: A→BAB 等价等值式: AB(A→B)(B→A) 假言易位: A→BB→A 等价否定等值式: ABAB 归谬论: (A→B)(A→B) A 注意: A,B,C代表任意的命题公式 牢记这些等值式是继续学习的基础
等值演算与置换规则 等值演算 由已知的等值式推演出新的等值式的过程 置换规则:若A台B,则(B)→(4) 等值演算的基础 (1)等值关系的性质:自反、对称、传递 (2)基本的等值式 (3)置换规则
6 等值演算与置换规则 等值演算: 由已知的等值式推演出新的等值式的过程 置换规则:若AB,则(B)(A) 等值演算的基础: (1) 等值关系的性质:自反、对称、传递 (2) 基本的等值式 (3) 置换规则
应用举例—证明两个公式等值 例1证明p→>(q→r)(∧q)-r 证p->(q→)r) 兮>-pw∨(-qm)(蕴涵等值式,置换规则) 兮(一p-qyr(结合律,置换规则 兮>一(∧qyvr(德摩根律,置换规则) 兮(p∧q)→r(蕴涵等值式,置换规则) 说明:也可以从右边开始演算(请做一遍) 因为每一步都用置换规则,故可不写出 熟练后,基本等值式也可以不写出
7 应用举例——证明两个公式等值 例1 证明 p→(q→r) (pq)→r 证 p→(q→r) p(qr) (蕴涵等值式,置换规则) (pq)r (结合律,置换规则) (pq)r (德摩根律,置换规则) (pq) →r (蕴涵等值式,置换规则) 说明:也可以从右边开始演算(请做一遍) 因为每一步都用置换规则,故可不写出 熟练后,基本等值式也可以不写出
应用举例——证明两个公式不等值 例2证明:p→>(q→)n(-→q)-r 用等值演算不能直接证明两个公式不等值,证明两 个公式不等值的基本思想是找到一个赋值使一个成 真,另一个成假 方法一真值表法(自己证) 方法二观察赋值法.容易看出00,000等是左边的 成真赋值,是右边的成假赋值 方法三用等值演算先化简两个公式,再观察
8 应用举例——证明两个公式不等值 例2 证明: p→(q→r) (p→q) →r 用等值演算不能直接证明两个公式不等值,证明两 个公式不等值的基本思想是找到一个赋值使一个成 真,另一个成假. 方法一 真值表法(自己证) 方法二 观察赋值法. 容易看出000, 010等是左边的 成真赋值,是右边的成假赋值. 方法三 用等值演算先化简两个公式,再观察
应用举例一判断公式类型 例3用等值演算法判断下列公式的类型 (1)q∧-(D→>q) 解q∧_(p→>q) 兮>q∧-(-yvq)(蕴涵等值式) 兮q(pA-q)(德摩根律) 兮p∧(q入-q)(交换律,结合律) >p~0 (矛盾律) 0 (零律) 由最后一步可知,该式为矛盾式
9 应用举例——判断公式类型 例3 用等值演算法判断下列公式的类型 (1) q(p→q) 解 q(p→q) q(pq) (蕴涵等值式) q(pq) (德摩根律) p(qq) (交换律,结合律) p0 (矛盾律) 0 (零律) 由最后一步可知,该式为矛盾式
例3(续) (2)(>q)>(q-→>yp) 解(p->q)>(-q→p) 兮(yVq)(qp)(蕴涵等值式) 兮(yVq)>(pq)(交换律) 台1 由最后一步可知,该式为重言式 问:最后一步为什么等值于1? 10
10 例3 (续) (2) (p→q)(q→p) 解 (p→q)(q→p) (pq)(qp) (蕴涵等值式) (pq)(pq) (交换律) 1 由最后一步可知,该式为重言式. 问:最后一步为什么等值于1?