[工学]_特殊关系.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 解 (续) 1、对?x∈A，有(x-x)被12所整除，所以x,x∈R，即R是自反的。 2、对?x,y∈A,若x,y∈R,有(x-y)被12整除，则(y-x)＝-(x-y)被12整除,所以,y,x∈R,即R是对称的。 3、对?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是传递的. 由1,2,3知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}。 例7.2.3 证明 (1)　对?x?Z，有n|(x-x)，所以x,x?R，即R是自反的。 (2)　对?x,y?Z，若x,y?R，即n|(x-y)，所以 m|(y-x)，所以，y,x?R，即R是对称的。 (3)　对?x,y,z?Z，若x,y?R且y,z?R，有n|(x-y)且n|(y-z)，所以由(x-z)=(x-y)+(y-z)得n|(x-z)， 所以，x,z?R，即R是传递的。 由(1)、(2)、(3)知，R是Z上的等价关系。 ■ 以n为模的同余关系(CongruenceRelation) 上述R称为Z上以n为模的同余关系，记xRy为 x＝y(mod n) 称为同余式。如用resn(x)表示x除以n的余数，则 x＝y(mod n) ? resn(x)＝resn(y)。 说明 同样地，这n个Z的子集具有如下特点： 1、在同一个子集中的元素之间都有关系R； 2、不同子集的元素之间没有关系R； 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.4 试给出非空集合A上2个不同的划分 解（1）在A中设定一个非空子集A1，令A2=A-A1，则根据集合划分的定义，{A1,A2}就构成了集合A的一个划分，见图 (a)； （2）在A中设定两个不相交非空子集A1和A2，令A3=A-(A1∪A2)，则根据集合划分的定义，{A1,A2,A3}就构成了集合A的一个划分，见图 (b)。 例7.2.5 设设A={0,1,2,4,5,8,9}， 1、写出R是A上的以4为模的同余关系R的所有元素； 2、求分别与元素1,2,3,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的等价类(equivalence class)，或叫作由x生成的一个R等价类，其中x称为[x]R的生成元(或叫代表元，或典型元)(generator) 。 由定义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.5(续) 设A={0,1,2,4,5,8,10}，R是A上的以4为模的同余关系。求 （1）R的所有等价类；（2）画出R的关系图。 定理7.2.1 设R是非空集合A上的等价关系，则有下面的结论成立： 定理7.2.1的证明 2) 对任意x,y∈A，若y∈[x]R，则x,y∈R。 定理7.2.1的证明（续） 商 集 定义7.2.4 设R是非空集合A上的等价关系，由R确定的一切等价类的集合，称为集合A上关于R的商集(QuotientSet)，记为A/R，即 A/R＝{[x]R|(x∈A)} 例7.2.7 设集合A={1,2,3,4,5,8}，R为A上以3为模的