《离散数学-3-12序关系.ppt》由会员分享，可在线阅读，更多相关《离散数学-3-12序关系.ppt（29页珍藏版）》请在三一办公上搜索。
1、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，并记 CO
2、V A,x,yA,y盖住x.例3：A=1,2,3,4,6,12,“”为A上整除关系，则“”=,U IACOVA,4,二盖住,偏序关系可以用关系图表示，但通常我们用简化了的关系图表示（哈斯图）对于偏序集，其盖住关系是唯一的，故可由盖住的性质画出偏序集合图，称哈斯图：图中不显示地表示所有序偶，仅画出符合条件“xy,xy，且没有其它元素子满足xz,zy”的那些序偶。（不画自环路，传递性所蕴含的边不画）1）用小圆圈代表元素。2）若xy,xy,把x画在y下面。3）若COVA,则在x,y之间连线。箭头不画例3的哈斯图为：COVA,5,二盖住,P141 定义3-12.3 设A，是一个偏序集，在A的一个子集中
3、，如果每两个元素都是有关系的，则称这个子集为链，在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,从哈斯图上容易看出，在每个链中总可以从最高结点出发沿着盖住方向遍历
4、该链中所有结点。每个反链中任两个结点间均无连线。,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,请问下列偏序关系是不是全序关系？为什么？实数集上的小于
5、等于关系(大于等于关系)。正整数集上的整除关系。集合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,*从图中可以看出，极大元和极小元不
6、是唯一的。*当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
7、）若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，若有
8、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,五、上界与下界,设A，为偏序集，BA，a为B的上界。若对B的
9、所有上界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）最大元？极大元？上界？上确界？则没有最大元
10、；极大元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 定理3-12.3 每一个有限的全序集一定是良序的。证明：设,且A，为全序集。若A，不是良序的，则必有非空子集B，在B中不存在最小元。因B有限，故在B中必可找到两个元素x,y无关（即xy，或yx都不成立）但x,yA，这与A，全序矛盾。,28,本课小结,偏序关系偏序集全序关系极大元极小元下确界上确界,29,作业,P146(7),
