《离散数学》教学大纲（专科）《离散数学》教学大纲（专科）说明一．课程的性质本课程是为计算机科学与技术专业专科开设的专业基础课。

离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程，是学习专业理论不可少的数学工具。

离散数学是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个和可数个元素，充分描述了计算机科学离散性的特点。

在计算机科学中，离散数学与数据结构、操作系统、逻辑设计、算法分析、编译原理、人工智能、系统结构等课程联系紧密。

学习离散数学不仅为后续课程作必要的理论准备，而且其课程内容中所提供的一些把科学理论应用于实践的范例，可以培养学生逐步增强如何实施“科学理论---技术---生产力”转化的观念和方法，提高学生在知识经济时代中的适应能力。

同时本课程在培养学生的创新能力，提高学生的科研素质方面都有着重要作用。

二．课程的教学目的和要求在计算机科学教学中，离散数学主要是为专业服务的基础理论课，是一门概念较多、理论性较强，应用性较广的课程。

本课程主要教授数理逻辑、集合论、代数系统、图论方面的基础知识，是计算机科学与技术教学中一些后续课程学习的基础和工具。

通过本课程的学习，要使学生掌握离散数学的基本概念和基本原理，以现代数学的观点和方法，初步掌握处理离散结构所必须的描述工具和方法。

同时，也要培养学生抽象思维、慎密概括、逻辑推理的能力，从而使学生具有良好的开拓专业理论的素质和使用所学知识，分析和解决实际问题的能力。

三．课程的主要教学内容1.集合论：集合的基本概念，集合的运算，包含排斥原理。

2.二元关系：集合的笛卡尔乘积，关系的定义，关系的表示法，特殊关系，复合关系和逆关系，关系的闭包运算。

3. 函数：函数的定义，特殊函数，复合函数和逆函数。

4. 代数结构：代数系统，特殊运算和特殊元素；同构概念，半群、群；子群，循环群，置换群；陪集和拉格朗日定理。

环、域；格与布尔代数。

5．图论：图的基本概念，通路、回路及图的连通性，赋权图的最短通路，图与矩阵表示、欧拉图与哈密顿图、平面图与二部图、无向树，有向树及其应用。

6. 命题逻辑: 命题与联结词、逻辑等价和永真蕴含式；推理理论，范式。

7. 谓词逻辑: 谓词与量词，谓词公式与变元约束，谓词演算的等价式与永真蕴含式；前束范式；谓词逻辑的推理理论。

四．本课程的知识范围及与相关课程的关系本课程包含数理逻辑、集合论、代数系统、图论等方面的基本内容，先修课程为：高等数学、线性代数；后续课程为：数据结构、数字电路、人工智能等。

五．课程的教学要求层次教学要求中，有关定义、定理、性质、特征等内容要求，由低到高分“知道、了解、理解”三个层次；有关计算、解法、公式、法则等方法的内容要求，由低到高分“会、掌握、熟练掌握”三个层次。

六．教学时数安排本课程可安排在一年级第二学期教学。

二年制脱产为72学时；三年制函授共120个学时，其中面授30学时，自学90学时。

学时分配如下表：对于两年制脱产学员，强调听课，复习，完成作业等教学环节。

对于三年制函授学员，强调自主学习，自己阅读教材，完成一定量的作业。

《离散数学》是理论性较强的学科，由于本教材作者在编写过程中，充分考虑到使用对象的现有水平及其学习特点，对于传统的离散数学的内容在取舍和编排上做了精心的处理。

淡化了某些理论性的证明，而注重介绍理论在实际中的应用。

因此学习中必须重视理论和方法的应用，通过做练习题来加深对概念的理解和掌握，熟悉各种公式的运用，从而达到消化、掌握所学知识的目的。

由此可知，独立完成作业是学好本课程的重要手段。

教学内容一．集合（一）教学内容：1．集合的概念与表示法，集合间的关系和特殊集合，幂集。

2．集合代数。

3．包含排斥原理。

