《离散数学》教学大纲
（2013版）
课程编码：0611100603
课程名称：离散数学
学时/学分：48/3
先修课程：《计算机导论》
适用专业：计算机科学与技术
开课教研室：网络工程教研室
执笔：
审定：
一、课程性质与任务
1．课程性质：本课程属于计算机科学与技术专业的专业基础课，是所有计算机科学与技术专业学生的必修课。
2．课程任务：本课程的教学目标是使学生正确理解离散数学的概念、定理、公式的客观实际意义，掌握离散对象的基本研究方法，掌握离散数学理论、方法在计算机科学技术中的应用，培养学生利用离散数学思想分析问题与解决实际问题的能力。结合离散数学在计算机科学技术中的应用，介绍离散数学的基本知识，帮助学生了解数学中的抽象思维与计算机科学实践之间的内在联系，使学生熟练掌握离散数学的基本概念、结论、算法、推理与证明方法，培养学生的抽象思维、逻辑推理、符号演算和概括的能力，能够用离散数学中的数学方法解决本专业的实际问题。
二、课程教学基本要求
离散数学是现代数学的一个分支，是研究离散量的结构及相互关系的学科，在计算机科学与技术中有着广泛的应用。教学内容以基本概念、结论、算法、推理与证明方法，以及一般应用方法的介绍为主，主要内容包括数理逻辑、集合论、代数结构与图论等四个方面的内容。通过本课程的学习，要求学生了解离散数学的主要组成部分及各部分所涉及的基本内容，及其在计算机科学与技术领域中的应用； 理解离散数学的基本概念、结论、算法、应用方法及适用范围；了解主要模型的应用；掌握离散数学的推理与证明过程、基本算法及应用方法；掌握处理离散量的一些数学方法，并具有较好的逻辑推理和抽象思维的能力，为后续课程的学习及将来从事计算机软硬件技术开发做好必要的理论储备。
本课程共计学时：48。
成绩考核形式：末考成绩（闭卷考试）（70%）＋平时成绩（平时测验、作业、课堂提问、课堂讨论等）（30%)。成绩评定采用百分制，60分为及格。
三、课程教学内容
第一章 命题逻辑
1.教学基本要求
主要包括命题与联结词、命题公式及其赋值、等值式、析取范式与合取范式、推理的形式结构、自然推理系统。
2.要求学生掌握的基本概念、理论、技能
通过本章学习，了解命题概念，掌握五种联结词与真值表的构造；理解命题公式的概念，掌握命题公式类型的判断；理解等值式的概念，掌握命题公式的等值演算；理解析取范式与合取范式的概念，掌握主析取范式与主合取范式的求解方法；理解推理的形式结构与推理定律，掌握形式证明的方法与技巧。
3.教学重点和难点
教学重点是主析取范式与主合取范式及命题逻辑的推理理论。教学难点是.主析取范式与主合取范式的求解、推理理论及应用。
4.教学内容
（1） 命题与联结词
主要知识点：命题的概念及判断；联结词的理解。
（2） 命题变元和合式公式
主要知识点：命题变元和合式公式的定义；判断合式公式。
（3） 公式分类与等价公式
主要知识点：公式类型的判断（永真、永假、可满足式）；等价公式的定义、判断及重要的等价公式。
（4） 对偶式与蕴涵式
主要知识点：对偶式的定义及应用；蕴涵式的定义及证明方法；一些重要的蕴涵公式。
（5） 联结词的扩充与功能完全组
主要知识点：扩充的几个联结词及功能完全组的定义；判断功能完全组。
（6） 公式标准型——范式
主要知识点：公式范式的定义；能够把给定的公式化为范式的形式。
（7） 公式的主范式
主要知识点：大项、小项及主范式的定义；能够把公式化为主范式。
（8） 命题逻辑的推理理论
主要知识点：证明推理的有效性。
第二章 一阶逻辑
1.教学基本要求
主要包括一阶逻辑命题符号化、一阶逻辑公式及其解释、一阶逻辑等值式与置换规则、一阶逻辑前束范式、一阶逻辑的推理理论。
2.要求学生掌握的基本概念、理论、技能
通过本章学习，理解谓词、量词、变元、个体域等概念；掌握用谓词、量词、联结词构造谓词逻辑公式的方法。理解一阶逻辑公式的概念及其解释，掌握简单一阶逻辑公式类型的判断方法；理解一阶逻辑置换规则、换名规则、代替规则，掌握一阶逻辑基本等值式的使用；掌握一阶逻辑公式前束公式的求解方法；能够以谓词逻辑作为工具，将命题符号化，并能用推理规则进行逻辑证明。
3.教学重点和难点
教学重点是.一阶逻辑的概念与表示，一阶逻辑公式及其解释，一阶逻辑的等值式与置换规则，一阶逻辑的推理理论。教学难点是.一阶逻辑公式类型的判断和一阶逻辑的推理证明。
4.教学内容
（1）个体、谓词和量词
主要知识点：个体；谓词和量词的定义及表示。
（2） 谓词公式与翻译
主要知识点：谓词公式公式的递归定义；能够用谓词公式表示命题。
（3） 约束变元与自由变元
主要知识点：约束变元与自由变元的定义及判断；改名规则和带入规则的使用。
（4） 公式解释与类型
主要知识点：谓词公式解释的定义及实例；谓词公式的类型。
（5） 等价式与蕴涵式
主要知识点：谓词公式中一些重要的等价式与蕴涵式；量词辖域的扩大与缩小等价式。
（6） 谓词公式范式
主要知识点：谓词公式的前束范式定义及化简；斯柯林范式。
（7） 谓词逻辑的推理理论
主要知识点：量词的消去和产生规则；谓词逻辑的推理理论。
第三章 集合
1.教学基本要求
主要包括集合的基本概念、集合的运算、有穷集的计数、集合恒等式。
2.要求学生掌握的基本概念、理论、技能
通过本章学习，了解集合的基本概念，掌握集合的性质，掌握集合的基本运算和基本恒等式，掌握集合等式的证明方法与技巧。
3.教学重点和难点
教学重点是有穷集的计数与集合恒等式及集合等式的证明。教学难点是集合等式的证明。
4.教学内容
（1） 集合论基础
主要知识点：外延公理和子集公理的谓词逻辑表示形式
（2） 集合运算及其性质
主要知识点：用谓词逻辑的形式表示集合运算及其性质
(3) 集合的笛卡儿积与无序积
主要知识点：笛卡儿积与无序积的定义与区别
第四章 二元关系
1.教学基本要求
主要包括有序对与笛卡儿积、二元关系、关系的运算、关系的性质 、关系的闭包 、等价关系与划分、偏序关系。
2.要求学生掌握的基本概念、理论、技能
通过本章学习，理解笛卡儿积与二元关系的概念，掌握关系的表示、运算与性质；理解关系闭包的定义，掌握关系闭包的求解方法；理解等价关系、划分与偏序关系的定义，掌握等价关系和偏序关系的结构。
3.教学重点和难点
教学重点是等价关系与偏序关系的结构及应用、关系的闭包与算法。教学难点是关系的闭包与算法。
4.教学内容
（1） 二元关系
主要知识点：二元关系的定义及性质；二元关系的矩阵表示及关系图。
（2） 关系运算
主要知识点：关系的运算；复合运算；幂运算；逆运算；闭包运算等。
（3） 关系类型
主要知识点：关系类型等价关系；偏序关系；相容关系；准序关系等。
第五章 函数
1.教学基本要求
主要包括函数的定义与性质、函数的复合与反函数。
2.要求学生掌握的基本概念、理论、技能
通过本章学习，理解函数的基本概念，掌握函数的性质；掌握逆函数和复合函数的基本概念与性质；了解函数作为工具在集合势的研究中所起的作用。
3.教学重点和难点
教学重点和难点均为逆函数和复合函数的性质。
4.教学内容
（1） 函数基本概念
主要知识点：函数基本概念。
（2） 函数类型
主要知识点：函数类型（单射、满射和双射）及恒等函数；特征函数。
（3） 函数运算
主要知识点：函数的复合运算；逆运算。
（4） 基数
主要知识点：理解基数的定义；基数的比较及相关定理。
第六章 代数结构
1.教学基本要求
主要包括二元运算及其性质、代数系统、代数系统的同态与同构、群、格。
2.要求学生掌握的基本概念、理论、技能
通过本章学习，理解二元运算的定义，掌握二元运算的性质及特异元素的求解方法；了解代数系统的基本概念和性质，掌握代数系统之间的同构关系和同态关系；理解半群、群等基本代数系统的概念，掌握半群与群的性质；正确理解格的定义，掌握格的性质及子格的判定；理解分配格、布尔格与布尔代数的概念；了解群与格在计算机科学与技术中的应用。
3.教学重点和难点
教学重点是代数系统的同态与同构、群的性质及子群的判断、格的性质及子格的判定、.分配格、有补格与布尔代数特性。教学难点是代数系统之间的同构关系和同态关系、群的陪集分解。
4.教学内容
（1）代数结构的定义与例
主要知识点：代数结构的定义；掌握几种常见的代数结构。
（2） 代数结构的基本性质
主要知识点：代数结构的运算基本性质；结合律；交换律；分配律；吸收律；等幂律与等幂元；幺元或单位元；零元；逆元；可约律与可约元等。
（3）同态与同构
主要知识点：同态与同构的定义及他们的性质。
（4） 同余关系
主要知识点：同余关系的定义及性质。
（5）商代数
主要知识点：商代数的定义及相关定理。
（6）积代数
主要知识点：积代数的定义及相关定理。
第七章 图论
1.教学基本要求
主要包括图的基本概念 、通路与回路、图的连通性、图的矩阵表示、图的运算、欧拉图、哈密顿图、树与生成树、根树及应用。
2.要求学生掌握的基本概念、理论、技能
通过本章学习，了解图论的基本内容及其在计算机领域中的应用；理解图的基本概念、子图与补图概念，通路与回路的概念、图的连通性与连通度的概念、欧拉图与汉密尔顿图的概念、树及最优树的概念；掌握图的表示方法、图的可达性与连通性的判断；掌握图的通路与回路的判断、图的连通性的判断；掌握欧拉图与汉密尔顿图的判定方法；掌握求最小生成树的Kruskal算法、求最优树的Huffman算法。
3.教学重点和难点
教学重点是握手定理及其推论的应用、图中通路和回路应用、图中的可达性和连通性的求解方法、欧拉图判定、哈密顿图判定、最短路径及应用、最小生成树。教学难点是图的连通性的有关定理、图的同构及哈密尔顿图的判定。
4.教学内容
（1） 图的基本概念
主要知识点：图的基本概念；有向图；无向图等。
（2） 链(或路)与圈(或回路)
主要知识点：链(或路)与圈(或回路)的定义。
（3） 图的矩阵表示
主要知识点：图的矩阵表示；可达矩阵；邻接矩阵等；Dijkstra算法。
（4）欧拉图与哈密尔顿图
主要知识点：欧拉图与哈密尔顿图的定义及判定定理。
(5）二部图
主要知识点：二部图及二部图中匹配理论的主要概念和成果。
(6)树
主要知识点：树的概念和性质；最小生成树；二叉树遍历以及哈夫曼树和哈夫曼编码。
(7)平面图
主要知识点：平面图的概念及相关定理；欧拉定理；平面图的着色。
四、学时分配
|
章序 |
内容 |
课时 |
备注 |
|
一 |
命题逻辑 |
6 |
|
|
二 |
谓词逻辑 |
6 |
|
|
三 |
集合 |
8 |
习题 |
|
四 |
二元关系 |
6 |
|
|
五 |
函数 |
6 |
|
|
六 |
代数结构 |
6 |
|
|
七 |
图论 |
10 |
习题 |
|
合计 |
48 |
|
|
五、主用教材及参考书
（一）主用教材：
《离散数学（第五版）》 主编：耿素云，屈婉玲，张立昂 出版社：清华大学出版社 出版时间：2013年。
（二）参考书：
1.《离散数学》 主编：屈婉玲等 出版社：清华大学出版社 出版时间：2011年。
2.《离散数学》 主编：李盘林等 出版社：人民邮电出版社 出版时间：2009年。
3.《离散数学》 主编：耿素云等 出版社：高等教育出版社 出版时间：2010年。