《离散数学》教学大纲

1、离散数学（Discrete Mathematics）课程代码：2131032学分：3 学时：48 （其中：课程教学学时：48，实验学时：0）先修课程：高等数学，线性代数适用专业：计算机科学与技术教材：离散数学，冯伟森，栾新成，石兵编著，机械工业出版社，2011开课学院：计算机与软件学院一、课程性质与课程目标（一）课程性质离散数学是高等工科院校计算机类相关专业的一门重要学科基础必修课，是学习后续计算机专业课程不可或缺的数学工具，包括数据结构、数据库系统、计算机网络、算法设计和人工智能等课程。该课程结合计算机学科的特点，主要研究离散量的结构及相互关系，是一门理论性较强、应用性较广的课程，也是培养学

2、生抽象思维能力和逻辑推理能力的核心课程。（二）课程目标课程目标包括知识目标和能力目标，具体如下：课程目标1：理解逻辑演算系统、集合论、图论和代数系统的基本概念，掌握从基本概念出发的计算和证明方法，培养逻辑思维和逻辑推理能力。课程目标2：掌握命题公式、集合运算、二元关系、函数、图的最短路径、代数系统特异元等离散结构求解方法；通过严格数学证明的讲授，使学生逐步习惯于以概念和公理为出发点的抽象思维方式，并初步掌握严谨数学论证的基本规范。课程目标3：能够利用逻辑演算、集合论、图论和代数系统的基本概念和方法对计算机领域复杂工程问题进行抽象、分析、推理、求解和验证。（三）课程目标与专业毕业要求指标点的对应

3、关系本课程支撑专业培养计划中的毕业要求指标点1.1和2.1。毕业要求指标点1.1：掌握数学与自然科学的基本概念、基本理论和基本技能，领会数学、物理思想方法，培养逻辑思维和逻辑推理能力。毕业要求指标点2.1：应用数学、自然科学和工程科学的基本原理，针对一个系统或者过程进行抽象、分析与识别，并进行问题推理、求解和验证。课程目标毕业要求指标点课程目标1课程目标2课程目标3毕业要求1.1毕业要求2.1二、课程内容及教学要求（按章撰写）本课程主要教学内容包括：命题逻辑、集合论、图论和代数系统等基本知识。数理逻辑部分主要讲授命题与命题联结词、命题逻辑演算等。集合论部分主要介绍集合基本概念、集合的运算、函数

4、、关系及其运算、等价关系与集合划分、偏序关系等。图论部分主要讲授无向图、有向图、通路、回路和图的连通性、最短路径、关键路径以及两种特殊图（欧拉图和哈密顿图）。代数部分则主要介绍二元运算及其性质、代数系统及其特异元、几个典型的代数系统、以及代数系统间的同态与同构关系。本课程基本要求是：理解各个联结词的定义和关系，能够把命题公式转化为等价的主析取范式或主合取范式，能够把自然语言翻译成数学语言，并给出推证过程；理解集合的基本概念和运算，理解关系及其性质，掌握几个重要的关系以及偏序集特殊元素的求取；理解图论的一些基本概念，掌握一些基本的图论算法，包括最短路径求解的Dijkstra算法等；理解代数系统的

5、基本概念，理解代数系统中特异元的基本概念并掌握这些元素的求解方法，理解代数系统之间的同态和同构关系；针对常见的应用问题，能应用离散数学的基本原理进行抽象、分析、推理、求解和验证。第1章命题逻辑教学内容命题及其真值重言式范式联结词的扩充与归约。推理规则和证明方法。（二）教学要求掌握命题、命题联结词的概念；理解命题公式的递归定义，熟练掌握命题符号化的方法，掌握命题公式真值表的求法；理解公式等值的定义，掌握运用基本等值式进行等值演算的方法。了解范式的概念，掌握求命题公式的析取范式、合取范式和主式的方法。了解与非、或非、异或等联结词及联结词的归约。掌握常用的推理规则和证明方法。（三）重点与难点1. 重

6、点命题、命题联结词的概念；自然语言翻译成数学语言；重言式与蕴含式；求命题公式的析取范式、合取范式和主式的方法；推理规则。2. 难点命题公式与翻译；推理规则。第3章集合代数（一）教学内容集合论的基本概念集合的运算集合的笛卡尔乘积（二）教学要求掌握子集、空集、全集、相等、密集等基本概念。理解集合的基本概念表示法；掌握集合的交、并、差和补等概念及交换律、结合律、分配律和De Morgan律等运算律，证明集合等式。掌握集合的笛卡尔乘积的运算。（三）重点与难点1.重点集合的概念与表示；集合的运算；序偶与笛卡尔积。2.难点序偶与笛卡尔积。第4章二元关系（一）教学内容关系的基本概念关系的运算关系上的闭包运算

7、（二）教学要求理解关系及有关概念，掌握关系图、关系矩阵及关系的特性（自反性、反自反性、对称性、反对称性和传递性）。掌握关系的合成、关系的幂关系、关系合成及其有关性质。掌握逆关系、关系的闭包运算（自反闭包、对称闭包和传递闭包）的性质及求法。（三）重点与难点1.重点关系的概念；关系的性质；关系的闭包运算；复合关系与逆关系。2.难点关系的闭包运算；复合关系与逆关系。第5章特殊关系（一）教学内容次序关系等价关系和划分函数的基本概念特殊函数类逆函数（二）教学要求掌握偏序集合、拟序集合、线序集合、良序集合及特殊元素的概念及性质。理解等价关系、覆盖及划分的概念，掌握求集合的等价类方法及划分的积与和。（三）重

