离散数学第4章关系.ppt

1 第4章关系 2 第4章关系 4 1关系的定义及其表示4 2关系运算4 3关系的性质4 4等价关系与偏序关系 3 4 1关系的定义及其表示 4 1 1有序对与笛卡儿积4 1 2二元关系的定义4 1 3二元关系的表示 4 定义4 1由两个元素 如x和y 按照一定的顺序组成的二元组称为有序对 记作实例 点的直角坐标 3 4 有序对的性质有序性 当x y时 与相等的充分必要条件是 x u y v例1 求x y 解3y 4 2 x 5 y y 2 x 3 有序对 5 笛卡儿积 定义4 2设A B为集合 A与B的笛卡儿积记作A B A B x A y B 例2A 0 1 B a b c A B B A A B P A A P A B 6 例 设A a b B 1 2 3 试求A B和B A 验证 A B A B 和 B A B A 解 A B a 1 a 2 a 3 b 1 b 2 b 3 B A 1 a 1 b 2 a 2 b 3 a 3 b A B 6 2 3 A B B A 6 3 2 B A 7 笛卡儿积的性质 对于并或交运算满足分配律A B C A B A C B C A B A C A A B C A B A C B C A B A C A 幻灯片9 若A或B中有一个为空集 则A B就是空集 A B 不适合交换律A B B A A B A B 幻灯片6 不适合结合律 A B C A B C A B C 幻灯片8 若 A m B n 则 A B mn幻灯片6 8 解 A B C A B C 1 a 1 b 2 a 2 b x y 1 a x 1 b x 2 a x 2 b x 1 a y 1 b y 2 a y 2 b y A B C 1 2 a x a y b x b y 1 a x 1 a y 1 b x 1 b y 2 a x 2 a y 2 b x 2 b y 显然A B C A B C 例 设A 1 2 B a b A x y 求 A B C A B C 9 证明 仅证明 任取 a b a b A B C a A b B C a A b B b C a A b B a A b C a b A B a b A C a b A B A C 故A B C A B A C 可类似地证明 A B C A B A C 10 有序n元组和n阶笛卡尔积 定义4 3 1 由n个元素x1 x2 xn按照一定的顺序排列构成有序n元组 记作 2 设A1 A2 An为集合 称A1 A2 An xi Ai i 1 2 n 为n阶笛卡儿积 实例 1 1 0 为空间直角坐标 1 1 0 R R R 11 二元关系的定义 定义4 4如果一个集合满足以下条件之一 1 集合非空 且它的元素都是有序对 2 集合是空集则称该集合为一个二元关系 简称为关系 记作R 如 R 可记作xRy 如果 R 则记作xy实例 R S a b R是二元关系 当a b不是有序对时 S不是二元关系根据上面的记法 可以写1R2 aRb ac等 12 实例 例3 1 R x y N x y 2 C x y R x2 y2 1 其中R代表实数集合 C是直角坐标平面上点的横 纵坐标之间的关系 C中的所有的点恰好构成坐标平面上的单位圆 3 R x y z R x 2y z 3 R代表了空间直角坐标系中的一个平面 13 5元关系的实例 数据库实体模型 5元组 14 从A到B的关系与A上的关系 定义4 5设A B为集合 A B的任何子集所定义的二元关系叫做从A到B的二元关系 当A B时则叫做A上的二元关系 例4A 0 1 B 1 2 3 R1 R2 A B R3 R4 从A到B的关系 R1 R2 R3 R4 A上的关系R3和R4 计数 A n B m A B nm A B的子集有个 所以从A到B有个不同的二元关系 A n A上有不同的二元关系 例如 A 3 则A上有512个不同的二元关系 15 A上重要关系的实例 设A为任意集合 是A上的关系 称为空关系定义4 6EA IA分别称为全域关系与恒等关系 其中 EA x A y A A A IA x A 例如 A 1 2 则 EA IA 16 A上重要关系的实例 续 小于等于关系LA 整除关系DA 包含关系R 定义如下 定义4 7LA x y A x y 这里A R R为实数集合 DB x y B x整除y B Z Z 为非0整数集 R x y A x y 这里A是集合族 例如A 1 2 3 B a b 则 LA DA A P B a b a b 则A上的包含关系是 R 类似的还可以定义大于等于关系 小于关系 大于关系 真包含关系等等 17 关系的表示 表示方式 关系的集合表达式 关系矩阵 关系图定义4 8关系矩阵若A x1 x2 xm B y1 y2 yn R是从A到B的关系 R的关系矩阵是布尔矩阵MR rij m n 其中rij 1 R 定义4 9关系图若A x1 x2 xm R是从A上的关系 R的关系图是GR 其中A为结点集 R为边集 如果属于关系R 在图中就有一条从xi到xj的有向边 注意 设A B为有穷集关系矩阵适合于表示从A到B的关系或者A上的关系关系图适合于表示A上的关系 18 2 用关系矩阵表示二元关系如果A B是有限集 A a1 a2 am B b1 b2 bn R是A到B的二元关系 R的关系矩阵MR定义为 MR m n i 1 mj 1 n称为二元关系R的关系矩阵 19 例 设A a1 a2 a3 a4 B b1 b2 b3 R是A到B的二元关系 定义为 R a1 b1 a1 b3 a2 b2 a2 b3 a3 b1 a4 b1 a4 b2 写出R的关系矩阵 解 R的关系矩阵为 MR 20 例 设A 1 2 3 4 R是A的二元关系 定义为 R 1 1 1 2 2 1 3 2 3 1 4 3 4 2 4 1 写出A上二元关系R的关系矩阵 解 R的关系矩阵为 MR 21 3 用关系图表示二元关系如果A和B是有限集 R是A到B二元关系 还可以用图表示二元关系R 表示二元关系R的图叫做R的关系图 A到B二元关系的关系图和A上的二元关系的关系图的定义是不一样的 分别描述如下 22 A到B二元关系R的关系图设A a1 a2 am B b1 b2 bn R是A到B二元关系 R的关系图的绘制方法如下 画出m个小点表示A的元素 再画出n个小点表示B的元素 这些小点叫做关系图的顶点 下同 如果 ai bj R 则从ai到bj画一根有方向 带箭头 的线 这些有方向 带箭头 的线叫做关系图的边 下同 23 例 设A a1 a2 a3 a4 B b1 b2 b3 R是A到B的二元关系 定义为 R a1 b1 a1 b3 a2 b2 a2 b3 a3 b1 a4 b1 a4 b2 R的关系图如下 24 A上的二元关系R的关系图设A a1 a2 am R是A上的二元关系 其关系图如下绘制 画出m个小点表示A的元素 如果 ai aj R 则从ai到aj画一根有方向 带箭头 的线 25 例5A a b c d R R的关系矩阵MR和关系图GR如下 26 例 设A 1 2 3 4 R是A的二元关系 R 1 1 1 2 2 1 3 2 3 1 4 3 4 2 4 1 A上二元关系R的关系图如下 27 4 2 1关系的基本运算定义域 值域 域 逆 合成基本运算的性质4 2 2关系的幂运算幂运算的定义幂运算的方法幂运算的性质 4 2关系运算 28 关系的基本运算 定义4 10定义域 值域和域domR x y R ranR y x R fldR domR ranR 例1R 则domR ranR fldR a c a d b d a c a d b d d 29 关系的基本运算 续 定义4 11R的逆R 1 R 定义4 12R与S的合成R S y R S 例2R S R 1 R S S R 30 合成运算的图示方法 利用图示 不是关系图 方法求合成R S S R 31 基本运算的性质 定理4 1设F是任意的关系 则 1 F 1 1 F 2 domF 1 ranF ranF 1 domF证 1 任取 由逆的定义有 F 1 1 F 1 F所以有 F 1 1 F 2 任取x x domF 1 y F 1 y F x ranF所以有domF 1 ranF 同理可证ranF 1 domF 32 定理4 2设F G H是任意的关系 则 1 F G H F G H 2 F G 1 G 1 F 1证 1 任取 F G H t F G H t s F G H t s F G H s F t G H s F G H F G H 所以 F G H F G H 基本运算的性质 续 33 2 任取 F G 1 F G t F t x G t G 1 t y F 1 G 1 F 1所以 F G 1 G 1 F 1 基本运算的性质 续 34 定理4 3设R为A上的关系 则 R IA IA R R证明 任取 R IA t R IA t R t y y A R从而有 R IA R 同理可证IA R R 基本运算的性质 续 35 A上关系的幂运算定义 定义4 13设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 36 幂运算的方法 对于集合表示的关系R 计算Rn就是n个R合成 矩阵表示的关系就是矩阵相乘 其中相加采用逻辑加 例3设A a b c d R 求R的各次幂 分别用矩阵和关系图表示 解R与R2的关系矩阵分别为 37 同理R3和R4的矩阵是 因此M4 M2 即R4 R2 因此可以得到 R2 R4 R6 R3 R5 R7 而R0 IA的关系矩阵 幂运算的方法 续 38 用关系图的方法得到R0 R1 R2 R3 的关系图如下图所示 幂运算的方法 续 39 幂运算的性质 定理4 4设A为n元集 R是A上的关系 则存在自然数s和t 使得Rs Rt 证R为A上的关系 由于 A n A上的不同关系只有个 当列出R的各次幂R0 R1 R2 必存在自然数s和t使得Rs Rt 40 定理4 5设R是A上的关系 m n N 则 1 Rm Rn Rm n 2 Rm n Rmn证用归纳法 1 对于任意给定的m N 施归纳于n 若n 0 则有 Rm R0 Rm IA Rm Rm 0假设Rm Rn Rm n 则有 Rm Rn 1 Rm Rn R Rm Rn R Rm n 1 所以对一切m n N有Rm Rn Rm n 幂运算的性质 续 41 2 对于任意给定的m N 施归纳于n 若n 0 则有 Rm 0 IA R0 Rm 0假设 Rm n Rmn 则有 Rm n 1 Rm n Rm Rmn Rm Rmn m Rm n 1 所以对一切m n N有 Rm n Rmn 幂运算的性质 续 42 定理4 6设R是A上的关系 若存在自然数s t s t 使得Rs Rt 则 1 对任何k N有Rs k Rt k 2 对任何k i N有Rs kp i Rs i 其中p t s 3 令S R0 R1 Rt 1 则对于任意的q N有Rq S证明 1 Rs k Rs Rk Rt Rk Rt k 2 对k归纳 若k 0 则有 Rs 0p i Rs i假设Rs kp i Rs i 其中p t s 则 Rs k 1 p i Rs kp i p Rs kp i Rp Rs i Rp Rs p i Rs t s i Rt i Rs i由归纳法命题得证 幂运算的性质 续 43 3 任取q N 若q t 显然有Rq S 若q t 则存在自然数k和i使得q s kp i 其中0 i p 1 于是 Rq Rs kp i Rs i而 s i s p 1 s t s 1 t 1这就证明了Rq S 幂运算的性质 续