《离散数学》教学大纲08版(56学时).doc

离散数学教学大纲课程编号：课程性质：专业基础课 先修课程：高等数学，线性代数总学时数：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集合的概念42二元关系103函数与集合的基数44命题逻辑105谓词逻辑8代数系统6图论14小 计56五、课程有关说明1、本课程与其它课程的关系本课程需要高等数学和线性代数的支持，高等数学中函数等概念有助于本课程的学习，线性代数中矩阵的知识在本课程中有重要应用。学习本课程应先修高等数学和线性代数。2、重点、难点的教学方式本课程的内容多且抽象，各内容之间彼此独立，教学过程中注意基本概念的介绍，通过例题和作业引导学生加深对基本概念的理解和基本算法的掌握。3、考核方式建议平时成绩占20%（作业、出勤等），考试成绩占80%，考试采取闭