《离散数学》课程教学大纲

序号

教学内容

教学重点

教学难点

1

数理逻辑

命题符号化；公式的递归定义；谓词公式的解释；命题逻辑公式演算与推理证明；一阶逻辑公式演算与推理证明性。

命题逻辑与谓语逻辑的演绎推理。

2

集合论

二元关系的性质:自反、反自反、对称、反对称、传递、反传递；判断法:序偶，关系图，关系矩阵；关系的运算:复合关系，逆关系，混合运算，关系的闭包；其他特殊关系:等价关系，偏序关系；函数的生成与复合运算。

关系闭包；等价关系与偏序关系。

3

图论

图的表示；子图、生成子图与补图；握手定理；图的同构；图的连通性；生成树与最小生成树；根树遍历算法；最优树与哈夫曼树；欧拉图与哈密尔顿图；带权图与最短路径算法。

欧拉图与哈密尔顿图的判定方法；带权图的最短路径算法；根树的递归遍历算法。

4

代数系统

代数系统的定义及分类；代数系统的同态、同构关系；半群与幺半群的定义与性质；群的定义与性质；循环群的生成元及子群；群同态与同构；格的定义及性质；几种特殊的格（分配格、有补格、布尔格）；环和域的定义。

群的性质及其应用；格及其性质。

知识块

一级知识点

二级知识点

掌握程度

评价标准

备注

数理逻辑

命题逻辑

命题、联结词与命题符号化:命题的概念，联结词,命题符号化；

掌握

1.掌握命题和公式的定义，公式的分类；

2.要求能够对语句进行形式化，并对公式熟练进行演算；

3.至少学会运用两种办法求公式的主析取（合取）范式形式。

讲授、练习

命题公式:变元与常元，公式递归定义，指派与真值表；

熟练掌握

重言式:重言式，矛盾式，可满足式；逻辑等价式，代入原理，替换原理，有效推理，对偶式及对偶原理；

熟练掌握

范式:析取范式，合取范式，极大（极小）项，主析取范式，主合取范式；

熟练掌握

联结词归约:联结词扩充，完备联结词。

掌握

谓词逻辑

谓词与量词:个体变元（常元），个体域，谓词的定义与元数，全称量词，存在量词，量词的辖域，约束变元与自由变元；

熟练掌握

1.掌握谓词的定义及谓词公式的定义；

2.能熟练运用演算的方法求公式的前束范式；

3.能熟练对命题符号化基本技能并能够进行有效推理。

讲授、练习

作业1

谓词公式:递归定义，特性谓词，命题符号化基本技能；

熟练掌握

谓词公式的真值:解释，逻辑等值式，有效推理；

掌握

几个基本原理:代入原理，替换原理，对偶式及对偶原理，改名原理。

了解

集合论

集合论基础

基本概念:集体的概念，集合表示，集合的包含与相等；

掌握

1． 掌握集合的基本运算及性质；

2．要求熟练运用幂集计算方法进行问题求解。

讲授、练习

集合运算:集合的交、并、补、差、对称差、广义交、广义并，集合运算的性质；

熟练掌握

幂集:幂集的定义与计算，幂集运算的性质。

掌握

关系及其性质

二元关系的概念:序偶与笛卡儿积，二元关系的定义，二元关系的表示；

掌握

1． 掌握二元关系的概念及其性质，以及关系与集合的关系；

2． 要求灵活运用二元关系的五种性质；

3．要求熟练掌握等价关系与偏序关系的判别条件和表示方法，清楚地理解偏序关系的特殊元之间的联系以及哈斯图的应用。

二元关系的性质:自反、反自反、对称、反对称、传递、反传递；判断法:序偶，关系图，关系矩阵；

熟练掌握

关系的运算:复合关系，逆关系，混合运算，关系的闭包；

熟练掌握

其他特殊关系:等价关系，偏序关系。

掌握

函数与集合基数

函数的基本概念:函数定义，单射、满射、双射；

掌握

1． 理解函数的概念以及函数与关系的区别与联系；

2．要求熟练掌握函数的复合运算与逆函数运算。

函数运算:复合函数、逆函数；

掌握

图论

图的基本概念

图的定义与表示:结点，边（有向边和无向边），端点，孤立点，环，邻接，关联，零图，平凡图，（n,m）图，图的集合（图形、矩阵）表示法；

掌握

1．掌握图的基本概念与图的分类；

2．熟练运用握手定理及其推论进行分析图的性质；

3．掌握把实际问题转化成为图的形式并运用图的性质进行分析。

讲授、练习

图的分类:无向图与有向图，简单图与多重图，无权图与有权图；

掌握

子图与补图:子图和真子图，生成子图，导出子图，完全图，补图；

掌握

结点度数与握手定理:结点的度数（有向图与无向图），握手定理及其推论，度数序列；

熟练掌握

图的同构:图同构的定义与判断。

掌握

图的连通性

通路与回路:通路与回路的定义，通路长度，简单通路与简单回路，基本通路与基本回路，距离，通路和回路的基本性质，可达和可达矩阵，可达性的判断；

掌握

1．掌握有向图和无向图中的连通性的基本概念；

2．学会运用图的矩阵表示，分析图的性质，如求两点间路径数目等。

无向连通与连通分支，有向连通图（强连通、单向连通、弱连通）。

掌握

特殊的图

欧拉图:欧拉通路、欧拉回路，欧拉图的判定定理及其推论，桥与割边 ；

熟练掌握

1．掌握欧拉图、哈密顿图、偶图、平面图的基本概念及其判断定理；

2．学会运用图模型表示和解决实际问题，如中国邮路问题、资源分配问题、排课表问题等。

哈密顿图:哈密顿通路，哈密顿回路，哈密顿图及判定定理；

熟练掌握

偶图:偶图定义，完全偶图，偶图的判定定理，匹配、匹配的判断定理:霍尔定理和t条件；

了解

平面图:平面图与非平面图，面、边界、次数，欧拉公式及其应用，平面图的判定定理，对偶图。

了解

树

树的定义与性质:树，叶子，分支点，内部结点，森林，平凡树；

掌握

1．掌握树的定义和性质，生成树的定义，根树的定义与应用；

2．熟练掌握向种算法:最小生成树算法，树的遍历算法，哈夫曼算法。

讲授、练习

生成树:生成树、树枝和弦、生成树的补、生成树的求法（避圈法、破圈法）、最小生成树及其算法（Kruskal算法和 Prim算法）。

掌握

根树:根树的定义，根树的分类，根树遍历算法，根树转化为二元树，森林转化为二元树，最优树与哈夫曼算法。

熟练掌握