9.5-relations

《9.5-relations》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、9.5EquivalenceRelations22021/9/16CollegeofComputerScience&Technology,BUPTDefinitionArelationRonasetAisanequivalencerelation(等价关系)iffRisreflexivesymmetrictransitiveItiseasytorecognizeequivalencerelationsusingdigraphs.32021/9/16CollegeofComputerScience&Technology,BUPTEquivalencerela

2、tionsThesubsetofallelementsrelatedtoaparticularelementformsauniversalrelation(containsallpossiblearcs)onthatsubset.The(sub)digraphrepresentingthesubsetiscalledacomplete(sub)digraph.Allarcsarepresent.Thenumberofsuchsubsetsiscalledtherankoftheequivalencerelation.42021/9/16CollegeofC

3、omputerScience&Technology,BUPTExamples:Ahas3elements23123123152021/9/16CollegeofComputerScience&Technology,BUPTEquivalenceclassEachofthesubsetsiscalledanequivalenceclass.Abracketaroundanelementmeanstheequivalenceclassinwhichtheelementlies.[x]={y

4、(x,y)isinR}Theelementinthebracketis

5、calledarepresentative(代表元)oftheequivalenceclass.Wecouldhavechosenanyone.62021/9/16CollegeofComputerScience&Technology,BUPTExampleLetAbethesetofalltrianglesintheplaneandletRbetherelationonAdefinedasfollows:R={(a,b)AA

6、aiscongruenttob}.ItiseasytoseethatRisanequivalencerelation.7202

7、1/9/16CollegeofComputerScience&Technology,BUPTExampleLetA=ZandletR={(a,b)A×A

8、aandbyieldthesameremainderwhendividedby2}.Showcongruencemod2isanequivalencerelationnote2iscalledthemodulusab(mod2)“aiscongruenttobmod2.“(模2同余)82021/9/16CollegeofComputerScience&Technology,BUPTSolution,a

9、typicalwayFirstclearlyaa(mod2).ThusRisreflexive.Secondifab(mod2),thenaandbyieldthesameremainderwhendividedby2,soba(mod2).Rissymmetric.Finallysupposethatab(mod2)andbc(mod2).Thena,b,andcyieldthesameremainderwhendividedby2.Thus,ac(mod2).Ristransitive.Hencecongruencemod2isanequi

10、valencerelation.92021/9/16CollegeofComputerScience&Technology,BUPTEquivalenceRelationsandPartitionsIfPisapartitionofasetA,thenPcanbeusedtoconstructanequivalencerelationonA.102021/9/16CollegeofComputerScience&Technology,BUPTTheorem1LetPbeapartitionofasetA.DefinetherelationRonAasfol

11、lows:aRbIfandonlyifaandbaremember