离散数学关系省公共课一等奖全国赛课获奖课件.pptx
《离散数学关系省公共课一等奖全国赛课获奖课件.pptx》由会员分享,可在线阅读,更多相关《离散数学关系省公共课一等奖全国赛课获奖课件.pptx(63页珍藏版)》请在咨信网上搜索。
1、第8讲 等价关系与序关系内容提要等价关系,等价类,商集 划分,第二类Stirling数偏序,线序,拟序,良序哈斯图特殊元素:最?元,极?元,?界,?确界(反)链/10/101集合论与图论第8讲第1页等价(equivalence)关系定义同余关系等价类商集划分划分加细Stirling子集数/10/102集合论与图论第8讲第2页等价(equivalence)关系定义等价关系:设 RAA 且 A,若R是自反,对称,传递,则称R为等价关系例9:判断是否等价关系(A是某班学生):R1=|x,yAx与y同年生R2=|x,yAx与y同姓R3=|x,yAx年纪不比y小R4=|x,yAx与y选修同门课程R5=|
2、x,yAx体重比y重/10/103集合论与图论第8讲第3页例9(续)定义自反对称 传递 等价关系R1x与y同年生R2x与y同姓R3x年纪不比y小R4x与y选修同门课程R5x体重比y重/10/104集合论与图论第8讲第4页例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(R)=srt(R)=rst(R)/10/105集合论与图论第8讲第5页例10(续
3、)tsr(R)=trs(R)=rts(R)str(R)=srt(R)=rst(R)自反对称传递等价关系(等价闭包)/10/106集合论与图论第8讲第6页等价类(equivalence class)等价类:设R是A上等价关系,xA,令 xR=y|yA xRy,称xR为x关于R等价类,简称x等价类,简记为x.等价类性质:xR;xRy xR=yR;xRy xRyR=;U xR|xA =A./10/107集合论与图论第8讲第7页定理27定理27:设R是A上等价关系,x,yA,(1)xR(2)xRy xR=yR;(3)xRy xRyR=;(4)U xR|xA =A.证实:(1)R自反xRxxxRxR.x
4、/10/108集合论与图论第8讲第8页定理27(证实(2)(2)xRy xR=yR;证实:(2)只需证实xRyR和xRyR.()z,zxRxRy zRxxRy zRy zyR.xRyR.()同理可证.xyz/10/109集合论与图论第8讲第9页定理27(证实(3)(3)xRy xRyR=;证实:(3)(反证)假设z,zxRyR,则 zxRyR zRxzRy xRzzRy xRy,这与xRy矛盾!xRyR=.xyz/10/1010集合论与图论第8讲第10页定理27(证实(4)(4)U xR|xA =A.证实:(4)A=U x|xA U xR|xA U A|xA=A.U xR|xA =A.#xy/
5、10/1011集合论与图论第8讲第11页同余关系:设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)关系 63987542110110/10/1012集合论与图论第8讲第12页例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/10/1013集合
6、论与图论第8讲第13页商集(quotient set)商集:设R是A上等价关系,A/R=xR|xA 称为A关于R商集,简称A商集.显然 U A/R=A.例11(续):A/R3=1,4,2,5,8,3./10/1014集合论与图论第8讲第14页例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上等价关系(非自反).#/10/1015集合论与图论第8讲第15页划分(partition)划分:设
7、A,AP(A),若A满足 (1)A;(2)x,y(x,yA xy xy=)(3)UA=A 则称A为A一个划分,A中元素称为划分块(block)./10/1016集合论与图论第8讲第16页划分(举例)设 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-.#/10/1017集合论与图论第8讲第17页划分(举例,续)AiAi/10/1018集合论与图论第8讲第18页等价关系与划分是一一对应定理28:设A,则(1)R是A上等价关系 A/R
8、是A划分(2)A是A划分 RA是A上等价关系,其中xRAy z(zA xz yz)RA称为由划分A 所定义等价关系(同块关系).#/10/1019集合论与图论第8讲第19页例12(2)例12(2):A=a,b,c,求A上全体等价关系.解:A上不一样划分共有5种:abcabcabcabcabcR1=EA,R2=IA,R3=IA,R4=IA,R5=IA.#/10/1020集合论与图论第8讲第20页Bell数(Bell number)问题:给n个对象分类,共有多少种分法?答案:Bell数 Bn=(Eric Temple Bell,18831960)Stirling子集数(Stirling subse
9、t number):把n个对象分成k个非空子集分法个数.递推公式:/10/1021集合论与图论第8讲第21页Stirling子集数递推公式:剔除一个其余分k类加入一类其余分k-1类自成一类/10/1022集合论与图论第8讲第22页第一、二类Stirling数第一类Stirling数(Stirling number of the first kind):s(n,k)第二类Stirling数(Stirling number of the second kind):S(n,k)=/10/1023集合论与图论第8讲第23页Bell数表 nBn nBn1184,14022921,1473510115,9
10、7541511678,570552124,213,59762031327,644,437787714190,899,322/10/1024集合论与图论第8讲第24页第二类Stirling数表nk01 23456789011012011301314017615011525101601319065151701633013501402118011279661,1701,050266281901255 3,0357,7706,9512,64646236110015119,33034,50142,52522,8275,88075045/10/1025集合论与图论第8讲第25页例13例13:问A=a,b,
11、c,d上有多少种等价关系?解:#/10/1026集合论与图论第8讲第26页划分加细(refinement)划分加细:设A和B都是集合A划分,若A每个划分块都包含于B某个划分块中,则称A为B加细.A为B加细 RARB /10/1027集合论与图论第8讲第27页例14例14:考虑A=a,b,c上划分之间加细.解:abcabcabcabcabc加细加细加细加细加细加细#/10/1028集合论与图论第8讲第28页序关系偏序,线序,拟序,良序哈斯图特殊元素:最?元,极?元,?界,?确界(反)链/10/1029集合论与图论第8讲第29页偏序(partial order)关系偏序关系:设 RAA 且 A,若
12、R是自反,反对称,传递,则称R为偏序关系通惯用表示偏序关系,读作“小于等于”R xRy xy“严格小于”:xy xy xy偏序集(poset):,是A上偏序关系例子:,/10/1030集合论与图论第8讲第30页偏序集,AR=|x,yA xy,=|x,yA xy,AZ+=x|xZ x0|=|x,yA x|y/10/1031集合论与图论第8讲第31页偏序集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 ,/10/1032集合论与图论第8讲第32页偏序集A,是由A一些划分组成集合加细=|x,y
13、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 ,.#/10/1033集合论与图论第8讲第33页哈斯图(Hasse diagram)设是偏序集,x,yA可比(comparable):x与y可比 xy yx覆盖(cover):y覆盖x xy z(zA xzy)哈斯图:当且仅当y覆盖x时,在x与y之间画无向边,而且x画在y下方/10/1034集合论与图论第8讲第34页例16(1)(2)例16:画出以下偏序关系哈斯图.(1),A=1,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 关系 公共课 一等奖 全国 获奖 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。