北大离散数学08课件.pptVIP

北大离散数学082023/9/12星期二《集合论与图论》第8讲1

等价(equivalence)关系?定义?同余关系?等价类?商集?划分?划分的加细?Stirling子集数2023/9/12星期二《集合论与图论》第8讲2

等价(equivalence)关系定义?等价关系:设R?A?A且A??,若R是自反的,对称的,传递的,则称R为等价关系?例9:判断是否等价关系(A是某班学生):R={x,y|x,y?A?x与y同年生}1R={x,y|x,y?A?x与y同姓}2R={x,y|x,y?A?x的年龄不比y小}3R={x,y|x,y?A?x与y选修同门课程}4R={x,y|x,y?A?x的体重比y重}52023/9/12星期二《集合论与图论》第8讲3

例9(续)定义自反对称传递等价关系Rx与y同年生?????1Rx与y同姓???2Rx的年龄不比?????3y小Rx与y选修同???4门课程Rx的体重比y????5重2023/9/12星期二《集合论与图论》第8讲4

例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)=rts(R)str(R)=srt(R)=rst(R)2023/9/12星期二《集合论与图论》第8讲5

例10(续)tsr(R)=trs(R)str(R)=srt(R)=rts(R)=rst(R)自反对称传递???????等价关系?(等价闭包)2023/9/12星期二《集合论与图论》第8讲6

等价类(equivalenceclass)?等价类:设R是A??上等价关系,?x?A,令[x]={y|y?A?xRy},R称[x]为x关于R的等价类,简称x的等价类,R简记为[x].?等价类性质:[x]??;RxRy?[x]=[y];RR?xRy?[x]?[y]=?;RRU{[x]|x?A}=A.R2023/9/12星期二《集合论与图论》第8讲7

定理27?定理27:设R是A??上等价关系,?x,y?A,(1)[x]??R(2)xRy?[x]=[y];RR(3)?xRy?[x]?[y]=?;RR(4)U{[x]|x?A}=A.R?证明:(1)R自反?xRx?x?[x]?[x]??.RRx2023/9/12星期二《集合论与图论》第8讲8

定理27(证明(2))?(2)xRy?[x]=[y];RR?证明:(2)只需证明[x]?[y]和[x]?[y]RRRR.(?)?z,z?[x]?xRy?zRx?xRyR?zRy?z?[y].?[x]?[y].RRR(?)同理可证.zxy2023/9/12星期二《集合论与图论》第8讲9

定理27(证明(3))?(3)?xRy?[x]?[y]=?;RR?证明:(3)(反证)假设?z,z?[x]?[y],则RRz?[x]?[y]?zRx?zRy?xRz?zRyRR?xRy,这与?xRy矛盾!?[x]?[y]=?.RRzyx2023/9/12星期二《集合论与图论》第8讲10

定理27(证明(4))?(4)U{[x]|x?A}=A.R?证明:(4)A=U{{x}|x?A}?U{[x]|x?A}?U{A|x?A}=A.R?U{[x]|x?A}=A.#Ryx2023/9/12星期二《集合论与图论》第8讲11

同余(congruence)关系?同余关系:设n?{2,3,4,…},x,y?Z,则x与y模n同余(becongruentmodulon)?x?y(modn)?n|(x-y)?x-y=kn(k?Z)?同余关系是等价关系011?[0]={kn|k?Z},[1]={1+kn|k?Z},[2]={2+kn|k?Z},…,[n-1]={(n-1)+kn|k?Z}.110824937562023/9/12星期二《集合论与图论》第8讲12

例11?例11:设A={1,2,3,4,5,8},求R={x,y|x,y?A?x?y(mod3)}3的等价类,画出R的关系图.3?解: