09年离散数学复习大纲

2009年《离散数学》课程复习大纲离散数学虽然是近几十年来产生出的一门新课，就其数学内容来说却不是新的，有些内容甚至是很古典的。随着计算机科学的发展和计算机应用领域的日益广泛，迫切需要适当的数学工具来解决计算机科学各个领域中提出的有关离散量的理论问题，离散数学就是适应这种需要而建立的，它综合了计算机科学中所用到的研究离散量的各个数学课题，并进行系统、全面的论述，从而为研究计算机科学及相关学科提供了有利的理论基础和工具。一、总则1、本课程的教学目的和要求：离散数学是计算机科学及相关学科的一门非常重要的专业基础课。教学的目的是培养学生的数学思维能力，通过教学，最终使学生能够在众多的概念中要找出最重要的，在众多的定理中找出最根本的，将这些少量的概念和定理能够透彻地理解，自如地运用，就达到了掌握离散数学的教学要求。2、本课程的主要内容：朴素集合论、古典数理逻辑、图论、组合数学基础、初等数论、离散概率、抽象代数学（包括群、环、域、格、布尔代数）。3、考核重点与难点：离散数学包含的数学内容非常多，这些数学内容彼此间的独立性很强，每一个内容都可以作为一门课单独讲授，而在一个学期里讲授离散数学这门课，就只能讲授各个内容的最基本的知识，为学生今后进一步学习打下基础。因此，教师在认真讲解基本概念和知识外，更重要的是培养学生的数学思维能力，决不能将离散数学讲成数学，这就是离散数学教学的重点，同时也是离散数学教学的难点。4、本课程的知识范围及相关课程的关系：离散数学涉及的数学领域非常广，同时与计算机科学和相关学科关系非常密切，是很多计算机有关课程的基础，如：高级语言、数据结构、编译原理、操作系统、可计算性理论、人工智能、形式语言与自动机、信息管理与检索以及开关理论等，离散数学也是研究自动控制、管理科学、电子工程等的重要工具。5、教材的选用：屈婉玲、耿素云等编著《离散数学》——普通高等教育“十一五”国家级规划教材，高等教育出版社。屈婉玲、耿素云等编著《离散数学》（第2版）——21世纪大学本科计算机专业系列教材，清华大学出版社。二、课程内容第一部分数理逻辑1、考核内容：命题及表示、命题公式与翻译、真值表与等价公式、重言式与蕴涵式、其他联结词、对偶与范式、推理理论。一阶逻辑的概念与表示、一阶逻辑公式与翻译、变量的约束、一阶逻辑的等值式、前束范式。2、考核重点：命题逻辑中的基本概念和基本推理方法。变量的约束和前束范式。第二部分集合论1、考核内容：集合的概念与表示、集合的运算。序偶与笛卡尔积、关系及表示、关系的性质、复合关系和逆关系、关系的闭包运算、等价关系与等价类、偏序关系与哈斯图。函数的概念、逆函数和复合函数。2、考核重点：集合的基本概念和基本运算。关系的闭包运算、等价关系、等价类、偏序关系与哈斯图。逆函数和复合函数。第三部分代数结构1、考核内容：代数系统的引入、运算及性质，群和子群的定义与判定定理，群的陪集分解、循环群与置换群，格与布尔代数。2、考核重点：代数系统的运算与性质，子群的定义与判定定理，循环群的计算，几类格的定义。第四部分组合数学1、考核内容：基本计数规则、排列与组合、二项式定理与组合恒等式。2、考核重点：排列与组合、二项式定理。第五部分图论1、考核内容：图的基本概念、欧拉图与汉密尔顿图、平面图、对偶图。2、考核重点：图的基本术语，以及图的相关定理的应用，平面图、对偶图等的定义和平面图的判定。第六部分初等数论1、考核内容：素数、最大公约数与最小公倍数、同余、一次同余方程与密码学。2、考核重点：素数、一次同余方程与RSA公钥密码。第七部分离散概率1、考核内容：随即事件与概率、事件的运算、条件概率与独立性、离散型随机变量及其分布律、数学期望、方差。2、考核重点：事件的运算、离散型随机变量数学期望、方差。三、考试题型(一)填空题例如：设全集E={a,b,c,d,e},A={a,b,c},B={a,d,e},则A∪B=,A∩B=______,A-B=____________,~A∩~B=___________。答案；},,,,{edcba，;},,{},{cba（二）计算题例如：设集合A＝{a，b，c},R是集合A上的关系，，求，并分别画出它们的关系图。答案：它们的关系图如下（三）证明题例如：设R是集合A上的关系，如果R是自反的和传递的，证明：.答案：用定义证明)},(),,(),{(Rcbabba，＝)(),(),(RsRtRr)};,(),,(),,(),,(),,(),,{()(cbabbaccbbaaRr)};,(),,(),,(),,{()(bccbabbaRs)}.,(),,(),,(),,(),,(),,{()(cbbbcaabbaaaRtRRR