离散数学关系的概念、性质及运算.ppt

1/25,第6节关系的概念、性质及合成,主要内容：关系的概念关系的性质关系的合成,2/25,定义1设A,B是两个集合。AB的任一子集R称为从A到B的一个二元关系。,如果A=B，则称R为A上的一个二元关系。,1关系的概念,如果(a,b)R，则称a与b符合关系R，并记为aRb;,3/25,定义2设RAB，集合xxA且yB使得(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是值域,一般情况下：Adom(R);Bran(R)。,集合yyB且xA使得(x,y)R称为R的值域，并记为ran(R)。,dom(R)A;ran(R)B。,定义域与值域,4/25,例如:A=1,2，B=a,b,c。,映射是特殊的二元关系。,令f:AB，f(1)=a，f(2)=b，则,映射f就对应着AB的子集(1,a)，(2,b),关系与映射,问题1：映射与二元关系有什么联系？（前提：映射和二元关系都是从A到B的）,5/25,定义1设A,B是两个集合，一个从AB到是,否的映射R，称为从A到B的一个二元关系，或A与B间的一个二元关系。,(a,b)AB，如果(a,b)在R下的象为“是”，则a与b符合关系R，记为aRb；,若A=B，则称R为A上的二元关系。,关系与映射,6/25,定义1一个从A到B的多值部分映射R称为从A到B的一个二元关系。,关系与映射,设A,B是两个集合，一个从A到2B的映射R称为从A到B的一个多值部分映射。如果aA，R(a)=，则称R在a无定义；而如果R(a)，则bR(a)，b称a在R下的一个象或值。,7/25,例如：设A=1,2，B=a,b,c，,AB=(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)。,AB有6个元素，从而有26个子集，因此从A到B就有26个关系。,答案：2mn,问题2：A到B的关系的个数设|A|=m，|B|=n，则A到B上有多少个二元关系？,关系的个数,8/25,集合(a,a)aA称为A上的恒等关系或相等关系，并记为IA。,空集也是AB的一个子集。空集叫做A到B的空关系。,AB是AB的一个子集，按定义AB也是从A到B的一个二元关系。AB叫做A到B的全关系。,四个特殊二元关系,设R是A到B的二元关系，集合(y,x)(x,y)R称为R的逆关系，简称R的逆，记为R-1。显然：R-1是B到A的二元关系。,9/25,例1：整除关系,例2：整数集Z上的模n同余关系,设Z为整数集，Z上的整除关系记为。m,nZ,mn当且仅当m能除尽n。,设n为任一给定的自然数。对任意两个整数m,k，如果m和k被n除，所得余数相等，则称m与k为模n同余，并记为：mk(modn),关系实例,例3：设X是一个集合，集合的包含于“”是2X上的二元关系。,10/25,定义3设A1,A2,.,An是n个集合，一个A1A2.An的子集R称为A1,A2,.,An间的n元关系。每个Ai称为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元关系的推广,11/25,这其实就是关系型数据库的一个数据表。n元关系是关系数据模型的核心，而关系数据模型是关系型数据库的基础。,二元关系到n元关系的推广,12/25,2关系的性质,定义1X上的二元关系R称为自反的，如果xX,xRx。,在这个定义中，要求X的每个元素x，都有xRx，即(x,x)R。,设IX是X上的恒等关系，即：IX=(x,x)xX。,显然：R是自反的，当且仅当IXR。,13/25,例1：IX是X上的自反关系，但IX的任一真子集RIX不是X上的自反关系。,例2：实数集上的“小于或等于”关系“”是不是自反的？小于关系“是反自反的。,注意：反自反的二元关系必不是自反的；,但不是自反的二元关系，却不一定是反自反。,例5：令X=a,b,c，R=(a,b),(a,a),(b,c),(c,c)。,关系的性质：反自反,R不是自反的，但它也不是反自反的。,显然：R是反自反的，当且仅当RIX=。,15/25,定义3设R为X上的二元关系。如果x,yX,只要xRy就有yRx，则称R是对称的。,例6：定义在人的集合X上的“同学”、“战友”、“兄弟”关系是对称关系。,例7：令f:AB,Ker(f)=(x,y)x,yA且f(x)=f(y),Ker(f)称为f的核。,自反,对称,关系的性质：对称,显然：R是对称的，当且仅当R=R-1。,16/25,定义4设R为X上的二元关系。对X的任意元素x,y,如果xRy且yRx，则x=y，那么就称R为反对称的。,例8：集合间的包含关系是不是反对称关系？,例9：实数集上的“小于或等于”关系是不是反对称的？,例10：恒等关系Ix。,关系的性质：反对称,显然：R是反对称的，当且仅当RR-1IX。,17/25,定义8：设R为X上的二元关系。如果对X上的任意x,y,z，只要xRy且yRz，就有xRz，则称R为传递关系。,例11：Z上的模n同余关系是不是传递关系？,例12：R上的“小于或等于”关系？,Z上的整除关系是不是传递关系？,关系的性质：传递,显然：R是传递的，当且仅当？。,18/25,例13：设R为X上的二元关系。如果R且R是反自反和对称的，则R不是传递的。,例14：设R为X上的二元关系。R是对称的且反对称的当且仅当RIX。,关系的性质,例15：设R,S是集合X上的两个传递关系，问RS是否是传递关系呢？,19/25,运算与性质的关系,20/25,定义1设R是A到B的二元关系，S是B到C的二元关系。R与S的合成是A到C的一个二元关系，记成RS，并且RS=(x,z)(x,z)AC且yB使得xRy且ySz,例1：设X=a,b,c,d，R=(a,b),(c,d)，S=(b,c),(d,a)。,RS=(a,c),(c,a),SR=(b,d),(d,b),3关系的合成,21/25,定理1设R1,R2,R3分别是从A到B，B到C，C到D的二元关系，则(R1R2)R3=R1(R2R3)。,2、合成运算满足结合律,1、一般来说，合成运算不满足交换律，即RSSR。,关系合成的性质,定理2设R1是A到B的二元关系，R2,R3是从B到C的二元关系，R4是从C到D的二元关系，则(1)R1(R2R3)=(R1R2)(R1R3)(2)R1(R2R3)(R1R2)(R1R3)(3)(R2R3)R4=(R2R4)(R3R4)(4)(R2R3)R4(R2R4)(R3R4),3、合成运算对并、交运算的分配关系,22/25,4、一般说来，合成运算对差运算不满足分配律：,R1(R2R3)(R1R2)(R1R3),(R2R3)R4(R2R4)(R3R4),例2：设X=a,b,c，R1=(a,a),(a,b),R2=(a,a),(b,c)，R3=(a,c),(b,b)。,R2R3=(a,a),(b,c),(R1R2)=(a,a),(a,c),R1(R2R3)=(a,a),(a,c),(R1R3)=(a,c),(a,b),(R1R2)(R1R3)=(a,a),关系合成的性质,23/25,定理3设R,S是集合X上的两个二元关系，则(1)(RS)-1=S-1R-1；(2)RR-1是对称的。,5、关系的逆的合成,关系合成的性质,定理4设R是X上的二元关系，则R是传递的当且仅当：RRR。,6、关系R是传递关系的充要条件,例3：集合X上的二元关系R是对称且传递的，当且仅当R=RR-1。,24/25,关系幂运算的定义及性质,定义2设R是X上的一个二元关系，R的n次幂记作Rn，n为非负整数。,(1)R0=IX，R1=R，R2=RR;,(2)Rn+1=RnR。,定理5设R是X上的一个二元关系，则对任意的非负整数m,n有(1)RmRn=Rm+n,(2)(Rm)n=Rmn。,25/25,定理7设R是X上的二元关系。如果存在非负整数