《离散数学关系4》由会员分享，可在线阅读，更多相关《离散数学关系4（63页珍藏版）》请在金锄头文库上搜索。
1、2017/12/9,集合论与图论第8讲,1,第8讲 等价关系与序关系,内容提要等价关系,等价类,商集 划分, 第二类Stirling数偏序,线序,拟序,良序哈斯图特殊元素: 最?元,极?元,?界,?确界(反)链,2017/12/9,集合论与图论第8讲,2,等价(equivalence)关系,定义同余关系等价类商集划分划分的加细Stirling子集数,2017/12/9,集合论与图论第8讲,3,等价(equivalence)关系定义,等价关系: 设 RAA 且 A, 若R是自反的, 对称的, 传递的,则称R为等价关系例9: 判断是否等价关系(A是某班学生): R1=|x,yAx与y同年生R2=|
2、x,yAx与y同姓R3=|x,yAx的年龄不比y小R4=|x,yAx与y选修同门课程R5=|x,yAx的体重比y重,2017/12/9,集合论与图论第8讲,4,例9(续),2017/12/9,集合论与图论第8讲,5,例10,例10: 设 RAA 且 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(
3、R )=srt( R )=rst( R ),2017/12/9,集合论与图论第8讲,6,例10(续),2017/12/9,集合论与图论第8讲,7,等价类(equivalence class),等价类: 设R是A上等价关系,xA,令 xR= y | yA xRy ,称xR为x关于R的等价类, 简称x的等价类,简记为x.等价类性质: xR ;xRy xR=yR ;xRy xRyR= ;U xR | xA =A.,2017/12/9,集合论与图论第8讲,8,定理27,定理27:设R是A上等价关系,x,yA, (1) xR (2) xRy xR=yR ; (3) xRy xRyR= ; (4) U x
4、R | xA =A. 证明: (1) R自反xRxxxRxR.,x,2017/12/9,集合论与图论第8讲,9,定理27(证明(2),(2) xRy xR=yR ;证明: (2) 只需证明xRyR和xRyR.() z, zxRxRy zRxxRy zRy zyR . xRyR.() 同理可证.,x,y,z,2017/12/9,集合论与图论第8讲,10,定理27(证明(3),(3) xRy xRyR= ;证明: (3) (反证) 假设z, zxRyR, 则 zxRyR zRxzRy xRzzRy xRy, 这与xRy矛盾! xRyR=.,x,y,z,2017/12/9,集合论与图论第8讲,11,
5、定理27(证明(4),(4) U xR | xA = A. 证明: (4) A=U x | xA U xR | xA U A | xA =A. U xR | xA = A. #,x,y,2017/12/9,集合论与图论第8讲,12,同余关系: 设n2,3,4, x,yZ,则x与y模n同余(be congruent modulo n) xy(mod n) 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)关系,6,3,9,8,7,5,4,2,1,10,11
6、,0,2017/12/9,集合论与图论第8讲,13,例11,例11: 设 A=1,2,3,4,5,8, 求R3 = | x,yA xy(mod 3) 的等价类, 画出R3的关系图.解: 1=4=1,4, 2=5=8=2,5,8, 3=3. #,1,4,2,5,8,3,2017/12/9,集合论与图论第8讲,14,商集(quotient set),商集: 设R是A上等价关系, A/R = xR | xA 称为A关于R的商集, 简称A的商集. 显然 U A/R = A.例11(续): A/R3 = 1,4, 2,5,8, 3 .,2017/12/9,集合论与图论第8讲,15,例12(1),例12(
7、1): 设A=a1,a2,an, IA, EA,Rij=IA,都是A上等价关系, 求对应的商集, 其中ai,ajA, ij. 是A上等价关系吗?解: A/IA= a1, a2, an A/EA= a1,a2,an A/Rij= A/IAai,aj - ai,aj. 不是A上等价关系(非自反). #,2017/12/9,集合论与图论第8讲,16,划分(partition),划分: 设A, AP(A),若A满足 (1) A ; (2) x,y( x,yA xy xy= ) (3) UA = A 则称A为A的一个划分, A中元素称为划分块(block).,2017/12/9,集合论与图论第8讲,17
8、,划分(举例),设 A1,A2,AnE, 则以下都是划分: Ai = Ai,Ai, ( i=1,2,n ) Aij = AiAj,AiAj, AiAj, AiAj- ( i,j =1,2,n ij ) A12n = A1A2 An, A1A2 An-1An, A1A2 An-. #,2017/12/9,集合论与图论第8讲,18,划分(举例,续),Ai,Ai,2017/12/9,集合论与图论第8讲,19,等价关系与划分是一一对应的,定理28: 设A, 则(1) R是A上等价关系 A/R是A的划分(2) A是A的划分 RA是A上等价关系,其中xRAy z(zA xz yz) RA称为由划分A 所定
9、义的等价关系(同块关系). #,2017/12/9,集合论与图论第8讲,20,例12(2),例12(2): A=a,b,c, 求A上全体等价关系.解: A上不同划分共有5种:,a,b,c,a,b,c,a,b,c,a,b,c,a,b,c,R1= EA, R2=IA, R3=IA, R4=IA, R5=IA. #,2017/12/9,集合论与图论第8讲,21,Bell数(Bell number),问题: 给n个对象分类, 共有多少种分法?答案: Bell数 Bn= (Eric Temple Bell, 18831960)Stirling子集数(Stirling subset number) : 把
10、n个对象分成k个非空子集的分法个数. 递推公式:,2017/12/9,集合论与图论第8讲,22,Stirling子集数,递推公式:,剔除一个,其余分k类,加入一类,其余分k-1类,自成一类,2017/12/9,集合论与图论第8讲,23,第一、二类Stirling数,第一类Stirling数(Stirling number of the first kind): s(n,k) 第二类Stirling数(Stirling number of the second kind): S(n,k)=,2017/12/9,集合论与图论第8讲,24,Bell数表,2017/12/9,集合论与图论第8讲,25,
11、第二类Stirling数表,2017/12/9,集合论与图论第8讲,26,例13,例13: 问A=a,b,c,d上有多少种等价关系?解: #,2017/12/9,集合论与图论第8讲,27,划分的加细(refinement),划分的加细: 设A和B都是集合A的划分, 若A的每个划分块都包含于B的某个划分块中, 则称A为B的加细. A为B的加细 RARB,2017/12/9,集合论与图论第8讲,28,例14,例14: 考虑A=a,b,c上的划分之间的加细.解:,a,b,c,a,b,c,a,b,c,a,b,c,a,b,c,加细,加细,加细,加细,加细,加细,#,2017/12/9,集合论与图论第8讲
12、,29,序关系,偏序,线序,拟序,良序哈斯图特殊元素: 最?元, 极?元, ?界, ?确界(反)链,2017/12/9,集合论与图论第8讲,30,偏序(partial order)关系,偏序关系: 设 RAA 且 A, 若R是自反的, 反对称的, 传递的, 则称R为偏序关系通常用表示偏序关系,读作“小于等于”R xRy xy“严格小于”: xy xy xy偏序集(poset): , 是A上偏序关系例子: , , , ,2017/12/9,集合论与图论第8讲,31,偏序集, , ,AR = | x,yA xy , = | x,yA xy ,AZ+= x | xZ x0 | = | x,yA x|y ,2017/12/9,集合论与图论第8讲,32,偏序集,AP(A), = | x,yA xy 设A=a,b, A1=,a,b, A2=a,a,b, A3=P(A)=,a,b,a,b,则1 = IA1 , 2 = IA2 3 = IA3 , , ,
