二元关系PPT课件.ppt

1 第二章二元关系 1二元关系及其表示形式 2二元关系的基本类型与判定方法 3等价关系 相容关系和偏序关系 4复合关系 逆关系和关系的闭包运算 2 2 1二元关系及其表示形式 本节要求掌握的知识点 1 序言 何谓关系 多样性 2 笛卡尔乘积 概念 求法 3 二元关系的定义4 二元关系的3 1 种表示方法 3 相关 按照某种规则 确定二个对象或多个对象之间有关系 称这二个对象或多个对象是相关的 注意 相关性与指定的规则有关 1 扑克牌中的方块 与梅花 同花关系 不相关 同点关系 相关 2 父子二人同辈关系 不相关 父子关系 相关 2 1 1 序言 关系 相关 4 注 二元关系 二个对象之间的关系多元关系 多个对象之间的关系多元关系常化成二元关系来研究无序的二元关系 方块 与梅花 谁在前 谁在后都还是同点的 有序的二元关系 父子关系 不能交换父与子的次序 又如 1 偶数 与 是无序的用 表示无序对 2 与 是有序的二元关系 叫作 相关于 记成 用 表示有序对 3 无序的二元关系可用有序的二元关系表示即 与 都属于这种二元关系 5 2 1 2 集合的笛卡儿乘积 有序对 设有二个集合 与 中任取元素 中任取元素 与 建立一种对应关系 记为 总是把 中元素写在前面 中元素写在后面 称 为有序对 6 有序对的集合 b 称为 对 的直交积 记为 又称叉积 笛卡儿 Descartes 乘积 注 不满足交换律 也不存在结合律 笛卡儿积满足分配律 对 7 的证明 对 且 即得 其次 对 而 而 即得 因此 8 的几何意义 设 均为实闭区间则有序对 是平面上一个点 1 表示矩形区域 2 应为矩形区域 注 1 当且仅当 时 是正方形区域 2 由于 也是集合 它应满足集合的一切性质 9 按照某种规定 定义了一个有序对 的集合 其中 称 为 到 的一个二元关系 显然R A B 即 A B的任意一个子集合都是A到B的一个二元关系 注意 二元关系是指满足某规律的有序对的全体 例 R 其中 R 读作 相关于 二元关系的定义 10 二元关系的前域和值域 若R是A到B的二元关系前域 domR x x y R 值域 ranR y x y R 空关系和全域关系 其他一般的二元关系 空关系 全域关系 A B当 时 是 到 的二元关系 称为 上的二元关系 A到A的二元关系 例 是自然数集 上的二元关系 称为 整除关系 11 2 1 3二元关系的几种表示方法 二元关系的表示 因为 二元关系本身也是集合 也可用穷举法 描述法来表示 还可用表格 图示 矩阵法表示 例如 张三 李四 王五 赵六 米 跳高 铅球 足球 跨栏 穷举法表示 张三 铅球 张三 足球 李四 米 李四 跳高 王五 跨栏 赵六 米 是运动会的报名表 12 二元关系的表示 1 集合法 穷举法 描述法 张三 铅球 张三 足球 李四 米 李四 跳高 王五 跨栏 赵六 米 是运动会的报名表 13 2 表格法 用表格表示一目了然 14 3 图示法 用字母数字来代替这些元素 a b c d 1 2 3 4 5 关系图 直观 a 3 a 4 b b 2 c 5 d 1 15 4 矩阵法 把 集合内元素排好序 16 若 称 为恒等关系 常用IA表示 说明 对于一个给定的有限集合 其上的恒等关系IA是唯一确定的 而且 恒等关系一定是A上的 例 A 1 2 3 4 上的恒等关系为 IA 1 1 2 2 3 3 4 4 17 讨论与思考 1 什么叫二元关系 它与子集合 幂集合 笛卡儿乘积的关系 例 A 4 B 5 问 A B有几个元素 即 有几个有序数对 A到B可以定义多少种互不相同的二元关系 2 二元关系各种表示方法的优缺点及其适应场合 18 作业 p24 7 12 13 14 19 2 2二元关系的基本类型与判定 本节要求掌握的知识点 1 二元关系的5种基本类型 概念 特点2 可传递关系的判别方法 20 设 是 上的二元关系 1 若对任意a A a a 则称 为A上的自反关系 自反的二元关系的关系矩阵对角元均为 即 ii 2 若对任意a A a a 则称 为A上的反自反关系 的关系矩阵对角元素均为 即 ii i 1 2 3 n 2 2 1二元关系的基本类型 21 自反关系任意 a a R 反自反关系任意 a a R 既不是自反的 也不是反自反的二元关系 注意 不是自反的不一定是反自反的 不是反自反的也不一定是自反的 自反性与反自及性是互斥的 但不互补 如下图 22 对称关系与反对称关系若 则有 则称这样的二元关系 为对称关系 此时 的相关矩阵是对称矩阵 即 ij ji 若 a b 则有 则称这样的二元关系 为反对称关系 此时 的关系矩阵满足 ij ji 0 23 对称关系若 a b R则 b a R a b 反对称关系若 a b R则 b a R a b 既不是对称的 也不是反对称的二元关系 注意 对称与反对称 既不互斥 又不互补 即 不是对称的 不一定是反对称的 反之依然 如下图 24 5 传递关系设R是A上的二元关系 若满足当 a b R且 b c 时 有 a c 则称这样的 为A上传递关系 例 若A 1 2 3 4 下面哪个是A上的传递关系 R1 1 2 R2 1 2 2 3 1 3 R3 1 1 2 2 R4 1 2 2 3 3 4 3 1 R5 A A 25 二元关系的性质 对应于关系图 有 1 自反关系 每个顶点都有自回路 2 反自反关系 每个顶点都没有自回路 3 对称关系 任意两个顶点间或没有边 或有两条相向边 4 反对称关系 任二顶点至多只有一条有向边 5 传递关系 若 到 有边 到 有边 则 到 必有边 思考 那么 它们的关系矩阵又有什么特点 26 例 1 是自反的 rii 1 不是对称的 1 2 R1 而 2 1 R1是反对称的 是传递的 注 将 改为 则无自反性 且是反自反的 例 2 整除 是自反的 不是对称的 是反对称的 是可传递的 例 3 1 2 1 2 1 2 其中 是 的幂集 3是自反的 不是对称的 是反对称的 是传递的 注 若 改为 则无自反性 27 例 4 a b a b 偶数 a 4是自反的 对称的 传递的 因 偶 偶 则 偶数 所以 4是传递的 例 5 a b互素 b 5是对称的 但不是自反的 也无传递性 28 2 2 2可传递关系的判定方法 1 定义法 验证 若 a b R且 b c 是否都有 a c 有一个例外就不是 2 矩阵法 方法1 若AR aij B A2 bij 则R可传递当且仅当bij 1时必有aij 1 其中方法2 对于关系矩阵AR中的每一个aij 1作如下操作 将AR中的第j行元素对应加 布尔加 到第i行元素上 若操作后矩阵无变化 则R是可传递的 否则 R不是可传递的 例见教材P30 例2 6 2 7 2 8 29 作业 p32 1 3 5 6 30 2 3等价关系 相容关系和偏序关系 本节要求掌握的知识点 1 等价关系的概念 等价类 集合划分的概念 商集 等价关系与集合划分的相互确定 2 相容关系的概念 相容类 最大相容类 覆盖 完全覆盖 相容关系与完全覆盖的相互确定 3 偏序关系的概念 盖住 盖住元素 哈斯图及其画法 极大 小元 最大 最小元 上 下界 上 下确界 链 反链 半 全序集 31 2 3 1等价关系 上的二元关系 如果 是 1 自反的 2 对称的 3 传递的 则称 为 A上的 等价关系 若 则称 与 等价 记作aRb 或 32 2 3 2等价关系的特征 2 等价关系的矩阵表示按等价关系来调整有限集中元素的顺序可使等价关系的矩阵表示的对角线上有若干个小方阵 这些小方正的元素都为1 例如 1 等价关系的表格及图形表示 p34 p35 33 2 3 3等价类和商集 1 等价类 若R是A上的等价关系 a A 由 中的所有与a等价的元素构成的集合 称为a的等价类 a的等价类记为 a R 即 a R x x A且aRx 注 等价关系 把 的元素分为若干类 各类之间没有公共元素 34 把集合 分为若干非空子集 1 2 An满足 1 当 时 i j 2 A 使 i 1 2 n 即 则集合Pr 1 2 n 称为 的一个划分 2 3 4集合的划分 35 定理1 上的等价关系 确定了A的一种划分 反之 给定了集合 的任一种划分 也总可以找到 上的一个等价关系 注 Pr 当且仅当 Pr 非空时Pr P P 的幂集 时 P 36 例 张扑克 1 扑克 与 同花 2 扑克 与 同点 则 1把 分为四类同花类 2把 分为 类同点类 例 设 则 是等价关系 37 是等价关系 但不直观 用关系图表示 三个不连通的图 二元关系R是自反的 对称的 传递的 且把 分成了三个等价类 A R 38 商集的元素个数 即 在 下的等价类个数 称为 的秩 2 等价关系R将A分成若干等价类 每个类选个代表组成新的集合称为A关于R的商集 表示为A R 即 以集合A上的等价关系R确定的所有互不相同的等价类作为元素而构成的集合 称为A关于等价关系R的商集 例 在上例中A R R R R 39 例 设A a b c d 给定 1 2 3 4 5 6 如下 1 a b c d 2 a b c d 3 a a b c d 4 a b c 5 a b c d 6 a a b c d 则 1和 2是A的划分 其它都不是A的划分 因为 3中的子集 a 和 a b c d 有交 4 A 5中含有空集 而 6根本不是A的子集族 40 例4 mod 是整数集合 上模 同余的二元关系 证明R是等价关系 证明 由于当 时 1 因 自反性 2 若 则 对称性 3 若 则 满足传递性 故 是等价关系商集 I R R R R 其中 R R R 41 小结 给定集合A上的一个等价关系总可以通过寻求互不相同的等价类找到集合A的一个划分 反之 若给定了集合A的一个划分 若指定位于同一个子集中的两个元素是相关的 则这个关系一定是等价关系 简言之 等价关系与划分可以相互确定 42 上的二元关系 若是自反的 对称的 称 为A上的相容关系 注 等价关系必然是相容关系 2 3 5相容关系 43 2 3 6覆盖与完全覆盖 若Ai i 1 2 n 是非空集合A的一些非空子集合 并且满足 A1 A2 An A 则称C A1 A2 An 为A的一个覆盖 44 定理 设C是集合A的一个覆盖 设R为A上的 二元关系 其定义为 当且仅当元素 属于同一覆盖快 则R是A上的相容关系 我们可记上述定理中的由C确定的相容关系为R R C 45 2 3 7相容类与最大相容类 设R是非空集合 上的相容关系 B是A的子集合 如果B中任意两个元素都是R相关的 称B是由相容关系R产生的相容类 注 相容类与等价类 46 若R是非空集合 上的相容关系 B是相容类 在差集A B中没有一个元素能和B中所有元素都是相关的 称B是由相容关系R产生的一个最大相容类 例 课本P40 最大相容类求法 课本P40 41 1 画出 简化的 相容关系图 2 找出所有互不相同的最大完全多边形 最大完全多边形 孤立点 悬挂边 三边形 完全四边形 完全五边形 由所有最大相容类所构成的集合称为集合A上的相容关系R所确定的完全覆盖 记为CR A 47 例 已知集合A 129 134 345 275 347 348 当a b A 且a b至少有一个数码相同时 a b R 求R的所有最大相容类 解 易知该二元关系为相容关系 其次 画出 简化的 关系图 最后 在图中找出所有最大的完全多边形 分别以这些最大的完全多边形的顶点作为元素构成的集合即为所求 R的所有最大相容类为 4个 129 134 129 275 345 275 347 134 345 347 348 48 小结 给定集合A上的一个相容关系总可以通过寻求最大相容类找到集合A的一个完全覆盖 反之 若给定了集合A的一个完全覆盖 若指定位于同一个子集中的两个元素是相关的 则这个关系一定是相容关系 简言之 相容关系与完全覆盖可以相互确定 49 2 3 8偏序关系 设 是 上的二元关系 如果 满足 1 自反的 2 反对称的 3 传递的 则称 是 上的偏序关系 半序关系 例 1 2 3 1 2 1 2 1 2 P 50 注 1 用矩阵表示偏序关系 不能明显看到二元关系的特征 2 用简化的关系图表示较适合 简化的关系图 1 自反性 每个顶点都有自回路 省去 2 反对称性 两个顶点间只可能有一个箭头从左 右 或从下 上的方向从小到大安置顶点 可省略箭头 3 传递性 由于有 a b b c R 则 a c R故只画 a b b c 对应的边 省略边 a c 51 Hasse图 哈斯图 设 是 上的一个偏序关系 如果 则将 画在 下面 且不 使 此时也称b是a的盖住元素 或称a被b盖住 则 间用直线连接 符合简化的关系图的绘制 称这样得到的关系图为哈斯图 例中 偏序关系R1的哈斯图如右 R1 52 哈斯图的画法 1 确定最底层元素 均为极小元 即不是盖住元素的元素 2 第i层是第i 1层元的盖住元素 层层向上 3 相邻层的顶点根据盖住关系进行连线 4 检查有无错漏连线 画哈斯图时的注意事项 1 图中不应该出现三角形 2 图中不应该出现水平线 3 应尽量减少线的交叉 使图清晰 53 例题 哈斯图的画法已知A 1 2 3 4 5 6 8 10 12 16 24 R是A上的整除关系 1 235 4610 812 1624 54 上偏序关系 如果 都有 或 则称 为 上的全序关系 注 1 全序的含义 中每两个元素均能比大小 即任何两个元素都相关 2 偏序则是部分有序 3 小于或等于 关系 1是全序 整除 关系 2和 包含于 关系 3都是偏序 在整除关系 2中 都排成了序 但 与 与 与 等在整除的意义上来说无法排出大小来 55 集合 及 上的一个偏序关系 组成的二元组 称为偏序集 也记之为 注 同一集合上的两个不同的偏序关系 可构成多个偏序集 如前例 1和 2都定义在 上 其中 1是小于或等于关系 2是整除关系 但 1 与 2 是不一样的偏序集 56 若偏序集 的偏序关系 是 上的全序关系 则称 为全序集 1 是全序集 显然 全序集是偏序集的特例 又如 实数全体 在 下是全序集 平面上点集 也可以规定一种 模长大的大 模长相等的情况下 以幅角的大小来比大小 因此 平面上点集也是全序集 当然也是全序集 注 实数全体 平面点集是无法用哈斯图表示的 一般来说 对有限集用哈斯图比较好 对可列集只能示意一下 对不可列无限集是没法表示的 因为任二个数之间一定还有别的数 57 设 是偏序集 是 的子集合 若 是全序集 则称 为 中的链 当 是有限集时 的基数 称为链长 例 在上例哈斯图 2 中 取 1 1 2 4 8 2 整除 则 1 2 是全序关系 1是偏序集 中链长为 的链 2 3 4 5 也都是 中的链 58 设 为偏序集 是 的子集合 且对 都有 且 则称 为 中的反链 当 为有限集时 为反链的长度 注 反链中的元素都互不相关 例如 2是整除关系 在 2 中 1 1 2 2 3 3 都是反链 59 设 A 是偏序集 若 且在 中找不到一个元素 使 则称 为 中的极大元 极小元 例 是偏序集 是整除关系 则 中极大元 中极小元 注1 极大元 极小元必须是子集 中的元素 注2 极大元 极小元并不要求唯一 且同一元素 可以既是极大元 又是极小元 如 60 设 A 是偏序集 若存在某个 对 都有 或 则称 为 的最大元 最小元 例 上例 其哈斯图如下 子集 中是不存在最大元 最小元 的 注 最大元 最小元 本身应属于子集 且与 中任一元素都有关系 61 设 A 是偏序集 B A 若 A 对 B都有 或 称 为B的上界 下界 注 1 上例中 无最大元 但存在 的上界 2 无最小元 1是 的下界 3 最大 小 若存在 则是 的一个上 下 界 4 上 下 界可以不唯一 也可以不存在 62 设 A 是偏序集 B A 若 是B的一个上界 下界 而对任意B的上界 下界 b 都有a b 或b a 称 是B的上确界 下确界 注 上确界 最小上界下确界 最大下界如果存在上 下确界 则上 下确界一定是唯一的 存在上 下界 但不一定存在上 下确界 63 例 试求出上面两个哈斯图中的最大 小 极大 小元素 以及左图中子集 2 3 4 的上 下界以及上 下确界 64 65 2 4复合关系 逆关系 和关系的闭包运算 本节要求掌握的知识点 1 复合关系的概念 求法2 逆关系的概念 求法3 自反 对称 传递 闭包的概念 求法 66 2 4 1复合关系 复合关系 若R是A到B的二元关系 S是B到C的二元关系 复合关系的求法 1 关系图法 R S是由从A到C的所有通路两端点元素构成的有序对作为元素的集合 2 矩阵法 设R S的关系矩阵分别为MR MS 则 MR S MR MS 例 课本P48 50 易见R S为A到C的二元关系 R与S复合记为R S 其定义为 67 显然 若 1和 2是 到 的二元关系 则 1 1 2 b a b 1或 2 2 1 2 b a b 1且 2 3 1 2 b a b 1但 a b 2 5 1 2 a b a b 1 2但 a b 1 2 68 逆关系 若R是A到B的二元关系 则称 b a a b R 是R的逆关系 即B到A的二元关系 例 设A 1 2 3 4 B x y z R 1 x 1 y 2 z 则R的逆关系为 x 1 y 1 z 2 显然 它是一个B到A的二元关系 2 4 2逆关系 R的逆关系也常常记为 69 逆关系的求法 1 集合法 有序对元素前后调换位置 2 矩阵法 矩阵转置 3 关系图 每条有向边取反向 70 2 4 3关系的闭包运算 设R是A上的关系 我们希望R具有某些有用的性质 比如说自反性 如果R不具有自反性 我们通过在R中添加一部分有序对来改造R 得到新的关系R 使得R 具有自反性 但又不希望R 与R相差太多 换句话说 添加的有序对要尽可能的少 满足这些要求的R 就称为R的自反闭包 通过添加有序对来构造的闭包除自反闭包外还有对称闭包和传递闭包 71 设R是非空集合A上的关系 若存在A上的二元关系R 同时满足下面两个条件 1 R 是自反的 对称的或传递的 2 RR 3 对A上任何包含R的自反 对称或传递 关系R 有R R 则称R 是R在A上的自反闭包 对称闭包或传递闭包 一般将R的自反闭包记作r R 对称闭包记作s R 传递闭包记作t R 定理若R A A 则 1 R是自反的iffr R R 2 R是对称的iffs R R 3 R是传递的ifft R R iff ifandonlyif 72 幂运算设R是集合A上的二元关系 n N R的n次幂记为Rn 定义为 1 R0 IA 2 Rn 1 Rn R定理若R A A 且m n N 则 1 Rm Rn Rm n 2 Rm n Rmn 73 幂运算设R是集合A上的二元关系 n N R的n次幂记为Rn 定义为 1 R0 IA 2 Rn 1 Rn R定理若R A A 且m n N 则 1 Rm Rn Rm n 2 Rm n Rmn 74 定理若R A A 则 1 r R R IA 2 s R R R 1 3 t R 75 定理若R A A A n 则t R 定理若R A A 则 1 r s R s r R 2 r t R t r R 3 s t R t s R 76 77 如果关系R是自反的和对称的 那么经过求闭包的运算以后所得到的关系仍就是自反的和对称的 但是对于传递的关系则不然 它的自反闭包仍旧保持传递性 而对称闭包就有可能失去传递性 例如A 1 2 3 R 2 3 是A上的传递关系 R的对称闭包s R s t R 2 3 3 2 而t s R 2 3 3 2 2 2 3 3 显然s R 不再是A上的传递关系 从这里可以看出 如果计算关系R的自反 对称 传递的闭包 为了不失去传递性 传递闭包运算应该放在对称闭包运算的后边 若令tsr R 表示R的自反 对称 传递闭包 我们能证明tsr R t s r R 78 例 若R是对称的 则Rn也是对称的 其中n是任何正整数 证明 用归纳法 1 当n 1 R1 R 显然是对称的 当n 2时 若 x y R2 由复合关系的定义知 必存在z A 使得 x z R且 z y R 又因R是对称的 所以 y z R且 z x R 再有由复合关系的定义知 y x R2 所以R2也是对称的 79 2 假设Rk是对称的 则对任意的 x y Rk 1 由复合关系的定义知 必存在元素t 使得 x t Rk且 t y R又因为Rk R均为对称的 所以 y t R且 t x Rk再由复合关系的定义知 y x R Rk 即 y x R1 k Rk 1所以Rk 1是对称的 综上 1 2 由归纳法 命题得证 80 定理 设R是非空集合A上的关系 1 若R是自反的 则s R 与t R 也是自反的 2 若R是对称的 则r R 与t R 也是对称的 3 若R是传递的 则r R 是传递的 证 只证 2 其余留作练习 由于R是A上的对称关系 所以R R 1 同时IA IA 1 得 R IA 1 R 1 I