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

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