《离散数学(第三版)》方世昌-的期末复习知识点总结.doc

《离散数学(第三版)》方世昌-的期末复习知识点总结
LT
1
3
《离散数学》期末复习提要
《离散数学》是中央电大“数学与数学应用专业”（本科）的一门选修课。该课程使用新的教学大纲，在原有离散数学课程的基础上削减了教学内容（主要是群与环、格与布尔代数这两章及图论的后三节内容），使用的教材为中央电大出版的《离散数学》（刘叙华等编）和《离散数学学习指导书》（虞恩蔚等编）。
离散数学主要研究离散量结构及相互关系，使学生得到良好的数学训练，提高学生抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。其先修课程为：高等数学、线性代数；后续课程为：数据结构、数据库、操作系统、计算机网络等。
课程的主要内容
集合论部分（集合的基本概念和运算、关系及其性质）；
数理逻辑部分（命题逻辑、谓词逻辑）；
图论部分（图的基本概念、树及其性质）。
学习建议
离散数学是理论性较强的学科，学习离散数学的关键是对离散数学（集合论、数理逻辑和图论）有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。
1
3
教学要求的层次
各章教学要求的层次为了解、理解和掌握。了解即能正确判别有关概念和方法；理解是能正确表达有关概念和方法的含义；掌握是在理解的基础上加以灵活应用。
一、各章复习要求与重点
第一章 集 合
[复习知识点]
1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集
2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、 De Morgan律等），文氏（Venn）图
3、序偶与迪卡尔积
本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明
[复习要求]
1
4
1
5
[复习知识点]
1、关系、关系矩阵与关系图
2、复合关系与逆关系
3、关系的性质（自反性、对称性、反对称性、传递性）
4、关系的闭包（自反闭包、对称闭包、传递闭包）
5、等价关系与等价类
6、偏序关系与哈斯图（Hasse）、极大/小元、最大/小元、上/下界、最小上界、最大下界
7、函数及其性质（单射、满射、双射）
8、复合函数与反函数
本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、半序关系、映射的概念
[复习要求]
1、理解关系的概念：二元关系、空关系、全关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。
2、掌握求复合关系与逆关系的方法。
3、理解关系的性质（自反性、对称性、反对称性、传递性），掌握其判别方法（定义、矩阵、图）。
4、掌握求关系的闭包 （自反闭包、对称闭包、传递闭包）的方法。
1
6
5、理解等价关系和偏序关系的概念，掌握等价类的求法和偏序关系做哈斯图的方法，极大/小元、最大/小元、上/下界、最小上界、最大下界的求法。
6、理解函数概念：函数、函数相等、复合函数和反函数。
7、理解单射、满射、双射等概念，掌握其判别方法。
[本章重点习题]
P25，1；P32~33，4，8，10； P43，2，3，5； P51~52，5，6； P59，1，2； P64，3； P74~75，2，4，6，7； P81，5，7； P86，1，2。
[疑难解析]
1、关系的概念
　　关系的概念是第二章全章的基础，又是第一章集合概念的应用。因此，学生应该真正理解并熟练掌握二元关系的概念及关系矩阵、关系图表示。
2、关系的性质及其判定
　　关系的性质既是对关系概念的加深理解与掌握，又是关系的闭包、等价关系、半序关系的基础。对于四种性质的判定，可以依据教材中P49上总结的规律。这其中对传递性的判定，难度稍大一点，这里要提及两点：一是不破坏传递性定义，可认为具有传递性。如空关系具有传递性，同时空关系具有对称性与反对称性，但是不具有自反性。另一点是介绍一种判定传递性的
1
8
“跟踪法”，即若，则。如若，则有，且。
３、关系的闭包
在理解掌握关系闭包概念的基础上，主要掌握闭包的求法。关键是熟记三个定理的结论：定理2， ；定理3， ；定理4，推论 。
４、半序关系及半序集中特殊元素的确定
理解与掌握半序关系与半序集概念的关键是哈斯图。哈斯图画法掌握了，对于确定任一子集的最大（小）元，极大（小）元也就容易了。这里要注意，最大（小）元与极大（小）元只能在子集内确定，而上界与下界可在子集之外的全集中确定，最小上界为所有上界中最小者，最小上界再小也不小于子集中的任一元素，可以与某一元素相等，最大下界也