天津理工大学：《离散数学》课程教学资源（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)， 所以，是冗余的联结词. 类似地，也是冗余的联 结词.   

故任意命题公式都可由仅包含，或{，V}的命题公式等价代换.即8个联结词的集合中至少有六个亢余联结词。又注意到联结词，}和(，}不再有余联结词,故{，^}或，}为最小联结词组.但实际中为了使用方便,命题公式常常同时包含{，^,V}

6 故任意命题公式都可由仅包含{┐,}或 {┐, }的命题公式等价代换.即8个联结词的 集合中至少有六个冗余联结词. 又注意到联结词{┐,}和{┐, }不再有 冗余联结词, 故{┐,}或{┐, }为最小联结词 组.但实际中为了使用方便, 命题公式常常同 时包含{┐,, }

联结词的全功能集（续）定义设S是一个联结词集合，如果任何n(n≥1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词全功能集说明：若S是联结词全功能集，则任何命题公式都可用S中的联结词表示若S,S,是两个联结词集合，且S,CS.若S,是全功能集，则S,也是全功能集

7 联结词的全功能集(续) 定义 设S是一个联结词集合，如果任何n(n1) 元 真值函数都可以由仅含S中的联结词构成的公式表 示，则称S是联结词全功能集. 说明： 若S是联结词全功能集，则任何命题公式都可用S 中的联结词表示. 若S1 , S2是两个联结词集合，且S1 S2 . 若S1是全 功能集，则S2也是全功能集

联结词的全功能集实例(1) S,={一, ^, V, →)(2) S,=, ^, V, →, )(3) S3={, ^)(4) S4={-, V)(5) S,={~, →)(6) S6={↑}(7) S:={)而v,等则不是联结词全功能集:

8 联结词的全功能集实例 (1) S1={, , , →} (2) S2={, , , →, } (3) S3={, } (4) S4={, } (5) S5={, →} (6) S6={} (7) S8={} 而{},{ }等则不是联结词全功能集

第一章 命题逻辑（Propositional Logic）1.6其它联结词(OtherConnectives)例1:试证（↑}是极小全功能集证: P (P^P)P PPAQ<> (PAQ)< (P ↑ Q)<(P ↑ Q) ↑ (P + Q)PvQ ( P< Q)<≤ ((P ↑ P)^(Q Q))(P ↑ P) ↑ (Q ↑ Q)例2.试证{一，→}是极小全功能集证: P^Q ( PV Q) (P→ Q)PvQ ( P)VQ- P-→Q

9 第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives) 例1:试证{↑}是极小全功能集. 证：┐P┐(PP)P↑P PQ┐┐(PQ)┐(P↑Q)(P↑Q)↑(P↑Q) PQ┐(┐P┐Q)┐((P↑P)(Q↑Q)) (P↑P)↑(Q↑Q) 例2.试证{┐，→}是极小全功能集 证：PQ┐(┐P┐Q)┐(P→┐Q) PQ┐(┐P)Q┐P→Q