资源描述：
《离散数学discrete2b》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、5.联结词的完全集【定义1.22】{0,1}上的n元函数f:{0,1}n®{0,1}就称为一个n元真值函数。联结词Ø实际上一个一元真值函数：fØ(0)=1,fØ(1)=0而联结词Ù、Ú、®和«则都是二元真值函数：fÙ(0,0)=0,fÙ(0,1)=0,fÙ(1,0)=0,fÙ(1,1)=1fÚ(0,0)=0,fÚ(0,1)=1,fÚ(1,0)=1,fÚ(1,1)=1f®(0,0)=1,f®(0,1)=1,f®(1,0)=0,f®(1,1)=1f«(0,0)=1,f«(0,1)=0,f«(1,0)=0
2、,f«(1,1)=1反过来，一个真值函数就可看成一个真值联结词。设f:{0,1}n®{0,1}是一个n元真值函数，则可如下定义一个n元真值联结词Nf:对于n个命题变元p1,p2,…,pn，命题公式Nf(p1,p2,…,pn)在真值赋值函数下的真值为f(t1,t2,…,tn)。显然互不相同的n元真值函数的个数为22n，因此可定义22n个n元真值联结词，例如1元真值函数有四个：f1:0®0,1®0f2:0®0,1®1f3:0®1,1®0f4:0®1,1®1而2元真值函数有16个，
3、可定义16个真值联结词，而我们常用的只不过是其中的4个。现在的问题是，是否所有的真值函数都可使用常用的这5个真值联结词来表示呢？【定义1.23】设W是联结词的一个集合，称W为联结词的一个完全集，如果任意真值函数f都可用仅含W中联结词的命题公式A来表示，即对A中命题变元的任意一个真值赋值，A在下的真值为f(t1,t2,…,tn)。【定理1.24】{Ø,Ù,Ú,®}是联结词的一个完全集。【证明】根据定义1.23只要证明对任意n元真值函数都可由只含Ø、Ù、Ú
4、和®的n元命题公式来表示即可。对真值函数的元数n进行归纳证明。归纳基：当n=1时，一元真值函数只有4个，可分别用pÙ(Øp)、p、Øp和pÚ(Øp)来表示，因此定理成立。归纳步：假设当n=k时定理成立，要证n=k+1定理也成立。设f(x1,x2,…,xk,xk+1)是一个k+1元真值函数，定义如下两个k元真值函数：f1(x1,x2,…,xk)=f(x1,x2,…,xk,0)f2(x1,x2,…,xk)=f(x1,x2,…,xk,1)由归纳假设知f1和f2都可由只含Ø、Ù、Ú和®的k元命题公式来表示，
5、设它们分别可由A1和A2表示，且假定A1和A2中的k个命题变元为p1,p2,…,pk。现在我们证f可由A=((Øpk+1)®A1)Ù(pk+1®A2)表示，其中pk+1是不同于p1,p2,…,pk的一个命题变元。即要证对命题变元p1,p2,…,pk,pk+1的一个真值赋值时，A的真值是f(t1,t2,…,tk,tk+1)。当tk+1=0时，即pk+1被赋值为0，这时((Øpk+1)®A1)与A1等值，而(pk+1®A2)的真值为1，所以A与A1等值，而按归纳假设有A
6、1的真值为f1(t1,t2,…,tk)，即为f(x1,x2,…,xk,0)。同理可证当tk+1=1时A的真值是f(x1,x2,…,xk,1)，从而A的真值是f(t1,t2,…,tk,tk+1)。□【推论1.25】{Ø,®},{Ø,Ù}和{Ø,Ú}都是联结词的完全集。【证明】1.要证{Ø,®}是联结词的一个完全集，只要证任一命题公式可与一个只含Ø和®的命题公式等值，事实上有：(AÚB)Û((ØA)®B)(AÙB)Û(Ø((ØA)Ú(ØB)))2.{Ø,Ù}是联结词的一个完全集，因为：(AÚB)Û(Ø(
7、(ØA)Ù(ØB)))(A®B)Û((ØA)ÚB)3.{Ø,Ú}是联结词的一个完全集，因为：(AÙB)Û(Ø((ØA)Ú(ØB)))(A®B)Û((ØA)ÚB)事实上，上述每个集合都是极小的完全集，即不能再从集合中去掉任意一个联结词还能保持是完全集。□【定理1.26】{®,Ù,Ú,«}不是联结词的完全集。【证明】总取0值的真值函数不能由只含此联结词集中的联结词的命题公式来表达，因为这样的命题公式当所有命题变元都真值赋值为1时真值为1，不可能为0。□6.命题公式的范式【定义1.27】将命题符号（代表命
8、题变元或命题常量）或命题符号的否定统称为文字(literal)。仅由有限个文字构成的析取式称为简单析取式。仅由有限个文字构成的合取式称为简单合取式。【例子1.8】文字、简单析取式与简单合取式：(1)p,Øq等为文字，也是一个文字的简单析取式和简单合取式(2)pÚq,pÚ(Øq)等为两个文字的简单析取式，pÚqÚ(Ør)为三个文字的简单析取式(3)pÙq,pÙ(Øq)等为两个文字的简单合取式，pÙqÙ(Ør)为三个文字的简单合取式【定理1.28】一个简单析取式是永真式当
