离散数学：第9讲 偏序关系.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,偏序关系,*,2025/5/16 周五,偏序关系,1,回顾,等价关系:设,R,AA,且,A,若,R,是,自反的,对称的,传递的,则称,R,为等价关系,等价类:设,R,是,A,上等价关系,xA,x,R,=y|yAxRy,称为,x,关于,R,的等价类,简称,x,的等价类,简记为,x.,商集:设,R,是,A,上等价关系,A/R=x,R,|x,A,称为,A,关于,R,的商集,简称,A,的商集.,2025/5/16 周五,偏序关系,2,定理,7.14,定理,7.14,:设,R,是,A,上等价关系,x,yA,(1),x,R,(2),xRy x,R,=y,R,;,(3),xRy x,R,y,R,=;,(4),U x,R,|xA =A.,2025/5/16 周五,偏序关系,3,覆盖和划分(,partition),设,A,S=A,1,A,2,A,n,P,(A),若,A,满足,(1),A,i,;,(2),A,i,=A,(,3),A,i,A,j,=(ij),则称,S,为,A,的一个,划分,A,中元素称为划分块(,block).,若只满足(1)(2)则称,S,为,A,的一个覆盖.,2025/5/16 周五,偏序关系,4,等价关系与划分是一一对应的,定理:设,A,则,(1),R,是,A,上等价关系,A/R,是,A,的划分,(2),A,是,A,的划分,R,A,是,A,上等价关系,其中,xR,A,y,B(B,A,xB yB),R,A,称为由划分,A,所定义的等价关系(同块关系),.,#,2025/5/16 周五,偏序关系,5,如何确定一个集合上的划分个数,问,A=a,b,c,d,上有多少种等价关系?,解:,2025/5/16 周五,偏序关系,6,偏序(,partial order),关系,偏序关系:设,R,AA,且,A,若,R,是,自反的,反对称的,传递的,则称,R,为偏序关系,用,“,”,表示偏序关系,读作,“,小于等于,”,R xRy x,y,“,严格小于,”,:,x,y,x,y xy,偏序集(,poset):,是,A,上偏序关系,2025/5/16 周五,偏序关系,7,举例,1,（偏序集）,AR,（实数集），,A,上的小于等于关系：,=|x,yA x,y,A=1,3,6,12,，偏序集,=,=|x,yA xy,2025/5/16 周五,偏序关系,8,举例,2,AZ,+,=,x|xZ x0,|=|x,yA x|y,A=1,2,3,4,5,6,9,10,15,=,2025/5/16 周五,偏序关系,9,举例3,=|x,yP(A)xy,设,A=a,b,P(A)=,a,b,a,b,=,I,P(A),注：,P(A),的任意子集关于包含关系都做成偏序集,2025/5/16 周五,偏序关系,10,举例4,A,是由,A,的一些划分组成的集合,加细,=|x,y,x,是,y,的加细,设,A=a,b,c,A,1,=a,b,c,A,2,=a,b,c,A,3,=b,a,c,A,4,=c,a,b,A,5,=a,b,c,取,1,=,A,1,A,2,2,=,A,2,A,3,3,=,A,1,A,2,A,3,A,4,A,5,1,=,I,1,2,=,I,2,3,=,I,3,.#,2025/5/16 周五,偏序关系,11,偏序关系,偏序关系表示,哈斯图,特殊元素,(反)链,线序(全序,),拟序,良序,2025/5/16 周五,偏序关系,12,偏序关系的表示,2025/5/16 周五,偏序关系,13,COV A,设,是偏序集,x,yA,若,x,y y,x,则称,x,与,y,是可比的,任意,x,y,有三种情况：,x,y,（或,y,x,）、,x=y,、,x,与,y,不是可比的,覆盖(,cover),或盖住:,y,盖住,x,x,y x,y,z(zAz,yz,xx,z,y),记,COV A,|x,yA,；,y,盖住,x,2025/5/16 周五,偏序关系,14,例1,例1:,A=1,2,3,4,5,6,9,10,15,=,COV A=,对于偏序集,，,盖住关系是,唯一的！,2025/5/16 周五,偏序关系,15,哈斯图(,Hasse diagram),哈斯图:,小圆圈,代表,元素,；,如果,y,盖住,x,时,在,x,与,y,之间画,无向边,如果,x,y x,y,，,则,x,画在,y,下方,2025/5/16 周五,偏序关系,16,例,2,（,1,）,画出下列偏序关系的哈斯图.,A=1,2,3,4,5,6,9,10,15,1,2,4,3,6,9,15,5,10,2025/5/16 周五,偏序关系,17,例,2(2),画出下列偏序关系的哈斯图.,A=a,b,c,SP(A),S=,a,b,c,a,b,b,c,a,c,a,b,c,a,b,a,c,b,c,2025/5/16 周五,偏序关系,18,例,2(3),画出下列偏序关系的哈斯图.,=,A,1,A,2,A,3,A,4,A,5,A,6,A=a,b,c,d,A,1,=a,b,c,d,A,2,=a,b,c,d,A,3,=a,c,b,d,A,4,=a,b,c,d,A,5,=a,b,c,d,A,6,=a,b,c,d,A,1,A,2,A,5,A,3,A,4,A,6,2025/5/16 周五,偏序关系,19,偏序关系中的特殊元素,最大元,最小元,极大元,极小元,上界,下界,最小上界(上确界),最大下界(下确界),2025/5/16 周五,偏序关系,20,最大元,最小元,设,为偏序集,BA,yB,最大元,(maximum/greatest element):,y,是,B,的最大元,x(xB x,y),最小元,(minimum/least element):,y,是,B,的最小元,x(xB y,x),2025/5/16 周五,偏序关系,21,最大元,最小元举例(例1(1),A=1,2,3,4,5,6,9,10,15,B,1,=1,2,3,B,2,=3,5,15,B,3,=A.,1,2,4,3,6,9,15,5,10,1,2,4,3,6,9,15,5,10,B,1,的最大元是？,B,1,的最小元是？,B,2,的最大元是？,B,2,的最小元是？,B,3,的最大元是？,B,3,的最小元是？,15,1,1,2025/5/16 周五,偏序关系,22,极大元,极小元,设,为偏序集,BA,yB,极大元,(maximal element):,y,是,B,的极大元,x(xB y,x x=y),极小元,(minimal element):,y,是,B,的极小元,x(xB x,y x=y),2025/5/16 周五,偏序关系,23,极大元,极小元举例(例1(1),A=1,2,3,4,5,6,9,10,15,B,1,=1,2,3,B,2,=3,5,15,B,3,=A.,B,1,的极大元是？,B,1,的极小元是？,B,2,的极大元是？,B,2,的极小元是？,B,3,的极大元是？,B,3,的极小元是？,1,2,4,3,6,9,15,5,10,1,2,4,3,6,9,15,5,10,2,3,15,4,6,9,15,10,1,3,，5,1,2025/5/16 周五,偏序关系,24,上界,下界,设,为偏序集,BA,yA,上界,(upper bound):,y,是,B,的上界,x(xB x,y),下界,(lower bound):,y,是,B,的下界,x(xB y,x),2025/5/16 周五,偏序关系,25,上界,下界举例,A=1,2,3,4,5,6,9,10,15,B,1,=1,2,3,B,2,=3,5,15,B,3,=A.,B,1,的上界是？,B,1,的下界是？,B,2,的上界是？,B,2,的下界是？,B,3,的上界是？,B,3,的下界是？,1,2,4,3,6,9,15,5,10,1,2,4,3,6,9,15,5,10,6,15,1,1,1,2025/5/16 周五,偏序关系,26,最小上界,最大下界,设,为偏序集,BA,最小上界,(,L,east,U,pper,B,ound):,设,C=y|y,是,B,的上界,C,的最小元称为,B,的,最小上界,或上确界,.,最大下界,(,G,reatest,L,ower,B,ound):,设,C=y|y,是,B,的下界,C,的最大元称为,B,的,最大下界,或下确界,.,2025/5/16 周五,偏序关系,27,最小上界,最大下界举例,A=1,2,3,4,5,6,9,10,15,B,1,=1,2,3,B,2,=3,5,15,B,3,=A.,B,1,的最小上界是,？,B,1,的最大下界是？,B,2,的最小上界是？,B,2,的最大下界是,？,B,3,的最小上界是？,B,3,的最大下界是,？,1,2,4,3,6,9,15,5,10,1,2,4,3,6,9,15,5,10,6,15,1,1,1,2025/5/16 周五,偏序关系,28,特殊元素比较,存在(,B,非空有穷),存在(,B,无穷),唯一,B,最大元,(表示,不一定,),最小元,极大元,(表示,一定,),B=Z,极小元,上界,下界,上确界,下确界,2025/5/16 周五,偏序关系,29,链(,chain),设,为偏序集,BA,链(,chain),:,B,是,A,中的链,xy(xByB,x,y y,x,),|,B|,称为链的长度,x,与,y,可比,2025/5/16 周五,偏序关系,30,反链(,antichain),设,为偏序集,BA,链(,chain),:,B,是,A,中的链,xy(xByB x,与,y,可比),反链(,antichain),:,B,是,A,中的反链,xy(xByBxy x,与,y,不可比),|,B|,称为反链的长度,2025/5/16 周五,偏序关系,31,链,反链(举例),设,偏序集,如图所示,A=a,b,k.,a,b,c,d,e,f,g,h,i,j,k,B,1,=a,c,d,e,是长为4的链,上界,e,f,g,h,上确界,e,下界,a,下确界,a,B,2,=a,e,h,是长为3的链,B,3,=b,g,是长为2的链,B,4,=g,h,k,是长为3的反链,上界,下界,上确界,下确界:无,B,5,=a,是长为1的链和反链,B,6,=a,b,g,h,既非链,亦非反链,2025/5/16 周五,偏序关系,32,全序(,total order),关系,全序关系,:若,偏序集,满足,xy,(xAyA,x,与,y,可比,),则称,为全序关系,称,为,全序集,全序关系亦称,线序,(,linear order),关系,例,:,2025/5/16 周五,偏序关系,33,拟序(,quasi-order),关系,拟序关系,:设,R,AA,且,A,若,R,是,反自反的,传递的,则称,R,为拟序关系,通常用,表示拟序关系(对比:,“,严格小于,”,),反自反性,与,传递性,蕴涵,反对称性,拟序集,:,是,A,上拟序关系,例子:,设,AR,BZ,+,A,|,=|x,yB x,|,y x,y,2025/5/16 周五,偏序关系,34,三歧性(,trichotomy),三歧性:设,是非空集合,A,上拟序关系,若,x,y,x=y,yx,中有且仅有一式成立,则称,具有,三歧性.,拟全序关系:设,是非空集合,A,上拟序关系,若,具有,三歧性,则,称,为拟全序关系,或拟线序关系,称,为拟线序集.,2025/5/16 周五,偏序关系,35,良序(,well-order),良序关系:设,为偏序集,若,A,的任何非空子集,B,均有最小元,则称,为良序关系,为良序集,例:,是良序集,不是良序集,良序原理(,well-ordering principle,):每一个集合都可以良序化(建立良序关系),良序原理等价于选择公理,良序集可做超限(,transfinite),归纳证明,2025/5/16 周五,偏序关系,36,作业,P134:43-49,