福州大学：《离散数学》课程教学资源（课件讲稿）第二章 命题逻辑等值演算

第二章命题逻辑等值演算 1

1 第二章 命题逻辑等值演算

命题逻辑等值演算 ■等值式 ■析取范式与合取范式 ■联结词的完备集 2

2 命题逻辑等值演算 等值式 析取范式与合取范式 联结词的完备集

§2.1等值式 定义若等价式A→B是重言式，则称A与B等值， 记作A曰B,并称A一B是等值式 说明：定义中，A,B,一均为元语言符号，A或B中 可能有哑元出现. 例如，在p→q)台(（一pVqN()中，r为左边 公式的哑元. 用真值表可验证两个公式是否等值21表2.2) 请验证：p→(q-→)台(P∧q)→1 p→(q→)÷(D→q)→1

3 §2.1等值式 定义 若等价式AB是重言式，则称A与B等值， 记作AB，并称AB是等值式 说明：定义中，A,B,均为元语言符号, A或B中 可能有哑元出现. 例如，在 (pq)  ((pq) (rr))中，r为左边 公式的哑元. 用真值表可验证两个公式是否等值(P21 表2.2） 请验证：p(qr)  (pq) r p(qr) (pq) r

基本等值式 双重否定律：一A台A 等幂律： AVA→A,AA台→A 交换律： AVB→BVA,AB台BA 结合律： (AVB)VC→AV(BvC) (AAB)AC台AA(BAC) 分配律： AV(BAC)台(VB)A(AVC) AA(BVC)台(AB)V(AAC)

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

基本等值式（续） 德摩根律：一(AVB)→AAB (AAB)→AV一B 吸收律： AV(AB)→A,AA(AVB)→A 零律： Av1台1，AA0→0 同一律： AV0→A,AΛ1→A 排中律： AVA台1 矛盾律： AΛA→0

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

基本等值式（续） 蕴涵等值式： AB→AVB 等价等值式： Ak→B→(A>B)Λ(B→A) 假言易位： AB←台→B→A 等价否定等值式： AK→B→AK→B 归谬论： (A→B)A(A→B)→A 注意： A,B,C代表任意的命题公式 牢记这些等值式是继续学习的基础 6

6 基本等值式(续) 蕴涵等值式: 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)一(A 等值演算的基础： ()等值关系的性质：自反、对称、传递 (2)基本的等值式 (3)置换规则 7

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

应用举例 证明两个公式等值 例1证明p→(g→)台(p^q)→1 证p-→(q→) →pV(Vr) (蕴涵等值式，置换规则) →(pvvr (结合律，置换规则) →(pΛ)r (德摩根律，置换规则) →pAq)→r (蕴涵等值式，置换规则) 说明：也可以从右边开始演算（请做一遍) 因为每一步都用置换规则，故可不写出 熟练后，基本等值式也可以不写出 8

8 应用举例——证明两个公式等值 例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-→)兮p→)→1 用等值演算不能直接证明两个公式不等值，证明两 个公式不等值的基本思想是找到一个赋值使一个成真， 另一个成假， 方法一真值表法（自己证） 方法二观察赋值法.容易看出000,010等是左边的 成真赋值，010是右边的成假赋值. 方法三用等值演算先化简两个公式，再观察

9 应用举例——证明两个公式不等值 例2 证明: p(qr) (pq) r 用等值演算不能直接证明两个公式不等值,证明两 个公式不等值的基本思想是找到一个赋值使一个成真, 另一个成假. 方法一 真值表法（自己证） 方法二 观察赋值法. 容易看出000, 010等是左边的 成真赋值， 010是右边的成假赋值. 方法三 用等值演算先化简两个公式，再观察

应用举例—判断公式类型 例3用等值演算法判断下列公式的类型 (1)qN-(p-→q) 解 IΛp→q) 台qA(pVq) (蕴涵等值式) 台qAPΛ一q (德摩根律) 台pΛ(qAq) (交换律，结合律) 台pA0 (矛盾律) 台0 (零律) 由最后 一步可知，该式为矛盾式。 10

10 应用举例——判断公式类型 例3 用等值演算法判断下列公式的类型 (1) q(pq) 解 q(pq)  q(pq) （蕴涵等值式）  q(pq) （德摩根律）  p(qq) （交换律，结合律）  p0 （矛盾律）  0 （零律） 由最后一步可知，该式为矛盾式