离散数学及应用 课件 1.3 命题逻辑等值演算

DiscreteMathematics鄢小虎

离散数学课程引入

为什么需要进行等值演算？n个命题变项，共有2n个可能的赋值，有2n行，计算量太大。例如：6个命题变项，有64行，这是不能接受的。

如何进行等值演算？1.3命题逻辑等值演算

等值式基本等值式代入定理、置换定理等值演算等值式

定义若等价式A

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

B，并称A

B是等值式说明：A,B,

均为元语言符号,

与、=不同，不能混为一谈。

是关系符，不是联结词，不能进行运算。“”的三个性质1.自反性A

A。2.对称性若A

B则B

A。3.传递性若A

B,B

C则A

C。A,B是否等值等价于A,B的真值表是否相同。课堂测验用真值表和编程验证以下公式是否等值（6分钟）请验证：p

(q

r)

(p

q)

r

(p

q)

r参考课本第9页的表1-5，1-6

基本等值式

双重否定律

:

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)真值表验证等值式(a)

AA双重否定(b)AAA 等幂律课堂练习：用真值表和编程证明分配律：

A

(B

C)

(A

B)

(A

C)基本等值式(续)德·摩根律:

(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

A

B等价等值式:A

B

(A

B)

(B

A)假言易位:A

B

B

A等价否定等值式:A

B

A

B归谬论:(A

B)

(A

B)

A注意:A,B,C代表任意的命题公式牢记这些等值式是继续学习的基础真值表验证等值式用真值表证明常用等式（10分钟）蕴涵等值式:A

B

A

B等价等值式:A

B

(A

B)

(B

A)德·摩根律:

(A

B)

A

B

如何利用程序验证？等值演算与置换规则

等值演算:

由已知的等值式推演出新的等值式的过程等值演算的基础：

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

(2)基本的等值式（16个）

(3)置换规则吸收律等值演算与置换规则

置换规则：若A

B,则

(B)

(A).

将

作为函数进行推理代换规则：证明两个公式等值

证明:

Q→（P

（P

Q））

Q→P

证：Q→（P

（P

Q））

Q→P~~~~~~~~~P（吸收律）证明两个公式等值

证明两个公式等值

证明：

p

(q

r)

(p

q)

r（前面真值表证明过）

课堂练习:从右边开始演算一遍（5分钟）提示：去掉

证

p

(q

r)

p

(

q

r)（蕴涵等值式，置换规则）

(

p

q)

r

（结合律，置换规则）

(p

q)

r

（德

摩根律，置换规则）

(p

q)

r

（蕴涵等值式，置换规则）课堂练习习题7中的(2)-(4)判断公式类型

用等值演算法判断下列公式的类型(真值表？编程实现？)(1)P→(Q→P)

提示：去除

和括号（蕴涵等值式）（排中等值式）（零律等值式）（交换律+结合律）解q

(p

q)

q

(

p

q)（蕴涵等值式）

q

(p

q)（德

摩根律）

p

(q

q)（交换律，结合律）

p

0（矛盾律）

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

用等值演算法判断下列公式的类型（编程验证）(2)q

(p

q)

提示：去除

、

和括号用等值演算法判断下列公式的类型（编程验证）(3)(p

q)

(

q

p)解

(p

q)

(

q

p)

(

p

q)

(q

p)（蕴涵等值式）

(

p

q)

(

p

q)（交换律，将

p

q

设为A）

1由最后一步可知，该式为重言式.问：最后一