4},对V®e4,有x^y=(xy)mod5(1)列岀*的运算表;(2)运算*是否有零元和幺元,并讨论所有元素的逆元。解:(1)运算表为*01234000000101234202413303142404321(2)e=l,^=0,l_l=1,2“=3,3-1=2,4-1=4,0无逆。?8分4、(6分)求公式的主析取范式PT((P—Q)A+QV「P))<=>^Pv((「Pv0a(2aP))<=>—}Pv(—iPaQaP)v(QaQaP))?—yPv(PaQ)<=>(-1Pa(2v->2))v(Pa2)<=>(Pa2)v(-iPa2)v(-iPa-iQ)o叫\/%V% 6分(也可用真值表求解)四、作图或证明题(共32分)1、(5分)画出一个5个顶点6条边的无向欧拉图,但不是哈密顿图。解: 5分2、(6分)画出氐q的所有含4条边的非同构生成子图。解:3、(9分)画出带权为2,3,5,7,8的最优二元树T,计算其树权和树高,并给出每个数字相对应的前缀码。解:订线内不要答W(巧=2x3+3x3+5x2+7x2+8x2=55树高为3对应的前缀码为{000,001,01,10,11}4、(6分)利用推理规则,证明证(1)A(2)A^B(3)B(4)-<BvC)(5)(6)(7)B八「B(矛盾)?9分P(附加前提)pT(1)(2)PT(4)T(5)T(3),(6)?——6分5、(6分)设H是群vG,*>的子群,在G中定义二元关系R={<a9b\>~}b*ae,证明R是G上的一个等价关系。证:由X1*X=eeH,有<兀,兀>€尺,故R是自反的;若<a,b>wR,即bf&,因H是群,有(^1?=*Z>gH,则vbqwR,故R是对称的;若<a,b>wR,<b,c>wR,即,因H是群,满足结合律,有(c~l?*a)=c_1*aeH,则<a9c>eR,故R是传递的。因此R是G上的一个等价关系。 6分
全文预览
