《离散数学教学大纲》

课程编号：

课程性质：专业基础课 先修课程：高等数学，线性代数

总学时数：56 学分：3.5 讲课：56 实验： 上机： 课外实践： 适合层次：本科 适合专业：信息管理与信息系统 一、课程的目的与任务

离散数学是现代数学的一个重要分支，主要研究离散量的结构和相互关系，是计算机学科的理论基础，是计算机类各专业的一门重要基础课。

本课程通过介绍数理逻辑、集合论、代数系统和图论的基本概念和基本原理，使学生了解离散结构之间的关系和基于这些离散结构的算法，培养抽象思维能力，对计算机描述的世界的建模能力，为学习数据结构、数据库、操作系统、计算机网络等课程提供数学处理工具。 二、理论教学要求

（一）集合的概念 本章教学内容有：

（1）集合的概念。集合、元素、子集、空集、全集、幂集、集合相等等概念，幂集的表示法。 （2）集合运算。集合的交、并、差、补、对称差等运算、文氏图、包含排斥原理。

（3）集合运算的性质。交换律、结合律、分配律、吸收律、De Morgan律、恒等律、互补律、否定律、零律；集合的特征函数。

（4）典型例题及本章小结。

本章的重点是集合的运算及其性质，难点有幂集的概念、包含排斥原理、集合的特征函数、证明集合相等的方法。要求了解幂集的表示方法、集合的特征函数；理解集合的运算概念、文氏图；掌握集合的运算性质、包含排斥原理和集合相等的证明方法。

（二）二元关系 本章教学内容有：

（1）序偶与笛卡尔积。有序n元组、笛卡尔积。

（2）关系的概念。n元关系（空关系、全关系、恒等关系）、二元关系、二元关系的表示（矩阵法和关系图法）。

（3）关系的运算。复合运算与复合关系、逆运算与逆关系

（4）关系的性质。自反性与反自反性、对称性与反对称性、传递性。

（5）关系闭包与特殊关系的构造。自反闭包、对称闭包、传递闭包的概念及其构造算法。 （6）等价关系与集合的分类。等价关系、等价类和商集的概念。

（7）偏序关系与集合元素的排序。偏序关系、偏序集、哈斯图、最（极）大元、最（极）小元、上界与上确界、下界与下确界。

（8）典型例题与本章小结

本章的重点是关系的性质及其判别，关系矩阵与关系图，关系的复合运算及其性质，等价关系及集合的划分，偏序集的概念；难点是关系闭包的构造算法，集合的分类方法，哈斯图的画法，与偏序关系有关的确界概念。要求了解商集、极大（小）元、最大（小）元、确界的概念；理解关系

矩阵与关系图；掌握序偶与笛卡尔积的概念、关系的概念、关系的性质、关系闭包的概念与构造算法、等价关系与偏序关系。

（三）映射与集合的基数 本章教学内容有：

（1）映射。映射、相等映射、单射、满射、双射的概念。

（2）复合映射与逆映射。映射的复合运算及其性质，映射的逆运算及其性质。 （3）映射的应用。等势、有限集合与无限集合、可数集合与不可数集合、集合的基数。 （4）典型例题与本章小结。

本章重点是映射的概念。难点是复合映射与逆映射的概念及其性质，映射与一般关系、逆映射与逆关系的区别。要求了解映射的应用；理解单射、满射、双射的概念，复合映射与逆映射的概念；掌握映射的概念。

（四）命题逻辑 本章教学内容有：

（1）命题与联接词。命题、命题的真值、原子命题与复合命题。

（2）命题公式与解释。常值命题与变量命题、命题公式、命题公式的解释、命题公式的分类、命题公式的等价。

（3）范式。析取范式和合取范式的概念、对偶原理、极大项和极小项的概念、主吸取范式和主合取范式的概念、主吸取范式和主合取范式的求法。

（4）公式恒真性的判定。利用主吸取范式或主合取范式判定公式的恒真性。

（5）公式的蕴涵。公式蕴涵的三个等价定义及其逻辑结果；公式的逻辑结果与演绎的逻辑结果的等价性，基本蕴涵公式。

（6）形式演绎。演绎规则（规则P，规则Q，规则D），公式的相容性。 （7）典型例题与本章小结

本章的重点是逻辑联结词的意义，命题公式的主吸取范式和主合取范式，推理证明的方法。难点是命题公式主吸取范式和主合取范式的求法，推理证明的间接证法。要求理解用联结词产生复合命题的方法，公式在解释下的真值，公式范式的概念，形式演绎和蕴涵的关系。掌握命题、逻辑联结词的概念，公式与解释的概念，公式的递归定义，用基本等价式化简其他公式，主析取范式及其唯一性，用真值表法判断公式的类型；公式蕴涵与逻辑结果的概念；形式演绎方法。

（五）谓词逻辑 本章教学内容有：

（1）谓词与量词。谓词（命题函数）、量词的概念。

（2）公式与解释。项、原子、谓词公式的概念，量词的协域，指导变元、约束变元与自由变元，改名规则，谓词公式的解释、谓词公式的类型。

（3）等价与蕴涵。谓词演算的等价式与蕴涵式 （4）前束范式。前束范式的概念与求法。

（5）谓词演算的演绎与推理。与量词有关的推理规则，谓词演绎的推理方法 （6）典型例题与本章小结。

本章重点是谓词公式等价的证明方法；谓词演算的推理证明方法。难点是谓词演算的推理证明

方法。要求了解以谓词逻辑为工具，将命题符号化的方法；理解用谓词、量词、逻辑联结词描述一个简单命题，公式的递归定义，用解释的方法证明等价式和蕴涵式；掌握个体词、个体域、谓词、量词的概念和使用，原子、公式、解释的概念，公式在解释下的真值，求公式的前束范式。

（六）代数系统 本章教学内容有：

（1）代数结构概述。代数运算，代数系统，单位元、逆元等的概念。 （2）群。群的概念、置换群。 （3）群的同态。同态映射的概念。 （3）环与域。环、域的概念

（4）格的概念。偏序格与代数格的概念，有余格、分配格、有界格的概念。 （5）布尔代数。布尔代数的概念，布尔代数的性质。

本章内容涉及抽象代数，要求学生了解代数系统的结构、特殊的代数系统群、环、域以及格的概念。

（七）图论 本章的教学内容有： （1）图的概念。 （2）路与回路 （3）图的矩阵表示 （4）关系与图 （5）二分图 （6）树的概念

（7）生成树与最优支撑树 （8）有向树与根树 （9）平面图

三、实践教学要求 四、学时分配

序号 1 2 3 4 5 课程内容 集合的概念 二元关系 函数与集合的基数 命题逻辑 谓词逻辑 代数系统 图论 小 计 学时分配 讲课 4 10 4 10 8 6 14 56 实验 上机 课外 小计