次序关系 第1页 次序关系也是常遇到的重要关系 例如 数值的 关系 集合的 关系 图书馆的图书按书名的字母次序排序 词典中的字 词 的排序 计算机中文件按文件名排序 程序按语句次序执行 本节讨论几种次序关系 第2页 等价关系 有向图 等价类 商集 划分 相容类 最大相容类 完全覆盖 简化图 二元关系 性质 自反 对称 传递 反对称 反自反 相容关系 偏序关系 全序 哈斯图 重要元素 第3页 一 偏序关系 partialorderrelation 1 定义3 12 1R是A上自反 反对称和传递的关系 则称R是A上的偏序关系 并称是偏序集 因为数集上的 是熟知的 且是偏序关系 所以用符号 表示任意偏序关系 R 表示为a b 读作 a小于等于b 意即在偏序关系中a排在b的前面 要注意 不一定是 小于或等于 的含义 常见偏序关系 小于等于关系 大于等于关系 集合的包含关系 恒等关系 空集上的空关系 全域关系呢 第4页 A 1 2 4 6 是A中的整除关系 证明其是偏序关系 证明 R 自反IA IA R反对称RC RC R IA传递R2 R R R所以 R是偏序关系 例3 12 1 第5页 是偏序集 x y A 若要么x y 要么y x 则称x与y是可比较的 例3 12 1中1与2 1与4 1与6 2与4 2与6是可比较的 而4与6是不可比较的 2 x与y是可比较的 第6页 二 全序 线序 链 定义3 12 2 是偏序集 任何x y A 如果x与y都是可比较的 则称 是全序关系 线序 链 例3 12 2 B 1 2 4 8 表示整除关系 如右图分析得到 是全序关系 全序关系一定是偏序关系 但是偏序不一定是全序 偏序关系的有向图 不能直观地反映出元素之间的次序 所以下面介绍另外一种图 Hasse图 通过这个图 就能够清晰地反映出元素间的层次 第7页 三 偏序集哈斯图 Hasse图 1 用矩阵表示偏序关系 不能明显看出二元关系的特征 2 用简化的关系图表示较合适 简化的关系图 1 自反性 每个结点都有自回路 可省去自回路 2 反对称性 两个结点间只可能有一个箭头方向 所以将箭头默认为从下 上 可省略箭头 3 传递性 由于有 R 则 R 故只画 对应的边 省略边 第8页 令是偏序集 x y z 作图规则 1 用 表示A中元素 2 若x y 且x y 则将结点y画在结点x的上方 3 若x y x y且没有不同于x y的z 使得x z z y 则在x y之间连一直线 方法 分层法一般先从最下层结点 全是序偶的第一元素 射出的边 逐层向上画 直到最上层结点 全是序偶的第二元素 射入的边 偏序集哈斯图 Hasse图 的画法 第9页 它们的Hasse图分别如下 例3 12 1和3 12 2 4 2 哈斯图的意义在于 元素之间从下向上有线相连 则这两个元素存在着偏序关系 反之则不存在偏序关系 右图是全序 它的Hasse图是一条直线 所以全序也叫线序 或链 6 1 4 2 6 1 4 2 2 8 第10页 练习 教材第146页 7 2 4 1 3 c 第11页 C 1 2 3 6 12 24 36 D 1 2 3 5 6 10 15 30 是C D上整除关系 的Hasse图 以及A a b c 的Hasse图 练习 第12页 定义设是偏序集 x y A 如果x y 且x y 且不存在z使得x z z y 则称y盖住x 并且记COVA x y A y盖住x 例 在A 1 2 4 6 上的整除关系中 有哪些盖住关系呢 解 整除关系 2盖住1 4盖住2 6盖住2 COVA 对于给定的偏序集合 它的盖住关系是唯一的 P140盖住 第13页 四 偏序集中的重要元素 设是偏序集 B是A的非空子集 一 极大 小 元 最大 小 元对于B中的一个元素b 若B中没有元素x 满足b x且x b 则称b为B的极小元 即B中没有比b更小的元素了 b就是极小元 对于B中的一个元素b 若B中没有元素x 满足b x且b x 则称b为B的极大元 在B中没有比b更大的元素了 b就是极大元 对于B中的一个元素b 若对于B中的任何元素x 满足b x 则称b为B的最小元 最小元b是B中元素 该元素比B中所有元素都小 对于B中的一个元素b 若对于B中的任何元素x 满足x b 则称b为B的最大元 最大元b是B中元素 该元素比B中所有元素都大 第14页 例3 12 3 给定的Hasse图如图所示 从Hasse图找极小 大 元 最小 大 元 A 1 2 3 6 12 24 36 IA 2 3 2 3 1 2 3 6 24 1 24 36 无 无 1 无 6 24 1 无 对于有穷集 极小元和极大元必存在 可能存在多个 最小元和最大元不一定存在 如果存在一定唯一 最小元一定是极小元 最大元一定是极大元 孤立结点既是极小元 也是极大元 第15页 对于有穷集 极小元和极大元必存在 可能存在多个 最小元和最大元不一定存在 如果存在一定唯一 最小元一定是极小元 最大元一定是极大元 孤立结点既是极小元 也是极大元 特殊元素的性质 第16页 证明 假设B有两个最小元a b 则因为a是最小元 b B 根据最小元定义 有a b 类似地 因为b是最小元 a B 根据最小元定义 有b a 因为 有反对称性 所以有a b 即有最小元则唯一 同理可证最大元的唯一性 定理3 12 1 是偏序集 B是A的非空子集 如果B有最小元 最大元 则最小元 最大元 是唯一的 第17页 若有a A 且对B的任意元素x 都满足x a 则称a是B的上界 上界a是A中元素 该元素比B中所有元素都大 若有a A 且对B的任意元素x 都满足a x 则称a是B的下界 下界a是A中元素 该元素比B中所有元素都小 a是B的上界 并且对B的所有上界x 都有a x 则称a是B的最小上界 上确界 记作LUBB a 即a是上界中最小的 若B有上确界 则是唯一的 a是B的下界 并且对B的所有下界y 都有y a 则称y是B的最大下界 下确界 记作GLBB a 即a是下界中最大的 若B有下确界 则是唯一的 二 上界 下界 最小上界 最大下界 第18页 例3 12 5 给定的Hasse图如图所示 1 6 12 24 36 1 24 1 2 3 6 1 无 6 12 24 36 6 6 24 无 1 1 6 1 1 一个集合可能没有上界或下界 若有 则不一定唯一 并且它们可能在B中 也可能在B外 2 一个集合若有上下确界 必定是唯一的 第19页 性质 1 一个集合可能没有上界或下界 若有 则不一定唯一 并且它们可能在B中 也可能在B外 2 一个集合若有上下确界 必定是唯一的 第20页 元素比较表 第21页 补充 若b B是B的最大元 b是B的极大元 上界 上确界 若b B是B的最小元 b是B的极小元 下界 下确界 若a A是B的上确界 且a B a是B的最大元 若a A是B的下确界 且a B a是B的最小元 若 是一个全序关系 且b B是B的最大元 b是B的极大元 若 是一个全序关系 且b B是B的最小元 b是B的极小元 若b B是B的极大元 且b是唯一的 b是B的最大元 若b B是B的极小元 且b是唯一的 b是B的最小元 第22页 定义3 12 9 是偏序集 如果对A的任何非空子集B 都有最小元 则称 是A上的良序 并称为良序集 例如N是自然数集合 是小于或等于关系 就是良序集 定理3 12 2 所有良序集 一定是全序集 证明 设为良序集 任取x y A 构成子集 x y 它有最小元 该最小元或是x或是y 于是有x y或y x 所以是全序集 良序 第23页 定理3 12 3 有限的全序集 一定是良序集 证明 设A a1 a2 an 是全序集 假设它不是良序 必存在非空子集B A B中无最小元 因B是有限集 必存在x y B 使得x与y无关 与 是全序矛盾 是良序集 无限的全序集 不一定是良序集 良序 第24页 掌握偏序 全序的概念 会画Hasse图 会求重要元素 作业第145页 1 6 7 本节要求 第25页 集合与关系的结构图 枚举法有向图矩阵 等价关系 有向图 等价类 商集 划分 偏序关系 相容类 最大相容类 完全覆盖 简化图 全序 哈斯图 计算方法 运算性质 重要元素 第26页 第27页 说明 1 集合中的元素间次序是无关紧要的 但是必须是可以区分的 2 对集合中的元素无任何限制 3 集合中的元素可以是集合 如S a 1 2 p q 4 对一个集合来说 任一事物或者是它的元素或者不是它的元素 二者必居其一而不可兼而有之 第28页 五 集合与集合的关系 集合中的元素都是不同的 凡是相同的元素 均视为同一个元素 1 1 2 1 2 一旦给定了集合A 对于任意元素a 可以准确地判定a是否在A中 这是明确的 集合中的元素是没有顺序的 2 1 1 2 集合的三大特征 1 互异性 2 确定性 3 无序性 第29页 3 1集合 一 集合的概念集合 SET 即是由一些确定的彼此不同的客体 事物 汇集到一起组成一个整体 称为集合具有共同性质的一些客体 事物 聚集成的整体 讨论 1 不同的确定的有共同性质的客体之全体 2 客体 泛指一切 可以是具体的 抽象的 元素 element 成员 即组成集合的客体 称之为元素 二 集合的记法通常用带 不带 标号的大写字母A B C A1 B1 C1 X Y Z 表示集合 通常用带 不带 标号的小写字母a b c a1 b1 c1 x y z 表示元素 第30页 3 2集合的运算 定义设A B是两个集合 x x A x B x A B x A x B x x A x B x A B x A x B x x A x B x A B x A x B x x E x A x x A x A x A x A x x A x B x B x A A B A B B A A B A B A B 1 并集A B 2 交集A B 3 差集A B 4 补集 A 5 对称差集A B 第31页 七 证明集合A是空集的方法 方法一 其逻辑判断条件是永假 x P x P x 方法二 用反证法 设 a A 引出矛盾的结果 方法三 利用等式 例如 A A P92c 第32页 例2令A a b c d e f g h i j k l m n o p q r s t u v w x y z 是英文字母表 一个英文单词可以看成有序n元组 如at boy data computer 于是可以说 at A2 boy A3 data A4 computer A8 于是英文词典中的单词集合可以看成是A A2 An的一个子集 作业第105页 第33页 第34页 二 例 给定A中关系R 如图所示 分别求A上另一个关系R 使得它是包含R的 最小的 序偶尽量少 分别具有自反 对称 传递 性的关系 这个R 就分别是R的自反 对称 传递 闭包 r R s R t R 第35页 R3 R4 R6 R8均是对称关系 例 对称 对称 对称 对称 非对称 非对称 非对称 非对称 第36页 例 集合的覆盖 第37页 例 集合的覆盖 续 第38页 例 集合划分 分类 第39页 第40页 二 简化图和简化矩阵 续 矩阵的简化 用下三角矩阵 不含主对角线 代替R的矩阵 主对角线全为1矩阵关于主对角线对称 第41页 。