离散数学关系的运算.ppt

1 基本运算定义定义域 值域 域逆 合成 限制 像基本运算的性质幂运算定义求法性质 4 2关系的运算 2 一 关系的基本运算定义 1 定义域 值域和域 定义设R是二元关系 由 x y R的所有x组成的集合称为R的前域 记为domR 即domR x y R 使 x y R的所有y组成的集合称为R的值域 记为ranR 即ranR y x R 称domR ranR为R的域 记为fldR 即fldR domR ranR 解 根据题意R1 1 2 1 3 1 4 2 3 2 4 3 4 故前域domR1 1 2 3 值域ranR1 2 3 4 fldR 1 2 3 4 例1设A 1 2 3 4 R1是A上的二元关系 当a b A 且a b时 a b R1 求R和它的前域 值域和域 3 2 逆与合成R 1 R R S y R S 例2已知R S 求R 1 R S S R 解 R 1 R S S R 4 合成运算的图示方法 利用图示 不是关系图 方法求合成R S S R 例2已知R S 求R 1 R S S R 5 3 限制与像 定义F在A上的限制F A xFy x A A在F下的像F A ran F A 例3设R 则R 1 R 1 2 4 R R 1 2 2 3 4 注意 F A F F A ranF 6 二 关系基本运算的性质 定理1设F是任意的关系 则 1 F 1 1 F 2 domF 1 ranF ranF 1 domF 定理2设F G H是任意的关系 则 1 F G H F G H 2 F G 1 G 1 F 1 7 定理设R S T均为A上二元关系 那么 1 R S T R S R T 2 S T R S R T R 3 R S T R S R T 4 S T R S R T R 5 R S T R S T 8 三 A上关系的幂运算 设R为A上的关系 n为自然数 则R的n次幂定义为 1 R0 x A IA 2 Rn 1 Rn R注意 对于A上的任何关系R1和R2都有R10 R20 IA对于A上的任何关系R都有R1 R 9 例 10 定理设R是A上的关系 m n N 则 1 Rm Rn Rm n 2 Rm n Rmn 四 幂运算的性质 11 关系运算的矩阵表示关系矩阵 matrixofrelation 设RA B A a1 a2 am B b1 b2 bn 那么R的关系矩阵MR为一m n矩阵 它的第i j分量rij 只取值0或1 而 当且仅当aiRbj 当且仅当 12 某关系R的关系图为 则R的关系矩阵为 13 思考 写出集合A 1 2 3 4 上的恒等关系 空关系 全域关系和小于关系的关系矩阵 答案 分别为 14 在讨论关系矩阵运算前 我们先定义布尔运算 它只涉及数字0和1 布尔加法 0 0 00 1 1 0 1 1 1布尔乘法 1 1 10 1 1 0 0 0 0 15 R0 R1 R2 R3 的关系图如下图所示 五 幂的求法 例3设A a b c d R 求R的各次幂 分别用矩阵和关系图表示 解R与R2的关系矩阵分别为 16 幂的求法 续 对于集合表示的关系R 计算Rn就是n个R右复合 矩阵表示就是n个矩阵相乘 其中相加采用逻辑加 例3设A a b c d R 求R的各次幂 分别用矩阵和关系图表示 解R与R2的关系矩阵分别为 17 同理 R0 IA R3和R4的矩阵分别是 因此M4 M2 即R4 R2 因此可以得到 R2 R4 R6 R3 R5 R7 幂的求法 续 18 六 幂运算的性质 定理设A为n元集 R是A上的关系 则存在自然数s和t 使得Rs Rt 证R为A上的关系 由于 A n A上的不同关系只有个 当列出R的各次幂R0 R1 R2 必存在自然数s和t使得Rs Rt 19 定理设R A A 若存在自然数s t s t 使得Rs Rt 则下面等式成立 1 Rs q Rt q q N 证明Rs q RsRq RtRq Rt q 2 Rs t s q r Rs r 其中q r N 证明对q用归纳法证明 当q 1 Rs t s q r Rs t s r Rt r Rs r 1 设q k时 命题成立 即Rs t s k r Rs r 其中q r N 当q k 1时 Rs t s k 1 r Rs t s k r t s Rs t s k rR t s Rs rRt s 归纳假设 Rs r t s Rt r Rs r 1 所以 2 成立 20 2 Rs t s q r Rs r 其中q r N 3 令S R0 R1 Rt 1 则对于任意n N 均有Rn S ss 因而存在q r N 使得n s t s q r 0 r t s 1 即n s t s q rRn Rs t s q r Rs r 2 而s r s t s 1 t 1 所以Rn Rs r S 21 Rs t s q r Rs r 例设R A A 化简R2003的指数 1 已知R3 R5 2 已知R7 R15 解 1 s 3 t 5 n 2003 1000 1000 1 0 因此 q 1000 r 0 R2003 R3 2 1000