(1.5.6)--ch3—第八讲离散数学离散数学.pdf

《(1.5.6)--ch3—第八讲离散数学离散数学.pdf》由会员分享，可在线阅读，更多相关《(1.5.6)--ch3—第八讲离散数学离散数学.pdf（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学离散数学(Discrete Mathematics)3-12 序关系序关系(Ordered Relations)1 偏序关系的定义偏序关系的定义(Partially Ordered Relations)设设A是一个集合是一个集合,如果如果 A上的一个关系上的一个关系R满足满足自反性、自反性、定义定义1 例例 实数集实数集R上的“上的“”关系是一个偏序关系”关系是一个偏序关系.例例 全集合全集合E的幂集的幂集P(E)上的“上的“”关系也是一个偏序关系”关系也是一个偏序关系.序偶序偶 称称为为偏序集偏序集.,A反对称性和传递性反对称性和传递性,则称则称R为为A上的一个上的一个偏序关系偏序关

2、系,记作记作 .例例1.证明实数集上的小于等于关系“证明实数集上的小于等于关系“”是偏序关系”是偏序关系.证明证明:(1)对任意的实数对任意的实数a R,有有a a,故故关系“关系“”是自反的”是自反的;(2)对任意的实数对任意的实数a,b R,如果如果a b,且且 b a,则必有则必有a=b,故故关系“关系“”是反对称的”是反对称的;(3)对任意的实数对任意的实数a,b,c R,如果如果a b,且且b c,则必有则必有:a c,故故关系“关系“”是传递的”是传递的;由由(1),(2),(3)知知关系“关系“”是一个偏序关系”是一个偏序关系.例例2.设设 A=2,3,6,8,令令“”=|x整除

3、整除y,验证关系验证关系“”是偏序关系是偏序关系.解解 10110110,00100001M 2 8 3 6“”=,从关系矩阵和关系图中可看出从关系矩阵和关系图中可看出“”是自反的”是自反的,反对称的反对称的 和可传递的和可传递的.COVA=|a,bA且且b盖住盖住a 定义定义2 设设 为偏序集为偏序集,对对任意任意a,b A,A如果如果a b或或b a成立成立,则称则称a与与b是可比的是可比的;如果如果a b,ab且且不存在其他元素不存在其他元素c A满足满足a c,c b,则称则称元素元素b盖住元素盖住元素a.并且记并且记 例例3.集合集合1,2,3,4,5上的整除关系是偏序关系上的整除关

4、系是偏序关系 1与任何数都可比与任何数都可比,3与与4不可比不可比.2与与4可比可比,2盖住盖住1,但但4不盖住不盖住1(124).COVA=,.4盖住盖住2,例例4.设设A是正整数是正整数 m=12的因子的集合的因子的集合,并设“并设“”为整”为整除关系除关系,求求COVA 解解 m=12其因子的集合为其因子的集合为 A=1,2,3,4,6,12,COVA=,(1)用小圆圈代表元素用小圆圈代表元素;(3)若若b盖住盖住a,就用一条线段连接就用一条线段连接a与与b.由于所有边的箭头向由于所有边的箭头向 上上,故省去箭头故省去箭头.作图规则如下作图规则如下:(2)若元素若元素ab且且a b时时,

5、则结点则结点a画在结点画在结点b的下方的下方.给定一个偏序集合给定一个偏序集合,它的盖住关系是唯一的它的盖住关系是唯一的,而且而且 知道一个偏序集合的盖住关系知道一个偏序集合的盖住关系,此偏序集合也是唯一确定的此偏序集合也是唯一确定的,所以可用盖住关系的关系图来表示偏序集合所以可用盖住关系的关系图来表示偏序集合(偏序关系偏序关系),此图此图 称为一个偏序集合的称为一个偏序集合的哈斯图哈斯图.2.偏序关系的哈斯图偏序关系的哈斯图 例例5 画出偏序集画出偏序集和和的哈斯图的哈斯图 例例6 设设A=2,3,6,12,24,36,A上的整除关系是一偏序关系上的整除关系是一偏序关系,画出其哈斯图画出其哈

6、斯图.abfcdegh,a ca da eb cb d ,Ab ec ed ef gI ,A求集合求集合A的偏序关系的偏序关系 例例7.已知偏序集已知偏序集 的哈斯图的哈斯图(右图右图),解解:,Aa b c d e f g h 3.偏序集中特殊位置的元素偏序集中特殊位置的元素 定义定义3.设设 为一偏序集为一偏序集,B A,A(1)若对于若对于,bB 如果如果 B 中中没有任何元素没有任何元素 x,满足满足 bx 且且,bx则称则称 b 是是 B的的极大元极大元.(2)若对于若对于,bB 如果如果 B 中中没有任何元素没有任何元素 x,满足满足 bx 且且,xb则称则称 b 是是 B的的极小

