最新北大离散数学08教学教材.ppt

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

1、等价(equivalence)关系定义同余关系等价类商集划分划分的加细Stirling子集数2021/8/182《集合论与图论》第8讲等价(equivalence)关系定义等价关系:设RAA且A,若R是自反的,对称的,传递的,则称R为等价关系例9:判断是否等价关系(A是某班学生):R1={

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

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

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

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

6、x,yAx的体重比y重}2

7、021/8/183《集合论与图论》第8讲例9(续)定义自反对称传递等价关系R1x与y同年生R2x与y同姓R3x的年龄不比y小R4x与y选修同门课程R5x的体重比y重2021/8/184《集合论与图论》第8讲例10例10:设RA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)

8、=rts(R)str(R)=srt(R)=rst(R)2021/8/185《集合论与图论》第8讲例10(续)tsr(R)=trs(R)=rts(R)str(R)=srt(R)=rst(R)自反对称传递等价关系(等价闭包)2021/8/186《集合论与图论》第8讲等价类(equivalenceclass)等价类:设R是A上等价关系,xA,令[x]R={y

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

10、[y]R=;U{[x]R

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

12、xA}=A.证明:(1)R自反xRxx[x]R[x]R.x2021/8/188《集合论与图论》第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

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

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

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

16、xA}U{A

17、xA}=A.U{[

18、x]R

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

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

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

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

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

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

25、8},求R3={

26、x,yAxy(mod3)}的等价类,画出R3的关系图.解:[1]=[4]={1,4},[2]=[5]=[8]={2,5,8},[3]={3}.#1425832021/8/1813《集合论与图论》第8讲商集(quotientset)商集:设R是A上等价关系,A/R={[x]R

27、xA}称为A关于R的商集,简称A的商集.显然UA/R=A.例11(续):A/R3={{1,4},{2,5,8},{3}}.2021/8/1814《集合论与图论》第8讲例12(1)例12(1):设A={a1,a2,…,

28、an},IA,EA,Rij=IA{,}都是A上等价关系,求对应的商集,其中ai,ajA,ij.是A上等价关系吗?解:A/IA={{a1},{a2},…,{an}}A/EA={{a1,a2,…,an}}A/Rij=A/IA{{ai,aj}}