《离散数学》教学大纲

课程编号：CE3008

课程名称：离散数学                       英文名称：Discrete Mathematics

学分/学时：3.0/48                         课程性质：必修

适用专业：网络工程、信息安全             建议开设学期：3

先修课程：高等数学、线性代数             开课单位：网络与信息安全学院

一、课程的教学目标与任务

离散数学是研究离散数量关系和离散结构数学模型的数学分支的统称，是网络工程、信息安全等计算机相关专业的专业平台基础课，也是学习专业课程必不可少的数学工具。本课程的数理逻辑是用符号化的方法研究推理的规律，集合论是现代数学的基础，代数结构、图论等知识在计算机相关的学科都有着广泛的应用。

通过本课程的学习，使学生掌握离散数学的基本概念和基本原理，掌握一些基本的能够描述离散对象的结构，了解这些离散结构的特性、离散结构之间的关系，理解离散结构在计算机问题求解中的意义与基本运用；进一步提高抽象思维和逻辑推理的能力，培养学生对简单问题进行合理数学建模的能力，使得学生能够在理论推导上有所提高，并且能够对计算机描述的世界进行基本建模；掌握一些基本的计数技巧，帮助学生掌握命题逻辑和谓词逻辑的概念、基本理论以及应用逻辑的理论建模，为进一步学习后续课程打下必要基础。

二、课程具体内容及基本要求

（一）数理逻辑（16学时）

具体内容提要：

（1）命题逻辑基本概念

• 命题与联接词；

• 命题公式及其赋值。

（2）命题逻辑等值演算

• 等值式；

• 析取范式与合取范式；

• 联接词的完备集。

（3）命题逻辑推理理论

• 推理的形式结构；

• 自然推理系统P。

（4）一阶逻辑基本概念

• 一阶逻辑命题的符号化；

• 一阶逻辑公式及其解释。

（5）一阶逻辑等值演算与推理理论

• 一阶逻辑等值式与置换规则；

• 一阶逻辑的前束范式；

• 一阶逻辑的推理理论。

• 基本要求

（1）对于命题逻辑：了解范式的应用和全功能联结词的应用；熟悉命题与联结词、命题公式及其赋值、命题公式的等值式模式、范式（析取范式和合取范式、主析取范式和主合取范式）、推理的形式结构和自然推理系统；掌握自然语言的形式描述、掌握利用真值表和等值演算的方法进行命题演算和范式表示、掌握用命题逻辑的推理规则进行证明的常用方法。

（2）对于一阶逻辑：了解一阶逻辑的前束范式和推理理论、了解一阶逻辑的应用；熟悉一阶逻辑的基本概念、一阶逻辑的合式公式；掌握一阶逻辑的命题符号化、一阶逻辑公式的解释及分类、掌握利用一阶逻辑的等值式和置换规则方法进行谓词演算。

2.重点、难点

重点：命题的符号化；命题公式的赋值与类型；等值式模式；析取范式与合取范式、极小项与极大项、主析取范式与主合取范式；求主析取(主合取)范式的方法；利用主析取(主合取)范式求公式的成真赋值、成假赋值、判断公式的类型、判断公式是否等值；推理的形式结构与推理规则；在自然推理系统中构造证明的直接证明法、附加前提证明法、归谬法；一阶逻辑命题的符号化；一阶逻辑公式、解释及判定其类型；一阶逻辑中重要的等值式；置换规则、换名规则、代替规则；前束范式；自然推理系统中的推理规则；在自然推理系统中构造推理的证明。

难点：“相容或”与“排斥或”；求主析取(主合取)范式；真值表法、等值演算法、主析取范式法等基本推理方法；直接证明法、附加前提证明法、归谬法等基本证明方法；一阶逻辑公式的解释；一阶逻辑的推理规则与证明。

3.作业及课外学习要求

选择与基本要求相关的典型习题布置为作业，阅读其他经典参考书中相关的内容。

（二）集合论（16学时）

具体内容提要：

（1）集合代数

• 集合的基本概念；

• 集合的运算；

• 有穷集的计数。

（2）二元关系

• 有序对与笛卡尔积；

• 二元关系；

• 关系的运算；

• 关系的性质；

• 关系的闭包；

• 等价关系与划分；

• 偏序关系。

（3）函数

• 函数的定义与性质；

• 函数的复合与反函数；

• 双射函数与集合的基数。

• 基本要求

（1）对于集合：了解集合相等/包含的证明方法和集合的应用；熟悉集合的基本概念、集合的运算；掌握包含排斥定理和集合恒等式。

（2）对于二元关系：了解关系的应用、关系运算的应用、关系性质的应用、关系闭包的应用；熟悉二元关系及其表示方式、关系的基本运算和运算的性质、关系的性质；掌握关系闭包的定义与构造方法、等价关系和偏序关系。

（3）对于函数：了解函数的相关应用；熟悉函数的定义、函数的复合运算和反函数；掌握单射、满射、双射函数的判别方法。

2.重点、难点

重点：集合之间的关系；集合的基本运算；有穷集合的计数方法；集合的相等或者包含关系的证明方法；笛卡儿积的运算和性质；关系的三种表示方法；关系的运算；关系闭包的构造方法；关系的性质；等价关系、等价类、商集、划分的概念以及等价关系与划分的关系；偏序关系、偏序集、哈斯图、偏序集中的特定元素等概念；函数的概念与性质；复合函数、双射函数的反函数。

