资料课件讲义英文版课件4 4

4.4PropertiesofRelations关系的性质,Inmanyapplicationstocomputerscienceandappliedmathematics,wedealwithrelationsonasetAratherthanrelationsfromAtoB.Moreover,theserelationsoftensatisfycertainpropertiesthatwillbediscussedinthissection.,1.ReflexiveandIrreflexiveRelations,(a).ArelationRonasetAisreflexive(自反的)if(a,a)RforallaA,thatis,ifaRaforallaA.(b).ArelationRonasetAisirreflexive(非自反的)ifaaforeveryaA.ThusRisreflexiveifeveryelementaAisrelatedtoitselfanditisirreflexiveifnoelementisrelatedtoitself.,Example1:Let=(a,a)|aA,sothatistherelationofequalityonthesetA.Thenisreflexive,since(a,a)forallaA.LetR=(a,b)AA|ab,sothatRistherelationofinequalityonthesetA.ThenRisirreflixive,since(a,a)RforallaA.,(c)LetA=1,2,3,andletR=(1,1),(1,2).ThenRisnotreflexivesince(2,2)Rand(3,3)R.Also,Risnotirreflexive,since(1,1)R.(d)LetAbeanonemptyset.LetR=AA,theemptyrelation.ThenRisnotreflexive,since(a,a)RforallaA(theemptysethasnoelements).However,Risirreflexive.,Wecanidentifyareflexiveorirreflexiverelationbyitsmatrixasfollows：Thematrixofareflexiverelation(自反关系)musthaveall1sonitsmaindiagonal；Thematrixofanirreflexiverelation(非自反关系)musthaveall0sonitsmaindiagonal.,Similarly,wecancharacterizethedigraphofareflexiveorirreflexiverelationasfollows:Areflexiverelation(自反关系)hasacycleoflength1ateveryvertex;Anirreflexiverelation(非自反关系)hasnocyclesoflength1.,AnotherusefulwayofsayingthesamethingusestheequalityrelationonasetA:RisreflexiveifandonlyifR,andRisirreflexiveifandonlyifR=.Finally,wemaynotethatifRisreflexiveonasetA,thenDom(R)=Ran(R)=A.,2.Symmetric(对称),Asymmetric(非对称)andAntisymmetric(反对称)Relations,1.ArelationRonasetAissymmetric(对称的)ifwheneveraRb,thenbRa.ItthenfollowsthatRisnotsymmetricifwehavesomeaandbAwithaRb,butba.,2.ArelationRonasetAisasymmetric(非对称的)ifwheneveraRb,thenba.ItthenfollowsthatRisnotasymmetricifwehavesomeaandbAwithbothaRbandbRa.,Symmetric(对称),Asymmetric(非对称)andAntisymmetric(反对称)Relations,3.ArelationRonasetAisantisymmetric(反对称的)ifwheneveraRbandbRa,thena=b.ThecontrapositiveofthisdefinitionisthatRisantisymmetricifwheneverab,thenaborba.ItfollowsthatRisnotantisymmetricifwehaveaandbinA,ab,andbothaRbandbRa.,Antisymmetric(反对称)Relations,GivenarelationR,weshallwanttodeterminewhichpropertiesholdforR.Keepinmindthefollowingremark:Apropertyfailstoholdingeneralifwecanfindonesituationwherethepropertydoesnothold.,Solution,Symmetry:Ifab,thenitisnottruethatba,soRisnotsymmetric.Asymmetry:Ifab,thenba(bisnotlessthana),soRisasymmetric.Antisymmetry:Ifab,theneitheraborba,sothatRisantisymmetric.,Example2:LetA=Z,thesetofintegers,andletR=(a,b)AA|ab，sothatRistherelationlessthan.IsRsymmetric,asymmetric,orantesymmetric?,Example3:LetAbeasetofpeopleandletR=(x,y)AA|xisacousinofy.ThenRisasymmetricrelation(verify).Example4:LetA=1,2,3,4andletR=(1,2),(2,2),(3,4),(4,1).ThenRisnotsymmetric,since(1,2)R,but(2,1)R.Also,Risnotasymmetric,since(2,2)R.Finally,Risantisymmetric,sinceifab,either(a,b)Ror(b,a)R.,Example5:LetA=Z+,thesetofpositiveintegers,andletR=(a,b)AA|adividesb.IsRsymmetric,asymmetric,orantisymmetric?,Solution：Ifa|b,itdoesnotfollowthatb|a,soRisnotsymmetric.Forexample,2|4,but4|2.Ifa=b=3,say,thenaRbandbRa,soRisnotasymmetric.Ifa|bandb|a,thena=b,soRisantisymmetric.,Relatesymmetric,asymmetric,andantisymmetricpropertiesofarelationtopropertiesofitsmatrix:1.ThematrixMR=mijofasymmetricrelationsatisfiesthepropertythatifmij=1,thenmji=1;Moreover,ifmji=0,thenmij=0.ThusMRisamatrixsuchthateachpairofentries,symmetricallyplacedaboutthemaindiagonal,areeitherboth0orboth1.ItfollowsthatMR=MTR,sothatMRisasymmetrecmatrix.,2.ThematrixMR=mijofanasymmetricrelationRsatisfiesthepropertythatifmij=1,thenmji=0.IfRisasymmetric,itfollowsthatmii=0foralli;thatis,themaindiagonalofthematrixMRconsistsentirelyof0s.Thismustbetruesincetheasymmetricpropertyimpliesthatifmii=1,thenmii=0,whichisacontradiction(矛盾),3.ThematrixMR=mijofanantisymmetricrelationRsatisfiesthepropertythatifij,thenmij=0ormji=0.,Example6:Considerthematricesnext,eachofwhichisthematrixofarelation,asindicated.,RelationsR1andR2aresymmetricsincethematricesMR1andMR2aresymmetricmatrices.RelationR3isantisymmetric,sincenosymmetricallysituated,off-diagonalpositionsofMR3bothcontain1s.Suchpositionsmaybothhave0s,however,andthediagonalelementsareunrestricted.TherelationR3isnotasymmetricbecauseMR3has1sonthemaindiagonal.,RelationR4hasnoneofthethreeproperties:MR4isnotsymmetric.Thepresenceofthe1sinpositions4,1and1,4ofMR4violatesbothasymmetryandantisymmetry.Finally,R5isantisymmetricbutnotasymmetric,andR6isbothasymmetricandantisymmetric.,Thedigraphsofthesethreetypesofrelations:IfRisanasymmetric(非对称)relation,thenthedigraphofRcannotsimultaneouslyhaveanedgefromvertexitovertexjandanedgefromvertexjtovertexi.Thisistrueforanyiandj,andinparticularifiequalsj.Thustherecanbenocyclesoflength1,andalledgesare“one-waystreets.”,IfRisanantisymmetricrelation,thenfordifferentverticesiandjtherecannotbeanedgefromvertexitovertexjandanedgefromvertexjtovertexi.Wheni=j,noconditionisimposed.Thustheremaybecyclesoflength1,butagainalledgesare“oneway.”,Weconsiderthedigraphsofsymmetricrelationsinmoredetail：ThedigraphofasymmetricrelationRhasthepropertythatifthereisanedgefromvertexitovertexj,thenthereisanedgefromvertexjtovertexi.Thus,iftwoverticesareconnectedbyanedge,theymustalwaysbeconnectedinbothdirections.Therefore,itispossibleandquiteusefultogiveadifferentrepresentationofasymmetricrelation：,Wekeeptheverticesastheyappearinthedigraph,butiftwoverticesaandbareconnectedbyedgesineachdirection,wereplacethesetwoedgeswithoneundirectededge,ora“two-waystreet.”Thisundirectededgeisjustasinglelinewithoutarrowsandconnectsaandb.Theresultingwillbecalledthegraphofthesymmetricrelation.,Example7:LetA=a,b,c,d,eandletRbethesymmetricrelationgivenbyR=(a,b),(b,a),(a,c),(c,a),(b,c),(c,b),(b,e),(e,b),(e,d),(d,e),(c,d),(d,c).NotethateachundirectededgecorrespondstotwoorderedpairsintherelationR.,a,c,e,b,d,b,d,e,c,a,GraphofR(b),DigraphofR(a),Anundirectededgebetweenaandb,inthegraphofasymmetricrelationR,correspondstoaseta,bsuchthat(a,b)Rand(b,a)R.Sometimeswewillalsorefertosuchaseta,basanundirectededge(无向边)oftherelationRandcallaandbadjacentvertices(邻接顶点).,AsymmetricrelationRonasetAiscalledconnected(连通的)ifthereisapathfromanyelementofAtoanyotherelementofA.ThissimplymeansthatthegraphofRisallinonepiece(都在一个块中).InFigure4.21weshowthegraphsoftwosymmetricrelations.ThegraphinFigure4.21(a)isconnected,whereasthatinFigure4.21(b)isnotconnected.,c,d,e,b,a,5,4,3,2,1,(a),(b),3.TransitiveRelations传递关系,WesaythatarelationRonasetAistransitive(传递的)ifwheneveraRbandbRc,thenaRc.Itisoftenconvenienttosaywhatitmeansforarelationtobenottransitive.ArelationRonAisnottransitiveifthereexista,b,andcinAsothataRbandbRc,butac.Ifsucha,bandcdonotexist,thenRistransitive.,Example8:LetA=Z,thesetofintegers,andletRbetherelationlessthan.ToseewhetherRistransitive,weassumethataRbandbRc.Thusabandbc.Itthenfollowsthatac,soaRc.HenceRistransitive.Example9:LetA=Z+andletRbetherelationconsideredinExample5.IsRtransitive?,Solution：SupposethataRbandbRc,sothata|bandb|c.Itthendoesfollowthata|c.ThusRistransitive.,Example10:LetA=1,2,3,4andletR=(1,2),(1,3),(4,2).IsRtransitive?,Solution：Sincethereareonelementsa,b,andcinAsuchthataRbandbRc,butac,weconcludethatRistransitive.,Statement:ArelationRistransitiveifandonlyifitsmatrixMR=mijhastheproperty:ifmij=1andmjk=1,thenmik=1.,Theleft-handsideofthisstatementsimplymeansthat(MR)2hasa“1”inpositioni,k.ThusthetransitivityofRmeansthatif(MR)2hasa“1”inanyposition,thenMRmusthavea“1”inthesameposition.Thus,inparticular,if(MR)2=MR,thenRistransitive.Theconverseisnottrue.,Example11:LetA=1,2,3andletRbetherelationonAwhosematrixisShowthatRistransitive.,Solution:Bydirectcomputation,(MR)2=MR;therefore,Ristransitive.,Toseewhattransitivitymeansforthedigraphofarelation,wetranslatethedefinitionoftransitivityintogeometricterms：Ifweconsiderparticularverticesaandc,thecond