离散数学课件--第二章-命题逻辑等值演算.pptVIP

第2章命题逻辑等值演算;本章说明;两公式什么时候代表了同一个命题呢？

抽象地看，它们的真假取值完全相同时即代表了相同的命题。

设公式A,B共同含有n个命题变项，可能对A或B有哑元，假设A与B有相同的真值表，那么说明在2n个赋值的每个赋值下，A与B的真值都相同。于是等价式A?B应为重言式。;定义2.1设A,B是两个命题公式，假设A,B构成的等价式A?B为重言式，那么称A与B是等值的，记作A?B。;例2.1判断下面两个公式是否等值

┐(p∨q)与┐p∧┐q;例题2.2判断以下各组公式是否等值

(1)p→(q→r)与(p∧q)→r

(2)(p→q)→r与(p∧q)→r;1.双重否认律 A?┐┐A

2.幂等律 A?A∨A, A?A∧A

3.交换律 A∨B?B∨A， A∧B?B∧A

4.结合律 (A∨B)∨C?A∨(B∨C)

(A∧B)∧C?A∧(B∧C)

5.分配律???????? A∨(B∧C)?(A∨B)∧(A∨C)

〔∨对∧的分配律〕

A∧(B∨C)?(A∧B)∨(A∧C)

〔∧对∨的分配律〕

6.德·摩根律????? ┐(A∨B)?┐A∧┐B

┐(A∧B)?┐A∨┐B

7.吸收律??????? ?A∨(A∧B)?A，A∧(A∨B)?A;根本等值式;一个逻辑等值式，如果只含有┐、∨、∧、0、1

那么同时

把∨和∧互换

把0和1互换

得到的还是等值式。;各等值式都是用元语言符号书写的，其中A,B,C可以代表任意的公式，称这样的等值式为等值式模式。

每个等值式模式都给出了无穷多个同类型的具体的等值式。

例如，在蕴涵等值式A→B?┐A∨B中，

取A=p，B=q时，得等值式p→q?┐p∨q

取A=p∨q∨r，B=p∧q时，得等值式

(p∨q∨r)→(p∧q)?┐(p∨q∨r)∨(p∧q)

这些具体的等值式都被称为原来的等值式模式的代入实例。

由的等值式推演出另外一些等值式的过程为等值演算。

置换规那么设Φ(A)是含公式A的命题公式，Φ(B)是用公式B置换了Φ(A)中所有的A后得到的命题公式，假设B?A，那么Φ(B)?Φ(A)。;等值演算的根底

等值关系的性质：

自反性：A?A。

对称性：假设A?B，那么B?A。

传递性：假设A?B且B?C，那么A?C。

根本的等值式

置换规那么

等值演算的应用

证明两个公式等值

判断公式类型

解判定问题;证明两个公式等值

(p→q)→r?(p∨r)∧(┐q∨r);例2.3用等值演算法验证等值式

(p∨q)→r?(p→r)∧(q→r);例2.4证明：(p→q)→r与p→(q→r)不等值;例题2.5用等值演算判断以下公式的类型：

〔1〕(p→q)∧p→q

〔2〕(p→(p∨q))∧r

〔3〕p∧(((p∨q)∧┐p)→q);(1)(p→q)∧p→q

?(┐p∨q)∧p→q 〔蕴涵等值式〕

?┐((┐p∨q)∧p)∨q 〔蕴涵等值式〕

?(┐(┐p∨q)∨┐p)∨q 〔德摩根律〕

?((p∧┐q)∨┐p)∨q 〔德摩根律〕

?((p∨┐p)∧(┐q∨┐p))∨q 〔分配律〕

?(1∧(┐q∨┐p))∨q 〔排中律〕

?(┐q∨q)∨┐p 〔同一律〕

?1∨┐p 〔排中律〕

?1 〔零律〕;例2.5解答;在某次研讨会的中间休息时间，3名与会者根据王教授的口音对他是哪个省市的人进行了判断：

甲说王教授不是苏州人，是上海人。

乙说王教授不是上海人，是苏州人。

丙说王教授既不是上海人，也不是杭州人。

听完以上3人的判断后，王教授笑着说，他们3人中有一人说的全对，有一人说对了一半，另一人说的全不对。试用逻辑演算法分析王教授到底是哪里人？;设命题p：王教授是苏州人。

q：王教授是上海人。

r：王教授是杭州人。

p,q,r中必有一个真命题，两个假命题，要通过逻辑演算将真命题找出来。

设 甲的判断为A1=┐p∧q

乙的判断为A2=p∧┐q

丙的判断为A3=┐q∧┐r;甲的判断全对?? B1=A1=┐p∧q

甲的判断对一半 B2=(┐p∧┐q)∨(p∧q)

甲的判断全错?? B3=p∧┐q

乙的判断全对?? C1=A2=p∧┐q

乙的判断对一半 C2=(p∧q)∨(┐p∧┐q)

乙的判断全错?? C3=┐p∧q

丙的判断全对?? D1=A3=┐q∧┐r

丙的判断对一半 D2=(q∧┐r)∨(┐q∧r)

丙的判断全错 D3=q∧r;由王教授所说

E=