《北大离散数学》PPT课件.ppt

《《北大离散数学》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8讲等价关系与序关系内容提要等价关系,等价类,商集划分,第二类Stirling数偏序,线序,拟序,良序哈斯图特殊元素:最?元,极?元,?界,?确界(反)链2021/10/41《集合论与图论》第8讲等价(equivalence)关系定义同余关系等价类商集划分划分的加细Stirling子集数2021/10/42《集合论与图论》第8讲等价(equivalence)关系定义等价关系:设RAA且A,若R是自反的,对称的,传递的,则称R为等价关系例9:判断是否等价关系(A是某班学生):R1={

2、,y>

3、x,yAx与y同年生}R2={

4、x,yAx与y同姓}R3={

5、x,yAx的年龄不比y小}R4={

6、x,yAx与y选修同门课程}R5={

7、x,yAx的体重比y重}2021/10/43《集合论与图论》第8讲例9(续)定义自反对称传递等价关系R1x与y同年生R2x与y同姓R3x的年龄不比y小R4x与y选修同门课程R5x的体重比y重2021/10/44《集合论与图论》第8讲例10例10:设RA

8、A且A,对R依次求三种闭包共有6种不同顺序,其中哪些顺序一定导致等价关系?rst(R),rts(R),str(R),srt(R),trs(R),tsr(R)=t(s(r(R)))解:st(R)ts(R),sr(R)=rs(R),…tsr(R)=trs(R)=rts(R)str(R)=srt(R)=rst(R)2021/10/45《集合论与图论》第8讲例10(续)tsr(R)=trs(R)=rts(R)str(R)=srt(R)=rst(R)自反对称传递等价关系(等价闭包)2

9、021/10/46《集合论与图论》第8讲等价类(equivalenceclass)等价类:设R是A上等价关系,xA,令[x]R={y

10、yAxRy},称[x]R为x关于R的等价类,简称x的等价类,简记为[x].等价类性质:[x]R;xRy[x]R=[y]R;xRy[x]R[y]R=;U{[x]R

11、xA}=A.2021/10/47《集合论与图论》第8讲定理27定理27:设R是A上等价关系,x,yA,(1)[x]R(2)xRy[x]R=[y]R;(3)xRy

12、[x]R[y]R=;(4)U{[x]R

13、xA}=A.证明:(1)R自反xRxx[x]R[x]R.x2021/10/48《集合论与图论》第8讲定理27(证明(2))(2)xRy[x]R=[y]R;证明:(2)只需证明[x]R[y]R和[x]R[y]R.()z,z[x]RxRyzRxxRyzRyz[y]R.[x]R[y]R.()同理可证.xyz2021/10/49《集合论与图论》第8讲定理27(证明(3))(3)xRy[x]R[y]R=;证明

14、:(3)(反证)假设z,z[x]R[y]R,则z[x]R[y]RzRxzRyxRzzRyxRy,这与xRy矛盾![x]R[y]R=.xyz2021/10/410《集合论与图论》第8讲定理27(证明(4))(4)U{[x]R

15、xA}=A.证明:(4)A=U{{x}

16、xA}U{[x]R

17、xA}U{A

18、xA}=A.U{[x]R

19、xA}=A.#xy2021/10/411《集合论与图论》第8讲同余关系:设n{2,3,4,…},x,yZ,则x与y模n同余(be

20、congruentmodulon)xy(modn)n

21、(x-y)x-y=kn(kZ)同余关系是等价关系[0]={kn

22、kZ},[1]={1+kn

23、kZ},[2]={2+kn

24、kZ},…,[n-1]={(n-1)+kn

25、kZ}.同余(congruence)关系639875421101102021/10/412《集合论与图论》第8讲例11例11:设A={1,2,3,4,5,8},求R3={

26、x,yAxy(mod3)}的等价类,画出R3的关系图.解:[1]=[4]={

27、1,4},[2]=[5]=[8]={2,5,8},[3]={3}.#1425832021/10/413《集合论与图论》第8讲商集(quotientset)商集:设R是A上等价关系,A/R={[x]R

28、xA}称为A关于R的商集,简称A的商集.显然UA/R=A.例11(续):A/R3={{1,4},{2,5,8},{3}}.2021/10/414《集合论与图论》第8讲例12(1)例12(1):设A={a1,a2,…,an},IA,EA,Rij=IA{,}都是A上等