离散数学试卷A答案

第1学期《离散数学》试卷A得分阅卷人（试卷共6页，答题时间120分钟）题号一二三四总分统分人复核人得分得分阅卷人一、选择题（每小题2分，共20分。请将答案1、从集合分类的角度看，命题公式可分为A.1、从集合分类的角度看，命题公式可分为A.永真式、矛盾式题号12345678910答案()B.永真式、可满足式、矛盾式C.可满足式、矛盾式C.可满足式、矛盾式D.永真式、可满足式2、设B不含有x,x（A（x）B）等值于A.xA(x)BB.x(A(x)B)A.xA(x)BB.x(A(x)B)C.xA(x)BC.xA(x)BD.x(A(x)B)3、设S,T,M是集合，下列结论正确的是（A.如果A.如果SUT=SUM,则T=M.如果S-T=①，贝US=TC.SSS.STS(~T)C.SSS.STS(~T)4、设R是集合A上的偏序关系，则4、设R是集合A上的偏序关系，则R不一定是（A.自反的B.对称的C.反对称的D.传递5设R为实数集，定义R上4个二元运算，不满足结合律的是fi(x,y)=x+yf2(x,y)=x-yf3(x,y尸xyf4(x,y)=max{x,y}6、设＜工5设R为实数集，定义R上4个二元运算，不满足结合律的是fi(x,y)=x+yf2(x,y)=x-yf3(x,y尸xyf4(x,y)=max{x,y}6、设＜工,＞是一个格，则它不满足（A.交换律B.结合律C.吸收律D.消去律7、设A={1,2},则群P(A),的单位元和零元是（A.与AB.C.{1}与D.{1}8、下列编码是前缀码的是).A.{1,11,101}B.{1,001,0011}C.{1,01,001,000}D.{0,00,000}9、下图中既是欧拉图又是哈密顿图的是（A.K9K10A.K9K10C.K2,3K3,310、下图所示的二叉树中序遍历的结果是B.edcba.badce得分阅卷人A.abcde二、填空题（每题3B.edcba.badce得分阅卷人A.abcde二、填空题（每题3分，共24分）1、含3个命题变项的命题公式的主合取范式为 MoM3M4M6M7,则它的主析取范式为。（表示成mm的形势）2、〈Z4,〉模4加群，则3是 阶元，33=—,3的逆元是

3、设3、设V=<Z,+>,其中“+”是普通加法xZ,令1（x）=x, 2（x）=-x,3（x）=x+5,4(x)=2x,其中有 上自同构.123456 4、设 是集合A={1,2,3,4,5,6}上的一个置换，则231546把它表示成不相交的轮换的积是。4、已知n阶无向简单图G有m条边，则G的补图有条边。5、一个有向图是强连通的充分必要条件是7、已知n阶无向图G中有m条边，各顶点的度数均为3。又已知2n-3=m,贝Um= .8、在下图中从A点开始，用普里姆算法构造最小生成树，加入生成树的第三条边是( )。计算题(每题9分，共计算题(每题9分，共36分)1、已知命题公式(pq)(qp),(1)构造真值表。(2)求主析取范式(要求通过等值演算推出)。2、R1={<1,2>,<1,3>,<2,3>},R 2={<2,2>,<2,3>,<3,4>},求：(1)RiR2 (2)R1 (3)求R2R13、设<A,R>为一个偏序集，其中，A={1,2,3,4,6,9,12,24},R是A上的整除关系。(1)画R出的哈斯图;

(2)求A的极大元和极小元；(3)求B={4,6}的上确界和下确界。4、画一棵带权为1,1,1,3,3,5,8的最优二叉树T,并计算它的权W(T)得分阅卷人得分阅卷人四、证明题(共20分)1、(7分)前提：p(qs),q,pr结论：rs2、(7分)A={(0,0),(0,1),(1,0),(1,3),(2,2),(2,3),(3,1)},R={<(a,b),(c,d)>|(a,b),(c,d) A且a+b=c+d}.(1)证明：R是A上的等价关系.(2)给出R确定的对A的划分(分类).3、(6分)设G,是群，S{x|xG且对于yG,xyyx},证明S是G的子群.《离散数学》试卷A

参考答案、选择题(每小题2分，共20分。请将答案填在下面的表格内)得分阅卷人得分阅卷人二、填空题(每题3分，共24分)题号12345678910答案cadbbdbcaa1、m〔m2m53、2 4 、（123）（45）。4n（n」）n 5、存在经过每个顶点的回路27、 9 . 8 、d,c或c,d三、计算题（每题9分，共36分）1、（1）构造真值表（4分）p,q(pq)(qp)(pq)(qp)0001101100101111,1111⑵主析取范式(5分)：(pq)(qp)(pq)(qp)(pq)(qp)(pq)(qp)(pq)(pq)(pq)mom2m3 (0,2,3)2、(每小题3分)⑴RiR2={<1,2>,<1,3>} (2)Ri1={<2,1>,<3,1>,<3,2>}(1)求R2R1={<1,2>,<1,3>,<1,4>,<2,4>}3、(每小题3分)(4分)24（3分）A的极大元9,24;极小元1;（2分）B={4,6}的上确界12下确界24、画图（7分）W（T）=55（2分）四、证明题（共20分）1、（7分）证明：附加前提证明法..1分①r②pr③p ①② 3分④p(qs)③④..5分③④⑦s ⑤⑥ 7分2、证明： (1)(5分)(a,b)R(a,b)自反性成立自反性。对于 (a,b)R(a,b)自反性成立对称性。对于 (a,b),(c,d)A,如果(a,b)R(c,d),abcdcdab所以(c,d)R(a,b)对称性成立传递性。(a,b),(c,d),(x,y)A,如果(a,b)R(c,d), (c,d)R(x,y),abcd,cdxy,所以abxy,从而(a,b)R(x,y)传递性成立(2)A/R={{(0,0)},{(0,1),(1,0)},{(1,3),(2,2),(3,1)},{(2,3)}}(2分)3、证明：(每步各2分)S不空：G,是群，设e是G,的单位元，那么yG,都有eyye,eS,所以S不空。x1,x2S,那么对于 yG, 都有x1y