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

1/6南昌大学2007～2008学年第一学期期末考试试卷试卷编号：(B)卷课程编号：课程名称：离散数学考试形式：闭卷适用班级：姓名：学号：班级：学院：专业：考试日期：题号一二三四五六七八九十总分累分人签名题分2080100得分考生注意事项：1、本试卷共4页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更换。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、填空题(每题4分，共20分)得分评阅人1、使得公式q∧(p→q)→p成真的赋值是：________使得公式q∧(p→q)→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RS=____________________2/6二、综合题(每小题10分，共80分)1、用等价演算证明：p→(q→r)(p∧q)→r2、求命题公式(p→q)∧r的主合取范式并求命题公式的成假赋值3、将下列命题符号化。并讨论它们的真值（1）凡是人都要休息。（2）每个自然数都有比它大的自然数。得分评阅人3/64、用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的连通矩阵。4/67、求带权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→(q→r)p∨(q∨r)(条件等价式)5/6(p∨q)∨r(结合律)(p∧q)∨r(德·摩根律)(p∧q)→r2、(p→q)∧r(p∨q)∧r(p∨q∨r)∧(p∨q∨r)∧(p∨r)∧(p∨r)(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∏0,2,4,5,6使得命题公式(p→q)∧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))P⑷F(c)→R(c)US⑶⑸R(c)T⑵⑷假言推理⑹(x)R(x)UG⑸⑺(x)F(x)→(x)R(x)CP5、解：R的关系图如图4.34所示。[1]R=[2]R=1,2，[3]R=[4]R=3,4，[5]R=5关系图每一个连通分支的结点构成的集合是一个等价类。或者说，每一个等价类导出了关系图的一个连通分支。6、解：⑴邻接矩阵0011001111011110（2）A=0011001111011110，A2=00110011110111100011001111011110=2211221111321123A3=00110011110111102211221111321123=2255225555455554长度为3的路的总条数66条，其中回路12条。6/6（3）C4=A0+A1+A2+A3=5477457777887788，G的连通矩阵为P=11111111111111117、最优树的权为：W(T)=(3＋4)×4＋7×3＋(5＋6)×3＋(8＋9)×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)