SG08离散数学大全-集合与图论ppt课件.ppt

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

1、第8讲等价关系与序关系内容提要等价关系,等价类,商集划分,第二类Stirling数偏序,线序,拟序,良序哈斯图特殊元素:最?元,极?元,?界,?确界(反)链2021/8/31《集合论与图论》第8讲等价(equivalence)关系定义同余关系等价类商集划分划分的加细Stirling子集数2021/8/32《集合论与图论》第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,

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

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

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

8、R),sr(R)=rs(R),…tsr(R)=trs(R)=rts(R)str(R)=srt(R)=rst(R)2021/8/35《集合论与图论》第8讲例10(续)tsr(R)=trs(R)=rts(R)str(R)=srt(R)=rst(R)自反对称传递等价关系(等价闭包)2021/8/36《集合论与图论》第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[y]R=

10、;U{[x]R

11、xA}=A.2021/8/37《集合论与图论》第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/38《集合论与图论》第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/8/3

13、9《集合论与图论》第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/310《集合论与图论》第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{[x]R

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

19、entmodulon)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/312《集合论与图论》第8讲例11例11:设A={1,2,3,4,5,8},求R3={

25、x,yAxy(mod3)}的等价类,画出R3的关系图.解:[1]=[4]={1,4},[2]=[5]=[8]={2,5,8},[3]={3}.#1425832021/8/313《集合论与图

26、论》第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/314《集合论与图论》第8讲例12(1)例12(1):设A={a1,a2,…,an},IA,EA,Rij=IA{,}都是A上等价关系,求对应的商集,其中a