2.6 半序(偏序)关系

《2.6 半序(偏序)关系》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六节半序（偏序）关系1定义1设R为非空集合A上的关系。如果R是自反的、反对称的和传递的，则称R为A上的半序(偏序)关系，记为≼。对一个偏序关系≼，如果≼，则记为x≼y。注：1.集合A上的恒等关系IA是A上的偏序关系，但空关系和全域关系EA一般不是A上的偏序关系。2.实数域上的小于等于关系（大于等于关系），自然数域上的整除关系，集合的包含关系等都是偏序关系。一.偏序关系与偏序集2注：在具有偏序关系的集合A中任二元素x和y之间必有下列四种情形之一：x≺y，y≺x，x=y，x与y不可比。例设A={1,2,3}≼

2、是A上的整除关系，则：1≺2,1≺3,1＝1,2＝2,3＝3，2和3不可比；(2)≼是A上的大于等于关系，则:2≺1,3≺1,3≺2,1＝1,2＝2，3＝3。定义2设R为非空集合A上的偏序关系，定义(1)x,yA,x≺y当且仅当x≼y且x≠y(2)x,yA,x与y可比当且仅当x≼y或y≼x3定义3设R为非空集合A上的偏序关系，如果x,yA,x与y都是可比的,则称R为A上的全序关系。例如大于等于关系（小于等于关系）是全序集，但整除关系一般不是全序集。定义4带有某种指定的偏序关系≼的集合A称为偏序集，记为

3、≼>.例如整数集Z和数的小于等于关系≤构成偏序集;集合A的幂集P(A)和集合的包含关系构成偏序集.定义5设为偏序集，x,yA,如果x≺y且不存在zA,使得x≺z≺y,则称y覆盖x。例如A={1,2,4,6}上的整除关系，有2覆盖1，4和6都覆盖2，但4不覆盖1,6不覆盖4。4利用偏序关系的自反性、反对称性和传递性可简化偏序关系的关系图，得到偏序集的哈斯图。设有偏序集,其哈斯图的画法如下：(1)以A的元素作为顶点，适当排列各顶点的顺序,使得对x,yA，若x≺y,则

4、将x画在y的下方。(2)对A中两个不同元素x和y,如果y覆盖x,则用一条线段连接x和y.例画出偏序集<{1,2,3,…,9},R整除}和的哈斯图.二.哈斯图解：它们的哈斯图分别为图A、图B表示如下：847236951图A{a,b}{a,b,c}{a}{b}{b,c}{c}{a,c}图B5例已知偏序集的哈斯图如下：求集合A和关系R的表达式。aedfhgbc解:A={a,b,c,d,e,f,g,h},R={,,,,,,

5、f>,,}∪IA.6定义6设为偏序集，BA.存在yB,使得(1)x(xB→y≼x)成立，则称y是B的最小元；(2)x(xB→x≼y)成立，则称y是B的最大元；(3)x(xB∧x≼y→x=y)成立，则称y是B的极小元；(4)x(xB∧y≼x→x=y)成立，则称y是B的极大元；注：极大(极小)元未必是最大(最小)元。极大(极小)元未必与B中任何元素都可比；(2)对有限集B，极大(极小)元一定存在，但最大(最小)元不一定存在;(3)最大(最小)元如果存在，必定是唯一的;而极大

6、(极小)元一般不唯一。但如果B中只有一个极大(极小)元,则它一定是B的最大(最小)元。三.偏序集中的特殊元素7解：极大元：a,f,h;极小元:a,b,c,g;无最大元和最小元。例求上例中A的极大元、极小元、最大元、最小元，8定义7设为偏序集，BA.(1)若存在yA,使得x(xB→x≼y)成立,则称y为B的上界;(2)若存在yA,使得x(xB→y≼x)成立，则称y为B的下界；(3)令C＝{y

7、y为B的上界}，则称C的最小元为B的最小上界或上确界；(4)令D＝{y

8、y为B的下界}，则称D的最大元为

9、B的最大下界或下确界.注：B的最大元(最小元)必定是B的上界(下界)，也是B的上确界(下确界)。2.B的上界和上确界都未必是B的最大元，因它们可能不在B中。同理，下界和下确也未必是B的最小元。3.B的上界、上确界、下界、下确界都可能不存在。但如果上确界(下确界)存在，则它是唯一的。9例考虑下图中的偏序集.令B={b,c,d},试讨论B的上(下)界，最大下界，最小上界等。解析：(1)则B的下界和最大下界都不存在;(2)上界有d和f,最小上界为d.10例设A={2,3,4,6,7,8,12,36,60},在半序集(A,

10、)

11、上，半序关系

12、是整除关系。取B1={7,8},B2={8,12},B3={2,3},B4={2,4,12}，则Bi(i=1,2,3,4)集合上的上(下)界,上(下)确界，极大(下)元？作出哈斯图！11集合上界下界上确界下确界极大元极小元B1无无无无7,87,8B2无4,2无48,128,12B36,12,36,60无6无2,32,