数学与应用数学专业(本科).doc

10羄莇薆薄衿莆芆蝿螅莆莈薂膄莅薁螈肀莄蚃蚁羆莃莂袆袂羀蒅虿螈罿薇袄肇羈芇蚇羃肇荿袃衿肆蒁蚅螅肅蚄蒈膃肄莃螄聿肄蒆薇羅肃薈螂袁肂芈薅螇膁莀螀肆膀蒂薃羂腿薅蝿袈膈莄薁袄膈蒇袇螀膇蕿蚀肈膆芈袅羄膅莁蚈袀芄蒃袃螆芃薅蚆肅节芅葿肁节蒇蚅羇芁薀薇袃芀艿螃蝿艿莂薆肈芈蒄螁羄莇薆薄衿莆芆蝿螅莆莈薂膄莅薁螈肀莄蚃蚁羆莃莂袆袂羀蒅虿螈罿薇袄肇羈芇蚇羃肇荿袃衿肆蒁蚅螅肅蚄蒈膃肄莃螄聿肄蒆薇羅肃薈螂袁肂芈薅螇膁莀螀肆膀蒂薃羂腿薅蝿袈膈莄薁袄膈蒇袇螀膇蕿蚀肈膆芈袅羄膅莁蚈袀芄蒃袃螆芃薅蚆肅节芅葿肁节蒇蚅羇芁薀薇袃芀艿螃蝿艿莂薆肈芈蒄螁羄莇薆薄衿莆芆蝿螅莆莈薂膄莅薁螈肀莄蚃蚁羆莃莂袆袂羀蒅虿螈罿薇袄肇羈芇蚇羃肇荿袃衿肆蒁蚅螅肅蚄蒈膃肄莃螄聿肄蒆薇羅肃薈螂袁肂芈薅螇膁莀螀肆膀蒂薃羂腿薅蝿袈膈莄薁袄膈蒇袇螀膇蕿蚀肈膆芈袅羄膅莁蚈袀芄蒃袃螆芃薅蚆肅节芅葿肁节蒇蚅羇芁薀薇袃芀艿螃蝿艿莂薆肈芈蒄螁羄莇薆薄衿莆芆蝿螅莆莈薂膄莅薁螈肀莄蚃蚁羆莃莂袆袂羀蒅虿螈罿薇袄肇羈芇 数学与应用数学专业（本科）离散数学课程考试大纲（08年11月审定）本课程是一门理论性较强的课程，要求在完成基础知识教学任务的同时，通过适当的实际应用的介绍，提高学生的实际应用能力的培养关于课程考核说明与实施要求 1考核对象：本课程考核说明适用于中央广播电视大学开放教育本科数学与应用数学专业的学生2考核依据：本考核说明是以本课程的教学大纲（2007年6月审定）和指定的参考教材为依据制定的本课程指定的参考教材是李伟生主编的、中央广播电视大学出版社出版的离散数学 3考核方式：本课程的考核实行形成性考核和终结性考核相结合的方式4课程综合成绩的记分方法：形成性考核占课程考核成绩的30%，即形成性考核的成绩满分为30分；终结性考核成绩占课程考核成绩的70%，即终结性考核成绩满分70分课程考核成绩满分100分，60分以上为合格，可以获得课程学分5形成性考核的说明：形成性考核由本课程中的形成性考核作业成绩构成，独立完成形成性考核作业是学好本课程的重要手段根据教学进度和教学基本要求，每学期安排4次形成性考核的作业学生完成形成性考核作业后，由辅导教师(或责任教师)根据作业完成情况和质量，对作业进行评分 6终结性考试的说明：终结性考核实行全国统一考核，根据本课程考试说明，由中央电大统一命题，统一评分标准，统一考核时间(1) 考核要求：本课程考核要求分三个层次，有关概念、性质和定理等理论方面的要求从高到低为理解，了解和知道；有关方法、公式和法则等的要求从高到低为熟练掌握，掌握和会 (2) 组卷原则：终结性考核的考核内容和要求以本考核说明为准，要求考核基本概念、基本原理和基本运算命题覆盖面可适当宽些，但试题难度要适中，题量要适当易、中、较难题目在试卷中分配为4：4：2 (3) 试题类型及结构：单项选择题的分数占15，填空题的分数占15，公式翻译题的分数占12，判断说明题的分数占14，计算题的分数占36；证明题的分数占8单项选择题和填空题主要涉及基本概念、基本理论、重要性质和结论、公式及其简单计算单项选择题给出四个备选答案，其一是正确选项填空题只需填写正确结论，不写计算、推论过程或理由逻辑公式翻译题主要是利用命题逻辑和谓词逻辑的基本概念及命题联结词、谓词量词，将一个陈述句翻译成命题公式或谓词公式判断说明题是对给定的一个命题或结论作出对与错的判断，并给出简单的说明计算题主要考核学生的基本运算技能和速度，要求写出化简、计算过程证明题主要考查应用概念、性质、定理及重要结论进行逻辑推理的能力，要求写出推理过程(4) 考核形式：采用半开卷、笔试方式，试卷满分100分 半开卷考试允许考生携带指定的一张专用A4纸（统一印制），考生可以将自己对全课程学习内容的总结归纳写在这张A4纸上带入考场，作为答卷时参考(5) 考核时间：90分钟考核内容与考核要求第1章 集合及其运算考核知识点1集合，元素，集合的表示，全集，空集 2集合的包含、相等，子集，幂集3集合的并、交、补、差、对称差等运算及其运算律4容斥原理考核要求1理解集合的概念，容斥原理2理解集合的包含、子集、相等和幂集等概念，熟练掌握集合的表示方法和集合的并、交、补、差和对称差等运算，会用文氏图表示集合的各种运算 3掌握用集合运算基本规律证明集合恒等式的方法4掌握利用容斥原理进行计数的方法第2章 关系与函数考核知识点 1有序对和笛卡儿积2关系及其运算性质3二元关系的矩阵与图4复合关系与逆关系5二元关系的性质6等价关系与等价类 7偏序关系、复盖集与哈斯图，极大(小)元，最大(小 )元，上(下)界，最小上界，最大下界8函数 反函数 复合函数 单射 满射和双射考核要求 1了解有序对和笛卡儿积的概念，掌握笛卡儿积的运算2理解关系的概念：包括二元关系、空关系、全关系、恒等关系掌握关系的集合表示、关系矩阵和关系图，掌握关系的运算3掌握求复合关系和逆关系的方法4理解关系的性质(自反性和反自反性、对称性和反对称性、传递性)，掌握其判别方法5理解等价关系和偏序关系概念，掌握等价关系、偏序关系的判定，掌握等价类、复盖集的求法和作偏序关系哈斯图的方法知道极大(小)元，最大(小)元的概念，会求极大(小)元、最大(小)元、最小上界和最大下界6理解函数概念：函数(映射)，函数相等，复合函数和反函数7理解单射、满射和双射等概念，掌握其判别方法第3章 图的基本概念与性质考核知识点1图的概念与表示，有向图，无向图，简单图，完全图，结点的度数，图的同构，子图、补图2通路，通路的长度，初级通路，简单通路，回路，初级回路，简单回路3图的连通性与连通度概念、判定，点割集与割点，边割集与割边4图的矩阵表示、邻接矩阵、可达性矩阵及其计算5最短路径考核要求1理解图的基本概念：结点、边、有向图，无向图、简单图、完全图、结点的度数、图的同构子图等，理解握手定理2了解通路与回路的概念：简单通路、初级通路和复杂通路，简单回路、初级回路和复杂回路，会求通路和回路的长度3了解无向图的连通性，会求无向图的连通分支了解点割集、割点、边割集、割边、点连通度、边连通度等概念4了解有向图的强连通性、单向连通性、弱连通性；会判别有向图连通性的类型5理解图的矩阵表示法、邻接矩阵、可达性矩阵的概念，掌握邻接矩阵、可达性矩阵的有关计算6知道最短路径的概念，会最短路径的算法第4章 几种特殊图考核知识点1欧拉通路(回路)，欧拉图2哈密顿通路(回路)，哈密顿图3平面图，欧拉公式4对偶图及着色 考核要求1了解欧拉回路、欧拉图的概念及性质，掌握欧拉图的判别方法2了解汉密尔顿回路、汉密尔顿图的概念及性质，掌握汉密尔顿图的判别方法3了解平面图的概念：平面图、面、边界、面的次数和非平面图，掌握平面图的判别方法，掌握欧拉公式的应用4理解平面图与对偶图的关系、对偶图在图着色中的作用，掌握着色算法；5掌握图论中常用的证明方法第5章 树及其应用考核知识点1树的定义及性质2生成树与最小生成树的概念，最小生成树的Kruskal算法3根树的概念及性质4最优树的概念，最优树的Huffman算法，前缀码的求法 考核要求 1了解无向树、树叶、分支点、平凡树、生成树和最小生成树等概念及性质，掌握最小生成树的Kruskal算法 2了解有向树、根树、有序树、最优二元（叉）树等概念及性质，掌握最优树的Huffman算法 3掌握利用最优树产生前缀码的方法第6章 命题逻辑考核知识点1命题与联结词(否定、析取、合取、蕴含、等价)，真值与真值表2命题公式的解释3命题公式的等值式与蕴涵式，等值演算4析取范式、合取范式、极小(大)项，主析取范式、主合取范式的概念与求法5命题逻辑的推理理论考核要求1理解命题联结词概念，掌握命题公式的翻译（命题符号化）及判断语句是不是命题的方法 2熟练掌握求给定公式真值表的方法3掌握基本等值式以及用真值表法和等值演算法判别公式类型和公式等值的方法4了解析取(合取)范式概念，理解极小(大)项的概念和主析取(合取)范式概念，熟练掌握用基本等值式或真值表将公式化为主析取(合取)范式的方法5掌握命题公式的的直接证明方法与间接证明方法 第7章 谓词逻辑考核知识点1谓词，量词，个体词，个体域，变元 2谓词公式的解释3前束范式的概念与求法 4谓词公式的等值式与蕴涵式5谓词逻辑的推理理论考核要求1理解谓词、量词、个体词、个体域、全域、原子公式、谓词公式和变元等概念掌握谓词公式的翻译2掌握在有限个体域下消去公式的量词和求公式在给定解释下真值的方法3掌握谓词演算的等值式和重言蕴含式4了解前束范式的概念，会求谓词公式的前束范式的方法5了解谓词逻辑推理的规则，掌握谓词公式的证明与推导方法试题类型及规范解答举例一、单项选择题1设a是集合A的元素，则以下正确的是( )A B C D选项B正确，填写答案：“B” （容易题）2有向完全图D， 则图D的边数是( )AE(E1)/2 BV(V1)/2 CE(E1) DV(V1)选项D正确，填写答案：“D” （中等题） 二、填空题3含有三个命题变项P，Q，R的命题公式PQ的主析取范式是 填写答案：“(PQR)(PQR)” （较难题）4设集合A=1, 2, 3, 4 ，B=6, 8, 12， A到B的二元关系R那么R1 填写答案：, （容易题） 三、公式翻译题 5请将语句“除非你去，否则我不去”翻译成命题公式，其中设命题P：你去；Q：我去 解：命题公式为：QP或者PQ （中等题） 6请将语句“尽管有人努力工作了，但未必一切人都努力工作”翻译成谓词公式，其中设P（x）：x是人； Q（x）：x努力工作解：谓词公式：($x)(P(x)Q(x)(x)(P(x)Q(x) （较难题） 四、判断说明题 7设R，S是集合A上传递的关系，判断R S是否具有传递性，并说明理由 解：R S不一定是传递的关系 例如集合A= 1 , 2 , 3 上的关系R = ，S =，都是A上传递的关系但是，R S = ，不是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 （较难题）IV样卷（一）一、单项选择题（每小题3分，本题共15分）1若集合A2，a，3，4，则下列表述正确的是( )AaAB3AC3ADA2设集合A=a, b，则A上的二元关系R=, 是A上的( )关系A是等价关系但不是偏序关系B是偏序关系但不是等价关系C既是等价关系又是偏序关系A不是等价关系也不是偏序关系3设图G的邻接矩阵为则G的边数为( )A5 B6 C3 D44无向图G存在欧拉通路，当且仅当( )AG中所有结点的度数全为偶数 BG中至多有两个奇数度结点CG连通且所有结点的度数全为偶数 DG连通且至多有两个奇数度结点5下列命题公式是等值的为( )APQ，PQ BA(BA)，A(AB) CQ(PQ)，Q(PQ) DA(AB)，B二、填空题（每小题3分，本题共15分）6设A, B为任意集合，命题A-B=的条件是 7设集合Aa,b,c，R是A上的二元关系，其关系图为 abc那么R的关系矩阵为：MR8设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v, e和r满足的关系式是 9设G是有p个结点，s条边的连通图，则从G中删去 条边，才能确定图G的一棵生成树10设个体域D1,2,那么谓词公式消去量词后的等值式为 三、公式翻译题（每小题4分，本题共12分） 11请将语句“今天不是天晴”翻译成命题公式，其中设命题P：今天天晴 12请将语句“如果天不下雪，我有时间，那么我就去市里”翻译成命题公式，其中设命题P：天下雪；Q：我有时间；R：我去市里 13请将语句“没有一个国家级运动员不是健壮的”翻译成谓词公式，其中设P(x)：x是国家级运动员，Q(x)：x是健壮的四、判断说明题（每小题7分，本题共14分）v1v2v3v5v4dbacefghn图G14如果R1和R2是A上的自反关系，判断结论：“R1R2是自反的” 是否成立？并说明理由15图G(如右图)能否一笔画出？说明理由. 若能画出，请写出一条通路或回路 五计算题（每小题12分，本题共36分）16设谓词公式（1）试写出量词的辖域；（2）指出该公式的自由变元和约束变元17设G=，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 18设集合Aa, b, c, d上的二元关系R的关系图如右图所示（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 B C D 5表达式中的辖域是( ) AP(x, y) BP(x, y)Q(z) CR(x, y) DP(x, y)R(x, y)二、填空题（每小题3分，本题共15分）6设集合A b，c，那么集合A的幂集合P(A)= 7设A，B为有限集，且|A|=m,|B|=n,那末A与B间存在双射，当且仅当 8已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是 9设G=是具有n个结点的简单图，若在G中每一对结点度数之和大于等于 ，则在G中存在一条汉密尔顿路10命题公式的真值是 三、公式翻译题（每小题4分，本题共12分） 11请将语句“如果天不下雨，我就去书店”翻译成命题公式，其中设命题P：天下雨，Q：我去书店 12请将语句“若a是偶数，b是偶数，则a+b也是偶数”翻译成命题公式，其中设命题P：你去；Q：我去；R：a+b是偶数 13请将语句 “鸟都会飞”翻译成谓词公式，其中设P(x)：x是鸟；Q(x)：x会飞翔 四、判断说明题（每小题7分，本题共14分）14设A、B、C为任意的三个集合，如果AB=AC，判断结论B=C 是否成立？并说明理由15给定两个图G1，G2（如下图所示），试判断它们是否为欧拉图、哈密顿图？并说明理由abcdefg图G2图G1 五计算题（每小题12分，本题共36分）16（1）化简集合表达式：(ABC)(AB)(B(BC)A)；（2）设集合A1,2，