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

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