《2013离散数学课程》模拟题答案

《离散数学》期末考试考点及模拟题答案一、考试题型及分值各种题型所占的比例：填空题10%，判断题10%，选择题20%，其它题型60%新出试卷按照如下各种题型所占的比例：填空题20%，判断题15%，选择题30%，其它题型35%二、考点1．命题逻辑熟练掌握命题及其表示;掌握常用联结词(¬、∧、∨、→、)的使用;熟练掌握命题公式的符号化;熟练掌握使用真值表判别命题等价的方法;掌握使用等价公式判别命题等价的方法;掌握重言式与蕴含式的概念及其判别方法;了解其他联结词的使用;了解对偶的概念;掌握求命题范式的方法;熟练掌握命题演算推理的基本理论。2．谓词逻辑熟练掌握谓词的概念及其表示;熟练掌握量词的使用;掌握使用谓词公式翻译命题的方法;掌握变元的约束;掌握谓词演算中等价式与蕴含式的判别;了解前束范式的求法;熟练掌握谓词演算推理的基本理论。3．集合与关系熟练掌握集合的概念和表示法;掌握集合的基本运算;掌握序偶与笛卡尔积的概念;熟练掌握关系及其表示;掌握关系的基本性质;了解复合关系和逆关系的概念;掌握关系的闭包运算;了解集合的划分和覆盖;掌握等价关系与等价类的概念;了解相容关系的概念;掌握各种序关系的概念。4．函数熟练掌握函数的概念;掌握逆函数和复合函数的概念;了解基数的概念;了解可数集与不可数集;了解基数的比较。5．代数结构掌握代数系统的概念;掌握n元运算及其性质;掌握半群、群与子群的概念;了解阿贝尔群和循环群的概念;了解陪集与拉格朗日定理;了解同构与同态的概念;了解环与域的概念。6．图论掌握图的基本概念；掌握路与回路的概念；熟练掌握图的矩阵表示;掌握欧拉图和哈密顿图的概念；掌握平面图的概念；了解对偶图与着色;熟练掌握树与生成树的概念;了解根树及其应用。（一）参考教材与网上资料复习（二）随堂练习或作业题在在新出试卷里有较大比例提高三、模拟试卷附后（请参考学习资料，找到或者做出解答）一、考试对象计算机学科中计算机科学与技术、软件工程等专业本科生。二、考试的性质、目的离散数学是随着计算机科学的发展而逐渐形成的一门学科，是近代数学的一个分支。在计算机科学中，它主要应用于数据结构、操作系统、编译原理、数据库理论、形式语言与自动机、程序理论、编码理论、人工智能、数字系统逻辑设计等方面。它是计算机科学各专业重要的专业基础课。本课程教学的目标是:①使学生掌握离散数学的基本理论和基本知识，为学习有关课程以及今后工作打好基础。②培养和提高学生的抽象思维与逻辑推理能力。四、考试方式及时间：考试方式：闭卷考试时间：120分钟五、课程综合评定办法1期末闭卷考试：占总成绩60%。2、平时成绩（作业、考勤情况等）：占总成绩40%3、试题难易程度：基础试题：中等难度试题：较难试题：难度较大的试题=4：3：2：1六、考试教材《离散数学》左孝凌、李为鑑、刘永才编著,上海科学技术文献出版社附：模拟试卷华南理工大学网络教育学院2012–2013学年度第一学期期末考试《离散数学》试卷（模拟卷）教学中心：专业层次：学号：姓名：座号：注意事项：1.本试卷共五大题，满分100分，考试时间120分钟，闭卷；2.考前请将以上各项信息填写清楚；3.所有答案直接做在试卷上,做在草稿纸上无效；4．考试结束，试卷、草稿纸一并交回。一.判断题(每题2分，共10分)1、设A，B都是合式公式，则ABB也是合式公式。（√）2.PQPQ。（√）3、对谓词公式（x）（P（y）Q（x,y））R（x,y）中的自由变元进行代入后得到公式（x）（P（z）Q（x,z））R（x,y）。（×）4．对任意集合A、B、C，有)()()(CBCACBA。（√）5.一个结点到另一个结点可达或相互可达。(×)二.单项选择题(每题2分,共20分)1.设：p：刘平聪明。q：刘平用功。在命题逻辑中，命题：“刘平不但聪明，而且用功”可符号化为：(A)A．PQB．PQC．PQD．PQ2.对于命题公式A，B，当且仅当(B)是重言式时，称“A蕴含B”，并记为AB。A．ABB．ABC．ABD．AB3．设Q（x）：x是有理数，R（x）：x是实数。命题“每一个有理数是实数”在谓词逻辑中的符号化公式是(A)A．（x）（Q（x）R（x））B．（x）（Q（x）R（x））题号一二三四五总分评分人得分教学中心：专业层次：姓名：学号：座号：（密封线内不答题）教学中心：专业层次：姓名：学号：座号：C．（x）（Q（x）R（x））D．（x）（Q（x）R（x））4．设[0，1]和（0，1）分别表示实数集上的闭区间和开区间，则下列命题中为假的是(D)A．（0，1）[0，1]B．{0，1}ZC．{0，1}[0，1]D．[0，1]Q5.设[a,b]和（c,d）分别表示实数集上的闭区间和开区间，则([0,4]∩[2,6])-(1,3)=(A)A．[3，4]B．(3,4)C．{3,4}D．[0，1]∪[3,6]6.对于集合{1,2,3}，下列关系中不等价的是(B)A．R={1,1，2,2,3,3}B．R={1,1,2,2,3,3,1,4}C．R={1,1,2,2,3,3,3，2,2,3}D．R={1,1,2,2,1,2,2,1,1,3,3,1,3,3,2,3,3,2}7．设A={1，2，3，4，5}，B={6，7，8，9，10}，以下哪个关系是从A到B的单射函数(B)A．f={1，7，2，6，3，5，1，9，5，10}B．f={1，8，2，6，3，7，4，9，5，10}C．f={1，7，2，6，3，5，4，6}D．f={1，10，2，6，3，7，4，8，5，10}8．集合S的幂集P(S)关于集合的并运算“∪”的零元为(B)A．B．SC．没有D．P(S)9．下列为欧拉图的是(（4）)10．给定无孤立点无向图G的边集：{（1，2），（1，3），（2，3），（2，4），（2，5），（3，4），（3，5）}，找出图G的一棵生成树为(A)A．{（1，2），（1，3），（2，4），（3，5）}B．{（1，2），（1，3），（2，3），（2，4）}C．{（1，2），（1，3），（3，5），（4，5）}D．{（1，2），（3，4），（3，5），（4，5）}三.填空题(每题2分，共10分)1．如果二元运算运算*对集合A封闭，则意味着对任意的Aba,有abA。2．设非空集合A的幂集为)(A，则在代数系统中,),(A，对于∪运算的幺元是，零元是A；3．设G是个具有5个结点的简单无向完全图，则G有_10_条边。4．设G是个无自环的无向图，其中有2个结点的度数为4，其余结点的度为2，有6条边。则G中共有_4个结点。因此，G是个欧拉图。5、仅当n4时，nK为平面图。四、证明推理题(每小题10分，共20分)1、(本题10分)用推理规则证明QP，QS，St，tRPQSR证（1）St前提引入（2）（St）（tS)（1）等价转换（3）tS（2）化简（4）tRP（5）t（4）化简（6）S（3）（5）假言推理（7）QSP（8）（QS）（SQ)（7）等价转换（9）SQ（8）化简（10）Q（6）（9）假言推理（11）QPP（12）P（10）（11）假言推理（13）R（4）化简（14）PQSR（6）（10）（12）（13）合取2、用(本题10分)推理规则证明x（P（x）Q（x））xP（x）xQ（x）证（1）x（P（x）Q（x））前提引入（2）P（Y）Q（Y）（1）US（3）xP（x）附加前提引入（4）P（Y）（3）US（5）Q（Y）（2）（4）假言推理（6）xQ（x）（5）UG五、解答题(每小题10分，共40分)1、(本题10分)求下面公式的主析取范式与主合取范式，并写出相应的成真赋值PQRPRQP解PQRPRQPPQRPRQPPQPRRQPPQPRRPQPPQRPQRPQRPQRRQPRQPRQPRQPPQRPQRPQRPQRPQR001011100101110mmmmm，主析取范式，成真赋值为001，011，100，101，110主合取范式为000010111PQRPQRPQRMMM2、(本题10分)求带权为1，1，2，3，3，4，5，6，7，8的最优三元树解01123345678(2)23345678(7)(12)(21)(40)3(11)223345678623884WT（作图略）3、(本题10分)求下列最小生成树的权值6816613491157解最小树权4+5+6+7=224、(本题10分)设{2,3,4,8,9,10,11},,|AA。（1）作关系的哈斯图；（2）求出该偏序集的极大元、极小元、最大元和最小元；（3）考虑{2,4,10}B，求出该偏序集的极大元、极小元、最大元、最小元、上确界、下确界解（1）,|A代表A上的整除关系，该关系R={(2,4),(2,8),(2,10),(3,9),(4,8)}AI，盖住关系COVR={(2,4),(2,10),(3,9),(4,8)}},哈斯图略；（2）该偏序集的极大元为8、9、10、11，极小元为2、3、11，没有最大元和最小元；（3）考虑{2,4,10}B，该偏序集的极大元4、10，极小元2，无最大元，最小元为2，上确界无，下确界为2。