命题逻辑等值演算.ppt

第二章命题逻辑等值演算
主要内容:
等值式与基本的等值式
等值演算与置换规则
析取范式与合取范式,主析取范式与主合取范式
联结词完备集
要求
深刻理解等值式的概念
牢记基本等值式的名称及它们的内容
了解简单析取式、简单合取式、析取范式、合取范式的概念
深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系,并理解简单析取式与极小项的关系
熟练掌握求主范式的方法(等值演算、真值表等)
会用公式的主范式求公式的成真、成假赋值及判断公式的类型、简单应用
会将任何公式化成任何联结词完备集中的
定义:设A、B为两例题公式,若A B是重言式,则称A与B是等值的,记作
例如:
P
Q
P→Q
Q→P
P Q
(P→Q)∧(Q→P)
T
T
T
T
T
T
T
F
F
T
F
F
F
T
T
F
F
F
F
F
T
T
T
T
一、等值式
等值式
双重否定
(对合律)
1
幂等律
2
结合律
3
交换律
4
分配律
5
吸收律
6

7
同一律
8
零律
9
排中律
10
矛盾律
11
蕴涵等值式
12
等价等值式
13
假言易位
14
等价否定等值式
15
归谬论
16
定义:根据已知的等值式,推演出另外一些等值式的过程称为等值演算。
定理:设P(A)是含命题公式A的命题公式,P(B)是用公式B置换了P(A)中的A之后得到的命题公式。如果A与B等值则P(A)与P(B)等值
二、等值演算与置换规则
三、等值演算的应用举例

例证明 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
证方法一真值表法(自己证)
方法二观察赋值法. 易知000, 010等是左边的成真赋值,是右边的成假赋值
方法三用等值演算先化简两个公式,再观察.