文档介绍：命题逻辑等值演算
等值式与等值演算
等值式与基本等值式
真值表法与等值演算法
联结词完备集
真值函数
联结词完备集
与非联结词和或非联结词
*
析取范式和合取范式
*
等值式
*
若等价式AB是重言式, 则称A与B等值, 记作
AB, 并称AB是等值式
说明: (1) 是元语言符号, 不要混同于和=
(2) A与B等值当且仅当A与B在所有可能赋值下的真值都相
同, 即A与B有相同的真值表
(3) n个命题变项的真值表共有个, 故每个命题公式都有
无穷多个等值的命题公式
(4) 可能有哑元出现. 在B中出现, 但不在A中出现的命题变项称作A的哑元. 同样,在A中出现, 但不在B中出现的命题变项称作B的哑元. 哑元的值不影响命题公式的真值.
析取范式和合取范式
*
真值表法
例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
析取范式和合取范式
*
真值表法(续)
例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不等值
析取范式和合取范式
*
基本等值式
双重否定律 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
*
析取范式和合取范式
*
基本等值式(续)
零律 A11, A00
同一律 A0A, A1A
排中律