离散数学等价偏序函数.ppt

第六节等价关系与划分 主要内容等价关系的定义与实例等价类及其性质商集与集合的划分等价关系与划分的一一对应 一 等价关系的定义与实例定义7 15设R为非空集合上的关系 如果R是自反的 对称的和传递的 则称R为A上的等价关系 设R是一个等价关系 若 R 称x等价于y 记做x y 在我们日常生活和学习中 就有一些等价关系的例子 如 1 在一群人的集合上年龄相等的关系是等价关系 而朋友关系不一定是等价关系 因为它可能不是传递的 2 命题公式间的逻辑等值关系是等价关系 3 集合上的恒等关系是等价关系 4 在同一平面上直线之间的平行关系 三角形之间的相似关系都是等价关系 实例设A 1 2 8 如下定义A上的关系R R x y A x y mod3 其中x y mod3 叫做x与y模3相等 即x除以3的余数与y除以3的余数相等 不难验证R为A上的等价关系 因为 x A 有x x mod3 x y A 若x y mod3 则有y x mod3 x y z A 若x y mod3 y z mod3 则有x z mod3 图6 模3等价关系的关系图 图6 2 等价类的性质 定理7 14设R是非空集合A上的等价关系 则 1 x A x 是A的非空子集 2 x y A 如果xRy 则 x y 3 x y A 如果xy 则 x 与 y 不交 4 x x A A 三 商集与集合的划分1 定义7 17设R为非空集合A上的等价关系 以R的所有等价类作为元素的集合称为A关于R的商集 记做A R A R x R x A 实例设A 1 2 8 A关于模3等价关系R的商集为A R 1 4 7 2 5 8 3 6 A关于恒等关系和全域关系的商集为 A IA 1 2 8 A EA 1 2 8 2 集合的划分定义7 18设A为非空集合 若A的子集族 P A 满足下面条件 1 2 x y x y x y x y 3 A则称 是A的一个划分 称 中的元素为A的划分块 例设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的划分 四 商集与划分的对应关系 商集A R就是A的一个划分 不同的商集对应于不同的划分 任给A的一个划分 如下定义A上的关系R R x y A x与y在 的同一划分块中 则R为A上的等价关系 且该等价关系所确定的商集就是 A上的等价关系与A的划分是一一对应的 例给出A 1 2 3 上所有的等价关系 解如下图 先做出A的所有划分 从左到右分别记作 1 2 3 4 5 1 2 3 图7 这些划分与A上的等价关系之间的一一对应是 4对应于全域关系EA 5对应于恒等关系IA 1 2和 3分别对应于等价关系R1 R2和R3 其中R1 IAR2 IAR3 IA 附录 等价关系在计算机科学中的应用 关系概念对计算机科学的理论和应用都非常重要 复合的数据结构 如陈列表 树等 用来表示数据的集合 这些数据是由元素间的关系联系的 关系是数学模型的一部分 它常常在数据结构内隐含地体现出来 数值应用 信息检索 网络问题等就是关系的应用领域 因而关系的运算和处理是重要的 关系在包括程序结构和算法分析的理论方面也有重要的作用 例 在信息检索系统中 所有生物的集合X可分割成 P A P表示所有植物集合 A表示所有动物集合 也可构成 E F E表示史前生物 F表示史后生物 其交叉划分Q P E P F A E A F 第七节偏序关系 一 偏序关系1 定义7 19偏序关系 非空集合A上的自反 反对称和传递的关系 记作 设 为偏序关系 如果 则记作x y 读作x 小于或等于 y 2 实例集合A上的恒等关系IA是A上的偏序关系 小于或等于关系 整除关系和包含关系也是相应集合上的偏序关系 3 相关概念定义7 20设R为非空集合A上的偏序关系 x y A x与y可比 x y y x 任取两个元素x和y 可能有下述几种情况发生 x y 或y x x y x与y不是可比的 定义7 21R为非空集合A上的偏序关系 x y A x与y都是可比的 则称R为全序 或线序 实例 数集上的小于或等于关系是全序关系整除关系不是正整数集合上的全序关系 定义7 22x y A 如果x y且不存在z A使得x z y 则称y覆盖x 例如 1 2 4 6 集合上的整除关系 2覆盖1 4和6覆盖2 但4不覆盖1 二 偏序集与哈斯图1 偏序集定义7 23集合A和A上的偏序关系 一起叫做偏序集 记作 实例 整数集合Z和数的小于或等于关系 构成偏序集集合A的幂集P A 和包含关系R 构成偏序集 2 哈斯图利用偏序关系的自反 反对称 传递性进行简化的关系图特点 每个结点没有环两个连通的结点之间的序关系通过结点位置的高低表示 位置低的元素的顺序在前具有覆盖关系的两个结点之间连边 三 偏序集中的特殊元素 1 最小元 最大元 极小元 极大元定义7 24设为偏序集 B A y B 1 若 x x B y x 成立 则称y为B的最小元 2 若 x x B x y 成立 则称y为B的最大元 3 若 x x B x y x y 成立 则称y为B的极小元 4 若 x x B y x x y 成立 则称y为B的极大元 性质 对于有穷集 极小元和极大元一定存在 还可能存在多个 最小元和最大元不一定存在 如果存在一定惟一 最小元一定是极小元 最大元一定是极大元 孤立结点既是极小元 也是极大元 2 下界 上界 下确界 最大下界 上确界 最小上界 定义7 25设为偏序集 B A y A 1 若 x x B x y 成立 则称y为B的上界 2 若 x x B y x 成立 则称y为B的下界 3 令C y y为B的上界 则称C的最小元为B的最小上界或上确界 4 令D y y为B的下界 则称D的最大元为B的最大下界或下确界 性质 下界 上界 下确界 上确界不一定存在下界 上界存在不一定惟一下确界 上确界如果存在 则惟一集合的最小元就是它的下确界 最大元就是它的上确界 反之不对 例画出和的哈斯图 并指出其中的特殊元 解 1 的哈斯图如下 由图可知1为最小元 没有最大元 7 8 9 10 11 12均为极大元 极小元为1 1为 1 2 12 的下界 也是下确界 1 2 12 中没有上确界或上界 2 的哈斯图如下 P a b c a b c a b a c b c a b c 由图可知 为P a b c 的最小元 a b c 为它的最大元 同时 a b c 也分别为它们的极小元和极大元 下确界和上确界 a b c d e 例已知偏序集的哈斯图如下 h g f 试写出对应的A和A上的偏序关系R 解 A a b c d e f g h R a b c d e h g f 例设偏序集如下图所示 求A的极小元 最小元 极大元 最大元 设B b c d 求B的下界 上界 下确界 上确界 图10 解极小元 a b c g 极大元 a f h 没有最小元与最大元 B的下界和最大下界都不存在 上界有d和f 最小上界为d 例 画出集合S 1 2 3 4 5 6 在偏序关系 整除 下的哈斯图 并讨论 写出 1 2 3 4 5 6 的极大 小 元 最大 小 元 分别写出 2 3 6 及 2 3 5 的上界 下界 上确界 下确界 解 设 为整除关系 在偏序集中 COV S COV S 1 极大元 4 5 6极小元 1最大元 没有最小元 1 2 3 6 的上 确 界 6下 确 界 1 2 3 5 的上 确 界 无下 确 界 1 序关系在项目管理中的应用 实例 调度问题 假设一个项目由20个任务构成 某些任务只能在其他任务结束之后完成 怎么找到关于这些项目的顺序 如果只有一台机器 而且每项任务的截止时间没有限制 则对这个问题可用拓扑排序来解决 所谓拓扑排序 将原来的偏序集扩张成一个对应的全序集 所以为了构造该问题的求解模型 我们首先建立任务集合上的部分序集 使得a b当且仅当a和b是任务且直到a结束后b才能开始 例 P129图7 97 10 第八节习题课 1 主要内容有序对与笛卡儿积的定义与性质二元关系 从A到B的关系 A上的关系关系的表示法 关系表达式 关系矩阵 关系图关系的运算 定义域 值域 域 逆 合成 限制 像 幂关系运算的性质A上关系的自反 反自反 对称 反对称 传递的性质A上关系的自反 对称 传递闭包A上的等价关系 等价类 商集与A的划分A上的偏序关系与偏序集 2 要求 基本概念要清楚熟练掌握关系的三种表示法能够判定关系的性质 等价关系或偏序关系 掌握含有关系运算的集合等式掌握等价关系 等价类 商集 划分 哈斯图 偏序集等概念 以下基本运算要熟练A B domR ranR fldR R 1 R S Rn r R s R t R 求等价类和商集A R给定A的划分 求出 所对应的等价关系求偏序集中的极大元 极小元 最大元 最小元 上界 下界 上确界 下确界掌握基本的证明方法证明涉及关系运算的集合等式证明关系的性质 证明关系是等价关系或偏序关系 2 设A 1 2 3 4 在A A上定义二元关系R R x y u v 求R导出的划分 解A A 根据有序对中的x y 2 3 4 5 6 7 8将A划分成等价类 A R 4 设偏序集的哈斯图如图所示 1 写出A和R的集合表达式 2 求该偏序集中的极大元 极小元 最大元最小元 主要内容函数的定义函数的性质函数的逆函数的合成与后面各章的关系是代数系统的基础 第八章函数 注 因时间关系只讲函数定义和性质 一 函数的定义与相关概念1 函数定义定义8 1设F为二元关系 若 x domF都存在唯一的y ranF使xFy成立 则称F为函数对于函数F 如果有xFy 则记作y F x 并称y为F在x的值 例F1 F2 F1是函数 F2不是函数 二 函数的性质 定义8 6设f A B 1 若ranf B 则称f A B是满射的 2 若 y ranf都存在唯一的x A使得f x y 则称f A B是单射的 3 若f A B既是满射又是单射的 则称f A B是双射的 例判断下面函数是否为单射 满射 双射的 为什么 1 f R R f x x2 2x 1 2 f R Z f x x 3 f R R f x 2x 1 4 f R R f x x2 1 x 其中R 为正实数集 解 1 f R R f x x2 2x 1在x 1取得极大值0 既不是单射也不是满射的 2 f R Z f x x 是满射的 但不是单射的 例如f 1 5 f 1 2 1 3 f R R f x 2x 1是满射 单射 双射的 因为它是单调函数并且ranf R 4 f R R f x x2 1 x有极小值f 1 2 该函数既不是单射的也不是满射的 三 练习1 对给定的A B和f