离散数学复习题5

08B得分一、单项选择题(每小题2分，共10分)1.下列命题公式等值的是()BBAAQPQQPQBAABAAQPQP),()D(),()C()(),()B(,)A(2.设全体域D是正整数集合，确定下列命题的真值为真的命题是：（)(A)xy(xy=y)(B)xy(x+y=y)(C)xy(x+y=x)(D)xy(y=2x)3.设集合A＝{0,b},B={1,b,3},则AB上的恒等关系是().(A){0,0,1,1,3,3}(B){0,0,1,1,b,b,3,3}(C){1,1,b,b,3,3}(D){0,1,1,bb,3,3,0}4.已知集合A＝{a,b,c}上的二元关系R的关系矩阵MR＝001011010，那么R＝()，(A){a,b,b,a,b,b,a,c}(B){a,b,b,a,b,b,c,b}(C){a,b,a,a,b,b,c,a}(D){a,b,b,a,b,b,c,a}5.命题公式QQPP))((是（）(A)．矛盾式(B).可满足式(C).重言式(D).等值式得分二、填空题(每小题2分，共10分)1.设命题公式G：P(QP)，则使公式G为假的真值指派是。2..设Ａ＝｛1,2,3,4,5,6｝，B={2,3,4}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2｝，则R-1=3.设个体域D＝{1,2},那么谓词公式)()(yyBxxA消去量词后的等值式为。4.设有向图D＝V,E的邻接矩阵为A(D)=1100100001000110，那么E＝。5.代数系统G,*是一个群，则G的等幂元是。得分三、计算题(40分)1.(10分)求命题公式))()((QPPQP的主合取范式、主析取范式。2.(5分)求下面有权图的最优生成树。3．(5分)设代数系统Z,*，其中Z是整数集，二元运算定义为2*,,babaZba，Za，求(1)Z,*的单位元（2）a的逆元（3）判断“*”是否可结合4.(10分)设集合A={1,2,3,4}，A上的二元关系分别为：R={1,1,1,2,2,4,3,1,3,3},S={1,3,2,2,4,4,3,2,},试用定义求SR，RS，2R，1R，1S,11SR，并画出其关系图。5．(10分)写出图4-3的邻接矩阵并求从b到d长度为3和从a到c长度为4的通路条数。图4-3得分四．证明题(每小题10分，共20分)1.（10分）设R是集合A上的对称关系和传递关系，试证明：若对aA,bA，使得a,bR,则R是等价关系.2.（10分）在群G,*,中，（1）如果对任意元素Ga有ea2，则G,*,是阿贝尔群。（2）如果对任何元素Gba,，有222*)*(baba，则G,*,是一个阿贝尔群。得分五、（10分）用CP规则证明：SQPSRQRQP),(),(。得分六、（10分）设G，为群,a为G中给定元素。定义函数f：G→G，使得对每一xG有f(x)=axa-1证明：f是G，到G，的自同构。答案一、单项选择题(每小题3分，共15分)1.C2.A3.B4.D5.A二、填空题(每小题3分，共15分)1.(1,0)；(1,1);2.2,43.A(1)A(2)(B(1)B(2));4.6;5.单位元.三、计算题(40分)1.(10分)解：))()((QPPQP分）（分）（分6)()()(5)00()())()2())()((QPQPQQPPQPPQPQPQPPQP此为主合取范式、主析取范式：分）（10)()(QPQP2.(5分)解：3.(5分)解：易知，二元运算满足交换律.∵对aZ,a*2=a+2－2＝a＝2*a，即2Z是单位元.(2分)aZ,a的逆元记作a－1,有22*11aaaa(单位元)a－1=4－a(5分)4.(10分)解：}2,3,3,3,4,2,2,1,3,1{SRRS={4,3,4,2,3,1,1,1}2R={3,3,2,3,1,3,4,1,2,1,1,1}1R={2,4,3,3,1,2,3,1,1,1}1S={4,4,1,3,3,2,2,2}11SR={3,4,2,4,1,3,1,1}（4分）其关系图如下图所示。（每图1分）（10分）5.(10分)A(D)=0101101001011110A2(D)=2120020221201212A3(D)=7774353414144242A4(D)=777681188777611161112(4分)从矩阵A2(D)可知，从b到d长度为3的通路有1条.(7分)从矩阵A4(D)a到c长度为4的通路有16条.(10分)四、证明题(每小题10分，共20分)1.证明：已知R是对称关系和传递关系，只需证明R是自反关系.(3分)4123R-S2213S-R24312R12341R3421S1234111SRaA,bA，使得a,bR，因为R是对称的，故b,aR;(6分)又R是传递的，a,bR，b,aRa,aR,由元素a的任意性，知R是自反的.(9分)所以，R是等价关系.2．证明：（1）因为Ga，ea2，所以ababGbaaa11)(,,,，又baab1)(，baab，因此得证。（5分）（2）因为Gba,有bbaababa*)*(**)*(222，又bababababa*)*(*)*(*)*()*(2，群中可约律成立，所以abba**，因此得证。（10分）五、（10分）证明：（1）QP（附加前提）（2）)(SRQP（3）SRT（1）（2）I（4）)(RQPP（5）PP(5分)（6）RQT（4）（5）I（7）RT（1）（6）I（8）ST（3）（7）I（9）SQCP(10分)