（二）教学目的集合论是现代数学各学科的基础。

本章介绍集合论的基础知识，以作为后续相关课程学习的工具。

通过本章学习，要求学生熟悉集合的概念、性质及其运算。

（三）教学知识点及基本要求1．掌握集合的两种表示法；2．理解集合的包含与相等，幂集等基本概念；3．熟练掌握集合的交、并、补、差、对称差运算，并通过文氏图加深理解。

4．会求集合的幂集；5．理解包含排斥原理，掌握其简单应用。

【重点】集合概念、集合的运算，包含排斥原理。

二．二元关系（一）教学内容：1．集合中的笛卡尔乘积；2．二元关系的定义；3．关系的三种表示法；4．关系的基本类型（自反、反自反、对称、反对称、传递等关系）及判别方法；5．等价关系与划分：等价关系、等价类和划分，商集。

6．相容关系：相容关系，最大相容类和完全覆盖。

7．偏序关系：偏序关系和全序关系，哈斯图，极大（极小）元素，最大（最小）元素，上界（下界），上（下）确界。

8．复合关系与逆关系；9．关系上的闭包运算。

（二）教学目的本章主要要求领会集合上二元关系的概念、性质，以及集合上的特殊关系：等价关系，相容关系，偏序关系的概念。

（三）教学知识点及基本要求1．理解二元关系的概念及其性质；2．掌握二元关系的表格表示，关系矩阵和关系图的画法；3．掌握关系的自反、反自反、对称、反对称、传递等性质；4．理解关系闭包概念，会求关系的自反闭包，对称闭包，传递闭包。

5．了解相容关系与极大相容性分块；6．理解等价关系、等价类和商集的概念，会求等价类，会判别等价关系；7．理解偏序关系的有关概念，会画偏序关系的哈斯图；了解极大（极小）元素，最大（最小）元素，上界（下界），上（下）确界的定义。

8. 会求复合关系与逆关系；【重点】关系概念及性质，等价关系和偏序关系，复合关系与逆关系。

【难点】二元关系概念，等价类和商集的概念，极大（极小）元素，最大（最小）元素，上界（下界），上（下）确界的概念。

三．函数（一）教学内容：1.函数的定义;2.特殊函数;3.复合函数与逆函数。

(二)教学知识点及基本要求1.掌握函数的概念；2.掌握满射，单射，双射函数的概念，并会判别之。

3.理解复合函数的概念。

四．代数结构（一）教学内容：1.代数系统：二元运算、代数系统概念；2.特殊运算和特殊元素：代数系统常见的性质(结合律、交换律、分配律，单位元素、逆元素、零元素)；3.代数系统的同构;4.半群、独异点；5.群的定义与性质；6.子群;7.循环群8.置换群；9.陪集及拉格郎日定理;10.环和域；（二）教学目的：代数系统是由集合上定义的若干运算而组成的系统，是一类特殊的数学结构。

人们研究、考察现实世界的事物、现象，往往要借助某些数学工具，因此，针对某个具体问题，需要选用适宜的数学结构去进行较为确切的描述。

代数系统的概念和方法则是计算机科学研究中使用的主要工具之一。

通过本章学习，要求学生熟悉代数系统的概念、性质及其运算；领会群、环、域的概念、性质以及两个代数系统间的同构与同态关系。

（三）教学知识点及基本要求：1．知道代数系统、代数系统的性质、以及代数系统的特殊元素；2．了解同构概念；3．掌握二元运算的性质：结合律、交换律、分配律、幂等律、吸收律。

4．掌握求集合上代数运算的单位元和逆元的方法。

5．了解半群、独异点、群和交换群的概念，掌握半群、独异点和群的性质及其判别法；6．了解交换群、置换群和循环群的概念，掌握其判别方法。

7．知道子群、子群的陪集定义，会求子群的陪集，理解拉格郎日定理，8．了解环、域的概念。

【重点】代数系统及其性质，群的概念，交换群和循环群。

【难点】判别群的同构，置换群和循环群的概念和判别方法。

