《离散数学》教学大纲

课程名称：	离散数学	离散数学	离散数学
课程编号：	408008	420008	436008
适用专业：	计算机科学与技术	网络工程	软件工程
课程类别：	专业必修课	专业必修课	专业必修课
课程学分：	3	3	3
总学时：	54	54	54
其中：理论学时	54	54	54
实验学时	0	0	0
先修课程：	高等数学、线性代数

一、课程的性质、目的与任务

离散数学是现代数学的一个重要分支。离散数学用数学语言来描述离散系统的状态、关系和变化过程，是计算机科学与技术的形式化描述语言，也是进行数量分析和逻辑推理的工具。离散数学为计算机科学和技术的发展奠定了重要的数学基础，其基本思想、概念和方法广泛渗透到计算机科学和技术的各个领域。

离散数学是计算机科学及相关学科的一门非常重要的专业基础课。教学的目的是进一步提高学生的抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础,并为后续课程的学习打下良好的基础。

通过本课程的学习，要求学生：

1.理解命题逻辑、一阶逻辑、关系、图所包含的基本概念

2.理解研究对象所具有的性质和相互关系

3.掌握各种典型的论证推理方法

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

二、课程基本内容与要求

第一章命题逻辑

（一）教学内容：

1.1命题与联结词

1.2命题公式与赋值

1.3等值演算

1.4析取范式与合取范式

1.5命题逻辑的推理理论

（二）教学要求：

教学目的：了解命题和五种联结词的概念，熟练掌握用五重联结词将复合命题符号化的方法；理解合式公式，成真和成假赋值以及公式的类型等概念，熟练掌握求真值表和判定公式类型的方法；了解等值式的概念，掌握置换定理的简单应用，熟记24个重要等值式并熟练掌握它们的应用；熟练掌握求主析取范式和主合取范式的方法及主范式的应用；了解推理、前提、有效结论、证明的概念，理解推理的形式结熟练掌握；掌握判断推理是否正确的方法，熟练掌握用已知的推理规则构造证明的方法。

教学重点：命题公式与赋值，等值演算，析取与合取范式，命题逻辑的推理理论。

教学难点：主析取与主合取范式的应用，用已知的推理规则构造证明的方法。

第二章 一阶逻辑

（一）教学内容：

2.1一阶逻辑的基本概念

2.2一阶逻辑公式及解释

2.3一阶逻辑等值式与前束范式

2.4一阶逻辑推理理论。

（二）教学要求：

教学目的：了解个体词、谓词、量词的概念。理解指定个体域与全总个体域的概念；掌握命题在全总个体域或指定个体域的符号化形式；了解合式公式、辖域、自由与约束出现、闭式与代换实例等概念，掌握换名规则、代换规则的应用；理解解释的组成及公式类型，掌握在给定解释下判断公式真值的方法；熟练掌握求已知公式的前束范式的方法；熟练掌握在一阶逻辑中构造推理证明的方法。

教学重点：一阶逻辑公式及解释，一阶逻辑等值式与前束范式，一阶逻辑推理理论。

教学难点：一阶逻辑公式解释，一阶逻辑前束范式，一阶逻辑推理理论。

第三章集合的基本概念和运算

（一）教学内容：

3.1集合的基本概念

3.2集合的基本运算

3.3集合恒等式

3.4有穷集合的计数。

（二）教学要求：

教学目的：理解元素与集合的隶属关系、集合之间的包含、相等、不等、真包含关系，掌握集合的表示方法；熟练掌握集合的基本运算；掌握证明简单的集合恒等式或包含关系的方法；掌握有穷集合的计数问题。

教学重点：集合的基本概念和运算，集合元素中的计数问题。

教学难点：幂集、有穷集合的计数。

第4章二元关系和函数

（一）教学内容：

4.1集合的笛卡尔积与二元关系

4.2关系的运算

4.3关系的性质

4.4关系的闭包

4.5等价关系与偏序关系

4.6函数的定义和性质

4.7函数的复合和反函数。

（二）教学要求：

