河南科技大学考研真题652离散数学答案2013.doc

河南科技大学2013年硕士研究生入学考试试题答案及评分标准考试科目代码： 652 考试科目名称： 离散数学 一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的备选项中只有一个是符合题目要求的，错选、多选或未选均无分。1-5：B A A D C 6-10：D A B B A 11-15：B D B B D二、填空题(本大题共10小题，每小题2分，共20分)1. 1或真2. 01，10 3. 反对称 、 传递 4. 5. 6. 7. 3 、 1 8. 9. 1 10. 三、计算题(本大题共5小题，每小题8分，共40分) 1利用等值演算化简命题公式A，并指出A的类型(注：重言式、矛盾式或可满足式)A=解：A= (1分) (1分) (1分) (1分) (1分) (1分)所以，A是可满足式 (2分) 2设f是一元运算，P是一元谓词，Q是二元谓词，给出解释I：D=2, 3，f(2)=3，f(3)=2，P(2)=1，P(3)=0，Q(2, 2)=Q(3, 3)=1，Q(2, 3)=Q(3, 2)=0，求在解释I下xy(Q(f(x), y)P(x)的真值。 解： (2分) (2分) (2分) (2分) 3设为偏序集，其中A=1,2,3,4,5,6，R是A上的整除关系。(1) 写出偏序关系R的表达式，并画出的哈斯图； (2) 求该偏序集的最大元、最小元、极大元和极小元； 解：(1) (2分) 哈斯图如下：(2分) (2) 无最大元 (1分)最小元是1 (1分)极大元是4，5，6 (1分)极小元是1 (1分) 4设S=QQ，其中Q是有理数集合，在S上定义二元运算：有：=。求代数系统(S,)的单位元和S中可逆元素的逆元。解：(1)设单位元e=，有 (1分)即=及= 得到： (2分) (1分)(2) ，其逆元记作，有， (1分)即 (2分)求得：x=，y= 对任意S，只要a0，那么的逆元为 (1分) 5. 已知图，的邻接矩阵为 (1) 画出G中所表示的图形； (2) G中长度为3的通路有几条？其中回路有几条？ 解：(1) G的图形如下：(2分) (2) 经计算知： (2分) (2分) 因此，G中长度为3的通路有72条，其中回路是0条。 (2分)四、证明题 (本大题共3小题，每小题10分，共30分)1在一阶(谓词)逻辑中符号化下列语句，并构造推理证明。 学术委员会的每个成员都是博士并且是教授。有些成员是年轻人。因而有的成员是青年教授。证明：先将简单命题符号化：(2分) 设F(x)：x是学术委员会成员，G(x)：x是教授，H(x)：x是博士，R(x)：x是青年人 前提：， 结论： 推理证明如下： (1) 前提引入 (2) (1)EI (1分)(3) 前提引入(4) (3)UI (1分)(5) (2)化简 (1分)(6) (4)(5)假言推理 (1分)(7) (6)化简 (1分)(8) (2)化简 (1分)(9) (5)(7)(8)合取 (1分)(10) (9)EG (1分)2如果集合A上的关系R和S是自反的、对称的、传递的，证明：RS是A上的等价关系。证明：(1) ，由R、S自反知：，则自反； (3分) (2) ，若，则，由R、S对称知：则对称； (3分)(3) ，若，由R、S的传递性知：则传递； (4分) 综上可得是A上的等价关系。 3. 设S=R-1(R为实数集)，a*b=a+b+ab。证明：是群。证明：(1) ，所以*运算封闭； (2分) (2) ，所以，*满足结合律； (2分) (3) 设S关于*有幺元e，有；(3分) (4) 设有逆元，有，即任意元有逆元； (3分) 综上得出，是群。五、应用题(本大题共2小题，每小题15分，共30分)1一航空公司采用三台计算机复核飞行计划以确保其安全性，每台计算机能给出飞行计划正确或错误的回答，由所给的答案，再根据“少数服从多数”的原则做出判断。试将结果用命题公式表示，并加以简化，画出相应的逻辑电路图。(门电路示意图如图5.1所示) 图5.1解：设p、q、r分别表示三台计算机的答案，S表示判断的结果(1) 根据题意，建立其真值表 -（4分）pqrS00000010010001111000101111011111(2) 根据真值关系写出S的命题公式 -（3分）S=(pqr)(pqr)(pqr)(pqr)(3) 利用等值演算化简S得 -（3分） S(qr)(pr)(pq)(4) S的逻辑电路图 -（5分）2假设有6个网络节点(i=l，2，6)，欲铺设光纤线路使各网络节点可连通，如图5.2所示，图中的边代表铺设线路，边上的数字表示铺设该线路所需费用。由于费用的限制，要求总的铺设费用最低并确保任意二个网络节点之间是可连通的，请写出求解过程，画出符合要求的最低费用的网络线路铺设图并计算其费用。图5.2 解： (1) 显然该问题是求带权无向图的最小生成树(用Kruskal算法-避圈法)，去掉顶点V