离散数学：第一章1-3 等值演算

1第一章命题逻辑

1.1命题符号化及联结词1.2命题公式及分类1.3等值演算1.4联结词全功能集1.5对偶与范式1.6推理理论2§3等值演算

一、等值式二、基本等值式三、等值演算与置换规则四、应用举例3一、等值式

定义若等价式A

B是重言式，则称A与B等值，记作A

B，并称A

B是等值式。┐(pVq)与┐pV┐q┐(pVq)与┐p∧┐q注:不是逻辑联结词，表示对任意的赋值，A与B的值相同。↔是等价联结词，它与不能混为一谈。4真值表法（1）pq┐p┐qpVq┐(pVq)┐pV┐q0011011011010110011011100100┐(pVq)与┐pV┐q不等值5真值表法（2）pq┐p┐ppVq┐(pVq)┐p∧┐q0011011011010010011001100100┐(pVq)与┐p∧┐q等值6二、基本等值式序号等值式定律1A

┐┐A双重否定2AAVA等幂律3A

A∧A4AVB

BVA交换律5A∧BB∧A6(AVB)VCA(VBVC)结合律7(A∧B)∧CA∧(B∧C)8AV(B∧C)(AVB)∧(AVC)分配律9A∧(BVC)(A∧B)V(A∧C)7基本等值式（2）序号等值式定律10┐(AVB)

┐A∧┐B德.摩根律11┐(A∧B)

┐AV

┐B12AV(A∧B)A吸收律13A∧(AVB)A14AV11零律15A∧0016AV0A同一律17A∧1A18AV

┐A1排中律19A∧┐A0矛盾律8基本等值式（3）序号等值式定律20A→B┐AVB蕴涵等值式(真值表)21A↔B(A→B)∧(B→A)等价等值式22A→B

┐B→┐A假言易位(逆否命题)23A↔B┐A↔

┐B等价否定等值式24(A→B)∧(A→┐B)┐A归缪论9三、等值演算与置换规则

等值演算:

由已知的等值式推演出新的等值式的过程置换规则：若A

B,则

(A)

(B)

等值演算的基础：

(1)等值关系的性质：自反、对称、传递

(2)基本的等值式

(3)置换规则

10四、应用举例——验证等值式验证下列等值式:p→(q→r)

(p∧q)→r（P10例1.9(1))

p→(q→r)┐p∨(q→r)（蕴涵等值式)

┐p∨(┐q∨r)（蕴涵等值式)

(┐p∨┐q)∨r（结合律）┐(p∧q)∨r（德

摩根律）(p∧q)→r（蕴涵等值式)

(p∧q)→r

┐(p∧q)∨r

(┐p∨┐q)∨r

┐p∨(┐q∨r)

┐p∨(q→r)p→(q→r)11验证等值式（续）验证下列等式:

p

(p∧q)∨(p∧┐q)（P10例1.9(2))

p

p∧1（同一律）

p∧(q∨┐q)（排中律）

(p∧q)∨(p∧┐q)（分配律）12四、应用举例——判断公式类型

例3

用等值演算法判断下列公式的类型(1)q

(p

q)

解q

(p

q)

q

(

p

q)（蕴涵等值式）

q

(p

q)（德

摩根律）

p

(q

q)（交换律，结合律）

p

0（矛盾律）

0（零律）由最后一步可知，该式为矛盾式.

13例3(续)(2)(p

q)

(

q

p)解

(p

q)

(

q

p)

(

p

q)

(q

p)（蕴涵等值式）

(

p

q)

(

p

q)（交换律）

1由最后一步可知，该式为重言式.14例3(续)(3)((p

q)

(p

q))

r)解((p

q)

(p

q))

r)

(p

(q

q))

r

（分配律）

p

1

r

（排中律）

p

r

（同一律）这不是矛盾式，也不是重言式，而是非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.总结：A为矛盾式当且仅当A

0A为重言式当且仅当A

1说明：演算步骤不惟一,应尽量使演算短些例用等值演算法解决下面问题。