第一命题逻辑等值演算.ppt

*
现在学习的是第1页，共19页
等值式
定义 若等价式AB是重言式，则称A与B等值，
记作AB，并称AB是等值式
说明：定义中，A,B,均为元语言符号, A或B中
可能有哑元出现.
例如，在 (pq)  ((pqq)(pq))r)
 (p(qq))r （分配律）
 p1r （排中律）
 pr （同一律）
这不是矛盾式，也不是重言式，而是非重言式的可
,000是它的成假赋值.
总结：A为矛盾式当且仅当A0
A为重言式当且仅当A1
说明：演算步骤不惟一,应尽量使演算短些
现在学习的是第11页，共19页
联结词全功能集
复合联结词
排斥或
与非式
或非式
真值函数
联结词全功能集
现在学习的是第12页，共19页
复合联结词
排斥或: pq(pq)(pq)
与非式: pq(pq)
或非式: pq(pq)
现在学习的是第13页，共19页
真值函數
问题：含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元真值函数.
现在学习的是第14页，共19页
命题公式与真值函数
对于任何一个含n个命题变项的命题公式A，都存在
惟一的一个n元真值函数F为A的真值表.
等值的公式对应的真值函数相同.
下表给出所有2元真值函数对应的真值表, 每一个含
2个命题变项的公式的真值表都可以在下表中找到.

例如：pq, pq, (pq)((pq)q) 等都对应
表中的
现在学习的是第15页，共19页
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
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
现在学习的是第16页，共19页
联结词的全功能集
定义 在一个联结词的集合中，如果一个联结词可
由集合中的其他联结词定义，则称此联结词为冗余
的联结词，否则称为独立的联结词.
例如,在联结词集{, , , , }中，由于
pqpq,
所以，为冗余的联结词; 类似地，也是冗余的
联结词. 又在{, , }中，由于
pq(pq)，
所以，是冗余的联结词. 类似地，也是冗余的联
结词.
现在学习的是第17页，共19页
联结词的全功能集(续)
定义 设S是一个联结词集合，如果任何n(n1) 元
真值函数都可以由仅含S中的联结词构成的公式表
示，则称S是联结词全功能集.
说明：
若S是联结词全功能集，则任何命题公式都可用S
中的联结词表示.
若S1, S2是两个联结词集合，且S1  S2. 若S1是全
功能集，则S2也是全功能集.
现在学习的是第18页，共19页
联结词的全功能集实例
(1) S