二元关系

第七章二元关系殷绪成电子邮件[e-mail](邮件Title：[离散数学]…)电话[phone](Office)课程公用邮箱用户名:dm.ustb;密码:ustb2012.基本要求学习要求知识体系：基本概念、基本计算、基本证明方法注意能力的培养：获取知识的能力----读书分析问题解决问题的能力----解题理论联系实际的能力----联系其它课程或研究课题课堂纪律认真听课；手机关机或静音，禁止设为闹铃和震动；不得旷课、迟到和早退。基本要求（续）作业按时做、交作业；不准抄袭；不要突击。收发作业时间（课代表）每周一课间及课后。相关知识复习定义7.3若一个集合满足以下条件之一:(1).集合非空,且它的元素都是有序对(2).集合是空集则称该集合为二元关系(BinaryRelation),记作R,可简称为关系.(1)若x(xAx,xR),则称R在A上是自反的;(2)若x(xAx,xR),则称R在A上是反自反的.关系的性质主要有:自反性(Reflexive),对称性(Symmetric)和传递性(Transitive).除此之外,还有:反自反性(Anti-Reflexive)和反对称性(Anti-Symmetric).定义7.11设R为A上的关系,A上的全域关系EA和恒等关系IA都是A上的自反关系小于等于关系LA,整除关系DB分别是A和B上的自反关系包含关系是给定集合簇A上的自反关系小于关系和真包含关系都是给定集合或集合簇上的反自反关系相关知识复习定义7.12设R为A上的关系,(2)称R在A上是反对称的关系,若关系R满足条件:xy(x,yA∧x,yR∧y,xRx=y)(1)称R在A上是对称的关系,若关系R满足条件:xy(x,yA∧x,yRy,xR)A上的全域关系EA,恒等关系IA和空关系都是A上对称的关系恒等关系IA和空关系都是A上反对称的关系全域关系EA一般不是A上的反对称关系,除非A为单元集或空集相关知识复习定义7.13设R为A上的关系,若xyz(x,y,zA∧xRy∧yRzx,zR)称R为A上传递的关系.A上的全域关系EA,恒等关系IA和空关系都是A上的传递关系小于等于关系,整除关系,包含关系,小于关系和真包含关系是相应集合上的传递关系相关知识复习下面介绍另一种重要的关系——偏序关系.定义7.19设R为非空集合A上的关系.如果R是自反的、反对称的和传递的,则称R为A上的偏序关系,记作.设为偏序关系,如果x,y,则记作xy,读作“小于或等于”.注意:这里的“小于或等于”不是指数的大小,而是在偏序关系中的顺序性.x“小于或等于”y的含义是:依照这个序,x排在y的前边或者x就是y.不同偏序的定义有不同的序解释.例如整除关系是偏序关系,36的含义是3整除6;大于或等于关系也是偏序关系,针对这个关系写54是说大于或等于关系中5排在4的前边,也就是5比4大.7.7偏序关系定义7.20设R为非空集合A上的偏序关系,定义(1)x,yA,xyxy∧xy;(2)x,yA,x与y可比xy∨yx.其中:xy读作x“小于”y.这里所说的“小于”是指在偏序中x排在y的前边.有以上两个定义可知:在具有偏序关系的集合A中任取两个元素x和y,可能有下述几种情况发生:xy(或yx),x=y,x与y不是可比的例如:A={1,2,3},是A上的整除关系,则有:12,13,1=1,2=2,3=3,2和3不可比.7.7偏序关系定义7.21设R为非空集合A上的偏序关系,如果x,yA,x与y都是可比的,则称R为A上的全序关系(或线序关系).例如:数集上的小于等于关系是全序关系,因为任何两个数总是可比大小的.一般来说,整除关系不是全序关系.如:集合{1,2,3}上的整除关系就不是全序关系,因为2和3不可整除.定义7.22集合A和A上的偏序关系一起叫做偏序集,记作A,.例如:整数集合Z和数的小于等于关系构成偏序集Z,,集合A的幂集P(A)和包含关系R构成偏序集P(A),R.7.7偏序关系利用偏序关系的自反性、反对称性和传递性可简化偏序关系的关系图,该关系图称为哈斯图(HasseDiagram).为了说明哈斯图的画法,先定义偏序集中顶点之间的覆盖关系.定义7.23设A,为偏序集,x,yA,如果xy且不存在zA,使得:xzy,则称y覆盖x.例如:{1,2,4,6}集合上的整除关系,有2覆盖1,4和6都覆盖2.但,4不覆盖1,因为有124,6也不覆盖4,因为46不成立.7.7偏序关系在画偏序集A,的哈斯图时,首先适当排列顶点的顺序,使得:x,yA,若xy,则将x画在y的下方.对于A中的两个不同元素x和y,如果y覆盖x,就用一条线段连接x和y.例7.19画出偏序集{1,2,3,4,5,6,7,8,9},R整除和P({a,b,c}),R的哈斯图.解两个哈斯图如右图所示.7.7偏序关系例7.20已知偏序集A,R的哈斯图如下图,试求出集合A和关系R的表达式.A={a,b,c,d,e,f,g,h}R={b,d,b,e,b,f,c,d,c,e,c,f,d,f,e,f,g,h}∪IA解7.7偏序关系下面考虑偏序集中的一些特殊元素.定义7.24设A,为偏序集,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中最小的元素,它与B中其它元素都可比;极小元不一定与B中元素都可比,只要没有比它小的元素,它就是极小元.对于有穷集B,极小元一定存在,而且还可能有多个.最小元不一定存在,若存在,则它一定是唯一的.若B中只有一个极小元,则它一定是B的最小元.类似的,极大元与最大元也有这种区别.7.7偏序关系例7.21设偏序集A,如下图所示,求A的极小元,最小元,极大元,最大元.解极小元:a,b,c,g.极大元:a,f,h.没有最小元与最大元.由这个例子可以知道,哈斯图中的孤立顶点既是极小元也是极大元.7.7偏序关系A,R不存在最小元和最大元,因为n≥2.考察幂集P(X)的哈斯图:最底层的顶点是空集,记作第0层;第1层是单元集;第2层是二元子集;…第n-1层是X的n-1元子集;第n层(最高层)只有一个顶点X.例7.22设X为集合,A=P(X)-{}-{X},且A.若|X|=n,问:(1)偏序集A,R是否存在最大元？(2)偏序集A,R是否存在最小元？(3)偏序集A,R中极大元和极小元的一般形式是什么？并说明理由.解偏序集A,R与P(X),R相比,恰好缺少第0层与第n层.因此,A,R的极小元就是X的所有单元集{x}(xX),极大元恰好少一个元素X-{x}(xX).7.7偏序关系定义7.25设A,为偏序集,BA,yA.(1)若x(xB→xy)成立,则称y为B的上界;(2)若x(xB→yx)成立,则称y为B的下界;(3)令C={y|y为B的上界},则称C的最小元为B的最小上界或上确界;(4)令D={y|y为B的下界},则称D的最大元为B的最大下界或下确界;由上面定义可知:B的最小元一定是B的下界,同时也是B的最大下界;B的最大元一定是B的上界,同时也是B的最小上界.反过来不一定正确,B的下界不一定是B的最小元,因为它可能不是B中的元素,B的上界也不一定是B的最大元.B的上界,下界,最小上界,最大下界都可能不存在.如果存在,最小上界与最大下界是唯一的.7.7偏序关系考虑下图中的偏序集.令B={b,c,d},则B的下界和最大下界都不存在,上界有d和f,最小上界为d.7.7偏序关系课后作业(1)习题七第46,48题（第135页）.谢谢!