等价关系与偏序关系精选PPT.ppt

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

1、等价关系与偏序关等价关系与偏序关系系第1页，此课件共22页哦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页，此

2、课件共22页哦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的等价类的等价类.等价类等价类第3页，此课件共22页哦4集合的划分集合的划分定义定义4.21设设A为非空集合为非空集合,若

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

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

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

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

7、在偏序关而指在偏序关系中的顺序性系中的顺序性第9页，此课件共22页哦【实例实例】试判断下列关系是否为偏序关系：试判断下列关系是否为偏序关系：（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)所对应的关系不具有反对称性，所对应的关系不具有反对称性，所以不是偏序集。所以不是偏序集。第10页，此课件共22页哦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.第11页，此课件共22页哦12偏序集与哈斯图偏序集与哈斯图定义：定义：集合集合A和和A上的偏序关系上的偏序关系 一起叫做偏序集一起叫做偏序集,记作记作.实例：实例：整数集和数的小于等于关系构成偏序集整数集和数的小于等于关系

10、构成偏序集 幂集幂集P(A)和包含关系构成偏序集和包含关系构成偏序集.第12页，此课件共22页哦 利用偏序自反、反对称、传递性简化的关系图：利用偏序自反、反对称、传递性简化的关系图：（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之间用一条线相连，之间用一条线相连，否则无线相连。否则无线相连。（因传递性）（因传递性）哈斯图：哈斯图：第13页，此课件共22页哦14哈斯图实例哈斯图实例例例例例 第14页，此课件共22页哦练习练习115设设A=2,3,6,12,24,36，“”是是A上的整除关系上的整除关系R，画出其一，画出其一般的关系图和哈斯图。般的关系图和哈斯图。解

12、解由题意可得由题意可得R=,，从而得出该偏序集，从而得出该偏序集的一般关系图的一般关系图和哈斯图如下：和哈斯图如下：哈斯图哈斯图2 23 36 6121236362424关系图关系图2 23 36 6121236362424第15页，此课件共22页哦16练习练习2已知偏序集已知偏序集的哈斯图如右图所示的哈斯图如右图所示,试求出集合试求出集合A和关系和关系R的表达式的表达式.解：解：A=a,b,c,d,e,f,g,hR=,IA 第16页，此课件共22页哦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的的极大元极大元.第17页，此课件共22页哦【性质性质】对于有穷集，极小元和极大元必存在，可能存在多对于有穷集，极小元和极大元必存在，可能存在多个个.最小元和最大元不一定存在，如果存在一定惟一最小元和最大元不一定存在，如果存在一定惟一.最小元一定是极小元；最大元一定是极大元最小元一定是极小元；最大元一定是极大元.【特定元素与哈斯图特定元素与哈斯图】如果图中有孤立

14、结点，那么这个结点既是极小元，如果图中有孤立结点，那么这个结点既是极小元，也是极大元，并且图中既无最小元，也无最大元也是极大元，并且图中既无最小元，也无最大元(除了除了图中只有唯一孤立结点的特殊情况图中只有唯一孤立结点的特殊情况)。除了孤立结点以外，其他的极小元是图中所有向下通路除了孤立结点以外，其他的极小元是图中所有向下通路的终点，其他的极大元是图中所有向上通路的终点。的终点，其他的极大元是图中所有向上通路的终点。图中唯一的极小元是最小元，唯一的极大元是最图中唯一的极小元是最小元，唯一的极大元是最大元；否则最小元和最大元不存在。大元；否则最小元和最大元不存在。第18页，此课件共22页哦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的最小元就是它的下确界，最大元就是它的上确界；反的最小元就是它的下确界，最大元就是它的上确界；反之不对之不对.偏序集的特定元素偏序集的特定元素第19页，此课件共22页哦20实例实例练练3设偏序集设偏序集如下图所示，求如下图所示，求A 的极小元、最小元、的极小元、最小元、极大元、最大元极大元、最大元.设设Bb,c,d,求求B 的下界、上界、下的下界、上界、下确界、上确界确界、上确界.解：解：A的极小元：的极小元：a,b,c,g；极大元：极大元：a,f,h；没有最小元与最大元没有最小元与最大元.B的下界不存在的

17、下界不存在,上界有上界有d 和和f下确界不存在下确界不存在,上确界为上确界为d.第20页，此课件共22页哦实例实例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无无第22页，此课件共22页哦