离散数学关系精品课件

1、离散数学关系2022/9/25集合论与图论第8讲1第1页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲2等价(equivalence)关系定义同余关系等价类商集划分划分的加细Stirling子集数第2页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲3等价(equivalence)关系定义等价关系: 设 RAA 且 A, 若R是自反的, 对称的, 传递的,则称R为等价关系例9: 判断是否等价关系(A是某班学生): R1=|x,yAx与y同年生R2=|x,yAx与y同姓R3=|x,yAx的年龄不比y小R4=|x

2、,yAx与y选修同门课程R5=|x,yAx的体重比y重第3页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲4例9(续)定义自反对称传递等价关系R1x与y同年生R2x与y同姓R3x的年龄不比y小R4x与y选修同门课程R5x的体重比y重第4页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲5例10例10: 设 RAA 且 A, 对R依次求三种闭包共有6种不同顺序, 其中哪些顺序一定导致等价关系? rst( R ), rts( R ), str( R ), srt( R ), trs( R ), tsr( R )=

3、t(s(r( R )解: st( R )ts( R ), sr( R )=rs( R ), tsr( R )=trs( R )=rts( R ) str( R )=srt( R )=rst( R )第5页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲6例10(续)tsr(R)=trs(R) =rts( R )str(R)=srt(R)=rst( R )自反对称传递等价关系(等价闭包)第6页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲7等价类(equivalence class)等价类: 设R是A上等价关系

4、,xA,令 xR= y | yA xRy ,称xR为x关于R的等价类, 简称x的等价类,简记为x.等价类性质: xR ;xRy xR=yR ;xRy xRyR= ;U xR | xA =A.第7页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲8定理27定理27:设R是A上等价关系,x,yA, (1) xR (2) xRy xR=yR ; (3) xRy xRyR= ; (4) U xR | xA =A. 证明: (1) R自反xRxxxRxR.x第8页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲9定理27

5、(证明(2) (2) xRy xR=yR ;证明: (2) 只需证明xRyR和xRyR.() z, zxRxRy zRxxRy zRy zyR . xRyR.() 同理可证.xyz第9页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲10定理27(证明(3)(3) xRy xRyR= ;证明: (3) (反证) 假设z, zxRyR, 则 zxRyR zRxzRy xRzzRy xRy, 这与xRy矛盾! xRyR=.xyz第10页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲11定理27(证明(4) (4)

6、 U xR | xA = A. 证明: (4) A=U x | xA U xR | xA U A | xA =A. U xR | xA = A. #xy第11页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第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)关系 6398754211011

7、0第12页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第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. #142583第13页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲14商集(quotient set)商集: 设R是A上等价关系, A/R = xR | xA 称为A关于R的商集, 简称A的商集. 显然 U A/R = A.例11(续): A/R3 = 1,4,

8、2,5,8, 3 .第14页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲15例12(1)例12(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上等价关系(非自反). #第15页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲16划分(partition)划分: 设A, AP(A),若A

9、满足 (1) A ; (2) x,y( x,yA xy xy= ) (3) UA = A 则称A为A的一个划分, A中元素称为划分块(block).第16页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲17划分(举例)设 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-. #第17页，共63页，2022年，5月20日，1点51分，星期六2022/

10、9/25集合论与图论第8讲18划分(举例,续)AiAi第18页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲19等价关系与划分是一一对应的定理28: 设A, 则(1) R是A上等价关系 A/R是A的划分(2) A是A的划分 RA是A上等价关系,其中xRAy z(zA xz yz) RA称为由划分A 所定义的等价关系(同块关系). #第19页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲20例12(2)例12(2): A=a,b,c, 求A上全体等价关系.解: A上不同划分共有5种:abcabcabcabca

11、bcR1= EA, R2=IA, R3=IA, R4=IA, R5=IA. #第20页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲21Bell数(Bell number)问题: 给n个对象分类, 共有多少种分法?答案: Bell数 Bn= (Eric Temple Bell, 18831960)Stirling子集数(Stirling subset number) : 把n个对象分成k个非空子集的分法个数. 递推公式: 第21页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲22Stirling子集数递推公

12、式: 剔除一个其余分k类加入一类其余分k-1类自成一类第22页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲23第一、二类Stirling数第一类Stirling数(Stirling number of the first kind): s(n,k) 第二类Stirling数(Stirling number of the second kind): S(n,k)=第23页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲24Bell数表 nBn nBn1184,14022921,1473510115,97541

13、511678,570552124,213,59762031327,644,437787714190,899,322第24页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲25第二类Stirling数表nk01 23456789011012011301314017615011525101601319065151701633013501402118011279661,1701,0502662819012553,0357,7706,9512,64646236110015119,33034,50142,52522,8275,88075045第25页，共63页，

14、2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲26例13例13: 问A=a,b,c,d上有多少种等价关系?解: #第26页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲27划分的加细(refinement)划分的加细: 设A和B都是集合A的划分, 若A的每个划分块都包含于B的某个划分块中, 则称A为B的加细. A为B的加细 RARB 第27页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲28例14例14: 考虑A=a,b,c上的划分之间的加细.解: abcabcabcabca

15、bc加细加细加细加细加细加细#第28页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲29序关系偏序,线序,拟序,良序哈斯图特殊元素: 最?元, 极?元, ?界, ?确界(反)链 第29页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲30偏序(partial order)关系偏序关系: 设 RAA 且 A, 若R是自反的, 反对称的, 传递的, 则称R为偏序关系通常用表示偏序关系,读作“小于等于”R xRy xy“严格小于”: xy xy xy偏序集(poset): , 是A上偏序关系例子: , , , 第3

16、0页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲31偏序集, , AR = | x,yA xy , = | x,yA xy ,AZ+= x | xZ x0 | = | x,yA x|y 第31页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第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 , , 第32页，共63页，2022年，5月20日，1点51分，星期六2022/

17、9/25集合论与图论第8讲33偏序集A, 是由A的一些划分组成的集合加细 = | x,y x是y的加细 设A=a,b,c, A1=a,b,c,A2=a,b,c,A3=b,a,c,A4=c,a,b,A5=a,b,c取1=A1,A2,2=A2,A3,3=A1,A2,A3,A4,A51 = I1 , 2 = I2, 3 = I3 , , ,. #第33页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲34哈斯图(Hasse diagram)设是偏序集, x,yA可比(comparable):x与y可比 xy yx覆盖(cover):y覆盖x xy z( zA

18、 xzy )哈斯图: 当且仅当y覆盖x时,在x与y之间画无向边, 并且x画在y下方第34页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲35例16(1)(2)例16: 画出下列偏序关系的哈斯图.(1) , A=1,2,3,4,5,6,9,10,15(2) , A=a,b,c, AP(A), A=,a,b,c,a,b,b,c,a,c解: 12436915510abca,ba,cb,c第35页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲36例16(3)例16: 画出下列偏序关系的哈斯图.(3) , =A1,A

19、2,A3,A4,A5,A6, A=a,b,c,d A1 = a, b, c, d , A2 = a,b, c,d , A3 = a,c, b,d , A4 = a, b,c,d , A5 = a, b, c,d , A6 = a,b,c,d 解: A1A2A5A3A4A6#第36页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲37偏序关系中的特殊元素最大元, 最小元极大元, 极小元上界, 下界最小上界(上确界), 最大下界(下确界)第37页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲38最大元, 最小元设

20、为偏序集, BA, yB最大元(maximum/greatest element): y是B的最大元 x( xB xy )最小元(minimum/least element): y是B的最小元 x( xB yx )第38页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲39最大元, 最小元举例(例16(1)例16(1): , A=1,2,3,4,5,6,9,10,15 B1=1,2,3, B2=3,5,15, B3=A. B1的最大元是, B1的最小元是1 B2的最大元是15, B2的最小元是 B3的最大元是, B3的最小元是1124369155101

21、2436915510第39页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲40极大元,极小元设为偏序集, BA, yB极大元(maximal element): y是B的极大元 x( xB yx x=y )极小元(minimal element): y是B的极小元 x( xB xy x=y )第40页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲41极大元,极小元举例(例16(1)例16(1): , A=1,2,3,4,5,6,9,10,15 B1=1,2,3, B2=3,5,15, B3=A.B1的极大元

22、是2,3, B1的极小元是1 B2的极大元是15, B2的极小元是3,5B3的极大元是4,6,9,15,10, B3的极小元是11243691551012436915510第41页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲42上界, 下界设为偏序集, BA, yA上界(upper bound): y是B的上界 x( xB xy )下界(lower bound): y是B的下界 x( xB yx )第42页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲43上界, 下界举例(例16(1)例16(1): ,

23、A=1,2,3,4,5,6,9,10,15 B1=1,2,3, B2=3,5,15, B3=A. B1的上界是6, B1的下界是1 B2的上界是15, B2的下界是1 B3的上界是, B3的下界是11243691551012436915510第43页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲44最小上界, 最大下界设为偏序集, BA最小上界(least upper bound): 设 C = y | y是B的上界 , C的最小元称为B的最小上界, 或上确界. 最大下界(greatest lower bound): 设 C = y | y是B的下界

24、 , C的最大元称为B的最大下界, 或下确界. 第44页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲45最小上界,最大下界举例(例16(1)例16(1): , A=1,2,3,4,5,6,9,10,15 B1=1,2,3, B2=3,5,15, B3=A. B1的最小上界是6, B1的最大下界是1 B2的最小上界是15, B2的最大下界是1 B3的最小上界是, B3的最大下界是11243691551012436915510第45页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲46特殊元素比较存在(B非空有

25、穷)存在(B无穷)唯一B最大元(表示不一定)最小元极大元 (表示一定),B=Z极小元上界下界上确界下确界第46页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲47链(chain), 反链(antichain)设为偏序集, BA,链(chain): B是A中的链 xy( xByB x与y可比 ) |B|称为链的长度反链(antichain): B是A中的反链 xy( xByBxy x与y不可比 ) |B|称为反链的长度第47页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲48链, 反链(举例)设偏序集如图所示

26、, A=a,b,k.abcdefghijkB1=a,c,d,e是长为4的链 上界e,f,g,h, 上确界e 下界a, 下确界aB2=a,e,h是长为3的链B3=b,g是长为2的链B4=g,h,k是长为3的反链 上界,下界,上确界,下确界: 无B5=a是长为1的链和反链B6=a,b,g,h既非链,亦非反链第48页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲49定理31定理31: 设为偏序集, A中最长链的长度为n, 则 (1) A中存在极大元 (2) A存在n个划分块的划分, 每个划分块都是反链(即A划分成n个互不相交的反链)推论: 设为偏序集, 若

27、|A|=mn+1,则A中要么存在长度为m+1的反链, 要么存在长度为n+1的链.第49页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲50定理31(举例)abcdefghijk最长链长度为6, 如B1=a,c,d,e,f,h, B2=a,c,d,e,f,g, A=a,b,k可以划分为A 1= a,b,i, c,j, d, e, f, g,h,k ,A 2= a,b, c,i, d,j, e,k, f, g,h |A|=11=25+1, A中既有长度为2+1=3的反链,也有长度为5+1=6的链第50页，共63页，2022年，5月20日，1点51分，星期

28、六2022/9/25集合论与图论第8讲51定理31(证明(1)定理31: 设为偏序集, A中最长链的长度为n, 则 (1) A中存在极大元证明: (1) 设B是A中长度为n的最长链, B有极大元(也是最大元)y, 则y也是A的极大元, 否则A中还有比y“大”的元素z, B就不是最长链.第51页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲52定理31(证明(2)定理31: 设为偏序集, A中最长链的长度为n, 则 (2) A存在n个划分块的划分, 每个划分块都是反链(即A划分成n个互不相交的反链)证明: (2) A1 = x | x是A中的极大元 ,

29、 A2 = x | x是(A-A1)中的极大元 , An = x | x是(A-A1-An-1)中的极大元 , 则 A = A1, A2, An 是满足要求的划分.第52页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲53定理31(证明(2):举例)abcdefghijk最长链长度为6, A1 = g, h, k , A2 = f, j , A3 = e, i , A4 = d , A5 = c , A6 = a, b , A = a,b, c, d, e,i, f,j, g,h,k 第53页，共63页，2022年，5月20日，1点51分，星期六20

30、22/9/25集合论与图论第8讲54定理31(证明(2)续)证明(续): 1 A1 = x | x是A中的极大元 , 极大元互相之间不可比, 所以A1是反链, 同理A2,An都是反链. 2 显然A1,A2,An互不相交. 3 最长链上的元素分属A1,A2,An, 所以A1,A2,An都非空. 4 假设zA-A1-An,则最长链上的元素加上z就是长度为n+1的链, 矛盾! 所以A=A1A2An. 综上所述, A= A1,A2,An 确是所求划分. #第54页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲55定理31推论(证明)推论: 设为偏序集, 若|

31、A|=mn+1,则A中要么存在长度为m+1的反链, 要么存在长度为n+1的链.证明: (反证)假设A中既没有长度为m+1的反链, 也没有长度为n+1的链, 则按照定理31(2)中要求来划分A, A至多划分成n块, 每块至多m个元素, 于是A中至多有mn个元素, 这与|A|=mn+1矛盾! #第55页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲56全序(total order)关系全序关系: 若偏序集满足xy( xAyA x与y可比) 则称为全序关系, 称为全序集全序关系亦称线序(linear order)关系例: , 第56页，共63页，2022年，5月20日，1点51分，星期六2022/9/25集合论与图论第8讲57拟序(quasi-order)关系拟序关系