难点：有穷集的计数方法；关系的闭包运算；等价关系、等价类；偏序关系、偏序集、哈斯图；复合函数、双射函数的反函数。

3.作业及课外学习要求

选择与基本要求相关的典型习题布置为作业，阅读其他经典参考书中相关的内容。

（三）图论（16学时）

具体内容提要：

（1）图的基本概念

• 图；

• 通路与回路；

• 图的连通性；

• 图的矩阵表示；

• 图的运算。

（2）欧拉图与哈密顿图

• 欧拉图；

• 哈密顿图。

（3）树

• 无向树及其性质；

• 生成树；

• 根树及其应用。

（4）平面图与图的着色

• 平面图的基本概念；

• 欧拉公式；

• 平面图的判断；

• 平面图的对偶图。

• 图的着色。

• 基本要求

了解无向图、有向图等的应用；了解平面图的基本概念、欧拉公式及平面图的判断基本定理；了解平面图的对偶图基本转换方法及对图中顶点的着色、地图的着色与平面图的着色及边着色等概念；熟悉与图的定义有关的概念、熟悉无向图的连通性与连通分支等概念、熟悉有向图连通性的概念；掌握握手定理及其推论、掌握图的同构、简单图、完全图、正则图、子图、补图、二部图等概念、掌握通路与回路的定义和表示方法、掌握无向图的点连通度与边连通度等概念、掌握用有向图的邻接矩阵及各次幂求图中通路与回路数的方法、掌握有向图可达矩阵的求解方法；掌握欧拉图与半欧拉图的定义及判别定理、掌握哈密顿图、半哈密顿图的定义及判别方法；掌握无向树的定义及性质、掌握无向树的求解方法、掌握给定带权连通图的最小生成树的求解方法、掌握基本回路、基本割集的概念及求解方法、掌握根树及其分类等概念、掌握阶数较小的所有非同构的根树的画法、掌握求最优树及最佳前缀码的方法、掌握波兰符号法与逆波兰符号法。

2.重点、难点

重点：图的定义；握手定理；同构、简单图、完全图、正则图、子图、补图、二部图等概念及其性质；通路与回路的定义与表示方法；无向图的连通性、连通分支等概念；无向图的点连通度、边连通度等概念及其之间的关系；用有向图的邻接矩阵及各次幂求图中通路与回路数的方法；有向图的关联矩阵、距离矩阵、可达矩阵；欧拉图与半欧拉图的定义及判别定理；哈密顿图及半哈密顿图的定义及判别方法；无向树的定义及性质；画出阶数n较小的所有非同构的无向树；基本回路、基本回路系统、基本割集、基本割集系统的概念；求最小生成树；根树及其分类等概念，阶数较小的所有非同构的根树的画法；Huffman算法并求最佳前缀码。

难点：无向图的连通性，连通分支；无向图的点连通度、边连通度；欧拉图与半欧拉图的判别定理；哈密顿图及半哈密顿图的判别定理；n阶树的所有非同构的无向树；求最小生成树；Huffman算法及求最佳前缀码；欧拉公式的应用及地图的着色。

3.作业及课外学习要求

选择与基本要求相关的典型习题布置为作业，阅读其他经典参考书中相关的内容。

三、教学安排及方式

总学时 48 学时，其中：讲授  40  学时，线上 8  学时。

注：教学方式包括面授和线上，其中面授包括： 讲授、实验、上机、实践。

四、考核及成绩评定方式

最终成绩由平时作业成绩和期末成绩组合而成。各部分所占比例如下：

平时作业成绩：60%。通过作业考核学生对知识点的复习、理解和掌握程度。

期末考试成绩：40%。采用书面考核的形式考察学生对数理逻辑、集合论、代数结构和图论等离散数学基础知识的掌握程度。可采用的题型有：选择题、填空题、判断题、问答题、构造题、计算题和综合题等。

过程成绩提交时间和总评成绩计算说明表

注：上表用于说明授课过程中分项成绩提交时间，教师应在规定的时间内提交对应成绩，提前或逾期无法提交，一旦提交无法修改。大纲可以根据需要自行定义提交成绩的次数、时间和名称或说明，总评成绩计算必须与考核和成绩评定方式中描述的一致。

五、教材及参考书目

教材：《离散数学》（第2版），屈婉玲、耿素云、张立昂编著，高等教育出版社。

参考书目：

1.《离散数学》，左孝凌、李为鉴、刘永才编著，上海科技文献出版社。

2.《离散数学及其应用》（原书第7版），（美）罗森著，徐六通等译，机械工业出版社。

3.《离散数学》（第3版），李盘林、李丽双、陈铭伟、徐喜荣、李洋编著，高等教育出版社。

六、说明

（一）与相关课程的分工衔接

后续课程：操作系统、数据库原理、信息安全数学基础、计算机与网络安全、编译原理等课程。

（二）其他说明

              无。

教材：《离散数学》（第2版），屈婉玲、耿素云、张立昂编著，高等教育出版社。

参考书目：

1.《离散数学》，左孝凌、李为鉴、刘永才编著，上海科技文献出版社。

2.《离散数学及其应用》（原书第7版），（美）罗森著，徐六通等译，机械工业出版社。

3.《离散数学》（第3版），李盘林、李丽双、陈铭伟、徐喜荣、李洋编著，高等教育出版社。