[离散数学]

本科课程教学大纲（理工医类/电气学院）

一、课程描述及课程目标

（一）课程描述

离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术相关领域有着广泛的应用。

教学内容以基本概念、结论、算法、推理与证明方法，以及一般应用方法的介绍为主，主要内容包括数理逻辑、集合论、与图论等内容。

通过本课程的学习，要求学生理解离散数学的基本概念、结论、算法、应用方法及适用范围；了解和掌握处理离散结构的描述工具和方法；提高抽象思维和严格的逻辑推理能力，为后续课程的学习及将来从事计算机软硬件技术开发打好必要的理论基础。

（二）课程目标

本课程为计算机类专业的专业限选课程，要求学生能够应用离散数学的基本知识来解决实际问题，通过本课程的学习，学生应达到下列学习目标:

1. 掌握离散数学基本知识及技能，核心能力1.1。

2. 能够运用离散数学相关理论解决生活中的相关问题，核心能力1.2和5.1。

3. 能够主动做好课前预习和课后实践，养成自主学习的意识和提高不断学习的能力，核心能力6.2。

二、课程内容

（一）第1章 命题逻辑的基本概念

主要知识点:

1.1命题与联结词

1.2命题公式及其赋值

教学要求:通过本章学习，了解命题概念，掌握五种联结词与真值表的构造；理解命题公式的概念，掌握命题公式类型的判断。

重点:命题联结词、命题公式。

采用的教学方法:知识点讲解、习题讲解。

讲授学时:2.5学时

讲解习题:0.5学时

（二）第2章 命题逻辑等值演算

主要知识点:

2.1等值式

2.2 析取范式与合取范式

2.3 联结词的完备集

教学要求:通过本章学习，理解等值式、析取范式、合取范式的概念；掌握命题公式的等值演算，理解析取范式与合取范式的概念，掌握主析取范式与主合取范式的求解方法；

重点:主析取范式与主合取范式

难点:主析取范式与主合取范式的求解

采用的教学方法:知识点讲解、习题讲解。

讲授学时:4学时

讲解习题:2学时

（三）第3章 命题逻辑的推理理论

主要知识点:

3.1 推理的形式结构

3.2 自然推理系统P

教学要求:通过本章学习，理解推理的形式结构，命题逻辑的推理理论；掌握自然推理系统P。

重点:命题逻辑的推理理论。

难点:利用命题逻辑的推理理论进行命题逻辑推理。

采用的教学方法:知识点讲解、习题讲解。

讲授学时:2学时

讲解习题:1学时

（四）第4章 一阶逻辑的基本概念

主要知识点:

4.1一阶逻辑命题符号化

4.2一阶逻辑公式及解释

教学要求:通过本章学习，理解一阶逻辑的基本概念，掌握一阶逻辑命题符号化，掌握一阶逻辑公式及其解释。

重点:一阶逻辑命题符号化、一阶逻辑公式及解释。

难点:一阶逻辑命题符号化、一阶逻辑公式及解释。

采用的教学方法:知识点讲解、习题讲解。

讲授学时:2时

讲解习题:1学时

（五）第5章 一阶逻辑等值演算

主要知识点:

5.1一阶逻辑等值式与置换规则

5.2一阶逻辑前束范式

教学要求:通过本章学习，了解一阶逻辑等值式、一阶逻辑前束范式的概念；掌握一阶逻辑等值式的置换规则；掌握命题路基公式前束范式的求解。

重点:

难点:

采用的教学方法:知识点讲解、习题讲解。

讲授学时:2学时

讲解习题:1学时

（六）第6章 集合代数

主要知识点:

6.1 集合的基本概念

6.2 集合的运算

6.3 有穷集的计数

6.4 集合恒等式

教学要求:通过本章学习，了解集合的基本概念，掌握集合的运算，以及有穷集的计数。

重点:集合的运算。

难点:集合的运算和有穷集的计数。

采用的教学方法:知识点讲解、习题讲解。

讲授学时:2学时

讲解习题:1学时

（七）第7章 二元关系

主要知识点:

7.1 有序对与笛卡儿积

7.2 二元关系

7.3 关系的运算

7.4 关系的性质

7.5 关系的闭包

7.6 等价关系与划分

7.7 偏序关系

教学要求:通过本章学习，了解有序对、笛卡尔积和二元关系的基本概念，掌握关系的运算和关系的性质，掌握关系闭包的求解；掌握等价关系与划分和偏序关系。

重点:关系的运算和性质、关系的闭包、等价关系和划分、偏序关系

难点:关系的闭包、偏序关系。

采用的教学方法:知识点讲解、习题讲解。

讲授学时:7学时

讲解习题:2学时

（八）第8章 函数

主要知识点:

8.1 函数的定义与性质

