离散数学课程教学大纲一、课程简介课程名称：离散数学英文名称：Discrete Mathematics课程代码：0310513 课程类别：专业基础课学 分：3 总 学 时：48课程概要：离散数学是现代数学的一个重要分支，是计算机类各专业的一门重要基础课，是计算机科学理论的基础。它是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是有限个或可列个元素，因此它充分描述了计算机科学的离散性特点。其主要内容包括数理逻辑、集合论、关系与函数、图论等内容。该课程与计算机类专业中的数据结构、操作系统、编译原理、数据库原理与应用、人工智能等后继专业课程紧密相关，因此是一门重要的学科基础必修课程。该课程以高等数学、线性代数为先修课程，但关系不很紧密。二、教学目的及要求通过该课程的学习，使学生掌握命题逻辑与谓词逻辑、集合与关系、图与树的基本概念和基本理论与方法，为学生学习计算机领域的后续课程奠定理论基础，并培养学生抽象思维、缜密概括和严密的逻辑推理能力，为学生今后处理离散信息打好数学基础。三、教学内容及学时分配第一章 命题逻辑（12学时）1.命题及其表示；2.逻辑联结词；3.命题公式与翻译；4.真值表与等价公式；5.命题公式的分类与蕴含式；6.命题公式的范式；7. 命题逻辑的推理理论。教学要求：熟悉命题、命题的真值、简单命题、复合命题、命题公式、真值表、等价公式、重言式、矛盾式、蕴涵式、（主）析取范式、（主）合取范式等概念；熟悉五个基本联结词（、）的定义；掌握命题公式的翻译、命题公式的类型的判别、命题定律、证明两个命题公式等价的真值表法和等值演算法及命题公式的（主）析取范式、（主）合取范式的求法；掌握推理证明的直接证法和间接证法。重点：五个逻辑联结词；翻译、命题公式的等值演算、主析取范式、主合取范式；推理证明的直接证法和间接证法。难点：命题公式的主析取范式、主合取范式的求法；推理证明的间接证法。第二章谓词逻辑（10学时）1.谓词与量词；2.谓词公式与翻译；3.变元的约束；4.谓词演算的等价式与蕴含式；5.谓词演算的推理理论。教学要求：熟悉谓词、命题函数、复合命题函数、全称量词、存在量词、谓词公式、辖域、约束变元、自由变元、谓词演算的等价式与蕴涵式、前束范式等概念；掌握谓词演算翻译、谓词演算的等价式、谓词演算的推理规则及谓词演算的推理证明的方法。 重点：谓词演算翻译、两个谓词公式等价的证明；谓词演算的推理证明。难点：谓词演算翻译、谓词演算的推理证明。第三章 集合的基本概念与运算（2学时）1.集合的基本概念；2.集合的运算。教学要求：熟悉集合的概念和表示法；掌握幂集的概念；掌握集合的交、并、差、补、对称差的运算及其运算律和幂集的求法。重点：集合的运算及其运算律；幂集的求法。难点：元素为集合组成的集合的运算与求幂集。第四章 二元关系和函数（12学时）1.关系及其表示；2.关系的性质及其判定方法；3.复合关系和逆关系；4.关系的闭包；5.等价关系；6.偏序关系；7.函数及特殊映射；8.复核映射和逆映射。教学要求：熟悉序偶、笛卡尔积、关系、集合的划分与覆盖、等价关系、等价类、商集、偏序关系、极大元、极小元、上（下）界、上（下）确界、最大（小）元、全序关系、良序关系等概念；掌握关系的三种表示 序偶集合、关系图和关系矩阵；掌握关系的交、并、逆、复合运算、闭包运算及其性质；理解关系的自反性、反自反性、对称性、反对称性和传递性，掌握其判别方法；了解集合的覆盖与划分的联系与区别；掌握等价关系与等价类、等价关系与集合的划分的联系；掌握偏序关系的判别及其哈斯图的画法；掌握偏序集中给定集合的极大元、极小元、上（下）界、上（下）确界、最大（小）元；掌握函数（映射）、函数的前域、值域、相等、入射、满射、双射、恒等映射、反函数、复合函数的概念；掌握函数与一般关系的区别；掌握函数复合运算的性质、反函数存在的条件；掌握函数是入射、满射、双射的证明。重点：关系的三种表示；关系的性质及其判别；关系的复合、求逆运算及其性质；等价关系与等价类、等价关系与集合的划分的联系；偏序关系判别及其哈斯图的画法、偏序集中特殊位置元素的求法。复合运算的性质；函数与一般关系、反函数与逆关系的区别；函数是入射、满射、双射的证明。难点：关系的传递性及其判别；偏序关系的哈斯图的画法；偏序集中特殊位置元素的求法。函数是入射、满射、双射的证明。第五章 图的基本概念（5学时）1.图的基本概念；2.路与图的连通性；3.图的矩阵表示。教学要求：掌握图、点邻接、边邻接、子图、结点的度数、出度、入度、有向图、无向图、简单图、完全图、补图、生成子图、图的同构、及其性质；掌握握手定理、路、回路、连通图、强连通、单向连通、弱连通、割点、割边的概念；掌握图的矩阵表示，利用图的邻接矩阵会求（1）任一结点的入度、出度和度数；（2）一个结点到另一个结点长度为k的路径的条数；（3）该图的可达性矩阵。重点：图、点邻接、边邻接、结点的度数的概念；握手定理（结点的度数及其相关性质）；路、回路、连通图、强连通、单向连通、弱连通、割点、割边的概念；图的邻接矩阵。难点：握手定理的应用；弱连通、强连通的判别。第六章 一些特殊的图（讲课3学时）1.欧拉图与汉密尔顿图；2.平面图。教学要求：掌握欧拉图、汉密尔顿图和平面图的定义、判别及其应用。重点：欧拉图、汉密尔顿图和平面图的定义、判别及其应用。难点：欧拉图、汉密尔顿图和平面图的判别及其应用。第七章 树 （讲课4学时）1.树与生成树；2.根树及其应用；3.最短路问题。教学要求：掌握树、生成树、最小生成树、根树、树根、树叶、分枝点、有序树、完全m叉树、最优树等概念及其有关性质；掌握有关树的几个等价命题；熟练应用最小生成树的Kruskal算法及最优二叉树的Huffman构造方法。重点：树、生成树、最小生成树、根树、树根、树叶、分枝点、完全m叉树、最优树等概念及其有关性质；有关树的几个等价命题；最小生成树的Kruskal算法及最优二叉树的Huffman构造方法。难点：树的几个等价命题。四、课程教学的基本要求1课堂讲授（48学时）采用启发式教学，引导、吸引和鼓励学生通过教学过程获取知识，从中培养学生思考问题、分析问题和解决问题的能力；强化基本概念的理解与基本思想方法的掌握，加强例题的讲解和课上练习，精心留课后作业，注重课上和作业反馈的作用和质量。2教学手段主要教学手段是采用投影仪和电脑使用多媒体课件组织教学，辅助教学手段是黑板板书讲解。3习题课、课外作业、答疑重点安排在命题公式和谓词公式的翻译、范式的求法及推理证明；关系的表示与判定；偏序集中的特殊元；利用图的邻接矩阵求一个结点到另一个结点长度为k的路径的条数；最小生成树的Kruskal算法及最优二叉树的Huffman构造方法。五、考核方式课程综合评定成绩中，期末考试成绩占70%，平时成绩占30%；结课考试采用闭卷笔试，题型分为选择题、填空题、简答题和证明题。平时成绩分配是考勤及听课状况占10%； 作业及测验占20%。