《离散数学-41-2关系.ppt》由会员分享，可在线阅读，更多相关《离散数学-41-2关系.ppt（32页珍藏版）》请在三一办公上搜索。
1、课件,1,第4章 关系,课件,2,第4章 关系,4.1 关系的定义及其表示4.2 关系运算4.3 关系的性质4.4 等价关系与偏序关系,课件,3,4.1 关系的定义及其表示,4.1.1 有序对与笛卡儿积4.1.2 二元关系的定义4.1.3 二元关系的表示,课件,4,定义4.1 由两个元素，如x和y，按照一定的顺序组成的二元组称为有序对，记作 实例：点的直角坐标(3,4)有序对的性质 有序性（当x y时）与相等的充分必要条件是=x=u y=v例1=，求 x,y.解 3y4=2,x+5=y y=2,x=3,有序对,课件,5,笛卡儿积,定义4.2 设A,B为集合，A与B 的笛卡儿积记作AB，AB=|
2、xA yB.例2 A=0,1,B=a,b,c AB=,BA=,A=,B=P(A)A=,P(A)B=,课件,6,笛卡儿积的性质,对于并或交运算满足分配律 A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA),若A或B中有一个为空集，则AB就是空集.A=B=,不适合交换律 ABBA(AB,A,B),不适合结合律(AB)CA(BC)(A,B,C),若|A|=m,|B|=n,则|AB|=mn,课件,7,有序 n 元组和 n 阶笛卡尔积,定义4.3(1)由 n 个元素 x1,x2,xn按照一定的顺序排列构成 有序 n 元组，记作(2)设A1,A
3、2,An为集合，称 A1A2An=|xiAi,i=1,2,n 为 n 阶笛卡儿积.实例(1,1,0)为空间直角坐标，(1,1,0)R R R,课件,8,二元关系的定义,定义4.4如果一个集合满足以下条件之一：（1）集合非空,且它的元素都是有序对（2）集合是空集则称该集合为一个二元关系,简称为关系，记作R.如R,可记作 xRy；如果R,则记作x y实例：R=,S=,a,b.R是二元关系,当a,b不是有序对时，S不是二元关系根据上面的记法，可以写1R2,aRb,a c等.,课件,9,实例,例3(1)R=|x,yN,x+y,(2)C=|x,yR,x2+y2=1，其中R代表实数集合，C是直角坐标平面上
4、点的横、纵坐标之间的关系，C中的所有的点恰好构成坐标平面上的单位圆.(3)R=|x,y,zR,x+2y+z=3，R代表了空间直角坐标系中的一个平面.,课件,10,5元关系的实例数据库实体模型,5元组：，,课件,11,从A到B的关系与A上的关系,定义4.5 设A,B为集合,AB的任何子集所定义的二元关系叫做从 A 到 B 的二元关系,当 A=B 时则叫做 A上的二元关系.例4 A=0,1,B=1,2,3,R1=,R2=AB,R3=,R4=,从A到B的关系:R1,R2,R3,R4,A上的关系R3和R4.计数：|A|=n,|B|=m,|AB|=nm,AB 的子集有 个.所以从A到B有 个不同的二元关
5、系.|A|=n,A上有 不同的二元关系.例如|A|=3,则 A上有512个不同的二元关系.,课件,12,A上重要关系的实例,设A为任意集合，是A上的关系，称为空关系定义 4.6 EA,IA分别称为全域关系与恒等关系，其中 EA=|xA yA=AA IA=|xA例如,A=1,2,则 EA=,IA=,课件,13,A上重要关系的实例（续）,小于等于关系LA,整除关系DA,包含关系R定义如下：定义4.7 LA=|x,yAxy,这里AR，R为实数集合 DB=|x,yBx整除y,BZ*,Z*为非0整数集 R=|x,yAxy,这里A是集合族.例如 A=1,2,3,B=a,b,则 LA=,DA=,A=P(B)
6、=,a,b,a,b,则A上的包含关系是 R=,类似的还可以定义大于等于关系,小于关系,大于关系,真包含关系等等.,课件,14,关系的表示,表示方式：关系的集合表达式、关系矩阵、关系图 定义4.8 关系矩阵 若A=x1,x2,xm，B=y1,y2,yn，R是从A到B的关系，R的关系矩阵是布尔矩阵MR=rij mn,其中 rij=1 R.定义4.9 关系图 若A=x1,x2,xm，R是从A上的关系，R的关系图是GR=,其中A为结点集，R为边集.如果属于关系R，在图中就有一条从 xi 到 xj 的有向边.注意：设A,B为有穷集关系矩阵适合于表示从A到B 的关系或者A上的关系关系图适合于表示A上的关系
7、,课件,15,实例,例5 A=a,b,c,d,R=,R的关系矩阵 MR 和关系图 GR 如下：,课件,16,4.2.1 关系的基本运算定义域、值域、域、逆、合成基本运算的性质4.2.2 关系的幂运算幂运算的定义幂运算的方法幂运算的性质,4.2 关系运算,课件,17,关系的基本运算,定义4.10 定义域、值域 和 域 domR=x|y(R)ranR=y|x(R)fldR=domR ranR,例1 R=,则 domR=ranR=fldR=,a,c,a,d,b,d,a,c,a,d,b,d,d,课件,18,关系的基本运算（续）,定义4.11 R 的逆 R1=|R定义4.12 R与S的合成 RS=|y(
8、RS),例2 R=,S=,R1=RS=SR=,课件,19,合成运算的图示方法,利用图示（不是关系图）方法求合成 RS=,SR=,课件,20,基本运算的性质,定理4.1 设F是任意的关系,则(1)(F1)1=F(2)domF1=ranF,ranF1=domF证(1)任取,由逆的定义有(F 1)1 F1 F所以有(F1)1=F(2)任取x,xdomF1 y(F1)y(F)xranF 所以有domF1=ranF.同理可证 ranF1=domF.,课件,21,定理4.2 设F,G,H是任意的关系,则(1)(FG)H=F(GH)(2)(FG)1=G1F1 证(1)任取,(FG)H t(FGH)t(s(F
9、G)H)t s(FGH)s(Ft(GH)s(FGH)F(GH)所以(FG)H=F(GH),基本运算的性质（续）,课件,22,(2)任取,(FG)1 FG t(F(t,x)G)t(G1(t,y)F1)G1F1所以(FG)1=G1F1,基本运算的性质（续）,课件,23,定理4.3 设 R 为 A上的关系,则 RIA=IAR=R 证明任取 RIA t(RIA)t(Rt=yyA)R从而有RIA=R.同理可证 IAR=R.,基本运算的性质（续）,课件,24,A上关系的幂运算定义,定义4.13 设R为A上的关系,n为自然数,则 R 的 n次幂是(1)R0=|xA=IA(2)Rn+1=RnR 注意：对于A上
10、的任何关系R1和R2都有 R10=R20=IA 对于A上的任何关系 R 都有 R1=R,课件,25,幂运算的方法,对于集合表示的关系R，计算Rn 就是 n 个 R 合成.矩阵表示的关系就是矩阵相乘,其中相加采用逻辑加.例3 设A=a,b,c,d,R=,求R的各次幂,分别用矩阵和关系图表示.解 R与R2的关系矩阵分别为,课件,26,同理R3和R4的矩阵是：因此M4=M2,即R4=R2.因此可以得到R2=R4=R6=,R3=R5=R7=而R0=IA的关系矩阵,幂运算的方法（续）,课件,27,用关系图的方法得到R0,R1,R2,R3,的关系图如下图所示,幂运算的方法（续）,课件,28,幂运算的性质,
11、定理4.4 设 A 为 n 元集,R是A上的关系,则存在自然数 s 和 t,使得 Rs=Rt.证 R 为A上的关系,由于|A|=n,A上的不同关系只有 个.当列出 R 的各次幂 R0,R1,R2,必存在自然数 s 和 t 使得 Rs=Rt.,课件,29,定理4.5 设 R 是 A 上的关系,m,nN,则(1)RmRn=Rm+n(2)(Rm)n=Rmn 证 用归纳法(1)对于任意给定的 mN,施归纳于 n.若n=0,则有 RmR0=RmIA=Rm=Rm+0 假设 RmRn=Rm+n,则有RmRn+1=Rm(RnR)=(RmRn)R=Rm+n+1,所以对一切 m,nN 有 RmRn=Rm+n.,幂
12、运算的性质（续）,课件,30,(2)对于任意给定的 mN,施归纳于 n.若 n=0,则有(Rm)0=IA=R0=Rm0 假设(Rm)n=Rmn,则有(Rm)n+1=(Rm)nRm=(Rmn)Rm=Rmn+m=Rm(n+1)所以对一切 m,nN 有(Rm)n=Rmn.,幂运算的性质（续）,课件,31,定理4.6 设R 是A上的关系,若存在自然数 s,t(st)使得 Rs=Rt,则(1)对任何 kN 有 Rs+k=Rt+k(2)对任何 k,iN 有Rs+kp+i=Rs+i,其中p=ts(3)令S=R0,R1,Rt1,则对于任意的 qN有 RqS证明(1)Rs+k=RsRk=RtRk=Rt+k（2）对 k 归纳.若k=0,则有 Rs+0p+i=Rs+i假设 Rs+kp+i=Rs+i,其中p=ts,则Rs+(k+1)p+i=Rs+kp+i+p=Rs+kp+iRp=Rs+iRp=Rs+p+i=Rs+ts+i=Rt+i=Rs+i 由归纳法命题得证.,幂运算的性质（续）,课件,32,(3)任取 qN,若qt,显然有 RqS.若 qt,则存在自然数 k 和 i 使得 q=s+kp+i，其中0ip1.于是Rq=Rs+kp+i=Rs+i 而 s+i s+p1=s+ts1=t1 这就证明了 RqS.,幂运算的性质（续）,
