离散数学课件(英文版)----Equivalence(II).ppt

《离散数学课件(英文版)----Equivalence(II).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、EquivalenceEquivalencePropertiesofRelationReflexivitySymmetryTransitivityEquivalenceEquivalenceandPartitionReflexivityRelationRonAisReflexiveifforallaA,(a,a)RIrreflexiveifforallaA,(a,a)RLetA={1,2,3},RAA{(1,1),(1,3),(2,2),(2,1),(3,3)}?{(1,2),(2,3),(3,1)}?{(1,2),(2,2),(2,3

2、),(3,1)}?RisreflexiverelationonAifandonlyifIARFIRNothingVisualizedReflexivityabcA={a,b,c}SymmetryRelationRonAisSymmetricifwhenever(a,b)R,then(b,a)RAntisymmetricifwhenever(a,b)Rand(b,a)Rthena=b.Asymmetricifwhenever(a,b)Rthen(b,a)R(Note:neitheranti-nora-symmetryisthenegat

3、iveofsymmetry)SymmetryLetA={1,2,3},RAA{(1,1),(1,2),(1,3),(2,1),(3,1),(3,3)}symmetric.{(1,2),(2,3),(2,2),(3,1)}antisymmetric.{(1,2),(2,3),(3,1)}antisymmetricandasymmetric.{(11),(2,2)}symmetricandantisymmetric.symmetricandantisymmetric,andasymmetric!VisualizedSymmetryA={a,b,c

4、}abcEveryedgehasitsreverseedgemi,j=mj,iVisualizedAntisymmetryA={a,b,c}abcExceptcycles,noedgehasreverseedge.mi,j+mj,i≤1fori≠júúúûùêêêëé=100101001RMVisualizedAsymmetryA={a,b,c}abcNocycle,noedgehasreverseedge.úúúûùêêêëé=000101000RMmi,i=0mi,j+mj,i≤1fori≠jTransitivityRelationRonAis

5、Transitivityifwhenever(a,b)R,(b,c)R,then(a,c)RLetA={1,2,3},RAA{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,3)}istransitive{(1,2),(2,3),(3,1)}isnottransitive.{(1,3)}??Transitive!VisualizedTransitivityabcA={a,b,c}RistransitiveifandonlyifRnRforalln1mi,j=1andmj,k=1thenmi,k=1Wha

6、t’sWrong?Awrongproof:ifRisasymmetricandtransitiverelationonA,thenRmustbereflexive.Proof:Foranya,bA,if(a,b)R,bythesymmetryofR,(b,a)R;sinceRistransitive,(a,a)R.So,Risreflexive.EquivalenceRelationRelationRonAisanequivalencerelationifandonlyifitisreflexible,symmetricandtransit

7、ive.“Equality”isaspecialcaseofequivalencerelation.Anexample:RZZ,(x,y)Rifandonlyifisinteger,i.e.xy(mod3)3:modulus,aiscongruenttobmod3EquivalenceRelationLetA={1,2,3,4,5,6}R:{<1,1>,<2,2>,…<6,6>,<1,4>,<2,5>,<3,6>,…,<6,3>}R(1),R(2),R(3),R(4),R(5),R(6)?R:+3Howabout+3inZ?R(100)?P

8、artitionGeneratedbyEquivalenceEquivalenceclass:LetRisaequival