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

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

1、4.4等价关系与偏序关系等价关系与偏序关系4.4.1等价关系等价关系4.4.2等价类和商集等价类和商集4.4.3集合的划分集合的划分4.4.4偏序关系偏序关系4.4.5偏序集与哈斯图偏序集与哈斯图1等价关系的定义与实例等价关系的定义与实例定义定义设设R为非空集合上的关系为非空集合上的关系.如果如果R是自反的、对称的是自反的、对称的和传递的和传递的,则称则称R为为A上的上的等价关系等价关系.设设R 是一个等价关系是一个等价关系,若若R,称称x等价于等价于y,记做记做xy.例例1设设A=1,2,8,如下定义如下定义A上的关系上的关系R：R=|x,yAxy(mod3)其中其中xy(mod3)叫做叫做

2、x与与y 模模3相等相等,即即x 除以除以3的余数与的余数与y 除以除以3的余数相等的余数相等.不难验证不难验证R为为A上的等价关系上的等价关系,因为因为 xA,有有xx(mod3)x,yA,若若xy(mod3),则有则有yx(mod3)x,y,zA,若若xy(mod3),yz(mod3),则有则有xz(mod3)2模模3 3等价关系的关系图等价关系的关系图设设A=1,2,8,R=|x,yAxy(mod3)R 的关系图如下：的关系图如下：3等价类等价类定义定义设设R为非空集合为非空集合A上的等价关系上的等价关系,xA，令，令xR=y|yAxRy 称称xR 为为x关于关于R 的的等价类等价类,简

3、称为简称为x 的等价类的等价类,简记为简记为x.实例实例A=1,2,8上模上模3等价关系的等价类：等价关系的等价类：1=4=7=1,4,72=5=8=2,5,83=6=3,64等价类的性质等价类的性质 定理定理4.8设设R是非空集合是非空集合A上的等价关系上的等价关系,则则(1)xA,x是是A的非空子集的非空子集.(2)x,yA,如果如果xRy,则则x=y.(3)x,yA,如果如果x y,则则x与与y不交不交.(4)，即所有等价类的并集就是即所有等价类的并集就是A.5性质的证明性质的证明由等价类定义可知由等价类定义可知,xA有有x A.由自反性有由自反性有xRx，因因此此xx,即即x非空非空.

4、任取任取z,则有则有zxR RRR R R从而证明了从而证明了zy.综上所述必有综上所述必有x y.同理可证同理可证y x.这就得到了这就得到了x=y.(3)假设假设xy,则存在则存在zxy,从而有从而有zxzy,即即RR 成立成立.根据根据R 的对称性和传递性必有的对称性和传递性必有R,与与x y矛盾矛盾6性质的证明（续）性质的证明（续）(4)先证先证.任取任取y,y x(xAyx)yxx A yA 从而有从而有.再证再证A.任取任取y,yA yyyA y从而有从而有A 成立成立.综上所述得综上所述得7商集商集定义定义设设R 为非空集合为非空集合A 上的等价关系上的等价关系,以以R 的所有等

