离散数学第4章关系.ppt

《离散数学第4章关系.ppt》由会员分享，可在线阅读，更多相关《离散数学第4章关系.ppt（43页珍藏版）》请在三一办公上搜索。

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=|xA yB.例2 A=0,1,

2、B=a,b,c AB=,BA=,A=,B=P(A)A=,P(A)B=,6,【例】设 A=a,b，B=1,2,3，试求AB和BA 验证|AB|=|A|B|和|BA|=|B|A|,解：AB=a,1,a,2,a,3,b,1,b,2,b,3 BA=1,a,1,b,2,a,2,b,3,a,3,b|AB|=6=23=|A|B|BA|=6=32=|B|A|,7,笛卡儿积的性质,对于并或交运算满足分配律 A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA)幻灯片 9,若A或B中有一个为空集，则AB就是空集.A=B=,不适合交换律 ABBA(AB,A,

3、B)幻灯片 6,不适合结合律(AB)CA(BC)(A,B,C)幻灯片 8,若|A|=m,|B|=n,则|AB|=mn 幻灯片 6,8,解：ABC=(AB)C=1,a,1,b,2,a,2,bx,y=1,a,x,1,b,x,2,a,x,2,b,x,1,a,y,1,b,y,2,a,y,2,b,y A(BC)=1,2a,x,a,y,b,x,b,y=1,a,x,1,a,y,1,b,x,1,b,y 2,a,x,2,a,y,2,b,x,2,b,y 显然ABCA(BC)。,【例】设A=1,2，B=a,b，A=x,y，求：ABC，A(BC)。,9,证明：仅证明 任取a,b a,bA(BC)aAbBC aA(bB

4、bC)(aAbB)(aAbC)a,bABa,bAC a,b(AB)(AC)故 A(BC)=(AB)(AC)可类似地证明、。,A(BC)=(AB)(AC),10,有序 n 元组和 n 阶笛卡尔积,定义4.3(1)由 n 个元素 x1,x2,xn按照一定的顺序排列构成 有序 n 元组，记作(2)设A1,A2,An为集合，称 A1A2An=|xiAi,i=1,2,n 为 n 阶笛卡儿积.实例(1,1,0)为空间直角坐标，(1,1,0)R R R,11,二元关系的定义,定义4.4如果一个集合满足以下条件之一：（1）集合非空,且它的元素都是有序对（2）集合是空集则称该集合为一个二元关系,简称为关系，记作

5、R.如R,可记作 xRy；如果R,则记作x y实例：R=,S=,a,b.R是二元关系,当a,b不是有序对时，S不是二元关系根据上面的记法，可以写1R2,aRb,a c等.,12,实例,例3(1)R=|x,yN,x+y,(2)C=|x,yR,x2+y2=1，其中R代表实数集合，C是直角坐标平面上点的横、纵坐标之间的关系，C中的所有的点恰好构成坐标平面上的单位圆.(3)R=|x,y,zR,x+2y+z=3，R代表了空间直角坐标系中的一个平面.,13,5元关系的实例数据库实体模型,5元组：，,14,从A到B的关系与A上的关系,定义4.5 设A,B为集合,AB的任何子集所定义的二元关系叫做从 A 到

6、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有 个不同的二元关系.|A|=n,A上有 不同的二元关系.例如|A|=3,则 A上有512个不同的二元关系.,15,A上重要关系的实例,设A为任意集合，是A上的关系，称为空关系定义 4.6 EA,IA分别称为全域关系与恒等关系，其中 EA=|xA yA=AA IA=|xA例如,A=1,2,则 EA=,IA=,16,A上重要关系的实例（

7、续）,小于等于关系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)=,a,b,a,b,则A上的包含关系是 R=,类似的还可以定义大于等于关系,小于关系,大于关系,真包含关系等等.,17,关系的表示,表示方式：关系的集合表达式、关系矩阵、关系图 定义4.8 关系矩阵 若A=x1,x2,xm，B=y1,y2,yn，R是从A到B的关系，R的关系矩阵是布尔矩阵MR=rij mn,其中 rij=1 R.

8、定义4.9 关系图 若A=x1,x2,xm，R是从A上的关系，R的关系图是GR=,其中A为结点集，R为边集.如果属于关系R，在图中就有一条从 xi 到 xj 的有向边.注意：设A,B为有穷集关系矩阵适合于表示从A到B 的关系或者A上的关系关系图适合于表示A上的关系,18,2.用关系矩阵表示二元关系 如果A，B是有限集，A=a1,a2,am，B=b1,b2,bn，R是A到B的二元关系，R的关系矩阵MR定义为：MR=mn,i=1,m j=1,n称为二元关系R的关系矩阵。,19,【例】设A=a1,a2,a3,a4，B=b1,b2,b3，R是A到B的二元关系，定义为：R=a1,b1,a1,b3,a2,

