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

《离散数学(第三版)》方世昌的期末复习知识点总结.docx《离散数学》期末复习提要
《离散数学》是中央电大“数学与数学应用专业”（本科）的一门选修课。该课程使 用新的教学大纲，在原有离散数学课程的基础上削减了教学内容（主要是群与环、格与布 尔代数这两章及图论的后三节内容），使用的教材为中央电大出方法。
3、 理解关系的性质(自反性、对称性、反对称性、传递性)，掌握其判别方法(定义、矩 阵、图)。
4、 掌握求关系的闭包(自反闭包、对称闭包、传递闭包)的方法。
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上总结的规律。这其中对传递性的 判定，难度稍大一点，这里要提及两点：一是不破坏传递性定义，可认为具有传递性。如 空关系具有传递性，同时空关系具有对称性与反对称性，但是不具有自反性。另一点是介 绍一种判定传递性的“跟踪法”，即若（知。2）cR （。2，。3）右人，……，（«,_!，7?, 则（＜?［, a,） e 7? o 如若（a,b） e R, （b,a） c R，则有（a,a） e R ,且（b,b） e R o
3、 关系的闭包
在理解掌握关系闭包概念的基础上，主要掌握闭包的求法。关键是熟记三个定理的结
n
论：定理 2, 「（R）=R5a；定理 3， s（R）=RuR L 定理 4,推论 .
i=\
4、 半序关系及半序集中特殊元素的确定
理解与掌握半序关系与半序集概念的关键是哈斯图。哈斯图画法掌握了，对于确定任 一子集的最大（小）元，极大（小）元也就容易了。这里要注意，最大（小）元与极大（小） 元只能在子集内确定，而上界与下界可在子集之外的全集中确定，最小上界为所有上界中 最小者，最小上界再小也不小于子集中的任一元素，可以与某一元素相等，最大下界也同 样。
5、 映射的概念与映射种类的判定
映射的种类主要指单射、满射、双射与非单非满射。判定的方法除定义外，可借助于 关系图，而实数集的子集上的映射也可以利用直角坐标系表示进行，尤其是对各种初等函 数。
［例题分析］
例1设集合A = {a,b,c,d},判定下列关系，哪些是自反的，对称的，反对称的和传递的：
氏={(。, a),(b, a)} R2 = {(a, a),(b, c), (d, a)} R3 = {(c, d)} R4 = {(a, a,\(b,"), (c, c)} 夫5 ={(a,c),(",d)}
解：均不是自反的;R4是对称的;R1 ,R2 ,R3,R4,R5是反对称的;R1 ,R2 ,R3,R4,R5是传递的。
例2设集合A = {1,2,3,4,5}, A上的二元关系R为
R = {（1,1）,（2,2）,（3,3）,（3,4）,（4,4）,（5,3）,（5,4）,（5,5）}
（1 ）写出R的关系矩阵，画出R的关系图;
（2 ）证明R是A上的半序关系，画出其哈斯图;
（3）若B^A,且3 = {2,3,4,5},求B的最大元，最小元，极大元，极小元，最小上界
和最大下界。
解（1）R的关系矩阵为
Mr
(1
0
0
0
〔0
0
0
1
0
1
0
0
1
1
1
R的关系图略
（2）因为R是自反的，反对称的和传递的，所以R是A上的半序关系o （A,R）为半序集, （A,R）的哈斯图如下
（3）当B = （2,3,4,5） , B的极大元为2, 4；极小元为2, 5： B无最大元与最小元；B
也无上界与下界，更无最小上界与最大下界。
第三章命题逻辑
［复习知识点］
1、 命题与联结词（否定、析取、合取、蕴涵、等价），复合命题
2、 命题公式与解释，真值表，公式分类（恒真、恒假、可满足），公式的等价
3、 析取范式、合取范式，极小（大）项，主析取范式、主合取范式
4、 公式类别的判别方法（真值表法、等值演算法、主析取/合取范式