离散数学教学大纲(本科)

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

一、 《离散数学》课程说明

课程英文名称：Discrete mathematics 课程类型：考试课

课程性质：专业技术基础课 总学时： 72学时

适用对象：计算机科学与技术专业本科生 先修课程：高等数学 线性代数

（一）课程简介

离散数学，是现代数学的一个重要分支，是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是有限个或可数个元素。

《离散数学》内容主要包括:集合、映射与运算，关系，命题逻辑，谓词逻辑，代数结构，图论，以及几类特殊的图和组合计数. 通过该课程可以培养学生的抽象思维和慎密的概括能力，是计算机专业的必修课。

（二）课程性质、目的和任务

《离散数学》课程是为计算机科学与技术专业的学生开设的一门专业基础课程。随着计算机科学的发展和计算机应用领域的日益广泛，迫切需要适当的数学工具来解决计算机科学各个领域中提出的有关离散量的理论问题，离散数学就是适应这种需要而建立的，它综合了计算机科学中所用到的研究离散量的各个数学课题，并进行系统、全面的论述，从而为研究计算机科学及相关学科提供了有利的理论基础和工具。是学习后续专业课程不可缺少的数学工具，如：高级语言、数据结构、编译原理、操作系统、可计算性理论、人工智能、形式语言与自动机、信息管理与检索以及开关理论等，离散数学也是研究自动控制、管理科学、电子工程等的重要工具。

教学的目的是进一步提高学生的抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。并为后续课程的学习打下良好的基础。

（三）与其他课程的联系

除要求学生具有矩阵和矩阵运算方面的一些知识外，离散数学基本上是一门体系独立自行封闭的基础数学课程，但由于它内容抽象，理论性较强，因此它需要学生先期有较好的数学思维的训练。最好将此课程安排在高等数学和线性代数课程之后。

本课程为“数据结构”、“数据库原理”、“操作系统”、“编译原理”、“人工智能”等许多其它专业基础课奠定必要的数学基础。

（五）对先修课的要求

《线性代数》：为本课程提供矩阵和矩阵运算方面的准备； 《高等数学》：为本课程提供必要的数学知识。

（六）学时数、学分数及学时具体分配

学时数：72学时 学时数具体分配:

（七）教学方式：使用多媒体教室以教师讲解为主的课堂教学方式 (八）考核方式和成绩记载说明

考核方式为考试。严格考核学生出勤情况，达到学记管理的旷课量取消考试资格。综合成绩根据平时成绩和期末成绩评定，平时成绩占30％，期末成绩占70％。

二、 大纲内容 第1章

集合、映射与运算

1、教学目标：

1、正确理解并熟记集合，集合的基数，子集，幂集等概念； 2、 能理解映射的有关概念、性质，掌握逆映射和复合映射的计算； 3、掌握运算的定义及其性质；

4、熟练掌握集合的求并、交、补，差集及对称差的运算； 5、了解集合的划分和覆盖概念；

6、了解集合对等的定义，掌握集合基数的概念。 2、教学内容（考核要求）： 1.1 集合的有关概念 1.1.1 集合 1.1.2 子集 1.1.3 幂集 1.1.4 n元组 1.1.5 笛卡儿积 1.2 映射的有关概念 1.2.1 映射的定义 1.2.2 映射的性质 1.2.3 逆映射 1.2.4 复合映射 1.3 运算的定义及性质 1.3.1 运算的定义 1.3.2 运算的性质 1.4 集合的运算 1.4.1 并运算 1.4.2 交运算 1.4.3 补运算 1.4.4 差运算 1.4.5 对称差运算 1.5 集合的划分与覆盖 1.5.1 集合的划分 1.5.2 集合的覆盖 1.6 集合的对等

1.6.1 集合对等的定义 1.6.2 无限集合 1.6.3 集合的基数 1.6.4 可数集合 1.6.5 不可数集合 1.6.6 基数的比较

第2章 关系

1、教学目标： 1、基本概念要清楚；

(1) 熟练掌握关系的三种表示法；

(2) 能够判定关系的性质（等价关系或偏序关系）； (3) 掌握含有关系运算的集合等式；

(4) 掌握等价关系、等价类、商集、划分、哈斯图、偏序集等概念；

2. 以下基本运算要熟练:

(1) A ⨯B, dom R, ranR, fldR, R-1, R︒S , Rn , r(R), s(R), t(R)； (2) 求等价类和商集A/R；

(3) 给定A 的划分π，求出π所对应的等价关系；

2) 求偏序集中的极大元、极小元、最大元、最小元、上界、下界、上确界、下确

