离散数学屈婉玲第七章.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 划分实例 例10 设 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的划分. * 例11 给出 A＝{1,2,3}上所有的等价关系 实例 1 2 3 ?1 1 2 3 ?5 1 2 3 ?2 1 2 3 ?4 1 2 3 ?3 ?1对应 EA, ?5 对应 IA, ?2, ?3 和 ?4分别对应 R2, R3和 R4.? R2={2,3,3,2}∪IA R3={1,3,3,1}∪IA R4={1,2,2,1}∪IA 解 先做出A的划分, 从左到右分别记作 ?1, ?2, ?3, ?4, ?5. * 7.7 偏序关系 主要内容 偏序关系 偏序关系的定义 偏序关系的实例 偏序集与哈斯图 偏序集中的特殊元素及其性质 极大元、极小元、最大元、最小元 上界、下界、最小上界、最大下界 * 定义与实例 定义7.19 偏序关系：非空集合A上的自反、反对称和传递的关系， 记作?. 设?为偏序关系, 如果 x, y ∈?, 则记作 x ? y, 读作 x“小于或等于”y. 实例 集合A上的恒等关系 IA是 A上的偏序关系. 小于或等于关系, 整除关系和包含关系也是相应集合上的偏 序关系. * 相关概念 定义7.20 设 R 为非空集合A上的偏序关系, (1) x, y∈A, x与y可比 ? x ? y∨y ? x (2) 任取元素 x 和 y, 可能有下述几种情况发生： x ? y (或 y ? x), x＝y, x与y不是可比的 定义7.21 R 为非空集合A上的偏序关系, (1) ?x,y∈A, x与y都是可比的，则称R为全序（或线序） 实例：数集上的小于或等于关系是全序关系,整除关系不是正 整数集合上的全序关系 定义7.22 x,y∈A, 如果 x?y 且不存在 z∈A 使得 x?z?y, 则称 y 覆盖x. 例如{1,2,4,6}集合上整除关系, 2覆盖1, 4和6覆盖2, 4不覆盖1. * 偏序集与哈斯图 定义7.23 集合A和A上的偏序关系?一起叫做偏序集, 记作 A,?. 实例: Z,≤, P(A),R? 哈斯图: 利用偏序关系的自反、反对称、传递性进行简化的 关系图 特点： (1) 每个结点没有环 (2) 两个连通的结点之间的序关系通过结点位置的高低表 示，位置低的元素的顺序在前 (3) 具有覆盖关系的两个结点之间连边 * 实例 例12 偏序集{1,2,3,4,5,6,7,8,9}, R整除和P({a,b,c}),R?的 哈斯图. * 例13 已知偏序集A,R的哈斯图如下图所示, 试求出集合A 和关系R的表达式.? 解 A={ a, b, c, d, e, f, g, h } R={b,d,b,e,b,f,c,d,c,e,c,f,d,f,e,f,g,h}∪IA 实例 * 偏序集中的特殊元素? 定义7.24 设A,?为偏序集, 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的极大元 性质： (1) 对于有穷集，极小元和极大元一定存在，可能存在多个. (2) 最小元和最大元不一定存在，如果存在一定惟一. (3) 最小元一定是极小元；最大元一定是极大元. (4) 孤立结点既是极小元，也是极大元. * 定义7.25 设A, ?为偏序集, B?A, y∈A (1) 若?x(x∈B→x?y)成立, 则称y为B的