离散数学-3-7 复合关系和逆关系.ppt

1 第三章集合与关系 3 7复合关系和逆关系授课人 李朔Email chn nj ls 2 一 关系的复合 二元关系是以序偶为元素的集合 可以进行集合运算 产生新的集合 本课介绍关系的一种新的运算 关系的复合 定义3 7 1设R为X到Y的关系 S为从Y到Z的关系 则R S称为R和S的复合关系 表示为R S x X z Z y y Y R S 易见R S是从X到Z的关系 从R和S 求R S称为关系的合成运算 合成运算由两个关系生成一个新的关系 P114例如 R1是关系 是 兄弟 R2是关系 是 父亲 那么R1 R2是关系 是 的叔伯 若R1是关系 是 的父亲 那么R1 R2是关系 是 的祖父 3 一 关系的复合 例题1 R S 则R S S R R S R R S R S S R R R R R 可以证明 关系的复合运算满足结合律 即 R S T R S T 故可记为 R S TP115例题2 当R与自己复合时 记R R R2 一般定义Rn 1 Rn R 4 一 关系的复合 例 设X 0 1 2 3 则R R2 R R R3 R2 R 关系可用矩阵表示 故复合关系亦可用矩阵表示 类似矩阵乘法 但采用逻辑加 P115 5 例 例题3A 1 2 3 4 5 A上的二元关系R和S定义如下 R 1 2 2 2 3 4 S 1 3 2 5 3 1 4 2 试求MR S和MR MS 它们是否相等 解 按照R和S的定义 求出R S 1 5 2 5 3 2 写出R S和R S关系矩阵如下 MR MS MR S 6 例 MR MS 所以MR S MR MS 7 二 关系的逆 关系是序偶的集合 由于序偶的有序性 关系还有一些特殊的运算 P117定义3 7 2设R为X到y的二元关系 如将R中每一序偶的元素顺序互换 所得的集称为R的逆关系 记为Rc 即 Rc R 例如 R 则Rc 易见 Rc c R又如集合Z上 关系 8 二 关系的逆 P117定理3 7 1设R S T都是从A到B的二元关系 则1 S T C SC TC2 S T C SC TC3 A B C B A4 R C RC R A B R RC B A RC 5 S T C SC TC 9 二 关系的逆 证 1 S T C S T S T SC Tc SC TC4 R C R R RC R C5 因S T S T 故 S T C S T C SC T C SC TC SC TC 10 二 关系的逆 P117定理3 7 2设T为从X到Y的关系 S为从Y到Z的关系 则 T S C SC TC证 T S C T S y y Y T S y y Y TC SC SC TC 11 二 关系的逆 定理3 7 3设R为X上的二元关系 则 1 R是对称的 当且仅当R RC 2 R是反对称的 当且仅当R RC IX 证 1 R对称 故 R R RC 故R RC反之RC R 则 R RC R 即R对称 12 二 关系的逆 定理3 7 3设R为X上的二元关系 则 1 R是对称的 当且仅当R RC 2 R是反对称的 当且仅当R RC IX 证 2 设R反对称 R RC则 R且 RC故有 R x y即 IX R RC IX 反之设R RC IX R且 R则 RC R RC即有 IX x y R是反对称的 13 二 关系的逆 关于RC的图形 是R的图形中将其弧线的箭头反置即得 而RC的关系矩阵是R的关系矩阵的转置 例 X a b c 其上二元关系R关系阵为则RC的关系阵为 14 例 例设X 1 2 3 4 Y a b c X到Y二元关系R 1 a 2 b 4 c 试求RC 写出MR和 验证 MRT 画出R和RC的关系图 验证将R关系图中的弧线的箭头反置可得到RC关系图 解 RC a 1 b 2 c 4 R和RC的关系矩阵是 MR 显然 MRT 15 例 R和RC的关系图分别是图1和图2 它们中