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

第二章命题逻辑等值演算 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