离散数学 课件.ppt.ppt

命题逻辑等值演算
等值式与等值演算
等值式与基本等值式
真值表法与等值演算法
联结词完备集
真值函数
联结词完备集
与非联结词和或非联结词
1
等值式
若等价式AB是重言式, 则称A与B等值, 记作
AB, 并称AB是等值式
说明: (1) 是元语言符号, 不要混同于和=
(2) A与B等值当且仅当A与B在所有可能赋值下的真值都相
同, 即A与B有相同的真值表
(3) 可能有哑元出现. 在B中出现, 但不在A中出现的命题变项称作A的哑元. 同样,在A中出现, 但不在B中出现的命题变项称作B的哑元. 哑元的值不影响命题公式的真值.
2
真值表法
例1 判断(pq) 与pq 是否等值
解
结论: (pq) (pq)
p q p q pq (pq) pq (pq)(pq)
0 0 1 1 0 1 1 1
0 1 1 0 1 0 0 1
1 0 0 1 1 0 0 1
1 1 0 0 1 0 0 1
3
真值表法(续)
例2 判断下述3个公式之间的等值关系:
p(qr), (pq)r, (pq)r
解
p q r p(qr) (pq)r (pq)r
0 0 0 1 0 1
0 0 1 1 1 1
0 1 0 1 0 1
0 1 1 1 1 1
1 0 0 1 1 1
1 0 1 1 1 1
1 1 0 0 0 0
1 1 1 1 1 1
p(qr)与(pq)r等值, 但与(pq)r不等值
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)
德摩根律(AB)AB
(AB)AB
吸收律 A(AB)A, A(AB)A
5
基本等值式(续)
零律 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
6
等值演算
等值演算: 由已知的等值式推演出新的等值式的过程
置换规则: 若AB, 则(B)(A)
例3 证明 p(qr) (pq)r
证 p(qr)
p(qr) (蕴涵等值式)
(pq)r (结合律)
(pq)r (德摩根律)
(pq) r (蕴涵等值式)
7
实例
等值演算不能直接证明两个公式不等值. 证明两个公式不
等值的基本思想是找到一个赋值使一个成真, 另一个成假.
例4 证明: p(qr) (pq) r
方法一真值表法(见例2)
方法二观察法. 容易看出000使左边成真, 使右边成假.
方法三先用等值演算化简公式, 再观察.
8
实例
例5 用等值演算法判断下列公式的类型
(1) q(pq)
解 q(pq)
 q(pq) (蕴涵等值式)
 q(pq) (德摩根律)
 p(qq) (交换律,结合律)
 p0 (矛盾律)
 0 (零律)
该式为矛盾式.
9
实例(续)
(2) (pq)(qp)
解(pq)(qp)
(pq)(qp) (蕴涵等值式)
(pq)(pq) (交换律)
 1
该式为重言式.
10