离散数学大纲

《离散数学大纲》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、离散数学教学大纲第一部分大纲说明一.        课程的性质与任务《离散数学》是现代数学的一个重要分支，也是计算机计算机科学与技术一级学科及其相关专业必修的基础理论的核心课程。它是学习后续专业课程不可缺少的数学工具。该课程结合计算机学科的特点，主要研究离散量结构及相互关系，其研究对象一般是有限个或可数个元素，因此《离散数学》充分描述了计算机学科离散性的特点。它是一门理论性较强，应用性较广的课程。掌握集合论、数理逻辑、图论、整数、群、环、域、格、布尔代数以及语言与有限自动机等离散数学的基本概念和

2、基本原理，为学习计算机专业各后续课程做好必要的知识准备。并通过这些知识的学习进一步提高学生的抽象思维和逻辑推理能力，为从事计算机相关的理论研究与应用提供必要的描述工具和理论基础。二《离散数学》的特点作为计算机科学与技术一级学科的一门课程，《离散数学》有与其他课程相同相似的地方，当然也有它自身的特点：1、义与定理多。《离散数学》是建立在大量定义之上的逻辑推理学科，因此对概念的理解是我们学习这门课程的核心。在学习这些概念的基础上，要特别注意概念之间的联系，而描述这些联系的实体则是大量的定理与性质。2

3、、法性强。《离散数学》的许多证明题中，方法性是非常强的，如果知道题的证明方法，很容易就可以证出来，反之则事倍功半。所以在学习该课程中要善于总结，勤于思考，这也是培养分析问题解决问题抽象思维能力的一个过程。三    与其他相关课程的关系先修课程：高等数学（包括数学分析、线性代数）后续课程：数据结构、数据库、编译原理等 四      课程的主要内容与基本要求本课程分为九部分：集合论基础、命题逻辑、谓词逻辑、图与网络、数论基础、群与环、多项式与有限域、格与布尔代数以及语言和有限自动机。（一）集合论基础

4、：在整个《离散数学》的知识体系中，集合论处于基础的地位，对于其所包含知识的掌握程度，直接关系到是否能学好图论和抽象代数问题。本章主要讲述集合、关系和映射。1.掌握集合、子集、超集、空集、幂集、集合族的概念。懂得两个集合间相等和包含关系的定义和性质，能够利用定义证明两个集合相等。熟悉常用的集合表示方法。2.掌握集合的基本运算：并、交、余、差、直乘积、对称差的定义以及集合运算满足的基本算律，能够利用它们来证明更复杂的集合等式。3.掌握关系、二元关系、空关系、全域关系、相等关系、逆关系的概念以及关系的

5、性质：自反性、对称性、反对称性、传递性。会做关系的乘积。了解关系的闭包运算：自反闭包、对称闭包、传递闭包。4.掌握等价关系、等价类、商集的概念，了解等价关系和划分的内在联系。5.掌握部分序关系、部分序集、全序关系、全序集的概念以及部分序集中的特殊元素：最大元、最小元、极大元、极小元、上确界、小确界的定义。能画出有限部分序集的Hasse图，并根据图讨论部分序集的某些性质。6.掌握映射、映像、1-1映射等概念，会做映射的乘积。了解可数集合的概念，掌握可数集合的判定方法。7.了解关系在数据库中的应用（

6、数据的增、删、改）以及划分在计算机中的应用。重点是使学生会用集合描述和解决问题，掌握二元关系，二元关系的性质及其证明方法（按定义证明法），对映射概念的深入理解；难点是证明集合相等，等价关系与部分序关系，1-1映射的证明和集合的可数性证明。（二） 数理逻辑：数理逻辑是用数学方法研究思维规律和推理过程的科学，由于它使用一套符号，简洁地表达出各种推理的逻辑关系，因此数理逻辑又称为符号逻辑。它和计算机的发展有着密切的联系，它为机器证明、自动程序设计、计算机辅助设计等计算机理论研究与应用提供了必要的理论基

7、础。本章需要学生掌握下列内容。1.掌握命题、逻辑联结词等概念，能够将命题符号化。2.掌握命题公式、解释、恒真公式、恒假公式等概念。能够判断一命题公式是恒真、恒假还是可满足。3.掌握公式的等价、蕴涵等概念，熟记基本的等价式、蕴涵式，会证明更复杂的等价式、蕴涵式。4.掌握联结词的功能完备集（全功能集）的概念，能够判别一个联结词集合是否为联结词的功能完备集。5.掌握演绎方法，能够使用演绎方法进行有效推理。6.掌握析取范式、合取范式、极大项、极小项、主析取范式、主合取范式的概念和性质。掌握求各种范式的方

8、法，能够用等价演算法和真值表法求命题公式的主析取范式、主合取范式。了解一个命题公式的主合取范式与主析取范式的关系——如何根据一种主范式立即写出另一种主范式。7.了解命题逻辑在二值逻辑器件和语句逻辑中的应用。重点是命题概念，等价公式与蕴涵公式，求主合取范式与主析取范式，联结词的变化与全功能集、演绎推理；难点是演绎推理和综合应用。（三）谓词逻辑：谓词逻辑是在命题逻辑的基础上，对命题进行进一步的细分，分解出命题中的主语、谓语等，以便能处理句子的内部结构之间的逻辑关系，而非仅仅是句子之间的逻辑关系。为此