联结词全功能集3(张).ppt
《联结词全功能集3(张).ppt》由会员分享,可在线阅读,更多相关《联结词全功能集3(张).ppt(19页珍藏版)》请在装配图网上搜索。
联结词全功能集,福建师范大学数学与计算机科学学院,回顾,命题符号化(符号)联结词(运算)等值演算(运算律与化简)用等值演算法证明公式类型用等值演算法证明等值式求解实际问题,例应用题,在某次研讨会的中间休息时间,3名与会者根据王教授的口音对他是哪个省市的人进行了判断:甲说王教授不是苏州人,是上海人。乙说王教授不是上海人,是苏州人。丙说王教授既不是上海人,也不是杭州人。听完以上3人的判断后,王教授笑着说,他们3人中有一人说的全对,有一人说对了一半,另一人说的全不对。试用逻辑演算法分析王教授到底是哪里人?,设命题p:王教授是苏州人。q:王教授是上海人。r:王教授是杭州人。p,q,r中或者全假;或者有一个真命题,两个假命题。甲说王教授不是苏州人,是上海人A=pq乙说王教授不是上海人,是苏州人B=pq丙说王教授既不是上海人,也不是杭州人C=qr,解答,列真值表:,根据王教授说,他们3人中有一人说的全对,有一人说对了一半,另一人说的全不对。可知:A,恰有一个为真,于是可得的赋值只能是或。如果是,则甲、乙都说对了一半,与已知不符;所以的赋值为。即王教授是上海人。,联结词全功能集,复合联结词排斥或与非式或非式真值函数联结词全功能集,排斥或(异或,排斥或)两个命题公式P和Q的排斥或是一个新命题公式,记作PQ。当且仅当P、Q真值不同时,PQ为T,其他情况下的真值都是F。,异或联结词的性质:(1)PQ(PQ)(PQ)(2)PQ(PQ)(3)PP0,0PP,1PP(4)PQQP交换律(5)(PQ)RP(QR)结合律(6)P(QR)(PQ)(PR)分配律(课后习题),与非设P和Q是两个命题公式,P和Q的与非是一个新命题公式,记作PQ。当且仅当P和Q的真值都为T时,PQ为F,其他情况下PQ的真值都是T。(读为“竖”)根据此定义,可知PQ(PQ),全真为假见假为真,或非设P和Q是两个命题公式,P和Q的或非是一个新命题公式,记作PQ。当且仅当P和Q的真值都为F时,PQ为T,其他情况下PQ的真值都是F。(读成“箭”)根据此定义,可知PQ(PQ),全假为真见真为假,问题:多少个联结词最合适?,真值函数,问题:含n个命题变项的所有公式共产生多少个互不相同的真值表?答案为个,为什么?定义称定义域为000,001,111,值域为0,1的函数是n元真值函数,定义域中的元素是长为n的0,1串.常用F:0,1n0,1表示F是n元真值函数.真值函数共有个。例如F:0,120,1,且F(00)=F(01)=F(11)=0,F(10)=1,则F为一个确定的2元真值函数.,命题公式与真值函数,对于任何一个含n个命题变项的命题公式A,都存在惟一的一个n元真值函数F为A的真值表.等值的公式对应的真值函数相同.下表给出所有2元真值函数对应的真值表,每一个含2个命题变项的公式的真值表都可以在下表中找到.例如:pq,pq,(pq)(pq)q)等都对应表中的,2元真值函数对应的真值表(书上表1-6),联结词的全功能集,定义在一个联结词的集合中,如果一个联结词可由集合中的其他联结词定义,则称此联结词为冗余的联结词,否则称为独立的联结词.例如,在联结词集,中,由于pqpq,所以,为冗余的联结词;类似地,也是冗余的联结词.又在,中,由于pq(pq)所以,是冗余的联结词,但,无冗余的联结词.类似地,也是冗余的联结词,但,无冗余的联结词.,联结词的全功能集(续),定义设S是一个联结词集合,如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示,则称S是联结词全功能集.如果联结词全功能集不含冗余的联结词,则称为极小功能集.说明:若S是联结词全功能集,则任何命题公式都可用S中的联结词表示.若S1,S2是两个联结词集合,且S1S2.若S1是全功能集,则S2也是全功能集.,联结词的全功能集实例,(1)S1=,(最常用)(2)S2=,(布尔代数系统)(3)S3=,(极小)(4)S4=,(极小)(5)S5=,(极小)(6)S6=(极小、大规模集成电路)(7)S7=(极小、大规模集成电路),例如已知,是全功能集,证明,也是全功能集证:因为,是全功能集,任意一个真值函数可以用,联结词的命题公式表示。对于任意的命题公式,ABAB,因此任意一个真值函数可以用,联结词的命题公式表示。例p(pp)ppp(pp)pppq(pq)(p)(q)(pp)(qq),课后习题:1.试证明P(QR)(PQ)(PR)2.1.10(1)(4)3.1.14,- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 联结 全功能
装配图网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文