安徽师范大学《离散数学》大纲本科教学大纲

《离散数学》课程大纲
课程名：离散数学 课程英文名：Discrete Mathematics
课程性质：必修 专业：计算机专业（师范类）、计算机专业（软件班）
学时：68 学分：4 预修要求：高等数学、线性代数
一、课程简介
离散数学是计算机学科的重要基础理论课，课程结合计算机学科的特点研究离散对象
及相互关系，它是计算机各专业课程的基础，对提高学生的抽象思维与逻辑推理能力
有重要作用。
二、课程的目的与任务
掌握集合论、代数系统、图论和数理逻辑基本内容，为今后学习计算机专业课程打下
必要的理论基础。
三、与其它相关课程的联系
先修课程有：高等数学、线性代数
后读课程有：数据结构、数据库、操作系统、计算机网络等
四、教学内容（见课程目录）
五、课程基本要求
本课程由四部分组成：集合论、代数系统、图论、数理逻辑。各部分的要求具体如下
（注：标明了应重点掌握的概念或内容）
（一）集合论
1、集合与集合的运算；集合的幂集；集合的两种表示法
2、序偶与笛卡儿乘积关系
3、二元关系的关系阵与关系图及其求法
4、关系的自反性、对称性、非对称性和传递性（概念与判定）
5、复合关系与逆关系（概念与求法）
6、关系的闭色运算（概念与求法）
7、次序关系（概念：偏序集与哈斯图，拟序集，最大（小）元，极大（小）元，上
（下）界，上（下）确界
8、相容关系
9、等价关系（判定与证明、等价类的求法）
10、映射、满射，单射、双射（概念与判定）复合映射与逆映射（概念与求法）
11、无限集与有限集（特征定义）
12、可列集（概念与制定方法）
13、集合间的等式关系与集合的基数
（二）代数系统
1、代数系统的基本概念：结合律、交换律、分配律、单位元、逆元、零元，代数系统
间的同构与同态。
2、群（定义证明与判定，性质）
3、置换和轮换（概念和运算性质）置换群
4、循环群：概念，生成元的求法，元素周期的求法
5、子群（概念与判定） 正规小群（概念）
6、拉格朗日定理及其应用 ； 陪集与陪集关系（概念，陪集的构造）
7、同余关系与商群（概念）群同态（概念）
8、环与域（定义）
9、格与布尔代数（定义，格的制定）
（三）图论
1、图的概念（图的同构；图的邻接阵的求法；结点的次数）
2、通路，回路与连通性（概念由邻接阵及邻接阵的幂求通路或回路的条数；有向图
三种连通性的概念及判定方法）；迪克斯特拉算法求有权图的最短路
3、欧拉图（概念，欧拉回路与欧拉通路的判定）；哈密尔顿图（概念）
4、树（几个等价定义）；外向树（概念）；二元树（用二元树表示算术表达式与表示
表格结构二元树的遍历问题；外向树转化成二元树）有权图的最短生成树（克鲁
斯卡尔（kruscal 算法与 prim 算法）
5、平面图 （概念，欧拉公式，库拉托夫斯基定理）
6、二步图（概念、判定、基数匹配的匈牙利算法）
（四）数理逻辑（命题演算部分）
1、命题，命题联接词（真值表）求命题公式的真值表
2、命题公式的恒真性，恒假性与可满足性
3、重言等价式与重言蕴含式（掌握其中重要的几个）
4、用化归的方法求公式的析取范式，合取范式，求公式的特异合取，析取范式
5、用真值表法求公式的特异析取范式，特异合取范式最大（小）项
6、命题联结词的扩充和归纳
7、命题演算的假设推理方法
（五）数理逻辑（谓词演算部分）
1、谓词、量词（概念）
2、日常语言与谓词公式的互译
3、公式在给定解释求真值的过程
4、求公式的前束范式与斯特林范式
5、谓词演算的假设推理方法
（六）课时说明
集合论部分（14 学时）
代数系统部分（18 学时）
图论部分（16 学时）
数理逻辑部分（16 学时）
综合习题课（4 学时）
合计 68 时