《第9节等价关系与偏序关系精选文档.ppt》由会员分享，可在线阅读，更多相关《第9节等价关系与偏序关系精选文档.ppt（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第9节等价关系与偏序关系1本讲稿第一页，共三十页 定义定义1 集合集合X上的二元关系上的二元关系R称为称为等价关系等价关系，如果，如果R同时同时具有以下三个性质：具有以下三个性质：例例1：集合集合X上的恒等关系是不是上的恒等关系是不是X上的等价关系？上的等价关系？1.R是自反的，即是自反的，即 x X，xRx;2.R是对称的，即如果是对称的，即如果xRy，则，则yRx;3.R是传递的，即如果是传递的，即如果xRy，yRz，则，则xRz。是是X上的等价关系。上的等价关系。1 等价关系等价关系2本讲稿第二页，共三十页等价关系实例等价关系实例例例2：考虑整数集考虑整数集Z上的模上的模n同余关系。同余
2、关系。例例4：设设f:XY，Ker(f)=(x,y)x,y X，且，且f(x)=f(y)。Ker(f)是是X上的等价关系上的等价关系。例例3：实数集上的实数集上的“”、“”、“”、“”、“”都不是都不是R上的等价关系。上的等价关系。是等价关系。是等价关系。3本讲稿第三页，共三十页例例5：设设 A=1,2,8,如下定义如下定义 A上的关系上的关系R：R=(x,y)|x,y Axy(mod 3)R 的关系图如下：的关系图如下：等价关系的关系图等价关系的关系图4本讲稿第四页，共三十页 定义定义2 设设R是是X上的一个等价关系，上的一个等价关系，x X，X的子集的子集Ex=y y X且且xRy称为称为
3、x关于关于R的的等价类等价类，或简记为，或简记为x的的等价类。等价类。x的等价类常记为的等价类常记为x，即，即x=yy X且且xRy。例例5：设设 A=1,2,8,如下定义如下定义 A上的关系上的关系R：R=(x,y)|x,y Axy(mod 3)等价类的定义等价类的定义A=1,2,8 上模上模 3 等价关系的等价类：等价关系的等价类：1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,65本讲稿第五页，共三十页等价类的性质等价类的性质(3)x,y X,如果如果(x,y)R,则则 xy=。定理定理1 设设R是非空集合是非空集合X上的等价关系上的等价关系,则则 (1)x X,x。(2)x
4、,y X,如果如果(x,y)R,则则 x=y。(4)，即所有等价类的并集就是，即所有等价类的并集就是X。6本讲稿第六页，共三十页 定义定义3 设设X为非空集合，为非空集合，X的若干个子集形成的集族的若干个子集形成的集族 称为称为X的一个的一个划分划分，如果，如果 具有性质：具有性质：集合的划分集合的划分 如果如果 是是X的一个划分，则当的一个划分，则当 =k时，时，被称为被称为X的一个的一个k-划分划分。(2)x,y ，若，若x y，则，则xy=;(1)；(3)。称称 中的元素为中的元素为X的的划分块划分块。7本讲稿第七页，共三十页例例6：设设Aa,b,c,d,给定给定 1,2,3,4,5,6
5、如如下：下：1=a,b,c,d，2=a,b,c,d 3=a,a,b,c,d，4=a,b,c 5=,a,b,c,d，6=a,a,b,c,d 1和和 2是是A的划分，其他都不是的划分，其他都不是A的划分。的划分。实实 例例8本讲稿第八页，共三十页 定理定理1 设设R是是X上的一个等价关系，则上的一个等价关系，则R的所有等价类的所有等价类的集合是的集合是X的一个划分。的一个划分。等价关系与集合的划分等价关系与集合的划分 定理定理2 设设 是集合是集合X的一个划分，令的一个划分，令 R=(x,y)|x,y Xx与与y在在 的同一划分块中的同一划分块中则则R是是X上的一个等价关系，并且上的一个等价关系，
6、并且 就是就是R的等价类之集。的等价类之集。注：注：由定理由定理1、2可得：可得：X上的等价关系与上的等价关系与X的划分是的划分是一一对应的，并且互相确定。一一对应的，并且互相确定。9本讲稿第九页，共三十页 定义定义4 设设R是是X上的等价关系，由上的等价关系，由R所确定的所确定的X的划分的划分也就是也就是R的所有等价类之集称为的所有等价类之集称为X对对R的的商集商集，并记，并记X/R。即：即：X/R=x x X，x是是x的等价类的等价类。等价关系等价关系R确定的划分是确定的划分是R的所有等价类之集的所有等价类之集 xx X商商 集集10本讲稿第十页，共三十页例例7：令令A=1,2,8。A关于
7、模关于模 3 等价关系等价关系R 的商集为：的商集为：A/R=1,4,7,2,5,8,3,6 A关于恒等关系和全域关系的商集为：关于恒等关系和全域关系的商集为：A/IA=1,2,8 A/EA=1,2,8 实实 例例11本讲稿第十一页，共三十页例例8：给出给出A1,2,3上所有的等价关系。上所有的等价关系。求解思路：先做出求解思路：先做出A的所有划分的所有划分,然后根据划分写出然后根据划分写出 对应的等价关系。对应的等价关系。实实 例例12本讲稿第十二页，共三十页实实 例例 1,2和和 3分别对应于等价关系分别对应于等价关系 R1,R2和和R3，其中，其中 R1=(2,3),(3,2)IA R2
8、=(1,3),(3,1)IA R3=(1,2),(2,1)IAA上的等价关系与划分之间的对应：上的等价关系与划分之间的对应：4对应于全域关系对应于全域关系EA；5对应于恒等关系对应于恒等关系IA；问题：问题：设集合设集合X为有限集，为有限集，|X|=n，则，则X上有多少个等价上有多少个等价关系？关系？13本讲稿第十三页，共三十页定理定理4 设设R为为X上的一个二元关系，则上的一个二元关系，则 e(R)=(RR-1)*。R的等价闭包的等价闭包(R的自反对称传递闭包的自反对称传递闭包)，记为，记为e(R),e(R)是是X上包含上包含R的那些等价关系的交集。的那些等价关系的交集。定理定理5 设设R,
9、S是是X上的等价关系，则上的等价关系，则R S是等价关系的是等价关系的充要条件是充要条件是R S=S R。推论推论设设R,S是是X上的等价关系，则上的等价关系，则R S是等价关系的是等价关系的充要条件是充要条件是R S S R。等价关系的运算等价关系的运算14本讲稿第十四页，共三十页 定义定义1 集合集合X上的二元关系上的二元关系R称为称为偏序关系偏序关系，如果，如果R同时满足以下三个性质：同时满足以下三个性质：当抽象地讨论当抽象地讨论X上的偏序关系时，常用符号上的偏序关系时，常用符号“”表表示偏序关系。如果示偏序关系。如果x y，则读作，则读作“x小于或等于小于或等于y”。1.R是自反的；是
10、自反的；2.R是反对称的；是反对称的；3.R是传递的。是传递的。约定约定x y且且x y时，就记为时，就记为xy。实实 例例17本讲稿第十七页，共三十页 定义定义3 集合集合X上的偏序关系上的偏序关系 叫做叫做全序关系全序关系，如果，如果 x,y X，x y与与y x至少有一个成立。全序关系也称为至少有一个成立。全序关系也称为线性序关系线性序关系。X与全序关系与全序关系构成的二元组构成的二元组(X,)称为称为全序集全序集。偏序集与全序集的主要区别在于全序集中任两个元素均偏序集与全序集的主要区别在于全序集中任两个元素均可比较可比较“大小大小”，而在偏序集中任意两个元素不一定都能比，而在偏序集中任
11、意两个元素不一定都能比较大小。较大小。实数间的常用的实数间的常用的“小于或等于小于或等于”关系是不是全序关系关系是不是全序关系?全序关系与全序集全序关系与全序集 集合的包含关系与自然数间的整除关系是不是全序集合的包含关系与自然数间的整除关系是不是全序关系关系?是全序关系，相应的偏序集也是全序集。是全序关系，相应的偏序集也是全序集。二者都不是全序关系。二者都不是全序关系。18本讲稿第十八页，共三十页 定义定义4 设设(X,)是一个偏序集，称是一个偏序集，称y盖住盖住x，如果，如果xy且且对每个对每个z X，若，若xzy，则，则x=z或或y=z。如果如果y盖住盖住x，则，则y被称为被称为x的的后继
12、后继，而，而x称为称为y的的前驱前驱。盖住的定义盖住的定义例例3：偏序集偏序集(N,)中，称中，称3盖住盖住2，3是是2的后继，的后继，2是是3的先的先驱驱。1,2,4,6集合上的整除关系集合上的整除关系,2覆盖覆盖1,4 和和 6 覆覆盖盖2；但；但4不覆盖不覆盖1.19本讲稿第十九页，共三十页哈斯哈斯(Hasse)图图 首先偏序关系首先偏序关系是自反的，所以偏序关系的关系图中每是自反的，所以偏序关系的关系图中每个顶点都有一个环，因此可以省略每个顶点的环。个顶点都有一个环，因此可以省略每个顶点的环。其次由于偏序关系是传递的，那么只要在前驱与后继其次由于偏序关系是传递的，那么只要在前驱与后继间
13、联线即可。间联线即可。最后由于反对称性，若最后由于反对称性，若xy，x y，则点，则点y画在画在x的的上方，这样就不必用矢线了，按上述方法画出的图称为上方，这样就不必用矢线了，按上述方法画出的图称为(X,)的的哈斯图哈斯图。20本讲稿第二十页，共三十页特点：特点：(1)每个结点没有环每个结点没有环;(2)两个连通的结点之间的序关系通过结点位置两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前的高低表示，位置低的元素的顺序在前;(3)具有覆盖关系的两个结点之间连边。具有覆盖关系的两个结点之间连边。哈斯图哈斯图就是利用偏序的自反、反对称、传就是利用偏序的自反、反对称、传递性简
14、化了的关系图。递性简化了的关系图。哈斯哈斯(Hasse)图的特点图的特点21本讲稿第二十一页，共三十页例例4：(1,2,3,4,5,6,7,8,9,R整除整除)(P(a,b,c),R)哈斯图实例哈斯图实例22本讲稿第二十二页，共三十页 例例5：已知偏序集已知偏序集(A,R)的哈斯图如下图所示，的哈斯图如下图所示，试求出试求出集合集合A和关系和关系R的表达式。的表达式。A=a,b,c,d,e,f,g,h R=(b,d),(b,e),(b,f),(c,d),(c,e),(c,f),(d,f),(e,f),(g,h)IA 哈斯图实例哈斯图实例23本讲稿第二十三页，共三十页例例6：设设A=a1,a2,
15、.,an是一个全序集，是一个全序集，则其元素则其元素(A,)的哈斯图象一条链子一样。的哈斯图象一条链子一样。所以，全序关系也叫做线性序关系，所以，全序关系也叫做线性序关系，全序集又称为线性序集。全序集又称为线性序集。可以可以“从小到大从小到大”排列为：排列为：ai1ai2.ain全序关系的哈斯图全序关系的哈斯图24本讲稿第二十四页，共三十页 定义定义5 设设(X,)是一个偏序集，是一个偏序集，B X。如果存在一个。如果存在一个元素元素a X使得对使得对B中每个元素中每个元素x有有xa，则称，则称a为为B的一个的一个上上界界。上界与下界的定义上界与下界的定义 如果存在一个元素如果存在一个元素b
16、X，使得对，使得对B的每一个元素的每一个元素x有有bx，则称，则称b为为B的一个的一个下界下界。上界与下界都不一定存在。上界与下界都不一定存在。例例7：令令A=2,3,6,12,24,36，A在整除关系在整除关系“”下构成一个下构成一个偏序集偏序集(A,)。24,36不存在上界不存在上界,上界与下界可能有很多元素上界与下界可能有很多元素6,12,24,36都是子集都是子集2,3的上界。的上界。2,3不存在下界不存在下界,25本讲稿第二十五页，共三十页 定义定义6 设设(X,)是一个偏序集，是一个偏序集，B X。如果存在一个元素。如果存在一个元素a B使得对使得对B中每个元素中每个元素x有有xa
17、，则称，则称a是是B中的中的最大元素最大元素。最大元素一定是上界，最小元素一定是下界最大元素一定是上界，最小元素一定是下界;最大与最小元素最大与最小元素 如果存在一个元素如果存在一个元素b B，使得对，使得对B的每一个元素的每一个元素x有有bx，则称，则称b是是B中的中的最小元素最小元素。有上下界不一定有最大与最小元素有上下界不一定有最大与最小元素,最大元素与最小元素若有一定是唯一的。最大元素与最小元素若有一定是唯一的。因为上下界不一定在子集中因为上下界不一定在子集中;26本讲稿第二十六页，共三十页 定义定义7 设设(X,)是一个偏序集，是一个偏序集，B X。如果。如果B有上界有上界且且B的一
18、切上界之集有最小元素，则这个最小上界称的一切上界之集有最小元素，则这个最小上界称为为B的的上确界上确界，记为，记为supB。上确界与下确界的定义上确界与下确界的定义 如果如果B有下界且有下界且B的一切下界之集有最大元素，则的一切下界之集有最大元素，则这个最大下界称为这个最大下界称为B的的下确界下确界，记为，记为infB。例例8：令令A=2,3,6,12,24,36，A在整除关系在整除关系“”下构成一个下构成一个偏序集偏序集(A,)。6,12,24,36都是子集都是子集2,3的上界。的上界。6是子集是子集2,3的上确界。的上确界。2,3,6,12都是子集都是子集24,36的下界。的下界。12是子
19、集是子集24,36的下确界。的下确界。27本讲稿第二十七页，共三十页A中有最大元素和最小元素吗？中有最大元素和最小元素吗？实实 例例例例9：令令A=2,3,6,12,24,36,A在整除关系在整除关系“”下构成一个偏下构成一个偏序集序集(A,)。A中没有最大元素也没有最小元素。中没有最大元素也没有最小元素。因为因为24与与36不可比，不可比，2与与3也不可比。也不可比。但是但是A中没有比中没有比24和和36更大的元素，也没有比更大的元素，也没有比2与与3更更小的元素。小的元素。称称24和和36都是极大元素都是极大元素,2与与3都是极小元素。都是极小元素。28本讲稿第二十八页，共三十页 定义定义
20、8 设设(X,)是一个偏序集，是一个偏序集，A X，A中元素中元素s称为称为A的的极大元素极大元素，如果，如果A中没有元素中没有元素m使得使得m s且且sm。若若A中有极大元素，则极大元素属于中有极大元素，则极大元素属于A，而且未必唯，而且未必唯一，甚至可能有无穷多个。一，甚至可能有无穷多个。如果如果A中有元素中有元素d，使得，使得 x A，若，若x d，则，则xd不成不成立，那么立，那么d被称为被称为A的的极小元素极小元素。极大元素不一定是最大元素，但最大元素一定是极大元素。极大元素不一定是最大元素，但最大元素一定是极大元素。同样若同样若A中有极小元素，则极小元素属于中有极小元素，则极小元素
21、属于A，而且未必，而且未必唯一，甚至可能有无穷多个。唯一，甚至可能有无穷多个。同样极小元素不一定是最小元素，但最小元素一定是极小同样极小元素不一定是最小元素，但最小元素一定是极小元素。元素。极大元素与极小元素的定义极大元素与极小元素的定义29本讲稿第二十九页，共三十页解：极小元：解：极小元：a,b,c,g；极大元：极大元：a,f,h；没有最小元与最大元。没有最小元与最大元。B的下界和最大下界都不存的下界和最大下界都不存在；在；上界有上界有d 和和 f；最小上界为最小上界为 d。实实 例例例例10：设偏序集设偏序集(A,)如下图所示，求如下图所示，求A 的极小元、的极小元、最小元、极大元、最大元。最小元、极大元、最大元。设设B b,c,d,求求B 的下界、上界、下确界、上确界。的下界、上界、下确界、上确界。30本讲稿第三十页，共三十页