9、b2,a2,b3,a3,b1,a4,b1,a4,b2 写出R的关系矩阵。解：R的关系矩阵为：,MR=,20,【例】设A=1,2,3,4，R是A的二元关系，定义为：R=1,1,1,2,2,1,3,2,3,1,4,3,4,2,4,1写出A上二元关系R的关系矩阵。解：R的关系矩阵为：,MR=,21,3.用关系图表示二元关系 如果A和B是有限集，R是A到B二元关系，还可以用图表示二元关系R。表示二元关系R的图叫做R的关系图。A到B二元关系的关系图和A上的二元关系的关系图的定义是不一样的。分别描述如下：,22,A到B二元关系R的关系图 设A=a1,a2,am，B=b1,b2,bn，R是A到B二元关系，R

10、的关系图的绘制方法如下：画出m个小点表示A的元素，再画出n个小点表示B的元素。这些小点叫做关系图的顶点(下同)。如果ai,bj R，则从ai到bj画一根有方向(带箭头)的线。这些有方向(带箭头)的线叫做关系图的边(下同)。,23,【例】设A=a1,a2,a3,a4，B=b1,b2,b3，R是A到B的二元关系，定义为：R=a1,b1,a1,b3,a2,b2,a2,b3,a3,b1,a4,b1,a4,b2 R的关系图如下：,24,A上的二元关系R的关系图 设A=a1,a2,am，R是A上的二元关系，其关系图如下绘制：画出m个小点表示A的元素。如果ai,ajR，则从ai到aj画一根有方向(带箭头)的

11、线。,25,例5 A=a,b,c,d,R=,R的关系矩阵 MR 和关系图 GR 如下：,26,【例】设A=1,2,3,4，R是A的二元关系，R=1,1,1,2,2,1,3,2,3,1,4,3,4,2 4,1 A上二元关系R的关系图如下：,27,4.2.1 关系的基本运算定义域、值域、域、逆、合成基本运算的性质4.2.2 关系的幂运算幂运算的定义幂运算的方法幂运算的性质,4.2 关系运算,28,关系的基本运算,定义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

12、,a,d,b,d,d,29,关系的基本运算（续）,定义4.11 R 的逆 R1=|R定义4.12 R与S的合成 RS=|y(RS),例2 R=,S=,R1=RS=SR=,30,合成运算的图示方法,利用图示（不是关系图）方法求合成 RS=,SR=,31,基本运算的性质,定理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.,32,定理4.2 设F,G,H是任意的关系,

13、则(1)(FG)H=F(GH)(2)(FG)1=G1F1 证(1)任取,(FG)H t(FGH)t(s(FG)H)t s(FGH)s(Ft(GH)s(FGH)F(GH)所以(FG)H=F(GH),基本运算的性质（续）,33,(2)任取,(FG)1 FG t(F(t,x)G)t(G1(t,y)F1)G1F1所以(FG)1=G1F1,基本运算的性质（续）,34,定理4.3 设 R 为 A上的关系,则 RIA=IAR=R 证明任取 RIA t(RIA)t(Rt=yyA)R从而有RIA=R.同理可证 IAR=R.,基本运算的性质（续）,35,A上关系的幂运算定义,定义4.13 设R为A上的关系,n为自

14、然数,则 R 的 n次幂是(1)R0=|xA=IA(2)Rn+1=RnR 注意：对于A上的任何关系R1和R2都有 R10=R20=IA 对于A上的任何关系 R 都有 R1=R,36,幂运算的方法,对于集合表示的关系R，计算Rn 就是 n 个 R 合成.矩阵表示的关系就是矩阵相乘,其中相加采用逻辑加.例3 设A=a,b,c,d,R=,求R的各次幂,分别用矩阵和关系图表示.解 R与R2的关系矩阵分别为,37,同理R3和R4的矩阵是：因此M4=M2,即R4=R2.因此可以得到R2=R4=R6=,R3=R5=R7=而R0=IA的关系矩阵,幂运算的方法（续）,38,用关系图的方法得到R0,R1,R2,R

15、3,的关系图如下图所示,幂运算的方法（续）,39,幂运算的性质,定理4.4 设 A 为 n 元集,R是A上的关系,则存在自然数 s 和 t,使得 Rs=Rt.证 R 为A上的关系,由于|A|=n,A上的不同关系只有 个.当列出 R 的各次幂 R0,R1,R2,必存在自然数 s 和 t 使得 Rs=Rt.,40,定理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+

16、n+1,所以对一切 m,nN 有 RmRn=Rm+n.,幂运算的性质（续）,41,(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.,幂运算的性质（续）,42,定理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 由归纳法命题得证.,幂运算的性质（续）,43,(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.,幂运算的性质（续）,