界。

3. 掌握基本的证明方法：

证明涉及关系运算的集合等式、证明关系的性质、证明关系是等价关系或偏序关系。

4. 给定f, A, B, 判别f 是否为从A 到B 的函数； 5. 判别函数f ：A →B 的性质（单射、满射、双射）； 6. 熟练计算函数的值、像、复合以及反函数； 7. 证明函数f ：A →B 的性质（单射、满射、双射）； 8. 给定集合A, B，构造双射函数f ：A →B 。

2、教学内容（考核要求）： 2.1 关系的概念

2.1.1 n 元关系的定义 2.1.2 2元关系

2.1.3 关系的定义域和值域 2.1.4 关系的表示 2.1.5 函数的关系定义 2.2 关系的运算 2.2.1 关系的集合运算

2.2.3 关系的复合运算 2.2.4 关系的其他运算 2.3 关系的性质 2.3.1 自反性 2.3.2 反自反性 2.3.3 对称性 2.3.4 反对称性 2.3.5 传递性 2.4 关系的闭包 2.4.1 自反闭包 2.4.2对称闭包 2.4.3 传递闭包 2.5 等价关系

2.5.1 等价关系的定义 2.5.2 等价类 2.6 相容关系 2.6.1 相容关系的定义 2.6.2 相容类 2.7 偏序关系

2.7.1 偏序关系的定义 2.7.2 偏序集的哈斯图 2.7.3 偏序集中的特殊元素

第3章 命题逻辑

1、教学目标：

1、理解命题和逻辑联结词的基本概念； 2、掌握公式分类和真值表构造。 3、理解命题等值关系式；

4、掌握公式的析取范式和合取范式； 5、了解联结词的完备集。

7、理解推理的形式结构和自然推理系统P 2、教学内容（考核要求）： 3.1 命题的有关概念 3.2 逻辑联结词 3.2.1 否定联结词 3.2.2 合取联结词 3.2.3 析取联结词 3.2.4 异或联结词 3.2.5 条件联结词 3.2.6 双条件联结词 3.2.7 与非联结词 3.2.8 或非联结词 3.2.9 条件否定联结词 3.3 命题公式及其真值表 3.3.1 命题公式的定义 3.3.2 命题的符号化 3.3.3 命题公式的真值表 3.3.4 命题公式的类型 3.4 逻辑等值的命题公式 3.4.1 逻辑等值的定义 3.4.2 基本等值式 3.4.3 等值演算法 3.4.4 对偶原理 3.5 命题公式的范式

3.5.1 命题公式的析取范式及合取范式 3.5.2 命题公式的主析取范式及主合取范式 3.6 联结词集合的功能完备性 3.6.1 联结词的个数 3.6.2 功能完备联结词集

3.7 命题逻辑中的推理 3.7.1 推理形式有效性的定义 3.7.2 基本推理规则

3.7.3 命题逻辑的自然推理系统

第4章 谓词逻辑

1、教学目标：

1、掌握谓词、全称量词、存在量词等概念学会使用它们符号化一些命题，并能够构成一些较复杂的命题。

2、掌握谓词公式的概念，并能够判定给定公式是否为谓词的合适公式 3、掌握约束变量、自由变量的概念，并能够正确的使用换名规则 4、掌握永真公式、永假公式可满足公式等概念。

5、掌握谓词公式的等价蕴含等概念，熟记基本的等价式、蕴含式会证明更复杂的等价式蕴含式。

6、掌握前束范式的概念，并能够将一谓词公式化成与之等价的前束范式；

7、掌握谓词演算的推理理论，并能够正确使用推理规则进行有效推理并能够判断一推理过程是否正确。

2、教学内容（考核要求）： 4.1 个体、谓词、量词和函词 4.1.1 个体 4.1.2 谓词 4.1.3 量词 4.1.4 函词

4.2 谓词公式及命题的符号化 4.2.1 谓词公式 4.2.2 命题的符号化 4.3 谓词公式的解释及类型 4.3.1 谓词公式的解释 4.3.2 谓词公式的类型 4.4 逻辑等值的谓词公式

4.4.2 基本等值式 4.5 谓词公式的前束范式

4.5.1 谓词公式的前束范式的定义 4.5.2 谓词公式的前束范式的计算 4.6 谓词逻辑中的推理 4.6.1 逻辑蕴涵式 4.6.2 基本推理规则

4.6.3 谓词逻辑的自然推理系统

第5章 代数结构

1、教学目标：

1、判断给定集合和运算能否构成代数系统 2、判断给定二元运算的性质和特异元素 3、了解同类型和同种代数系统的概念 4、了解子代数的基本概念。

