第四章关系精选PPT.ppt
《第四章关系精选PPT.ppt》由会员分享,可在线阅读,更多相关《第四章关系精选PPT.ppt(85页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第四章第四章 关系关系第1页,此课件共85页哦一、有序对一、有序对 定定义义 由由两两个个固固定定次次序序的的个个体体x x,y y组组成成的的序序列列称称为为有有序序对对或或序序偶偶,记记为为xy,其其中中x x,y y分分别别称称为为序序偶偶的的第第一一、二元素(或称第一、二分量)。二元素(或称第一、二分量)。第一节第一节 有序对与笛卡尔积有序对与笛卡尔积2 2、=当且仅当当且仅当a=u,b=v.a=u,b=v.注注:1 1、当、当abab时,时,.第2页,此课件共85页哦二、二、笛卡儿积的概念笛卡儿积的概念 1.1.定定义义 给给定定集集合合A A和和B B,称称集集合合xy xAyBx
2、AyB为为A A与与B B的笛卡尔积,简称为卡氏积,记为的笛卡尔积,简称为卡氏积,记为ABAB。注注:a a)设)设 ,故故的子集个数:的子集个数:第3页,此课件共85页哦 b b)推广:称)推广:称为为A A1 1,A,A2 2,.,A,.,An n的笛卡尔积。特别的,记的笛卡尔积。特别的,记为为A A的的n n次幂,且有次幂,且有第4页,此课件共85页哦例例 (1 1)A=aA=a,bb,B=cB=c,dd,求,求ABAB和和BA BA。(2)A=a,b,B=1,2,C=c,(2)A=a,b,B=1,2,C=c,求求(AB)C(AB)C和和A(BC)A(BC)。解(解(1 1)AB=aAB
3、=a,bcbc,d=ad=c,ad,b c,bd BA=c BA=c,dada,b=cb=a,cb,d a,d b(2 2)AB=aAB=a,b1b1,22=a=1,a2,b1,b2。第5页,此课件共85页哦(ABAB)C=aC=1,cc,a2,cc,b 1,cc,b2,cc BC=1BC=1,2c=12c=c,2c。A A(BCBC)=a=a,1c,aa,2c,b b,1c,b b,2c。第6页,此课件共85页哦2.2.笛卡儿积的性质笛卡儿积的性质 1)1)对任意集合对任意集合A A,有,有AA=,A=A=。2)2)笛卡尔积不满足交换律,即一般的,当笛卡尔积不满足交换律,即一般的,当A A,
4、B B且且A AB B时,时,AAB BBBA A。3)3)笛卡尔积不满足结合律,即一般的,当笛卡尔积不满足结合律,即一般的,当A,B,CA,B,C时,时,(AAB)B)CC A(BCA(BC)。第7页,此课件共85页哦5)5)设设A,B,C,DA,B,C,D为为四四个个非非空空集集合合,则则ABAB CDCD的的充充分分必必要要条条件是:件是:A A C C且且B B D D。4)4)笛卡尔积关于交、并满足分配律。笛卡尔积关于交、并满足分配律。(1 1)AA(BCBC)=(ABAB)(ACAC)(2 2)AA(BCBC)=(ABAB)(ACAC)(3 3)()(ABAB)C=C=(ACAC)
5、(BCBC)(4 4)()(ABAB)C=C=(ACAC)(BCBC)第8页,此课件共85页哦2.2.定义定义 设设S S是是A A到到B B上的二元关系,称上的二元关系,称 x x y(yy(y BxBy S)S)为为S S的定义域,记作的定义域,记作D(S).D(S).称称yy x x(xAxxASyS)为为S S的值域,记作的值域,记作R(S)R(S)。1.1.定定义义 设设A A,B B是是两两个个集集合合,R R是是ABAB的的任任一一子子集集,则则称称R R为为从从A A到到B B的的一一个个二二元元关关系系,简简称称关关系系。特特别别当当A=BA=B时时,则则称称R R为为A A
6、上上的的二元关系(或二元关系(或A A上的关系)。上的关系)。第二节第二节 二元关系二元关系一、概念一、概念第9页,此课件共85页哦二、三种特殊关系:二、三种特殊关系:1.A1.A上的关系:上的关系:I IA A=a=a a a AA,称为,称为A A上的恒等关系。上的恒等关系。2.A2.A到到B B上的全关系:上的全关系:AB=a AB=b aAbBaAbB3.A3.A到到B B上的空关系上的空关系。第10页,此课件共85页哦三、关系的表示三、关系的表示1 1、集合形式、集合形式2 2、关系图形式(关系表示法)、关系图形式(关系表示法)1)1)将将A A,B B中元素称为结点,画为中元素称为
7、结点,画为 ;2)2)若若aRbR,画从,画从a a到到b b的有向弧;的有向弧;3)3)对对A A上的关系上的关系R R,若,若aRaR,画,画a a点的自回路。点的自回路。将涉及到二元关系将涉及到二元关系R R的集合元素及序偶按以上规定的集合元素及序偶按以上规定画出图,称为画出图,称为R R的关系图。的关系图。第11页,此课件共85页哦 注注:1)1)空关系:只有结点。空关系:只有结点。2)2)全关系:全关系:AB:A AB:A的每个结点到的每个结点到B B的任一结点均有有向弧。的任一结点均有有向弧。A A2 2:每个结点均有自回路,且任意两个不同结点均每个结点均有自回路,且任意两个不同结
8、点均有有向弧。有有向弧。3)3)恒等关系恒等关系I IA A:只有每个结点均有自回路。:只有每个结点均有自回路。第12页,此课件共85页哦解解 R R的关系图,如图所示:的关系图,如图所示:例例 A=1,2,3,4 A=1,2,3,4,B=5,6,7B=5,6,7,R=R=,作出,作出R R的关系图。的关系图。第13页,此课件共85页哦解解 A A上的关系图如图所示。上的关系图如图所示。例例 设设A=1A=1,2 2,3 3,44,R=1R=2,22,33,41。画出画出A A上的关系图。上的关系图。第14页,此课件共85页哦3 3、关系的矩阵表示、关系的矩阵表示 设设A=aA=a1 1,a,
9、a2 2,a,am m,B=b,B=b1 1,b,b2 2,b,bn n,R,R为为A A到到B B上的二元上的二元关系,称矩阵关系,称矩阵M MR R=(m=(mijij)mnmn为为R R的关系矩阵,其中的关系矩阵,其中 注注:1)1)空关系:空关系:M M空空=0=0;2)2)全关系:全关系:3)3)恒等关系:恒等关系:第15页,此课件共85页哦一、关系的基本运算一、关系的基本运算 例例 设设X=1X=1,2 2,3 3,4 4,55,若若A=xA=yx x与与y y的的差差能能被被2 2整整除除,B=xB=yx x与与y y的的差差为为正正且且能能被被3 3整整除除,求求ABAB,AB
10、AB,A-BA-B,B-AB-A,A A。第三节第三节 关系的运算关系的运算解解 A=1 A=1,13,15,22,2 4,31,33,35,42,4 4,51,53,55 B=4 B=1,52第16页,此课件共85页哦AB=1AB=1,13,15,22,24,3 1,33,35,41,42,4 4,51,52,53,55AB=AB=A-B=1A-B=1,13,15,22,24,3 1,33,35,42,44,5 1,53,55第17页,此课件共85页哦B-A=4B-A=1,52A=XA=X2 2-A-A =1 =2,14,21,23,25,3 2,34,41,43,45,5 2,54 注注:
11、A A到到B B上的关系的交并差补运算结果仍为上的关系的交并差补运算结果仍为A A到到B B上的关上的关系。系。第18页,此课件共85页哦二、关系的特殊运算二、关系的特殊运算 1.1.定义定义 设设R,SR,S分别是集合分别是集合A A到到B,BB,B到到C C上的二元关系,则上的二元关系,则R RS S称称为为R R和和S S的复合关系,表示为的复合关系,表示为R RS=S=xAzCxAzC y(yBRS)y(yBRS)A:A:复合运算(复合关系)复合运算(复合关系)第19页,此课件共85页哦例例 A=1,2,3,4,B=3,5,7,C=1,2,3,A=1,2,3,4,B=3,5,7,C=1
12、,2,3,R=R=,S=S=,.R RS=2S=2,43。如图所示:如图所示:第20页,此课件共85页哦 注注:a)a)复合运算不满足交换律,即复合运算不满足交换律,即R RS SR RS Sb)b)推推广广 设设R R是是从从A A上上的的关关系系,n,n为为整整数数,关关系系R R的的n n次次幂幂定定义义如下:如下:(1 1)R R0 0=x=xxA=IxA=IA A;(2 2)R Rn+1n+1=R=Rn nR R。从关系从关系R R的的n n次幂定义,可得出下面的结论:次幂定义,可得出下面的结论:(1 1)R Rn+mn+m=R=Rn nR Rm m;(2 2)()(R Rn n)m
13、 m=R=Rnmnm。第21页,此课件共85页哦定理定理 设设R,SR,S分别是从分别是从A A到到B B,B B到到C C的关系,其中的关系,其中A=aA=a1 1,a,a2 2,a,am m,B=bB=b1 1,b,b2 2,b,bn n,C=cC=c1 1,c,c2 2,c,ct t,而,而M MR R,M,MS S和和M MR RS S分别为关系分别为关系R,SR,S和和R RS S的关系矩阵,则有的关系矩阵,则有 M MR RS S=M=MR RMMS S其中其中为矩阵的乘法,而元素运算为布尔运算。为矩阵的乘法,而元素运算为布尔运算。2 2、复合运算与关系矩阵、复合运算与关系矩阵第2
14、2页,此课件共85页哦b)b)复合运算关于并满足分配律,即复合运算关于并满足分配律,即(1)R(1)R(ST)=R(ST)=RSRSRT T(2)(RS)(2)(RS)T=RT=RTSTST T复合运算关于交满足下面两式成立:复合运算关于交满足下面两式成立:(3)R(3)R(ST)(ST)R RSRSRT T(4)(RS)(4)(RS)T T R RTSTST T3 3、复合运算的性质、复合运算的性质a)a)复合运算满足结合律,即设复合运算满足结合律,即设R,S,TR,S,T分别是从分别是从A A到到B,BB,B到到C,CC,C到到D D的关系,则有的关系,则有R R(S(ST)=(RT)=(
15、RS)S)T T。第23页,此课件共85页哦1 1、定定义义 设设R R是是A A到到B B的的二二元元关关系系,如如果果将将R R中中每每个个序序偶偶的的第第一一元元素素和和第第二二元元素素的的顺顺序序互互换换,所所得得到到的的集集合合称称为为R R的逆关系,记为的逆关系,记为R R-1-1,即,即R R-1-1=y=x xRyRB.B.逆运算逆运算 注注:1)R1)R关系图中有向弧的方向反向就得关系图中有向弧的方向反向就得R R-1-1的关系图。的关系图。2)2)关系矩阵:关系矩阵:3)3)特殊关系的逆关系说明:特殊关系的逆关系说明:第24页,此课件共85页哦(1)(1)(R R-1-1)
16、-1-1=R=R(2)(R(2)(RS)S)-1-1=S=S-1-1R R-1-1(3)(RS)(3)(RS)-1-1=R=R-1-1SS-1-1(4)(RS)(4)(RS)-1-1=R=R-1-1SS-1-1(5)(5)(R)R)-1-1=(R(R-1-1)(6)(R-S)(6)(R-S)-1-1=R=R-1-1-S-S-1-1(7)(7)若若R R S S中,则中,则R R-1-1 S S-1-1。2 2、逆运算的性质、逆运算的性质第25页,此课件共85页哦有限集合上关系运算的矩阵形式小结有限集合上关系运算的矩阵形式小结1 1、并运算、并运算定理定理1 1:设:设R,SR,S均为有限集合均
17、为有限集合A A到到B B上的二元关系,则上的二元关系,则其中矩阵加法为常规矩阵加法,元素间的加法为布尔加法。其中矩阵加法为常规矩阵加法,元素间的加法为布尔加法。推论:设推论:设R Ri i(i=1,2,(i=1,2,k),k)均为有限集合均为有限集合A A到到B B上的二元关上的二元关系,则系,则第26页,此课件共85页哦2 2、交运算、交运算定理定理2 2:设:设R,SR,S均为有限集合均为有限集合A A到到B B上的二元关系,则上的二元关系,则其中其中“”为为H H乘法(对应相乘)乘法(对应相乘),元素间的乘法为布尔乘法。元素间的乘法为布尔乘法。【注】:【注】:1 1、H H乘法一般定义
18、:乘法一般定义:其中元素间的乘法为布尔乘法。其中元素间的乘法为布尔乘法。第27页,此课件共85页哦2 2、H H乘法满足以下性质:乘法满足以下性质:b b)分配律:)分配律:c c)结合律:)结合律:d d)其中其中e e)a a)交换律:)交换律:第28页,此课件共85页哦3 3、补运算、补运算定理定理3 3:设:设R R为有限集合为有限集合A A,B B上的二元关系,则上的二元关系,则其中其中“”为矩阵的余运算:为矩阵的余运算:。4 4、差运算、差运算定理定理4 4:设:设R R,S S都为都为A A到到B B上的二元关系,则上的二元关系,则.第29页,此课件共85页哦5 5、逆运算、逆运
19、算定理定理5 5:设:设R R为有限集合为有限集合A A到到B B上的二元关系,则上的二元关系,则。6 6、复合运算、复合运算定理定理6 6:设:设R R,S S分别为有限集合分别为有限集合A A,B B和和B B,C C上的二元关系,上的二元关系,则则其中其中“”为常规矩阵乘法,元素间的乘法和加法分别为常规矩阵乘法,元素间的乘法和加法分别为布尔乘法和布尔加法运算。为布尔乘法和布尔加法运算。第30页,此课件共85页哦定定义义 设设R R是是集集合合A A上上的的二二元元关关系系,如如果果对对于于每每个个x x A A,都都有有 R R,则称二元关系,则称二元关系R R是自反的。是自反的。第四节
20、第四节 关系的性质关系的性质一、自反性和反自反性一、自反性和反自反性 1 1、自反性、自反性【注】【注】R R在在A A上是自反的上是自反的 I IA A R RM MR R主对角线元素均为主对角线元素均为1 1。R R的关系图中任意结点均有自回路。的关系图中任意结点均有自回路。第31页,此课件共85页哦定义定义 设设R R是集合是集合A A上的二元关系,如果对于每个上的二元关系,如果对于每个x x A A,都有,都有 R R,则称二元关系,则称二元关系R R是反自反的。是反自反的。2 2、反自反性、反自反性【注】【注】R R在在A A上是反自反的上是反自反的 I IA ARR M MR R主
21、对角线元素均为主对角线元素均为0 0。R R的关系图中每个结点都无自回路。的关系图中每个结点都无自回路。第32页,此课件共85页哦定定义义 设设R R是是集集合合A A上上的的二二元元关关系系,若若对对任任意意xRyR,就就有有yRxR,则称二元关系,则称二元关系R R是对称的。是对称的。二、对称性和反对称性二、对称性和反对称性 1 1、对称性、对称性【注】【注】R R在在A A上是对称的上是对称的 R R-1-1=R=RM MR RM MR R。R R的关系图中任意不同结点间的有向弧要么成对出现的关系图中任意不同结点间的有向弧要么成对出现要么没有。要么没有。第33页,此课件共85页哦定义定义
22、 设设R R是集合是集合A A上的二元关系,若上的二元关系,若R,R,则则x=yx=y或或yx R,R,称二元关系称二元关系R R是反对称的。是反对称的。2 2、反对称性、反对称性【注】【注】R R在在A A上是反对称的上是反对称的 若若,RR,则,则x=yx=y。M MR R元素中若元素中若a aijij=1(i=1(ij),j),则则a ajiji=0=0。R R的关系图中不同结点间若有有向弧,则只有一条。的关系图中不同结点间若有有向弧,则只有一条。第34页,此课件共85页哦定义定义 设设R R是集合是集合A A上的二元关系,若上的二元关系,若xy,yRzR,就有,就有xRzR则称二元关系
23、则称二元关系R R在在A A上是传递的。上是传递的。3 3、传递性、传递性例例1 1:设:设A A为集合,为集合,A A上的二元关系为上的二元关系为R R,证明:,证明:2 2、R R是传递的是传递的。1 1、R R是反对称的是反对称的第35页,此课件共85页哦1 1、定定义义 设设R R是是集集合合A A上上的的关关系系,若若A A上上的的另另一一关关系系R R满满足:足:(1 1)R R是自反的(对称的、传递的);是自反的(对称的、传递的);(2 2)R R R R;(3 3)对对于于A A上上任任何何包包含含R R的的自自反反的的(对对称称的的、传传递递的的)关系关系R R,都有,都有R
24、 R R R。则称关系则称关系R R为为R R的自反(对称、传递)闭包。的自反(对称、传递)闭包。第五节第五节 关系的闭包关系的闭包一、关系闭包的概念一、关系闭包的概念第36页,此课件共85页哦【注】:【注】:a.a.闭包闭包R R是包含是包含R R的具有自反(对称,传递)的具有自反(对称,传递)性质的最小关系。性质的最小关系。b.b.记号记号:自反闭包自反闭包r(R);r(R);对称闭包对称闭包s(R);s(R);传递闭包传递闭包t(R).t(R).2 2、性质、性质1)1)设设R R是是A A上的关系,则上的关系,则a)Ra)R是自反的是自反的r(R)=R.r(R)=R.b)Rb)R是对称
25、的是对称的s(R)=R.s(R)=R.c)Rc)R是传递的是传递的t(R)=R.t(R)=R.第37页,此课件共85页哦2)2)设设R R,S S是非空集合是非空集合A A上的关系,且上的关系,且R R S S,则,则a a)r r(R R)r r(R R););b b)s s(R R)s s(R R););c c)t t(R R)t t(R R)。)。3)3)设设R R是非空集合是非空集合A A上的关系,则上的关系,则a a)rsrs(R R)=sr=sr(R R););b b)rtrt(R R)=tr=tr(R R););c c)tsts(R R)st st(R R)。)。第38页,此课件
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第四章 关系精选PPT 第四 关系 精选 PPT
限制150内