离散数学(第11讲)二元关系.ppt

1 设R S都是集合A到B的两个关系 则 R S xRy xSy R S xRy xSy R A B R R S xRy xSy 4 2关系的运算 一 关系的交 并 补 差运算 补充 根据定义 由于A B是相对于R的全集 所以R A B R 且R R A B R R 2 设A a b c B 1 2 R S 则 R S R S R S 例 A B R 3 结论如果R是A上的关系 则有 1 R是自反的充要要条件是IA R 2 R是反自反的充要条件是R IA 例设R S是A上的自反关系 试证明R 1 R S R S 也是A上的自反关系 4 定义设R是一个从集合A到集合B的二元关系 则R的逆关系R 1是从B到A的关系 R 1 R 运算 1 称为逆运算 二 关系的逆运算 逆关系 注意 关系是一种集合 逆关系也是一种集合 因此 如果R是一个关系 则R 1和都是关系 但R 1和是完全不同的两种关系 千万不要混淆 5 设A a b c d B 1 2 3 R是从A到B的一个关系 R 则 R 1 A B R 例 6 R R 1 关系矩阵如下 例 续 如用关系图表示逆关系 则仅将关系图中的有向边的方向改变成相反方向 如用关系矩阵表示逆关系 则MR 1 MRT 7 设R S是从集合A到集合B的二元关系 则有 双重否定律 定理 补充 R 1 1 R 1 可换性 R S 1 R 1 S 1 分配性 R S 1 R 1 S 1 R S 1 R 1 S 1 1 A B 1 B A S R S 1 R 1 单调性 8 证明 3 1 1 R S 1 R 1 S 1 R R 1 证明 4 R S 1 R S R S R 1 S 1 R 1 S 1 9 6 若 3 5 成立 则有 R S 1 R S 1 R 1 S 1 R 1 S 1 R 1 S 1 证明 5 R S 1 则 R S R S R 1 S 1 R 1 S 1 R S 1 R 1 S 1 10 设R是A上的二元关系 那么R是对称的当且仅当R R 1 证明 充分性 a b A 如 R 则 R 1 由于R 1 R 故 R R是对称的 必要性 R 1 则 R 又因为R是对称的 故 R R 1 R R 因R是对称的 R R 1 R R 1 从而有R R 1 40 11 结论R是A上反对称关系的充要条件是R R 1 A 设R和S是A上的反对称关系 则R 1 R S 也是A的反对称关系 R S均是反对称的 未必能得出R S也是反对称的 12 三 关系的合成运算 设R是一个从集合A到集合B的二元关系 S是从集合B到集合C的二元关系 也可简单地描述为R A B S B C 则R与S的合成关系 合成关系 R S是从A到C的关系 并且 R S x A z C y y B xRy ySz 运算 称为合成运算 13 注意 在合成关系中 R的后域B一定是S的前域B 否则R和S是不可合成的 合成的结果R S的前域就是R的前域A 后域就是S的后域C 如果对任意的x A和z C 不存在y B 使得xRy和ySz同时成立 则R S为空 否则为非空 并且 R R 例 1 某人a与c有外祖父的关系 则一定存在一个b 使得a与b有父女关系而b与c有母子关系 2 某人a与b有 兄妹 关系 b和c有 母子 关系 则a与c有 舅甥 关系 14 例 设A B C 1 2 3 4 定义R为A B的关系R S为B C的关系S 1 用集合方法求R S S R R R S S 则 R S S R R R S S 15 R S R SABCAC1 1 11 12 2 22 23 3 33 34 4 44 4 2 用关系图求R S 例R S 3 用关系矩阵求R S MR S MRMS 16 定理1 设R是从集合A到集合B的关系 S1 S2是从集合B到集合C的关系 T是从集合C到集合D的关系 则 R S1 S2 R S1 R S2 左分配 S1 S2 T S1 T S2 T 右分配 R S1 S2 R S1 R S2 S1 S2 T S1 T S2 T 17 证明 1 R S1 S2 y B 使得 R S1 S2 y R S1 S2 y R S1 y R S2 R S1 R S2 R S1 R S2从而有 R S1 R S2 R S1 S2 18 证明对任意 R S1 S2 则由合成运算知 至少存在c B 使得 R S1 S2 即 S1 且 S2 因此 由 R 且 S1 则有 R S1 由 R 且 S2 则有 R S2 所以 R S1 R S2 即 R S1 S2 R S1 R S2 3 R S1 S2 R S1 R S2 19 定理2设R S T分别是从集合A到集合B 集合B到集合C 集合C到集合D的二元关系 则1 R S T R S T 结合律 2 R S 1 S 1 R 1 补充 证明1 设 R S T c C 使得 R S T 则由合成运算知 至少存在 R S T 又对于 R S 则至少存一个b B 使得 R S 因此 由 S T 有 S T 又由 R和 S T 知 所以 R S T R S T 同理可证 R S T R S T 由集合性质知 R S T R S T 20 2 任取 R S 1 则 R S由 的定义知 则至少存一个b B 使得 R S 即 R 1 S 1 由 S 1和 R 1 有 S 1 R 1 所以 R S 1 S 1 R 1 反之 任取 S 1 R 1 由 的定义知 则至少存一个b B 使得 S 1和 R 1 所以 R S 由 知 R S 即有 R S 1 所以 S 1 R 1 R S 1 由集合的定义知 R S 1 S 1 R 1 定理 续 2 R S 1 S 1 R 1 21 结论R是传递关系的充要条件是R R R 设R S是A上的传递关系 则R 1 R S也是A上的传递关系 R S是传递的 但R S未必是传递的 22 定义设R是集合A上的二元关系 则可定义R的n次幂Rn 该Rn也是A上的二元关系 定义如下 1 R0 IA a A 2 R1 3 R2 R R3 Rn 1 Rn R R Rn 四 关系的幂 显然 Rm n Rm Rn Rm n Rmn 23 例 设A a b c d e f 定义在A上的关系R 求Rn 解R0 IA R1 R R2 R R R3 R R R R2 R R4 R3 R R5 R4 R R6 R5 R R5 R7 R6 R R5 Rn R5 n 5 24 例 续 S1 S S2 S S S3 S S S S2 S S4 S3 S S5 S4 S S6 S5 S S7 Sn n 5 设A a b c d e f 定义在A上的关系S 求Sn 25 定理3 2 4令R A A 且 A n 则存在i和j 使得Ri R