3.5等价关系和划分.pptVIP

南京信息工程大学数理学院 南京信息工程大学 离散数学教学组 制作 离 散 数 学 电 子 课 件 * 南京信息工程大学数理学院 * 第三章 二元关系 3.1 基本概念 3.2 关系的合成 3.3 关系上的闭包运算 3.4 次序关系 3.5 等价关系和划分 * 南京信息工程大学数理学院 * 第3-5讲 等价关系和划分 1. 等价关系 2. 划分 3. 划分的积与和 4. 第3-5讲 作业 * 南京信息工程大学数理学院 * 等价关系是最重要、最常见的二元关系之一。它有良好的性质。在计算机科学和计算机技术、信息科学和信息工程中都有广泛的应用。 定义1 设R?A×A，如果R是自反的、对称的和传递的，则称R是A上的等价关系。设R是等价关系，若?x,y??R，称x等价于y。 例如：三角形的相似关系是等价关系 等价关系的特性 关系矩阵：主对角线全为1且是对称矩阵； 关系图：每一个结点上都有自回路；每两个不同结点间或没有弧线连接，或有成对弧出现。 1、等价关系 * 南京信息工程大学数理学院 * 例1 设A=?1,2,3,4,5?，R是A上的二元关系， R=??1,1?,?1,2?,?2,1?,?2,2?,?3,3?,?3,4?,?4,3?,?4,4?,?5,5??，证明R是A上的等价关系。 证明：写出R的关系矩阵MR如下： ? ? MR的主对角线全为1且是对称阵，所以R是自反的和对称的；还可以用二元关系传递性的定义证明R是传递的。故R是A上的等价关系。 * 南京信息工程大学数理学院 * 在R的关系图中每一个结点上都有自回路；每两个不同结点间如果有边，一定有方向相反的两条边。所以R是自反的和对称的。与前面一样，也可以用二元关系传递性的定义证明R是传递的。故R是A上的等价关系。 注：等价关系R的关系图被分为三个互不连通的部分。每部分中的结点两两都有关系，不同部分中的任意两个结点则没有关系。 * 南京信息工程大学数理学院 * 定义2 设x和y是两个整数，k是一个正整数，若x，y用k除的余数相等，就称x和y模k同余，也称x和y模k等价。记为 x ≡ y (mod k) 设x (y)用k除的商为t1 (t2 )，余数为a1 ( a2 )，数学上将x(y)表示成为： x= k×t1＋a1， t1?I，a1?I 且 0≤a1＜k。 y= k×t2＋a2， t2?I，a2?I 且 0≤a2＜k。 若x，y用k除的余数相等，x-y= k×(t1-t2)，t1-t2?I。 即x-y可以被k整除。所以，x和y模k同余还可以描述为：x-y可以被k整除。 * 南京信息工程大学数理学院 * 例2 设R=??x,y?? x?I ∧ y?I ∧ x ≡ y （mod k）?是整数集合I上的二元关系。证明R是等价关系。 证明：设a,b,c是任意的整数。 ⑴ 因为 a-a=k×0，所以 a≡a mod k，?a,a??R。故R是自反的。 ⑵ 若?a,b??R，a ≡ b mod k，a-b = k×t，t?I，b-a =-(a-b)=k×(–t)，–t?I，b≡a mod k，?b,a??R。故R是对称的。 ⑶ 若?a,b??R且?b,c??R， a-b = k×t1，t1?I，b-c = k×t2， t2 ?I， a-c=(a-b)+(b-c)=k×t1+k×t2=k×(t1+t2)，t1+t2?I，?a,c??R，故R是传递的。 所以R是整数集合I上的等价关系。 * 南京信息工程大学数理学院 * 定义3 设R是A上的等价关系，?x?A，集合 ?y ? y?A∧xRy ? 叫做x形成的R等价类。记为 [x]R 在例1中，等价关系R等价类为：[1]R=[2]R=?1,2?，[3]R=[4]R=?3,4?，[5]R=?5?。在R的关系图中，三个互不连通的部分，每一部分中的所有结点构成一个等价类。 上述模3等价关系的等价类叫模3等价类，模3等价类有以下三个： [0]R=?…，–6，–3，0，3，6，… ? [1]R=?…，–5，–2，1，4，7，… ? [2]R=?…，–4，–1，2，5，8，… ?