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

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

1、1/30,第9节 等价关系与偏序关系,主要内容： 等价关系 偏序关系,2/30,定义1 集合X上的二元关系R称为等价关系，如果R同时具有以下三个性质：,例1：集合X上的恒等关系是不是X上的等价关系？,1. R是自反的，即xX，xRx;,2. R是对称的，即如果xRy，则yRx;,3. R是传递的，即如果xRy，yRz，则xRz。,是X上的等价关系。,1 等价关系,3/30,等价关系实例,例2：考虑整数集Z上的模n同余关系。,例4：设f:XY，Ker(f)=(x,y)x,yX，且f(x)=f(y)。,Ker(f)是X上的等价关系。,例3：实数集上的“”、“”、“”、“”是不是R上的等价关系？,实

2、数集上的“”、“”、“”、“”都不是R上的等价关系。,是等价关系。,4/30,例5：设 A=1, 2, , 8, 如下定义 A上的关系R： R=(x,y)| x,yAxy (mod 3),R 的关系图如下：,等价关系的关系图,5/30,定义2 设R是X上的一个等价关系，xX，X的子集Ex=yyX且xRy称为x关于R的等价类，或简记为x的等价类。,x的等价类常记为x，即x=yyX且xRy。,例5：设 A=1, 2, , 8, 如下定义 A上的关系R： R=(x,y)| x,yAxy (mod 3),等价类的定义,A= 1, 2, , 8 上模 3 等价关系的等价类： 1=4=7=1,4,7 2=

3、5=8=2,5,8 3=6=3,6,6/30,等价类的性质,(3) x, yX, 如果(x, y)R, 则 xy=。,定理1 设R是非空集合X上的等价关系, 则 (1) xX, x 。,(2) x, yX, 如果(x, y)R, 则 x=y。,(4) ，即所有等价类的并集就是X。,7/30,定义3 设X为非空集合，X的若干个子集形成的集族称为X的一个划分，如果具有性质：,集合的划分,如果是X的一个划分，则当=k时， 被称为X的一个k-划分。,(2) x,y，若xy，则xy=;,(1) ；,(3) 。,称 中的元素为X的划分块。,8/30,例6：设Aa, b, c, d, 给定 1, 2, 3,

4、 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的划分。,实 例,9/30,定理1 设R是X上的一个等价关系，则R的所有等价类的集合是X的一个划分。,等价关系与集合的划分,定理2 设是集合X的一个划分，令 R =(x,y) | x,yXx与y在的同一划分块中 则R是X上的一个等价关系，并且就是R的等价类之集。,注： 由定理1、2可得：X上的等价关系与X的划分是一一对应的，并且互相确定。,10/30,定义4 设R是X上的等价关系，由R

5、所确定的X的划分也就是R的所有等价类之集称为X对R的商集，并记X/R。,即：X/R=x xX，x是x的等价类。,等价关系R确定的划分是R的所有等价类之集 xxX,商 集,11/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 ,实 例,12/30,例8：给出A1,2,3上所有的等价关系。 求解思路：先做出A的所有划分, 然后根据划分写出 对应的等价关系。,实 例,13/30,实 例, 1, 2和 3分别对应于等价关

6、系 R1, R2和R3，其中 R1=(2,3),(3,2)IA R2=(1,3),(3,1)IA R3=(1,2),(2,1)IA,A上的等价关系与划分之间的对应： 4对应于全域关系EA； 5对应于恒等关系IA；,问题：设集合X为有限集，|X|=n，则X上有多少个等价关系？,14/30,定理4 设R为X上的一个二元关系，则 e(R)=(RR-1)*。,R的等价闭包(R的自反对称传递闭包)，记为e(R), e(R)是X上包含R的那些等价关系的交集。,定理5 设R,S是X上的等价关系，则RS是等价关系的充要条件是RS=SR。,推论设R,S是X上的等价关系，则RS是等价关系的充要条件是RSSR。,等

