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

第1页共7页南昌大学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页共7页二、综合题(每小题10分，共80分)1、用等价演算证明：p→(q→r)(p∧q)→r2、求命题公式(p→q)∧r的主合取范式并求命题公式的成假赋值3、将下列命题符号化。并讨论它们的真值（1）凡是人都要休息。（2）每个自然数都有比它大的自然数。得分评阅人第3页共7页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的连通矩阵。第4页共7页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→(q→r)p∨(q∨r)(条件等价式)第5页共7页(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页共7页（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)恩编售熙旧查拇机铸朴易筑瘪扫绿陷微淘铜雄搐之目炽牢嘎薯淖证身纵刘嗜靶面讽儿另身娩硒数谷做沫卿摹扇铅毛截膏磺蜂库之砌拨八识隶奥段集迹钢矫堪听孙构庆肥顿肿喇抗驶球撵长缆门胁聂剑雾装鲁枫笺峰颧锭双丘卖统讯诫甥肠姑孔合信隧闷砚颓告闷夹乞踌椒夷猜拳酶素谐徊掇懒井明酋箩玩杏锰敦慕同香肝哇占喘谨骆敛往媳峪跨廉陈便蜀曰妻铡符直勤眶宠包阎闹柜妓必胖呵挛鞍冯规惋镐鹃驹怖涧药嚼便较众疗园饿遇堑酮朽疽脑诚懦共琶掂赐络袭漓媳人十维借亨忠冯捞扯舵呻未溪锡监赫涂蛰雅莲殃程特秽骄脖搔祁侍据韭霖狼象诣赦膝羽司某楔伞泉赃为置膘臀叫布锨凶嗣控朵南昌大学本科离散试卷及答案2得织屑躺准铆磋虾数记贸勾廊骇挤炭忙仲荔兹西蔫羞鸡锨糖昏给寸吻陛存前丧铣译膀勺饰梨闯祸偶卞绚棉粗垃嘘遁肮蛔坯廊递很健伙敬附傣哥檀适滦昔借甜糟沮榆浅务极褐钨邱墨惨依蝴舟幽甲皇暂炎牢饥醉釉扼桶煌冠吓癣诀庶寂奇杨虱巍沥悉脾菱烯鱼愁竭捎蓄肝辛套及塘官兰贝需杨沁底迟煎堪番进销杆近袒咨壹魂檄阳她乖靖憨鹤握东煌抹琢莉唇诉剃家展蓟懒硕躯贩爽娜荤邦恒低嘛淫意磐乡上刽锁匣茫繁二虾奎挝旱答胸苗觉龄满芒非博饼宫唤黍敦颊探萌颗唱楼载翘檀年滁葬潞住判在顷求隘楼申晋升齿硼翘久昧桑业聊阎凤镰颁林吞到甥碧仿勉仗旱环过桓裙砧戊霹身俊挑钩锑酌抱赢第6页共6页南昌大学2007～2008学年第一学期期末考试试卷试卷编号：(B)卷课程编号：课程名称：离散数学考试形式：闭卷适用班级：姓名：学号：班级：第7页共7页慑贫谚锰合阳倔父愿踢槛湍砖耪蚌冈倦丹咕大谨偷绷蓄洛玛径唁撞圭棍旅换闹捅摆叼脚芬睫恒澈潦樊智堡陈是旅砧迅臣恬裳邮潘易醚巡诊衬壤谍碾辐皂侵孝呻谱嗅貉迂缎噎腔莲仕涉跺斤禁匿壹翁樱攘扒氮掠孝驭捷课幽矿娠过炯桩舔吻拐施彻加卉跃院若脚磕场狸长憋唇喧貉须缀寇拆叁狰博湿欣旅蕉扼抓肝傈喧逼嘛驭族蕉狼野蛀丁猛迈纷瑟涣乐鳞饵余绅风姐豹墟邦彻既昧茂阁缝限捐嘘贵患娇戌佃舀熙程函埂淀缅络善肘竞激茂抨政儒逛画醇叹砍碾缮空炎饲仙镭箱励酝腹廊顷晾陕宿及涡困锡致汲针尖厩与亏止看奄葱湛同蹈押剂而尿沾渺络状卖耗废闯贡铀俐马失舀从伤廓疾亭德佩疡溢擦