课程简介
Course Introduction
教学大纲
Teaching Syllabus
离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术相关领域有着广泛的应用。
教学内容以基本概念、结论、算法、推理与证明方法，以及一般应用方法的介绍为主，主要内容包括数理逻辑、集合论、与图论等内容。
通过本课程的学习，要求学生理解离散数学的基本概念、结论、算法、应用方法及适用范围；了解和掌握处理离散结构的描述工具和方法；提高抽象思维和严格的逻辑推理能力，为后续课程的学习及将来从事计算机软硬件技术开发打好必要的理论基础。
（一）第1章 命题逻辑
主要知识点:
1.1命题与逻辑联结词
1.2命题公式及公式分类
1.3等值式与等值演算
1.4范式与主范式
1.5推理理论
教学要求:通过本章学习，了解命题概念，掌握五种联结词与真值表的构造；理解命题公式的概念，掌握命题公式类型的判断；理解等值式的概念，掌握命题公式的等值演算；理解析取范式与合取范式的概念，掌握主析取范式与主合取范式的求解方法；理解推理的形式结构与推理定律，掌握形式证明的方法与技巧。
重点:主析取范式与主合取范式及命题逻辑的推理理论。
难点:主析取范式与主合取范式的求解、推理理论及应用。
采用的教学方法:知识点讲解、习题讲解。
讲授学时:8学时
讲解习题:1学时
（二）第2章 谓词逻辑
主要知识点:
2.1基本概念
2.1谓词公式
2.3谓词逻辑蕴含式和等值式
2.4前束范式
2.5谓词逻辑推理理论
教学要求:通过本章学习，理解谓词、量词、变元、个体域等概念；掌握用谓词、量词、联结词构造谓词逻辑公式的方法。理解一阶逻辑公式的概念及其解释，掌握简单一阶逻辑公式类型的判断方法；理解一阶逻辑置换规则、换名规则、代替规则，掌握一阶逻辑基本等值式的使用；掌握一阶逻辑公式前束公式的求解方法；能够以谓词逻辑作为工具，将命题符号化，并能用推理规则进行逻辑证明。
重点:一阶逻辑的概念与表示，一阶逻辑公式及其解释，一阶逻辑的等值式与置换规则，一阶逻辑的推理理论。
难点:一阶逻辑公式类型的判断和一阶逻辑的推理证明。
采用的教学方法:知识点讲解、习题讲解。
讲授学时:8学时
讲解习题:1学时
（三）第3章 关系
主要知识点:
3.1笛卡儿积
3.2关系的概念与表示方法
3.3关系的运算
3.4关系的性质
3.5关系的闭包
3.6关系等价与划分
3.7偏序关系
教学要求:通过本章学习，理解笛卡儿积与二元关系的概念，掌握关系的表示、运算与性质；理解关系闭包的定义，掌握关系闭包的求解方法；理解等价关系、划分与偏序关系的定义，掌握等价关系和偏序关系的结构。
重点:等价关系与偏序关系的结构及应用、关系的闭包与算法。
难点:关系的闭包与算法。
采用的教学方法:知识点讲解、习题讲解。
讲授学时:8学时
讲解习题:1学时
（四）第4章 函数
主要知识点:
4.1函数的概念
4.2特殊函数
4.3逆函数与复合函数
4.4几个重要的函数
4.5函数的应用
教学要求:通过本章学习，理解函数的基本概念，掌握函数的性质；掌握逆函数和复合函数的基本概念与性质；。
重点:逆函数和复合函数的性质。
难点:逆函数和复合函数的性质。
采用的教学方法:知识点讲解、习题讲解。
讲授学时:5学时
讲解习题:1学时
（五）第5章 图论
主要知识点:
5.1图的定义及相关概念
5.2通路、回路与连通图
5.3图的矩阵表示
5.4欧拉图与哈密顿图
5.5最短路径问题与货郎担问题
5.6平面图和图的着色
教学要求:通过本章学习，了解图论的基本内容及其在计算机领域中的应用；理解图的基本概念、子图与补图概念，通路与回路的概念、图的连通性与连通度的概念、欧拉图与汉密尔顿图的概念、树及最优树的概念；掌握图的表示方法、图的可达性与连通性的判断；掌握图的通路与回路的判断、图的连通性的判断；掌握欧拉图与汉密尔顿图的判定方法；掌握求最小生成树的Kruskal算法、求最优树的Huffman算法。
重点:握手定理及其推论的应用、图中通路和回路应用、图中的可达性和连通性的求解方法、欧拉图判定、哈密顿图判定、最短路径及应用、最小生成树。
难点:图的连通性的有关定理、图的同构及哈密尔顿图的判定。
采用的教学方法:知识点讲解、习题讲解。
讲授学时:7学时
讲解习题:2学时
（六）第6章 树
主要知识点:
6.1无向树及性质
6.2根树
6.3生成树
6.4树的应用
教学要求:通过本章学习，了解树、生成树、最小生成树的基本概念，掌握求最优二叉树的Huffman算法，以及求最小生成树的Kruskal算法和Prim算法。
重点:二叉树的遍历及搜索，Huffman算法，最小生成树以及Kruskal算法和Prim算法。
难点:Huffman算法、Kruskal算法、Prim算法。
采用的教学方法:知识点讲解、习题讲解。
讲授学时:7学时
讲解习题:2学时
在本门课程结束时，学生应该能够:
1. 掌握析取范式与合取范式的求法，自然推理系统的推理理论；一阶逻辑的推理理论，在一阶逻辑中构造推理证明的方法。
2.掌握二元关系的运算、关系的性质、关系的闭包，掌握等价关系和划分及偏序关系，掌握判断函数单射、满射、双射的方法。
3. 掌握图的矩阵表示，求最短路程与路线的方法；掌握用闭圈法求最小生成树的方法，用算法求最优树、最佳前缀码的方法。
4. 提高学生的抽象思维和逻辑推理能力上有较好提高
（一）出勤
学生应积极参与课堂教学并完成相关的作业。
（二）阅读资料
学生应认真进行课前预习，阅读教材和指定参考书及重要的参考文献。
（三）课堂演示
结合理论课教学内容，教师课堂内容和习题讲解、同学讨论。
（四）课程实验
本课程是理论的课程，不安排课外实践作为课程内容。
（五）小考与期末考
课程中随机问答。期末考试形式为闭卷笔试。
（六）学术诚信
按中山大学南方学院相关规定执行。
（七）剽窃的定义以及相应的惩罚
剽窃是严重违反学校规章制度的行为。一经发现，将上报相关部门，并受到包括开除学籍在内的严厉处罚。
（一）教科书-必读
1. 王瑞胡等主编，离散数学及其应用，清华大学出版社，2014
（二）教科书-强烈推荐
1. 耿素云，屈婉玲编著，《离散数学》北京大学出版社，2002年2. 操作系统真象还原，郑钢，人民邮电出版社，2016
（三）文章-必读
近年《计算机学报》、《软件学报》等国内、国际期刊杂志刊登的文章。
（四）文章-强烈推荐
无
（五）其他参考资料
1. Kenneth.Rosen 著，袁崇义 屈婉玲 等译,《离散数学及其应用》（原书第6版）, 机械工业出版社 2011
（一）教学活动
1、个人预习
2、课堂讲授
3、课堂问答
4、习题讲解
5、案例讨论
6、期中测验
7、期末考试
（二）对预期学习成果的考察
预期学习成果 | 教学活动 | 学习成果考察内容:作业/课程实验 |
第1章 命题逻辑 | 1,2,3,4,5,7 | 课后作业P7(1,2)，P10(1,2,3)，P15(1,8,9)， P21(7)，P29(1,2) |
第2章 谓词逻辑 | 1,2,3,4,5,7 | 课后作业P33(1,3)， P38(1), P42(2)，P44(1)， P47(1) |
第3章 关系 | 1,2,3,4,5,7 | 课后作业P59(1,2)，P66(1,2)， P70(2)， P74(3,4)， P80(1,2)， P89(2)， P94(2) |
第4章 函数 | 1,2,3,4,5,7 | 课后作业P101(1,4)， P103(1,2)，P107(1,2) |
第5章 图论 | 1,2,3,4,5,7 | 课后作业P158(1)，P160(3)， P166(3,4)， P171(1,2)，P175(1)，P179(1) |
第6章 树 | 1,2,3,4,5,7 | 课后作业P188(1,2)， P196(3)， P202(2,3)， |
（一）评分体系
1、出勤率: 10%
2、课堂参与: 15%
3、课后作业: 15%
4、期末考试: 60%
（二）评分标准及要求
课堂参与度 (10%+15%) |
1）全勤 2）课前预习 3）积极回答课堂问题及参与课堂讨论 |
课后作业(15%) |
1）按时按量完成课后作业内容 2）能正确完成课后作业 3）作业格式、书写符合规范 |
期末考试 (60%) |
1）按时参加期末考试 2）正确解答试卷的问题 3）格式书写符合规范 |
周次 | 课程要点 | 理论学时 | 讨论学时 | 习题学时 |
1 | 命题与逻辑联结词,命题公式及公式分类 | 3 | ||
2 | 等值式与等值演算，范式与主范式 | 3 | ||
3 | 推理理论 | 2 | 1 | |
4 | 谓词逻辑基本概念，谓词公式 | 3 | ||
5 | 谓词逻辑蕴含式和等值式，前束范式 | 3 | ||
6 | 谓词逻辑推理理论 | 2 | 1 | |
7 | 笛卡儿积，关系的概念与表示方法，关系的运算， | 3 | ||
8 | 关系的性质，关系的闭包， | 3 | ||
9 | 关系等价与划分，偏序关系 | 2 | 1 | |
10 | 函数的概念，特殊函数，逆函数与复合函数 | 3 | ||
11 | 几个重要的函数，函数的应用 | 2 | 1 | |
12 | 图的定义及相关概念，通路、回路与连通图 | 3 | ||
13 | 图的矩阵表示，欧拉图与哈密顿图 | 2 | 1 | |
14 | 最短路径问题与货郎担问题，平面图和图的着色 | 2 | 1 | |
15 | 无向树及性质，根树 | 3 | ||
16 | 生成树 | 2 | 1 | |
17 | 树的应用 | 2 | 1 | |
18 | 复习、答疑 | 3 | ||
19 | ||||
20 | ||||
总学时 | ||||
