离散数学-二元关系与运算.ppt

解：逐条性质加以验证R={x,y | (x?y)/3?I} 任取A中元素x，由于(x?x)/3=0，所以R是自反的； 又设A中任意两个元素x,y，如果 xRy，即x?y可被3整除，则y?x也一定可被3整除，即yRx，从而R是对称的； 如果A中三 个元素x，y，z满足xRy， yRz，则x ? y，y?z被3整除，由于x?z=(x?y)+(y?z)，所以x?z被3整除，从而xRz即R具有传递性。 §4.4 关系的闭包运算 闭包：设R?A?A， 自反闭包 记作 r(R) 对称闭包 记作 s(R) 传递闭包 记作 t(R) 由A求r(R)，s(R)，t(R)的过程叫闭包运算。 那么，包含R而使之具有自反性质的最小关系，称之为R的自反闭包； 包含R而使之具有对称性质(传递性质)的最小关系，称之为R的对称(传递)闭包。 一、定义 幂运算：设R?A?A，k?N，约定 (1) R0 = IA = {x, x | x?A} (2) R1 = R (3) Rk+1 = Rk ? R 显然 Rm ? Rn = Rm+n (Rm)n = Rmn 二、计算方法 为了有效地计算关系R的各种闭包，先引进关系的幂运算概念。 闭包运算的方法：设R是A上的任一关系，则 (1) r (R) = R∪IA (2) s (R) = R??∪R (3) t (R) = R∪R2∪R3∪… ∪Rn∪… 矩阵形式：(M为R的关系矩阵) (1) Mr = M + E (2) Ms = M + M (M 是M的转置) (3) Mt = M+M2+M3…… 其中“ +” 均表示“ 逻辑加” 例4.8 设A={a,b,c,d}，A上的关系 求 r (R)，s (R) 和 t (R) 解： r(R) = R∪IA ={a, b, b, c, c, d,d, c,, a, a, b, b, c, c, d, d} R={a, b,b,c,c, d,d, c, a, a} = R∪{a,a,b,b,c,c,d,d} 三、实例 s(R) = R∪R?? ={a,b,b,c,c,d,d,c,b,a,c,b,a,a} t(R) = R∪R2∪R3∪…… = R∪{b,a,c,b,d,c,c,d,a,a} 而R2 = R ? R R3 = R2 ? R R4 = R3 ? R = {a,c,b,dc,c,d,d,a,b,a,d,a,a} = {a,d,b,c,c,d,d,c,a,b,a,c,a,a} = {a, c, b, d,c, c, d, d,a, b, a, a} 实际上，看到当k ? 4时，已有R4 ? R∪R2∪R3 故 t(R) = R∪R2∪R3 ={a,b,b,cc,d,d,c,a,d,a,c, b,d,c,c,d,d,a,a} 四、闭包运算的性质 设A是有限集且|A| = n，R?A?A，则： ? §4.6 等价关系和偏序关系 等价关系：集A上的关系R是自反的, 对称的和传递的。 等价类： R是集A上的等价关系，对于任一a?A， [a]R={x | aRx, x?A} 被称为a的等价类。 即A中所有和a有R关系的元素的集合。 一、等价关系及用途 等价类的性质：R是非空集合，对任意的x，y?A，下面的结论成立： (1) [x]??且[x]?A (等价类为A的子集) (2) 若xRy，则[x] = [y] (3) 若x\Ry，则[x]∩[y] = ? 集A在等价关系R下的商集：设R为非空集A上的等价关系，以R的不交的等价类为元素的集合叫做A在R下的商集，记作A/R. 即： A/R = {[x]R | x?A} 集A的划分：设A是非空集合， (1) ? ?? (2) ? 中任意两个元素不交 (3) ? 中所有元素的并集为A 则? 为A的划分。 如果存在一个A的子集族?，? ?P(A)满足以下条件： 由等价类的性质和商集的定义可知，商集A/R是A的划分，称之为由R诱导的划分。 反过来，给定A的任一划分? ，则A被分割成若干个划分块。 若定义A上的二元关系R：?x，y?A且x,y属? 的同一块，则xRy，那么R是A上的等价关系，称之为由? 诱导的等价关系。 集A上的等价关系与划分是一一对应的。 * 1. 二元有序组：由两个元素x和y按一定顺序排成二元组，记作：x，y 。 §4.1 二元关系的概念 如： 平面直角坐标系中点的坐标 一、二元关系的概念 二元有序组的性质 (1) 当x ? y时，x，y ? y，x (2) x，y = u，v，当且仅当x = u，y = v (1)、(2)说明有序组区别于集合 n元有序组：由n个元素x1，x2，…，xn，按一