联结词全功能集3(张)

《联结词全功能集3(张)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、联结词全功能集福建师范大学数学与计算机科学学院回顾命题符号化（符号）联结词（运算）等值演算（运算律与化简）用等值演算法证明公式类型用等值演算法证明等值式求解实际问题例应用题在某次研讨会的中间休息时间，3名与会者根据王教授的口音对他是哪个省市的人进行了判断：甲说王教授不是苏州人，是上海人。乙说王教授不是上海人，是苏州人。丙说王教授既不是上海人，也不是杭州人。听完以上3人的判断后，王教授笑着说，他们3人中有一人说的全对，有一人说对了一半，另一人说的全不对。试用逻辑演算法分析王教授到底是哪里人？设命题p：王教授是苏州人。q：王教授是上海人。r：王教授是杭州人。p,q,r中或者全假;或者有一个真

2、命题，两个假命题。甲说王教授不是苏州人，是上海人A=┐p∧q乙说王教授不是上海人，是苏州人B=p∧┐q丙说王教授既不是上海人，也不是杭州人C=┐q∧┐r解答列真值表：pqr┐p┐q┐r┐p∧qp∧┐q┐q∧┐r00011100110001101101010110０001110000根据王教授说，他们3人中有一人说的全对，有一人说对了一半，另一人说的全不对。可知：A，Ｂ，Ｃ恰有一个为真，于是可得ｐｑｒ的赋值只能是０００或０１０。如果是０００，则甲、乙都说对了一半，与已知不符；所以ｐｑｒ的赋值为０１０。即王教授是上海人。联结词全功能集复合联结词排斥或与非式或非式真值函数联结词全功能集排斥或（

3、异或,排斥或）两个命题公式P和Q的排斥或是一个新命题公式，记作PQ。当且仅当P、Q真值不同时，PQ为T，其他情况下的真值都是F。011001010011pqqp异或联结词的性质：（1）PQ（P∧┐Q）∨（┐P∧Q）（2）PQ┐(PQ）（3）PP0，0PP，1P┐P（4）PQQP交换律（5）（PQ）RP（QR）结合律（6）P∧（QR）（P∧Q）（P∧R）分配律（课后习题）与非设P和Q是两个命题公式，P和Q的与非是一个新命题公式，记作PQ。当且仅当P和Q的真值都为T时，PQ为F，其他情况下PQ的真值都是T。（读为“竖”）根据此定义，可知PQ┐（P∧Q）11100

4、1010011pqqp全真为假见假为真或非设P和Q是两个命题公式，P和Q的或非是一个新命题公式，记作PQ。当且仅当P和Q的真值都为F时，PQ为T，其他情况下PQ的真值都是F。（读成“箭”）根据此定义，可知PQ┐（P∨Q）100001010011pqqp全假为真见真为假问题：多少个联结词最合适？真值函数问题：含n个命题变项的所有公式共产生多少个互不相同的真值表？答案为个，为什么？定义称定义域为{00…0,00…1,…,11…1}，值域为{0,1}的函数是n元真值函数，定义域中的元素是长为n的0,1串.常用F:{0,1}n{0,1}表示F是n元真值函数.真值函数共有个。例如

5、F:{0,1}2{0,1}，且F(00)=F(01)=F(11)=0，F(10)=1，则F为一个确定的2元真值函数.命题公式与真值函数对于任何一个含n个命题变项的命题公式A，都存在惟一的一个n元真值函数F为A的真值表.等值的公式对应的真值函数相同.下表给出所有2元真值函数对应的真值表,每一个含2个命题变项的公式的真值表都可以在下表中找到.例如：pq,pq,(pq)((pq)q)等都对应表中的2元真值函数对应的真值表（书上表1-6）pq0001101100000000000011110011001101010101pq00011011111111110000111100

6、11001101010101联结词的全功能集定义在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为冗余的联结词，否则称为独立的联结词.例如,在联结词集{,,,,}中，由于pqpq,所以，为冗余的联结词;类似地，也是冗余的联结词.又在{,,}中，由于pq(pq)所以，是冗余的联结词，但{,}无冗余的联结词.类似地，也是冗余的联结词，但{,}无冗余的联结词.联结词的全功能集(续)定义设S是一个联结词集合，如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词全功能集.如果联结词全功能

7、集不含冗余的联结词，则称为极小功能集.说明：若S是联结词全功能集，则任何命题公式都可用S中的联结词表示.若S1,S2是两个联结词集合，且S1S2.若S1是全功能集，则S2也是全功能集.联结词的全功能集实例(1)S1={,,,,}（最常用）(2)S2={,,}（布尔代数系统）(3)S3={,}（极小）(4)S4={,}（极小）(5)S5={,}（极小）(6)S6={}（极小、大规模集成电路）(7)S7={