离散结构教学大纲

离散结构教学大纲DiscreteStructures适用专业：计算机科学与技术专业 课程编号：0809213001前修课程：高等数学，线性代数 学分：3.5总学时：56一、课程性质、目的与要求课程性质：专业基础、必修课课程目的：离散数学是现代数学的一个重要分支，主要研究离散量的结构和相互关系，是计算机学科的理论基础，是计算机类各专业的一门重要基础课。本课程通过介绍数理逻辑、集合论、代数系统和图论的基本概念和基本原理，使学生了解离散结构之间的关系和基于这些离散结构的算法，培养抽象思维能力，对计算机描述的世界的建模能力，为学习数据结构、数据库、操作系统、计算机网络等课程提供数学处理工具。教学要求：通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。二、教学内容 理论总学时：56学时第一章：命题逻辑10学时基本要求：理解用联结词产生复合命题的方法，公式在解释下的真值，公式范式的概念，形式演绎和蕴涵的关系。掌握命题、逻辑联结词的概念，公式与解释的概念，公式的递归定义，用基本等价式化简其他公式，主析取范式及其唯一性，用真值表法判断公式的类型；公式蕴涵与逻辑结果的概念；形式演绎方法。重点：逻辑联结词的意义，命题公式的主吸取范式和主合取范式，推理证明的方法。难点：命题公式主吸取范式和主合取范式的求法，推理证明的间接证法。第二章：谓词逻辑8学时基本要求：了解以谓词逻辑为工具，将命题符号化的方法；理解用谓词、量词、逻辑联结词描述一个简单命题，公式的递归定义，用解释的方法证明等价式和蕴涵式；掌握个体词、个体域、谓词、量词的概念和使用，原子、公式、解释的概念，公式在解释下的真值，求公式的前束范式。重点：谓词公式等价的证明方法；谓词演算的推理证明方法。难点：谓词演算的推理证明方法。第三章：集合的概念4学时基本要求：了解幂集的表示方法、集合的特征函数；理解集合的运算概念、文氏图；掌握集合的运算性质、包含排斥原理和集合相等的证明方法。重点：集合的运算及其性质。难点：幂集的概念、包含排斥原理、集合的特征函数、证明集合相等的方法。第四章：二元关系10学时基本要求：了解商集、极大（小）元、最大（小）元、确界的概念；理解关系矩阵与关系图；掌握序偶与笛卡尔积的概念、关系的概念、关系的性质、关系闭包的概念与构造算法、等价关系与偏序关系。重点：关系的性质及其判别，关系矩阵与关系图，关系的复合运算及其性质，等价关系及集合的划分，偏序集的概念。难点：是关系闭包的构造算法，集合的分类方法，哈斯图的画法，与偏序关系有关的确界概念。第五章：映射与集合的基数4学时基本要求：要求了解映射的应用；理解单射、满射、双射的概念，复合映射与逆映射的概念；掌握映射的概念。难点：是复合映射与逆映射的概念及其性质，映射与一般关系、逆映射与逆关系的区别。第六章：图论14学时基本要求：熟记图的定义和各个基本概念及图的表示方法；理解并熟记欧拉图和哈米尔顿图的定义，欧拉图的判定定理以及对哈米尔顿图的直观判别法；理解并熟记树、生成树和最小生成树的定义；掌握并熟记树的性质，构造生成树和最小生成树的方法；熟记二部图的定义，并能对给定的图进行判别；掌握平面图的定义，掌握对图的平面性的三种判别方法；能证明或计算图和树中结点与边之间的一些数量关系。重点：图的定义和图的表示方法，对各种特殊图（欧拉图、哈密尔顿图、二部图、平面图）的定义，相关的性质以及判别方法要重点掌握。难点：计算图和树中结点与边之间的一些数量关系。第七章：代数系统6学时基本要求：了解代数系统的结构、特殊的代数系统群、环、域以及格的概念。本章教学内容有：重点：利用定义判断群。难点：群的判断。三、实践环节或相关课程 实践总学时：0学时四、课时分配序号章节内容理论环节时数实验时数其他环节1一命题逻辑102二谓词逻辑83三集合的概念44四二元关系105五函数与集合的基数45六图论146七代数系统6合计56总学分3.5总学时56五、建议教材与教学参考书序号书名编者出版社版本1离散数学屈婉玲,耿素云,张