离散数学卷-参考答案

《离散数学卷-参考答案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、离散数学模拟卷2参考答案一、选择题1、请指出下列选项中哪一个是错谋的：(2)(1)0C0(2)060⑶0C{0}(4)0G{0}2、对任意集合下述论断正确的是：(1)(1)若恥B,BuC,则ay⑵若则AuC(3)若AuSBwC,则A*⑷若AaB9BeCfWlJAcC3、假设A二{d#,c}上的关系R={}f那么，r是:⑴)(1)反自反的(2)反对称的(3)可传递的(4)不可传递的4、非空集合A上的空关系/?不具备下列哪个性质：(1)(1)白反性(2)反白反性(3)对称性(4)

2、传递性5、若f：ATB,g:BTC是满射函数，则复合函数必是：(3)(1)双射函数(2)单射函数(3)满射函数(4)不单射也不满射6、假设人二{d"，c},B={1,2]下列哪个关系是4到〃的函数：(3)(])于={vg,1xa,2>}⑵f={<>}(3)/={vd，lxb,2〉vc,l>}(4)/={vl，ax2,bxl,c>}7、一个无向简单图G有加条边，农个顶点，则图中顶点的总度数为：(3)(1)(2)(3)2m(

3、4)2nX、一个图是哈密顿图是指：(3)(1)图小包含-•条回路经过图小每条边一次且仅一次；(2)图中包含一条路经过图中每条边一次且仅一次；(3)图中包含一条回路经过图中每个顶点一次H.仅一次；(1)图屮包含一条路经过图中每个顶点一•次且仅一次。9、一•棵树有2个2度顶点，1个3度顶点，3个4度顶点，则其1度的顶点数为：(2)(1)5(2)7(3)8(4)910、完全加叉树中有/片叶，「个分支点，则有关系式是：(2)(Dz=Z-1(2)(m-1)/+1=/(3)(血_“=!(4)(m-1)/=z-1二、填空题1

4、、假设A={{a,b},{c}},B={{a}y[h},{c}}试求出：A的幕集p(A)=2、假设A={xx2<30,xe正整数},B=(xx是正奇数，xv20},C={1,3,5}(1)(C—A)IJ(3—A)={7911,13,15,17,19}；(1)(BnC)-A=0；3、假设A={1,2,3,4}上的关系R={<2,3>},M：(1)r(R)二{v1,1>,<2,2>,v2,3>,v3,3>,v4,4>}；(2)s(R)={v2,3>,v3,2>h(3)”R)={v2,3>}；4、假设A={1,2

5、,3},仁g、h是A到A的函数，其中:(a)/⑴=/(2)=/(3)=1；(b)g⑴=1,g⑵=3,g(3)=2；(c)/?(1)=3,/z(2)=/?(3)=1；则:(1)丄是满射；(2)―是双射；5、设无向图G有36条边，冇6个3度的顶点，其余顶点度数均小于3,则G中至少有辽个顶点。6、假设P：今天天气好，Q：我就去锻炼身体。(1)命题“如果今天天气好，我就去锻炼身体”符号化为Pz±Q；三、假设A、B是任意两个集合，证明：p(A)np(B)=p(AnB)o证明:对0Xwp(A)Dp(B)，则Xgp(A)且X

6、wp(B)所以XUA并且XuB由交集的定义，则XuACB所以X丘p(AAB)因此p(A)np(B)cp(AnB)反之，假设WXep(AnB)则XcAAB所以XuA并门X^B所以X丘p(A)且Xwp(B)由交集定义,则X"(A)rip(B)故p(AnB)cp(A)Ap(B)综上p(A)n/7(B)=p(Ane)四、证明定义在实数集合/?上的关系S二｛vX』〉

7、兀,yW/?,□是整数｝是一个等价关系。证明：对VxeR，贝

8、J3是整数，所以s是白反的；x-y=对Fx、y*R,并且设v%,y>wS,则3$是整数丿_兀二

9、而39也是整数，所以vy，%>ws,s是对称的；对Vx,y,zeR并几设v%,y>wS,vy,z>wSx-yy-z=q=r则3,3,9"是整数；_x-y^y-z_x-yy-z_■——I=q七f而3333也是整数所以vx,z>wS因此S是传递的综上，S是等价关系。五、对下列集合在整除关系下构成的偏序集，画出Hasse图，并写出最大元，最小元,极大元，极小元。(1)人二{2,3,6,12,24,36}(2)4二{1,2,3,5,6,10,15,30}(3)A3={1,3,6,9}解：(1)无最大元，极大元为：24,

10、36；无最小元，极小元为：2,3；(2)最大兀和极大兀为：30；［小元和极小元为:(3)无最大元,极大元为：6,9；最小元和极小元为：1(1)155(3)六、设无向图G中有9个顶点，每个顶点的度数不是5就是6,试证明G中至少有5个6度顶点或至少有6个5度顶点。解：假设图G中最多有4个6度顶点，并且最多有有5个5度顶点则度为奇数的顶点只能为偶数个，所以5度顶点应该为4个，而6度顶点最多也