二元关系(syhang II).ppt

二元关系（Cont.） 关系的闭包 闭包的定义 闭包的构造方法 闭包的性质 闭包的相互关系 闭包的定义 定义 设R是非空集合A上的关系，R的自反（对称或传递）闭包是A上的关系R′，使得 R′满足以下条件： （1）R′是自反的（对称的或传递的） （2）R?R′ （3）对A上任何包含R的自反（对称或传递）关系R″有 R′? R″。 一般将R的自反闭包记作r(R)，对称闭包记作s(R)，传递闭包记作t(R)。 闭包的构造方法 定理 设R为A上的关系，则有 （1）r(R)＝R∪R0 （2）s(R)＝R∪R-1 （3）t(R)＝R∪R2∪R3∪… 设A={a,b,c,d}, R={a,b,b,a, b,c,c,d},则R和r(R),s(R),t(R)分别是什么？ r(R)=R∪R0={a,b,b,a,b,c,c,d, a,a,b,b,c,c,d,d} s(R)=R∪R-1={a,b,b,a,b,c,c,d, c,b,d,c} t(R)=R∪R2∪R3∪… R ={a,b,b,a,b,c,c,d} R2={a,a,a,c,b,b,b,d} R3={a,b,a,d,b,a,b,c} R4=R2; R5=R3。 ∴ t(R)=R∪R2∪R3 t(R)={a,b,b,a,b,c,c,d， a,a,a,c,b,b,b,d,a,d} 通过关系矩阵求闭包的方法 设关系R，r(R)，s(R)，t(R)的关系矩阵分别为M，Mr，Ms和Mt，则 Mr ＝ M＋E 对角线上的值都改为1 Ms ＝ M＋M′ 若aij＝1，则令aji＝1 Mt ＝ M＋M2＋M3＋… 沃舍尔算法 其中E是和M同阶的单位矩阵，M′是M的转置矩阵。 注意在上述等式中矩阵的元素相加时使用逻辑加。 等价关系与划分(Equivalence Partition) 定义 设R为非空集合上的关系。如果R满足 自反性、对称性和传递性， 则称R为A上的等价关系。 设R是一个等价关系，若x,y∈R，称x等价y，记做x～y。 举例 (1)平面上三角形集合中，三角形的全等、相似关系。 (2)正整数集合中的整除关系不是等价关系。 例 设A＝{1,2,…,8}，如下定义A上的关系R：R＝{x，y|x，y∈A∧x≡y(mod 3)}其中x≡y(mod 3)叫做x与y模3同余，即x除以3的余数与y除以3的余数相等。不难验证R为A上的等价关系，因为 ?x∈A，有x≡x(mod 3) ?x,y∈A，若x≡y(mod 3)，则有y≡x(mod 3) ?x,y,z∈A，若x≡y(mod 3)，y≡z(mod 3)，则有x≡z(mod 3) 等价类 定义 设R为非空集合A上的等价关系，?x∈A，令[x]R={y|y∈A∧xRy}称[x]R为x关于R的等价类，简称为x的等价类，简记为[x] 整数集合Z上的模n等价关系 设x是任意整数，n为给定的正整数，则存在唯一的整数q和r，使得x＝qn+r其中0≤r≤n-1，称r为x除以n的余数。 例如n＝3，那么－8除以3的余数为1，因为 -8＝-3×3+1 对于任意的整数x和y，定义模n的同余关系～为x～y ? x≡y(mod n) 不难验证它是整数集合Z上的等价关系。 将Z中的所有整数根据它们除以n的余数分类如下： 余数为0的数，其形式为kn，k∈Z余数为1的数，其形式为kn+1，k∈Z… 余数是n-1的数，其形式为kn+(n-1)，k∈Z 以上构成了n个等价类，使用等价类的符号可记为[i]＝{kn+i|k∈Z}，i=0，1，…，n-1 等价类的性质 定理 设R是非空集合A上的等价关系，则 （1）?x∈A，[x]是A的非空子集。 （2）?x,y∈A，如果xRy，则[x]＝[y]。 （3）?x,y∈A，如果x,y?R，则[x]与[y]不交。 （4）∪{[x]|x∈A}＝A。 证明 略 商集 定义 设R为非空集合A上的等价关系，以R的所有等价类作为元素构成的集合称为A关于R的商集记做A/R，即 A/R={[x]R|x∈A} 上例中的商集为 A/～={[0],[1],[2]}={{1,4,7},{2,5,8},{3,6}} 整数集合Z上模n同余等价关系的商集是  Z/～={[0],[1],…,[n-1]} Zn={0,1,…,n-1} 划分 定义设A为非空集合，若A的若干子集A1,A2,…满足下面的条件： （1）非空: Ai≠?; （2）两两不交: