南昌大学本科离散试卷及答案(8页).doc
-南昌大学本科离散试卷及答案-第 8 页南昌大学20072008学年第一学期期末考试试卷试卷编号：( B)卷课程编号：课程名称：离散数学考试形式： 闭卷适用班级：姓名：学号：班级：学院：专业：考试日期：题号一二三四五六七八九十总分累分人 签名题分2080 100得分考生注意事项：1、本试卷共4页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更换。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、 填空题(每题4 分，共 20 分)得分评阅人 1、使得公式q(pq)p成真的赋值是：使得公式q(pq)p成假的赋值是：2、设A=ía,bý，B=í1,2,3ý，求：A×B=B×A=3、一棵无向树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=í<1,2>,<2,4>,<3,3>ý S=í<1,3 >,<2,4>,<4,2>ý 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,5ý，A上的等价关系R定义为：R=í<1,2>,<2,1>,<3,4>,<4,3>ý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卷答案一填空题1成真的赋值是：00，10，11成假的赋值是：012、A×B=í<a,1>,<a,2>,<a,3>,<b,1>,<b,2>,<b,3>ýB×A=í<1,a>,<1,b>,<2,a>,<2,b>,<3,a>,<3,b>ý3、T有9片叶子4、约束变元：x，y，z，自由变元：x，y5、í<1,2>,<1,3>,<3,3>,<4,2>ý二、综合题1、p(qr)ÛØp(Øqr)(条件等价式)Û(ØpØq)r(结合律)ÛØ(pq)r(德·摩根律)Û(pq)r2、(pq)rÛ(Øpq)rÛ(Øpqr)(ØpqØr)(Øpr)(pr)Û(Øpqr)(ØpqØr)(Øpqr)(ØpØqr)(pqr)(pØqr)Û(Øpqr)(ØpqØr)(ØpØqr)(pqr)(pØqr)Û0,2,4,5,6使得命题公式(pq)r成假的赋值是：000,010,100,101,110。3、（1）设R(x)：x是人。S(x)：x要休息。“凡是人都要休息。”符号化为：("x)(R(x)S(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)×47×3(56)×3(89)×2=116。8、解：按题意构造一个二部图G=<X,E,Y>，其中X=í p1，p2，p7ý，Y=ía1，a2，a10ý，E表示合格工作岗位关系。如图所示。在图中可以求得一个最大匹配：M=í(p1,a9),(p2,a2),(p3,a6), (p4,a3),(p5,a4),(p6,a1),(p7,a5)ý
