[数学]04-关系-42.ppt

第四章 关 系 第二节 关系运算 一、复合运算 假设R1是从A到B的关系 复合运算 定义： 设R是从A到B的关系，S是从B到C的关系，经过对R和S实行复合运算“°”，得到一个新的从A到C的关系R°S，称R°S为关系R和S的复合关系（合成关系），也称R°S为关系R和S的复合运算（合成运算）。即 R°S={a,c|(?b)(b?B∧aRb∧bSc)} 复合运算 例4.2.1 设B是关系“…是…的兄弟”，F是关系“…是…的父亲” 则： B°F表示关系： F°B表示关系： F°F表示关系： B°B表示关系： 复合运算 例4.2.2 给定集合A={1,2,3,4}，B={2,3,4}，C={1,2,3}设R是A到B 的关系，S是B到C的关系：R={x,y|x+y=6}={2,4,3,3,4,2}S={y,z|y-z=1}={2,1,3,2,4,3} 复合运算 例4.2.3 给定集合A={1,2,3,4,5}，R和S都是A上的二元关系：R={1,2,3,4,2,2}S={4,2,2,5,3,1,1,3} 则： R°S = S°R = (R°S)°R = R°(S°R) = R°R = 复合运算 定理：设R是A上的二元关系，则 R°IA = IA°R = R 证明：对于任意a,b ? R°IA ? (?c)(c?A ∧ a,c?R ∧c,b ?IA) ? (?c)(c?A ∧ a,c?R ∧c=b) ? a,b?R 对于任意a,b ? IA°R ? (?c)(c?A ∧ a,c? IA ∧c,b ?R) ? (?c)(c?A ∧ a=c ∧ c,b ?R) ? a,b?R 复合运算 扩展： 设R是从A到B的二元关系，  IA是A上的恒等关系， IB是B上的恒等关系  则：R°IB = IA°R =R 若 R(R) ? D(S)=?，则 R°S=?。 复合运算 定理：R ? A×B，S ? B×C，T ? B×C，W ? C×D，则 R ° (S ? T) = R ° S ? R ° T R ° (S ? T) ? R ° S ? R ° T (S ? T) ° W = S ° W ? T ° W (S ? T) ° W ? S ° W ? T ° W 证明略（教材P70） 复合运算 结合律：R ? A×B，S ? B×C，T ? C×D，则 (R ° S ) ° T= R ° (S ° T) 证明：对于任意a,d ? (R ° S ) ° T ? (?c)(c?C ∧a R ° S c∧cTd) ? (?c)(c?C∧(?b)(b?B∧aRb∧bSc)∧cTd) ? (?c)(?b)(c?C∧b?B∧aRb∧bSc∧cTd) ? (?b)( b?B∧aRb∧ (?c)(c?C∧ bSc∧cTd) ) ? (?b)( b?B∧aRb∧ b S ° T d ) ? a,d ? R ° (S ° T) 复合运算的矩阵表达 定理：A={a1, a2, …, am}，B={b1, b2, …, bn}，C={c1, c2, …, cp} ， R ? A×B，S ? B×C，T =R ° S 已知MR=[rij](m×n矩阵)和MS=[sij](n×p矩阵)，则： MT=[tij]是m×p矩阵，且 tij = ∨(rik∧skj) (i=1…m, j=1…p, k=1…n) 复合运算的矩阵表达 例4.2.4 已知：A={1, 2}, B={a, b, c}, C={α, β} R ? A×B，S ? B×C，T =R ° S 并且： 求MT 幂运算 二、幂运算 定义： 设R是A上的二元关系，n ? N， R的n次幂定义为Rn R0=IA Rn+1=Rn ° R 幂运算 定理：若R是A上的二元关系，m, n ? N，则 Rm ° Rn= Rm+n (Rm )n = Rmn 证明略（可使用归纳法证明） 幂运算 定理：若R是A上的二元关系，|A|= n，则存在i和j，且ij，使得Ri = Rj ，其中0 ≤ i j ≤ 2n。 幂运算 定理：若R是A上的二元关系，若存在i和j，且ij， 使得Ri = Rj 且d=j-i，则 对于任意k ≥ 0，有Ri+k=Rj+k 对于任意k ≥ 0，m ≥ 0，有Ri+md+k=Ri+k 设S={R0, R1,…, Rj-1}，对于任意n ? N，有Rn ? S 证明：1)和2)可以用归纳法证明（略） 3)