离散数学-3-12序关系.pptVIP

第三章 集合与关系 3-12 序关系 授课人：李朔 Email: 1 一偏序关系 n 当在一个集合考虑元素的次序问题时，就牵涉一个重要关 系部分序关系。 n P140 定义3-12.1 A为一个集合，若A上的一个关系R有自 反性，反对称性和传递性，则称R为A上的一个偏序关系， 记为“”。序偶A，称为偏序集。 n 例1：易证实数集R上的小于等于关系是偏序关系。 是偏序集。 n 例2：给定A=2, 3, 6, 8, “”=x整除y *易见 “”=, , , , ，, 也是一个偏序关系。 n 集合间的包含关系是偏序关系吗？ 2 二盖住 n P140定义3-12.2 在偏序集A，中，若x, yA, xy, xy, 且没有其它元素子满足xz, zy, 则称元素y 盖住x，并记 COV A, x, yA, y盖住x. n 例3：A=1, 2, 3, 4, 6, 12, “”为A上整除关系，则 “”=, ,U IA COVA, , , , , 3 二盖住 n 偏序关系可以用关系图表示，但通常我们用简化了的关系 图表示（哈斯图） n 对于偏序集，其盖住关系是唯一的，故可由盖住的性质画 出偏序集合图，称哈斯图：图中不显示地表示所有序偶， 仅画出符合条件“xy,xy，且没有其它元素子满足xz, zy”的那些序偶。（不画自环路，传递性所蕴含的边不 画） n1）用小圆圈代表元素。 n2）若xy, xy,把x画在y下面。 n3）若COVA,则在x, y之间连线。 n箭头不画 n 例3的哈斯图为： COVA, , , , , 4 二盖住 n P141 定义3-12.3 设A，是一个偏序集，在A 的一个子集中，如果每两个元素都是有关系的， 则称这个子集为链，在A中的一个子集中，如果每 两个元素都是无关的，则称这个子集为反链。单 个元素的子集既是链也是反链。 n P141 例如：设集合A=a,b,c,d,e R=, 验证为偏序集，画出哈斯图，举例说明 链及反链。 5 二盖住 n 解 写出R的关系矩阵。 从关系矩阵中易知，R是自反和反对称的，并可验证R是 传递的，故它是偏序关系。(关系图P142 图3-12.3) COV A=, 其哈斯图如上右： 显然，集合a,b,c,e，a,b,c，b,c，a和a,d,e等 都是A的子集也是链。而b,d，c,d，a等都是反链。 c b a d e 6 n从哈斯图上容易看出，在每个链中总可以 从最高结点出发沿着盖住方向遍历该链中 所有结点。 n每个反链中任两个结点间均无连线。 7 三全序关系 n P142 定义3-12.4 在偏序集A，中，如果A 是一个链，则称A，为全序集或线序集，称 该关系为全序关系或线序关系。 n全序集就是对任意x,yA,或者有xy,或者有yx成立。 n 例：定义于自然数集N上的“小于等于”关系是全 序集。 8 n 练习1 集合A1,2,3,4,5,6, 关系为整除关系， 画出哈斯图。 COV A=, 5 3 64 1 2 9 n 练习2：给定A=,a,a, b,a, b, c 上的包含关系 ，画出哈斯图。 易见, aa, ba, b, c， 故为全序集。 其哈斯图如下： a,b,c,d a,b a (全序关系的哈斯图图呈现现一直线线段-链。) 10 请问下列偏序关系是不是全序关系？为什么？ 实数集上的小于等于关系(大于等于关系)。 正整数集上的整除关系。 集合A的幂集P(A)上的包含关系。 11 四极大元和极小元 n P142 定义3-12.5 设A，为一个偏序集，且 B为A的子集，对B中一个元素b，若B中没有元素x 使bx，且bx，则称b为B中极大元。 n 同理若B中没有元x满足bx, xb，则b称为B的极 小元。 12 四极大元和极小元 n P143例6：设A=2, 3, 5, 7, 14, 15, 21，R为A上整除 关系，B=2, 7, 3, 21, 14，求B上极大元与极小元。 解：CovA=, , , , , ,哈斯图如下： 易见B的极小元为2，3，7，极大元为14，21。当BA时， 即可求出A中的极大、极小元。 13 *从图中可以看出，极大元和极小元不是唯一的。 *当B=A时，则A，的极大元是哈斯图中最顶层 的元素，极小元是是哈斯图中最底层的元素，不 同的极大元和极小元之间是无关的。 14 四最大元和最小元 n P143 定义3-12.6 A，为一个偏序集，且B 为A的子集。若有某个元素bB，对B中的每个元x 有xb，则b称为B，的最大元。 n 同理，若有某个元素bB，对每一个xB有bx， 则b称为B，的最小元。 n P143 定理3-12.1 令A，为偏序集BA，若 B有最大（最小）元，则必唯一。 证：设a, b都为B的最大元，则ab，ba，由的反 对称性知a=b。 15 四最大元和最小元 a,b a b 例如，考虑偏序集，其哈 斯图如右图所示： （1）若Ba, ，则B的最大元为 ，最小元为 。 （2）若Ba,b，则B的最大元为 ，最小元为 。 （3）若B,a,b,a,b,则B的最大 元为 ，最小元为 。 16 四最大元和最小元 n最大(小)元是B中最(大）小的元素，它与B 中每个元素都有关系；而极大(小)元不一定 与B中每个元素有关系，只要没有比它小的 元素，它就是极小元。 n对于有穷集B，极大（小）元一定存在，但 最大（小）元不一定存在。 n极大（小）元可能有多个，但最大（小） 元如果存在，一定是唯一的。 17 四最大元和最小元 5 3 64 1 2 集合A1,2,3,4,5,6, 上的整除关系，其哈斯图 如右图所示：当BA时， 极大元为 ， 极小元为 ， 最大元为 ， 最小元为 。 18 五上界与下界 n P144 定义3-12.7 设A，为偏序集，BA， 若有aA且对B的任意元素x有xa，称a为子集B的 上界， n 同样的，对B的任意元素x有ax，则称a为B的下界 。 19 a b cde f g hi jk 例如，给定偏序集的其哈斯 图如右图所示： 若Ba,b,c,d,e,f,g，则B的 极大元 ，极小元 ， 最大元 ，最小元 ， 上界为 ，下界为 。 若Bh,i,f,g， 则B的 极大元 ，极小元 ， 最大元 ，最小元 ， 上界为 ，下界为 。 20 a b cde f g hi jk 例如，给定偏序集的其哈斯 图如右图所示： 若Ba,b,c,d,e,f,g，则B的 极大元 ，极小元 ， 最大元 ，最小元 ， 上界为 ，下界为 。 若Bh,i,f,g， 则B的 极大元 ，极小元 ， 最大元 ，最小元 ， 上界为 ，下界为 。 上界下界不是唯一的 21 五、上界与下界 n 定义3.12.8 设A，为偏序集，BA，a为B 的上界。若对B的所有上界y均有ay，称a为B的最 小上界（上确界），记作LUB B n 同样，b为B的一个下界，若对B的任一下界z，有 zb，称b为B的最大下界（下确界）记作GLB B。 22 五上界与下界 2 3 6 12 24 36 例如，给定偏序集的其 哈斯图如右图所示： 若B6,12， 则B的极大元 ， 极小元 ， 最大元 ， 最小元 ， 上界为 ， 下界为 ， 上确界为 ， 下确界为 。 23 五上界与下界 例如，给定偏序集的其 哈斯图如右图所示： 若B2，3，6， 则B的极大元 ， 极小元 ， 最大元 ， 最小元 ， 上界为 ， 下界为 ， 上确界为 ， 下确界为 。 24 五上界与下界 n 例：X=a , b, c， A=P(X)， A， n思考：若B=a, b, b, c, b, c, 1）最大元？极大元？上界？上确界？ 则没有最大元；极大元a, b, b, c；上界，上确 界为a, b, c； 2）最小元，极小元，下界，下确界？ 最小，极小，下界，下确界都为。 n若B=a,c时？ 则没有最大元；极大元为a,c；上界为a, c, a, b, c；上确界为a, c； 没有最小元；极小元为a,c；下界，下确界为。 25 六良序集 n P144 定义3-12.9：任一偏序集，如果它的每个非空子集 存在最小元，这种偏序集称良序集。 n 例如:自然数集N对于小于等于关系是良序集。 整数集上的小于等于关系是不是良序集 ？ n 定理3-12.2 每一个良序集，一定为全序集。 证证明：设A，为良序集，对任x, yA构成子集x, y，其最小元不是x，就是y，即一定有xy或yx。故A ，为全序集。但是一个全序集，并一定是良序集。 n 例如：大于0小于1的全部实数，按其大小次序显然构成一 个全序集，但不是良序集，集合本身就不存在最小元。 n 但容易证明以下定理 26 六良序集 n P145