天津理工大学：《离散数学》课程教学资源（PPT课件）第一章 命题逻辑 Propositional Logic 1.4 其它联结词 Other Connectives（2/2）

1.4联结词全功能集真值函数联结词全功能集

1 1.4 联结词全功能集 ▪真值函数 ▪联结词全功能集

真值函敷问题：含n个命题变项的所有公式共产生多少个互不相同的真值函数？答案为22"个，为什么？定义称定义域为00...0,00...1，...，11...1)，值域为{0,1}的函数是n元真值函数，定义域中的元素是长为n的0,1串.常用F:{0,1)n→{0,1}表示F是n元真值函数.共有22"个n元真值函数例如 F:{0,1)2→[0,1}, 且F(00)=F(01)=F(11)=0,F(01)=1，则F为一个2元真值函数

2 真值函數 n 2 2 n 2 2 问题：含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元真值函数

命题公式与真值函数每个真值函数可对应无穷多个命题公式，他们彼此都是等值的。下表给出所有2元真值函数对应的真值表，每一个含2个命题变项的公式的真值表都可以在下表中找到例如：→>,p,(pq)((p→))等都对应表中的F(2)13

3 命题公式与真值函数 (2) F13 每个真值函数可对应无穷多个命题公式，他们彼此 都是等值的。 下表给出所有2元真值函数对应的真值表, 每一个含 2个命题变项的公式的真值表都可以在下表中找到. 例如：p→q, pq, (pq)((p→q)q) 等都对应 表中的

2元真值函数对应的真值表3Ff(2)F(2)Fr(2)q0000000001福0000F2)FISeF,(2)Fl)Fil2)FG)Fl(2)90111111D00000011

4 2元真值函数对应的真值表 p q 0 0 0 1 1 0 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) F0 F F F F F F F p q 0 0 0 1 1 0 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) 1 5 (2) 1 4 (2) 1 3 (2) 1 2 (2) 1 1 (2) 1 0 (2) 9 (2) F8 F F F F F F F

联结词的全功能集定义在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为穴余的联结词，否则称为独立的联结词，例如,在联结词集{一,^,,→,台，，个，}中，由于所以，一为亢余的联结词：类似地，台也是亢余的联结词.又在{一,^,v)中，由于-(),所以，入是穴余的联结词.类似地，V也是穴余的联结词.L

5 联结词的全功能集 定义 在一个联结词的集合中，如果一个联结词可 由集合中的其他联结词定义，则称此联结词为冗余 的联结词，否则称为独立的联结词. 例如,在联结词集{, , , →, ， ， ， }中，由于 p→qpq, 所以，→为冗余的联结词; 类似地，也是冗余的 联结词. 又在{, , }中，由于 pq(pq)， 所以，是冗余的联结词. 类似地，也是冗余的联 结词.   