离散数学 第三章特殊关系3.pptVIP

国际学院 特殊关系 　　在前面章节中定义了关系的5个性质，按照关系的性质可以将关系进行分类，本章将介绍三类特殊的关系——等价关系、相容关系和序关系。 3.1等价关系 3.1.1　集合的划分 定义3.1设A是一个集合，A1,A2,A3...Am是A的任何m个子集，如果A1,A2,A3...Am满足： 对一切的i≠j(i,j＝1,2,3,....,m)，都有Ai∩Aj＝Φ。 　。 例 设对于全集U,考虑： A={a,b,c}下列子集均是A的划分： I0 ={ {a},{b},{c} } I1 ={ {a},{b，c} } I2={ {a，b，c} } 例3.1 设对于全集U,考虑： 对任何的子集A?U,{I0,I1}构成了集合U的一个划分，其中，I0＝ ,I1＝A。 例3.1(续) 3.1.2 等价关系 定义3.2 设R是定义在集合A上的关系，如果R是自反的、对称的、传递的，则称此关系R为A上的等价关系。 例3.3 证明 (1)　对任意x?Z，有m|(x-x)，所以x,x?R，即R 是自反的。 (2)　对任意x,y?Z，若x,y?R，即m|(x-y)，所以 m|(y-x)，所以，y,x?R，即R是对称的。 (3)　对任意x,y,z?Z，若x,y?R且y,z?R，有m|(x-y) 且m|(y-z)，所以由(x-z)=(x-y)+(y-z)得m|(x-z)， 所以，x,z?R，即R是传递的。 由(1)、(2)、(3)知，R是Z上的等价关系。 ■ 以m为模的同余关系（补充） 上述R称为Z上以m为模的同余关系，一般记xRy为 x＝y(mod m) 称为同余式。如用resm(x)表示x除以m的余数，则 x＝y(mod m) ? resm(x)＝resm(y)。 以m为模的同余关系（补充） 　　这m个Z的子集具有的特点：在同一个子集中的元素之间都有关系R，而不同子集的元素之间无关系R。也就是说，通过等价关系，将集合分成若干子集，使这些子集构成的集合就是Z的一个划分。 3.1.3　等价类与商集 定义3.3设R是集合A上的等价关系,对任意x∈A,称集合 [x]R＝{y|(y∈A)∧(x,y∈R)} 为x关于R的等价类,或叫作由x生成的一个R等价类。其中x称为[x]R的生成元(或叫代表元，或典型元)。 例3.4 设A＝{1,2,3,4,5,8}，考虑R是A上的以3为模的同余关系，求其等价类。 等价类的性质 　　定理3.1设R是非空集合A上的等价关系，有下面结论成立： 等价类的性质 　　定理3.1设R是非空集合A上的等价关系，有下面结 等价类的性质 3) 对任意x,y∈A， 商 集 定义3.4设R是集合A上的等价关系，由R确定的一切等价类的集合，称为集合A上的关于R的商集，记为A/R，即 A/R＝{[x]R|(x∈A)}。 3.1.4　等价关系与划分 定理3.2　设R是非空集合A上的等价关系，则A上的关于R的商集A/R是A的一个划分，称之为由R所导出的等价划分。 定理3.3 设P(A)是非空集合A的一个划分，则A上的关系 RП＝{x,y|(x,y∈A)∧(x,y同属П(A)的一个划分块)｝ 是A上的等价关系，称之为由P(A)所导出的等价关系。 即若设П(A)＝{A1,A2,A3,....,Am}，则： RП＝(A1×A1)∪(A2×A2)∪(A3×A3)∪...∪(Am×Am) 　　 ＝　　 。 定理3.3(续) 对任意x,y∈A，若x,y∈R，则x和y同属于П(A)的一个划分块Ai，因此y和x同属于П(A)的一个划分块Ai，故y,x∈R，所以R是对称的。 对任意x,y,z∈A，若x,y∈R，y,z∈R，则x和y同属于П(A)的一个划分块Ai，y和z同属于П(A)的一个划分块Aj，因此y∈Ai∩Aj，由于不同的划分块交为空，所以Ai=Aj，因此x和z同属于П(A)的一个划分块Ai，即x,z∈R，所以R是传递的。 综上，由1)、2)、3)知，R是A上的等价关系。 例3.5 解先求A的划分：只有1个划分块的划分为П1，具有2个 例 解：R1＝{1,2,3}×{1,2,3}∪{4,5}×{4,5}∪{6}×{6} ={1,1,2,2,3,3,1,2,2,1,1,3,3,1,2,3,3,2,4,4,5,5,4,5,5,4,6,6}； R2＝{1,2,3}×{1,2,3}∪{4,5,6}×{4,5,6} ＝{1,1,2,2,3,3,1,2,2,1,1,3, 3,1,2,3,3,2,4,4,5,5,6,6, 4,5,5,4,4,6,6,4,5,6,6,5}。 例3.6 设R是集合A上的一个传递关系和自反关系，S是A上的一个关系，使得对任意a,b∈A，a,b∈S当且仅当a,b∈R且b,a∈R，试证明S是A