离散数学：第8讲 等价关系.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,等价关系,*,2025/6/16 周一,等价关系,1,自反、对称、传递闭包,定理,7.11:,设,R,A,A,且,A,则,(1),R,自反,r(R)=R,;,(2),R,对称,s(R)=R,;,(3),R,传递,t(R)=R,.,2025/6/16 周一,等价关系,2,定理,7.12,定理,7.12:,设,R,1,R,2,A,A,且,A,则,(1),r(R,1,),r(,R,2,),;,(2),s(R,1,),s(,R,2,),;,(3),t(R,1,),t(,R,2,),;,2025/6/16 周一,等价关系,3,定理,7.10,定理,7.10:,设,R,A,A,且,A,则,r(R)=,R,I,A,;,s(R)=R,R,-1,;,t(R)=R,R,2,R,3,.,推论,:,设,R,A,A,且 0,|A|,则,l N,使得,t(R)=R,R,2,R,3,R,l,2025/6/16 周一,等价关系,4,定理,7.13,定理,7.13,:设,R,A,A,且,A,则,(1),R,自反,s(R),和,t(R),自反;,(2),R,对称,r(R),和,t(R),对称;,(3),R,传递,r(R),传递。,2025/6/16 周一,等价关系,5,性质,1,性质,1:,设,R,1,R,2,A,A,且,A,则1),r(R,1,R,2,)=,r(R,1,),r(,R,2,),;,(2),s(R,1,R,2,)=,s,(R,1,),s(,R,2,),;,(3),t(R,1,R,2,),t,(R,1,),t(,R,2,).,2025/6/16 周一,等价关系,6,性质,2,性质,2:,设,R,A,A,且,A,则,(1),rs(R)=sr(R),;,(2),rt(R)=tr(R),;,(3),st(R),ts(R).,2025/6/16 周一,等价关系,7,等价关系,等价关系:设,R,AA,且,A,若,R,是,自反的,对称的,传递的,则称,R,为等价关系。,2025/6/16 周一,等价关系,8,内容提要,等价(,equivalence),关系,等价类,同余关系,商集,集合的划分,2025/6/16 周一,等价关系,9,例,1,例,1:,判断是否等价关系(,A,是某班学生):,R,1,=|x,y,Ax,与,y,同年生,R,2,=|x,y,Ax,与,y,同姓,R,3,=|x,y,Ax,的年龄不比,y,小,R,4,=|x,y,Ax,与,y,选修同门课程,R,5,=|x,y,Ax,的体重比,y,重,2025/6/16 周一,等价关系,10,例,1(,续),定义,自反,对称,传递,等价关系,R,1,x,与,y,同年生,R,2,x,与,y,同姓,R,3,x,的年龄不比,y,小,R,4,x,与,y,选修同门课程,R,5,x,的体重比,y,重,2025/6/16 周一,等价关系,11,例,2,例,2:,设,R,AA,且,A,对,R,依次求三种闭包共有6种不同顺序,其中哪些顺序一定导致等价关系?,rst(R),rts(R),str(R),srt(R),trs(R),tsr(R),2025/6/16 周一,等价关系,12,例,2(,续,1),tsr(R)=trs(R),=rts(R),str(R),=,srt(R),=rst(R),自反,对称,传递,等价关系,(等价闭包),2025/6/16 周一,等价关系,13,例,3,例,3:,设,A=1,2,3,4,5,8,则,R=|x,yA,x,y(mod 3),是否为等价关系,画出,R,的关系图.,1,4,2,5,8,3,R,是等价关系#,2025/6/16 周一,等价关系,14,等价类(,equivalence class),等价类:设,R,是,A,上等价关系,xA,x,R,=y|yAxRy,称为,x,关于,R,的等价类,简称,x,的等价类,简记为,x.,X,的等价类是,A,中所有与,x,等价的元素构成的集合。,2025/6/16 周一,等价关系,15,例,3,（续）,例,3:,设,A=1,2,3,4,5,8,等价关系,R=|x,yA,x,y(mod 3),的等价类如下：,1,4,2,5,8,3,1=4=1,4,2=5=8=2,5,8,33.#,2025/6/16 周一,等价关系,16,同余关系:对于任意大于的自然数,n,x,yZ,则,x,与,y,模,n,同余,(,be congruent module n),x,y(mod n)n|(x-y)x-y=kn(kZ),同余关系是等价关系,0 =kn|kZ,1 =1+kn|kZ,2 =2+kn|kZ,n-1=(n-1)+kn|kZ.,同余(,congruence),关系,6,3,9,8,7,5,4,2,1,10,11,0,2025/6/16 周一,等价关系,17,定理,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.,证明:(1),R,自反,xRxx,x,R,x,R,.,x,2025/6/16 周一,等价关系,18,定理,7.14(,证明(2),(2),xRy x,R,=y,R,;,证明:(2)只需证明,x,R,y,R,和,x,R,y,R.,()z,zx,R,xRy,zRxxRy,zRy zy,R,.,x,R,y,R,.,(,)同理可证.,x,y,z,2025/6/16 周一,等价关系,19,定理,7.14(,证明(3),(3),xRy x,R,y,R,=;,证明:(3)(反证)假设,z,zx,R,y,R,则,zx,R,y,RzRxzRy xRzzRy,xRy,这与,xRy,矛盾!,x,R,y,R,=.,x,y,z,2025/6/16 周一,等价关系,20,定理,7.14(,证明(4),(4),U x,R,|xA =A.,证明:(4),A=,U x|xA,U x,R,|xA U A,|xA=A.,U x,R,|xA =A.#,x,y,2025/6/16 周一,等价关系,21,商集(,quotient set),商集:设,R,是,A,上等价关系,A/R=x,R,|x,A,称为,A,关于,R,的商集,简称,A,的商集.,(,即,:,以,R,的所有等价类作为元素的集合,),例,11(,续),（,Slide 13,）,A/R,=1,4,2,5,8,3.,2025/6/16 周一,等价关系,22,例,4,例:考虑,A=a,b,c,上的等价关系.,解:,I,A,E,A,R,1,=I,A,R,2,=I,A,R,3,=I,A,对应的商集分别是什么？,A,上是否还有其他等价关系？,2025/6/16 周一,等价关系,23,例,4,（续）,例,4(2):,设,A=a,1,a,2,a,n,I,A,E,A,R,ij,=I,A,都是,A,上等价关系,求对应的商集,其中,a,i,a,j,A,ij.,2025/6/16 周一,等价关系,24,例,4,（续,2,）,解:,A/,I,A,=,a,1,a,2,a,n,A/,E,A,=,a1,a,2,a,n,A/,R,ij,=,A/,I,A,a,i,a,j,-,a,i,a,j,2025/6/16 周一,等价关系,25,覆盖和划分(,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/6/16 周一,等价关系,26,划分的加细(,refinement,),定义:,A,1,A,2,A,r,与,B,1,B,2,B,s是同一个集合,A,的两种划分，若对于每一个,A,i,都有,B,j,使得,A,i,B,j,则,A,1,A,2,A,r,称为是,B,1,B,2,B,s,的加细。,2025/6/16 周一,等价关系,27,例,4,例:考虑,A=a,b,c,上的划分.,解:,a,b,c,a,b,c,a,b,c,a,b,c,a,b,c,加细,加细,加细,加细,加细,加细,#,如何确定一个集合上的划分个数？,2025/6/16 周一,等价关系,28,例,5,例,13:,问,A=a,b,c,d,有多少种划分?,2025/6/16 周一,等价关系,29,Bell,数(,Bell number),问题:给,n,个对象进行分类共有多少种分法?,答案:,Bell,数,(Eric Temple Bell,18831960),Proof:,We count the number of partitions of a set of n+1 elements,depending on the,size,of the,block,containing the n+1 st element.If the block has size j for then we have choices for the n other elements of the block.The remaining n+1-j elements can be partitioned in B(n+1j)ways.We have therefore that:,2025/6/16 周一,等价关系,30,Bell,数表,n,B,n,n,B,n,1,1,8,4,140,2,2,9,21,147,3,5,10,115,975,4,15,11,678,570,5,52,12,4,213,597,6,203,13,27,644,437,7,877,14,190,899,322,2025/6/16 周一,等价关系,31,第二类,Stirling,数性质,Stirling,子集数(,Stirling subset number,):把,n,个对象分成,k,个非空子集的分法个数.,递推公式:,分析：,设有,n,个不同的球，分别用,T1,T2,.,Tn,表示。从中取出一个球,Tn,，,Tn,的放法有以下两种：,1.Tn,独占一个盒子，那么剩下的球只能放在,k-1,个盒子里，方案数为,S,（,n-1,k-1);,2.Tn,与别的球共占一个盒子，那么可以将,T1,T2,.,Tn-1,这,n-1,个球放入,k,个盒子里，然后将,Tn,放入其中一个盒子中，方案数为,k*S(n-1,k).,2025/6/16 周一,等价关系,32,Stirling,子集数,递推公式:,剔除一个,其余分,k,类,加入一类,其余分,k-1,类,自成一类,2025/6/16 周一,等价关系,33,第二类,Stirling,数表,nk,0,1,2,3,4,5,6,7,8,9,0,1,1,0,1,2,0,1,1,3,0,1,3,1,4,0,1,7,6,1,5,0,1,15,25,10,1,6,0,1,31,90,65,15,1,7,0,1,63,301,350,140,21,1,8,0,1,127,966,1,170,1,050,266,28,1,9,0,1,255,3,035,7,770,6,951,2,646,462,36,1,10,0,1,511,9,330,34,501,42,525,22,827,5,880,750,45,2025/6/16 周一,等价关系,34,等价关系与划分是一一对应的,定理:设,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/6/16 周一,等价关系,35,例,6,例,6,:,A=a,b,c,求,A,上全体等价关系.,解:,A,上不同划分共有5种:,a,b,c,a,b,c,a,b,c,a,b,c,a,b,c,R,1,=E,A,R,2,=,I,A,R,3,=,I,A,R,4,=,I,A,R,5,=,I,A,.,#,2025/6/16 周一,等价关系,36,例,5,例,5:,问,A=a,b,c,d,上有多少种等价关系?,解:,2025/6/16 周一,等价关系,37,作业,P133,：,31-34,39,41,