5、深刻理解和掌握代数系统的基本概念和运算

掌握半群和独异点的概念及性质；群的定义及性质；了解子群的概念，子群判定定理；陪集的概念，拉格朗日定理；正规子群的概念，正规子群的性质及判定；掌握群的同态概念；循环群的概念，循环群的性质，应用相关定理；置换群的概念，置换群的性质。环的概念及性质；域的概念及性质

2、教学内容（考核要求）： 5.1 代数结构简介 5.1.1 代数结构的定义

5.1.2 两种最简单的代数结构: 半群及独异点 5.1.3 子代数

5.1.4 代数结构的同态与同构 5.2 群的定义及性质 5.2.1 群的有关概念 5.2.2 子群 5.2.3 群的同态

5.3.1 环的定义 5.3.2 几种特殊的环 5.3.3 域的定义 5.3.4 有限域 5.4 格与布尔代数 5.4.1 格的定义和性质 5.4.2 分配格 5.4.3 有补格 5.4.4 布尔代数

第6章 图论

1、教学目标：

1、深刻理解握手定理及推论的内容并能灵活地应用它们；

2、深刻理解图同构、简单图、完全图、正则图、子图、补图、二部图的概念以及它们的性质及相互之间的关系；

3、记住通路与回路的定义、分类及表示法；

4、深刻理解与无向图连通性、连通度有关的诸多概念； 5、会判别有向图连通性的类型；

6、熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方法，会求可达矩阵。 2、教学内容（考核要求）： 6.1 图的基本概念 6.1.1 图的定义； 6.1.2 邻接 6.1.3 关联 6.1.4 简单图 6.2 节点的度数

6.3 子图、图的运算和图同构 6.3.1 子图 6.3.2 图的运算 6.3.3 图同构

6.4.1 路 6.4.2 回路 6.5 图的连通性 6.5.1 无向图的连通性

6.5.2 无向连通图的点连通度与边连通度 6.5.3 有向图的连通性 6.6 图的矩阵表示 6.6.1 图的邻接矩阵 6.6.2 图的可达矩阵 6.6.3 图的关联矩阵 6.7 赋权图及最短路径 6.7.1 赋权图 6.7.2 最短路径

第7章 几类特殊的图

1、教学目标：

1、了解二分图与完全二分图掌握二分图中的匹配 2、理解欧拉图、半欧拉图的定义及判别定理； 3、刻理解哈密顿图、半哈密顿图的定义；

4、 哈密顿图的必要条件判断某些图不是哈密顿图. 会用充分条件判断某些图是哈密顿图. 要特别注意的是，不能将必要条件当作充分条件，也不要将充分条件当必要条件。

5、深刻理解无向树的定义及性质； 6、熟练地求解无向树；

7、准确地求出给定带权连通图的最小生成树；

8、深刻理解基本回路、基本割集的概念，并对给定的生成树会求出它们； 9、理解根树及其分类等概念；

10、会画n 阶（n 较小）非同构的无向树及根树（1≤n ≤6）； 11、熟练掌握求最优树及最佳前缀码的方法。 2、教学内容（考核要求）： 7.1 欧拉图

7.1.2 欧拉定理

7.1.3 中国邮递员问题

7.2 哈密尔顿图

7.2.1 哈密尔顿图的有关概念

7.2.2 哈密尔顿图的必要条件

7.2.3 哈密尔顿图的充分条件

7.2.4 旅行商问题

7.3 无向树

7.3.1 无向树的定义

7.3.2 无向树的性质

7.3.3 生成树

7.3.4 最小生成树

7.4 有向树

7.4.1 有向树的定义

7.4.2 根树

7.4.3 m叉树

7.4.4 有序树

7.4.5 定位二叉树

7.5 平面图

7.5.1 平面图的有关概念

7.5.2 欧拉公式

7.5.3 库拉托夫斯基定理

7.5.4 平面图的对偶图

7.6 平面图的面着色

7.6.1 平面图的面着色定义

7.6.2 图的节点着色

7.6.3 任意图的边着色

7.7 二部图及其匹配

7.7.1 二部图

7.7.2 匹配

第8章 组合计数

1、教学目标：

2、教学内容（考核要求）：

8.1 排列组合与二项式定理

8.1.1 排列

8.1.2 组合

8.1.3 二项式定理

8.2 生成函数

8.2.1 组合计数生成函数

8.2.2 排列计数生成函数

8.3 递归关系

8.3.1 递归关系的概念

8.3.2 常用的递归关系求解方法