- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
计算机应用技术研究所
4
Байду номын сангаас
关系的基本性质
☺ 关系的自反与反自反 关系的对称与反对称 关系的传递性 关系性质的判定
自反与反自反
2020/3/7
例题
2020/3/7
例题
2020/3/7
例题
2020/3/7
例题
2020/3/7
例题
2020/3/7
小结
2020/3/7
关系性质的判断
2020/3/7
关系性质的判断
2020/3/7
关系性质的判断
2020/3/7
关系性质的判定
2020/3/7
关系性质的判定
2020/3/7
关系性质的判定
2020/3/7
例题
【例题】试举例说明下列事实： R和S是反自反、反对称和传递的，但是R∘S不一定具有反自反性和反
离散数学
Discrete Mathematics
汪荣贵 教授
合肥工业大学计算机与信息学院
20210/3/7
计算机应用技术研究所
1
第5章 关系模型与理论 (下)
2020/3/7
计算机应用技术研究所
2
本章学习内容
3
关系的基本性质
4
关系的性质闭包
5
关系模型的应用
2020/3/7
关系的基本性质
2020/3/7
2020/3/7
例题
【解】图b的关系是反自反的，因为每个顶点都没有自环 ；是反对称的，因为两条边都是单向边；是传递的，因为 不存在顶a,b,c∈{1,2,3}，使得a到b有边，b到c有边，但 a到c没有边. 同理可知，图c的关系是自反的、反对称的 ，但不是传递的.
2020/3/7
例题
【例题】设A={1,2,3,4,6,12}，A上的整除关系记为R，则R是自反的、 对称的、反自反的、反对称的、传递的吗？画出A中关系R的关系. 【解】关系R是A中的关系，所以它的关系图如下图所示. 从图中容易看出，R是自反、反对称和传递的，不是反自反的，也不是 对称的. 容易验证，一般正整数集合中整除关系都具有自反性、反对称性、传递 性，而不具有反自反性和对称性.
关系的基本性质
关系的自反与反自反 ☺ 关系的对称与反对称 关系的传递性 关系性质的判定
对称与反对称
2020/3/7
例题
2020/3/7
例题
2020/3/7
例题
2020/3/7
例题
【例题】试判断下列关系是否具有对称性和反对称性. （1）对任意集合A，其幂集Q（A）上的包含关系； （2）整数集Z上的整除关系. 【分析】（1）当两个集合不相等时，如果有其中一个集合包 含于另一个，则反过来必然没有包含关系，故有反对称性但没 有对称性；（2）当整数a和整数b不等时，若a整除b，则必有b 不能整除a，故有反对称性但没有对称性. 【解】对任意集合A，其幂集P(A)上的包含关系具有反对称性 ；整数集Z上的整除关系具有反对称性.
对称性；R∪S不一定具有反对称性和传递性； 【解】设A={1,2,3}，R和S是定义在A上的两个关系： R={〈1,2〉,〈2,3〉,〈1,3〉}； S={〈3,2〉,〈3,1〉,〈2,1〉} 显然R，S都是反自反的、反对称和传递的. 但 R∘S={〈1,1〉,〈2,2〉,〈2,1〉,〈1,2〉}不具有反自反性和反对称性； R∪S={〈1,2〉,〈2,3〉,〈1,3〉,〈3,2〉,〈3,1〉,〈2,1〉}不具有反对称性和传递性.
2020/3/7
小结
2020/3/7
关系的基本性质
关系的自反与反自反 关系的对称与反对称 ☺ 关系的传递性 关系性质的判定
传递性的定义
2020/3/7
例题
2020/3/7
例题
2020/3/7
例题
2020/3/7
小结
2020/3/7
关系的基本性质
关系的自反与反自反 关系的对称与反对称 关系的传递性 ☺ 关系性质的判定
2020/3/7
例题
【例题】试判断下图关系的性质 【解】图a的关系在集合{1,2,3}上是对称的，因为结点1与2，1与3之间的 有向边是成对出现且方向相反；因为有的点有自环，有的点没有自环，故 不是自反的，也不是反自反的；因为〈2,1〉∈R，〈1,3〉∈R，若是传递关系， 必有〈2,3〉∈R. 然而结点2没有一条指向结点3的有向边，故不是传递的；因 为〈2,1〉∈R且〈1,2〉∈R，但 1≠2，故不是反对称的.
2020/3/7
例题
【例题】试举例说明下列事实： R和S是自反、对称和传递的，但是R∘S不一定具有对称性和传递性；R-S不一
定具有自反性和传递性. 【解】设A={1,2,3}，R和S是定义在A上的两个关系： R={〈1,1〉,〈2,2〉,〈3,3〉,〈1,2〉,〈2,1〉}； S={〈1,1〉,〈2,2〉,〈3,2〉,〈2,3〉}显然R，S都是 自反、对称和传递的. 但是： R∘S={〈1,1〉,〈2,2〉,〈3,3〉,〈2,3〉,〈3,2〉〈1,2〉,〈2,1〉,〈1,3〉}不具有对称性和传递性； R-S={〈1,2〉,〈2,1〉}不具有自反性和传递性.
关系闭包的概念
2020/3/7
构造方法
2020/3/7
例题
2020/3/7
例题
2020/3/7
构造方法
2020/3/7
例题
2020/3/7
例题
2020/3/7
例题
【例题】设集合A={1,2,3,4}，R是A上的关系，且有： R={〈1,2〉,〈2,2〉,〈3,4〉}. 试画出R的关系图，并根据关系图求出 r(R)，s(R)和t(R). 【解】R的关系图如左图所示. 从关系图上看，如果每个结点都 有自环，那么该关系就具有自反性. 故可在R的关系图的结点1 ，3和4处添加自环，即得到r(R)的关系图，如右图所示，故有 ：r(R)={〈1,2〉,〈2,2〉,〈2,3〉,〈3,4〉,〈1,1〉,〈3,3〉,〈4,4〉}.
2020/3/7
例题
2020/3/7
例题
2020/3/7
本节内容到此结束
2020/3/7
本章学习内容
3
关系的基本性质
4
关系的性质闭包
5
关系模型的应用
2020/3/7
关系的性质闭包
2020/3/7
计算机应用技术研究所
42
关系的闭包运算
☺ 关系闭包的概念 传递闭包的构造 关系闭包的性质