8.2 函数的复合与反函数

8.3 双射函数与集合的基数

教学要求:通过本章学习，了解函数的定义及性质，掌握函数的复合与反函数，掌握双射函数的判断。

重点:函数的复合与反函数

难点:函数符合的求解、反函数的求解与双射函数的判定。

采用的教学方法:知识点讲解、习题讲解。

讲授学时:2.5学时

讲解习题:0.5学时

（九）第9章 图的基本概念

主要知识点:

9.1 图

9.2 通路与回路

9.3 图的连通性

9.4 图的矩阵表示

教学要求:通过本章学习，了解图的基本概念，掌握图的通路和回路的求解，掌握图的连通性的判定和图的各种矩阵表示。

重点:图的通路与回路、图的连通性、图的矩阵表示。

难点:图的连通性。

采用的教学方法:知识点讲解、习题讲解。

讲授学时:3.5学时

讲解习题:2.5学时

（十）第10章 树

主要知识点:

10.1 无向树及其性质

10.2 生成树

10.3 根树及其应用

教学要求:通过本章学习，了解无向树及其性质，掌握生成树的概念及求解，掌握根树及其应用。

重点:生成树、根树

难点:生成树和根树。

采用的教学方法:知识点讲解、习题讲解。

讲授学时:3学时

讲解习题:3学时

（十一）第11章 几种特殊的图

主要知识点:

11.1 欧拉图

11.2 哈密顿图

11.3 二部图与匹配

11.4 平面图

教学要求:通过本章学习，了解欧拉图、哈密顿图、二部图和平面图的概念，掌握欧拉图、哈密图的判定，掌握二部图与匹配及应用，掌握平面图着色。

重点:欧拉图、二部图与匹配、平面图。

难点:二部图与匹配、平面图着色。

采用的教学方法:知识点讲解、习题讲解。

讲授学时:4学时

讲解习题:2学时

三、课程的预期学习成果

在本门课程结束时，学生应该能够:

1. 掌握析取范式与合取范式的求法，自然推理系统的推理理论；一阶逻辑的推理理论，在一阶逻辑中构造推理证明的方法。

2.掌握二元关系的运算、关系的性质、关系的闭包，掌握等价关系和划分及偏序关系，掌握判断函数单射、满射、双射的方法。

3. 掌握图的矩阵表示，求最短路程与路线的方法；掌握用闭圈法求最小生成树的方法，用算法求最优树、最佳前缀码的方法。

4. 提高学生的抽象思维和逻辑推理能力上有较好提高

四、课程要求

（一）出勤

学生应积极参与课堂教学并完成相关的作业。

（二）阅读资料

学生应认真进行课前预习，阅读教材和指定参考书及重要的参考文献。

（三）课堂演示

结合理论课教学内容，教师课堂内容和习题讲解、同学讨论。

（四）课程实验

本课程是理论的课程，不安排课外实践作为课程内容。

（五）小考与期末考

课程中随机问答。期末考试形式为闭卷笔试。

（六）学术诚信

按中山大学南方学院相关规定执行。

（七）剽窃的定义以及相应的惩罚

剽窃是严重违反学校规章制度的行为。一经发现，将上报相关部门，并受到包括开除学籍在内的严厉处罚。

五、课程资料

（一）教科书-必读

1. 屈婉玲,耿素云,张立昂，《离散数学及其应用（第2版）》，高等教育出版社，2018,12

（二）教科书-强烈推荐

1. 耿素云，屈婉玲编著，《离散数学》北京大学出版社，2002年

2. 王瑞胡等主编，离散数学及其应用，清华大学出版社，2014

（三）文章-必读

近年《计算机学报》、《软件学报》等国内、国际期刊杂志刊登的文章。

（四）文章-强烈推荐

无

（五）其他参考资料

1. Kenneth.Rosen 著，袁崇义 屈婉玲 等译,《离散数学及其应用》（原书第6版）, 机械工业出版社 2011

六、教学活动以及对于预期学习成果的评估

（一）教学活动

1、个人预习

2、课堂讲授

3、课堂问答

4、习题讲解

5、案例讨论

6、期中考试

7、期末考试

（二）对预期学习成果的考察

七、评估的程序和方法

（一）评分体系

1、平时成绩: 40%

平时成绩由考勤、课堂参与（加分）、课后作业、课堂实验组成，各部分占比如下:

（1）考勤: 20%

（2）课堂参与: 加分

（3）课后作业: 20%

2、期中考试: 10%

3、期末考试: 50%

（二）考试内容及要求

考试包含以下内容:

1. 离散数学的基本语法知识及使用（核心能力1.1）；

2. 能够利用离散数学的理论解决计算机工程问题（核心能力5.1）；

八、教学进度与学时分配表