离散数学等价关系与偏序关系课件.ppt

《离散数学等价关系与偏序关系课件.ppt》由会员分享，可在线阅读，更多相关《离散数学等价关系与偏序关系课件.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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、实例例例2：考虑整数集考虑整数集Z上的模上的模n同余关系。同余关系。例例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的子集的

3、子集Ex=y y X且且xRy称为称为x关于关于R的的等价类等价类，或简记为或简记为x的等价类。的等价类。x的等价类常记为的等价类常记为x，即，即x=y y 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上的等价关系上的等价关系,则则

4、(1)x X,x。(2)x,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,

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集合与图论 定理定理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的所有等价类之集的所有等价类之集 x x X商商 集集10集合与图论例例7：令令A=1,2,8。A关于模关于模 3 等价关系等价关系R

7、的商集为：的商集为：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=(1,3),(3,1)IA R3=(1,2),(2,1)IA

8、A上的等价关系与划分之间的对应：上的等价关系与划分之间的对应：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,S是是X上的等价关系，则上的等价关系，则R S是等价关是等价关系的充要条件是

9、系的充要条件是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是自反的；是自反的；2.R是反对称的；是反对称的；3.R是传递的。是传递的。约定约定x y且且x y时

10、，就记为时，就记为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的的后继后继，而，而x称为称为y的的前前驱驱。盖住的定义盖住的定义例例3：偏序集偏序集(N,)中，称中，称3盖住盖住2，3是是

12、2的后继，的后继，2是是3的先驱的先驱。1,2,4,6集合上的整除关系集合上的整除关系,2覆盖覆盖1,4 和和 6 覆覆盖盖2；但；但4不覆盖不覆盖1.19集合与图论哈斯哈斯(Hasse)图图 首先偏序关系首先偏序关系是自反的，所以偏序关系的关系图是自反的，所以偏序关系的关系图中每个顶点都有一个环，因此可以省略每个顶点的环。中每个顶点都有一个环，因此可以省略每个顶点的环。其次由于偏序关系是传递的，那么只要在前驱与其次由于偏序关系是传递的，那么只要在前驱与后继间联线即可。后继间联线即可。最后由于反对称性，若最后由于反对称性，若xy，x y，则点，则点y画在画在x的上方，这样就不必用矢线了，按上述

13、方法画出的图的上方，这样就不必用矢线了，按上述方法画出的图称为称为(X,)的的哈斯图哈斯图。20集合与图论特点：特点：(1)每个结点没有环每个结点没有环;(2)两个连通的结点之间的序关系通过结点两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前位置的高低表示，位置低的元素的顺序在前;(3)具有覆盖关系的两个结点之间连边。具有覆盖关系的两个结点之间连边。哈斯图哈斯图就是利用偏序的自反、反对称、传就是利用偏序的自反、反对称、传递性简化了的关系图。递性简化了的关系图。哈斯哈斯(Hasse)图的特点图的特点21集合与图论例例4：(1,2,3,4,5,6,7,8,9,R整除整除)(

14、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,.,an是一个全序集，是一个全序集，则其元素则其元素(A,)的哈斯图象一条链子一样。的哈斯图象一条链子一样。所以，全序关系也叫做线性序关系，所以，全序关系也叫做线性序关系，全序集又称为线性序集。

15、全序集又称为线性序集。可以可以“从小到大从小到大”排列为：排列为：ai1ai2.ain全序关系的哈斯图全序关系的哈斯图24集合与图论 定义定义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在整除关系在整除关

16、系“”下构成下构成一个偏序集一个偏序集(A,)。24,36不存在上界不存在上界,上界与下界可能有很多元素上界与下界可能有很多元素6,12,24,36都是子集都是子集2,3的上界。的上界。2,3不存在下界不存在下界,25集合与图论 定义定义6 设设(X,)是一个偏序集，是一个偏序集，B X。如果存在一。如果存在一个元素个元素a B使得对使得对B中每个元素中每个元素x有有xa，则称，则称a是是B中的中的最大元素最大元素。最大元素一定是上界，最小元素一定是下界最大元素一定是上界，最小元素一定是下界;最大与最小元素最大与最小元素 如果存在一个元素如果存在一个元素b B，使得对，使得对B的每一个元素的每

17、一个元素x有有bx，则称，则称b是是B中的中的最小元素最小元素。有上下界不一定有最大与最小元素有上下界不一定有最大与最小元素,最大元素与最小元素若有一定是唯一的。最大元素与最小元素若有一定是唯一的。因为上下界不一定在子集中因为上下界不一定在子集中;26集合与图论 定义定义7 设设(X,)是一个偏序集，是一个偏序集，B X。如果。如果B有有上界且上界且B的一切上界之集有最小元素，则这个最小上的一切上界之集有最小元素，则这个最小上界称为界称为B的的上确界上确界，记为，记为supB。上确界与下确界的定义上确界与下确界的定义 如果如果B有下界且有下界且B的一切下界之集有最大元素，的一切下界之集有最大元

18、素，则这个最大下界称为则这个最大下界称为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集合与图论A中有最大元素和最小元素吗？中有最大元素和最小元素吗？实实 例例例例9：令令A=2,3,6,12,24,36,A在整除关系在整除关系“”下构成一个下构成一个偏序集偏序集(A,)。A中没有最大

19、元素也没有最小元素。中没有最大元素也没有最小元素。因为因为24与与36不可比，不可比，2与与3也不可比。也不可比。但是但是A中没有比中没有比24和和36更大的元素，也没有比更大的元素，也没有比2与与3更小的元素。更小的元素。称称24和和36都是极大元素都是极大元素,2与与3都是极小元素。都是极小元素。28集合与图论 定义定义8 设设(X,)是一个偏序集，是一个偏序集，A X，A中元素中元素s称称为为A的的极大元素极大元素，如果，如果A中没有元素中没有元素m使得使得m s且且sm。若若A中有极大元素，则极大元素属于中有极大元素，则极大元素属于A，而且未必，而且未必唯一，甚至可能有无穷多个。唯一，

20、甚至可能有无穷多个。如果如果A中有元素中有元素d，使得，使得 x A，若，若x d，则，则xd不不成立，那么成立，那么d被称为被称为A的的极小元素极小元素。极大元素不一定是最大元素，但最大元素一定是极大元素不一定是最大元素，但最大元素一定是极大元素。极大元素。同样若同样若A中有极小元素，则极小元素属于中有极小元素，则极小元素属于A，而且未，而且未必唯一，甚至可能有无穷多个。必唯一，甚至可能有无穷多个。同样极小元素不一定是最小元素，但最小元素一定同样极小元素不一定是最小元素，但最小元素一定是极小元素。是极小元素。极大元素与极小元素的定义极大元素与极小元素的定义29集合与图论解：极小元：解：极小元：a,b,c,g；极大元：极大元：a,f,h；没有最小元与最大元。没有最小元与最大元。B的下界和最大下界都的下界和最大下界都不存在；不存在；上界有上界有d 和和 f；最小上界为最小上界为 d。实实 例例例例10：设偏序集设偏序集(A,)如下图所示，求如下图所示，求A 的极小元、的极小元、最小元、极大元、最大元。最小元、极大元、最大元。设设B b,c,d,求求B 的下界、上界、下确界、上确界。的下界、上界、下确界、上确界。30