7、价关系的运算,15/30,定义1 集合X上的二元关系R称为偏序关系，如果R同时满足以下三个性质：,当抽象地讨论X上的偏序关系时，常用符号“”表示偏序关系。如果xy，则读作“x小于或等于y”。,1. R是自反的；,2. R是反对称的；,3. R是传递的。,约定xy且xy时，就记为xy。,在偏序关系中，并不是X中所有元素都可比较;,如果存在x,yX使得xy与yx中有一个成立，则称x与y可比较;,2 偏序关系,16/30,定义2 设是X上的一个偏序关系，则称二元组(X,)为偏序集。,一个集合上可能存在多个偏序集。,例1：设S是一个集合，S的子集间的包含关系是不是偏序关系？,在这个偏序集中，存在着不可

8、比较元素。 例如：S=a,b,c，则a与b,c不可比较。,偏序集,例如实数集上存在(R,)和(R,)两个偏序集。,S的子集间的包含关系是2S上的偏序关系，(2S,)是一个偏序集。,17/30,例2：自然数集合N上的整除关系“”是不是偏序关系?,自然数集合N上的整除关系“”是偏序关系。 (N,)是一个偏序集。,设是X上的偏序关系，则的逆-1也是X上的偏序关系，以后用“”表示的逆关系，并读成“大于或等于”。,若xy且xy，则简记为xy。,实 例,18/30,定义3 集合X上的偏序关系叫做全序关系，如果x,yX，xy与yx至少有一个成立。全序关系也称为线性序关系。X与全序关系构成的二元组(X,)称为

9、全序集。,偏序集与全序集的主要区别在于全序集中任两个元素均可比较“大小”，而在偏序集中任意两个元素不一定都能比较大小。,实数间的常用的“小于或等于”关系是不是全序关系?,全序关系与全序集,集合的包含关系与自然数间的整除关系是不是全序关系?,是全序关系，相应的偏序集也是全序集。,二者都不是全序关系。,19/30,定义4 设(X,)是一个偏序集，称y盖住x，如果xy且对每个zX，若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 和

10、6 覆 盖2；但4不覆盖1.,20/30,哈斯(Hasse)图,首先偏序关系是自反的，所以偏序关系的关系图中每个顶点都有一个环，因此可以省略每个顶点的环。,其次由于偏序关系是传递的，那么只要在前驱与后继间联线即可。,最后由于反对称性，若xy，xy，则点y画在x的上方，这样就不必用矢线了，按上述方法画出的图称为(X,)的哈斯图。,21/30,特点： (1)每个结点没有环; (2)两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前; (3)具有覆盖关系的两个结点之间连边。,哈斯图就是利用偏序的自反、反对称、传 递性简化了的关系图。,哈斯(Hasse)图的特点,22/30,例4

11、：( 1, 2, 3, 4, 5, 6, 7, 8, 9 , R整除) (P(a, b, c), R),哈斯图实例,23/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,哈斯图实例,24/30,例6：设A=a1,a2,.,an是一个全序集，则其元素,(A,)的哈斯图象一条链子一样。,所以，全序关系也叫做线性序关系，全序集又称为线性序集。,可以“从小到大”排列为： ai1ai2.ain,全序

12、关系的哈斯图,25/30,定义5 设(X,)是一个偏序集，BX。如果存在一个元素aX使得对B中每个元素x有xa，则称a为B的一个上界。,上界与下界的定义,如果存在一个元素bX，使得对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不存在下界,26/30,定义6 设(X,)是一个偏序集，BX。如果存在一个元素aB使得对B中每个元素x有xa，则称a是B中的最大元素。,最大元素一定是上界，最小

13、元素一定是下界;,最大与最小元素,如果存在一个元素bB，使得对B的每一个元素x有bx，则称b是B中的最小元素。,有上下界不一定有最大与最小元素,最大元素与最小元素若有一定是唯一的。,因为上下界不一定在子集中;,27/30,定义7 设(X,)是一个偏序集，BX。如果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,

14、3的上确界。,2,3,6,12都是子集24,36的下界。,12是子集24,36的下确界。,28/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都是极小元素。,29/30,定义8 设(X,)是一个偏序集，AX，A中元素s称为A的极大元素，如果A中没有元素m使得ms且sm。,若A中有极大元素，则极大元素属于A，而且未必唯一，甚至可能有无穷多个。,如

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