等价关系与偏序关系精选文档.ppt

《等价关系与偏序关系精选文档.ppt》由会员分享，可在线阅读，更多相关《等价关系与偏序关系精选文档.ppt（22页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、等价关系与偏序关系等价关系与偏序关系本讲稿第一页，共二十二页2实例实例设设A=1,2,8,R=|x,yAxy(mod3)R 的关系图如：的关系图如：例例1设设A=1,2,8,如下定义如下定义A上的关系上的关系R：R=|x,yAxy(mod3)其中其中xy(mod3)叫做叫做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定理定理4.8设设R是非空集合是非空集合A上的等价关系，则有下面的结论成立：上的等价关系，则有下面的结论成立：1)对对 x A，xR；2)对对 x,yA，如果，如果yxR，则有，则有xR=yR3)对对 x,yA，如果，如果yxR，则有，则有xRyR4)A；定义定义4.20设设R是非空集合是非空集合A上的等价关系，对任意上的等价关系，对任意xA，称集合，称集合xRy|yAR(也即也即A中与中与x等价的等价的全体元素构成的子集全体元素构成的子集)为为x关于关于R的等价类的等价类.等价类等价类本讲稿第三页，共二十二页4集合的划分集合的划分定义定义4.21设设A为非空集合为非空集合,若

