《离散数学[C]》课程教学大纲

离散数学C课程教学大纲【课程编号】：16119013【英文译名】：Discrete Mathematics【适用专业】：信息管理与信息系统【学 分 数】： 2【总 学 时】： 32【实践学时】： 0一、本课程教学目的和课程性质离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程，它研究世界事物间的离散结构和相互关系。离散数学理论体系完整，结构严谨，具有很多相应的典型实例。离散数学课程的目的不仅为计算机科学的专业理论课，诸如：数据结构、操作系统、编译理论、算法分析、逻辑设计、系统结构、容错诊断、机器定理证明等课程提供必要的理论基础，而且为学生今后从事计算机科学方面的工作提供重要的工具。同时通过对本课程学习，要使学生能够接受现代数学关于离散结构的观点，从系统结构的研究方法出发，研究事物间的有关属性；同时要应用数形结合方法，使事物论证简洁直观；此外要通过描述方法和缜密思维方法的训练，使学生具有良好的抽象思维和逻辑思维能力。总之，离散数学不仅是一门服务于专业的工具性学科，而且也是一门培养学生具有缜密素质的核心基础课程。二、本课程的基本要求离散数学是培养学生抽象思维和缜密概括能力的素质训练课程。它需要使学生紧密结合专业，为其他专业基础课程做好各种数学知识的准备，同时也要使学生兼具开拓能力。本课程总目标是训练学生具有严密的思维方法，严格证明的推理能力，应用自如的解题技巧，以及训练有素的演算能力，使学生能掌握处理各种离散结构事物的描述工具与方法，以适应学习其他专业课程的各种需要。一般离散数学课程包括数理逻辑、集合论、图论、代数结构等几个部分。数理逻辑的重点是公式演算与推理证明；集合论的重点是关系理论与映射的描述；图论着重于数形结合的描述以及各种实际应用；代数结构则主要是从系统宏观的代数方法去研究客观事物的各种性质与特征。三、本课程与其他课程的关系离散数学是一门体系独立自行封闭的基础数学课程，但为了论述方便，此课程应安排在高等数学与线性代数课程之后。为了加强离散结构方法的训练，在讲授本课程的基础上，可讲授数据结构、数据库原理，这样对于集合和图论的应用能够加深理解，温故而知新。另外离散数学与计算机网络与通信，以及计算机系统结构等课程关系紧密，是本专业其它专业基础和专业课的先修课。四、课程内容一 命题演算（8学时）主要内容：1.命题概念2.基本联合词与复习命题3.合式公式与联合词优先次序4.命题公式的等价变换、命题符号化5.构造真值表证明等价式6.不构造真值表证明蕴含式7.范式与主范式8.应用P、T规则的推理证明9.CP规则与间接推理证明基本要求：数理逻辑的任务是采用数学方法研究抽象的思维规律，研究的中心问题是推理，而推理基本要素是命题，故学习本章首先要深刻理解命题的概念。理解原子命题与复合命题的关系，在了解复合命题的基础上，理解联结词的定义。命题演算中两个重要内容是命题公式的范式表示与命题的推理理论，前者主要是命题公式化简与主范式表示，后者则需要熟悉直接推理与间接推理两种方法。重点：命题概念及其表示、命题公式化简、主范式及其互化、P规则、T规则以及CP规则。难点：推理理论及应用。教学要点：掌握： 命题、逻辑联结词的概念；公式与解释的概念，公式的递归定义，用基本等价式化简其他公式；主析取范式及其唯一性，用真值表法判断公式的类型；公式蕴涵与逻辑结果的概念；推理理论及应用。理解：用联结词产生复合命题的方法；公式在解释下的真值；公式范式的概念；形式演绎和蕴涵的关系。二 谓词演算（4学时）主要内容：1.谓词概念2.量词及合式公式3.谓词演算的等价式与蕴含式4.谓词演算的推理理论基本要求：谓词演算是命题演算的继续和深入，它不仅研究命题间的逻辑结构，而且要考察命题间的内部性质。在命题演算中，基本主成单位是原子命题并且把它看成是不可分解的。在谓词演算中，对于命题的内部逻辑结构作了进一步刻画分析，在此引进了客体和谓词概念。在讨论谓词公式中引入量词及其辖域的概念，对于带量词的谓词公式，也存在公式变换和推理理论。本章的重点是带量词的公式变换，即前束范式。难点是谓词演算的推理理论。本章在重点讲解清楚谓词概念情况下，对带量词的蕴含，等价公式表只作解释性推论。重点：带量词的公式变换，即前束范式。难点：谓词演算的推理理论。本章在重点讲解清楚谓词概念情况下，对带量词的蕴含，等价公式表只作解释性推论。教学要点：掌握：个体词、个体域、谓词、量词的概念和使用；原子、公式、解释的概念；公式在解释下的真值；求公式的前束范式；谓词演算的推理理论理解：用谓词、量词、逻辑联结词描述一个简单命题；公式的递归定义；用解释的方法证明等价式和蕴涵式。了解：以谓词逻辑为工具，将命题符号化。 三 集合与二元关系（8学时）主要内容：1.集合概念与运算2.关系概念与运算3.关系表示法与性质4.关系矩阵与闭包5.等价关系与划分6.序关系基本要求：集合论式现代各学科数学的基础。本章从集合概念出发，引出了关系的种运算性质，即等价关系与序关系等。 集合代数的运算与逻辑代数性质相对应。这为以后代数系统的讨论做出准备。重点：关系运算及分类，还有相容关系，等价关系与序关系等有关性质。难点：关系闭包概念及求法，这里将略去复杂的证明。映射的一些定理证明，亦从略。教学要点：掌握：子集、空集、全集、相等、幂集等基本概念；集合的表示法；集合的交、并、差、补等概念；交换律、结合律、分配律、De Morgan律等运算律，证明集合等式；序偶与迪卡尔积的概念和应用；关系的概念；关系的性质；自反闭包、对称闭包、传递闭包的概念；等价关系与等价类的概念，划分的有关概念；偏序关系、偏序集的概念及用哈斯图表示；函数的概念。 理解：文氏图；关系矩阵与关系图；复合关系与逆关系的概念及求法；单射、满射、双射的概念；复合函数与反函数的概念。 了解：序关系与序集的概念。四 图 论（10学时）主要内容：1.图的基本概念2.图的连通性3.欧拉图与哈密尔顿图4.平面图与偶图5.二部图与匹配6.树及其应用基本要求：现实世界中许多状态变化，都可由图形描述。图形表达事物是现代科学技术中的一种重要手段。图形不仅形象直观，而且可以结合数据，可以数形结合便于计算。重点：图的连通性，平面图、二部图的最大匹配和树的应用。难点：哈密尔顿图和图的着色问题，对平面图的判定，只作介绍不作深入证明。教学要点：掌握：图的有关概念；用关联矩阵和相邻矩阵表示图；路的基本概念，权图的概念，用Dijkstra算法求权图中最短路；欧拉图判定及应用；哈密尔顿图定义及必要判定条件；平面图概念，平面欧拉公式及其应用；二部图的概念，二部图的最大匹配及应用；树、二叉树与支撑树的有关概念；用Kruskal算法求权图中最小树。理解：图的连通、同构的概念；树的等价定理；有向图与有向树的概念。五、教学方法建议在有条件的情况下，利用网络资源、多媒体等教学手段为教学服务。六、考核方式闭卷考试七、其它说明（如习题或作业，实践环节内容和要求）至少完成书上习题的三分之一。八、选用教材及主要参考书（名称、编著者、出版社、出版时间）1、教材离散数学屈婉玲等编 清华大学出版社 1999年9月2、参考书离散数学方世昌等编 西安电子科技大学出版社 1985年1月离散数学乔维声编著 西安电子科技大学出版社 1989年6月离散数学马叔良等编 电子工业出版社 1997年6月离散数学美Richard Johnsonbaugh著离散数学，人民邮电出版社 2003年9月3、习题辅导书2000离散数学习题精解 美S.利普舒茨 M.L.利普森 著 林成森 译 2002年3月离散数学题解屈婉玲 耿素云 张立昂编著 清华大学出版社 1999年9月 离散数学习题与解析胡新启 胡元明 清华大学出版社 2002年1月九、学时分配课程内容讲课实验大作业1.1 命题符号化及联结词1.2命题公式及分类1.3等值演算1.4范式1.5推理理论22400012.1一阶逻辑的基本概念2.2一阶逻辑合式公式及解释2.3一阶逻辑等值式2.4一阶逻辑推理理论22024.1集合的有关概念与二元关系4.2关系的运算4.3关系的性质22024.4关系的闭包4.5等价关系4.6偏序关系22027.1无向图及有向图7.2通路 回路 图的连通性7.3图的矩阵表示8.1二部图22028.2欧拉图8.3哈密尔顿图8.4平面图22029.1无向树及生成树9.2根树及其应用复习机动2202合计32编写负责人：郑斌审核：郑克龙部门主管领导：周自刚