北大离散数学08PPT学习教案

1、会计学1北大离散数学北大离散数学082021-10-12集合论与图论第8讲2第1页/共63页2021-10-12集合论与图论第8讲3R4=|x,yAx与y选修同门课程R5=|x,yAx的体重比y重第2页/共63页2021-10-12集合论与图论第8讲4定义自反对称 传递 等价关系R1x与y同年生R2x与y同姓R3x的年龄不比y小R4x与y选修同门课程R5x的体重比y重第3页/共63页2021-10-12集合论与图论第8讲5 str( R )=srt( R )=rst( R )第4页/共63页2021-10-12集合论与图论第8讲6tsr(R)=trs(R) =rts( R )str(R)=sr

2、t(R)=rst( R )自反对称传递等价关系(等价闭包)第5页/共63页2021-10-12集合论与图论第8讲7U xR | xA =A.第6页/共63页2021-10-12集合论与图论第8讲8x第7页/共63页2021-10-12集合论与图论第8讲9xyz第8页/共63页2021-10-12集合论与图论第8讲10 xyz第9页/共63页2021-10-12集合论与图论第8讲11xy第10页/共63页2021-10-12集合论与图论第8讲12 n-1=(n-1)+kn|kZ.63987542110110第11页/共63页2021-10-12集合论与图论第8讲13142583第12页/共63页

3、2021-10-12集合论与图论第8讲14第13页/共63页2021-10-12集合论与图论第8讲15ai,aj. 不是A上等价关系(非自反). #第14页/共63页2021-10-12集合论与图论第8讲16第15页/共63页2021-10-12集合论与图论第8讲17n, A1A2 An-. #第16页/共63页2021-10-12集合论与图论第8讲18AiAi第17页/共63页2021-10-12集合论与图论第8讲19第18页/共63页2021-10-12集合论与图论第8讲20abcabcabcabcabcR1= EA, R2=IA, R3=IA, R4=IA, R5=IA. #第19页/共

4、63页2021-10-12集合论与图论第8讲21.211nnnnknnkkn. 1,1, 122, 11, 0021nnCnnnnnnn.111knknkkn第20页/共63页2021-10-12集合论与图论第8讲22.111knknkkn剔除一个其余分k类加入一类其余分k-1类自成一类第21页/共63页2021-10-12集合论与图论第8讲23kn.) 1()2)(1(),(0kknkxkxxxxxkns.),() 1() 2)(1(),(00knknknxknSkxxxxknSx第22页/共63页2021-10-12集合论与图论第8讲24 nBn nBn1184,14022921,1473

5、510115,97541511678,570552124,213,59762031327,644,437787714190,899,322第23页/共63页2021-10-12集合论与图论第8讲25nk01 23456789011012011301314017615011525101601319065151701633013501402118011279661,1701,050266281901255 3,0357,7706,9512,64646236110015119,33034,50142,52522,8275,88075045第24页/共63页2021-10-12集合论与图论第8讲26.

6、1516711) 12 (1443424142434CB第25页/共63页2021-10-12集合论与图论第8讲27第26页/共63页2021-10-12集合论与图论第8讲28abcabcabcabcabc加细加细加细加细加细加细#第27页/共63页2021-10-12集合论与图论第8讲29第28页/共63页2021-10-12集合论与图论第8讲30第29页/共63页2021-10-12集合论与图论第8讲31第30页/共63页2021-10-12集合论与图论第8讲32, 第31页/共63页2021-10-12集合论与图论第8讲331=A1,A2,2=A2,A3,3=A1,A2,A3,A4,A5

7、1 = I1 , 2 = I2, 3 = I3 , , ,. #第32页/共63页2021-10-12集合论与图论第8讲34第33页/共63页2021-10-12集合论与图论第8讲3512436915510abca,ba,cb,c第34页/共63页2021-10-12集合论与图论第8讲36A1A2A5A3A4A6#第35页/共63页2021-10-12集合论与图论第8讲37第36页/共63页2021-10-12集合论与图论第8讲38第37页/共63页2021-10-12集合论与图论第8讲391243691551012436915510第38页/共63页2021-10-12集合论与图论第8讲40

8、第39页/共63页2021-10-12集合论与图论第8讲411243691551012436915510第40页/共63页2021-10-12集合论与图论第8讲42第41页/共63页2021-10-12集合论与图论第8讲431243691551012436915510第42页/共63页2021-10-12集合论与图论第8讲44第43页/共63页2021-10-12集合论与图论第8讲451243691551012436915510第44页/共63页2021-10-12集合论与图论第8讲46存在(B非空有穷) 存在(B无穷) 唯一 B最大元 (表示不一定)最小元 极大元 (表示一定),B=Z 极小

9、元 上界下界上确界 下确界 第45页/共63页2021-10-12集合论与图论第8讲47第46页/共63页2021-10-12集合论与图论第8讲48abcdefghijkB1=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既非链,亦非反链第47页/共63页2021-10-12集合论与图论第8讲49n+1.第48页/共63页2021-10-12集合论与图论第8讲50abcdefghijk最长链长度为6,

10、如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的链第49页/共63页2021-10-12集合论与图论第8讲51第50页/共63页2021-10-12集合论与图论第8讲52 An = x | x是(A-A1-An-1)的极大元 ,则 A = A1, A2, An 是满足要求的划分.第51页/共63页2021-10-12集合论与图论第8讲53abcd

11、efghijk最长链长度为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 第52页/共63页2021-10-12集合论与图论第8讲54第53页/共63页2021-10-12集合论与图论第8讲55, |A|=mn+1矛盾! #第54页/共63页2021-10-12集合论与图论第8讲56第55页/共63页2021-10-12集合论与图论第8讲57n例子: 设AR, BZ+A,| = | x,yB x|y xy第56页/共63页2021-10-12集合论与图论第8讲58第57页/共63页2021-10-12集合