1
1.3 命题逻辑等值演算
?等值式
?基本等值式
?等值演算
?置换规则
2
等值式
定义 若等价式 A?B是重言式，则称 A与 B等值,
记作 A?B，并称 A?B是 等值式
说明：定义中,A,B,?均为元语言符号,A或 B中
可能有哑元出现,
例如，在 (p?q) ? ((?p?q)? (?r?r))中,r为左边
公式的哑元,
用真值表可验证两个公式是否等值
请验证,p?(q?r) ? (p?q) ?r
p?(q?r) (p?q) ?r
3
基本等值式
双重否定律, ??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)
4
基本等值式 (续 )
德 ·摩根律, ?(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
5
基本等值式 (续 )
蕴涵等值式, 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代表任意的命题公式
牢记这些等值式是继续学习的基础
6
等值演算与置换规则
等值演算,
由已知的等值式推演出新的等值式的过程
置换规则,若 A?B,则 ?(B)??(A)
等值演算的基础,
(1) 等值关系的性质：自反, 对称, 传递
(2) 基本的等值式
(3) 置换规则
7
应用举例 —— 证明两个公式等值
例 1 证明 p?(q?r) ? (p?q)?r
证 p?(q?r)
??p?(?q?r) （ 蕴涵等值式, 置换规则 ）
?(?p??q)?r （ 结合律, 置换规则 ）
??(p?q)?r （ 德摩根律, 置换规则 ）
?(p?q) ?r （ 蕴涵等值式, 置换规则 ）
说明,也可以从右边开始演算 （ 请做一遍 ）
因为每一步都用置换规则, 故可不写出
熟练后，基本等值式也可以不写出
8
应用举例 —— 证明两个公式不等值
例 2 证明, p?(q?r) (p?q) ?r
用等值演算不能直接证明两个公式不等值,证明两
个公式不等值的基本思想是找到一个赋值使一个成
真,另一个成假,
方法一 真值表法（自己证）
方法二 观察赋值法, 容易看出 000,010等是左边的
成真赋值，是右边的成假赋值,
方法三 用等值演算先化简两个公式，再观察,
9
应用举例 —— 判断公式类型
例 3 用等值演算法判断下列公式的类型
(1) q??(p?q)
解 q??(p?q)
? q??(?p?q) （ 蕴涵等值式 ）
? q?(p??q) （ 德摩根律 ）
? p?(q??q) （ 交换律, 结合律 ）
? p?0 （ 矛盾律 ）
? 0 （ 零律 ）
由最后一步可知，该式为矛盾式,
10
例 3 (续 )
(2) (p?q)?(?q??p)
解 (p?q)?(?q??p)
? (?p?q)?(q??p) （ 蕴涵等值式 ）
? (?p?q)?(?p?q) （ 交换律 ）
? 1
由最后一步可知, 该式为重言式,
问：最后一步为什么等值于 1？
11
例 3 (续 )
(3) ((p?q)?(p??q))?r)
解 ((p?q)?(p??q))?r)
? (p?(q??q))?r （ 分配律 ）
? p?1?r （ 排中律 ）
? p?r （ 同一律 ）
这不是矛盾式, 也不是重言式, 而是非重言式的可
满足式,如 101是它的成真赋值,000是它的成假赋值,
总结,A为矛盾式当且仅当 A?0
A为重言式当且仅当 A?1
说明：演算步骤不惟一,应尽量使演算短些
12
1.4 联结词全功能集
?复合联结词
? 排斥或
? 与非式
? 或非式
?真值函数
?联结词全功能集
13
复合联结词
排斥或, p?q?(p??q)?(?p?q)
与非式, p?q??(p?q)
或非式, p?q??(p?q)
14
真值函數
n22
n22
问题：含 n个命题变项的所有公式共产生多少个互
不相同的真值表？
答案为 个, 为什么？
定义 称定义域为 {00… 0,00… 1,…,11… 1},值域
为 {0,1}的函数是 n元真值函数, 定义域中的元素是
长为 n的 0,1串, 常用 F:{0,1}n?{0,1} 表示 F是 n元真值
函数,
共有 个 n元真值函数,
例如 F:{0,1}2?{0,1}，且 F(00)=F(01)=F(11)=0,
F(01)=1，则 F为一个确定的 2元真值函数,
15
命题公式与真值函数
)2(
13F
对于任何一个含 n个命题变项的命题公式 A,都存在
惟一的一个 n元真值函数 F为 A的真值表,
等值的公式对应的真值函数相同,
下表给出所有 2元真值函数对应的真值表,每一个含
2个命题变项的公式的真值表都可以在下表中找到,
例如,p?q,?p?q,(?p?q)?(?(p?q)?q) 等 都对应
表中的
16
2元真值函数对应的真值表
p q
0 0
0 1
0 1
1 1
0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
)2(7)2(6)2(5)2(4)2(3)2(2)2(1)2(0 FFFFFFFF
p q
0 0
0 1
0 1
1 1
1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
)2(15)2(14)2(13)2(12)2(11)2(10)2(9)2(8 FFFFFFFF
17
联结词的全功能集
定义 在一个联结词的集合中, 如果一个联结词可
由集合中的其他联结词定义, 则称此联结词为 冗余
的联结词, 否则称为 独立的联结词,
例如,在联结词集 {?,?,?,?,?}中, 由于
p?q??p?q,
所以, ?为冗余的联结词 ; 类似地, ?也是冗余的
联结词, 又在 {?,?,?}中, 由于
p?q??(?p??q),
所以,?是冗余的联结词, 类似地,?也是冗余的联
结词,
18
联结词的全功能集 (续 )
定义 设 S是一个联结词集合, 如果任何 n(n?1) 元
真值函数都可以由仅含 S中的联结词构成的公式表
示, 则称 S是 联结词全功能集,
说明,
若 S是联结词全功能集, 则任何命题公式都可用 S
中的联结词表示,
若 S1,S2是两个联结词集合，且 S1 ? S2,若 S1是全
功能集，则 S2也是全功能集,
19
联结词的全功能集实例
(1) S1={?,?,?,?}
(2) S2={?,?,?,?,?}
(3) S3={?,?}
(4) S4={?,?}
(5) S5={?,?}
(6) S6={?}
(7) S8={?}{?,?}
而 {?},{ ?}等则不是联结词全功能集,
1.3 命题逻辑等值演算
?等值式
?基本等值式
?等值演算
?置换规则
2
等值式
定义 若等价式 A?B是重言式，则称 A与 B等值,
记作 A?B，并称 A?B是 等值式
说明：定义中,A,B,?均为元语言符号,A或 B中
可能有哑元出现,
例如，在 (p?q) ? ((?p?q)? (?r?r))中,r为左边
公式的哑元,
用真值表可验证两个公式是否等值
请验证,p?(q?r) ? (p?q) ?r
p?(q?r) (p?q) ?r
3
基本等值式
双重否定律, ??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)
4
基本等值式 (续 )
德 ·摩根律, ?(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
5
基本等值式 (续 )
蕴涵等值式, 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代表任意的命题公式
牢记这些等值式是继续学习的基础
6
等值演算与置换规则
等值演算,
由已知的等值式推演出新的等值式的过程
置换规则,若 A?B,则 ?(B)??(A)
等值演算的基础,
(1) 等值关系的性质：自反, 对称, 传递
(2) 基本的等值式
(3) 置换规则
7
应用举例 —— 证明两个公式等值
例 1 证明 p?(q?r) ? (p?q)?r
证 p?(q?r)
??p?(?q?r) （ 蕴涵等值式, 置换规则 ）
?(?p??q)?r （ 结合律, 置换规则 ）
??(p?q)?r （ 德摩根律, 置换规则 ）
?(p?q) ?r （ 蕴涵等值式, 置换规则 ）
说明,也可以从右边开始演算 （ 请做一遍 ）
因为每一步都用置换规则, 故可不写出
熟练后，基本等值式也可以不写出
8
应用举例 —— 证明两个公式不等值
例 2 证明, p?(q?r) (p?q) ?r
用等值演算不能直接证明两个公式不等值,证明两
个公式不等值的基本思想是找到一个赋值使一个成
真,另一个成假,
方法一 真值表法（自己证）
方法二 观察赋值法, 容易看出 000,010等是左边的
成真赋值，是右边的成假赋值,
方法三 用等值演算先化简两个公式，再观察,
9
应用举例 —— 判断公式类型
例 3 用等值演算法判断下列公式的类型
(1) q??(p?q)
解 q??(p?q)
? q??(?p?q) （ 蕴涵等值式 ）
? q?(p??q) （ 德摩根律 ）
? p?(q??q) （ 交换律, 结合律 ）
? p?0 （ 矛盾律 ）
? 0 （ 零律 ）
由最后一步可知，该式为矛盾式,
10
例 3 (续 )
(2) (p?q)?(?q??p)
解 (p?q)?(?q??p)
? (?p?q)?(q??p) （ 蕴涵等值式 ）
? (?p?q)?(?p?q) （ 交换律 ）
? 1
由最后一步可知, 该式为重言式,
问：最后一步为什么等值于 1？
11
例 3 (续 )
(3) ((p?q)?(p??q))?r)
解 ((p?q)?(p??q))?r)
? (p?(q??q))?r （ 分配律 ）
? p?1?r （ 排中律 ）
? p?r （ 同一律 ）
这不是矛盾式, 也不是重言式, 而是非重言式的可
满足式,如 101是它的成真赋值,000是它的成假赋值,
总结,A为矛盾式当且仅当 A?0
A为重言式当且仅当 A?1
说明：演算步骤不惟一,应尽量使演算短些
12
1.4 联结词全功能集
?复合联结词
? 排斥或
? 与非式
? 或非式
?真值函数
?联结词全功能集
13
复合联结词
排斥或, p?q?(p??q)?(?p?q)
与非式, p?q??(p?q)
或非式, p?q??(p?q)
14
真值函數
n22
n22
问题：含 n个命题变项的所有公式共产生多少个互
不相同的真值表？
答案为 个, 为什么？
定义 称定义域为 {00… 0,00… 1,…,11… 1},值域
为 {0,1}的函数是 n元真值函数, 定义域中的元素是
长为 n的 0,1串, 常用 F:{0,1}n?{0,1} 表示 F是 n元真值
函数,
共有 个 n元真值函数,
例如 F:{0,1}2?{0,1}，且 F(00)=F(01)=F(11)=0,
F(01)=1，则 F为一个确定的 2元真值函数,
15
命题公式与真值函数
)2(
13F
对于任何一个含 n个命题变项的命题公式 A,都存在
惟一的一个 n元真值函数 F为 A的真值表,
等值的公式对应的真值函数相同,
下表给出所有 2元真值函数对应的真值表,每一个含
2个命题变项的公式的真值表都可以在下表中找到,
例如,p?q,?p?q,(?p?q)?(?(p?q)?q) 等 都对应
表中的
16
2元真值函数对应的真值表
p q
0 0
0 1
0 1
1 1
0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
)2(7)2(6)2(5)2(4)2(3)2(2)2(1)2(0 FFFFFFFF
p q
0 0
0 1
0 1
1 1
1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
)2(15)2(14)2(13)2(12)2(11)2(10)2(9)2(8 FFFFFFFF
17
联结词的全功能集
定义 在一个联结词的集合中, 如果一个联结词可
由集合中的其他联结词定义, 则称此联结词为 冗余
的联结词, 否则称为 独立的联结词,
例如,在联结词集 {?,?,?,?,?}中, 由于
p?q??p?q,
所以, ?为冗余的联结词 ; 类似地, ?也是冗余的
联结词, 又在 {?,?,?}中, 由于
p?q??(?p??q),
所以,?是冗余的联结词, 类似地,?也是冗余的联
结词,
18
联结词的全功能集 (续 )
定义 设 S是一个联结词集合, 如果任何 n(n?1) 元
真值函数都可以由仅含 S中的联结词构成的公式表
示, 则称 S是 联结词全功能集,
说明,
若 S是联结词全功能集, 则任何命题公式都可用 S
中的联结词表示,
若 S1,S2是两个联结词集合，且 S1 ? S2,若 S1是全
功能集，则 S2也是全功能集,
19
联结词的全功能集实例
(1) S1={?,?,?,?}
(2) S2={?,?,?,?,?}
(3) S3={?,?}
(4) S4={?,?}
(5) S5={?,?}
(6) S6={?}
(7) S8={?}{?,?}
而 {?},{ ?}等则不是联结词全功能集,