五．图论（一）教学内容：1.图的基本概念，图的同构;2.通路和赋权图的最短通路：通路和回路，赋权图的最短通路的Dijkstra算法。

3.图与矩阵：图的邻接矩阵，可达性矩阵；4.欧拉图；5.哈密顿图；6.中国邮路问题和旅行售货员问题；7.二部图：二部图及其判别，最大对集的匈牙利算法。

8.平面图；平面图的概念，欧拉公式，平面图和非平面图的判别。

9.无向树：树的定义，树的性质；10.有向树：有向树的基本概念，前缀码与最优树，搜索树。

（二）教学目的：本章仅介绍图的一些基本概念和定义，以及一些典型的应用实例。

为在以后的计算机相关学科学习、研究时，以图论的基本知识为工具。

通过本章学习，要求学生：熟悉图的基本概念及其性质；掌握图的矩阵表示，树的概念及其性质；了解图、树的典型实例及其应用。

（三）教学知识点及基本要求：1.理解有关图的基本概念，掌握图的顶点和边的关系定理，理解图的同构。

2.理解简单通（回）路、基本通（回）路的概念，理解图的连通性，掌握其判别方法;会求赋权图的最短通路。

3.掌握图的矩阵表示方法，会通过可达性矩阵求图的强分支。

4.理解欧拉通路、回路的概念，掌握判别欧拉图的相关定理和应用。

5.理解哈密顿通路、回路的概念，并了解相关定理和应用。

6.了解中国邮路问题和旅行售货员问题，知道旅行售货员问题的最邻近算法。

7.掌握二部图及其判别，掌握最大对集的匈牙利算法。

8．掌握平面图的欧拉公式，了解平面图和非平面图判别的相关定理。

9．理解树及其性质，会求最小生成树；8.知道有向树的基本概念，掌握求最优树的哈夫曼算法。

【重点】图的概念，顶点度数和边关系的定理，图的矩阵表示；欧拉图和哈密顿图；树及应用。

【难点】判别图的同构，利用图的矩阵判别图的性质和连通性，非平面图的判别。

六．命题逻辑（一）教学内容：1.命题与联结词，复合命题与命题公式；2.真值表与逻辑等价：命题公式的真值表和常用的逻辑等价公式。

3.永真蕴含式概念和常用的永真蕴含公式。

4．命题演算的推理理论。

（二）教学目的：数理逻辑是用数学方法来研究推理规律的方法。

本章和下一章介绍数理逻辑最基本的内容：命题逻辑和谓词逻辑，是后续相关课程学习的工具。

通过这两章学习，要求学生熟悉真值表及其应用，熟悉命题和谓词的概念；熟悉命题公式和谓词公式的演算；掌握命题的公式符号化应用；领会推理理论及其规则；掌握推理演算方法。

（三）教学知识点及基本要求1.理解命题的概念，会判断语句是否命题，会将命题符号化；2.掌握六个联结词的真值表，掌握命题公式真值表的构造法；3.掌握命题的常用逻辑等价公式，熟练掌握对命题公式进行逻辑等价变换的方法。

4.掌握命题演算的永真蕴含式以及命题逻辑的推理演算方法。

【重点】命题符号化，命题公式真值表的构造法，对命题公式进行逻辑等价变换，命题逻辑的推理演算。

【难点】命题符号化，命题逻辑的推理演算（直接证法，反证法和CP规则）七．谓词逻辑（一）教学内容：1．谓词与个体，量词；2．谓词公式、自由变元和约束变元;3．谓词演算的等价式和永真蕴含式；4.前束范式；5.谓词演算的推理理论。

（二）教学知识点及基本要求1．理解谓词、量词、变元、个体域等概念；掌握用谓词、量词、联结词构造谓词公式的方法；2．掌握谓词公式在给定解释下求真值的方法。

3．会将谓词逻辑化为前束范式；4．会将谓词逻辑作为工具，将命题符号化，并能用推理规则进行逻辑证明。