2018年10月高等教育自学考试全国统一命题考试离散数学试卷课程代码02324

2018年10月高等教育自学考试全国统一命题考试离散数学试卷(课程代码02324)本试卷共4页，满分l00分，考试时间l50分钟。考生答题注意事项：.本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。.第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。.第二部分为非选择题。必须注明大、小题号，使用0.5毫米黑色字迹签字笔作答。.合理安排答题空间，超出答题区域无效。第一部分选择题一、单项选择题：本大题共15小题，每小题l分，共15分。在每小题列出的备选项中只有一项是最符合题目要求的，请将其选出。.下列命题公式为矛盾式的是A.Pf(PVQVR)B.(P-「P)f「QC.「(Q叶R)AR D.(PfQ)f(「Qf「P).命题公式A中含9个命题变项，A为重言式的条件是人的主析取范式含A.2“个极大项 B.1个极大项 C.2n个极小项D.1个极小项.设R为集合人上的关系，则下列叙述不正确的是A.2"个极大项 B.1个极大项 C.2n个极小项 D,1个极小项.设F(x)：x是兔子，G(y):y是乌龟，H(x,y)：x比y跑得快。命题“并不是所有兔子都比乌龟跑得快”可符号化为A.「三蠹(F⑴AVy(G(y)-H(%y)))我iVxVy(F(x)AG(y)fH(%y))3x3y(F(x)AC6)t必札y))D.f¥加(尸(#)Amy(G(y))).设集合乂={3{a}},则下列陈述不正确的是A. B. C.|aT|<i}}CXD..对罪空集合H和君，若AnB工儿则有A.捷E=0 =0 =0.设A={1,{1},{1,{1}}},则其幂集P(A^q元素总个数为A1 8.4C.8D.16.描述偏序集的是人.哈密顿图 B.哈斯图C.欧拉图 D.树.在整数集z上，下列定义的运算能构成一个群的是A.a*b=max{a,b}B.a*b=|a-b|C.a*b=a+b+1 D.a*b=ab10.设f：X-Y,,g:Y-Z是函数，则下列陈述不正确的是A.若f和g都是单射的，则f。g也是单射的B.若f和g都是双射的，则f。g也是双射的C.若g和f。g是满射的，则厂也是满射的D.若，和9都是满射的，则f。g也是满射的.由4阶3条边构成的无向简单图的结点最大度数为A.1 8.2C.3D.4.下列为一颗6阶无向树的度数列，对应不止一颗同构树的是A.1,1,1,1,2,4 B.1,1,1,2,2,3C.1,1,2,2,2,2 D.1,1,1,1,3,3.设有集合4 则下列描述不本知的是A.(4U8)UC=AU(BJ3)’b,au(snc)=(4un(4uC)c.an(J?uc)=(ans)u(4nc)D.4TBeC)(A-B)r\(A-C).下列关于整数集合上的小于关系性质描述不正确的是A.反自反的 B.对称的 C.反对称的 D.传递的.分别记Z、N、Q、R为整数、自然数、有理数、实数集合，下列关于普通加法的代数系统不是群的是A.<Z,+> B.<N,+> C.<Q,+>D.<R,+>第二部分非选择题二、填空题：本大题共10小题，每小题2分，共20分。.集合4={1,2,3,4,5},集合8=3,b,c,也0},现有从4到8的二元关系R={<1,b>,<3,e>,<5,P>},和从8到4的二元关系S={<b,4>,<a,5>,<c,2>},则R。S=,S。R=。.命题公式(rP-Q)l(PArQ)的成真指派为，成假指派力.公式(三人)((P(孙y)fQ(z))VR(z))的约束变元为，自由变元为.设4= ，4=[1,2,31,贝ijMx创=,14xP(B)l=。.设实数集合上的函数/(%)=d,g⑴=2%+1,那么复合函数/。或%)= 反函数g「"切 _ ..O2L有理数集Q中的运算*定义如下：a*6=a+6+而，贝IJ*运算的单位元为；设a有逆元，则其逆元J为o22.<Zn,+>是一个群，其中Z*=[0,1,2,…,nT],x+y=(x+y)modn,则在<Z6t+>中,1的阶为,2的阶为o.设5阶简单连通图G所有结点的度数之和为18,则G的结点的最大度数为,最小度数为O.下图的格中,6的补元是 ,c的补元是 o.设二元关系美={<2,5>,<3,5>,<3,4>1,5=1<1,3>,<2,5>,<3,4>],那么dom(4ClB)=,ran(AuB)=。三、计算题：本大题共5小题，每小题6分，共30分。.研究4阶完全图兄,判断其是否存在欧拉回路?是否存在哈密顿回路？如果存在，共有多少个非同构的回路？.构造命题公式(尸一「Q)AR的真值表。.给出集合4=口,2,3|上所有等价关系的个数，并列出这些关系的集合表达式。.求命题公式「(PV(QAR))的主析取范式和主合取范式。.集合集={。力山4人上有偏序关系也={<a,d〉，<a,c>,<a,b>,〈a,e>，<b,e>,<c,e>,<d,e>(U"o(1)画出偏序集〈A,K〉的哈斯图；(2)找出A的极大元、极小元、最大元和最小元。四、证明题:本大题共3小题，每小题7分洪21分。.设Z是整数集合，在Z上定义二元运算*如下：Vx,yeZ,**y=%+y_2证明Z关于运算*构成群。.设4=| 为正整数]，在4上定义二元关系〜如下：〜<%”>当且仅当a+d=b+c。证明〜是一个等价关系。.在9阶无向图G中,每个结点的度数不是5就是6,证明G中至少有5个6度结点或至少有6个5度结点。五、综合应用题：本大题共2小题，每小题7分，共14分。.某研究所要从3名科研人员A、B、C中挑选1―2人去进修，由于工作需要，选派时需要满足下列条件：(1)若A去，则C同去；(2)若B去，则C4能去；(3)若C不去，则A或8可以去。问：如何确定选派方案？.某地区5个居民点之间现有道路距离见下列邻接矩阵（单位：千米）：「0 512145nTOC\o"1-5"\h\z5 0 9 11 812 9 0 6 1014 11 6 0 7L5 8 10 7 0二现需利用现有道路铺设天然气管道。假定铺设戒本完全由距离决定，试用最小生成树规划最低成本管道铺设方案，并确定该方案下总的铺设长度。绝密★启用前2018年10月高等教育自学考试全国统一命题考试离散数学试题答案及评分参考（课程代码02324）一、单项选择题（本大题共15小题,每小题1分，共15分）1.C 2.C 3.D 4.B 5.D6.A 7.C 8.B 9.C 10.C11.C 12.B 13.D 14.B 15.B二、填空题（本大题共10小题,每小题2分，共20分）16.|<1,4>|, j<afe>|18.x,yfz20.1+2x2, (”-1)/217.00JO.01JI19.6, 1621.0, --*a+122.6, 324.a,c,b.d23.4, 325.123, 13,4.51三、计算题（本大题共5小题,每小题6分，共30分）26.解:对于4阶完全图七，每个结点的度数均为3,为奇数,四而不存在欧拉回路,（2分）4阶完全图&中存在哈密顿回路。 （2分）而且存在3个不同构的哈密顿回路。 （2分）（列表得2分,基本正确得4分,完整得6分）离散数学试题答案及评分参考第I页（共4页）TOC\o"1-5"\h\z.解:A上的等价关系共有5个 （I分）它们分别是：凡=|〈1.2〉，〈2,l〉，〈l,3〉，〈3.l〉，〈2,3〉，〈3.2〉|Uh （1 分）R2=｛《2,3〉，〈3,2〉|5a （I 分）R3=|<1,3>,<3,1>|UIA （1 分）R4=|<1,2>,<2,1>|u1a （1 分）R5=ia （1分）.解：（1）主析取范式r（PV（QAK））PA（rQVrR）=5PAr0）V5PArR）O（rOAK）V5PArQArA）V5PAQArA）或omgVmoo,Vm010 （3分）（2）主合取范式由主析取范式可得.r（PV（QAK））]AMiqqA-W|Q]AM“oAM”]（3分）（3分）0（尸QVrR）A（rPVQVR）A（r尸VQV-R）A（「PVrQVK）（3分）（3分）.解：（1）哈斯图答30答30图（2）A的极大元:e（3分）极小元:a最大元:e最小元:（3分）离散数学试题答案及评分参考第2页（共4页）四、证明题（本大题共3小题，每小题7分，共21分）TOC\o"1-5"\h\z.证明：V4,yeZ,**y=x+y-2eZ,因而*运算是封闭的。 （2分）显然，*运算可结合，且单位元e=2。 （2分）VaeZ,由（a*a'）=a+a'-2=e=2,可得a1=4-a （2分）即任一元素均存在逆元。综上,Z关于运算*构成群。 （1分）.证明：⑴自反性 （2分）又寸V<a,b>e4,^a+6=a+4.所以<a.b>〜<a,b>0故〜具有自反性°（2）对称性 （2分）设<a,6>〜<c,d>.贝ij有a+d=b+c,亦即c+b=d+a.所以<c,d>〜<q,6>。故〜具有对称性。（3）传递性 （2分）设<a,b>〜<c,d>且<c,d>〜<e./〉.则有a+d=b+c,c+f=e+d,上述两式两边分别相加后消去c+d,从而有a+/=6+e。所以<a,b>〜<e./>o故〜具有传递性。综合（1）（2）（3）,〜是一个等价关系。 （1分）TOC\o"1-5"\h\z.证明：（1）假设C中至少有5个6度结点，则结论成立。 （2分）（2）如果C中至多只有4个6度结点,由于每个结点的度数不是5就是6,则至少有5个度数为5的结点,而奇度数结点不能为奇数个.因而这时C中度数为5的结点应当有6个或8个，即至少有6个5度结点。 （4分）综合（1）和（2）,结论成立。 （1分）五、综合应用题（本大题共2小题，每小题7分，共14分）

34.解:符号化.设p：派A去，

g：派B去，

r：派C去，

由已知条件可得：

（p—r）A（g-rr）A（r「一（pVg）） （2分）TOC\o"1-5"\h\z经等值演算可得（p-*r）A（q—>rr）A（~»r-（pVg））0（rpA-«gAr）V（-»pAgA-»r）V（pAigAr） （2 分）因此，有3种选派方案：（1）C去.A和B都不去； （I分）（2）B去,A和C都不去； （1分）（3