8、点与难点1.重点等价关系与等价类；序关系；特殊元素的概念和求法。2.难点等价关系与等价类；序关系。第6章函数（一）教学内容函数的基本概念特殊函数类逆函数集合的基数、可数集和不可数集（二）教学要求理解函数的概念，掌握函数的合成运算。理解满射、单射和双射函数的概念，了解置换、特征函数的概念及运算。理解逆函数和规范映射的概念及性质。掌握集合基数的概念会判断一个集合是可数集还是不可数集（三）重点与难点1.重点满射、单射和双射函数的概念和判断；逆函数与复合函数；可数集和不可数集的判断。2.难点可数集和不可数集的判断。第8章基本计数方法（一）教学内容1. 容斥原理2. 鸽巢原理（二）教学要求理解容斥原理和

9、鸽巢原理的原理。会应用容斥原理和鸽巢原理去解决实际问题。（三）重点与难点1.重点容斥原理及其应用；鸽巢原理及其应用。2.难点应用容斥原理和鸽巢原理解决实际问题。第10章图的基本概念（一）教学内容图的基本概念路径和回路图的矩阵表示（二）教学要求理解图的基本概念，了解几类特殊的图。理解路径与回路及有关概念（基本路径、简单路径、基本回路和简单回路），了解连通图的概念（强连通、单向连通、弱连通、强分图、单向分图和弱分图）。掌握图的矩阵表示（邻接矩阵和可达性矩阵）。（三）重点与难点1.重点图的基本概念；握手定理；连通性；图的表示。2.难点应用握手定理解决实际问题。第11章树及其应用（一）教学内容无向树及

10、其性质生成树（二）教学要求理解无向树和生成树的概念掌握用Kruskal算法求最小生成树。（三）重点与难点1.重点树的基本概念；生成树的概念；Kruskal算法求最小生成树。2.难点Kruskal算法求最小生成树。第13章欧拉图与哈密顿图（一）教学内容欧拉回路与欧拉图哈密顿回路与哈密顿图（二）教学要求掌握欧拉路径、欧拉回路和欧拉图的判别法。理解哈密尔顿路径、哈密尔顿回路和哈密尔顿图的概念，掌握哈密顿图的判定。（三）重点与难点1.重点欧拉图的概念和判定；哈密顿图的概念和判定。2.难点哈密顿图的判定。第14章代数系统教学内容二元运算及其性质代数系统及其特异元广群、半群和群（二）教学要求理解二元运算的

11、定义，熟练掌握二元运算性质的判断及证明。理解代数系统的基本概念。理解代数系统中特异元（单位元、逆元）的基本概念，掌握这些元素的求解方法。理解代数系统广群、半群、群、环和域的基本概念，掌握特殊代数系统的判定方法。（三）重点与难点1.重点二元运算及其性质的判断及证明；代数系统的特异元；特殊代数系统的判断与证明。2.难点二元运算性质的判断及证明；代数系统的特异元求取；特殊代数系统的判断与证明。第15章半群与群教学内容子群和正规子群群的同态与同构（二）教学要求了解子群、子群的陪集以及正规子群的概念。掌握群的同态和同构定义，会证明。（三）重点与难点1.重点群的同态和同构的证明。2.难点群的同态和同构的证

12、明。第16章环与域教学内容环和域（二）教学要求掌握环和域的定义，判断与证明。（三）重点与难点1.重点环和域的判断与证明。2.难点环和域的判断与证明。三、学时分配及教学方法章教学形式及学时分配主要教学方法支撑的课程目标课堂教学实验上机课程实践小计第1章命题逻辑1010讲授、案例、演示、讨论课程目标1， 2，3第3章集合代数22讲授、案例、自学课程目标1， 2第4章二元关系33讲授、案例、对比、讨论课程目标1， 2， 3第5章特殊关系33讲授、案例、对比、讨论课程目标1， 2， 3第6章函数44讲授、案例、讨论课程目标1， 2， 3第8章基本计数方法22讲授、案例、讨论课程目标1， 2， 3第10

13、章图的基本概念44讲授、案例、演示、讨论课程目标1， 2第11章树及其应用33讲授、案例、演示、讨论课程目标1， 2第13章欧拉图与哈密顿图33讲授、案例、研究型、讨论课程目标1， 2， 3第14章代数系统22讲授、案例、研究型、讨论课程目标1， 2， 3第15章半群与群44讲授、案例、研究型、讨论课程目标1， 2， 3第16章环与域22讲授、案例、研究型、讨论课程目标1， 2， 3习题课66讲授、讨论课程目标1， 2， 3合计4848注：1.课程实践学时按相关专业培养计划列入表格； 2.主要教学方法包括讲授法、讨论法、演示法、研究型教学方法（基于问题、项目、案例等教学方法）等。四、课程考核

14、1. 课程考核方式包括期末考试、平时表现考核。考核形式考核要求考核权重备注平时作业及期中考试课后完成2025个习题，主要考核学生对每节课知识点的复习、理解和掌握度，计算全部作业的平均成绩再按30%计入总成绩；可让学生查阅资料，了解本课程相关技术发展情况，自主学习并完成。30%根据平时作业得分取平均值或结合期中测试和考勤情况期末考试试卷题型包括选择题、填空题、判断题、计算题、应用题和证明题等，以卷面成绩的70%计入课程总成绩。70%期末考试采用闭卷笔试。五、参考书目及学习资料左孝凌等编，离散数学(第一版)，上海科学技术文献出版社，1982。段禅伦、魏仕民编著，离散数学(第一版)，北京大学出版社，2006。耿素云、屈婉