1、2022-8-5计算机应用技术研究所计算机应用技术研究所11离散数学离散数学Discrete Mathematics汪荣贵汪荣贵 教授教授合肥工业大学计算机与信息学院合肥工业大学计算机与信息学院2022-8-5计算机应用技术研究所计算机应用技术研究所2第第6 6章章 特殊关系模型特殊关系模型2022-8-52022-8-5 相容关系与元素聚类相容关系与元素聚类2 2 偏序关系与元素比较偏序关系与元素比较3 3 等价关系与元素分类等价关系与元素分类1 1 特殊关系的应用特殊关系的应用4 4&本章学习内容本章学习内容2022-8-5计算机应用技术研究所计算机应用技术研究所4等价关系与元素分类等价关
2、系与元素分类2022-8-5计算机应用技术研究所计算机应用技术研究所5&等价关系与元素分类等价关系与元素分类J 等价关系与等价类等价关系与等价类4 集合的划分与商集集合的划分与商集2022-8-52022-8-5&实实 例例2022-8-52022-8-5&等价关系的定义等价关系的定义【定义】假设A是任一给定的非空集合，R是A上的一个二元关系，如果R满足自反性、对称性和传递性，则称R是一个等价关系.此时，对于A中任意两个元素x和y，如果 x,y R，则称x与y等价，记为xy.从定义可知：关系R是等价关系当且仅当R同时具备自反性、对称性和传递性；关系R不是等价关系当且仅当R不具备自反性或对称性或
3、传递性。因此，等价关系的定义是判断关等价关系的一个很好判据。2022-8-52022-8-5&例例 题题【例题】根据定义判断下述关系哪些是等价关系、哪些不是，并说出理由.（1）集合上的恒等关系和完全关系；（2）某人群上的朋友关系；（3）合肥工业大学2016级新生集合上的同姓关系.【分析】根据等价关系的定义可知，满足自反性、对称性和传递性即为等价关系。【解】（1）集合上的恒等关系是自反的、对称的和传递的，因此是等价关系，完全关系也是自反的、对称的和传递的，因此也是等价关系；（2）朋友关系是自反和对称的但不是传递的，所以朋友关系不是等价关系；（3）全体新生的同姓关系是自反的、对称的和传递的，因此是
4、等价关系.2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题【例题】设集合A=1,2,3，关系R=1,2,1,3，现对R依次求自反、对称和传递三种闭包，共有如下6种不同顺序：rst(R),rts(R),str(R),srt(R),tsr(R),trs(R)问其中哪些关系是等价关系？【分析】利用闭包运算的性质可以大大化简计算的步骤，然后依次逐步画出对应的关系图，即可得出结果。【解】由于sr(R)=rs(R);tr(R)=rt(R);st(R)ts(R)，故有：tsr(R)=trs(R)=rts(R)；str(R)=srt(R)=rst(R)2022-8-52
5、022-8-5&例例 题题 依次画出关系R、tsr(R)和str(R)的关系图，如下图所示。其中(a)图表示最初的关系，(b)图表示第一种闭包运算后的关系图，(c)图表示第二种闭包运算后的关系图。由关系图可以看出，(b)满足自反性，传递性和对称性，因此第一种闭包运算后的关系为等价关系，而(c)图仅满足自反性和对称性，不满足传递性，因此第二种闭包运算后的关系不是等价关系。2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5&等价类等价类2022-8-52022-8-5&等价类的性质等价类的性质2022-8-52022-8-5&等
6、价类的性质等价类的性质2022-8-52022-8-5&等价类的性质等价类的性质2022-8-5计算机应用技术研究所计算机应用技术研究所18&等价关系与元素分类等价关系与元素分类4 等价关系与等价类等价关系与等价类J 集合的划分与商集集合的划分与商集&集合的划分集合的划分&例例 题题&例例 题题&例例 题题2022-8-52022-8-5&商集的概念商集的概念2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5&特殊等价关系特殊等价关系2022-8-52022-8-5&等价关系性质等价关系性质2022-8-52022-8-5&
7、等价关系性质等价关系性质2022-8-52022-8-5&等价关系性质等价关系性质2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5本节内容到此结束2022-8-52022-8-5 等价关系与元素分类等价关系与元素分类1
8、1 偏序关系与元素比较偏序关系与元素比较3 3 相容关系与元素聚类相容关系与元素聚类2 2 特殊关系的应用特殊关系的应用4 4&本章学习内容本章学习内容2022-8-5计算机应用技术研究所计算机应用技术研究所41相容关系与元素聚类相容关系与元素聚类2022-8-5计算机应用技术研究所计算机应用技术研究所42&相容关系与元素聚类相容关系与元素聚类J 相容关系与相容类相容关系与相容类4 集合的覆盖集合的覆盖2022-8-52022-8-5&相容关系的概念相容关系的概念2022-8-52022-8-5&例例 题题【例题例题】判断下列关系是否为相容关系：（1）人群中的朋友关系；（2）某校学生中的同班关
9、系；（3）集合上的包含关系.【分析】【分析】关系满足自反性和对称性即为相容关系.【解】【解】（1）朋友关系满足自反性和对称性，但不满足传递性，故是相容关系；(2)同班关系满足自反性、对称性和传递性，因此是相容关系，也是等价关系；（3）集合上的包含关系满足自反性，不满足对称性和传递性，因此不是相容关系.2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5&简化图与简化矩阵简化图与简化矩阵2022-8-52022-8-5&简化图与简化矩阵简化图
10、与简化矩阵2022-8-52022-8-5&相容类的概念相容类的概念2022-8-52022-8-5&例例 题题2022-8-52022-8-5&最大相容类最大相容类2022-8-52022-8-5&最大相容类最大相容类2022-8-52022-8-5&例例 题题2022-8-52022-8-5&最大相容类性质最大相容类性质2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所60&相容关系与元素聚类相容关系与元素聚类4 相容关系与相容类相容关系与相容类J 集合
11、的覆盖集合的覆盖2022-8-52022-8-5&集合的覆盖集合的覆盖2022-8-52022-8-5&例例 题题2022-8-52022-8-5&完全覆盖完全覆盖2022-8-52022-8-5&完全覆盖完全覆盖2022-8-52022-8-5&集合的覆盖集合的覆盖2022-8-52022-8-5&集合的覆盖集合的覆盖2022-8-52022-8-5&例题例题2022-8-52022-8-5本节内容到此结束2022-8-52022-8-5&本章学习内容本章学习内容 等价关系与元素分类等价关系与元素分类1 1 相容关系与元素聚类相容关系与元素聚类2 2 特殊关系的应用特殊关系的应用4 4 偏序
12、关系与元素比较偏序关系与元素比较3 32022-8-5计算机应用技术研究所计算机应用技术研究所70偏序关系与元素比较偏序关系与元素比较2022-8-52022-8-5&实实 例例2022-8-5计算机应用技术研究所计算机应用技术研究所72&偏序关系与元素比较偏序关系与元素比较J 偏序关系与哈斯图偏序关系与哈斯图4 偏序集的特殊元素偏序集的特殊元素4 全序与良序全序与良序2022-8-52022-8-5&偏序关系的概念偏序关系的概念2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5&拟序关系拟序关系2022-8-52022-8
13、-5&例例 题题2022-8-52022-8-5&哈斯图的画法哈斯图的画法2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例题例题2022-8-52022-8-5&例题例题2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所85&偏序关系偏序关系2022-8-52022-8-5&特殊元素特殊元素2022-8-52022-8-5&例例 题题【例题】确定下图的每个哈斯图表示的偏序集是否有最大元素和最小元素。2022-8-52022-8
14、-5&例例 题题2022-8-52022-8-5&最大元和最小元最大元和最小元2022-8-52022-8-5&最大元和最小元最大元和最小元2022-8-52022-8-5&极大元和极小元极大元和极小元2022-8-52022-8-5&极大元和极小元极大元和极小元2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5&上界与下界上界与下界2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5&最大元与最小元最大元与最小元
15、2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题其关系图和哈斯图如下图所示.2022-8-52022-8-5&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所103&偏序关系与元素比较偏序关系与元素比较2022-8-52022-8-5&全序关系的概念全序关系的概念2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5&全序关系全序关系2022-8-52022-8-5&全序关系全序关系2022-8-52022-8-5&良序关系的概念良序关系的概念2022-8-52022-8
16、-5&例例 题题2022-8-52022-8-5&总结总结2022-8-52022-8-5本节内容到此结束2022-8-52022-8-5&本章学习内容本章学习内容 等价关系与元素分类等价关系与元素分类1 1 相容关系与元素聚类相容关系与元素聚类2 2 偏序关系与元素比较偏序关系与元素比较3 3 特殊关系的应用特殊关系的应用4 42022-8-5计算机应用技术研究所计算机应用技术研究所114特殊关系的应用特殊关系的应用2022-8-5计算机应用技术研究所计算机应用技术研究所115&特殊关系的应用特殊关系的应用J 粗集定义问题粗集定义问题4 得分评判问题得分评判问题2022-8-52022-8-5&等价关系和粗糙集等价关系和粗糙集 2022-8-52022-8-5&例例 题题2022-8-52022-8-5&小小 结结2022-8-5计算机应用技术研究所计算机应用技术研究所119&特殊关系的应用特殊关系的应用4 粗集定义问题粗集定义问题J 得分评判问题得分评判问题2022-8-52022-8-5&实例实例2022-8-52022-8-5&实例实例2022-8-52022-8-5&实例实例2022-8-52022-8-5&实例实例2022-8-52022-8-5本章内容到此结束
