《离散数学》课程复习指导

PAGE13PAGEPAGE13《离散数学》课程复习指导考试题型：（1）单项选择题（每小题3分，本题共15分） （2）填空题（每小题3分，本题共15分）（3）逻辑公式翻译（每小题6分，本题共12分）（4）判断说明题（每小题7分，本题共14分）（5）计算题（每小题12分，本题共36分）（6）证明题（本题共8分）期末考试采用半开卷笔试形式，卷面满分为100分，考试时间为90分钟。考试说明：Ⅰ．关于课程考核说明与实施要求1．考核对象：本课程考核说明适用于中央广播电视大学开放教育本科电气信息类计算机科学与技术专业的学生． 2．考核依据：本考核说明是以本课程的教学大纲（2007年6月审定）和指定的参考教材为依据制定的．本课程指定的参考教材是李伟生主编的、中央广播电视大学出版社出版的《离散数学》．3．考核方式：本课程的考核实行形成性考核和终结性考核相结合的方式．4．课程综合成绩的记分方法：形成性考核占课程考核成绩的30%，即形成性考核的成绩满分为30分；终结性考核成绩占课程考核成绩的70%，即终结性考核成绩满分70分．课程考核成绩满分100分，60分以上为合格，可以获得课程学分． 5．形成性考核的说明：见附件一。6．终结性考试的说明：终结性考核实行全国统一考核，根据本课程考试说明，由中央电大统一命题，统一评分标准，统一考核时间． (1)考核要求：本课程考核要求分三个层次，有关概念、性质和定理等理论方面的要求从高到低为理解，了解和知道；有关方法、公式和法则等的要求从高到低为熟练掌握，掌握和会．(2)组卷原则：终结性考核的考核内容和要求以本考核说明为准，要求考核基本概念、基本原理和基本运算．命题覆盖面可适当宽些，但试题难度要适中，题量要适当．易、中、较难题目在试卷中分配为4：4：2． (3)试题类型及结构：单项选择题的分数占15％，填空题的分数占15％，公式翻译题的分数占12％，判断说明题的分数占14％，计算题的分数占36％；证明题的分数占8％．单项选择题和填空题主要涉及基本概念、基本理论、重要性质和结论、公式及其简单计算．单项选择题给出四个备选答案，其一是正确选项．填空题只需填写正确结论，不写计算、推论过程或理由．逻辑公式翻译题主要是利用命题逻辑和谓词逻辑的基本概念及命题联结词、谓词量词，将一个陈述句翻译成命题公式或谓词公式．判断说明题是对给定的一个命题或结论作出对与错的判断，并给出简单的说明．计算题主要考核学生的基本运算技能和速度，要求写出化简、计算过程．证明题主要考查应用概念、性质、定理及重要结论进行逻辑推理的能力，要求写出推理过程．(4)考核形式：采用半开卷、笔试方式，试卷满分100分．半开卷考试允许考生携带指定的一张专用A4纸（统一印制），考生可以将自己对全课程学习内容的总结归纳写在这张A4纸上带入考场，作为答卷时参考． (5)考核时间：90分钟．三．重点复习内容第1章集合及其运算 1．理解集合的概念，容斥原理．2．理解集合的包含、子集、相等和幂集等概念，熟练掌握集合的表示方法和集合的并、交、补、差和对称差等运算，会用文氏图表示集合的各种运算．3．掌握用集合运算基本规律证明集合恒等式的方法．4．掌握利用容斥原理进行计数的方法．第2章关系与函数1．了解有序对和笛卡儿积的概念，掌握笛卡儿积的运算． 2．理解关系的概念：包括二元关系、空关系、全关系、恒等关系．掌握关系的集合表示、关系矩阵和关系图，掌握关系的运算．3．掌握求复合关系和逆关系的方法．4．理解关系的性质(自反性和反自反性、对称性和反对称性、传递性)，掌握其判别方法．5．理解等价关系和偏序关系概念，掌握等价关系、偏序关系的判定，掌握等价类、复盖集的求法和作偏序关系哈斯图的方法．知道极大(小)元，最大(小)元的概念，会求极大(小)元、最大(小)元、最小上界和最大下界．6．理解函数概念：函数(映射)，函数相等，复合函数和反函数．7．理解单射、满射和双射等概念，掌握其判别方法．第3章图的基本概念与性质 1．理解图的基本概念：结点、边、有向图，无向图、简单图、完全图、结点的度数、图的同构子图等，理解握手定理．2．了解通路与回路的概念：简单通路、初级通路和复杂通路，简单回路、初级回路和复杂回路，会求通路和回路的长度．3．了解无向图的连通性，会求无向图的连通分支．了解点割集、割点、边割集、割边、点连通度、边连通度等概念．4．了解有向图的强连通性、单向连通性、弱连通性；会判别有向图连通性的类型．5．理解图的矩阵表示法、邻接矩阵、可达性矩阵的概念，掌握邻接矩阵、可达性矩阵的有关计算．6．知道最短路径的概念，会最短路径的算法．第4章几种特殊图 1．了解欧拉回路、欧拉图的概念及性质，掌握欧拉图的判别方法．2．了解汉密尔顿回路、汉密尔顿图的概念及性质，掌握汉密尔顿图的判别方法．3．了解平面图的概念：平面图、面、边界、面的次数和非平面图，掌握平面图的判别方法，掌握欧拉公式的应用．4．理解平面图与对偶图的关系、对偶图在图着色中的作用，掌握着色算法；5．掌握图论中常用的证明方法第5章树及其应用1．了解无向树、树叶、分支点、平凡树、生成树和最小生成树等概念及性质，掌握最小生成树的Kruskal算法．2．了解有向树、根树、有序树、最优二元（叉）树等概念及性质，掌握最优树的Huffman算法．3．掌握利用最优树产生前缀码的方法．第6章命题逻辑 1．理解命题联结词概念，掌握命题公式的翻译（命题符号化）及判断语句是不是命题的方法． 2．熟练掌握求给定公式真值表的方法． 3．掌握基本等值式以及用真值表法和等值演算法判别公式类型和公式等值的方法．4．了解析取(合取)范式概念，理解极小(大)项的概念和主析取(合取)范式概念，熟练掌握用基本等值式或真值表将公式化为主析取(合取)范式的方法． 5．掌握命题公式的的直接证明方法与间接证明方法．第7章谓词逻辑 1．理解谓词、量词、个体词、个体域、全域、原子公式、谓词公式和变元等概念．掌握谓词公式的翻译．2．掌握在有限个体域下消去公式的量词和求公式在给定解释下真值的方法．3．掌握谓词演算的等值式和重言蕴含式．4．了解前束范式的概念，会求谓词公式的前束范式的方法．5．了解谓词逻辑推理的规则，掌握谓词公式的证明与推导方法．*．各种试题类型及解答举例一、单项选择题1．设a是集合A的元素，则以下正确的是()． A．B．C．D．选项B正确，填写答案：“B”．（容易题） 2．有向完全图D＝<V，E>，则图D的边数是()． A．E(E－1)/2B．V(V－1)/2C．E(E－1)D．V(V选项D正确，填写答案：“D”．（中等题）二、填空题3．含有三个命题变项P，Q，R的命题公式PQ的主析取范式是．填写答案：“(PQR)(PQR)”．（较难题）4．设集合A={1,2,3,4}，B={6,8,12}，A到B的二元关系R＝那么R－1＝填写答案：{<6,3>,<8,4>}．（容易题）三、公式翻译题5．请将语句“除非你去，否则我不去”翻译成命题公式．解：设命题P：你去；Q：我去．则命题公式为：Q→P或者┐P→┐Q．（中等题）6．请将语句“尽管有人努力工作了，但未必一切人都努力工作．”翻译成谓词公式．解：设P（x）：x是人；Q（x）：x努力工作．则谓词公式：(x)(P(x)∧Q(x))∧┐((x)(P(x)→Q(x)))（较难题）四、判断说明题7．设R，S是集合A上传递的关系，判断RS是否具有传递性，并说明理由．解：RS不一定是传递的关系．例如集合A={1,2,3}上的关系R={<1,2>}，S={<2,3>}，都是A上传递的关系．但是，RS={<1,2>，<2,3>}不是A上传递的．（中等题）8．用真值表判断命题公式的类型．解：命题公式的真值表如下PQPQ001000011000100011111111原式为可满足式.（容易题）五、计算题9．设，求：（1）(AB)~C；（2）P(A)－P(C)；（3）AB． 解：（1）(AB)~C={1} （2） （3）AB=(AB)－（AB）=（容易题）10．（1）求命题公式的主析取范式；（2）求该命题公式的成假赋值．解：（1）（2）因为该命题公式的成真赋值是（1，0），所以成假赋值为（0，0），（0，1），（1，1）（中等题）六、证明题11．设G是连通简单平面图，则它一定有一个度数不超过5的结点．（提示：用反证法）证：因为G是连通简单平面图，它的每个面至少有3条边，所以有，即（其中r，e分别为图G的面数和边数） 假设结论不成立，则每个结点的度数都大于等于6．则有，即有（其中v是图G的结点数）由欧拉公式：2==0矛盾．所以G中至少有一个结点的度数小于或等于5．（较难题）=4\*ROMANIV．样卷（一）一、单项选择题（每小题3分，本题共15分）1．若集合A＝{2，a，{3}，4}，则下列表述正确的是()． A．{a}A B．{3}A C．{3}A D．A 2．设集合A={a,b}，则A上的二元关系R={<a,a>,<b,b>}是A上的()关系． A．是等价关系但不是偏序关系B．是偏序关系但不是等价关系C．既是等价关系又是偏序关系A．不是等价关系也不是偏序关系 3．设图G的邻接矩阵为 则G的边数为()． A．5B．6C 4．无向图G存在欧拉通路，当且仅当()．A．G中所有结点的度数全为偶数B．G中至多有两个奇数度结点C．G连通且所有结点的度数全为偶数D．G连通且至多有两个奇数度结点5．下列命题公式是等值的为()．A．PQ，PQ B．A(BA)，A(AB)C．Q(PQ)，Q(PQ)D．A(AB)，B二、填空题（每小题3分，本题共15分）6．设A,B为任意集合，命题AB的条件是．7．设集合A＝{a,b,c}，R是A上的二元关系，其关系图如图一所示：aabc图一那么R的关系矩阵为：MR＝．8．设G是连通平面图，v,e,r分别表示G的结点数，边数和面数，则v,e和r满足的关系式是．9．设G＝<V,E>是有p个结点，s条边的连通图，则从G中删去条边，才能确定图G的一棵生成树． 10．设个体域D＝{1,2},那么谓词公式消去量词后的等值式为．三、公式翻译题（每小题6分，本题共12分）11．请将语句“今天不是天晴”翻译成命题公式．12．请将语句“如果天不下雪，我有时间，那么我就去市里”翻译成命题公式．v1v2v3v1v2v3v5v4dbacefghn图二13．如果R1和R2是A上的自反关系，判断结论：“R1∪R2是自反的”是否成立？并说明理由．14．图G(如图二所示)能否一笔画出？说明理由．若能画出，请写出一条通路或回路．五．计算题（每小题12分，本题共36分）15．设谓词公式．（1）试写出量词的辖域；（2）指出该公式的自由变元和约束变元．16．设G=<V，E>，V={v1，v2，v3，v4，v5}，E={(v1,v2)，(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)}．（1）试给出G的图形表示；（2）写出其邻接矩阵；（3）求出每个结点的度数．adbc图三17．设集合A＝{a,b,c,adbc图三关系图如图三所示．（1）写出R的表达式；（2）写出R的关系矩阵；（3）求出R2．六、证明题（本题共8分）19．试证明集合等式：A(BC)=(AB)(AC)．样卷（二）一、单项选择题（每小题3分，本题共15分）1．非空集合A上的二元关系R，满足()，则称R是等价关系． A．自反性，对称性和传递性B．反自反性，对称性和传递性C．反自反性，反对称性和传递性D．自反性，反对称性和传递性 2．下列数组中，能构成无向图的度数列的数组是()． A．(1,1,2,3)B．(1,2,3,4,5)C．(2,2,2,2)D．(1,3,3) 3．设G是有n个结点，m条边的连通图，必须删去G的()条边，才能确定G的一棵生成树． A．B．C．D．4．命题公式的主析取范式是()． A．BC．D．5．表达式中的辖域是()．A．P(x,y)B．P(x,y)Q(z)C．R(x,y)D．P(x,y)R(x,y) 二、填空题（每小题3分，本题共15分）6．设集合A＝{b，c}，那么集合A的幂集合P(A)=． 7．设A，B为有限集，且m,n,那末A与B间存在双射，当且仅当． 8．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是． 9．设G=<V，E>是具有n个结点的简单图，若在G中每一对结点度数之和大于等于，则在G中存在一条汉密尔顿路． 10．命题公式的真值是．三、公式翻译题（每小题6分，本题共12分）11．请将语句“如果天不下雨，我就去书店”翻译成命题公式．12．请将语句“若a是偶数，b是偶数，则a+b也是偶数．”翻译成命题公式．四、判断说明题（每小题7分，本题共14分）13．设A、B、C为任意的三个集合，如果A∪B=A∪C，判断结论B=C是否成立？并说明理由．14．给定两个图G1，G2（如下图所示），试判断它们是否为欧拉图、哈密顿图？并说明理由．aabcdefg图G2图G1五．计算题（每小题12分，本题共36分）15．（1）化简集合表达式：((ABC)(AB))－((B(B－C))－A)；（2）设集合A＝{1,2}，求A×P(A)．16．设A={1,2,3,4,5,6,7,8,9,10,11,12}，R是A上的整除关系，B={2,4,6}．（1）写出关系R的表示式；（2）画出关系R的哈斯图；（3）求出集合B的最大元、最小元．17．图G=<V,E>，其中V={a,b,c,d,e,f}，E={(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(d,e),(d,f),(e,f)}，对应边的权值依次为5，2，1，2，6，1，9，3及8．（1）画出G的图形；（2）求出G权最小的生成树．六、证明（本题共8分）18．试证明逻辑式：(A→B)∧┐B∧┐(C∧┐A)┐C附件一离散数学课程基于网络考核改革试点方案（2010年6月修改）离散数学是中央电大计算机科学与技术专业（本科）的一门统设必修学位课程。在现代远程教育的环境下，学生以业余自主学习为主，数学课程在远程教育教学中难教难学、学生学习参与性和主动性不高等问题是不争的事实。为了探索解决这些问题的途径，离散数学作为中央电大“基于WEB2.0的数字化教学环境与资源建设模型”课题的试点课程，2008年起在北京电大、深圳电大和辽宁电大进行了教学改革实践研究。本课程采取基于混合式学习理论的教学模式，按照学习者需求和课程教学内容的要求，将面对面的课堂教学与数字化学习有机整合，将不同媒体学习资源有机整合，将不同学习方式有机整合。既充分体现学生的学习主体作用，又不忽视教师的指导作用；调动教与学两个方面的主动性、积极性，较好地解决了远程教育中数学课程的一些教学难点。为进一步推广应用本课程的教学改革实践研究成果，按照课题组计划，从09春开始全面推广基于WEB2.0的数字化教学环境的一站式学习模式。因此，从09春开始，本课程的形成性考核在离散数学课程学习平台进行。一、考核改革的目的1．通过本课程形成性考核的改革，深入探索现代远程开放教育中基于WEB2.0的数字化教学环境的一站式学习模式的形成性考核基本模式；2．通过本课程形成性考核的改革，探索离散数学课程的形成性考核的目标、形式、题型、题量、难易程度等；3．通过本课程形成性考核的改革，进一步强化教学过程的落实，引导学生在学习过程中，充分利用本课程学习平台中丰富的教学资源，更好地理解和掌握课程的基本内容，实现各个学习环节，达到学习目标；4．探索现代远程开放教育形成性考核的信度、效度，保证学习质量。二、考核对象本形成性考核修改方案于2010年秋季在全国范围内实施。适用于2010年春季以后注册开放教育本科（专科起点）计算机科学与技术专业第二学期学习本课程的所有学生，也适用于历届没有通过本课程考核的学生。对往届课程考核不及格的学生，形成性考核不及格者必须参加本次形成性考核及终结性考试；形成性考核及格而终结性考试不及格的同学无需参加本次形成性考核，只需参加终结性考试。三、考核目标本课程主要内容包括集合论、图论与数理逻辑等三个方面的内容。通过考核既要检测学生对离散数学的的基本概念、结论的理解程度，又要检测学生对离散数学的的基本推理与证明过程、基本算法及应用方法的掌握程度。四、考核方式本课程的考核实行网上形成性考核和半开卷、笔试方式的终结性考核相结合的方式。形成性考核占总成绩的30%，由7次作业构成，登陆形成性考核系统进行，随平时学习过程中完成。终结性考试占总成绩的70%，在学期末以半开卷、笔试方式的方式进行，具体时间见中央电大统一时间安排。形成性考核和终结性考试的成绩合成后达到及格就确认本课程考核合格。（一）形成性考核通过网上形成性考核一方面可以加强对地方电大教师教学过程的引导、指导和管理，优质的完成教学任务，提高教学质量，实现教学目标；另一方面可以加强对学生平时自主学习过程的指导和监督，重在对学生自主学习过程进行的指导和检测，引导学生按照教学要求和学习计划完成学习任务，达到掌握知识、提高应用能力的目标，提高学生的综合素质。第一部分形考说明本课程共设计七次形考作业，其中线上作业四次，线下作业三次，占课程综合成绩的30％。形式：四次线上作业，每次都是客观测试题，其中第一次是本课程网上学习指南，第二、四、六次是本课程集合论部分、图论部分、数理逻辑部分的概念及性质的检测。三次线下作业，分别是集合论部分、图论部分、数理逻辑部分的综合性作业，目的是通过综合性作业，使同学自己检验每一部分的学习成果，找出掌握的薄弱知识点，重点复习，更好地完成本部分的学习任务。注：每次形考任务按百分制进行成绩评定。操作：所有形成性考核试题均由中央电大统一编制。第二部分形考内容序号章内容形式发布时间最迟提交时间权重1网上学习指南单项选择题第1周初第9周末10%21-2集合论部分概念及性质单项选择题第2周初第10周末10%31-2集合论部分综合性作业线下作业第3周初第11周末20%43-5图论部分概念及性质单项选择题第5周初第13周末10%53-5图论部分综合性作业线下作业第7周初第15周末20%66-7数理逻辑部分概念及性质单项选择题第9周初第16周末10%76-7数理逻辑部分综合性作业线下作业第11周初第17周末20%其中，01、02、04、06四次任务的形成性考核成绩为：3分/次，合计12分，每次作业按100分计算；03、05、07三次任务的形成性考核成绩为：6分/次，合计18分，每次作业按100分计算；第一次考核目的与要求为使学生能充分利用课程学习平台中丰富多彩的学习资源，能顺利地完成学习任务，我们安排了离散数学课程网上学习培训、编制了网上学习平台使用手册．通过本次作业，检查学生是否了解课程的学习内容和学习方式，是否了解课程平台的资源分布、栏目分布和完成形考作业的方法，以此来落实学习过程，提高学生的学习效率。本次作业是共有9个题目，第1~8题是选择题，学生按照题目的要求选择正确答案，第9题要求学生在文本框中提交自己的学习计划．第二次考核目的与要求在第一单元学习任务完成后，通过客观性作业检查学生：1．是否清楚地知道元素与集合、集合与集合的关系，是否正确掌握了集合的表示方法，掌握了集合的并、交、差、补和对称差等的基本运算。2．是否理解了关系的概念和关系的性质，理解了复合关系、逆关系及关系的闭包的概念，理解了等价关系与等价类、序关系等的概念；理解了函数的概念及其性质、逆函数与复合函数的概念，了解函数与关系的区别；是否正确掌握了关系的表示方法，掌握等价关系的判定、序关系的判定、函数的判定．第三次考核目的与要求本次作业是线下作业，是集合论部分的综合练习，基本上是按照期末考试中这一部分的题型安排练习题目，目的是通过综合性线下作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，更好地完成集合论部分的学习任务。要求学生将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅。第四次考核目的与要求在第二单元学习任务完成后，通过客观性作业检查学生：1．是否了解了图的基本概念、类型和几种表示方法，理解了握手定理，了解了图的同构概念及图同构的必要条件；理解了路与回路、简单路径、基本路径、简单回路、基本回路、连通性与连通度、点割集与割点、边割集与割边等概念，掌握了图的路、回路、连通性、强连通、点割集、边割集、割点、割边和图同构的判断方法。2．是否理解了欧拉通路、欧拉图的概念，掌握了欧拉图的判别方法；理解了汉密尔顿通路、汉密尔顿图的概念，会做简单判断；了解平面图、面、边界、面的次数和非平面图的概念，掌握了欧拉公式的应用．3．是否理解了树、生成树和最小生成树等概念，掌握求最小生成树的方法；了解了有向树、根树、有序树、二叉树、二叉完全树、正则二叉树、带权二叉树和最优二叉树等概念。第五次考核目的与要求本次作业是线下作业，是图论部分的综合练习，基本上是按照期末考试中这一部分的题型安排练习题目，目的是通过综合性线下作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，更好地完成图论部分的学习任务。要求学生将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅。第六次考核目的与要求在第二单元学习任务完成后，通过客观性作业检查学生：1．是否理解了命题概念，会判别语句是不是命题；理解了五个联结词及其真值表，了解公式的概念，会将简单命题符号化．是否理解了永真式和永假式概念，掌握其判别方法；了解公式等价概念，知道联结词、与关系符、之间的区别．是否理解了析取范式、合取范式、主析取范式和主合取范式的概念．2．是否理解了谓词、量词、个体词、个体域等概念，会将简单命题符号化；了解了原子公式、谓词公式、约束变元、自由变元和辖域等概念．是否理解了等价式与蕴含式的概念，了解了前束范式的概念。