离散数学 集合的笛卡儿积与二元关系PPT课件.ppt

1 第4章二元关系与函数 4 1集合的笛卡儿积与二元关系4 2关系的运算4 3关系的性质4 4关系的闭包4 5等价关系和偏序关系4 6函数的定义和性质4 7函数的复合和反函数 2 4 1集合的笛卡儿积和二元关系 有序对笛卡儿积及其性质二元关系的定义二元关系的表示 3 有序对 定义由两个元素x和y 按照一定的顺序组成的二元组称为有序对 记作实例 平面直角坐标系中点的坐标有序对性质1 有序性 当x y时 2 与相等的充分必要条件是 x u y v 例1 求x y 解3y 4 2 x 5 y y 2 x 3 4 有序n元组 定义一个有序n n 3 元组是一个有序对 其中第一个元素是一个有序n 1元组 即 xn 实例 空间直角坐标系中的坐标n维向量是有序n元组 当n 1时 形式上可以看成有序1元组 5 笛卡儿积 定义设A B为集合 用A中元素为第一个元素 B中元素为第二个元素 构成有序对 所有这样的有序对组成的集合叫做A与B的笛卡儿积记作A B 即A B x A y B 例2A 1 2 3 B a b c A B B A A P A A 6 笛卡儿积的性质 不适合交换律A B B A A B A B 不适合结合律 A B C A B C A B 对于并或交运算满足分配律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 若A或B中有一个为空集 则A B就是空集 A B 若 A m B n 则 A B mn 7 性质的证明 证明A B C A B A C 证任取 A B C x A y B C x A y B y C x A y B x A y C A B A C A B A C 所以有A B C A B A C 8 例题 解 1 任取 A C x A y C x B y D B D 例3 1 证明A B C D A C B D 2 A C B D是否推出A B C D 为什么 2 不一定 反例如下 A 1 B 2 C D 则A C B D但是A B 9 例4 1 证明A B C D A C B D 2 A C B D是否推出A B C D 解 1 任取 A C x A y C x B y D B D 2 不一定 反例如下 A 1 B 2 C D 10 例5设A B C D为任意集合 判断以下等式是否成立 说明为什么 A B C D A C B D A B C D A C B D A B C D A C B D A B C D A C B D 解 1 成立 因为对任意的 A B C D x A B y C Dx A x B y C y D A C B D 11 2 A B C D A C B D 解 不成立 若A D B C 1 则有 A B C D B C 3 A B C D A C B D 解 不成立 A B 1 C 2 D 3 A B C D A C B D 4 A B C D A C B D 解 A 1 B C D 1 A B C D 1 1 A C B D 12 设A1 A2 An是集合 n 2 它们的n阶笛卡尔积记作A1 A2 An 其中A1 A2 An x1 A1 x2 A2 xn An 当A1 A2 An时 可将它们的n阶笛卡尔积记作An例如 A a b 则A3 13 二元关系 集合中两个元素之间的某种关系例1甲 乙 丙3个人进行乒乓球比赛 任何两个人之间都要比赛一场 假设比赛结果是乙胜甲 甲胜丙 乙胜丙 比赛结果可表示为 其中表示x胜y 它表示了集合 甲 乙 丙 中元素之间的一种胜负关系 例2有A B C3个人和四项工作G1 G2 G3 G4 已知A可以从事工作G1和G4 B可以从事工作G3 C可以从事工作G1和G2 那么 人和工作之间的对应关系可以记作R C G2 它表示了集合 A B C 到工作 G1 G2 G3 G4 之间的关系 14 二元关系的定义 定义如果一个集合满足以下条件之一 1 集合非空 且它的元素都是有序对 2 集合是空集则称该集合为一个二元关系 简称为关系 记作R 如 R 可记作xRy 如果 R 则记作xy实例 R S a b R是二元关系 当a b不是有序对时 S不是二元关系根据上面的记法 可以写1R2 aRb ac等 15 从A到B的关系与A上的关系 定义设A B为集合 A B的任何子集所定义的二元关系叫做从A到B的二元关系 当A B时则叫做A上的二元关系 例4A 0 1 B 1 2 3 R1 R2 A B R3 R4 那么R1 R2 R3 R4是从A到B的二元关系 R3和R4同时也是A上的二元关系 计数 A n A A n2 A A的子集有个 所以A上有个不同的二元关系 例如 A 3 则A上有 512个不同的二元关系 16 A上重要关系的实例 设A为任意集合 是A上的关系 称为空关系EA IA分别称为全域关系与恒等关系 定义如下 EA x A y A A A IA x A 例如 A 1 2 则 EA IA 17 A上重要关系的实例 续 小于等于关系LA 整除关系DA 包含关系R 定义 LA 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是集合族 类似的还可以定义大于等于关系 小于关系 大于关系 真包含关系等等 18 实例 例如A 1 2 3 B a b 则 LA DA A P B a b a b 则A上的包含关系是R 19 关系的表示 表示方式 关系的集合表达式 关系矩阵 关系图关系矩阵 若A x1 x2 xm B y1 y2 yn R是从A到B的关系 R的关系矩阵是布尔矩阵MR rij m n 其中rij 1 R 关系图 若A x1 x2 xm R是从A上的关系 R的关系图是GR 其中A为结点集 R为边集 如果属于关系R 在图中就有一条从xi到xj的有向边 注意 A B为有穷集 关系矩阵适于表示从A到B的关系或者A上的关系 关系图适于表示A上的关系 20 实例 A 1 2 3 4 R R的关系矩阵MR和关系图GR如下 21 基本运算定义定义域 值域 域逆 合成 限制 像基本运算的性质幂运算定义求法性质 4 2关系的运算 22 关系的基本运算定义 定义域 值域和域domR x y R ranR y x R fldR domR ranR例1R 则 domR 1 2 4 ranR 2 3 4 fldR 1 2 3 4 23 关系的基本运算定义 续 定义设F G为任意的关系 A为集合 则逆与合成F 1 F F G z G F 例2R S R 1 S R R S 24 合成运算的图示方法 利用图示 不是关系图 方法求合成R S S R R S S R 25 限制与像 定义F在A上的限制F A xFy x A A在F下的像F A ran F A 实例R R 1 R 1 2 4 R R 1 2 2 3 4 注意 F A F F A ranF 26 例 设F G是N上的关系 其定义为F x y N y x2 G x y N y x 1 求G 1 F G G F F 1 2 F 1 2 解 G 1 y x N y x 1 G 1 对任何x N有y z2 x 1 2 所以F G x y N y x 1 2 G F x y N y x2 1 F 1 2 F 1 2 ran F 1 2 1 4 27 例 设F 求F F F a F a 解 F F F a A a F A ran F A ran a 28 关系基本运算的性质 定理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 29 3 F G H F G H 4 F G 1 G 1 F 1证 3 任取 F G H t H F G t H s G F t s H G F s F t H G s F G H F G H 所以 F G H F G H 关系基本运算的性质 续 30 4 任取 F G 1 F G t G t x F t F 1 t y G 1 G 1 F 1所以 F G 1 G 1 F 1 关系基本运算的性质 续 31 关系基本运算的性质 续 定理4 2设F G H为任意的二元关系 则有 F G H F G F H G H F G F H F 合成运算对 运算满足分配律 3 F G H F G F H4 G H F G F H F 合成运算对 运算分配后是包含关系 32 A上关系的幂运算 设R为A上的关系 n为自然数 则R的n次幂定义为 1 R0 x A IA 2 Rn Rn 1 R n 1注意 对于A上的任何关系R1和R2都有R10 R20 IA对于A上的任何关系R都有R1 R 33 幂的求法 1 对于集合表示的关系R 计算Rn就是n个R左复合 2 矩阵表示就是n个矩阵相乘 其中相加采用逻辑加 例3设A a b c d R 求R的各次幂 分别用矩阵和关系图表示 解R与R2的关系矩阵分别为 34 同理 R0 IA R3和R4的矩阵分别是 因此M4 M2 即R4 R2 因此可以得到 R2 R4 R6 R3 R5 R7 对于有穷集A A上关系R的不同幂只有有限个 幂的求法 续 35 R0 R1 R2 R3 的关系图如下图所示 幂的求法 续 36 幂运算的性质 定理3设A为n元集 R是A上的关系 则存在自然数s和t 使得Rs Rt 证R为A上的关系 由于 A n A上的不同关系只有个 当列出R的各次幂R0 R1 R2 必存在自然数s和t使得Rs Rt 37 定理4设R是A上的关系 m n N 则 1 Rm Rn Rm n 2 Rm n Rmn证用归纳法 1 对于任意给定的m N 施归纳于n 若n 0 则有 Rm R0 Rm