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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2021/10/3,#,离散数学,集合论,1,第1页,主要内容,集合代数,二元关系,函数,集合基本概念,集合运算,有穷集合计数,集合恒等式,有序对与笛卡儿积,二元关系,关系运算,关系性质,关系闭包,等价关系与划分,偏序关系,函数定义与性质,函数复合与反函数,双射函数与集合基数,2,第2页,7.6 等价关系与划分,例7.16,设 A=1,2,8,定义 A 上关系 R以下:,验证R是A上等价关系.,一.等价关系,定义7.15,设R为非空集合A上关系.假如R是,自反,对称,和,传递,则称R为A上等价关系.,对等价关系R,若,R,则称,x,等价于,y,记为,xy,or,xRy,.,解,:,x,A,有 ,故R是自反.,x,y,A,若 ,则 ,故R是对称.,x,y,z,A,若 ,则 ,故 R是传递.,R是A上一个等价关系.,3,第3页,等价类,定义 7.16,设 R 为非空集合A上等价关系,x,A,令,称,x,R,为,x,在R下等价类(简称为x等价类),有时简记为,x,.,x,称为该等价类代表元.,注,:一个等价类是A中在等价关系R下彼此等价全部元素集,合,等价类中各元素地位是平等,每个元素都能够作为,其所在等价类代表元.,比如,在上例中等价关系R下,A中元素形成了三个等价类:,1,=,4,=,7,=1,4,7;,2,=,5,=,8,=2,5,8;,3,=,6,=3,6.,4,第4页,等价类性质,定理7.14,设 R 为非空集合 A上等价关系,则,（1）,x,A,x,是A非空子集.,（2）,x,y,A,假如xRy,则,x,=,y,（3）,x,y,A,假如x与y不具相关系 R,则,x,与,y,不相交.,（4）x|xA =A,证,：(1)显然.,(2)z,x,R,R（R是对称）,R,R,R,R,z,y,从而,x,y,同理可得,y,x,.故,x,=,y,5,第5页,等价类性质,(3)反证法.,假设,x,y,则存在 z,x,y,.,因而 z,x,且z,y,即,R,R.,依据R对称性和传递性,必有,R.这与前提条件矛盾.,故原命题成立.,(4),先证,再证,所以,6,第6页,商集与划分,定义7.17,设R为非空集合A上等价关系,以R全部等价类作为元素,形成集合称为A关于R,商集,记为A/R,即:,比如,:例7.16中等价关系形成商集为:,A/R 1,4,7,2,5,8,3,6,定义7.18,设A为非空集合,若A子集族,(,P(A),是由A一些子集形,成集合)满足以下条件:,(1),(2),x,y(x,y,xyxy=,),(3),则称,是A一个,划分,而称,中元素为 A划分块或类.,五.集合划分,7,第7页,等价关系与划分,例7.17 设A=a,b,c,d,则,1,=a,b,c,d和,2,=a,b,c,d都是A划分,而,3,=a,a,b,c,d和,4,=,a,b,c都不是A划分.,注:给定非空有限集A上一个等价关系R,在R下彼此等价元素组成子集便形成了A一个划分,它其实就是商集A/R,其每个类(等价块)就是R一个等价类;,反之,任给A一个 划分,可定义A上关系R以下:,R=,x,y,Ax与y在,同一个类中,能够验证R是A上一个等价关系.可见A上等价关系与A划分是一一对应.,8,第8页,例,例7.18,求A=1,2,3上全部等价关系.,解,先求出A全部划分:,1,=1,2,3;,2,=1,2,3；,3,=2,1,3;,4,=3,1,2;,5,=1,2,3.,与这些划分一一对应等价关系是:,1,:全域关系E,A,2,:R,2,=,I,A,3,:R,3,=,I,A,4,:R,4,=,I,A,5,:恒等关系I,A,9,第9页,7.7 偏序关系,偏序关系与偏序集,定义7.19,设R为非空集合A上关系.假如R是,自反,反对称,和,传递,则称 R 为 A上偏序关系,记为 .,对一个偏序关系 ,假如,则记为 x y.,注,:,1.集合A上恒等关系I,A,和空关系都是A上偏序关系,但全域关系E,A,普通不是A上偏序关系.,2.实数域上小于等于关系（大于等于关系）,自然数域上整除关系,集合包含关系等都是偏序关系.,10,第10页,可比与不可比,注,:在含有偏序关系集合A中任二元素 x 和 y 之间必有以下四,种情形之一:,xy,yx,x=y,x与y不可比.,例,设A=1,2,3,是A上整除关系,则:12,13,11,22,33,2 和 3 不可比;,(2)是 A 上大于等于关系,则:2 1,3 1,3 2,11,22,33.,定义7.20,设R为非空集合A上偏序关系,定义,(1),x,y,A,x y当且仅当 x y且 xy(2),x,y,A,x 与 y 可比当且仅当 x y 或 y x,11,第11页,偏序集,定义7.21,设R为非空集合A上偏序关系,假如,x,y,A,x 与 y 都是可比,则称R为A上全序关系.,比如,大于等于关系(小于等于关系)是全序集,但整除关系普通不是全序集.,定义7.22,带有某种指定偏序关系 集合A称为偏序集,记为.,比如,整数集Z和数小于等于关系组成偏序集;,集合A幂集P(A)和集合包含关系,组成偏序集.,定义7.23,设 为偏序集,x,y,A,假如 x y且不存在 z,A,使得x z y,则称 y 覆盖 x.,比如,A=1,2,4,6上整除关系,有2覆盖1,4和6都覆盖2,但4不覆盖1,6不覆盖4.,12,第12页,哈斯图,利用偏序关系自反性,反对称性和传递性可简化偏序关系关系图,得到偏序集哈斯图.,设有偏序集,其哈斯图画法以下:,(1)以 A 元素作为顶点,适当排列各顶点次序,使得对,x,y,A,若x y,则将 x 画在 y 下方.,(2)对A中两个不一样元素x和y,假如y覆盖x,则用一条线段连接 x 和 y.,例7.19,画出偏序集1,2,3,9,R,整除,和哈斯图.,解:它们哈斯图分别为图A,图B表示以下:,8,4,7,2,3,6,9,5,1,图A,a,b,a,b,c,a,b,b,c,c,a,c,图B,13,第13页,例,例7.20,已知偏序集哈斯图以下:求集合A和关系R表示式.,a,e,d,f,h,g,b,c,解 A=a,b,c,d,e,f,g,h,R=,I,A.,14,第14页,特殊元素,定义7.24,设 为偏序集,B,A,y,B.,(1)若,x(x,Byx)成立,则称 y 是B最小元;,(2)若,x(x,Bxy)成立,则称 y 是B最大元;,(3)若,x(x,Bxyx=y)成立,则称 y 是B极小元;,(4)若,x(x,Byxx=y)成立,则称 y 是B极大元.,注:,极大(极小)元未必是最大(最小)元.极大(极小)元未必与B中任何元素都可比;,(2)对有限集B,极大(极小)元一定存在,但最大(最小)元不一定存在;,(3)最大(最小)元假如存在,必定是唯一;而极大(极小)元普通不唯一.但假如B中只有一个极大(极小)元,则它一定是B最大(最小)元.,15,第15页,例,解,:极大元:a,f,h;极小元:a,b,c,g;无最大元和最小元.,例7.21,求上例中A极大元,极小元,最大元,最小元,例7.22,设x为集合,A=P(x)-,-x,且A,若|x|=n,问:,(1)偏序集 是否有最大元?,(2)偏序集 是否有最小元?,(3)偏序集 中极大元和极小元普通形式是什么?,解,:首先,因A,故n2,x中单个元素组成子集都在 A中,他们在 R,下相互不可比,所以A中无最大元和最小元.,例,x=1,2,3,A=1,2,3,1,2,1,3,2,3,和 x 不是A中元素,故A中无最小元和最大元,1,2,3 都是极小元;1,2,1,3,2,3 都是极大元,16,第16页,例,其次考查(P(x),R,),哈斯图.,其最低层是空集,记为第0层,由底向上,第1层是单元集,第2层是二元子集,第n-1层是x全部n-1元子集,最顶层即第n层,只有一个顶点x.,偏序集,哈斯图是由哈斯图去掉第0层与第n层得到,故x全部单元集都是,极小元,x全部n-1元子集都是,极大元.,17,第17页,特殊元素,定义7.25,设为偏序集,B,A,y,A.,(1)若,x(x,Bxy)成立,则称y为B上界;(2)若,x(x,Byx)成立,则称y为B下界;(3)令 Cy|y为B上界,则称C最小元为B最小上界或上确界;(4)令 Dy|y为B下界,则称D最大元为B最大下界或下确界.,注:,B最大元(最小元)必定是B上界(下界),也是B上确界(下确界).,2.B上界和上确界都未必是B最大元,因它们可能不在B中.同理,下界和下确也未必是B最小元.,3.B上界,上确界,下界,下确界都可能不存在.但假如上确界(下确界)存在,则它是唯一.,18,第18页,该休息啦,第19页,