教学目的：了解有序对、二元关系、集合A到B的关系、集合A上的关系的定义，掌握笛卡儿积的运算和性质；熟练掌握关系表达式、关系矩阵、关系图的表示法；掌握关系的定义域只值域、逆、复合、幂的计算方法；理解自反、对称、传递闭包的概念并能求出给定集合上关系的闭包；深刻理解等价关系、等价类、商集、划分、偏序关系、偏序集、哈斯图、偏序集中的特定元素概念，并能熟练求出等价关系的等价类、商集、偏序关系的哈斯图及特定元素；理解函数、集合到的函数、函数的像的概念，、熟练掌握判断函数单射、满射、双射的方法。会构造双射函数。会求复合函数和双射函数的反函数。

教学重点：二元关系的运算，关系的闭包、等价关系与偏序关系，函数的复合和反函数。

教学难点：等价关系与偏序关系

第七章图的基本概念

（一）教学内容：

7.1无向图及有向图

7.2通路、回路和图的连图性

7.3图的矩阵表示。

（二）教学要求：

教学目的：了解无向图与有向图的定义、顶点的度数等概念；理解零图、平凡图、简单图、完全图、正则图、子图、补图、图的同构等概念；熟练掌握握手定理及应用；理解通路与回路、简单通路、简单回路、初级通路、初级回路（圈）、无向图顶点间的连通、有向图顶点间的可达等概念；理解无向连通图、连通分支、点割集、割点、边割集、桥等概念；掌握求短程线与距离的方法。熟练掌握判断通路与回路类型的方法；深刻理解n阶有向图的邻接矩阵和可达矩阵的定义，熟练掌握通过邻接矩阵求顶点间长度为k的通路数、回路数以及图中长度为k的通路和回路数的方法。

教学重点：图的基本概念，通路、回路和图的连通性，图的矩阵表示。

教学难点：图的同构，点连通度、边连通度，邻接矩阵的应用。

第八章树

（一）教学内容：

8.1无向树

8.2根树与应用。

（二）教学要求：

教学目的：了解无向树、分支点、有向树、根树、根子树等概念；掌握求对应于生成树的基本回路和基本割集的方法；熟练掌握利用无向树的性质及握手定理求顶点度数的方法；熟练掌握用闭圈法求最小生成树的方法；熟练掌握用算法求最优树、最佳前缀码的方法。

教学重点：无向树、根树及其应用。

教学难点：求最优树、最佳前缀码的方法。

第九章 二部图、欧拉图、哈密顿图

（一）教学内容：

9.1二部图

9.2欧拉图

9.3哈密顿图

（二）教学要求：

教学目的：理解二部图的判别定理，会用二部图描叙某些实际问题；理解欧拉通路、回路和欧拉图的概念，熟练掌握判定欧拉图的方法；理解哈密顿通路、回路和哈密顿图的概念，会判断某些图是或不是哈密顿图。

教学重点：二部图，二部图中的匹配，欧拉图，哈密顿图。

教学难点：二部图中的匹配，寻找哈密顿通路

三、课程各章节学时分配

四、本课程课外学习与修学指导

由于该课程概念多且较为抽象，内容多且较为零散，所以要学好本课程，要求学生多参阅相关书籍，做好预习，多做练习，掌握离散数学的基本慨念、基本理论和基本方法。

五、本课程成绩的考查方法及评定标准

考核方式：闭卷考试

成绩评定标准：本课程的考核是平时成绩和期终考试成绩相结合，平时成绩的评定包括作业、出勤两部分，平时成绩占课程考核成绩的30%，期末考试成绩占课程考核成绩的70%。

其中期未考试总分100分，基础题占50%，中等难度题占40%，较难题占10%。考试题型主要有：判断题、选择题、填空题、简答题、计算题、证明题、综合应用题等。

六、教材及参考书

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

主要参考书：

[1]《离散数学》，刘爱民著，北京邮电大学出版社.

[2]《离散数学》，邵学才著，清华大学出版社.

[3]《离散数学》，左孝凌著，上海科技出版社出版.

[4]《离散数学》，刘任任主编，中南大学出版社，2005年.

大纲撰写人：杨丽英

大纲审阅人：袁辉勇

教学副主任：易叶青

编写日期：2012年6月15日