1、1离散数学离散数学 (Discrete Mathematics)张捷第三章 集合与关系（ Sets and Relations) 3.6 关系的闭包运算 (Closure Operations)3.7 集合的划分与覆盖 (Partition & Cover of Sets) 3.8 等价关系 (Equivalent Relations) 3.9 相容关系 (Compatibility Relations) 3.10 序关系 (Ordered Relations)3.1 集合及其运算 (Sets & Operations with sets) 3.2 序偶与笛卡尔积 (Ordered Pairs
2、 & Cartesian Product)3.3 关系 (Relations) 3.4 关系的性质 (The Propeties of Relations) 3.5 复合关系与逆关系 (Compound Relations & InverseRelations)3.8 等价关系与等价类 (Equivalence Relations & Equivalence classes ) 3.8.1等价关系的定义 (The Definition of Equivalence Relation ) 3.8.2等价类的性质 (The Properties of Equivalenceclass )3.8.3
3、等价关系与划分 (Equivalence Relations & Partitions)第三章 集合与关系 (Sets & Relations)3.8.1等价关系的定义 (The Definition ofEquivalence Relation )1. 等价关系 定义 3.8.1集合 A上的关系 ，如果它是自反的，对称的，且可传递的，则称 是 A上的等价关系。 例如 数的相等关系是任何数集上的等价关系。 又例如 一群人的集合中姓氏相同的关系也是等价关系。但父子关系不是等价关系，因为它不可传递。 例 1 设 A是任意集合，则 A上的恒等关系和全域关系 UA均是 A上的等价关系。例 2 设 ，
4、A上的关系 是 A上的等价关系。 例 3 设 m为大于等于 2的正整数，整数集 Z上的同余关系则 是集合 Z上的等价关系，称为 Z上的模 m同余关系。有时写成 或2. 元素 a与 b等价 设 是集合 A上的等价关系，若元素 ab ，则称 a与 b等价，或称 b与 a等价。 3. 等价类 定义 3.8.2 设 是集合 A上的等价关系，则 A 中等价于元素 a 的所有元素组成的集合称为 a 生成的等价类，用 表示，即 a称为 等价类 的代表元素。显然有例 4 对于例 2中的 来说例 5 整数集 Z关于模 3同余关系 的等价类共有三个：而 恰好为 Z 的一个划分。1. 对任意 , 3.8.2等价类的
5、性质 (The Properties of Equivalence class )因为对于任意的 aA ,有 aa ，所以 。2. 对任意的 a,bA 有 ab 当且仅当 。由 的对称性有 xa ， 证明 “ ” 若 ，则 ax ， 又由 ab 及 的传递性有 xb ，因此 故 。 类似地可以证明由上得3.8.2等价类的性质 (The Properties of Equivalence class )2. 对任意的 a,bA 有 ab 当且仅当 证明 (续 ) “ ” 由 ，知 因此有 ab . 与 相矛盾。3. 对任意 a,bA ，若 ，则 .证明 （用反证法）假设 , 则 A中至少有一元素 因此 且 ， 即 xa ，且 xb , 于是由 ax,xb ，得 ab ，故
