复旦大学 赵一鸣 离散数学 三

1.InverserelationDefinition2.13:LetRbearelationfromAtoB.TheinverserelationofRisarelationfromBtoA,wewriteR-1,definedbyR-1={(b,a)|(a,b)R}2.4OperationsonRelations

1Theorem2.1：LetR,R1,andR2berelationfromAtoB.Then(1)(R-1)-1=R;(2)(R1∪R2)-1=R1-1∪R2-1;(3)(R1∩R2)-1=R1-1∩R2-1;(4)(A×B)-1=B×A;(5)-1=;(7)(R1-R2)-1=R1-1-R2-1(8)IfR1R2thenR1-1R2-12Theorem2.2：LetRbearelationonA.ThenRissymmetricifonlyifR=R-1.Proof:(1)IfRissymmetric,thenR=R-1。RR-1andR-1R。(2)IfR=R-1,thenRissymmetricForany(a,b)R,(b,a)?R

32.CompositionDefinition2.14:LetR1bearelationfromAtoB,andR2bearelationfromBtoC.ThecompositionofR1andR2,wewriteR2R1,isarelationfromAtoC,andisdefinedR2R1={(a,c)|thereexistsomebBsothat(a,b)R1and(b,c)R2,whereaAandcC}.(1)R1isarelationfromAtoB,andR2isarelationfromBtoC(2)commutativelaw?

R1={(a1,b1),(a2,b3),(a1,b2)}R2={(b4,a1),(b4,c1),(b2,a2),(b3,c2)}

4Associativelaw?ForR1

A×B,R2B×C,andR3C×DR3(R2R1)=?(R3R2)R1subsetofA×DForany(a,d)R3(R2R1),(a,d)?(R3R2)R1,Similarity,(R3R2)R1R3(R2R1)Theorem2.3：LetR1bearelationfromAtoB,R2bearelationfromBtoC,R3bearelationfromCtoD.ThenR3(R2R1)=(R3R2)R1(Associativelaw)5Definition2.15:Let

RbearelationonA,andnN.TherelationRnisdefinedasfollows.(1)R0={(a,a)|aA}),wewriteIA.(2)Rn+1=RRn.Theorem2.4:Let

RbearelationonA,andm,nN.Then(1)RmRn=Rm+n(2)(Rm)n=Rmn6A={a1,a2,,an},B={b1,b2,,bm}R1andR2berelationsfromAtoB.MR1=(xij),MR2=(yij)MR1∪R2=(xijyij)MR1∩R2=(xijyij)01010

010

001

111

01Example:A={2,3,4},B={1,3,5,7}R1={(2,3),(2,5),(2,7),(3,5),(3,7),(4,5),(4,7)}R2={(2,5),(3,3),(4,1),(4,7)}InverserelationR-1ofR:MR-1=MRT,MRTisthetransposeofMR.7A={a1,a2,,an},B={b1,b2,,bm},C={c1,c2,,cr},R1bearelationsfromAtoB,MR1=(xij)mn,R2bearelationfromBtoC,MR2=(yij)nr.ThecompositionR2R1ofR1andR2,8Example：R={(a,b),(b,a),(a,c)},isnotsymmetric+(c,a),R'={(a,b),(b,a),(a,c),(c,a)}，R'

issymmetric.Closure92.5ClosuresofRelations1.IntroductionConstruct

anewrelationR‘,

s.t.RR’,

particularproperty,smallestrelationclosureDefinition2.17:LetRbearelationonasetA.R'iscalledthereflexive(symmetric,transitive)closureofR,wewriter(R)(s(R),t(R)orR+),ifthereisarelationR'withreflexivity(symmetry,transitivity)containingRsuchthatR'isasubsetofeveryrelationwithreflexivity(symmetry,transitivity)containingR.10Condition:1)R'isreflexivity(symmetry,transitivity)2)RR'3)Foranyreflexive(symmetric,transitive)relationR",IfRR",thenR'R"Example：IfRissymmetric,s(R)=?IfRissymmetric，thens(R)=RContrariwise,Ifs(R)=R，thenRissymmetricRissymmetricifonlyifs(R)=RTheorem2.5:LetRbearelationonasetA.Then(1)Risreflexiveifonlyifr(R)=R(2)Rissymmetricifonlyifs(R)=R(3)Ristransitiveifonlyift(R)=R11Theorem2.6:LetR1andR2berelationsonA,andR1R2.Then(1)r(R1)r(R2)；(2)s(R1)s(R2)；(3)t(R1)t(R2)。Proof:(3)R1R2t(R1)t(R2)BecauseR1R2，R1t(R2)t(R2):transitivity12Example:LetA={1,2,3},R={(1,2),(1,3)}.Then2.ComputingclosuresTheorem2.7:LetRbearelationonasetA,andIAbeidentity(diagonal)relation.Thenr(R)=R∪IA(IA={(a,a)|aA})Proof：LetR'=R∪IA.Definitionofclosure(1)ForanyaA,(a,a)?R'.(2)R?R'.(3)SupposethatR''isreflexiveandRR''，R'?R''13Theorem2.8：LetRbearelationonasetA.Thens(R)=R∪R-1.Proof：LetR'=R∪R-1Definitionofclosure(1)R',symmetric?(2)R?R'.(3)SupposethatR''issymmetricandRR''，R'?R'')14Example：symmetricclosureof“<”onthesetofintegers,is“≠”<,>，LetAisnoemptyset.ThereflexiveclosureofemptyrelationonAistheidentityrelationonAThesymmetricclosureofemptyrelationonA,isanemptyrelation.15Theorem2.9:LetRbearelationonA.Then

Theorem2.10：LetAbeasetwith|A|=n,andletRbearelation