离散数学：第7讲 等价关系

2026/2/11等价关系1定理7.11定理7.11:设R

A

A且A

,则(1)R自反

r(R)=R;(2)R对称

s(R)=R;(3)R传递

t(R)=R.2026/2/11等价关系2定理7.12定理7.12:设R1

R2

A

A且A

,则(1)r(R1)r(R2);(2)s(R1)s(R2);(3)t(R1)t(R2);2026/2/11等价关系3定理7.10定理7.10:设R

A

A且A

,则r(R)=R

IA;s(R)=R

R-1;t(R)=R

R2

R3….推论:设R

A

A且0<|A|<,则

lN,使得t(R)=R

R2

R3…Rl2026/2/11等价关系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)传递。2026/2/11等价关系5性质1性质1:设R1,R2

A

A且A

,则(1)r(R1

R2)=

r(R1)r(R2);(2)s(R1

R2)=s(R1)s(R2);(3)t(R1

R2)t(R1)t(R2).2026/2/11等价关系6性质2性质2:设R

A

A且A

,则(1)rs(R)=sr(R);(2)rt(R)=tr(R);(3)st(R)

ts(R).2026/2/11等价关系7问题rst(R),rts(R),str(R),srt(R),trs(R),tsr(R)是否相等？哪些满足自反性，对称性，传递性？2026/2/11等价关系8问题（续1）解:st(R)ts(R),sr(R)=rs(R),tr(R)=rt(R)tsr(R)=trs(R)=trs(R)=rts(R)str(R)=srt(R)=srt(R)=rst(R)失去传递性因为要先做对称再做传递才具有对称性2026/2/11等价关系9问题(续2)tsr(R)=trs(R)=rts(R)str(R)=srt(R)=rst(R)自反

对称

传递

2026/2/11等价关系10定理7.13定理7.13:设R

A

A且A

,则(1)R自反

s(R)和t(R)自反;(2)R对称

r(R)和t(R)对称;(3)R传递

r(R)传递。2026/2/11等价关系11等价关系等价关系:设RAA且A,若R是自反的,对称的,传递的,则称R为等价关系。2026/2/11等价关系12内容提要等价(equivalence)关系等价类同余关系商集集合的划分2026/2/11等价关系13例9例9:判断是否等价关系(A是某班学生):R1={<x,y>|x,yAx与y同年生}R2={<x,y>|x,yAx与y同姓}R3={<x,y>|x,yAx的年龄不比y小}R4={<x,y>|x,yAx与y选修同门课程}R5={<x,y>|x,yAx的体重比y重}2026/2/11等价关系14例9(续)定义自反对称传递等价关系R1x与y同年生

R2x与y同姓

R3x的年龄不比y小

（我不比你小，你不比我小）

R4x与y选修同门课程

（可以有多个选修课）

R5x的体重比y重

2026/2/11等价关系15例10例10:设RAA且A,对R依次求三种闭包共有6种不同顺序,其中哪些顺序一定导致等价关系?rst(R),rts(R),str(R),srt(R),trs(R),tsr(R)2026/2/11等价关系16例10(续1)tsr(R)=trs(R)=rts(R)str(R)=srt(R)=rst(R)自反

对称

传递

等价关系(等价闭包)

2026/2/11等价关系17例11例11:设A={1,2,3,4,5,8},则R={<x,y>|x,yAxy(mod3)}//x和y除以3的余数相同是否为等价关系,画出R的关系图.142583R是等价关系#2026/2/11等价关系18等价类(equivalenceclass)等价类:设R是A

上等价关系,

xA,[x]R={y|yAxRy}称为x关于R的等价类,简称x的等价类,简记为[x].2026/2/11等价关系19例11（续）例11:设A={1,2,3,4,5,8},等价关系R={<x,y>|x,yAxy(mod3)}的等价类如下：142583[1]=[4]={1,4},[2]=[5]=[8]={2,5,8},[3]={3}.#2026/2/11等价关系20同余关系:对于任意大于１的自然数n,x,yZ,则x与y模n同余(becongruentmodulon)

xy(modn)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)关系

639875421101102026/2/11等价关系21定理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.x2026/2/11等价关系22定理7.14(证明(2))(2)xRy[x]R=[y]R;证明:(2)只需证明[x]R[y]R和[x]R[y]R.()z,z[x]RxRy

zRxxRyzRyz[y]R.

[x]R[y]R.(

)同理可证.xyz2026/2/11等价关系23定理7.14(证明(3))(3)xRy[x]R[y]R=;证明:(3)(反证)假设

z,z[x]R[y]R,则z[x]R[y]RzRxzRyxRzzRyxRy,这与xRy矛盾![x]R[y]R=.xyz2026/2/11等价关系24定理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.#xy2026/2/11等价关系25商集(quotientset)商集:设R是A

上等价关系,A/R={[x]R|xA}称为A关于R的商集,简称A的商集.例11(续):A/R

={{1,4},{2,5,8},{3}}.2026/2/11等价关系26例12例:考虑A={a,b,c}上的等价关系.解:IA,EA,R1=IA{<a,b>,<b,a>}R2=IA{<a,c>,<c,a>}R3=IA{<c,b>,<b,c>}对应的商集分别是什么？A上是否还有其他等价关系？2026/2/11等价关系27例12（续）例12(2):设A={a1,a2,…,an},IA,EA,Rij=IA{<ai,aj>,<aj,ai>}都是A上等价关系,求对应的商集,其中ai,ajA,ij.2026/2/11等价关系28例12（续2）解:A/IA={{a1},{a2},…,{an}}A/EA={{a1,a2,…,an}}A/Rij=A/IA{{ai,aj}}-{{ai},{aj}}2026/2/11等价关系29覆盖和划分(partition)设A,S={A1,A2,…An}P(A),若A满足(1)Ai≠;不空(2)∪Ai=A;不漏(3)Ai∩Aj=(i≠j)；不重则称S为A的一个划分,A中元素称为划分块(block).若只满足(1)(2)则称S为A的一个覆盖.2026/2/11等价关系30划分的加细(refinement)定义:{A1,A2,…Ar}与{B1,B2,…Bs}是同一个集合A的两种划分，若对于每一个Ai都有Bj使得Ai

Bj,则{A1,A2,…Ar}称为是{B1,B2,…Bs}的加细。2026/2/11等价关系31例12例:考虑A={a,b,c}上的划分.解:abcabcabcabcabc加细加细加细加细加细加细#如何确定一个集合上的划分个数？2026/2/11等价关系32例13例13:问A={a,b,c,d}有多少种划分?2026/2/11等价关系33Bell数(Bellnumber)问题:给n个对象分类,共有多少种分法?答案:Bell数Bn=(EricTempleBell,1883~1960)Stirling子集数(Stirlingsubsetnumber):把n个对象分成k个非空子集的分法个数.

递推公式:2026/2/11等价关系34第二类Stirling数性质

递推公式:2026/2/11等价关系35Stirling子集数递推公式:剔除一个其余分k类加入一类其余分k-1类自成一类2026/2/11等价关系36Bell数表nBn

nBn1184,14022921,1473510115,97541511678,570552124,213,59762031327,644,437787714190,899,3222026/2/11等价关系37第二类Stirling数表n\k0123456789011012011301314017615011525101601319065151701633013501402118011279661,1701,0502662819012553,0357,