南昌大学本科离散试卷及答案.doc

《南昌大学本科离散试卷及答案.doc》由会员分享，可在线阅读，更多相关《南昌大学本科离散试卷及答案.doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品文档，仅供学习与交流，如有侵权请联系网站删除南昌大学20072008学年第一学期期末考试试卷试卷编号：( B)卷课程编号：课程名称：离散数学考试形式： 闭卷适用班级：姓名：学号：班级：学院：专业：考试日期：题号一二三四五六七八九十总分累分人 签名题分2080 100得分考生注意事项：1、本试卷共4页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更换。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、 填空题(每题4 分，共 20 分)得分评阅人 1、使得公式q(pq)p成真的赋值是：使得公式q(pq)p成假的赋值是：2、设A=a,b，B=1,2,3，求：AB=BA=3、一

2、棵无向树T有2个4度结点，3个3度结点，其余的结点都是树叶，问T有片树叶?4、指出公式(z) (P(x)($x)R(x,z)($y)Q(x,y)R(x,y)中的约束变元和自由变元。5、.A=1,2,3,4，A上二元关系R和S分别为：R=, S=, RS =二、综合题(每小题10分，共 80 分)得分评阅人 1、用等价演算证明：p(qr)(pq)r2、求命题公式(pq)r的主合取范式并求命题公式的成假赋值3、将下列命题符号化。并讨论它们的真值（1）凡是人都要休息。（2）每个自然数都有比它大的自然数。4、用CP规则证明。 (x)(F(x)R(x)(x)F(x)(x)R(x)5、设A=1,2,3,4

3、,5，A上的等价关系R定义为：R=,IA画出关系图，找出所有等价类，总结等价类和关系图的关系。.6、无向图G如图所示。 写出G的邻接矩阵。 求G中长度为3的路的总数，其中有多少条回路。 求G的连通矩阵。7、求带权3,4,5,6,7,8,9的最优二叉树T。8、某单位按编制有7个工作空缺：p1，p2，p7，有10个申请者：a1，a2，a10。它们能胜任的工作集合依次是p1, p5, p6，p2, p6, p7，p3, p4，p1, p5，p6, p7，p3，p2, p3，p1, p3，p1，p5。如果规定每个申请者最多只能安排一个工作。试给出一种方案使分配到工作的申请者最多。离散数学B卷答案一填空

4、题1成真的赋值是：00，10，11成假的赋值是：012、AB=,BA=,3、T有9片叶子4、约束变元：x，y，z，自由变元：x，y5、,二、综合题1、p(qr)p(qr)(条件等价式)(pq)r(结合律)(pq)r(德摩根律)(pq)r2、(pq)r(pq)r(pqr)(pqr)(pr)(pr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)0,2,4,5,6使得命题公式(pq)r成假的赋值是：000,010,100,101,110。3、（1）设R(x)：x是人。S(x)：x要休息。“凡是人都要休息。”符号化为：(x)(R(x)S(

5、x)它的真值为：真。 （2）解：设N(x)：x是自然数。G(x,y)：x比y大。“每个自然数都有比它大的自然数。”符号化为：(x)(N(x)($y)(N(y)G(y,x)它的真值为：真4、证明：(x)F(x)P(附加前提)F(c)US(x)(F(x)R(x)PF(c)R(c)USR(c) T假言推理(x)R(x)UG(x)F(x)(x)R(x)CP5、解：R的关系图如图4.34所示。1R=2R=1,2，3R=4R=3,4，5R=5关系图每一个连通分支的结点构成的集合是一个等价类。或者说，每一个等价类导出了关系图的一个连通分支。6、解：邻接矩阵（2） A=，A2=A3=长度为3的路的总条数66条，其中回路12条。（3） C4= A0+A1+A2+A3=，G的连通矩阵为P=7、最优树的权为：W(T)=(34)473(56)3(89)2=116。8、解：按题意构造一个二部图G=，其中X= p1，p2，p7，Y=a1，a2，a10，E表示合格工作岗位关系。如图所示。在图中可以求得一个最大匹配：M=(p1,a9),(p2,a2),(p3,a6), (p4,a3),(p5,a4),(p6,a1),(p7,a5)【精品文档】第 7 页