5、的所有等价类作为元素的集合称为价类作为元素的集合称为A关于关于R 的的商集商集,记做记做A/R,A/R=xR|xA 例例2令令A=1,2,8，A关于模关于模3等价关系等价关系R 的商集为的商集为A/R=1,4,7,2,5,8,3,6 A关于恒等关系和全域关系的商集为：关于恒等关系和全域关系的商集为：A/IA=1,2,8A/EA=1,2,88集合的划分集合的划分定义定义4.21设设A为非空集合为非空集合,若若A的子集族的子集族 (P(A)满满足下面条件：足下面条件：(1)(2)x y(x,y xyxy=)(3)=A 则称则称 是是A的一个的一个划分划分,称称 中的元素为中的元素为A的的划分块划分

6、块.例例3设设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的划分的划分.9等价关系与划分的一一对应等价关系与划分的一一对应商集商集A/R 就是就是A 的一个划分的一个划分不同的商集对应于不同的划分不同的商集对应于不同的划分任给任给A 的一个划分的一个划分 ,如下定义如下定义A 上的关系上的关系R：R=|x,yAx 与与y 在在 的同一划分块中的同一划分块中则则R 为为A上的等价关系上的等价关系,且

7、该等价关系确定的商集就是且该等价关系确定的商集就是.例例4给给出出A1,2,3上所有的等价关系上所有的等价关系求解思路：先做出求解思路：先做出A的所有划分的所有划分,然后根据划分写出然后根据划分写出对应对应的等价关系的等价关系.10例例4 1,2和和 3分别对应于等价关系分别对应于等价关系R1,R2和和R3.其中其中R1=,IAR2=,IAR3=,IAA上的等价关系与划上的等价关系与划分之间的对应：分之间的对应：4对应于全域关系对应于全域关系EA 5对应于恒等关系对应于恒等关系IA11实例实例根据有序对根据有序对的的x+y=2,3,4,5,6,7,8将将A A划分划分.(A A)/R=,例例5

8、设设A=1,2,3,4，在，在A A上定义二元关系上定义二元关系R：,R x+y=u+v，求求R 导出的划分导出的划分.解解A A=,12偏序关系偏序关系定义定义非空集合非空集合A上的自反、反对称和传递的关系，称为上的自反、反对称和传递的关系，称为A上的上的偏序关系偏序关系，记作，记作.设设 为偏序关系为偏序关系,如果如果,则记作则记作x y,读作读作x“小于或等于小于或等于”y.实例实例集合集合A上的恒等关系上的恒等关系IA 是是A上的偏序关系上的偏序关系.小于或等于关系小于或等于关系,整除关系和包含关系也是相应集合整除关系和包含关系也是相应集合上的偏序关系上的偏序关系.13相关概念相关概念

9、定义定义 x与与y可比可比设设R为非空集合为非空集合A上的偏序关系上的偏序关系,x,y A,x与与y 可比可比x y y x.结论：结论：x,y A，下述几种情况发生其一且仅发生其一，下述几种情况发生其一且仅发生其一.x y,y x,xy,x与与y不是可比的不是可比的定义定义全序全序R为非空集合为非空集合A上的偏序上的偏序,x,y A,x与与y 都可都可比，则称比，则称R为全序为全序.定义定义4.26覆盖覆盖x,yA,如果如果x y且不存在且不存在z A使得使得x z y,则称则称y覆盖覆盖x.实例：数集上的小于或等于关系是全序关系实例：数集上的小于或等于关系是全序关系整除关系不是正整数集合上

10、的全序关系整除关系不是正整数集合上的全序关系1,2,4,6集合上的整除关系集合上的整除关系,2覆盖覆盖1,4和和6覆盖覆盖2.但但4不覆盖不覆盖1.14偏序集与哈斯图偏序集与哈斯图定义定义4.27集合集合A和和A上的偏序关系上的偏序关系 一起叫做一起叫做偏序集偏序集,记记作作.实例：整数集和数的小于等于关系构成偏序集实例：整数集和数的小于等于关系构成偏序集 幂集幂集P(A)和包含关系构成偏序集和包含关系构成偏序集.哈斯图哈斯图：利用偏序自反、反对称、传递性简化的关系图：利用偏序自反、反对称、传递性简化的关系图特点：特点：每个结点没有环每个结点没有环两个连通的结点之间的序关系通过结点位置的高低两

11、个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前表示，位置低的元素的顺序在前具有覆盖关系的两个结点之间连边具有覆盖关系的两个结点之间连边15哈斯图实例哈斯图实例例例616 例例7已知偏序集已知偏序集的哈斯图如下图所示的哈斯图如下图所示,试求出集合试求出集合A和关系和关系R的表达式的表达式.哈斯图实例（续）哈斯图实例（续）A=a,b,c,d,e,f,g,hR=,IA 17偏序集的特定元素偏序集的特定元素定义定义设设为偏序集为偏序集,B A,yB.(1)若若 x(xBy x)成立成立,则称则称y 为为B 的的最小元最小元.(2)若若 x(xBx y)成立成立,则称则称y 为为

12、B 的的最大元最大元.(3)若若 x(xBx yx=y)成立成立,则称则称y 为为B的的极小元极小元.(4)若若 x(xBy xx=y)成立成立,则称则称y 为为B的的极大元极大元.性质：性质：对于有穷集，极小元和极大元必存在，可能存在多个对于有穷集，极小元和极大元必存在，可能存在多个.最小元和最大元不一定存在，如果存在一定惟一最小元和最大元不一定存在，如果存在一定惟一.最小元一定是极小元；最大元一定是极大元最小元一定是极小元；最大元一定是极大元.孤立结点既是极小元，也是极大元孤立结点既是极小元，也是极大元.18定义定义4.29设设为偏序集为偏序集,B A,y A.（1）若若 x(xBx y)

13、成立成立,则称则称y 为为B 的的上界上界.（2）若若 x(xBy x)成立成立,则称则称y 为为B 的的下界下界.（3）令令Cy|y为为B的上界的上界,则称则称C的最小元为的最小元为B 的的最最小上界小上界或或上确界上确界.（4）令令Dy|y为为B的下界的下界,则称则称D的最大元为的最大元为B 的的最最大下界大下界或或下确界下确界.性质：性质：下界、上界、下确界、上确界不一定存在下界、上界、下确界、上确界不一定存在下界、上界存在不一定惟一下界、上界存在不一定惟一下确界、上确界如果存在，则惟一下确界、上确界如果存在，则惟一集合的最小元就是它的下确界，最大元就是它的上确集合的最小元就是它的下确界

14、，最大元就是它的上确界；反之不对界；反之不对.偏序集的特定元素偏序集的特定元素(续续)19实例实例例例8设偏序集设偏序集如下图所示，求如下图所示，求A 的极小元、最小元、的极小元、最小元、极大元、最大元极大元、最大元.设设Bb,c,d,求求B 的下界、上界、下的下界、上界、下确界、上确界确界、上确界.解：极小元：解：极小元：a,b,c,g；极大元：极大元：a,f,h；没有最小元与最大元没有最小元与最大元.B的下界和最大下界的下界和最大下界都不存在都不存在,上界有上界有d 和和f,最小上界为最小上界为d.20偏序集的特殊子集偏序集的特殊子集定义定义设设为偏序集为偏序集,B A.(1)如果如果 x

15、,y B，x与与y都是可比的，则称都是可比的，则称B是是A中的一条中的一条链链，B中的元素个数称为中的元素个数称为链的长度链的长度；(2)如果如果 x,y B，x y，x与与y都是不可比的，则称都是不可比的，则称B是是A中的一条中的一条反链反链，B中的元素个数称为中的元素个数称为反链的长度反链的长度.实例：在偏序集实例：在偏序集中，中，1,2,4,8是长为是长为4的的链，链，1,4是长为是长为2的链，的链，2,3是长为是长为2的反链的反链.对于单元对于单元集集2，它的长度是，它的长度是1，既是链也是反链，既是链也是反链.21分解为反链分解为反链算法算法4.2偏序集反链分解算法偏序集反链分解算法

16、输入：偏序集输入：偏序集A输出：输出：A中的反链中的反链B1,B2,1i12BiA 的所有极大元的集合（显然的所有极大元的集合（显然Bi是一条反链）是一条反链）3令令AA Bi4ifA 5ii+16转转2定理定理设设为偏序集，如果为偏序集，如果A中最长的链长度为中最长的链长度为n,则则该偏序集可以分解为该偏序集可以分解为n 条不相交的反链条不相交的反链.22拓扑排序拓扑排序算法算法拓扑排序拓扑排序输入：偏序集输入：偏序集A输出：输出：A中元素的排序中元素的排序1.i12.从从A中选择一个极小元中选择一个极小元ai 作为最小元作为最小元3AA ai4ifA5ii+16转转2把偏序集扩张成一个全序集，称为把偏序集扩张成一个全序集，称为拓扑排序拓扑排序.23实例实例有偏序约束的任务集有偏序约束的任务集A，偏序集偏序集的的哈斯图如图哈斯图如图A=T1,T2,T3,T4,T5,S1,T6,S2,T,T9,T10可行的拓扑排序有多个，可行的拓扑排序有多个，如：如：T1,T2,T3,T4,S1,T5,T6,S2,T,T9,T10；T1,T2,T3,T4,S1,T6,S2,T,T9,T5,T10;24