离散数学教学大纲.doc

《离散数学》课程教学大纲

课程编号：
总学时数：80
总学分数：5
课程性质：专业必修课
适用专业：信息与计算科学

一、课程的任务和基本要求：
离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支，其研究对象一般是有限个或可数个元素。离散数学是程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。
本课程主要介绍集合论、代数系统、图论以及数理逻辑四个部分。通过本课程的学习，使学生具有现代数学的观点和方法，并初步掌握处理离散问题所必须的描述工具和方法，培养学生抽象思维能力和分析问题、解决问题的能力，并为学好后继专业课打好基础。

二、基本内容和要求：
第一章 集合论初步
1．集合的基本概念，集合的运算，集合的图解表示，集合的基本定律。
2．幂集、笛卡儿乘积。
本章教学要求：
要求掌握集合的基本概念、集合的运算及其基本定律，如集合的包含与相等、幂集等。会做笛卡儿积的运算，能证明集合恒等式，学会用集合的观点来描述和解决问题。
第二章 关系
1．关系的基本概念、有关定义及图的表示方法。
2．关系的运算，复合关系与逆关系的定义及有关定理。
3．关系的五种重要性质的定义及判定。
4．关系的三种闭包的定义和运算及有关定理。
5．三种重要关系：偏序关系的定义，哈斯图，极大（小）元、最大（小）元、上（下）界、上（下）确界及有关定理；相容关系的定义，极大相容性分块，完全覆盖的有关定理；等价关系、等价类、划分的的定义，以及三者之间关系的有关定理，商集的概念。
本章教学要求：
熟练掌握关系的有关概念及基本性质并能进行相应的运算，掌握关系上的闭包运算，能够通过关系的图的表示法进行关系性质的判定和相应的运算。弄清等价关系、相容关系、偏序关系三者之间的联系，并会对各种关系进行判定及表示。掌握关系的闭包的定义及计算。掌握偏序关系的定义，能够作出偏序集的哈斯图，指出偏序集的最大（小）元，极大（小）元，上（下）界，上（下）确界。会求等价类及商集，搞清等价关系、相容关系与覆盖和划分的联系。
第三章 函数
1．函数的基本概念，映射、单射、满射、双射的定义。
2．反函数和复合函数的定义及有关定理。
本章教学要求：
理解函数的概念，并掌握函数的性质，掌握映射、单射、满射、双射的定义并能进行相应的运算。弄清关系与映射之间的联系。
第四章 有限集与无限集
1．有限集与无限集的基本概念，基数的概念及有关定理。
2．无限集的性质，等势的概念，可列集的定义及有关定理。
本章教学要求：
掌握集合的等势、基数概念，掌握有关集合基数的一些结论，加深对于无限集的理解，了解常见的可列集些，会进行集合间基数的比较。
第五章 代数系统基础
1．代数系统的基本概念和常见的一些性质(结合律、交换律、分配律 ，单位元素、逆元素、零元素)。
2．代数系统的同构与同态及相关定理。
3．自然同态、同余关系及商代数。
本章教学要求：
掌握代数系统的基本概念和性质。掌握代数系统之间的同构关系和同态关系，并能够证明两个代数系统是否同构或同态。
第六章 群论
1．半群的基本概念与性质：半群，子半群，可换半群、单元半群、循环单元半群的定义及相关定理。
2．群的基本概念与性质：群的定义和性质，子群的概念，群同构，变换群的相关性质，循环群的定义及相关性质。
3．子群：有关定理，子群的陪集及拉格朗日定理，正规子群与同态。
本章教学要求：
理解半群和群的概念，熟练掌握其性质及其判别法，掌握子群、子群的陪集定义，理解拉格郎日定理，会应用定义、性质证明相关的结论。
第七章 其他代数系统
1．环、理想、整环和域：环的基本概念和性质，理想、整环和域的概念，整环和域的性质。
2．格与布尔代数的基本概念与性质
　　本章教学要求：
掌握环、整环、域和格的基本概念与性质。了解有界格、有补格、分配格和有补的分配格等几种特殊性质的格及布尔代数的基本概念与性质。
第八章 图论原理
1．图的基本概念：图和子图的定义，图的同构，图中结点的次数。
2．通路与回路：通路与回路，基本通路与基本回路，图的连通性。
3．欧拉图与汉密尔顿图：欧拉通路、欧拉回路、汉密尔顿通路、汉密尔顿回路、欧拉图和汉密尔顿图的定义及有关判定定理。
4．图的矩阵表示：图的矩阵表示方法，邻接矩阵，可达矩阵。
本章教学要求：
掌握图的基本概念和性质及图的矩阵表示。掌握图中通路和回路的基本概念和应用，在此基础上掌握图中的可达性和连通性的概念和求解方法。
第九章 常用图
1．树：树的定义及性质，有向树、无向树的定义，二元树的定义，生成树的定义及有关定理，最小生成树的定义及求法。
2．平面图和两步图：平面图、欧拉公式，判别平面图的库拉托夫斯基定理，两步图的定义和判别定理。
本章教学要求：
理解树及等价定义，掌握根树、二元树的定义及有关定理，会求最小生成树。掌握平面图的欧拉公式，会应用平面图和两步图的相关定理。
第十章 命题逻辑
1．命题及命题联结词：命题的定义、表示以及命题常元与变元，否定、合取、析取、蕴含、等价五种连接词的意义，将日常用语翻译成命题。
2．命题变元与命题公式：命题变元与命题公式的定义，指派，真值表。
3．重言式、矛盾式的定义，命题逻辑的基本等式及证明，对偶定理。
4．命题逻辑的基本蕴含式及推理规则。
5．范式：析取范式、合取范式、特异析取范式、特异合取范式的定义、求法及应用，最大项、最小项的定义和相关结论。
本章教学要求：
掌握命题、命题公式以及五个联结词的定义，熟记命题逻辑的有关等价式及蕴含式并会应用其证明其他等价式及蕴含式，会求命题公式的范式及主范式。
第十一章 谓词逻辑
1．谓词逻辑的基本概念：谓词、个体词以及个体常元与变元的定义，个体域，存在量词、全称量词的意义及应用，特性谓词和全总个体域的定义，函数的概念。
2．谓词逻辑公式的定义。
3．指导变元、作用域、自由变元与约束变元的定义，约束变元的换名规则，自由变元的代入规则。
4．谓词演算的基本等式及常用的蕴含永真公式，对偶定理。
5．前束范式和斯柯林范式的定义及求法。
本章教学要求：
掌握谓词与谓词逻辑公式的定义，熟练掌握量词的应用和谓词演算的基本等价式及蕴含式，会求谓词公式的前束范式。
第十二章 数理逻辑的公理化理论
1．命题演算的公理系统与命题演算的推理理论。
2．谓词演算的公理系统与谓词演算的推理理论。
本章教学要求：
掌握命题逻辑的推理演算方法，会将谓词逻辑作为工具将命题符号化，并能用推理规则进行逻辑证明。