3、若A的子集族的子集族 (P(A)满足满足下面条件：下面条件：(1)(2)x y(x,y xyxy=)(3)=A 则称则称 是是A的一个划分的一个划分,称称 中的元素为中的元素为A的划分块的划分块.本讲稿第四页，共二十二页5商集商集定义定义4.22设设R 为非空集合为非空集合A 上的等价关系上的等价关系,以以R 的的所有等价类作为元素的集合称为所有等价类作为元素的集合称为A关于关于R 的商集的商集,记做记做A/R,A/R=xR|xA 本讲稿第五页，共二十二页6等价关系与划分的一一对应等价关系与划分的一一对应(1)商集商集A/R 就是就是A 的一个划分的一个划分,不同的商集对应于不同不同的商集对应

4、于不同的划分的划分(2)任给任给A 的一个划分的一个划分 ,如下定义如下定义A 上的关系上的关系R：R=|x,yAx 与与y 在在 的同一划分块中的同一划分块中则则R 为为A上的等价关系上的等价关系,且该等价关系确定的商集就是且该等价关系确定的商集就是.本讲稿第六页，共二十二页7总结总结1、熟记等价关系的定义；、熟记等价关系的定义；2、利用等价关系的定义证明一个关系是等价关系；、利用等价关系的定义证明一个关系是等价关系；3、给定、给定A上的等价关系上的等价关系R，会求所有的等价类和商集，会求所有的等价类和商集A/R；并求出对应的集合的划分；并求出对应的集合的划分；4、给定集合、给定集合A上的划

5、分，会求对应的等价类。上的划分，会求对应的等价类。本讲稿第七页，共二十二页8判定下列关系具有哪些性质判定下列关系具有哪些性质1、对任何非空集合、对任何非空集合A，A上的恒等关系；上的恒等关系；2、多边形的、多边形的“相似关系相似关系”、“全等关系全等关系”；3、集合、集合A的幂集的幂集P(A)上定义的上定义的“包含关系包含关系”；4、集合、集合A的幂集的幂集P(A)上定义的上定义的“真包含关系真包含关系”。解：解：1，2都都具有具有自反性，对称性自反性，对称性自反性，对称性自反性，对称性和和和和传递性传递性传递性传递性，是等价关系；，是等价关系；，是等价关系；，是等价关系；3具有具有自反性自反

6、性自反性自反性，反对称性和传递性；反对称性和传递性；4具有具有反自反性，反自反性，反自反性，反自反性，反对称性，传递性。反对称性，传递性。偏序关偏序关系系拟序关系拟序关系本讲稿第八页，共二十二页94.7偏序关系偏序关系定义定义4.22非空集合非空集合A上的自反、反对称和传递的关系，上的自反、反对称和传递的关系，称为称为A上的偏序关系，记作上的偏序关系，记作.设设 为偏序关系为偏序关系,如果如果,则记作则记作x y,读作读作x“小于或等于小于或等于”y.并将集合并将集合A A与偏序关系与偏序关系R R一起叫做偏序集，一起叫做偏序集，用序偶用序偶或者或者表示。表示。不指数的大小，不指数的大小，而指

7、在偏序关而指在偏序关系中的顺序性系中的顺序性本讲稿第九页，共二十二页【实例实例】试判断下列关系是否为偏序关系：试判断下列关系是否为偏序关系：（1 1）集合）集合A A的幂集的幂集P P(A)(A)上的上的包含包含关系关系“”（2 2）实数集合实数集合R R上的上的小于小于等于关系等于关系“”（3 3）自然数集合自然数集合N N上的上的模模m m同余关系；同余关系；（4 4）自然数集合）自然数集合N N上的整除关系上的整除关系“|”；根据偏序关系的定义知根据偏序关系的定义知(1)(1)，(2)(2)，(4)(4)，所对应的关系，所对应的关系同时具有自反性，反对称性和传递性，所以都是偏同时具有自反

8、性，反对称性和传递性，所以都是偏序集序集 ；(3)(3)所对应的关系不具有反对称性，所对应的关系不具有反对称性，所以不是偏序集。所以不是偏序集。本讲稿第十页，共二十二页11相关概念相关概念定义定义4.24 x与与y可比可比设设R为非空集合为非空集合A上的偏序关系上的偏序关系,x,y A,x与与y 可比可比x y y x.x x,y yA A,如如 果果x x y y且不存在且不存在z z A A使得使得 x x z z y y,则称则称 y y覆盖覆盖x x.结论：结论：x,y A，下述几种情况发生其一且仅发生其一：，下述几种情况发生其一且仅发生其一：x y,y x,xy,x与与y不是可比的不

9、是可比的定义定义4.25R为非空集合为非空集合A上的偏序上的偏序,x,y A,x与与y 都可比，都可比，则称则称R为为全序全序.实例：数集上的小于或等于关系是全序关系实例：数集上的小于或等于关系是全序关系整除关系不是正整数集合上的全序关系整除关系不是正整数集合上的全序关系1,2,4,6集合上的整除关系集合上的整除关系,2覆盖覆盖1,4和和6覆盖覆盖2.但但4不覆盖不覆盖1.本讲稿第十一页，共二十二页12偏序集与哈斯图偏序集与哈斯图定义：定义：集合集合A和和A上的偏序关系上的偏序关系 一起叫做偏序集一起叫做偏序集,记作记作.实例：实例：整数集和数的小于等于关系构成偏序集整数集和数的小于等于关系构

10、成偏序集 幂集幂集P(A)和包含关系构成偏序集和包含关系构成偏序集.本讲稿第十二页，共二十二页 利用偏序自反、反对称、传递性简化的关系图：利用偏序自反、反对称、传递性简化的关系图：（1 1）由偏序关系是自反的，故关系图上每个节点都有）由偏序关系是自反的，故关系图上每个节点都有环，用小圆圈或点表示环，用小圆圈或点表示A A中的元素，省掉关系图中的中的元素，省掉关系图中的所有的环；所有的环；（因自反性（因自反性)（2 2）对任意）对任意x,yAx,yA，若，若x xy y，则将，则将x x画在画在y y的下的下方，方，可省掉关系图中所有边的箭头；可省掉关系图中所有边的箭头；（因反对称性）（因反对称

11、性）（3 3）具有覆盖关系的两个结点之间连边）具有覆盖关系的两个结点之间连边.即对任意即对任意x,yA(xy)x,yA(xy)，若，若x x y y，且，且x x与与y y之间不存在之间不存在zAzA，使得，使得x x z z y y，则，则x x与与y y之间用一条线相连，之间用一条线相连，否则无线相连。否则无线相连。（因传递性）（因传递性）哈斯图：哈斯图：本讲稿第十三页，共二十二页14哈斯图实例哈斯图实例例例例例 本讲稿第十四页，共二十二页练习练习115设设A=2,3,6,12,24,36，“”是是A上的整除关系上的整除关系R，画出其一般，画出其一般的关系图和哈斯图。的关系图和哈斯图。解解

12、由题意可得由题意可得R=,，从而得出该偏序集，从而得出该偏序集的一般关的一般关系图和哈斯图如下：系图和哈斯图如下：哈斯图哈斯图2 23 36 6121236362424关系图关系图2 23 36 6121236362424本讲稿第十五页，共二十二页16练习练习2已知偏序集已知偏序集的哈斯图如右图所示的哈斯图如右图所示,试求出集合试求出集合A和关系和关系R的表达式的表达式.解：解：A=a,b,c,d,e,f,g,hR=,IA 本讲稿第十六页，共二十二页174.7.2极值与最值极值与最值定义定义4.26设设为偏序集为偏序集,B A,yB.(1)若若 x(xBy x)成立成立,则称则称y 为为B 的

