《离散数学》教学大纲

1、离散数学教学大纲课程编码531002-3教学单位计算机科学与技术学院课程名称离散数学-英文名称Discrete Mathematics课程学时128课程学分 8课程类别学科基础课课程性质必修课开课学期第2，3学期适用专业、方向计算机科学与技术、网络与信息安全方向、物联网工程、卓越工程师培养计划选用教材欧阳丹彤等，离散数学结构，高等教育出版社，2011主要参考书1.屈婉玲，耿素云，张立昂，离散数学，高等教育出版社，20082.傅彦，顾小丰，王庆，刘启和，离散数学及其应用，高等教育出版社，2007制定人欧阳丹彤制定时间2013.6.20教学目的离散数学是计算机科学与技术整个一级学科的重要专业基础课

2、，其主要目的在于向学生讲授集合论基础、经典数理逻辑、图论与网络、格与布尔代数、近世代数等离散数学内容。为学生进一步学习数据结构、编译原理、电路设计等专业课打好数学基础。离散数学在教给学生离散问题建模、数学理论、计算机求解方法和技术知识的同时,培养学生的数学抽象能力与严密的逻辑推理能力。离散数学既是一门基础理论课程，又是一门与实际问题紧密相连的课程。通过本课程学习，将增强学生使用离散数学知识分析问题与解决实际问题的能力。教学要求掌握集合论、数理逻辑、图论、整数、群、环、域、格、布尔代数等离散数学的基本概念和基本原理，为学习计算机专业各后续课程做好必要的知识准备。并通过这些知识的学习进一步提高学生

3、的抽象思维和逻辑推理能力，为从事计算机相关的理论研究与应用提供必要的描述工具和理论基础。预备知识或先修课程要求高等数学、线性代数教学方式 多媒体教学，课堂讲解，结合练习或课堂讨论。教学内容及学时分配集合论基础 （理论教学20学时）知识点：集合的概念，集合相等和包含关系的定义和性质，常用的集合表示方法，集合的基本运算，关系的相关概念以及关系的性质，关系的乘积，关系的闭包运算，等价关系相关的基本概念，等价关系和划分的内在联系，部分序关系、部分序集、全序关系、全序集的概念以及部分序集中的特殊元素：最大元、最小元、极大元、极小元、上确界、小确界的定义，有限部分序集的Hasse图，映射、映像、1-1映射

4、等概念，映射的乘积，可数集合的概念及可数集合的判定方法。1.1 集合的基本概念 （6学时） 1.2 关系 （9学时） 1.2.1 关系的基本概念及其性质 1.2.2 等价关系 1.2.3 偏序关系1.3 映射 （5学时）1.3.1 集合的基数 1.3.2 可数集合 1.3.3 不可数集合第二章 计数 （理论教学6学时）知识点：加法原理和乘法原理，集合排列数和组合数，多重集合的排列数和组合数，二项式定理及推广，容斥原理及应用，鸽巢原理的简单形式和加强形式及其应用。2.1 两个基本计数原理（0.5学时） 2.1.1 加法原理 2.1.2 乘法原理2.2 排列与组合 （0.5学时） 2.2.1 集合

5、的排列数和组合数 2.2.2 多重集的排列数和组合数2.3 二项式定理 （1学时） 2.3.1 二项式定理 2.3.2 二项式定理的推广2.4 容斥原理 （2学时）2.4.1 容斥原理2.4.2 容斥原理的应用2.5 鸽巢原理 （2学时） 2.5.1 简单的鸽巢原理2.5.2 加强的鸽巢原理第三章 古典数理逻辑 （理论教学15学时）知识点：命题、逻辑联结词等概念，命题的符号化，命题公式、解释、恒真公式、恒假公式等概念，命题公式是恒真、恒假、可满足的判断，公式的等价、蕴涵等概念，基本的等价式、蕴涵式，复杂的等价式、蕴涵式的证明，联结词的功能完备集（全功能集）的概念，一个联结词集合是否为联结词的功