7、元极小元.(3)若有某个元素若有某个元素,bB 对于对于 B 中中每一个元素每一个元素 x,有有,xb则称则称 b 是是 B的的最大元最大元.(4)若有某个元素若有某个元素,bB 对于对于 B 中中每一个元素每一个元素 x,有有,bx则称则称 b 是是 B的的最小元最小元.注意注意:最小最小(大大)元与极小元与极小(大大)元的区别与联系元的区别与联系.最大最大(小小)元必是极大元必是极大(小小)元元,反之不然反之不然.最小最小(大大)元是元是B中最小中最小(大大)的元素的元素,它与它与B中其它元素都中其它元素都可比可比.极小极小(大大)元不一定与元不一定与B中元素都可比中元素都可比,只要没有比

8、它小只要没有比它小(大大)的元素的元素,它就是极小它就是极小(大大)元元.但但最小最小(大大)元不一定存在元不一定存在.若存在若存在,则它一定是唯一的则它一定是唯一的.则必是唯一的则必是唯一的.设设 为一偏序集为一偏序集,B A,A定理定理12.1 若若B有最大有最大(最小最小)元元,对于有穷集对于有穷集B,极小极小(大大)元一定存在元一定存在,而且还可能有多个而且还可能有多个.例例8.设偏序集设偏序集如下图所示如下图所示,求求A的极小元的极小元,最小元最小元,极大元极大元,最大元最大元.解解 极小元极小元:a,b,c,g.极大元极大元:a,f,h.没有最小元与最大元没有最小元与最大元.由此例

9、可知由此例可知,哈斯图中的孤立顶点哈斯图中的孤立顶点 既是极小元也是极大元既是极小元也是极大元.极大元即是其哈斯图中最顶层元素极大元即是其哈斯图中最顶层元素,它们处在哈斯图中它们处在哈斯图中 最底层元素最底层元素,不同的极大不同的极大(小小)元之间不可比元之间不可比,其极小元是哈斯图中其极小元是哈斯图中 的同一个层次的同一个层次.例例9.设设A=a,b,c,对于偏序集对于偏序集 集合集合 极大元极大元 极小元极小元 最大元最大元 最小元最小元 P(A)a,b,c a,a,b a,b,c a,b,c a,b a a 无无 无无 a,b,c a,b,c a,b 定义定义4.设设 为一偏序集为一偏序

10、集,B A,A(1)如有如有,aA 且对于且对于 B 中中任意元素任意元素 x,都满足都满足,xa则称则称 a为子集为子集 B的的上界上界.(2)如有如有,aA 且对于且对于 B 中中任意元素任意元素 x,都满足都满足,ax则称则称 a为子集为子集 B的的下界下界.(3)设设a为为B的任一上界的任一上界,若对于若对于 B 的的所有上界所有上界 y,有有,ay则称则称 a 是是 B的的最小上界或上确界最小上界或上确界,记作记作LUB B(4)设设a为为B的任一下界的任一下界,若对于若对于 B 的的所有下界所有下界 z,有有,za则称则称 a 是是 B的的最大下界或下确界最大下界或下确界,记作记作

11、GLB B 由上面定义可知由上面定义可知:(1)B 的最小元一定是的最小元一定是B的下界的下界,同时也是同时也是B的最大下界的最大下界;(2)B的最大元一定是的最大元一定是B的上界的上界,同时也是同时也是B的最小上界的最小上界.(3)反过来不一定正确反过来不一定正确.B的下界不一定是的下界不一定是B的最小元的最小元,因为它可能不是因为它可能不是B中的元中的元素素,B的上界也不一定是的上界也不一定是B的最大元的最大元.(4)B的上界的上界,下界下界,最小上界最小上界,最大下界都可能不存在最大下界都可能不存在.如果存在如果存在,最小上界与最大下界是唯一的最小上界与最大下界是唯一的.,a b c,a

12、 b,a c,b c a b c(1)例例10.(),P A R上、下界上、下界,上、下确界上、下确界.,偏序集偏序集 求求 B 的最大、小元的最大、小元,极大、小元极大、小元,解解:B的最大元的最大元:无无;极大元极大元:极小元极小元:上界上界:下界下界:上确界上确界:下确界下确界:A=a,b,c,B=a,b,c,c 最小元最小元:无无;a,b,c;a,c;a,b,c;a,b,c;(2)解解:B的最大元的最大元:极大元：极大元：极小元：极小元：上界：上界：下界：下界：上确界：上确界：下确界：下确界：B=a,b,a,b 最小元：无最小元：无;a,b;a,b;a,b,a,b;a,b;a,b,c;