三、实践环节和要求：无

四、教学时数分配：

理论： 80 实验： 0 上机： 0 其它：0
教学内容
学时分配
教学内容
学时分配
第一章 集合论初步
4
第十章 命题逻辑
10
第二章 关系
10
第十一章 谓词逻辑
8
第三章 函数
2
第十二章 数理逻辑的公理化理论
6
第四章 有限集与无限集
2
机动
2
第五章 代数系统基础
6
考试复习
2
第六章 群论
8

第七章 其他代数系统
4

第八章 图论原理
8

第九章 常用图
8

合计
80

五、其它项目：无

六、有关说明：
1、教学和考核方式：
本课程属考试课，考试方式为闭卷。
2、习题：
以教材的课后习题为主，要求至少完成50%，并根据学生的具体情况适当补充部分习题。
3、能力培养要求：
通过教学使学生了解和掌握离散数学的基础理论和基本方法，培养学生严格的逻辑推理能力和抽象思维能力，以及解决计算机科学中的实际问题的能力，为进一步学习相关的内容打下基础。
4、与其它课程和教学环节的联系：
先修课程和教学环节：数学分析、高等代数
后续课程和教学环节：数据结构、计算机算法基础
平行开设课程和教学环节：无
5、教材和主要参考书目：
（1）教材：《离散数学》 徐洁磐编著 高等教育出版社 （第三版）
（2）主要参考书目：
① 《离散数学》 杜忠复等编著 高等教育出版社；
② 《离散数学》 耿素云等编著 清华大学出版社；