6、能完备集的判别，演绎方法及应用，析取范式、合取范式、极大项、极小项、主析取范式、主合取范式的概念和性质，求各种范式的方法，一个命题公式的主合取范式与主析取范式的关系，谓词、全称量词、存在量词等概念及在命题符号化的应用，约束变量、自由变量的概念，改名规则，谓词公式、解释的概念，能够求出一给定公式在某一解释下的真值，恒真公式、恒假公式、可满足公式等概念，谓词逻辑判定问题，谓词公式的等价、蕴涵等概念，基本的等价式、蕴涵式，复杂的等价式、蕴涵式的判别，谓词演算的推理理论，使用推理规则进行有效推理及推理过程是否正确的判断，前束范式、Skolem范式等概念，与谓词公式等价的前束范式的转化，及进一步到Sko

7、lem范式的转化。3.1 命题逻辑（10学时） 3.1.1命题和公式 3.1.2 命题公式的等价关系和蕴含关系 3.1.3 范式 3.2 谓词逻辑（5学时） 3.2.1 谓词逻辑的基本概念3.2.2 谓词公式3.2.3 谓词公式的等价关系和蕴含关系3.2.4 范式第四章 图与网络 （理论教学15学时）知识点：图、有限图、母图、子图、支撑子图、完全图、补图等概念，有限图中点的度及性质，图的矩阵表示，路、简单路、回路、连通图等概念，Dijkstra算法及应用，支撑树的概念以及图是树的几个等价命题，Kruskal算法及应用，求最优树的Prim算法和Sollin算法，有向图、有向子图、有向路、简单有向

8、路、有向回路等概念，有向图的强连通性和有向图的根的概念及二者的关系，有向树的概念以及有向树与树的转化定理，Euler路、Euler图的概念，有向图中和无向图中Euler图的充要条件，Euler图的判定，从Euler路得出有向支撑树以及从有向支撑树得出Euler路的方法，Hamilton路、Hamilton回路、Hamilton图的概念以及Hamilton图的必要条件和若干充分条件。4.1图（5学时） 4.1.1 图的基本概念 4.1.2 全图Dijkstra算法4.2树 （2学时） 4.2.1 树及其等价命题 4.2.2 最优树Kruskal算法 4.2.3 求最优树的其他算法4.3有向图 欧

9、拉路（5学时） 4.3.1 有向图与有向树 4.3.2 欧拉路 欧拉图4.4哈密顿图（3学时） 4.4.1哈密顿路 哈密顿图的必要条件4.4.2哈密顿图的若干充分条件第五章 数论基础 （理论教学8学时）知识点：整除、因数、倍数等概念，整除性质的应用，最高公因数的概念，辗转相除法及应用，利用数的数码特征判别某些整除性，互质的概念和质数的性质，质数、合数的概念以及算术基本定理、欧几里得定理，合同的概念以及合同的基本性质，剩余系、剩余类的概念，一次合同方程在有解、无解、有唯一解（一个剩余类）和有多解（多个剩余类）的条件，及有解情况的求解方法，秦九韶定理(及其推广)、合同方程组的一般解法。5.1 整除

10、性 辗转相除（2学时）5.1.1 整除及其性质 5.1.2 辗转相除5.2 互质 质因数分解（1学时） 5.2.1 整数互质 5.2.2 质数与合数 算术基本定理5.3 合同 一次同余式（2学时） 5.3.1 合同及其性质 5.3.2 剩余类 一次同余式5.4 秦九昭定理 欧拉函数（3学时） 5.4.1 一次同余式组 秦九昭定理 5.4.2 一元高次同余式的化简 5.4.3 剩余系遍历欧拉函数第六章 群、环、域（理论教学50学时）知识点：二元代数运算、代数系统的定义，运算是否为二元代数运算的判断，运算是否满足交换律、结合律、分配律、幂等律、吸收律、消去律的判断，半群、群的定义以及群的性质，代数