13、的最小元最小元.(2)若若 x(xBx y)成立成立,则称则称y 为为B 的的最大元最大元.(3)若若 x(xBx yx=y)成立成立,则称则称y 为为B的的极小元极小元.(4)若若 x(xBy xx=y)成立成立,则称则称y 为为B的的极大元极大元.本讲稿第十七页，共二十二页【性质性质】对于有穷集，极小元和极大元必存在，可能存在多个对于有穷集，极小元和极大元必存在，可能存在多个.最小元和最大元不一定存在，如果存在一定惟一最小元和最大元不一定存在，如果存在一定惟一.最小最小元一定是极小元；最大元一定是极大元元一定是极小元；最大元一定是极大元.【特定元素与哈斯图特定元素与哈斯图】如果图中有孤立结

14、点，那么这个结点既是极小元，如果图中有孤立结点，那么这个结点既是极小元，也是极大元，并且图中既无最小元，也无最大元也是极大元，并且图中既无最小元，也无最大元(除除了图中只有唯一孤立结点的特殊情况了图中只有唯一孤立结点的特殊情况)。除了孤立结点以外，其他的极小元是图中所有向下通除了孤立结点以外，其他的极小元是图中所有向下通路的终点，其他的极大元是图中所有向上通路的终点。路的终点，其他的极大元是图中所有向上通路的终点。图中唯一的极小元是最小元，唯一的极大元是最图中唯一的极小元是最小元，唯一的极大元是最大元；否则最小元和最大元不存在。大元；否则最小元和最大元不存在。本讲稿第十八页，共二十二页19定义

15、定义4.27设设为偏序集为偏序集,B A,y A.（1）若若 x(xBx y)成立成立,则称则称y 为为B 的的上界上界.（2）若若 x(xBy x)成立成立,则称则称y 为为B 的的下界下界.（3）令令Cy|y为为B的上界的上界,则称则称C的最小元为的最小元为B 的的最小上界最小上界或或上确界上确界.（4）令令Dy|y为为B的下界的下界,则称则称D的最大元为的最大元为B 的的最大下界最大下界或或下确界下确界.由由定义定义4.27可知以下性质：可知以下性质：1.下界、上界、下确界、上确界不一定存在于集合下界、上界、下确界、上确界不一定存在于集合B中中2.下界、上界存在不一定惟一下界、上界存在不

16、一定惟一3.下确界、上确界如果存在，则惟一下确界、上确界如果存在，则惟一4.子集子集B的最小元就是它的下确界，最大元就是它的上确界；反之的最小元就是它的下确界，最大元就是它的上确界；反之不对不对.偏序集的特定元素偏序集的特定元素本讲稿第十九页，共二十二页20实例实例练练3设偏序集设偏序集如下图所示，求如下图所示，求A 的极小元、最小元、的极小元、最小元、极大元、最大元极大元、最大元.设设Bb,c,d,求求B 的下界、上界、下的下界、上界、下确界、上确界确界、上确界.解：解：A的极小元：的极小元：a,b,c,g；极大元：极大元：a,f,h；没有最小元与最大元没有最小元与最大元.B的下界不存在的下

17、界不存在,上界有上界有d 和和f下确界不存在下确界不存在,上确界为上确界为d.本讲稿第二十页，共二十二页实例实例22练练5设集合设集合A=a,b,c,d,e,f,g,h，对应的哈斯图见下，对应的哈斯图见下图。令图。令B1=a,b，B2=c,d,e。求出。求出B1，B2的最大的最大元、最小元、极大元、极小元、上界、下界、上确元、最小元、极大元、极小元、上界、下界、上确界、下确界。界、下确界。【解解】B1和和B2的各种特殊元素见下表的各种特殊元素见下表。eabcdfgh集合集合最大元最大元 最小元最小元 极大元极大元 极小元极小元上界上界下下界界上确上确界界下确界下确界B1B2无无cd,echc,a,bhc无无无无a,ba,bc,d,e,f,g,h无无c无无本讲稿第二十二页，共二十二页