二元关系 4.5 偏序关系.ppt

《二元关系 4.5 偏序关系.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1离散数学DiscreteMathematics主讲：陈哲云青岛理工大学计算机工程学院2013.09第4章二元关系二元关系4.1二元关系基本概念(重点)4.2关系的运算4.3关系的性质(重点)4.4关系的闭包4.5等价关系和偏序关系(重点及难点)4.6函数的基本概念偏序关系偏序关系Hasse图（重点）重要元素（重点）拓扑排序偏序关系定义偏序关系：设A上的二元关系R,如果R是自反的,反对称的，传递的，则称R为偏序关系，记为“≼”,称为偏序集。若∈R，称“x小于等于y”，记作x≼

2、y。偏序关系例1几个常见的偏序关系：(1)A上的小于等于关系，A={1,2,3,4,5,6}：Ｒ1={｜x≤y，x，y∈A}(2)A上的整除关系，A={1,2,3,4,5,6}：Ｒ2＝{｜x

3、y，x，y∈A}(3)P(A)上的包含关系，A={1,2,3}：Ｒ3＝{｜s1s2，s1，s2∈P(A)}(4)任务集S={T1,T2,....,Tn}上的关系R4={

4、Ti=Tj或Ti必须在Tj之前完成}≼≼≼≼偏序关系关于例1(4)的一个举例：如完成室内

5、闪光拍照的任务，任务集T包括任务：1、打开镜头盖；2、照相机调焦；3、打开闪光灯；4、按下快门按钮。在T上定义关系R：∈R如果i=j或者任务i必须在任务j之前完成。则R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<1,4>,<2,4>,<3,4>}偏序关系定义设R为非空集合A上的偏序关系,x,y∈A,则x与y可比x≼y∨y≼x定义设R为非空集合A上的偏序关系,x,y∈A,则y盖住xx≺y且不存在z∈A使得x≺z≺yHasse（哈斯）图例2设A={2,3,6,1

6、2,24,36}，“≼”是A上的整除关系R，画出其关系图。关系图236123624236123624简化的关系图——Hasse图Hasse图简化的关系图——Hasse图（哈斯图）(1)自反性：每个顶点都有自回路，省去。(2)反对称性：两个顶点间只可能有一个箭头，从小到大(或从低到高)安置顶点，可省略箭头。(3)传递性：由于有，∈R，则∈R，故只画，对应的边，省略边。Hasse图Hasse图的画法——“层次”与“连线”(1)极小元放在第一

7、层（最底层）。(2)若第n层已放好，则第n+1层的元素满足至少能盖住第n层的一个元素。（层次）(3)若y盖住x，则x，y之间连线。（连线）注：哈斯图体现了偏序集中元素间的“大小”和“层次”关系。Hasse图例3画出例1中各关系的Hasse图：A＝{1,2,3,4,5,6,7,8,9},B＝{a,b,c},S={1,2,3,4}Ｒ1＝｛｜x≤y，x，y∈A｝Ｒ2＝｛｜x

8、y，x，y∈A｝Ｒ3＝｛｜s1s2，s1，s2∈P(B)｝R4={

9、Ti=Tj

10、或Ti必须在Tj之前完成且Ti,Tj∈S}={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<1,4>,<2,4>,<3,4>}Hasse图Ｒ1Ｒ2——全序集Hasse图1243Ｒ3Ｒ4全序关系定义全序关系——任意两个元素都可比设是一个偏序集，若对任意x,y∈A，总有x≼y或y≼x，二者必居其一，则称“”为全序关系，或者线序关系。称为全序集，或者线序集，或者链。偏序集中的重要元素设偏序集,BA，b表示相应的特殊元素，B的极小元——B中没有比b小的元素

11、b∈B且x(x∈Bx≺b)B的最小元——B中所有的元素都比b大b∈B且x(x∈B→b≼x)极大元和最大元类似定义。注：上述元素都在B中寻找。偏序集中的重要元素设偏序集,BA，b表示相应的特殊元素，B的上界—B中所有的元素都比b小b∈A且x(x∈B→x≼b)B的上确界上确界——B的上界的最小元下界和下确界类似定义。注：上述元素都在A中寻找。偏序集中的重要元素例4设偏序集，求A的极小元、极大元、最小元、最大元。设B＝{b,c,d},求B的下界、上界、下确界、上确界.解

12、：极小元：a,b,c,g；极大元：a,f,h；没有最小元与最大元.B的下界和下确界都不存在；上界有d和f,上确界为d.偏序集中的重要元素性质：(1)对于有穷集，极小元和极大元一定存在，可能存在多个。(2)最小元和最大元不一定存在，如果存在一定惟一。(3)最小元一定是极小元；最大元一定是极大元。(4)孤立结点既是极小元，也是极大元。(5)下界、上界、下确界、上确界不一定存在，存在不一定唯一。(6)下确界、上确界如果存在，则惟一。偏序集中的重要元素练习的Hasse图如下所示，讨论当B取相