《半序偏序关系》PPT课件.ppt

《《半序偏序关系》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《半序偏序关系》PPT课件.ppt（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章 第六节第六节半序（偏序）关系半序（偏序）关系 1第二章第二章定定义义1设设R为为非非空空集集合合A上上的的关关系系。如如果果R是是自自反反的的、反反对对称称的的和和传传递的，则称递的，则称R为为A上的半序上的半序(偏序偏序)关系，记为关系，记为。对一个偏序关系对一个偏序关系，如果，如果 ，则记为，则记为x y。注：注：1.集合集合A上的恒等关系上的恒等关系IA是是A上的偏序关系，但上的偏序关系，但空关系和空关系和全全域关系域关系EA一般不是一般不是A上的偏序关系。上的偏序关系。2.实数域上的小于等于关系（大于等于关系），自然数域上实数域上的小于等于关系（大于等于关系），自然数域上

2、的整除关系，集合的包含关系等都是偏序关系。的整除关系，集合的包含关系等都是偏序关系。一一.偏序关系与偏序集偏序关系与偏序集 2第二章第二章注注：在具有偏序关系的集合：在具有偏序关系的集合A中任二元素中任二元素x和和y 之间必有下列四之间必有下列四种情形之一：种情形之一：x y，y x，x=y，x与与y不可比。不可比。例例设设A=1,2,3(1)是是A上的整除关系，则：上的整除关系，则：1 2,1 3,11,22,33，2和和3不可比；不可比；(2)(2)是是A上的大于等于关系，则上的大于等于关系，则:2 1,3 1,3 2,11,22，33。定义定义定义定义2 2 设设设设R R为非空集合为非

3、空集合为非空集合为非空集合A A上的偏序关系，定义上的偏序关系，定义上的偏序关系，定义上的偏序关系，定义(1)x,y A,x y当且仅当当且仅当x y且且xy(2)x,y A,x与与y可比当且仅当可比当且仅当x y或或y x 3第二章第二章定义定义3设设R为非空集合为非空集合A上的偏序关系，如果上的偏序关系，如果 x,y A,x与与y都是可比的都是可比的,则称则称R为为A上的全序关系。上的全序关系。例如例如大于等于关系（小于等于关系）是全序集，但整除关系一般不是全大于等于关系（小于等于关系）是全序集，但整除关系一般不是全序集。序集。定义定义4带有某种指定的偏序关系带有某种指定的偏序关系 的集合

4、的集合A称为偏序集，记为称为偏序集，记为.例如例如整数集整数集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第二章第二章 利用偏序关系的自反性、反对称性和传递性可简化偏序关系的关系图，利用偏序关系的自反性、反对称性和传递性可简化偏序关

5、系的关系图，得到偏序集的哈斯图。得到偏序集的哈斯图。设有偏序集设有偏序集,其哈斯图的画法如下：其哈斯图的画法如下：(1)以以A的元素作为顶点，适当排列各顶点的顺序的元素作为顶点，适当排列各顶点的顺序,使得对使得对 x,y A，若若x y,则将则将x画在画在y的下方。的下方。(2)对对A中两个不同元素中两个不同元素x和和y,如果如果y覆盖覆盖x,则用一条线段连接则用一条线段连接x和和y.例例画出偏序集画出偏序集1,2,3,9,R整除整除和和的哈斯图的哈斯图.二二.哈斯图哈斯图解：解：解：解：它们的哈斯图分别为图它们的哈斯图分别为图它们的哈斯图分别为图它们的哈斯图分别为图A A、图、图、图、图B

6、B表示如下：表示如下：表示如下：表示如下：847236951图图Aa,ba,b,cabb,cca,c 图图B 5第二章第二章例例已知偏序集已知偏序集的哈斯图如下：求集合的哈斯图如下：求集合A和关系和关系R的表达式。的表达式。aedfhgbc解解:A=a,b,c,d,e,f,g,h,R=,IA.6第二章第二章定义定义6设设为偏序集，为偏序集，B A.存在存在y B,使得使得(1)x(x By x)成立，则称成立，则称 y是是B的的最小元最小元；(2)x(x Bx y)成立，则称成立，则称y是是B的的最大元最大元；(3)x(x Bx yx=y)成立，则称成立，则称y是是B的的极小元极小元；(4)x

7、(x By xx=y)成立，则称成立，则称y是是B的的极大元极大元；注：注：极大极大(极小极小)元未必是最大元未必是最大(最小最小)元。极大元。极大(极小极小)元未必与元未必与B中任中任何元素都可比；何元素都可比；(2)对有限集对有限集B，极大极大(极小极小)元一定存在，但最大元一定存在，但最大(最小最小)元不一定存在元不一定存在;(3)最大最大(最小最小)元如果存在，必定是唯一的元如果存在，必定是唯一的;而极大而极大(极小极小)元一般不元一般不唯一。但如果唯一。但如果B中只有一个极大中只有一个极大(极小极小)元元,则它一定是则它一定是B的最大的最大(最最小小)元。元。三三.偏序集中的特殊元素

8、偏序集中的特殊元素 7第二章第二章解解：极大元：极大元：a,f,h;极小元极小元:a,b,c,g;无最大元和最小元。无最大元和最小元。例例例例 求上例中求上例中求上例中求上例中A A的极大元、极小元、最大元、最小元，的极大元、极小元、最大元、最小元，的极大元、极小元、最大元、最小元，的极大元、极小元、最大元、最小元，8第二章第二章定义定义定义定义7 7 设设设设A,为偏序集，为偏序集，为偏序集，为偏序集，B B A.A.(1)若存在若存在若存在若存在y y A A,使得使得使得使得 x(x Bx y)成立成立,则称则称y为为B的上界的上界;(2)若存在若存在若存在若存在y y A A,使得使得

9、使得使得 x(x By x)成立，则称成立，则称y为为B的下界；的下界；(3)令令Cy|y为为B的上界的上界，则称，则称C的最小元为的最小元为B的最小上界或上确界；的最小上界或上确界；(4)令令Dy|y为为B的下界的下界，则称，则称D的最大元为的最大元为B的最大下界或下确界的最大下界或下确界.注：注：1.B的最大元的最大元(最小元最小元)必定是必定是B的上界的上界(下界下界)，也是，也是B的上确界的上确界(下确界下确界)。2.B的上界和上确界都未必是的上界和上确界都未必是B的最大元，因它们可能不在的最大元，因它们可能不在B中。同理，中。同理，下界和下确也未必是下界和下确也未必是B的最小元。的最

10、小元。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,|)上，半序关系上，半序关系|是整除关系。是整除关系。取取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,3B412,36,602122122 12第二章第二章 作业：作业：P P5252 25,31 25,31 13