二元关系偏序关系

1、二元关系偏序关系二元关系二元关系根本概念 (重点)4.2 关系的运算4.3 关系的性质 (重点)4.4 关系的闭包4.5 等价关系和偏序关系 (重点及难点)4.6 函数的根本概念偏序关系偏序关系Hasse图重点重要元素重点拓扑排序偏序关系定义 偏序关系：设A上的二元关系R, 假设R是自反的, 反对称的，传递的，那么称R为偏序关系，记为“, 称为偏序集。假设R，称“x小于等于y，记作x y。偏序关系例1 几个常见的偏序关系：(1)A上的小于等于关系，A=1,2,3,4,5,6：1 = xy，x，yA (2) A上的整除关系， A=1,2,3,4,5,6 ：2 x|y，x，yA(3)P(A)上的包

2、含关系， A=1,2,3 ： 3s1s2， s1，s2P(A)(4)任务集S=T1,T2, . , Tn 上的关系R4=|Ti=Tj或Ti必须在Tj之前完成偏序关系关于例1(4)的一个举例：如完成室内闪光拍照的任务，任务集T包括任务：1、翻开镜头盖；2、照相机调焦；3、翻开闪光灯；4、按下快门按钮。在T上定义关系R：R假设i=j或者任务i必须在任务j之前完成。那么R=,偏序关系定义 设R 为非空集合A上的偏序关系, x, yA,那么 x与y可比 x yy x 定义 设R 为非空集合A上的偏序关系, x, yA, 那么 y盖住x xy 且不存在 zA 使得 xzyHasse哈斯图例2 设A=2,

3、3,6,12,24,36，“是A上的整除关系R，画出其关系图。 关系图236123624236123624简化的关系图Hasse图Hasse图简化的关系图Hasse图哈斯图 (1)自反性：每个顶点都有自回路，省去。 (2)反对称性：两个顶点间只可能有一个箭头，从小到 大(或从低到高)安置顶点，可省略箭头。 (3)传递性：由于有，R，那么R， 故只画，对应的边，省略边。Hasse图Hasse图的画法“层次与“连线(1)极小元放在第一层最底层。(2)假设第n层已放好，那么第n+1层的元素满足至少能盖住第n层的一个元素。层次(3)假设y盖住x ，那么x，y之间连线。连线注：哈斯图表达了偏序集中元素间

4、的“大小和“层次关系。Hasse图例3 画出例1中各关系的Hasse图： A1,2,3,4,5,6,7,8,9, Ba,b,c, S =1, 2, 3, 4 1 x y，x，yA 2 x | y，x，yA 3s1s2， s1，s2P(B) R 4=|Ti=Tj或Ti必须在Tj之前完成且Ti,Tj S =,Hasse图 1 2全序集Hasse图1243 3 4全序关系定义 全序关系任意两个元素都可比 设是一个偏序集，假设对任意x, yA，总有x y或y x，二者必居其一，那么称 “为全序关系，或者线序关系。称为全序集，或者线序集，或者链。偏序集中的重要元素设偏序集, B A，b表示相应的特殊元素

5、，B的极小元B中没有比b 小的元素 bB 且 x(x B x b)B的最小元B中所有的元素都比b大 bB 且 x(xBb x)极大元和最大元类似定义。 注：上述元素都在B中寻找。偏序集中的重要元素设偏序集, B A，b表示相应的特殊元素，B的上界B中所有的元素都比b小 bA 且 x(xBx b) B的上确界 上确界B的上界的最小元下界和下确界类似定义。 注：上述元素都在A中寻找。 偏序集中的重要元素例4 设偏序集，求A的极小元、极大元、最小元、最大元。设B b,c,d , 求B的下界、上界、下确界、上确界. 解：极小元：a, b, c, g； 极大元：a, f, h；没有最小元与最大元.B的下

6、界和下确界都不存在；上界有 d 和 f, 上确界为 d. 偏序集中的重要元素性质：(1) 对于有穷集，极小元和极大元一定存在，可能存在多个。(2) 最小元和最大元不一定存在，假设存在一定惟一。(3) 最小元一定是极小元；最大元一定是极大元。 (4) 孤立结点既是极小元，也是极大元。(5) 下界、上界、下确界、上确界不一定存在，存在不一定唯一。(6) 下确界、上确界假设存在，那么惟一。偏序集中的重要元素练习 的Hasse图如下所示，讨论当B取相应集合时，其最大元，最小元，极大元，极小元，上界，下界，上确界，下确界。 B1=a,b, B2=a,b,c, B3=a,b,c,d, B4=b,c,d,f, B5=a,c,f, i abcdefghiB极小元极大元最小元最大元a,ba,b,ca,ba,b无无a,bc无ca,b,c,db,c,d,fa,c,f,ia,bc,d无bfbaia无fiabcdefghi 无b