《离散数学关系的概念、性质及运算.ppt》由会员分享,可在线阅读,更多相关《离散数学关系的概念、性质及运算.ppt(25页珍藏版)》请在三一办公上搜索。
1、1,第6节 关系的概念、性质及合成,主要内容:关系的概念关系的性质关系的合成,2,定义1 设A,B是两个集合。AB的任一子集R称为从A到B的一个二元关系。,如果A=B,则称R为A上的一个二元关系。,1 关系的概念,如果(a,b)R,则称a与b符合关系R,并记为aRb;,3,定义2 设RAB,集合 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使
2、得(x,y)R称为R的值域,并记为ran(R)。,dom(R)A;ran(R)B。,定义域与值域,4,例如: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,定义1 设A,B是两个集合,一个从AB到是,否的映射R,称为从A到B的一个二元关系,或A与B间的一个二元关系。,(a,b)AB,如果(a,b)在R下的象为“是”,则a与b符合关系R,记为aRb;,若A=B,则称R为A上的二元关系。,关系与映射,6,定义1
3、一个从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,例如:设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,集合(a,a)a A称为A上的恒等关系或相等关系,并记为
4、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,例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),关系实例,例3:设X是一个集合,集合的包含于“”是2X上
5、的二元关系。,10,定义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,这其实就是关系型数据库的一个数据表。n元关系是关系数据模型的核心,而关系数据模型是关系型数据库的基础。,二元关系到n元关系的推广,12,2 关系的性质,
6、定义1 X上的二元关系R称为自反的,如果x X,xRx。,在这个定义中,要求X的每个元素x,都有xRx,即(x,x)R。,设IX是X上的恒等关系,即:IX=(x,x)x X。,显然:R是自反的,当且仅当IXR。,13,例1:IX是X上的自反关系,但IX的任一真子集RIX不是X上的自反关系。,例2:实数集上的“小于或等于”关系“”是不是自反的?小于关系“”是不是自反的?,例3:令X=a,b,c,R=(a,b),(a,a),(b,c),(c,c),则R是不是自反的?,关系的性质:自反,14,定义2 X上的二元关系R称为反自反的,如果x X,都有(x,x)R。,例4:实数集R上的“大于”关系是反自反
7、的。,注意:反自反的二元关系必不是自反的;,但不是自反的二元关系,却不一定是反自反。,例5:令X=a,b,c,R=(a,b),(a,a),(b,c),(c,c)。,关系的性质:反自反,R不是自反的,但它也不是反自反的。,显然:R是反自反的,当且仅当RIX=。,15,定义3 设R为X上的二元关系。如果x,y X,只要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,定
8、义4 设R为X上的二元关系。对X的任意元素x,y,如果xRy且yRx,则x=y,那么就称R为反对称的。,例8:集合间的包含关系是不是反对称关系?,例9:实数集上的“小于或等于”关系是不是反对称的?,例10:恒等关系Ix。,关系的性质:反对称,显然:R是反对称的,当且仅当RR-1 IX。,17,定义8:设R为X上的二元关系。如果对X上的任意x,y,z,只要xRy且yRz,就有xRz,则称R为传递关系。,例11:Z上的模n同余关系是不是传递关系?,例12:R上的“小于或等于”关系?,Z上的整除关系是不是传递关系?,关系的性质:传递,显然:R是传递的,当且仅当?。,18,例13:设R为X上的二元关系
9、。如果R且R是反自反和对称的,则R不是传递的。,例14:设R为X上的二元关系。R是对称的且反对称的当且仅当RIX。,关系的性质,例15:设R,S是集合X上的两个传递关系,问RS是否是传递关系呢?,19,运算与性质的关系,20,定义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,定理1 设R1,R2,R3分别是从A到B,B
10、到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,4、一般说来,合成运算对差运算不满足分配律:,R1(R2R3)(R1R2)(R1R3),(R2R3)R4(R2R4)(R
11、3R4),例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,定理3 设R,S是集合X上的两个二元关系,则(1)(RS)-1=S-1R-1;(2)RR-1是对称的。,5、关系的逆的合成,关系合成的性质,定理4 设R是X上的二元关系,则R是传递的当且仅当:RRR。,6、关系R是传递关系的充要条件,例3:集合X上的二元关系R是
12、对称且传递的,当且仅当R=RR-1。,24,关系幂运算的定义及性质,定义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,定理7 设R是X上的二元关系。如果存在非负整数s,t,st,使得Rs=Rt,则,(1)Rs+k=Rt+k,k为非负整数;,(2)Rs+kp+i=Rs+i,其中p=t-s,而k,i为非负整数;,(3)令S=R0,R,R2,.,Rt-1,则对任意的非负的整数q有RqS。,定理6 设X是一个有限集合且X=n,R为X上的任一二元关系,则存在非负整数s,t使得0st2n2且Rs=Rt。,关系幂运算的定义及性质,