13、例例10.(),P A R上、下界上、下界,上、下确界上、下确界.,偏序集偏序集 A=a,b,c,求求 B 的最大、小元的最大、小元,极大、小元极大、小元,例例11.设设 A=2,3,4,6,9,12,18上的整除关系上的整除关系DA的哈斯图如下试的哈斯图如下试求求 B1=2,4.B2=4,6,9,B3=12,18的上界、下界、上确界、的上界、下界、上确界、下确界下确界.12。18。4。6 。9 2。3 B1的上界的上界:上确界上确界:4;下下 界界:2;B2无上界和下界无上界和下界;B3下界为下界为6,3,2;下确界下确界:6;无上界和上确界无上界和上确界.解解:4、12;无上确界和下确界无

14、上确界和下确界.下确界下确界:2;定义定义5 设设 是一个偏序集合是一个偏序集合,在在 A的一个子集中的一个子集中,A如果每如果每两个元素都是有关系两个元素都是有关系的的,则称这个子集为则称这个子集为链链.如果如果每两个元素都是无关每两个元素都是无关的的,则称这个子集为则称这个子集为反链反链.约定约定:若若A的子集只有单个元素的子集只有单个元素,则这个子集既是链又是反链则这个子集既是链又是反链.4.全序关系全序关系 例例7.设设A=a,b,c,d,e 上的二元关系为上的二元关系为 R=,验证验证:为偏序集为偏序集,画出哈斯图画出哈斯图,举出链及反链的例子举出链及反链的例子.解解:1111101

15、101001000001100001RM 主对角线元素都为主对角线元素都为1,故故R是自反的是自反的;rij与与rji不同时为不同时为1,故故R是反对称的是反对称的;从关系图中可得出从关系图中可得出R是可传递的是可传递的.故故R是一个偏序关系是一个偏序关系.a b c d e 例例7.设设A=a,b,c,d,e 上的二元关系为上的二元关系为 R=,验证验证:为偏序集为偏序集,画出哈斯图画出哈斯图,举出链及反链的例子举出链及反链的例子.哈斯图哈斯图 COVA=,解解:a b c d e a,b,c,e,a,b,c,b,c,a,a,d,e 等都是链等都是链.b,d,c,d,a等都是反链等都是反链.

16、定义定义6.,A在偏序集在偏序集 中中,如果如果A本身是一个链本身是一个链,则称则称,A为为全序集合或线序集合全序集合或线序集合,称关系称关系 为为全序关系或线序关系全序关系或线序关系.,A注注:全序集全序集 中任意两个元素中任意两个元素x,y,(1)实数集实数集R上的“小于等于”关系“上的“小于等于”关系“”是全序关系是全序关系.(2)N上的整除关系就仅是一个偏序而上的整除关系就仅是一个偏序而不是不是全序全序.如如.例例9.给定给定P=,a,a,b,a,b,c上的包含关系上的包含关系,证明证明:是全序关系是全序关系.解解:(1)是偏序关系是偏序关系(2)a a,b a,b,c 故故是全序关系

17、是全序关系.或有或有x y或有或有y x 成立成立.定义定义7.任一偏序集合任一偏序集合,若它的每一个非空子集存在最小元素若它的每一个非空子集存在最小元素,则称这种偏序集为则称这种偏序集为良序的良序的.(1)正整数集正整数集N上的小于等于关系“上的小于等于关系“”是良序关系”是良序关系.(2)In=1,2,n上的小于等于关系“上的小于等于关系“”是良序关系”是良序关系.(3)整数集整数集Z和实数集和实数集R上的小于等于关系“上的小于等于关系“”不是不是良序关良序关系系(因为因为Z或或R本身无最小元本身无最小元).例如例如 定理定理12.2 良序集合一定是全序集合良序集合一定是全序集合.注意注意:全序集合不一定是良序集合全序集合不一定是良序集合.定理定理12.3 有限有限的全的全序集合一定是良序集合序集合一定是良序集合.本书介绍了偏序关系及几种特殊的偏序。本书介绍了偏序关系及几种特殊的偏序。重点掌握重点掌握:偏序的概念，哈斯图的画法偏序的概念，哈斯图的画法 及偏序关系中特异位置元素。及偏序关系中特异位置元素。小结小结