y,试根据求得的最优树构造前缀码,并对二进制序列0100110110010001011译码。四、证明题A®(BÙC),(E®ØF)®ØC,B®(AÙØS)ÞB®E试证明命题公式为永真式。试证明:(PÚQ)∧(P®R)∧(Q®S)ÞSÚR用推理规则证明:("x)(P(x)®Q(x))Þ($x)P(x)®($y)(P(y)ÙQ(y))对所有集合A、B和C,有(AÇB)ÈC=AÇ(BÈC),当且仅当CÍA。若R和S是集合A上的等价关系,试证明RÇS也是A上的等价关系。证明集合[0,1]和(0,1)是等势的。设f:X->Y和g:Y->Z是函数,使得g°f是一个满射,且g是一个入射。证明f是满射。设<G1,*>,<G2,°>是两个群,在G1´G2上定义运算为:<a1,b1><a2,b2>=<a1*a2,b1°b2>,证明<G1´G2,>是一个群。f是群<G,°>到群<G’,*>的同态映射,e’是G’中的幺元则,f的同态核K={x|xÎG且f(x)=e’}构成的代数系统<K,°>是<G,°>的子群。证明在格中,若a£b£c,则(1)aÚb=bÙc (2)(aÙb)Ú(bÙc)=b=(aÚb)Ù(aÚc)若有n个人,每个人恰有三个朋友,证明n必为偶数。证明当且仅当G的一条边e不包含在G的回路中时,e才是G的割边。画出K3,3图,并证明其不是欧拉图,也不是平面图。设G为连通图,证明当且仅当边e是G的割边时,e才在G的每颗生成树中。设T是非平凡的无向树,T中度数最大的结点有2个,它们的度数为k(k>=2),证明:T中至少有2k-2片树叶。设G=<V,E>有11个结点,m条边,证明G或者其补图G’是非平面图。部分参考答案一、判断题(错误)(正确)(正确)(错误)(正确)(正确)(正确)(正确)(正确)(正确)(正确)(错误)(错误)(错误)(正确)(正确)(正确)(正确)(正确)(错误)
全文预览