《离散数学》课程PPT教学课件（讲稿）第1章 命题逻辑（1.3-1.4）命题逻辑等值演算、联结词全功能集

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 等值式 定义 若等价式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

基本等值式 双重否定律:--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 基本等值式 双重否定律 : 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)

基本等值式(续) 德摩根律:_(vB)分→-4∧B ( AAB-Av-B 吸收律:(AAB)台A,AA(B)分A 零律 Av10

4 基本等值式(续) 德·摩根律 : (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

基本等值式(续) 蕴涵等值式:A→>B台AvB 等价等值式:AB兮(A-→>B)(B→4) 假言易位: A→B今-B→4 等价否定等值式:AB分_AB 归谬论: (4->B)(4→>-B)冷A 注意: A,B,C代表任意的命题公式 牢记这些等值式是继续学习的基础

5 基本等值式(续) 蕴涵等值式: 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代表任意的命题公式 牢记这些等值式是继续学习的基础

等值演算与置换规则 等值演算 由已知的等值式推演出新的等值式的过程 置换规则:若A台B,则(B)→(4) 等值演算的基础 (1)等值关系的性质:自反、对称、传递 (2)基本的等值式 (3)置换规则

6 等值演算与置换规则 等值演算: 由已知的等值式推演出新的等值式的过程 置换规则：若AB,则(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)  (pq)→r 证 p→(q→r) p(qr) （蕴涵等值式，置换规则） (pq)r （结合律，置换规则） (pq)r （德摩根律，置换规则） (pq) →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(pq) （蕴涵等值式）  q(pq) （德摩根律）  p(qq) （交换律，结合律）  p0 （矛盾律）  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)  (pq)(qp) （蕴涵等值式）  (pq)(pq) （交换律）  1 由最后一步可知，该式为重言式. 问：最后一步为什么等值于1？