资源描述：
《1.4 联结词全功能集》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、~授课时间第一周第2次课授课章节1.4联接词全功能集任课教师及职称唐新华讲师教学方法与手段板书和电子课件结合课时安排1课时使用教材和主要参考书1、教材：耿素云等，离散数学，清华大学出版社，20082.参考书左孝琳、李为槛、刘永才，离散数学（上海科技文献版）2006教学与目的要求：理解真值函数、了解联结词全功能集教学重点、难点:教学重点：真值函数联结词的全功能集教学难点：真值函数联结词的全功能集教学内容:1.4联结词全功能集一、本节主要内容复合联结词排斥或与非式或非式真值函数联结词全功能集二、教学内容复合联结词排斥或（异或）:“p、q之中恰好有一个成
2、立”p"qÛ(pÙØq)Ú(ØpÙq)与非式:“p与q的否定”pqÛØ(pÙq)或非式:“p或q的否定”p¯qÛØ(pÚq)问题：多少个联结词最合适？真值函数问题：含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(10)=1，则F为一个确定的2元
3、真值函数.命题公式与真值函数对于任何一个含n个命题变项的命题公式A，都存在惟一的一个n元真值函数F为A的真值表.等值的公式对应的真值函数相同.下表给出所有2元真值函数对应的真值表,每一个含2个命题变项的公式的真值表都可以在下表中找到.例对于任何一个含n个命题变项的命题公式A，都存在惟一的一个n元真值函数F为A的真值表.等值的公式对应的真值函数相同.下表给出所有2元真值函数对应的真值表,每一个含2个命题变项的公式的真值表都可以在下表中找到.例如：p®q,ØpÚq,(ØpÚq)Ú(Ø(p®q)Ùq)等都对应表中的如：p®q,ØpÚq,(ØpÚq)Ú(Ø
4、(p®q)Ùq)等都对应表中的2元真值函数对应的真值表pq 0001101100000000000011110011001101010101pq ~~~~0001101111111111000011110011001101010101联结词的全功能集定义在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为冗余的联结词，否则称为独立的联结词.例如,在联结词集{Ø,Ù,Ú,®,«}中，由于p®qÛØpÚq,所以，®为冗余的联结词;类似地，«也是冗余的联结词.又在{Ø,Ù,Ú}中，由于pÙqÛØ(ØpÚØq)所以，Ù是冗余的联结
5、词，但{Ø,Ú}无冗余的联结词.类似地，Ú也是冗余的联结词，但{Ø,Ù}无冗余的联结词.联结词的全功能集定义设S是一个联结词集合，如果任何n(n³1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词全功能集.如果联结词全功能集不含冗余的联结词，则称为极小功能集.说明：若S是联结词全功能集，则任何命题公式都可用S中的联结词表示.若S1,S2是两个联结词集合，且S1ÍS2.若S1是全功能集，则S2也是全功能集.联结词的全功能集实例(1)S1={Ø,Ù,Ú,®}(2)S2={Ø,Ù,Ú,®,«}(3)S3={Ø,Ù}(4)S4={Ø,Ú}
6、(5)S5={Ø,®}(6)S6={}(7)S7={¯}而{Ú},{Ù}等则不是联结词全功能集.例如已知{Ø,®}是全功能集，证明{Ø,Ú}也是全功能集证：因为{Ø,®}是全功能集，任意一个真值函数可以用{Ø,®}联结词的命题公式表示。~~~~对于任意的命题公式，A®BÛØAÚB,因此任意一个真值函数可以用{Ø,Ú}联结词的命题公式表示。例ØpÛØ(pÙp)ÛppØpÛØ(pÚp)Ûp¯ppÛØ(Øp)ÛØ(pp)Û(pp)(pp)pÛØ(Øp)ÛØ(p¯p)Û(p¯p)¯(p¯p)复习思考题、作业题：去掉下面连接词集中冗余的联接词(1)S1={Ø
7、,Ù,Ú,®}(2)S2={Ø,Ù,Ú,®,«}下次课预习要点：1.5.1对偶原理1.5.2析取范式与合取范式1.5.2.1基本概念1.5.2.2命题公式的范式1.5.2.3求公式的范式举例1.5.3主析取范式与主合取范式1.5.3.1、极小项与极大项1.5.3.2、主析取范式与主合取范式1.5.3.3、命题公式A的主析取范式与主合取范式1.5.3.4、用等值演算法求公式的主范式的步骤1.5.4主范式的用途——与真值表相同~~~~实施情况及教学效果分析:院系部审核意见:院系部负责人签字年月日~~~
