《离散数学 》课件第3-4章 集合与关系.ppt

********************************************************************************************************************3.9.2偏序关系的哈斯图(TheHasseDiagramofPosets)哈斯(Hasse)根据盖住的概念给出了偏序关系图的一种画法,这种画法画出的图称为哈斯图,作图规则如下：*3.9.2偏序关系的哈斯图(TheHasseDiagramofPosets)用小圆圈代表元素;若元素a≠b且a≤b时，则结点a画在结点b的下方。(3)若b盖住a，则在a与b之间用直线连接.由于所有边的箭头向上,故省去箭头。例3中的关系的哈斯图如右图.*例5设U={a,b,c}，则“”关系是2U上的偏序关系，偏序关系“”的哈斯图如下：*例6设A={2,3,6,12,24,36}，A上的整除关系“”是一偏序关系，其哈斯图如下：*3.9.3偏序集中特殊位置的元素既然偏序集的元素之间具有分明的层次关系，则其中必有一些处于特殊位置的元素。定义3.9.3（极大元，极小元，最大元，最小元）B，设是一个偏序集，且BA，如果存在元素b使得（1）不存在xB满足xb且bx，则称b为B的极大元；B满足xb且x（2）不存在xb，则称b为B的极小元；（3）对B中任意元素x，均有xb，则称b为B的最大元；（4）对B中任意元素x，均有bx，则称b为B的最小元。*例7.设A＝｛a,b,c｝，对于偏序集，集合极大元极小元最大元最小元{a,b,c}{a,b,c}{{a},{b},{c}}{a},{b},{c}{a},{b},{c}无无{{a},{a,b}}{a,b}{a}{a,b}{a}3.9.3偏序集中特殊位置的元素*例8在例6中取B={6，12}，C={2，3，6}，则集合极大元极小元最大元最小元A24,362,3无无{6,12}126126{2,3,6}62,36无3.9.3偏序集中特殊位置的元素*最大（小）元和极大（小）元的性质：（1）最大（小）元必是极大（小）元，反之不然。（2）最大（小）元不一定存在，若存在，则是唯一的。（3）极大（小）元不唯一，当B＝A时，偏序集的极大元即是其哈斯图中最顶层元素，其极小元是哈斯图中最底层元素，不同的极大（小）元之间不可比，它们处在哈斯图中的同一个层次。证：3.9.3偏序集中特殊位置的元素*定义3.9.4（上界，下界，上确界，下确界)A，如果存在元素a设为一偏序集，且BA，B中任意元素x，都满足（1）xa，则称a为B的上界；x，则称a为B的下界；（2）a（3）若a是B的上界，且对B的任意上界，均有a则称a为B的最小上界（上确界），记作LUB(B)；（4）若a是B的下界，且对B的任意下界，均有a,则称a为B的最大下界（下确界），记作GLB(B)。*例9.设A＝｛a,b,c｝，对于偏序集，集合上界下界上确界下确界{a,b,c}{a,b,c}{{a},{b},{c}}{a,b,c}{a,b,c}{{a},{a,b}}{a,b},{a,b,c}{a},{a,b}{a}3.9.3偏序集中特殊位置的元素*例10在例6中取B={12,24,36}，C={2，3，6}，则集合上界下界上确界下确界Anonenonenonenone{12,24,36}none2,3,6,12none12{2,3,6}6,12,24,36none6none{6,12}12,24,362,3,6126{24,36}none2,3,6,12none123.9.3偏序集中特殊位置的元素*