资源描述：
《离散数学(3.10等价关系和等价类).ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、1离散数学(DiscreteMathematics)张捷第三章集合与关系（SetsandRelations)3.6关系的闭包运算(ClosureOperations)3.7集合的划分与覆盖(Partition&CoverofSets)3.8等价关系(EquivalentRelations)3.9相容关系(Compatibility Relations)3.10序关系(OrderedRelations)3.1集合及其运算(Sets&Operationswithsets)3.2序偶与笛卡尔积(OrderedPairs&CartesianPro
2、duct)3.3关系(Relations)3.4关系的性质(ThePropetiesofRelations)3.5复合关系与逆关系(CompoundRelations&InverseRelations)3.8等价关系与等价类(EquivalenceRelations&Equivalenceclasses)3.8.1等价关系的定义(TheDefinitionofEquivalenceRelation)3.8.2等价类的性质(ThePropertiesofEquivalenceclass)3.8.3等价关系与划分(EquivalenceRel
3、ations&Partitions)第三章集合与关系(Sets&Relations)3.8.1等价关系的定义(TheDefinitionofEquivalenceRelation)1.等价关系定义3.8.1集合A上的关系ρ，如果它是自反的，对称的，且可传递的，则称ρ是A上的等价关系。例如数的相等关系是任何数集上的等价关系。又例如一群人的集合中姓氏相同的关系也是等价关系。但父子关系不是等价关系，因为它不可传递。例1设A是任意集合，则A上的恒等关系和全域关系UA均是A上的等价关系。例2设，A上的关系ρ是A上的等价关系。例3设m为大于等于2的正
4、整数，整数集Z上的同余关系则ρ是集合Z上的等价关系，称为Z上的模m同余关系。有时写成或2.元素a与b等价设ρ是集合A上的等价关系，若元素aρb，则称a与b等价，或称b与a等价。3.等价类定义3.8.2设ρ是集合A上的等价关系，则A中等价于元素a的所有元素组成的集合称为a生成的等价类，用表示，即a称为等价类的代表元素。显然有例4对于例2中的ρ来说例5整数集Z关于模3同余关系ρ的等价类共有三个：而恰好为Z的一个划分。1.对任意,3.8.2等价类的性质(ThePropertiesofEquivalenceclass)因为对于任意的a∈A,有aρ
5、a，所以。2.对任意的a,b∈A有aρb当且仅当。由ρ的对称性有xρa，证明“”若，则aρx，又由aρb及ρ的传递性有xρb，因此故。类似地可以证明由上得3.8.2等价类的性质(ThePropertiesofEquivalenceclass)2.对任意的a,b∈A有aρb当且仅当证明(续)“”由，知因此有aρb.与相矛盾。3.对任意a,b∈A，若，则.证明（用反证法）假设,则A中至少有一元素因此且，即xρa，且xρb,于是由aρx,xρb，得aρb，故例6设A={a,b,c,d}，A上的关系ρ是A上的等价关系同一个等价类中元素均相互等价。
6、不同等价类中的元素互不等价。3.8.3等价关系与划分(EquivalenceRelations&Partitions)集合A上的等价关系与集合A上的划分具有一一对应关系.定理3.8.1设ρ是集合A上的一个等价关系，则集合A中所有元素产生的等价类的集合是A的一个划分。（1）对每一元素a∈A，是A的非空子集。（2）对任意a,b∈A，或者与是A的同一子集或者（3）对所有的元素的等价类求并集，显然有.另一方面，对任一，而所以，因此，故。定义3.8.3设ρ是集合A上的等价关系,其所有不同等价类的全体所组成的A的划分称为A关于ρ的商集，记作。例如在集
7、合A={a,b,c,d}上，例2中A关于等价关系ρ的商集为例5中Z关于模3同余关系ρ的商集为例6中A关于等价关系ρ的商集为定理3.8.2设是集合A的一个划分，则存在A上的一个等价关系ρ，使得S是A关于ρ的商集。证明：在集合A上定义一个关系ρ，对于任意的a,b∈A，当且仅当a与b在同一分划块中时，有aρb。对任意a∈A，a与a在同一分划块中，所以有aρa，即ρ自反。又对任意的a,b∈A,若a与b在同一分划块中，则b与a在同一分划块中.即,若aρb,则bρa,因此ρ是对称的.对于任意a,b,c∈A，若a与b在同一分划块中，b与c在同一分划块中
8、，因为，所以a与c也在同一分划块中，此即,若aρb，bρc，则必有aρc，因此ρ是可传递的。由定理3.8.2可知:由集合A的划分所确定的A上的等价关系ρ为例7设A={a,b,c,d}，A上的划
