离散数学简明教程付延友

由天下分享时间：2024/12/24 2:39:48 加入收藏我要投稿点赞

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

一、课程简介

课程名称：离散数学

英文名称：Discrete Mathematics

课程代码：0310513 课程类别：专业基础课学分：3 总学时：48 课程概要：

《离散数学》是现代数学的一个重要分支，是计算机类各专业的一门重要基础课，是计算机科学理论的基础。它是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是有限个或可列个元素，因此它充分描述了计算机科学的离散性特点。其主要内容包括数理逻辑、集合论、关系与函数、图论等内容。该课程与计算机类专业中的数据结构、操作系统、编译原理、数据库原理与应用、人工智能等后继专业课程紧密相关，因此是一门重要的学科基础必修课程。该课程以高等数学、线性代数为先修课程，但关系不很紧密。

二、教学目的及要求

通过该课程的学习，使学生掌握命题逻辑与谓词逻辑、集合与关系、图与树的基本概念和基本理论与方法，为学生学习计算机领域的后续课程奠定理论基础，并培养学生抽象思维、缜密概括和严密的逻辑推理能力，为学生今后处理离散信息打好数学基础。

三、教学内容及学时分配

第一章命题逻辑（12学时）

1.命题及其表示； 2.逻辑联结词； 3.命题公式与翻译； 4.真值表与等价公式； 5.命题公式的分类与蕴含式； 6.命题公式的范式； 7. 命题逻辑的推理理论。

教学要求：熟悉命题、命题的真值、简单命题、复合命题、命题公式、真值表、等价公式、重言式、矛盾式、蕴涵式、（主）析取范式、（主）合取范式等概念；熟悉五个基本

联结词（?、?、?、?、?）的定义；掌握命题公式的翻译、命题公式的类型的判别、命题定律、证明两个命题公式等价的真值表法和等值演算法及命题公式的（主）析取范式、（主）合取范式的求法；掌握推理证明的直接证法和间接证法。

重点：五个逻辑联结词；翻译、命题公式的等值演算、主析取范式、主合取范式；推理证明的直接证法和间接证法。

难点：命题公式的主析取范式、主合取范式的求法；推理证明的间接证法。

第二章谓词逻辑（10学时）

1.谓词与量词； 2.谓词公式与翻译； 3.变元的约束；

4.谓词演算的等价式与蕴含式； 5.谓词演算的推理理论。

教学要求：熟悉谓词、命题函数、复合命题函数、全称量词、存在量词、谓词公式、辖域、约束变元、自由变元、谓词演算的等价式与蕴涵式、前束范式等概念；掌握谓词演算翻译、谓词演算的等价式、谓词演算的推理规则及谓词演算的推理证明的方法。

重点：谓词演算翻译、两个谓词公式等价的证明；谓词演算的推理证明。难点：谓词演算翻译、谓词演算的推理证明。

第三章集合的基本概念与运算（2学时）

1.集合的基本概念； 2.集合的运算。

教学要求：熟悉集合的概念和表示法；掌握幂集的概念；掌握集合的交、并、差、补、对称差的运算及其运算律和幂集的求法。

重点：集合的运算及其运算律；幂集的求法。难点：元素为集合组成的集合的运算与求幂集。

第四章二元关系和函数（12学时）

1.关系及其表示；

2.关系的性质及其判定方法； 3.复合关系和逆关系； 4.关系的闭包； 5.等价关系；

6.偏序关系； 7.函数及特殊映射； 8.复核映射和逆映射。

教学要求：熟悉序偶、笛卡尔积、关系、集合的划分与覆盖、等价关系、等价类、商集、偏序关系、极大元、极小元、上（下）界、上（下）确界、最大（小）元、全序关系、良序关系等概念；掌握关系的三种表示序偶集合、关系图和关系矩阵；掌握关系的交、并、逆、复合运算、闭包运算及其性质；理解关系的自反性、反自反性、对称性、反对称性和传递性，掌握其判别方法；了解集合的覆盖与划分的联系与区别；掌握等价关系与等价类、等价关系与集合的划分的联系；掌握偏序关系的判别及其哈斯图的画法；掌握偏序集中给定集合的极大元、极小元、上（下）界、上（下）确界、最大（小）元；掌握函数（映射）、函数的前域、值域、相等、入射、满射、双射、恒等映射、反函数、复合函数的概念；掌握函数与一般关系的区别；掌握函数复合运算的性质、反函数存在的条件；掌握函数是入射、满射、双射的证明。

重点：关系的三种表示；关系的性质及其判别；关系的复合、求逆运算及其性质；等价关系与等价类、等价关系与集合的划分的联系；偏序关系判别及其哈斯图的画法、偏序集中特殊位置元素的求法。复合运算的性质；函数与一般关系、反函数与逆关系的区别；函数是入射、满射、双射的证明。

难点：关系的传递性及其判别；偏序关系的哈斯图的画法；偏序集中特殊位置元素的求法。函数是入射、满射、双射的证明。

第五章图的基本概念（5学时）

1.图的基本概念； 2.路与图的连通性； 3.图的矩阵表示。

教学要求：掌握图、点邻接、边邻接、子图、结点的度数、出度、入度、有向图、无向图、简单图、完全图、补图、生成子图、图的同构、及其性质；掌握握手定理、路、回路、连通图、强连通、单向连通、弱连通、割点、割边的概念；掌握图的矩阵表示，利用图的邻接矩阵会求（1）任一结点的入度、出度和度数；（2）一个结点到另一个结点长度为k的路径的条数；（3）该图的可达性矩阵。

重点：图、点邻接、边邻接、结点的度数的概念；握手定理（结点的度数及其相关性质）；路、回路、连通图、强连通、单向连通、弱连通、割点、割边的概念；图的邻接矩

阵。

难点：握手定理的应用；弱连通、强连通的判别。

第六章一些特殊的图（讲课3学时）

1.欧拉图与汉密尔顿图； 2.平面图。

教学要求：掌握欧拉图、汉密尔顿图和平面图的定义、判别及其应用。重点：欧拉图、汉密尔顿图和平面图的定义、判别及其应用。难点：欧拉图、汉密尔顿图和平面图的判别及其应用。

第七章树（讲课4学时）

1.树与生成树； 2.根树及其应用； 3.最短路问题。

教学要求：掌握树、生成树、最小生成树、根树、树根、树叶、分枝点、有序树、完全m叉树、最优树等概念及其有关性质；掌握有关树的几个等价命题；熟练应用最小生成树的Kruskal算法及最优二叉树的Huffman构造方法。

重点：树、生成树、最小生成树、根树、树根、树叶、分枝点、完全m叉树、最优树等概念及其有关性质；有关树的几个等价命题；最小生成树的Kruskal算法及最优二叉树的Huffman构造方法。

难点：树的几个等价命题。

四、课程教学的基本要求