2019年4月离散数学自考试题及参考答案

书书书!#$!%&%’离散数学试题(第)((((页共’页#!#$!%&%’通卡#绝密!启用前%)*年’月高等教育自学考试全国统一命题考试离散数学(试卷课程代码%&%’#注意事项$)+本试卷分为两部分%第一部分为选择题%第二部分为非选择题&%+应考者必须按试题顺序在答题卡纸#指定位置上作答%答在试卷上无效&&+涂写部分’画图部分必须使用%,铅笔%书写部分必须使用黑色字迹签字笔&第一部分(选择题一’单项选择题$本大题共)-小题%每小题)分%共)-分%在每小题列出的备选项中只有一项是最符合题目要求的%请将其选出&)+令!$下午下雨%$我去公园%#$家里来客人%则命题&若下午不下雨%我就去公园%除非家里来人’的符号化形式为!+(!#,+(!(#.+(!(###/+(!###%+令$%#$%是火车%&’#$’是汽车%(%%’#$%比’快%则命题说&火车都比汽车快是不对的’的符号化形式为!+$%$’$%#&’###(%%’#,+($%$’$%#&’###(%%’#.+($%$’$%#&’#(%%’##/+%%%’$%#&’###(%%’#&+设&是有)个结点%*条边的连通图%要确定&的一棵生成树%必须删去&的多少条边)!+*0)1),+*0).+*1)1)/+)0*1)’+一个#阶无向简单图%其结点的最大度数为!+-,+2.+#/+$-+下列可以作为’阶无向简单图的结点度数序列是!+)%%%&%’,+%%%%%&.+)%)%%%%/+)%&%&%&2+下列关于二元关系#的逆关系#0)的性质%不成立的是!+#0)#0)3#,+456#0)3789#.+789#0)3456#/+#)&#%#0)3#)’#%#+设&为#阶无向简单图%下列命题中可成立的是!+&的每个结点的度数均为&,+&的每个结点的度数均为-.+&的每个结点的度数均为2/+&的每个结点的度数均为#!#$!%&%’离散数学试题(第%((((页共’页#$+集合+和,%其幂集分别为!+#和!,#%下列关系不成立的是!+:!+#:3%:+:,+:!,#:3%:,:.+!+’,#3!+#’!,#/+!+&,#3!+#&!,#*+包含)个命题变项的重言式的主析取范式包括有小项的个数为!+%),+%).+)/+)+设;-%(是一个有界格%下列叙述中%正确的是!+每个元素都有补元,+每个元素都没有补元.+至少有两个元素有补元/+最多有一个元素有补元))+下列关于图的命题正确的是!+欧拉图都是哈密顿图,+哈密顿图都是欧拉图.+’阶以上完全图都是欧拉图/+’阶以上完全图都是哈密顿图)%+一个)阶图不一定是树的为!+无回路的连通图,+无回路且有)0)条边.+)阶连通图/+有)0)条边的连通图)&+集合+上有两个二元关系#)与#%%.*/*0分别代表自反*对称和传递闭包%下列不成立的恒等式为!+.#)&#%#3.#)#&.#%#,+/#)&#%#3/#)#&/#%#.+.#)’#%#3.#)#’.#%#/+0#)&#%#30#)#&0#%#)’+集合+上的二元关系#和1都是自反关系%下列不是自反关系的为!+#0),+#’1.+#&1/+#01)-+下列-阶图中为哈密顿图的是ABCD!#$!%&%’离散数学试题(第&((((页共’页#第二部分(非选择题二’填空题$本大题共)小题%每小题%分%共%分&)2+下面的*阶无向图%需要添加边使其成为欧拉图%至少需要添加和+123698547)#+在实数域中%命题公式$%%’%!’3#的真值为%命题公式%%$’%!’3)#的真值为+)$+设集合+3,)%%%&%’%-%2-%集合,3,%:%3)%1)%))(%%;%-%则+&,3+)*+谓词公式%%%’$%%’##%2&%%’%2#的前束范式为+%+设集合+3,)%%%&%’%-%2%#%$%*%)-%二元关系#3,;%%’:%%’)+%%是’的因子%%;--%则456#3%789#3+%)+一颗#阶树%其分支结点最多有个%最多有片树叶+%%+对集合+上的恒等关系3+%和全域关系4+%如果:+:3)%那么:3+:3%:4+:3+%&+下图给出了一个格-%那么5的补元是%全上界是+edcba%’+对#阶无向简单图&%其最多有条边+%-+谓词公式$%!%##%’’##*#’#中%$%的辖域是%自由变元是+三’计算题$本大题共-小题%每小题2分%共&分&%2+用列真值表的方法说明下列逻辑等价式成立!*####+!######%#+求命题公式!*(!######的主析取范式+%$+根据关系的性质%填写下表具备该项性质填写&,’%不具备该项性质填写&=’#(((((性质关系(((((自反的对称的传递的相等关系全域关系!#$!%&%’离散数学试题(第’((((页共’页#%*+(为自然数集合%设6$7=7#7%6;%%’#3%1’1)+)#说明6是否为单射*满射*双射.%#令+3,;%%’:%%’)(且6;%%’#3&-%求++&+如题&图所示有向图8%求其长度为’的通路总数%并指出其中回路有几条)v1v4v3v2四’证明题$本大题共&小题%每小题#分%共%)分&&)+)为实数集%$%%’))%证明%1’368%%’#16?9%%’#&%+设在实数集)上有运算-%定义为$9%:))%9-:391:1%9:证明;)%-是群%并求出其单位元和)中任意元素9的逆元+&&+证明下列谓词公式为永真式$%$%#*%’&’###(%’&’###$%$%##五’综合应用题$本大题共%小题%每小题#分%共)’分&&’+某开发区有新建的-个工厂%相互之间的距离由下列矩阵表示单位为千米#)2#-2)22*$#2)&))-*)&’2$))’现要架设供电线路+请找出最短的供电线路铺设方案%并算出该方案的线路长度+&-+对任意集合+*,*;%推导出下列集合等式成立的充要条件)#+0,#&+0;#3+%#+0,#&+0;#3.离散数学试题答案及评分参考(第)((((页共&页#绝密!启用前%)*年’月高等教育自学考试全国统一命题考试离散数学试题答案及评分参考课程代码%&%’#一’单项选择题本大题共)-小题%每小题)分%共)-分#)+.((%+,((&+!((’+,((-+.((2+/((#+.(($+/((*+!(()+.))+/(()%+.(()&+/(()’+/(()-+!二’填空题本大题共)小题%每小题%分%共%分#)2+%’%2$本题答案不唯一%还可以是%2%’$#)#+@%A)$+,)%%%&%’%-%2%)%)#-)*+$%$’$2$%%’##&%=%2##注$*=可以自行命名#%+,)%%%&%’-%,)%%%&%’%-%2%#%$%*%)-或+%)+-%2%%+)%)%%&+:%%’+%)%-+!%##%’’#%#’#中的’+三’计算题本大题共-小题%每小题2分%共&分#%2+解$分别列出两个命题公式的真值表如下!#!*!*###!####!######))))))))))))))))))))))))))))))))))))))))从真值表可见%!*###与!######的真值完全相同%因此有!*####+!######真值表’分%最后结论%分#%#+解$!*(!######+!*!*##(*##%分#………………………………………………………………………+!(#*!##*##%分#…………………………………………………………………+!##*!(##*!((##*(!##%分#………………………………离散数学试题答案及评分参考(第%((((页共&页#+*)))**))**)**))%$+(((((性质关系(((((自反的对称的传递的相等关系,,,全域关系,,,每空)分#%*+解$)#易见6;%%$&%%#32故6不是单射的.)分#……………………………………………………………………………………又6/%故6不是满射的.)分#…………………………………………………………………………从而6不是双射的.)分#…………………………………………………………………………………%#使6;%%’#3&的序对只有;)%)%;%%%;%%%分#…………………………………于是+3,;)%)%;%%%;%%-)分#……………………………………………………………&+解$由题&图可得图8的邻接矩阵?83)))))))%分#…………………………………………………………………………………由矩阵乘法可得到?’83)&%&))%)%%%’)&’-%分#…………………………………………………………………………………可见8中长度为’的通路共有&#条%其中回路有*条+%分#………………………………………四’证明题本大题共&小题%每小题#分%共%)分#&)+证明$根据%%’的取值情况%可以列出下表可能情况68%%’#6?9%%’#68%%’#16?9%%’#%0’%’%1’%;’’%%1’由上表可见%无论出现何种情况%68%%’#16?9%%’#均与%1’相等+-分#……………………因此%在实数范围内%1’368%%’#16?9%%’#成立%分#…………………………………………………………………………………………………&%+证明$)#$9%:))19-:391:1%9:))因此%运算-是封闭的+%#$9%:%5)))分#………………………………………………………………………………9-:#-5391:151%9:1%:51%951’9:59-:-5#391:151%9:1%:51%951’9:539-:#-5因此运算-是可结合的+&#$9))19-391139%分#…………………………………………………………离散数学试题答案及评分参考(第&((((页共&页#因此是;)%-的单位元+综合)#%#&#%;)%-是群%%分#………………………………………………………$9))%9-09)1%939093%即9的逆元为09)1%9%分#…………………………………&&+证明$利用谓词等值式和换名规则原式+$%$%#*%’&’###(%’&’###$%$%##%分#………………………………………+$%%’$%#*&’###%&#*$=$=##%分#…………………………………………+$%%’$%#*&’###$%%’$%#*&’##%分#…………………………………………+@)分#五’综合应用题本大题共%小题%每小题#分%共)’分#&’+解$)#先画出-个工厂的相互距离情况如答&’图0)所示a1667856411913bcde%#根据B7CDE8F算法%可得答&’图0)的最小生成树@如答&’图0%所示baedc6745此即最短的供电线路铺设方案+’分#……………………………………………………………&#可以算出答&’图0%所示的线路长度为A@#3’1-1#123%%千米#)分#………………&-+解$)#+0,#&+0;#3+’G,#&+’G;#3+’G,&G;#3+’G,’;#3+0,’;#%分#…………………………………………因此%当且仅当+’,’;3.时%+0,#&+0;#3+%分#……………………………………%#由)#可知$+0,#&+0;#3.++0,’;#3.++2,’;#%分#…………………………………………………………………………………因此%+0,#&+0;#3.的充要条件是+2,’;#)分#……………………………………