关系的概念性质及运算

1/25,第6节 关系的概念、性质及合成,主要内容： 关系的概念 关系的性质 关系的合成,2/25,定义1 设A,B是两个集合AB的任一子集R称为从A到B的一个二元关系如果A=B，则称R为A上的一个二元关系1 关系的概念,如果(a, b) R，则称a与b符合关系R，并记为 aRb;,3/25,定义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定义域与值域,4/25,例如: 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的）,5/25,定义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上的二元关系关系与映射,6/25,定义1’’ 一个从A到B的多值部分映射R称为从A到B的一个二元关系关系与映射,设A,B是两个集合，一个从A到2B 的映射R称为 从A到B的一个多值部分映射 如果aA，R(a)= ，则称R在a无定义； 而如果R(a) ，则bR(a)，b称 a在R下的一 个象或值 7/25,例如：设A={1,2}，B={a,b,c}，,AB={(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)}AB有6个元素， 从而有26个子集， 因此从A到B就有26个关系答案：2mn,问题2：A到B的关系的个数 设|A|=m，|B|=n，则A到B上有多少个二元关系？,关系的个数,8/25,集合{(a, a) a A}称为A上的恒等关系或相等关 系，并记为IA空集也是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的二元关系9/25,例1：整除关系,例2：整数集Z上的模n同余关系,设Z为整数集，Z上的整除关系记为m, n Z, mn 当且仅当 m能除尽n设n为任一给定的自然数对任意两个整数m, k，如果m和k被n除，所得余数相等，则称m与k为模n同余，并记为：m  k (mod n),关系实例,例3：设X是一个集合，集合的包含于“”是2X上的二元关系10/25,定义3 设A1,A2,.,An是n个集合，一个 A1A2.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 关系的性质,定义1 X上的二元关系R称为自反的，如果x X, xRx。

在这个定义中，要求X的每个元素x，都有xRx， 即(x, x) R设IX是X上的恒等关系，即：IX={(x, x) x X}显然：R是自反的，当且仅当IXR13/25,例1：IX是X上的自反关系，但IX的任一真子集RIX不是X上的自反关系例2：实数集上的“小于或等于”关系“≤”是不是自反的？小于关系“”是不是自反的？,例3：令X={a,b,c}，R={(a,b),(a,a),(b,c),(c,c)}，则 R是不是自反的?,关系的性质：自反,14/25,定义2 X上的二元关系R称为反自反的，如果 x X，都有(x, x) R例4：实数集R上的“大于”关系是反自反的注意： ①反自反的二元关系必不是自反的；,②但不是自反的二元关系，却不一定是反自反例5：令X={a,b,c}，R={(a,b),(a,a),(b,c),(c,c)}关系的性质：反自反,R不是自反的，但它也不是反自反的显然：R是反自反的，当且仅当R∩IX= 15/25,定义3 设R为X上的二元关系如果x, y X, 只要xRy就有yRx，则称R是对称的例6： 定义在人的集合X上的“同学”、“战友”、“兄弟”关系是对称关系。

例7：令f: AB, Ker(f)={(x,y)x,yA且f(x)=f(y)}, Ker(f)称为f的核自反,对称,关系的性质：对称,显然：R是对称的，当且仅当R= R-116/25,定义4 设R为X上的二元关系对X的任意元素x,y,如果xRy且yRx，则x=y，那么就称R为反对称的例8：集合间的包含关系是不是反对称关系？,例9：实数集上的“小于或等于”关系≤是不是反对称的？,例10：恒等关系Ix关系的性质：反对称,显然：R是反对称的，当且仅当R∩R-1 IX17/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是对称的且反对称的当且仅当RIX关系的性质,例15：设R,S是集合X上的两个传递关系，问R∪S是否是传递关系呢？,19/25,运算与性质的关系,20/25,定义1 设R是A到B的二元关系，S是B到C的二元关系。

R与S的合成是A到C的一个二元关系，记成RS，并且 RS={(x,z)(x,z)AC且yB使得xRy且ySz},例1：设X={a,b,c,d}，R={(a,b),(c,d)，S={(b,c),(d,a)}RS ={(a,c), (c,a)},SR ={(b,d), (d,b)},3 关系的合成,21/25,定理1 设R1,R2,R3分别是从A到B，B到C，C到D的二元关系，则(R1R2)R3=R1(R2R3)2、合成运算满足结合律,1、一般来说，合成运算不满足交换律，即RSSR关系合成的性质,定理2 设R1是A到B的二元关系，R2,R3是从B到C的二元关系，R4是从C到D的二元关系，则 (1)R1(R2∪R3)=(R1R2)∪(R1R3) (2)R1(R2∩R3)(R1R2)∩(R1R3) (3)(R2∪R3)R4=(R2R4)∪(R3R4) (4)(R2∩R3)R4(R2R4)∩(R3R4),3、合成运算对并、交运算的分配关系,22/25,4、一般说来，合成运算对差运算不满足分配律：,R1(R2\R3)(R1R2)\(R1R3),(R2\R3)R4(R2R4)\(R3R4),例2： 设X={a,b,c}，R1={(a,a),(a,b)}, R2={(a,a),(b,c)}，R3={(a,c),(b,b)}。

R2\R3={(a,a),(b,c)},(R1R2)={(a,a),(a,c)},R1(R2\R3)={(a,a),(a,c)},(R1R3)={(a,c),(a,b)},(R1R2)\(R1R3)={(a,a)},,关系合成的性质,23/25,定理3 设R,S是集合X上的两个二元关系，则 (1)(RS)-1=S-1R-1； (2)RR-1是对称的5、关系的逆的合成,关系合成的性质,定理4 设R是X上的二元关系，则R是传递的当 且仅当：RRR6、关系R是传递关系的充要条件,例3：集合X上的二元关系R是对称且传递的，当且 仅当R=RR-124/25,关系幂运算的定义及性质,定义2 设R是X上的一个二元关系，R的n次幂 记作Rn，n为非负整数1)R0=IX，R1=R，R2=RR;,(2)Rn+1=RnR定理5 设R是X上的一个二元关系，则对任意的非负整数m,n有 (1)RmRn=Rm+n, (2)(Rm)n=Rmn25/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有RqS。

定理6 设X是一个有限集合且X=n，R为X上的任一二元关系，则存在非负整数s,t使得0≤st≤2n2且Rs=Rt关系幂运算的定义及性质,。