离散数学PPT电子教案-第07章_特殊关系.ppt

第三篇 二元关系 第7章 特殊关系 7.0 内容提要 7.1 本章学习要求 判定下列关系具有哪些性质 1、在全体中国人所组成的集合上定义的“同姓”关系; 2、对任何非空集合A, A上的全关系; 3、三角形的“相似关系”、“全等关系”; 4、直线的“平行关系” ; 5、“朋友”关系； 7.2 等价关系 定义7.2.1设R是定义在非空集合A上的关系，如果R是自反的、对称的、传递的，则称R为A上的等价关系。 例7.2.1 判定下列关系是否是等价关系? 例7.2.2 例7.2.2 解 例7.2.2 解 (续) (3) ① 对?x∈A，有(x-x)被12所整除，所以x,x∈R, 即 R是自反的。 ② 对?x,y∈A, 若x,y∈R, 有(x-y)被12整除, 则 (y-x)＝-(x-y)被12整除, 所以 y,x∈R, 即R是对称的。 ③ 对?x,y,z∈A, 若x,y∈R且y,z∈R, 有(x-y)被12所整除且(y-z)被12所整除, 所以(x-z)＝(x-y)＋(y-z)被12所整除, 所以, x,z∈R, 即R是传递的. 由①②③知, R是等价关系。 从例7.2.2可以看出 关系R将集合A分成了如下的12个子集： {1, 13}, {2,14}, {3,15}, {4,16}, {5,17}, {6, 18}, {7,19}, {8,20}, {9,21}, {10,22}, {11,23}, {12,24}。 以n为模的同余关系 记xRy为 x＝y(mod n), 则 R 是Z上的等价关系。 如用resn(x)表示x除以n的余数，则 x＝y(mod n) ? resn(x)＝resn(y)。 7.2.2 集合的划分 定义7.2.2给定非空集合A，设有集合S={S1,S2,S3...Sm}. 如果满足 Si?A 且 Si≠?, i＝1,2,...,m; Si∩Sj＝?，i≠j, i,j＝1,2,...,m; 例7.2.5 设A={0,1,2,4,5,8,9}, R是A上的以4为模的同余关系。 (1) 写出R的所有元素； (2) 求分别与元素1,2,4有关系R的所有元素所作成的集合。 例7.2.5 解 7.2.3 等价类与商集 定义7.2.3 设R是非空集合A上的等价关系，对任意x∈A，称集合 [x]R＝{y|y∈A∧x,y∈R} 为x关于R的等价类，或叫作由x生成的一个R等价类，其中x称为[x]R的生成元 (或叫代表元) 。 由定义7.2.3可以看出： （1）等价类产生的前提: A上的关系R是等价关系； （2）A中所有与x有关系R的元素y构成了[x]R； （3）A中每个元素都对应一个由它生成的等价类； （4）R具有自反性意味着对?x∈A，[x]R≠?； （5）R具有对称性意味着对任意x, y∈A, 若有y∈[x]R, 则一定有x∈[y]R。 定理7.2.1 设R是非空集合A上的等价关系, 则有： 例7.2.5(续) 设A={0,1,2,4,5,8,9}, R是A上的以4为模的同余关系。 求（1）R的所有等价类；（2）画出R的关系图。 商 集 定义7.2.4 设R是非空集合A上的等价关系，由R确定的一切等价类的集合，称为集合A上关于R的商集, 记为A/R, 即 A/R＝{[x]R|(x∈A)} 计算商集A/R的通用过程： (1) 任选A中一个元素a, 计算[a]R； (2) 如果[a]R≠A, 任选一个元素b∈A-[a]R, 计算[b]R; (3) 如果[a]R∪[b]R≠A, 任选一个元素c∈A-[a]R-[b]R, 计算[c]R; 以此类推, 直到A中所有元素都包含在计算出的等价类中。 例7.2.7 设集合A={1,2,3,4,5,8}，R为A上以3为模的同余关系。求A/R。 解 根据例7.2.3知，A上以3为模的同余关系R是等价关系。因为 [1]R={1,4}=[4]R, [2]R=[5]R=[8]R={2,5,8}, [3]R={3}， 所以根据商集的定义，A/R={[1]R, [2]R, [3]R} ={{1,4}, {2,5,8}, {3}}。 练习: P217 6, 8 6. 设A={1,2,3,4}