第9节等价关系与偏序关系优秀课件.ppt

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