《离散数学-44等价关系与偏序关系.ppt》由会员分享，可在线阅读，更多相关《离散数学-44等价关系与偏序关系.ppt（24页珍藏版）》请在三一办公上搜索。
1、课件,1,4.4 等价关系与偏序关系,4.4.1 等价关系4.4.2 等价类和商集4.4.3 集合的划分4.4.4 偏序关系4.4.5 偏序集与哈斯图,课件,2,等价关系的定义与实例,定义4.18 设R为非空集合上的关系.如果R是自反的、对称的和传递的,则称R为A上的等价关系.设 R 是一个等价关系,若R,称 x等价于y,记做xy.例1 设 A=1,2,8,如下定义 A上的关系R：R=|x,yAxy(mod 3)其中 xy(mod 3)叫做 x与y 模3相等,即 x 除以3的余数与 y 除以3的余数相等.不难验证R为A上的等价关系,因为 xA,有xx(mod 3)x,yA,若xy(mod 3)
2、,则有yx(mod 3)x,y,zA,若xy(mod 3),yz(mod 3),则有 xz(mod 3),课件,3,模3等价关系的关系图,设 A=1,2,8,R=|x,yAxy(mod 3)R 的关系图如下：,课件,4,等价类,定义4.19 设R为非空集合A上的等价关系,xA，令 xR=y|yAxRy 称 xR 为x关于R 的等价类,简称为 x 的等价类,简记为x.实例 A=1,2,8 上模 3 等价关系的等价类：1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,6,课件,5,等价类的性质,定理4.8 设R是非空集合A上的等价关系,则(1)xA,x 是A的非空子集.(2)x,yA,如
3、果 xRy,则 x=y.(3)x,yA,如果 x y,则 x与y不交.(4)，即所有等价类的并集就是A.,课件,6,性质的证明,由等价类定义可知,xA有xA.由自反性有xRx，因此xx,即x非空.任取z,则有zx R RRR R R从而证明了zy.综上所述必有xy.同理可证y x.这就得到了x=y.(3)假设xy,则存在zxy,从而有zxzy,即RR 成立.根据R 的对称性和传递性必有R,与x y矛盾,课件,7,性质的证明（续）,(4)先证.任取y,y x(xAyx)yxxA yA 从而有.再证A.任取y,yA yyyA y从而有A 成立.综上所述得,课件,8,商集,定义4.20 设R 为非空
4、集合A 上的等价关系,以R 的所有等价类作为元素的集合称为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,8 A/EA=1,2,8,课件,9,集合的划分,定义4.21 设A为非空集合,若A的子集族(P(A)满足下面条件：(1)(2)xy(x,yxyxy=)(3)=A 则称是A的一个划分,称 中的元素为A的划分块.例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,
5、b,c 5=,a,b,c,d，6=a,a,b,c,d 则 1和 2是A的划分,其他都不是A的划分.,课件,10,等价关系与划分的一一对应,商集 A/R 就是A 的一个划分 不同的商集对应于不同的划分 任给A 的一个划分,如下定义A 上的关系 R：R=|x,yAx 与 y 在的同一划分块中 则R 为A上的等价关系,且该等价关系确定的商集就是.,例4 给出A1,2,3上所有的等价关系求解思路：先做出A的所有划分,然后根据划分写出 对应的等价关系.,课件,11,例 4,1,2和 3分别对应于等价关系 R1,R2和R3.其中 R1=,IA R2=,IA R3=,IA,A上的等价关系与划分之间的对应：4
6、对应于全域关系EA 5对应于恒等关系IA,课件,12,实例,根据有序对的 x+y=2,3,4,5,6,7,8 将AA划分.(AA)/R=,例5 设A=1,2,3,4，在AA上定义二元关系 R：,R x+y=u+v，求R 导出的划分.,解 AA=,课件,13,偏序关系,定义4.22 非空集合A上的自反、反对称和传递的关系，称为A上的偏序关系，记作.设为偏序关系,如果,则记作 xy,读作 x“小于或等于”y.实例 集合A上的恒等关系 IA 是A上的偏序关系.小于或等于关系,整除关系和包含关系也是相应集合上的偏序关系.,课件,14,相关概念,定义4.23 x与y可比 设R为非空集合A上的偏序关系,x
7、,yA,x与y 可比 xy yx.结论：x,yA，下述几种情况发生其一且仅发生其一.xy,yx,xy,x与y不是可比的定义4.25 全序 R为非空集合A上的偏序,x,yA,x与y 都可比，则称R为全序.定义4.26 覆盖 x,yA,如果xy且不存在 zA使得 xzy,则称 y覆盖x.实例：数集上的小于或等于关系是全序关系 整除关系不是正整数集合上的全序关系 1,2,4,6集合上的整除关系,2覆盖1,4 和 6 覆盖2.但4不覆盖1.,课件,15,偏序集与哈斯图,定义4.27 集合A和A上的偏序关系一起叫做偏序集,记作.实例：整数集和数的小于等于关系构成偏序集 幂集P(A)和包含关系构成偏序集.
8、哈斯图：利用偏序自反、反对称、传递性简化的关系图特点：每个结点没有环 两个连通的结点之间的序关系通过结点位置的高低 表示，位置低的元素的顺序在前 具有覆盖关系的两个结点之间连边,课件,16,哈斯图实例,例6,课件,17,例7 已知偏序集的哈斯图如下图所示,试求出集合A和关系R的表达式.,哈斯图实例（续）,A=a,b,c,d,e,f,g,h R=,IA,课件,18,偏序集的特定元素,定义4.28 设为偏序集,BA,yB.(1)若x(xByx)成立,则称 y 为 B 的最小元.(2)若x(xBxy)成立,则称 y 为 B 的最大元.(3)若x(xBxyx=y)成立,则称 y 为B的极小元.(4)若
9、x(xByxx=y)成立,则称 y 为B的极大元.性质：对于有穷集，极小元和极大元必存在，可能存在多个.最小元和最大元不一定存在，如果存在一定惟一.最小元一定是极小元；最大元一定是极大元.孤立结点既是极小元，也是极大元.,课件,19,定义4.29 设为偏序集,BA,yA.（1）若x(xBxy)成立,则称 y 为B 的上界.（2）若x(xByx)成立,则称 y 为B 的下界.（3）令Cy|y为B的上界,则称C的最小元为B 的最小上界 或上确界.（4）令Dy|y为B的下界,则称D的最大元为B 的最大下界 或下确界.性质：下界、上界、下确界、上确界不一定存在 下界、上界存在不一定惟一 下确界、上确界
10、如果存在，则惟一 集合的最小元就是它的下确界，最大元就是它的上确界；反之不对.,偏序集的特定元素(续),课件,20,实例,例8 设偏序集如下图所示，求A 的极小元、最小元、极大元、最大元.设B b,c,d,求B 的下界、上界、下确界、上确界.,解：极小元：a,b,c,g；极大元：a,f,h；没有最小元与最大元.B的下界和最大下界都不存在,上界有d 和 f,最小上界为 d.,课件,21,偏序集的特殊子集,定义4.30 设为偏序集,BA.(1)如果x,yB，x与y都是可比的，则称B是A中的一条链，B中的元素个数称为链的长度；(2)如果x,yB，xy，x与y都是不可比的，则称B是A中的一条反链，B中
11、的元素个数称为反链的长度.实例：在偏序集中，1,2,4,8是长为4的链，1,4是长为2的链，2,3是长为2的反链.对于单元集2，它的长度是1，既是链也是反链.,课件,22,分解为反链,算法4.2 偏序集反链分解算法输入：偏序集A输出：A中的反链B1,B2,1i12BiA 的所有极大元的集合（显然Bi是一条反链）3令AABi4if A 5 ii+16 转2,定理4.9 设为偏序集，如果A中最长的链长度为n,则该偏序集可以分解为 n 条不相交的反链.,课件,23,拓扑排序,算法4.3 拓扑排序输入：偏序集A输出：A中元素的排序1.i12.从A中选择一个极小元 ai 作为最小元3AAai4if A5 ii+16 转2,把偏序集扩张成一个全序集，称为拓扑排序.,课件,24,实例,有偏序约束的任务集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;,