11、系统是否为半群或群的判断，交换群的定义以及交换群中的三个指数律，置换、轮换、不相杂轮换、对换等概念，置换的乘法，任意置换写成不相杂轮换的乘积，奇置换、偶置换的概念，n次对称群、n次交代群的概念，子群的定义以及子群的判别条件，周期、循环群的定义和乘法群、加法群中周期的性质以及循环群中一元素作为生成元的充要条件，群中合同、右陪集的定义，子群在大群中的右陪集的一些性质，正规子群的概念以及一子群为大群的正规子群的充要条件，Lagrange定理，同态映射、同构映射、自同构映射的概念以及同态定理，同态映射、同构映射或自同构映射的判断，同态核，同态与同构的基本定理，环、交换环、含壹环、消去环的定义及其性质，

12、整区、体、域、子环、子体、子域等概念，以及环的子集作成子环的充要条件，理想、主理想的定义，环中合同关系、剩余类的定义以及环中合同关系的性质，环同态映射、同构映射、剩余环的定义，环中的关于同态映射、同构映射的一些定理，单纯环与极大理想的定义，以及二者的关系，一个环是域的充要条件，群与环在计算机科学中的应用，多项式整除的概念及其性质。公因式、最高公因、真因式、互质、质式等定义及相关定理，多项式恒等、多项式的根、k重根、重根等概念，余式定理及其推论，多项式有重根的充要条件，实数域上、复数域上、有理域上的质式问题，本原多项式的概念、Eisenstein定则以及求有理数多项式的有理根问题，有理根的计算，

13、某多项式在有理域上不可约的证明，代数数、超越数的概念，有理域上和任意域上分圆多项式的定义，分圆多项式的计算，有限域的元数和其子域的元数的关系，有限域的构造。6.1 代数系统（3学时）6.2 群的定义（6学时）6.2.1 半群6.2.2 群6.2.3 群的性质6.2.4 置换群6.3 子群及其陪集（9学时）6.3.1 子群的定义6.3.2 子群的判别条件6.3.3 循环群6.3.4 陪集6.4 群的同态及同构（6学时）6.4.1 同态映射6.4.2 同构映射6.4.3 同态核6.5 环（9学时）6.5.1 环的定义及性质6.5.2 环同态6.6 域的特征 素域（3学时）6.6.1 域的特征6.6

14、.2 素域6.7 多项式（8学时）6.7.1 多项式的整除性6.7.2 多项式的根6.7.3 有理域上的多项式6.7.4 分圆多项式6.8 有限域（6学时）第七章 格与布尔代数（理论教学14学时）知识点： 半序格、半序子格、代数格、代数子格的定义，半序格和代数格的定义的等价关系，互相对偶的两个关系、互相对偶的两个格的定义及二者关系，格中表达式、对偶格中的对偶表达式、本格中的对偶表达式的定义，对偶原理，格的其它性质，如格的保序性、分配不等式、模不等式等，格同态映射、格的自同态映射、格同构映射的定义及应用，格的同态映射一定是保序映射，同构映射的逆映射也是同构映射等结论，有界格、有余格、分配格以及模

15、格的定义及相关结论，一个格为模格的充要条件，布尔代数的定义及其16个性质，Huntington公理及其应用，电路代数、集合代数、命题代数、开关代数，布尔代数的子集是其子代数的充要条件，可唯一表示布尔代数中元素的基底的定义及其性质，极小元的定义及其性质，布尔代数的生成、极小项、多项式、多项范式、布尔代数中一组元素互相独立等概念，布尔代数中元素与多项范式的关系和极小项、基底、极小元间的关系，布尔代数中同态、同构的概念及其相应结论，布尔代数的同构，Stone定理，布尔表达式的化简。 7.1 引言（0.5学时）7.2 格的定义（0.5学时）7.3 格的性质（4学时）7.3.1 对偶原理7.3.2 格的其它性质7.3.3 格的同态与同构7.4 几种特殊的格（3学时）7.4.1