(精品)第3章二元关系

,第二级,第三级,第四级,第五级,第3章 二元关系,第3章 二元关系,3.1 基本概念,3.2 关系的合成,3.3 关系上的闭包运算,3.4 次序关系,3.5 等价关系和划分,3.1 基本概念,3.1.1 关系,关系的数学概念是建立在日常生活中关系的概念之上的.让我们先看两个例子,例1设,A,=,a,b,c,d,是某乒乓球队的男队员集合,B,=,e,f,g,是女队员集合.如果,A,和,B,元素之间有混双配对关系的是,a,和,g,d,和,e,.,我们可表达为:,R,=,a,g,d,e,这里,R,表示具有混双配对关系的序偶集合.所有可能具有混双配对关系的序偶 集合是:,A,B,=,x,y,|,x,A,y,B,=,a,e,a,f,a,g,b,e,b,f,b,g,c,e,c,f,c,g,d,e,d,f,d,g,例2设学生集合,A,1,=,a,b,c,d,选修课集合,A,2,=,日语,法语,成绩等级集合,A,3,=,甲,乙,丙.如果四人的选修内容及成绩如下:,a,日 乙,b,法 甲,c,日 丙,d,法 乙,我们可表达为,S,=,a,日,乙,b,法,甲,c,日,丙,d,法,乙,这里,S,表示学生和选修课及成绩间的关系,.,而可能出现的全部情况为,A,1,A,2,A,3,=,x,y,z,|,x,A,1,y,A,2,z,A,3,=,a,日,甲,a,日,乙,a,日,丙,a,法,甲,a,法,乙,=,a,法,丙,b,日,甲,b,日,乙,b,日,丙,b,法,甲,=,b,法,乙,b,法,丙,c,日,甲,c,日,乙,c,日,丙,=,c,法,甲,c,法,乙,c,法,丙,d,日,甲,d,日,乙,=,d,日,丙,d,法,甲,d,法,乙,d,法,丙,定义 3.11,(1),A,B,的子集叫做,A,到,B,的一个二元关系.,(2),A,1,A,2,A,n,(,n,1),的子集叫做,A,1,A,2,A,n,上的一个,n,元关系.,(3),的子集叫做,A,上的,n,元关系,从定义可看出,关系是一个集合,所有定义集合的方法,都可用来定义关系,例1,例2是列举法的例子一个谓词,P,(,x,1,x,2,x,n,),可以定义一个,n,元关系,R,:,R,=,x,1,x,2,x,n,|,P,(,x,1,x,2,x,n,),例如,实数,R,上的二元关系可定义如下:,=,x,y,|,x,R,y,R,x,y,反之,一个,n,元关系也可定义一个谓词:,P,(,x,1,x,2,x,n,)=,1(真),当,x,1,x,2,x,n,R,时,0(假),当,x,1,x,2,x,n,R,时,当,n,=1,时,R,=,x,|,P,(,x,),称为一元关系.它是一重组集合,表示论述域上具有性质,P,的元素集合,其意义与,R,=,x,|,P,(,x,),相同,仅记法不同而崐已例如,设,P,(,x,),表示“,x,是质数”,论述域是,N,则质数集合可表示为,x,P,(,x,),或,x,P,(,x,),关系也可归纳地定义.自然数上的小于关系可定义如下:,(1)(基础)0,1,(2)(归纳)如果,x,y,那么,(,i),x,y,+1,(ii),x,+1,y,+1,(3)(,极小性)对一切,x,y,N,x,y,当且仅当,x,y,是由有限次应用条款(1)和(2)构成,定义3.12设,R,是 的子集,如果,R,=,则称,R,为空关系,如果,则称,R,为全域关系.,现在定义关系相等的概念,在关系相等的概念中不仅需要,n,重组集合相等,还需其叉积扩集也相同.,定义3.13设,R,1,是 上的,n,元关系,R,2,是,上的,m,元关系.那么,R,1,=,R,2,当且仅当,n,=,m,且对一切,i,1,i,n,A,i,=,B,i,并且,R,1,和,R,2,是相等的有序,n,重组集合,3.1.2 二元关系,最重要的关系是二元关系.本章主要讨论二元关系,今后术语“关系”都指二元关系.若非二元关系将用“三元”或“,n,元”一类术语指出.,二元关系有自己专用的记法和若干新术语,设,A,=,x,1,x,2,x,7,B,=,y,1,y,2,y,6,R,=,x,3,y,1,x,3,y,2,x,4,y,4,x,6,y,2,A,到,B,的二元关系,R,可如图3.11那样形象地表示.,x,3,y,1,R,也可写成,x,3,Ry,1,称为中缀记法,读做,x,3,和,y,1,有关系,R,.,中缀记法常用来表示诸如“=”,“”,“”等关系,例如3,5,通常写作35.,图 3.11,A,叫做关系,R,的前域,B,叫做关系,R,的陪域,D,(,R,)=,x,y,(,x,y,R,),叫做关系,R,的定义域,R,(,R,)=,y,x,(,x,y,R,),叫做关系,R,的值域,关系是序偶的集合,对它可进行集合运算,运算结果定义一个新关系.设,R,和,S,是给定集合上的两个二元关系,则,R,S,R,S,R,-,S,等可分别定义如下:,x,(,R,S,),y,xRy,xSy,x,(,RS,),y,xRy,xSy,x,(,R-S,),y,xRy,x$y,x,(),y,xRy,例3平面上的几何图形是平面,R,2,的子集,也是一种关系.设(参看图3.1,2),R,1,=,x,y,x,y,R,2,x,2,+,y,2,9,R,2,=,x,y,x,y,R,2,1,x,3),(0,y,3),R,3,=,x,y,x,y,R,2,x,2,+,y,2,4,则,R,1,R,2,=,x,y,x,y,R,2,(,x,2,+,y,2,9,(1,x,3,0,y,3),R,1,R,3,=,x,y,x,y,R,2,(,x,2,+,y,2,9,x,2,+,y,2,4),R,1,-,R,3,=,x,y,x,y,R,2,(,x,2,+,y,2,9,L,(,x,2,+,y,2,4),=,x,y,x,y,R,2,L,(,x,2,+,y,2,4),图 3.12,3.1.3 关系矩阵和关系图,表达有限集合到有限集合的二元关系时,矩阵是一有力工具定义3.14给定集合,A,=,a,1,a,2,a,m,和,B,=,b,1,b,2,b,n,及一个,A,到,B,的二元关系,R,.,使.,r,ij,=,1,如果,a,i,Rb,j,0,如,a,i,Rb,j,则称,M,R,=,r,ij,矩阵是,R,的关系矩阵.,例4设,A,=,a,1,a,2,B,=,b,1,b,2,b,3,R,=,a,1,b,1,a,2,b,1,a,1,b,3,a,2,b,2,则其关系矩阵为,b,1,b,2,b,3,a,1,1,0,1,a,2,1,1,0,即,例5设,A,=1,2,3,4,A,上的二元关系,R,=,x,y,x,y,试求出关系矩阵,解,R,=4,1,4,2,4,3,3,1,3,2,2,1,图 3.13,例6设,A,=1,2,3,4,5,R,=1,2,2,2,3,2,3,4,4,3,其图示如图3.13所示.图中结点5叫做孤立点利用关系,R,的图示,也可写出关系,R,.,3.1.4 关系的特性,在研究各种二元关系中,关系的某些特性扮演着重要角色,我们将定义这些特性,并给出它的图示和矩阵的特点,定义3.15设,R,是,A,上的二元关系,(1)如果对,A,中每一,x,xRx,那么,R,是自反的.即,A,上的关系,R,是自反的,x,(,x,A,xRx,),A,=1,2,3,R,1,=1,1,2,2,3,3,1,2,是自反的.其关系图和关系矩阵的特点如图3.14所示.,图 3.14,(2)如果对,A,中每一,x,xRx,那么,R,是反自反的.即,A,上的关系,R,是反自反的,x,(,x,A,xRx,),例如,A,=1,2,3,R,2,=2,1,1,3,3,2,是反自反的,其关系图和关系矩阵的特点如图3.15所示.,图 3.15,有些关系既不是自反的,又不是反自反的(如图3.16),例如,R,3,=1,1,1,2,3,2,2,3,3,3,图 3.16,(3)如果对每一,x,y,A,xRy,蕴含着,yRx,那么,R,是对称的.即,A,上的关系,R,是对称的,x,y,(x,A,y,A,xRy,yRx,),例如,A,=1,2,3,R,4,=1,2,2,1,1,3,3,1,1,1,是对称的.其关系图和关系矩阵的特点如图3.17所示,图 3.17,(4)如果对每一,x,y,A,xRy,yRx,蕴含着,x,=,y,那么,R,是反对称的.即,A,上的关系,R,是反对称的,x,y,(,x,A,y,A,xRy,yRx,x,=,y,),例如,A,=1,2,3,R,5,=1,2,2,3,是反对称的,其关系图和关系矩阵的特点如图3.18所示.,图 3.18,(5)如果对每一,x,y,z,A,xRy,yRz,蕴含着,xRz,那么,R,是传递的.即,A,上的关系,R,是传递的,x,y,z,(,x,A,y,A,z,=,A,xRy,yRz,xRz,),例如,A,=1,2,3,4,R,5,=4,1,4,3,4,2,3,2,3,1,2,1,是传递的.其关系图和关系矩阵如图3.110所,示.,图 3.19,图 3.110,例7,(,a),任何集合上的相等关系是自反的,对称的,反对称的和传递的,但不是反自反的,(,b),整数集合,I,上,关系是自反的,反对称的,可传递的.但不是反自反的和对称的.关系是反自反的,反对称的,可传递的,但不是自反的和对崐称的,(,c),设=,a,b,试考察上的下列关系:,(,i),关系“与有同样长度”是自反的,对称的,可传递的,但不是反自反的和反对称的,(,ii)“,xRy,”,当,且仅当,x,是,y,的真词头”,这里,R,是反自反的,反对称的,可传递的,但不是自反的和对称的,(,iii)“,xRy,”,当,且仅当,x,的某真词头是,y,的一个真词尾”,这里,R,既不是自反的又不是反自反的,因为,aaRaa,但,abRab,既不是对称的也不是反对称的,并且不是传递的,(,d),非空集合上的空关系是反自反的,对称的,反对称的和传递的,但不是自反的.空集合上的空关系则是自反的,反自反的,对称的,反对称的和可传递的,(,e),基数大于1的集合上的全域关系是自反的,对称的和传递的,但不是反自反的和反对称的.例如图3.111所示的关系,图 3.111,3.2 关系的合成,3.2.1 关系的合成,前边已经指出,关系是序偶的集合,因此可以进行集合运算.本节介绍一种对关系来说,更为重要的运算合成运算.假设,R,1,是,A,到,B,的关系,R,2,是,B,到,C,的关系(参看图3.21).合成关系,R,1,R,2,是一个,A,到,C,的关系:如果,在关系图上,从,a,A,到,c,C,有一长度,(,路径中弧的条数,),为,2,的路径,其第一条弧属于,R,1,其第二条弧属于,R,2,那么,a,c,R,1,R,2,.,合成关系,R,1,R,2,就是由,a,c,这样的序偶组成的集合.,图 3.21,定义3.21设,R,1,是从,A,到,B,的关系,R,2,是从,B,到,C,的关系,从,A,到,C,的合成关系记为,R,1,R,2,定义为,R,1,R,2,=,a,c,a,A,c,C,b,b,B,a,b,R,1,b,c,R,2,例1,(,a),如果,R,1,是关系“是的兄弟”,R,2,是关系“是的父亲”,那么,R,1,R,2,是关系“是的叔伯”.,R,2,R,2,是关系“是的祖父”,(,b),给定集合,A,=1,2,3,4,B,=2,3,4,C,=1,2,3,设,R,是,A,到,B,的关系;,S,是,B,到,C,的关系.,R,=,x,y,x+y,=6=2,4,3,3,4,2,S,=,y,z,y-z,=1=2,1,3,2,4,3,则,RS,=2,3,3,2,4,1.,如图3.22所示.,图 3.22,(,c),设,A,=1,2,3,4,5,R,和,S,都是,A,上二元关系.如果,R,=1,2,3,4,2,2,S,=4,2,2,5,3,1,1,3,则,RS,=1,5,3,2,2,5,SR,=4,2,3,2,1,4,(,RS,),R,=3,2,R,(,SR,)=3,2,RR,=1,2,2