关系的概念性质及运算

集合与图论,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第6节 关系的概念、性质及合成,主要内容：,关系的概念,关系的性质,关系的合成,1,定义1,设A,B是两个集合。A,B的任一子集R称为从A到B的一个,二元关系,。,如果A=B，则称R为A上的一个二元关系。,1 关系的概念,如果(a,b)R，则称a与b符合关系R，并记为,aRb;,如果(a,b)R，则称a与b不符合关系R，并记为aRb。,2,定义2,设R,A,B，集合,x,x A且y B使得(x,y)R,称为R的,定义域,，并记为dom(R)。,例如：,设A=1,2,3,4，B=a,b,c,d,e，,(1,a),(2,b),(2,c),(3,c)是一个二元关系。,1,2,3是定义域，a,b,c是值域,一般情况下：A dom(R);B ran(R)。,集合,y,y B且x A使得(x,y)R,称为R的,值域,，并记为ran(R)。,dom(R)A;ran(R)B。,定义域与值域,3,例如:,A=1,2，B=a,b,c。,映射是特殊的二元关系。,令f:A,B，f(1)=a，f(2)=b，,则,映射f就对应着A,B的子集(1,a)，(2,b),关系与映射,问题1：,映射与二元关系有什么联系？,（,前提：映射和二元关系都是从A到B的,）,4,定义1,设A,B是两个集合，一个从A,B到是,否的映射R，称为从A到B的一个,二元关系,，或A与B间的一个二元关系。,(a,b),A,B，如果(a,b)在R下的象为“是”，则a与b符合关系R，记为aRb；,若A=B，则称R为A上的二元关系。,如果(a,b)在R下的象为“否”，则说a与b没有或不符合关系R，并记为aRb。,关系与映射,5,定义1,一个从A到B的多值部分映射,R称为从A到B的一个,二元关系,。,关系与映射,设A,B是两个集合，一个从A,到2,B,的映射R称为,从A到B的一个,多值部分映射,。,如果a,A，R(a)=,，则称,R,在,a,无定义；,而如果,R(a),，则,b,R(a)，b,称,a,在,R,下的一,个象或值,。,6,例如：,设A=1,2，B=a,b,c，,A,B,=(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)。,A,B有6个元素，,从而有2,6,个子集，,因此从A到B就有2,6,个关系。,答案：2,mn,问题2：,A到B的关系的个数,设|A|=m，|B|=n，则,A到B上有多少个二元关系？,关系的个数,7,集合(a,a),a A称为A上的,恒等关系,或相等关,系，并记为I,A,。,空集也是,A,B的一个子集。,空集叫做A到B的,空关系,。,A,B是,A,B的一个子集，按定义,A,B也是从,A,到,B的一个二元关系。,A,B叫做A到B的,全关系,。,四个特殊二元关系,设R是A到B的二元关系，集合,(y,x)(x,y)R,称为R的,逆关系，简称,R的,逆，,记为R,-1,。,显然：,R,-1,是B到A的二元关系。,8,例1：,整除关系,例2：,整数集Z上的模n同余关系,设Z为整数集，Z上的整除关系记为,。m,n Z,mn 当且仅当 m能除尽n。,设n为任一给定的自然数。对任意两个整数m,k，如果m和k被n除，所得余数相等，则称m与k为,模n同余,，并记为：m,k(mod n),当n=3时，2,5(mod 3)，,5,7(mod 3)。,关系实例,例3：,设X是一个集合，集合的包含于“,”是2,X,上的二元关系。,9,定义3,设A,1,A,2,.,A,n,是n个集合，一个,A,1,A,2,.,A,n,的子集R称为A,1,A,2,.,A,n,间的,n元关系,。,每个A,i,称为R的一个,域,。,例4：,设,1、A为某单位职工“姓名”的集合；,2、B为“性别”之集合，B=男，女；,3、C为职工年龄集合 C=1,2,.,100;,4、D表示“文化程度”；,D=小学,初中,高中,大学,硕士,博士；,5、E是“婚否”集合，E=是，否；,6、F表示月工资，F=0,20000。,二元关系到n元关系的推广,10,姓名,A,性别,B,年龄,C,文化程度,D,婚否,E,工资,F,张三,男,28,大学,是,400,李四,男,50,硕士,是,1400,李晓芬,女,18,高中,否,300,这其实就是关系型数据库的一个数据表。,n元关系是关系数据模型的核心，而关系数据模型,是关系型数据库的基础。,二元关系到n元关系的推广,11,2 关系的性质,定义1,X上的二元关系R称为,自反的,，如果,x X,xRx。,在这个定义中，要求X的每个元素x，都有xRx，,即(x,x),R。,设I,X,是X上的恒等关系，即：I,X,=(x,x),x X。,显然：,R是自反的，当且仅当I,X,R。,12,例1：,I,X,是X上的自反关系，但I,X,的任一真子集R,I,X,不是X上的自反关系。,例2：,实数集上的“小于或等于”关系“”是不是自反的？小于关系“是反自反的。,注意：,反自反的二元关系必不是自反的；,但不是自反的二元关系，却不一定是反自反。,例5：,令X=a,b,c，R=(a,b),(a,a),(b,c),(c,c)。,关系的性质：反自反,R不是自反的，但它也不是反自反的。,显然：,R是反自反的，当且仅当,R,I,X,=,。,14,定义3,设R为X上的二元关系。如果,x,y X,只要xRy就有yRx，则称R是,对称的,。,例6：,定义在人的集合X上的“同学”、“战友”、“兄弟”关系是对称关系。,例7：,令f:A,B,Ker(f)=(x,y)x,yA且f(x)=f(y),Ker(f)称为f的,核,。,自反,对称,关系的性质：对称,显然：,R是对称的，当且仅当,R=R,-1,。,15,定义4,设R为X上的二元关系。对X的任意元素x,y,如果,xRy且yRx，则x=y，那么就称R为,反对称的,。,例8：,集合间的包含关系,是不是反对称关系？,例9：,实数集上的“小于或等于”关系是不是反对称的？,例10：,恒等关系I,x,。,关系的性质：反对称,显然：,R是反对称的，当且仅当,R,R,-1,I,X,。,16,定义8：,设R为X上的二元关系。如果对X上的任意x,y,z，只要xRy且yRz，就有xRz，则称R为,传递关系,。,例11：,Z上的模n同余关系是不是传递关系？,例12：,R上的“小于或等于”关系？,Z上的整除关系是不是传递关系？,关系的性质：传递,显然：,R是传递的，当且仅当,？,。,17,例13：,设R为X上的二元关系。,如果R且R是反自反和对称的，则R不是传递的。,例14：,设R为X上的二元关系。R是对称的且反对称的当且仅当R,I,X,。,关系的性质,例15：,设R,S是集合X上的两个传递关系，问R,S是否是传递关系呢？,18,自反性,反自反性,对称性,反对称性,传递性,R,1,1,R,1,R,2,R,1,R,2,R,1,R,2,R,1,R,2,运算与性质的关系,19,定义1,设R是A到B,的二元关系,，S是B到C的二元关系。R与S的,合成,是A到C的一个二元关系，记成R,S，并且,R,S=(x,z)(x,z)AC且yB使得xRy且ySz,例1：,设,X=a,b,c,d，R=(a,b),(c,d)，S=(b,c),(d,a)。,R,S=(a,c),(c,a),SR=(b,d),(d,b),3 关系的合成,20,定理1,设R,1,R,2,R,3,分别是从A到B，B到C，C到D的二元关系，则(R,1,R,2,)R,3,=,R,1,(R,2,R,3,)。,2、合成运算满足结合律,1、一般来说，合成运算不满足交换律，即R,SS,R。,关系合成的性质,定理2,设R,1,是A到B的二元关系，R,2,R,3,是从B到C的二元关系，R,4,是从C到D的二元关系，则,(1)R,1,(R,2,R,3,)=(,R,1,R,2,)(,R,1,R,3,),(2)R,1,(R,2,R,3,)(,R,1,R,2,)(,R,1,R,3,),(3),(R,2,R,3,),R,4,=(,R,2,R,4,)(,R,3,R,4,),(4),(R,2,R,3,),R,4,(,R,2,R,4,)(,R,3,R,4,),3、合成运算对并、交运算的分配关系,21,4、一般说来，合成运算对差运算不满足分配律：,R,1,(R,2,R,3,)(,R,1,R,2,)(,R,1,R,3,),(R,2,R,3,),R,4,(,R,2,R,4,)(,R,3,R,4,),例2：,设X=a,b,c，R,1,=(a,a),(a,b),R,2,=(a,a),(b,c)，R,3,=(a,c),(b,b)。,R,2,R,3,=(a,a),(b,c),(,R,1,R,2,)=(a,a),(a,c),R,1,(R,2,R,3,)=(a,a),(a,c),(,R,1,R,3,)=(a,c),(a,b),(,R,1,R,2,)(,R,1,R,3,)=(a,a),关系合成的性质,22,定理3,设R,S是集合X上的两个二元关系，则,(1)(RS),-1,=S,-1,R,-1,；,(2)RR,-1,是对称的。,5、关系的逆的合成,关系合成的性质,定理4,设R是X上的二元关系，则R是传递的当,且仅当：,RRR。,6、关系R是传递关系的充要条件,例3：,集合X上的,二元关系R是对称且传递的，当且,仅当R=R,R,-1,。,23,关系幂运算的定义及性质,定义2,设,R是X上的一个二元关系，R的,n次幂,记作R,n,，n为非负整数。,(1)R,0,=I,X,，R,1,=R，R,2,=RR;,(2)R,n+1,=R,n,R。,定理5,设,R是X上的一个二元关系，则对任意的非负整数m,n有,(1)R,m,R,n,=R,m+n,(2)(R,m,),n,=R,mn,。,24,定理7,设R是,X上的二元关系。如果存在非负整数s,t，st，使得R,s,=R,t,，则,(1)R,s+k,=R,t+k,，k为非负整数；,(2)R,s+kp+i,=R,s+i,，其中p=t-s，而k,i为非负整数；,(3)令S=R,0,R,R,2,.,R,t-1,，则对任意的非负的整数q有R,q,S。,定理6,设,X是一个有限集合且X=n，R为X上的任一二元关系，则存在非负整数s,t使得0st2,n,2,且R,s,=R,t,。,关系幂运算的定义及性质,25,