|
 教学大纲 |
《离散数学》教学大纲
(总学时90，其中讲课72，实验18)
一、教学目的
《离散数学》是现代数学的一个重要分支，是计算机科学与技术专业的基础理论课，也是该专业的核心课程和主干课程。传统的《离散数学》包括四个部分的内容：数理逻辑、集合论、代数系统和图论。该课程一方面为后继课程如数据结构、编绎原理、操作系统、数据库原理、人工智能和形式语言与自动机等提供必要的理论基础；同时，更为重要的是培养学生的抽象思维能力和逻辑推理能力，为今后的学习和工作打好基础。无论从计算机学科发展的过去、现在和未来看，《离散数学》都是计算机科学与技术专业不可缺少的重要组成部分。这门课程有着其它课程不可替代的地位和作用，是一门承前启后的课程。
二、教学内容
第一篇 数理逻辑
要求学生掌握计算机学科所必须的数理逻辑基础知识：命题逻辑与谓词逻辑。并补充介绍非单调逻辑、时序逻辑等与计算机学科发展相适应的前沿性、拓展性知识以及数理逻辑的有关应用。
第一章 命题逻辑
【本章要求】命题逻辑也称符号逻辑，或演算逻辑。它研究以命题为基本单位构成的前提和结论之间的可推导的关系。要求学生熟练掌握命题、联结词、等价式、永真式、永假式、蕴涵式、最小全功能联结词集、范式、主范式等基本概念和理论，熟练掌握有关证明方法和推理方法。
第一节 命题及联结词
1． 命题的概念。
2． 命题的表示。
3． 命题的分类。
4． 联结词的定义。
第二节 命题公式及命题公式的翻译
1． 命题公式的概念。
2． 公式的翻译。
第三节 公式的等价性
1． 等价式的定义。
2． 子公式的定义。
3． 利用真值表和公式推导证明等价式的方法。
第四节 永真式、永假式及蕴涵式
1． 永真式、永假式的概念。
2． 蕴涵式的定义。
3． 等价式和蕴涵式之间的关系。
4． 蕴涵式的证明方法，即真值表法、叙述法。
第五节 不同真值表的命题公式及全功能联结词的集合
1． 某公式不同真值表的个数。
2． 异或、与非、或非、逆条件联结词的定义。
3． 全功能联结词集、最小全功能联结词集的定义。
第六节 对偶
1． 对偶的定义。
2． 对偶定理及运用。
第七节 公式标准型――范式
1． 基本和、基本积、析取范式、合取范式的定义及求解。
2． 极小项、极大项、主析取范式、主合取范式的概念。
3． 主范式的求解方法。
第八节 命题演算的推理理论
1． 有效结论的概念。
2． P规则、T规则、CP规则。
3． 证明有效结论的方法：真值表法、直接证法、间接证法。
第二章 谓词逻辑
【本章要求】命题逻辑主要研究了命题及命题演算，其基本组成单位为原子命题。为了刻划命题内部的逻辑结构，有必要研究谓词逻辑。本章应熟练掌握谓词、量词、个体域、谓词公式、约束变元、自由变元、谓词演算的等价式、蕴涵式、前束范式等基本概念与理论，熟练运用相关理论求解谓词逻辑的等价式、蕴涵式、熟练掌握推理证明的方法。
第一节 谓词 量词 个体域
1． 谓词逻辑的基本概念。
2． 谓词、个体、个体域、量词的概念。
第二节 谓词公式及翻译
1． 谓词公式的定义。
2． 谓词公式的翻译。
第三节 约束变元与自由变元
1． 约束变元与自由变元的概念。
2． 约束变元的换名。
3． 自由变元的代入。
第四节 谓词演算的等价式及蕴涵式
1． 谓词演算的永真式、等价式、蕴涵式的概念。
2． 量词转换律、量词辖域的扩张和收缩律等谓词演算的等价式及蕴涵式。
3． 多个量词的定义及使用。
第五节 前束范式
1． 前束范式的定义。
2． 任意谓词公式都存在与其等价的前束范式、前束析取范式与前束全取范式。
3． 前束范式与前束析取范式的定义及求解方法。
第六节 谓词演算的推理理论
1． 谓词演算中对量词的处理规则：US、ES、UG和EG。
2． 谓词演算的推理方法――直接证明方法和间接证明方法。
3． 全称规定规则、存在规定规则、全称推广规则和存在推广规则的使用方法。
第三章 非经典逻辑简介
【本章要求】本章简要介绍了非经典逻辑的有关内容。讨论了非经典逻辑与经典逻辑的区别、非经典逻辑的主要类型、与现代计算机科学与技术的联系等内容。目的是使学生把握学科发展的脉络、留有与新知识的接口和“窗口”。
第一节 模态逻辑基础
1． 模态算子“可能”、“必然”的定义及其翻译。
2． 模态逻辑的非形式讨论。
3． 模态命题逻辑公式的定义。
4． 命题时态逻辑中的模态算子的定义。
5． 模态谓词逻辑的概念及有关等价式。
第二节 模态逻辑的几种解释
1． 真理论模态逻辑。
2． 认识论模态逻辑。
3． 道义论模态逻辑。
4． 时态逻辑。
5． 经验论模态逻辑。
第三节 三值逻辑
1． 三值逻辑的概念。
2． 克利恩三值逻辑、卢卡西维茨三值逻辑、波兹瓦三值逻辑的定义。
第四节 非单调逻辑
非单调逻辑的概念。
第二篇 集合论
在计算机科学领域中，集合论是不可缺少的数学工具。本部分除了介绍一般的集合及其运算、基数、关系及函数等计算机科学所必须的基础知识外，还简单介绍了近年来在计算机科学中得到广泛应用的模糊集和粗糙集的有关概念和应用，以拓展基础理论与计算机学科发展与应用的接口与窗口。
第四章 集合
【本章要求】集合论是现代数学的重要分支，也是计算机科学的重要基础。本章应该掌握集合的概念及表示、集合间的关系、集合运算、有限集与无限集、可数集与不可数集的概念，掌握基本的求解集合问题的方法，技巧，学会运用包含排斥原理。
第一节 集合的概念及其表示法
1． 元素、集合的概念。
2． 枚举法、描述法等集合的表示法。
第二节 集合间的关系
1． 集合相等的定义。
2． 集合包含的定义及有关性质。
第三节 集合的基本运算
1． 集合的交、并、补、差、对称差的定义。
2． 集合运算的性质。
3． 集合的幂集的概念。
第四节 包含排斥原理
1． 两个集合的包含排斥原理及应用。
2． 包含排斥原理。
第五节 有限集与无限集
1． 集合的基数及一一对应的概念。
2． 有限集、无限集的概念。
第六节 可数集与不可数集
可数集、不可数集的概念及判定方法。
第五章 关系
【本章要求】关系是一种特殊的集合，在数据结构、数据库、情报检索、算法分析等领域都有很多应用。本章应熟练掌握关系的概念、二元关系的表示及其性质、等价关系、相容关系、偏序关系的定义及判定方法，掌握关系的运算。
第一节 关系的概念
1． 序偶（二元组）、三元组及n元组的概念。
2． 笛卡尔积的概念及性质。
3． 关系、关系的定义域和值域的概念。
第二节 二元关系的表示及其性质
1． 关系的矩阵表示。
2． 关系的图形表示法。
3． 二元关系自反性、反自反性、对称性、反对称性、传递性的定义及判定。第三节 等价关系与划分
1． 等价关系的定义及判定。
2． 等价类与商集的概念。
3． 等价类的性质。
4． 集合覆盖、划分的概念及判定。
第四节 相容关系与覆盖
1． 相容关系的定义及判定。
2． 相容类、最大相容类的定义及性质。
第五节 关系的运算
1． 关系的合成运算及合成运算的有关性质。
2． 关系的逆运算及性质。
3． 关系的闭包运算及性质。
第六节 偏序关系
1、 偏序关系、偏序集、全序关系、拟序关系、良序关系的定义及其相互间的关系。
2、 偏序集中的成员判定。
第六章 函数
【本章要求】函数是二元关系的特例，熟练掌握函数、函数的合成、特殊函数、反函数、集合的特征函数与模糊子集的概念及性质。
第一节 函数
1． 函数的定义、表示及与关系的区别。
2． 两个函数相等的定义。
3． 函数的合成运算的定义。
第二节 特殊函数
1． 满射函数、单射函数、双射函数的定义及判定方法。
2． 常函数、恒等函数、等幂函数等的定义。
第三节 反函数
反函数的定义及性质。
第四节 集合的特征函数与模糊子集的概念
1． 特征函数、隶属函数的定义。
2． 模糊子集的概念及判定。
第七章 粗糙集简介
【本章要求】掌握粗糙集的概念、粗包含、粗等价、上近似、下近似、粗等价、粗包含等概念及性质。
第一节 粗糙集合研究概况
第二节 知识的基本概念
1． 知识与分类的关系。
2． 知识、知识库、近似空间的概念。
3． 可区分关系、不可区分关系的概念。
第三节 粗糙集的基本概念
1． 集合X是可定义集、不可定义集、精确集和粗糙集的概念。
2． 上近似集、下近似集、正域、负域的概念及性质。
第四节 成员关系 粗等价和粗包含
1． 上成员关系、下成员关系、成员关系。
2． 上等价、下等价和粗等价的概念，粗等价与上近似、下近似间的关系。
3． 上包含、下包含和粗包含的概念。
第三篇 近世代数
近世代数把在任意性质的元素上所进行的代数运算作为研究的基本对象，对计算机学科的发展起着重要的作用。本部分介绍代数系统、半群、群、环、域、格与布尔代数的内容。
第八章 代数系统
【本章要求】掌握代数系统的基本概念、运算的基本性质以及代数系统同态、同构、代数系统的同余关系、积代数的基本概念及判定。
第一节 代数系统的概念
1． 代数系统、子代数系统、代数系统同型的概念
2． 代数系统的封闭性、代数系统中的运算所具有的性质及判定。
第二节 代数系统的同态与同构
1． 代数系统之间的同态与同构的概念及判定。
2． 代数系统的自同态、自同构的概念。
第三节 代数系统的同余关系与商代数
1． 同余关系、商代数的概念及有关性质。
2． 代数系统同态基本定理。
第四节 代数系统的积代数
积代数系统的概念。
第九章 半群与群
【本章要求】具有一个二元运算的代数系统。应熟练掌握半群、含幺半群、子半群、子含幺半群的概念、群、子群、陪集等的定义及判定方法。
第一节 含幺半群
1． 半群、含幺半群的概念及判定方法。
2． 交换半群、交换含幺半群的定义。
3． 循环半群、循环含幺半群的概念。
4． 半群、含幺半群的积代数的概念。
第二节 子半群与子含幺半群
子半群、子含幺半群的概念及判定方法。
第三节 半群与含幺半群的同态与同构
1． 半群与含幺半群同态（构）的概念及判定。
2． 半群与含幺半群的满同态、单同态的概念。
3． 半群与含幺半群的自同态、自同构的概念及判定。
第四节 群
1． 群、阿贝尔群的概念及判定。
2． 代数系统是群、阿贝尔群概念及判定定理。
3． 半群是群的判定定理。
4． 有限半群是群的定理。
5． 置换群概念、循环群的概念。
6． 两个群的积代数是群。
第五节 子群与陪集
1． 子群、真子群的概念及判定。
2． 循环群的子群必为循环群。
3． 左陪集、右陪集、陪集及正规子群的概念及有关性质。
4． 群的非空子集构成子群的判定定理。
5． 商群的概念。
第六节 群的同态与同构
1． 群同态（构）的概念及判定。
2． 群的自同态、自同构的概念。
3． 群的同态基本定理。
第十章 环与域
【本章要求】本章研究具有两个二元运算的代数系统――环。熟练掌握环、各种特殊环、子环、理想子环的概念及环的同态、同构的概念，域的概念及判定。
第一节 环
1． 环的定义及判定。
2． 交换环、含幺环、布尔环、零因子环、无零因子环、整环、除环等特殊环的定义及判定。
3． 环的有关性质。
4． 两个环的积代数是环。
第二节 子环与理想
1． 子环的定义及判定。
2． 环的非空子集构成环的充要条件。
3． 左理想子环、右理想子环、理想子环的定义及判定。
4． 商环的定义。
第三节 环的同态与同构
1． 环同态（构）、环自同态（构）的概念。
2． 环同态基本定理。
第四节 域
1． 域的定义。
2． 代数系统是域的充要条件。
3． 两个域的积代数不是域。
第十一章 格与布尔代数
【本章要求】熟练掌握格的两种定义及判定，格同态、格同构、格的积代数、有界格、完全格、有补格、模格、分配格的定义及判定。有补分配格是布尔代数，掌握布尔代数的子布尔代数、布尔代数的同态、同构的定义及判定。
第一节 用偏序集定义的格
1． 保交、保联运算的定义。
2． 用偏序集定义格的概念。
3． 格的保序性、格的分配不等式、格的模不等式等概念及有关性质。
第二节 用代数系统定义的格
1． 代数系统构成格的定义。
2． 代数系统定义的格与偏序集定义格的等价性。
3． 子格、格同态、格同构、格保序映射的概念。
4． 两个格的积代数是格
第三节 特殊格
1． 完全格、有界格、有补格的概念及有关性质。
2． 模格、分配格、有补分配格的概念及有关性质、判定定理。
第四节 布尔代数
1． 布尔代数的定义及其性质。
2． 代数系统是布尔代数的充要条件。
3． 子布尔代数的概念。
4． 布尔代数同态（构）的定义及判定方法
5． 两个布尔代数的积代数是布尔代数的概念及判定。
第四篇 图论
图论是研究点和线的位置关系的一门学科，在计算机科学领域有着极为广泛的应用。本部分介绍图的基本概念、几种特殊图及应用，并补充有关PETRI网的简要介绍。
第十二章 图的基本概念
【本章要求】本章介绍了图的一般概念，要求掌握图、子图、简单图、完全图、连通图、图中顶点数和边数间的关系、生成子图、导出子图、补图、图同构、路径、循环、等概念。掌握图的矩阵表示、可达矩阵的基本概念及有关性质，熟练利用图的有关理论解决一些应用问题。
第一节 图与子图
1． 无向图、有向图的定义。
2． 图的基本术语、子图、生成子图、真子图、导出子图的概念。
3． 完全图、补图、图同构、连通图的概念。
4． 图中顶点数和边数间的关系。
第二节 路径与循环
1． 路径、基本路径、简单路径的定义。
2． 循环、基本循环、简单循环的定义及有关性质。
3． 割边、割点的定义。
4． 有向图的联通性的概念及性质。
第三节 图的矩阵表示
1． 关联矩阵的定义。
2． 邻接矩阵的定义及性质。
3． 可达矩阵的定义及与邻接矩阵间的关系。
4． 距离矩阵的定义。
第四节 应用举例
1． 均分问题求解的方法。
2． dijkstra算法及应用。
3． floyd算法及应用。
4． 决策图和评审图的概念及应用。
第十三章 欧拉图与哈密顿图
【本章要求】掌握欧拉图和哈密顿图的定义、判定及应用。
第一节 欧拉图
1． 欧拉路径、欧拉循环、欧拉图的定义。
2． 欧拉定理。
第二节 哈密顿图
1． 哈密顿路径、哈密顿循环、哈密顿图的定义。
2． 有关充分条件及必要条件的定理。
第十四章 特殊图
【本章要求】掌握树、生成树、最优树、有向树、有序树、二分图、二分图的判定定理、平面图、可平面图、欧位公式及推论、非可平面图、对偶图等概念和应用。
第一节 树
1． 树的概念及判定定理。
2． 生成树、最优树的概念及求解。
3． 有向树、有序树、m元有序树、位置m元有序树的概念及判定。
4． 前缀码的概念及应用。
第二节 二分图
1． 二分图、有向二分图、完全二分图的概念。
2． 无向图是二分图的判定定理。
3． 匹配和完美匹配的概念和判定。
第三节 平面图
1． 平面图、可平面图、平面嵌入、非可平面图的概念。
2． 极大可平面图、极大平面图的概念。
3． 有限面、无限面的概念。
4． 欧拉公式及推论。
5． 库拉托夫斯基定理。
6． 平面图的对偶图及求解。
7． 四色定理。
第十五章 PETRI网简介
【本章要求】了解PETRI网、标记PETRI网等有关概念。
1． PETRI网的定义。
2． 标记PETRI网的概念。
3． PETRI网的活动性及安全性。
三、授课方式：
讲授为主。
四、考核方式：
作业、实习及平时成绩：20%
期中测验：10%
期末闭卷考试成绩：70%
|
|
课堂教学大纲