1、1张捷第三章第三章 集合与关系集合与关系（Sets and Relations)Sets and Relations) 3.6 3.6 关系的闭包运算关系的闭包运算(Closure Operations)(Closure Operations)3.7 3.7 集合的划分与覆盖集合的划分与覆盖(Partition & Cover of Sets) (Partition & Cover of Sets) 3.8 3.8 等价关系等价关系(Equivalent Relations) (Equivalent Relations) 3.9 3.9 相容关系相容关系(Compatibility(Compa
2、tibilityRelations) Relations) 3.10 3.10 序关系序关系(Ordered Relations)(Ordered Relations)3.1 3.1 集合及其运算集合及其运算(Sets & Operations with sets)(Sets & Operations with sets) 3.2 3.2 序偶与笛卡尔积序偶与笛卡尔积(Ordered Pairs & Cartesian Product)(Ordered Pairs & Cartesian Product)3.3 3.3 关系关系 (Relations) (Relations) 3.4 3.4
3、关系的性质关系的性质(The Propeties(The Propeties of Relations) of Relations) 3.5 3.5 复合关系与逆关系复合关系与逆关系(Compound Relations & Inverse(Compound Relations & Inverse Relations) Relations)BABA 3.8 3.8 等价关系与等价类等价关系与等价类(Equivalence Relations & (Equivalence Relations & Equivalence classes ) Equivalence classes ) 3.8.13
4、.8.1等价关系的定义等价关系的定义(The Definition of (The Definition of Equivalence Relation ) Equivalence Relation ) 3.8.23.8.2等价类的性质等价类的性质(The Properties of Equivalence(The Properties of Equivalence class ) class )3.8.33.8.3等价关系与划分等价关系与划分(Equivalence Relations & (Equivalence Relations & Partitions) Partitions)第三章
5、第三章 集合与关系集合与关系(Sets & Relations)3.8.13.8.1等价关系的定义等价关系的定义(The Definition of(The Definition of Equivalence Relation ) Equivalence Relation )1. 1. 等价关系等价关系 定义定义3.8.13.8.1集合集合A A上的关系上的关系，如果它是自反的，对，如果它是自反的，对称的，且可传递的，则称称的，且可传递的，则称是是A A上的等价关系。上的等价关系。 例如例如 数的相等关系是任何数集上的等价关系。数的相等关系是任何数集上的等价关系。 又例如又例如 一群人的集合中
6、姓氏相同的关系也是一群人的集合中姓氏相同的关系也是等价关系。等价关系。但父子关系不是等价关系，因为它不可传递。但父子关系不是等价关系，因为它不可传递。 例例1 1 设设A A是任意集合，则是任意集合，则A A上的恒等关系和全上的恒等关系和全域关系域关系U UA A均是均是A A上的等价关系。上的等价关系。 例例2 2 设设 ，A A上的关系上的关系是是A A上的等价关系。上的等价关系。 例例3 3 设设m m为大于等于为大于等于2 2的正整数，整数集的正整数，整数集Z Z上的同余上的同余关系关系则则是集合是集合Z Z上的等价关系，称为上的等价关系，称为Z Z上的模上的模m m同余同余关系。有时
7、写成关系。有时写成 ,dcbaA,ddcddcccbbabbaaa,Zkbakmbaba)(mod,mbaZbaba 或或 2. 2. 元素元素a a与与b b等价等价 设设是集合是集合A A上的等价关系，若元素上的等价关系，若元素abab ，则，则称称a a与与b b等价，或称等价，或称b b与与a a等价。等价。 ,整除余数相同被和mbaZbaba3. 3. 等价类等价类 定义定义3.8.23.8.2 设设是集合是集合A A上的等价关系，则上的等价关系，则 A A 中等价中等价于元素于元素 a a 的所有元素组成的集合称为的所有元素组成的集合称为 a a 生成的等价生成的等价类，用类，用
8、表示，即表示，即 a|baAbba且a称为称为等价类等价类 的代表元素。的代表元素。a 显然有显然有例例4 4 对于例对于例2 2中的中的来说来说,babbaa,dcddcc例例5 5 整数集整数集Z Z关于模关于模3 3同余关系同余关系的等价类共有三个：的等价类共有三个：,3 , 6 , 3 , 0 , 3, 6,3,01nnZ, 13 , 7 , 4 , 1 , 2, 5, 13, 1 2nnZ, 23 , 8 , 5 , 2 , 1, 4, 23,23nnZ 30 36 1 425而而 恰好为恰好为 Z 的一个划分。的一个划分。2 1321,ZZZ1. 1. 对任意对任意 , 3.8.2
9、3.8.2等价类的性质等价类的性质(The Properties of (The Properties of Equivalence class )Equivalence class )因为对于任意的因为对于任意的aAaA, ,有有aaaa，所以，所以 。 2. 2. 对任意的对任意的a,bAa,bA 有有 abab 当且仅当当且仅当 。由由的对称性有的对称性有xaxa ， 证明证明 “ ” 若若 ，则，则axax ， 又由又由abab 及及的传递性有的传递性有xbxb ，因此，因此 Aaaaabaaxbx故故 。 ba类似地可以证明类似地可以证明由上得由上得abba3.8.23.8.2等价类
10、的性质等价类的性质(The Properties of (The Properties of Equivalence class )Equivalence class ) 2. 2. 对任意的对任意的a,bAa,bA 有有 abab 当且仅当当且仅当 ba 证明证明( (续续) ) “ ” 由由 ，知，知 因此有因此有abab. . abbba与与 相矛盾。相矛盾。ba3 . 3 . 对 任 意对 任 意 a , b Aa , b A ， 若， 若 ，则则 . .ba 证明证明（用反证法）（用反证法）假设假设 , , 则则A A中至少有一元素中至少有一元素 因此因此 且且 ，即即xaxa，且，
11、且xbxb, , 于是由于是由ax,xbax,xb，得，得abab，故故 babaxaxbxbaba例例6 6 设设A=a,b,c,dA=a,b,c,d ，A A上的关系上的关系是是A上的等价关系上的等价关系 同一个等价类中元素均相互等价。不同等价类同一个等价类中元素均相互等价。不同等价类中的元素互不等价。中的元素互不等价。 ,ddacbcabbbcccacbbaaa,cbacbadd3.8.33.8.3等价关系与划分等价关系与划分(Equivalence Relations & (Equivalence Relations & Partitions) Partitions)集合集合A A上的
12、等价关系与集合上的等价关系与集合A A上的划分具有一一对应关系上的划分具有一一对应关系. . 定理定理3.8.13.8.1设设是集合是集合A A上的一个等价关系，则集合上的一个等价关系，则集合A A中中所有元素产生的等价类的集合所有元素产生的等价类的集合 是是A A的一个划的一个划分。分。 （1 1）对每一元素）对每一元素aAaA， 是是A A的非空子集。的非空子集。 （2 2）对任意）对任意a,bAa,bA，或者，或者 与与 是是A A的同一子集或的同一子集或 者者 |AaaAaabba （3 3）对所有的元素的等价类求并集，显然有）对所有的元素的等价类求并集，显然有 . .AaAa另一方面
13、，对任一另一方面，对任一 ，而，而 ,xxAx有Aaax所以所以 ，因此，因此 ，故，故 。AaaxAaaAAaAaA定义定义3.8.3 3.8.3 设设是集合是集合A A上的等价关系上的等价关系, ,其所有不其所有不同等价类的全体所组成的同等价类的全体所组成的A A的划分称为的划分称为A A关于关于的的商集，记作商集，记作 。 例如例如 在集合在集合A=a,b,c,dA=a,b,c,d 上，例上，例2 2中中A A关于等价关于等价关系关系的商集为的商集为例例5 5中中Z Z关于模关于模3 3同余关系同余关系的商集为的商集为例例6 6中中A A关于等价关系关于等价关系的商集为的商集为 ,/db
14、dcbaA/A ,/cadcbaA2 , 1 ,0/A 定理定理3.8.23.8.2设设 是集合是集合A A的一个的一个划分，则存在划分，则存在A A上的一个等价关系上的一个等价关系，使得，使得S S是是A A关于关于的的商集。商集。 证明：证明： 在集合在集合A A上定义一个关系上定义一个关系，对于任意的，对于任意的a,bAa,bA，当且仅当，当且仅当a a与与b b在同一分划块中时，有在同一分划块中时，有abab。 对任意对任意aAaA，a a与与a a在同一分划块中，所以有在同一分划块中，所以有aaaa，即即自反。自反。 又对任意的又对任意的 a,bAa,bA, ,若若a a与与b b在
15、同一分划块中，则在同一分划块中，则b b与与a a在同一分划块中在同一分划块中. .即即, ,若若abab, , 则则baba , ,因此因此是对称的是对称的. . 对于任意对于任意a,b,cAa,b,cA，若，若a a与与b b在同一分划块中，在同一分划块中，b b与与c c在同一分划块中，在同一分划块中， 因为因为 ，所，所以以a a与与c c也在同一分划块中，此即也在同一分划块中，此即, ,若若abab，bcbc，则，则必有必有acac，因此，因此是可传递的。是可传递的。,21rAAAS)(jiAAji 由定理由定理3.8.23.8.2可知可知: : 由由集合集合A A的划分的划分 所确
16、定的所确定的A A 上的等价关系上的等价关系为为 ,21rAAASrrAAAAAA2211例例7 7 设设A=a,b,c,dA=a,b,c,d ，A A上的划分上的划分试求出等价关系试求出等价关系 和和 ，使得，使得 和和 的等价类的等价类分别是分别是 和和 的分划块。的分划块。 解解 定义定义A上等价关系上等价关系则则 定义定义A A上的等价关系上的等价关系则则,1dcbaS ,2dcbaS 12121S2S,1ddccbccbbbaa,/11dcbaSA,2ddccbbaa,/22dcbaSA例例8 8 设设A=a,b,cA=a,b,c ，求出，求出A A上所有的等价关系。上所有的等价关系
17、。解解 先求出先求出A A上有多少个不同的分划。上有多少个不同的分划。分成一个分划块的分划分成一个分划块的分划 分成两个分划块的分划分成两个分划块的分划 分成三个分划块的分划分成三个分划块的分划 ,1cbaS ,2cbaS ,4bacS ,3cabS ,5cbaS c ca ab b,2ccbccbbbaa因此，因此，A A上有上有5 5个不同的分划，如下图所示个不同的分划，如下图所示记与分划记与分划 相对应的等价关系为相对应的等价关系为a ab bc ca ab bc cb ba ac ca ac cb b54321SSSSSiSiAUccbcaccbbbabcabaaa,1,3ccaccaaabb,4bbabbaaaccAIccbbaa,5第三章第三章 集合与关系集合与关系(Sets & Relations)小结小结:本结介绍了等价关系和等价类的概念，本结介绍了等价关系和等价类的概念，并研究了它们的特性。重点是等价类的性质、并研究了它们的特性。重点是等价类的性质、商集的概念、等价关系与划分之间的密切联商集的概念、等价关系与划分之间的密切联系。系。Pg134 (2),(3),(6).Pg134 (2),(3),(6).
