二元关系PPT讲稿.ppt-得力文库

资源描述

《二元关系PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《二元关系PPT讲稿.ppt（148页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、二元关系二元关系第1页，共148页，编辑于2022年，星期四第三篇第三篇二元关系二元关系第第6 6章章二元关系二元关系第2页，共148页，编辑于2022年，星期四6.0 6.0 内容提要内容提要关系的性质关系的性质3关系的闭包运算关系的闭包运算4二元关系二元关系1关系的运算关系的运算2第3页，共148页，编辑于2022年，星期四6.16.1本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1 二元关系的二元关系的概念和表示概念和表示2 2 关系的复合关系的复合与逆运算与逆运算3 3 关系的性质关系的性质31 n1 n重有序组重有序组2 n2 n个集合的个集合的笛卡儿积笛

2、卡儿积3 n3 n重有序组重有序组相等的判定相等的判定21 1 关系的闭包关系的闭包运算运算第4页，共148页，编辑于2022年，星期四第三篇第三篇二元关系二元关系关系理论历史悠久。它关系理论历史悠久。它与集合论、数理逻辑、组与集合论、数理逻辑、组合学、图论和布尔代数合学、图论和布尔代数都有密切的联系。都有密切的联系。关系是关系是日常生活以及数学日常生活以及数学中的一个基本概念，例如：中的一个基本概念，例如：兄弟关系，师生关系、位置关系、大小关系、等于关系、兄弟关系，师生关系、位置关系、大小关系、等于关系、包含关系等。包含关系等。第5页，共148页，编辑于2022年，星期四第三篇第三篇二

3、元关系二元关系另外，关系理论还广泛用于另外，关系理论还广泛用于计算机科学技术计算机科学技术，如，如l计算机程序的输入、输出关系；计算机程序的输入、输出关系；l数据库的数据特性关系；数据库的数据特性关系；l数据结构本身就是一个关系等。数据结构本身就是一个关系等。在某种意义下，在某种意义下，关系是有联系的一些对象相互之间的关系是有联系的一些对象相互之间的各种比较行为。各种比较行为。第6页，共148页，编辑于2022年，星期四6.2 6.2 二元关系二元关系6.2.1 6.2.1 序偶与笛卡尔积序偶与笛卡尔积上上,下下；左左，右右；3434；中中国国地地处处亚亚洲洲；平平面面上上点点的的坐坐标标（x

4、,yx,y）等。）等。特征：特征：成对出现、具有一定的顺序。成对出现、具有一定的顺序。定定义义6.2.16.2.1由由两两个个元元素素x,yx,y按按照照一一定定的的次次序序组组成成的的二二元元组组称称为为有有序序偶偶对对(序序偶偶),记记作作,其其中中x x为为第一个元素，第一个元素，y y为第二个元素。为第二个元素。第7页，共148页，编辑于2022年，星期四例例6.2.16.2.1用序偶表示下列语句中的次序关系用序偶表示下列语句中的次序关系(1)(1)平面上点平面上点A A的横坐标是的横坐标是x,x,纵坐标是纵坐标是y,x,yRy,x,yR；(2)(2)成都是四川的省会；成都是四川的省会

5、；(3)(3)英语课本在书桌上；英语课本在书桌上；(4)(4)左，右关系。左，右关系。解解各语句的序偶表示如下：各语句的序偶表示如下：(1)(1)，x,yRx,yR；(2)(2)；(3)(3)；(4)(4)。第8页，共148页，编辑于2022年，星期四序偶相等判定定理序偶相等判定定理定义定义6.2.2 6.2.2 给定序偶给定序偶和和，如果如果a=ca=c，b=db=d，则，则=。第9页，共148页，编辑于2022年，星期四N N重有序组重有序组定义定义6.2.36.2.3由由n n个元素个元素a a1 1,a,a2 2,a,a3 3,a,an n按照一定次序组成按照一定次序组成的的n n元

6、组称为元组称为n n重有序组重有序组(n-Type)(Vector)(n-Type)(Vector)，记作记作:a 例例6.2.26.2.2 用用n n重有序组描述下列语句。重有序组描述下列语句。（1 1）中国四川成都电子科技大学计算机学院；）中国四川成都电子科技大学计算机学院；（2 2）20062006年年9 9月月1010日日1818点点1616分分2525秒；秒；（3 3）1616减减5 5再加再加3 3除以除以7 7等于等于2 2。解解：（：（1 1）（2 2）；（3 3）。第10页，共148页，编辑于2022年，星期四N N重有序组重有序组定定义义6.2.46.2.4给给定定n

7、n重重有有序序组组和和b1,b2,bn。如如果果aiaibi(ibi(i1,2,1,2,，n)n)，则则=b1,b2,=bn。第11页，共148页，编辑于2022年，星期四笛卡尔乘积笛卡尔乘积定义定义6.2.56.2.5 设设A A，B B是两个集合，称集合：是两个集合，称集合：AB AB|(xA)(yB)|(xA)(yB)为集合为集合A A与与B B的的笛卡尔积笛卡尔积(DescartesProduct)(DescartesProduct)。注意注意：（1 1）集合）集合A A与与B B的笛卡儿积的笛卡儿积ABAB仍然是集合；仍然是集合；（2 2）集合）集合ABAB中的元素是序偶，序偶

8、中的第一个元中的元素是序偶，序偶中的第一个元素取自素取自A A，第二个元素取自，第二个元素取自B B。第12页，共148页，编辑于2022年，星期四例例6.2.36.2.3设设A=a,B=b,c,C=,D=1,2A=a,B=b,c,C=,D=1,2，请分别请分别写出下列笛卡儿积中的元素。写出下列笛卡儿积中的元素。（1 1）AB,BAAB,BA；（；（2 2）AC,CAAC,CA；（3 3）A(BD),(AB)DA(BD),(AB)D。解解根据根据笛卡儿积的定义笛卡儿积的定义，有，有（1 1）AB=AB=,BA=,BA=,；（2 2）AC=AC=,CA=,CA=；第13页，共148页，编辑于2

9、022年，星期四例例6.2.3 6.2.3 解（续）解（续）（3 3）因为）因为BD=BD=,，所以所以A(BD)=A(BD)=a,a,a,a,a,a,a,a,。同理同理，(AB)D=(AB)D=,1,2,1,2,1,2,1,2。第14页，共148页，编辑于2022年，星期四注意注意由例由例6.2.36.2.3我们可以看出：我们可以看出：（1 1）笛卡儿积不满足交换律；）笛卡儿积不满足交换律；（2 2）AB=AB=当且仅当当且仅当A=A=或者或者B=B=；（3 3）笛卡儿积不满足结合律；）笛卡儿积不满足结合律；（4 4）对有限集）对有限集A,BA,B，有，有|AB|=|BA|=|A|B|AB|

10、=|BA|=|A|B|第15页，共148页，编辑于2022年，星期四集合相等集合相等两个集合互相包含两个集合互相包含等式成立等式成立两个集合相等两个集合相等定理定理6.2.16.2.1设设A,B,CA,B,C是任意三个集合，则是任意三个集合，则（1 1）A(BC)=(AB)(AC)A(BC)=(AB)(AC)；（2 2）(BC)A=(BA)(CA)(BC)A=(BA)(CA)；（3 3）A(BC)=(AB)(AC)A(BC)=(AB)(AC)；（4 4）(BC)A=(BA)(CA)(BC)A=(BA)(CA)。分析分析显然，待证等式两端都是集合显然，待证等式两端都是集合第16页，共148页，编

11、辑于2022年，星期四定理定理6.2.1 6.2.1 分析分析对（对（1 1）A(BC)=(AB)(AC)A(BC)=(AB)(AC)A(BC)A(BC)(AB)(AC),(AB)(AC)(AB)(AC),(AB)(AC)A(BC)A(BC)利用利用按定义证明方法按定义证明方法，首先叙述包含关系的定义，即首先叙，首先叙述包含关系的定义，即首先叙述述A(BC)A(BC)(AB)(AC)(AB)(AC)的定义：的定义：对任意对任意A(BC)A(BC)，有有(AB)(AC)(AB)(AC)，则则A(BC)A(BC)(AB)(AC)(AB)(AC)。同理可分析同理可分析(AB)(AC)(AB)(AC)

12、A(BC)A(BC)。第17页，共148页，编辑于2022年，星期四定理定理6.2.1 6.2.1 证明证明（1 1）对任意）对任意A(BC)A(BC)，由由笛卡儿积笛卡儿积的定义知，的定义知，xAxA且且yBCyBC；由由并运算并运算定义知，定义知，yByB或者或者yCyC。于是有于是有xAxA且且yByB或者或者xAxA且且yCyC。从而，从而，ABAB或者或者ACAC。即即(AB)(AC)(AB)(AC)，所以，所以，A(BC)A(BC)(AB)(AC)(AB)(AC)。第18页，共148页，编辑于2022年，星期四定理定理6.2.1 6.2.1 证明（续）证明（续）另一方面，对任意另一

13、方面，对任意(AB)(AC)(AB)(AC)，由由并运算定义并运算定义知知,AB,AB或者或者ACAC。由由笛卡儿积的定义笛卡儿积的定义知知,xA,xA且且yByB或或xAxA且且yCyC。进一步有进一步有xAxA且且yBCyBC，从而从而A(BC)A(BC)。所以所以(AB)(AC)(AB)(AC)A(BC)A(BC)。于是，根据定理于是，根据定理1.2.21.2.2，有有A(BC)=(AB)(AC)A(BC)=(AB)(AC)。(2)(2)、(3)(3)和和(4)(4)的证明作为练习，自证。的证明作为练习，自证。第19页，共148页，编辑于2022年，星期四定理定理6.2.26.2.2设设

14、A,B,C,DA,B,C,D是任意四个集合，则是任意四个集合，则(AB)(AB)(CD)(CD)A A C C，B B D D。证明证明充分性充分性()：对任意对任意ABAB，有，有xAxA且且yByB。又因为又因为A A C C，B B D D，所以有，所以有xCxC且且yDyD，即，即CDCD，从而，从而(AB)(AB)(CD)(CD)。第20页，共148页，编辑于2022年，星期四定理定理6.2.2 6.2.2 证明（续）证明（续）设设A,B,C,DA,B,C,D是任意四个集合，则是任意四个集合，则(AB)(AB)(CD)(CD)A A C C，B B D D。证明证明必要性必要性(

15、)：对任意的对任意的xAxA，yByB，有，有ABAB。又因为又因为(AB)(AB)(CD)(CD)，所以，所以CDCD。根据笛卡儿积的定义有根据笛卡儿积的定义有xCxC且且yDyD，从而，从而A A C C，B B D D。综上所述，定理成立。综上所述，定理成立。第21页，共148页，编辑于2022年，星期四定义定义6.2.66.2.6设设A A1 1,A,A2 2,A,An n是是n n个集合，称集合个集合，称集合A A1 1AA2 2AAn n =a=|(a|(ai iAAi i)i1,2,3,n)i1,2,3,n为集合为集合A A1 1,A,A2 2,A,An n的的笛卡儿积笛卡儿积(

16、DescartesProduct)DescartesProduct)当当A A1 1=A=A2 2=A=An n=A=A时，有时，有A A1 1AA2 2AAn n=A An n。第22页，共148页，编辑于2022年，星期四定理定理6.2.36.2.3当集合当集合A A1 1,A,A2 2,A,An n都是都是有限集有限集时，时，|A|A1 1AA2 2AAn n|=|A|=|A1 1|A|A2 2|A|An n|。第23页，共148页，编辑于2022年，星期四6.2.26.2.2关系的定义关系的定义问题：问题：某学校组织学生看电影，电影院里共有某学校组织学生看电影，电影院里共有n n个个座

17、位，看电影的学生共有座位，看电影的学生共有m m个（个（mnmn），每个学生），每个学生坐一个座位。请问，坐一个座位。请问，怎样表示学生和座位之间的从怎样表示学生和座位之间的从属关系？属关系？a1a2a3amABbnb3b2b10图6.2.1假设假设A,BA,B分别表示某学校所有分别表示某学校所有学生的集合学生的集合和电影院里所有和电影院里所有座位的集合座位的集合，即，即A=aA=a1 1,a,a2 2,a,am m,B=,B=bb1 1,b,b2 2,b,bn n。第24页，共148页，编辑于2022年，星期四定义定义6.2.7 6.2.7 设设A,BA,B为两个非空集合，称为两个非空集合，

18、称ABAB的任何的任何子集子集R R为为从从A A到到B B的二元关系的二元关系，简称关系，简称关系(Relation)(Relation)。如如A AB B，则称，则称R R为为A A上的二元关系上的二元关系。二元关系二元关系设一有序对设一有序对：若若RR，则记为则记为xRyxRy，读作读作“x“x对对y y有关系有关系R”R”；若若 R R，则记为则记为xRyxRy，读作读作“x“x对对y y没有关系没有关系R”R”。注：注：当当R=R=时，称时，称R R为为空关系空关系(emptyrelation)；当当R=A BR=A B时，则称时，则称R R为为全关系全关系(TotalRelatio

19、n)。第25页，共148页，编辑于2022年，星期四例例6.2.46.2.4假设假设A=a,bA=a,b，B=c,dB=c,d，写出从，写出从A A到到B B的所有不的所有不同关系。同关系。解解因为因为A=a,b,B=c,dA=a,b,B=c,d，所以，所以AB=,AB=,。于是。于是ABAB的所的所有不同子集为：有不同子集为：00元子集：元子集：；11元子集：元子集：,；22元子集：元子集：,b,c,；第26页，共148页，编辑于2022年，星期四例例6.2.4 6.2.4 解（续）解（续）33元子集：元子集：,；44元子集：元子集：,。注意：注意：当集合当集合A,BA,B都是有限集时，都

20、是有限集时，ABAB共有共有2 2|A|A|B|B|个不同个不同的子集，即，的子集，即，从从A A到到B B的不同关系共有的不同关系共有2 2|A|A|B|B|个。个。第27页，共148页，编辑于2022年，星期四其中，其中，A A称为称为R R的的前域前域，B B称为称为R R的的后后域。域。D D A A，C C B B满足：满足：D Dx|x|RR，C Cy|y|RR，称，称D D为为R R的的定义域定义域，记为，记为D DdomRdomR；称称C C为为R R的的值域值域,记记C CranRranR；并称并称fldRfldRDCDC为为R R的域的域。第28页，共148页，编辑于202

21、2年，星期四假假设设A=aA=a1 1,a,a2 2,a,a3 3,a,a4 4,a,a5 5,a,a6 6,B=b,B=b1 1,b,b2 2,b,b3 3,b,b4 4,b,b5 5,C=aC=a3 3,a,a4 4,a,a6 6,D=b,D=b1 1,b,b2 2,b,b4 4,b,b5 5,R=aR=,。显显然，然，R R CDCD ABAB。第29页，共148页，编辑于2022年，星期四求定义在求定义在Z Z上关系的定义域、值域和域。上关系的定义域、值域和域。（1 1）R R1 1=|(x,yZ)y=x=|(x,yZ)y=x2 2；（2 2）R R2 2=|(x,yZ)|x|=|y|

22、=7=|(x,yZ)|x|=|y|=7。解解（1 1）domRdomR1 1=Z,ranR=Z,ranR1 1=Z=Z+0,fldR0,fldR1 1=Z=Z；（2 2）domRdomR2 2=7,7,ranR=7,7,ranR2 2=7,7,=7,7,fldR fldR2 2=7,7=7,7。例例6.2.56.2.5第30页，共148页，编辑于2022年，星期四例例6.2.66.2.6设设H=f,m,s,dH=f,m,s,d表示一个家庭中父母子女四个人表示一个家庭中父母子女四个人的集合，确定的集合，确定H H上的一个长幼关系上的一个长幼关系R RH H，指出该关系，指出该关系的定义域、值域和

23、域。的定义域、值域和域。解解 R RH H=,=,；domRdomRH H=f,m,ranR=f,m,ranRH H=s,d=s,d，fldRfldRH H=f,m,s,d=f,m,s,d定义定义6.2.8 6.2.8 设设A A1 1,A,A2 2,A,An n为为n n个非空集合，称个非空集合，称A A1 1AA2 2AAn n的任意子集的任意子集R R为以为以A A1 1AA2 2AAn n为为基的基的n n元关系元关系(n-Relation)(n-Relation)。第31页，共148页，编辑于2022年，星期四6.2.36.2.3关系的表示法关系的表示法1.1.集合表示法集合表示法（

24、枚举法和叙述法枚举法和叙述法）例例6.2.76.2.7（1 1）设）设A=a,B=b,cA=a,B=b,c，用枚举法写出从，用枚举法写出从A A到到B B的不同关系；的不同关系；（2 2）用叙述法写出定义在）用叙述法写出定义在R R上的上的“相等相等”关系。关系。解解（1 1）A A到到B B的不同关系有：的不同关系有：R R1 1=,R,R2 2=,=,R R3 3=,R=,R4 4=,=,；（2 2）设）设R R上的上的“相等相等”关系为关系为S S，则，则S=|(x,yR)(x=y)S=|(x,yR)(x=y)。第32页，共148页，编辑于2022年，星期四6.2.3 6.2.3 关系的

25、表示法关系的表示法2.2.关系图法关系图法（1 1）A AB B设设A Aaa1 1,a,a2 2,.,a,.,an n,B,Bbb1 1,b,b2 2,.,b,.,bn n，R R是是从从A A到到B B的一个二元关系，则规定的一个二元关系，则规定R R的关系图如下：的关系图如下：.设设a a1 1,a,a2 2,.,a,.,an n和和b b1 1,b,b2 2,.,b,.,bn n分分别别为为图图中中的的结结点点，用用“。”表示表示；.如如a R,R,则从则从a ai i到到b bj j可用有向边可用有向边a ai i。b bj j相连。相连。a 为对应图中的有向边。为对应图中的有向边。

26、第33页，共148页，编辑于2022年，星期四（2)A=B2)A=B设设A AB=aB=，R R是是A A上的关系，则上的关系，则R R的关的关系图规定如下：系图规定如下：.设设a a1 1,a,a2 2,.,a,.,an n为图中节点，用为图中节点，用“。”表示表示.如如a R,R,则从则从a ai i到到a aj j可用有向边可用有向边a ai i。b bj j相连。相连。a 为对应图中的有向边为对应图中的有向边。.如如a R,R,则从则从a ai i到到a ai i用一带箭头的小圆环用一带箭头的小圆环表示，即：表示，即：a ai i2.2.关系图法（关系图法（续）续）第34页，共148页

27、，编辑于2022年，星期四2图图6.2.3244336134图图6.2.4例例6.2.86.2.8试用关系图表示下面的关系。试用关系图表示下面的关系。（1 1）设）设A=2,3,4A=2,3,4，B=3,4,5,6B=3,4,5,6，则，则A A到到B B之间之间的一种的一种整除关系整除关系:R R1 1=,=,（2 2）假设）假设A=1,2,3,4A=1,2,3,4，则，则A A上的上的小于等于关系小于等于关系:R R2 2=,2,3,。第35页，共148页，编辑于2022年，星期四设设A=aA=a1 1,a,a2 2,.,a,.,an n,B=b,B=b1 1,b,b2 2,.,b,.,b

28、m m,R,R是从是从A A到到B B的一个二元关系，称矩阵的一个二元关系，称矩阵M MR R（r rijij)nmnm为关为关系系R R的的关系矩阵关系矩阵(Relation Matrix)(Relation Matrix)，其中，其中又称又称M MR R为为R R的的邻接矩阵邻接矩阵(Adjacency Matrix)(Adjacency Matrix)。3.3.关系矩阵关系矩阵注意：注意：A A中元素序号中元素序号对应矩阵元素的对应矩阵元素的行下标行下标，B B中元素序号中元素序号对应矩阵元素的对应矩阵元素的列下标列下标；关系矩阵是关系矩阵是0-10-1矩阵，称为矩阵，称为布尔矩阵布尔矩

29、阵。第36页，共148页，编辑于2022年，星期四例例6.2.96.2.9设设A=1,2,3,4A=1,2,3,4，考虑考虑A A上的上的整除关系整除关系R R和和等于关系等于关系S S。（1 1）试写出）试写出R R和和S S中的所有元素；中的所有元素；（2 2）试写出）试写出R R和和S S的关系矩阵。的关系矩阵。第37页，共148页，编辑于2022年，星期四例例6.2.96.2.9解解（1 1）根据整除关系和等于关系的定义，有）根据整除关系和等于关系的定义，有 R=,R=,S=,S=,。（2 2）设）设R R和和S S的关系矩阵分别为的关系矩阵分别为M MR R和和M MS S，则有，

30、则有第38页，共148页，编辑于2022年，星期四布尔矩阵的运算布尔矩阵的运算定义定义6.2.96.2.9 如果如果A=(aA=(aijij)和和B=(bB=(bijij)是两个是两个mnmn矩阵矩阵,则则A A和和B B的并的并(join)(join)是矩阵是矩阵AB=C=(cAB=C=(cijij),),其中：其中：。(6.2.2)(6.2.2)定义定义6.2.106.2.10 如果如果A=(aA=(aijij)和和B=(bB=(bijij)是两个是两个mnmn矩阵矩阵,则则A A和和B B的交的交(meet)(meet)是矩阵是矩阵AB=C=(cAB=C=(cijij),),其中：其中

31、：。(6.2.3)(6.2.3)第39页，共148页，编辑于2022年，星期四布尔矩阵的运算布尔矩阵的运算(续续)定义定义6.2.116.2.11 如果如果A=(aA=(aijij)是是mpmp矩阵，矩阵，B=(bB=(bijij)是是pnpn矩阵，矩阵，则则A A和和B B的布尔积的布尔积(Boolean product)(Boolean product)是矩阵是矩阵A A B=C=B=C=(c(cijij),),其中：其中：两个布尔矩阵可进行并和交运算的前提两个布尔矩阵可进行并和交运算的前提是是有相同的行数和列数有相同的行数和列数；两个布尔矩阵可进行布尔积运算的前提是两个布尔矩阵可进行布尔

32、积运算的前提是前一矩阵的列数等于后一矩阵的行数前一矩阵的列数等于后一矩阵的行数。第40页，共148页，编辑于2022年，星期四例例6.2.106.2.10令令、和和。计算计算（1 1）ABAB；（2 2）ABAB；（3 3）ACAC。（1 1）（2 2）（3 3）第41页，共148页，编辑于2022年，星期四6.2.5 6.2.5 关系的应用关系的应用集合集合A A到集合到集合B B上的关系可以看成是列出了集合上的关系可以看成是列出了集合A A中中的一些元素与集合的一些元素与集合B B中的相关元素的中的相关元素的表表(table)(table)。例例6.2.116.2.11 试用关系表示图

33、试用关系表示图6.2.56.2.5。dbcfae图图6.2.5解解图图6.2.56.2.5可以用关系表示如下：可以用关系表示如下：,。第42页，共148页，编辑于2022年，星期四例例6.2.126.2.12设集合设集合A=A=张红，李明，王强，程飞，赵伟张红，李明，王强，程飞，赵伟，B=B=离散数学，操作系统，计算机图形学离散数学，操作系统，计算机图形学，R=R=，试用表的形式表示关系试用表的形式表示关系R R。解解关系关系R R的表的表示形式见表的表的表示形式见表6.2.16.2.1。学生课程张红离散数学李明离散数学王强操作系统程飞操作系统赵伟计算机科学张红算法分析李明组合数学王强数据

34、结构程飞组合数学赵伟计算机图形学第43页，共148页，编辑于2022年，星期四例例6.2.136.2.13请分别将下列表请分别将下列表6.2.26.2.2和和6.2.36.2.3表示的关系改写为关系集合表示表示的关系改写为关系集合表示形式。形式。表表6.2.2 6.2.2 表表6.2.36.2.38840锤子9921钳子452油漆2207地毯a3b1b4c1解解（1 1）设表）设表6.2.26.2.2表示的关系为表示的关系为R R1 1，则，则R R1 1=8840,=,；(2)(2)设表设表6.2.36.2.3表示的关系为表示的关系为R R2 2，则，则R R2 2=,=,第44页，共14

35、8页，编辑于2022年，星期四例例6.2.1 6.2.1 请将下列关系改写为表。请将下列关系改写为表。（1 1）R=,R=,；（2 2）在）在1,2,31,2,3上定义关系上定义关系R R：如果：如果x x2 2y y，则，则RR。解（解（1 1）关系）关系R R的表表示的表表示形式见表形式见表6.2.46.2.4；（2 2）由题意得）由题意得R=,R=,，其对应的表见表其对应的表见表6.2.56.2.5a6b2a1c111213122233233 表表6.2.4 6.2.4 表表6.2.56.2.5 第45页，共148页，编辑于2022年，星期四6.3 6.3 关系的运算关系的运算设设R R

37、R S,S R,RS,RS,R S,S R,。第47页，共148页，编辑于2022年，星期四例例6.3.1 6.3.1 解解RS=,RS=,；RS=|(xRy)(xSy)=RS=|(xRy)(xSy)=；RS=|(xRy)(xy)=RS=|(xRy)(xy)=,；=A =A2 2R=,R=,d,b,=,=,c,d,。第48页，共148页，编辑于2022年，星期四6.3.1 6.3.1 关系的复合运算关系的复合运算定义定义6.3.1 6.3.1 设设A,B,CA,B,C是三个集合，是三个集合，R R是从是从A A到到B B的关系的关系(R:AB)(R:AB)，S S是从是从B B到到C C的关系

38、的关系(S:BC)(S:BC)，则，则R R与与S S的的复复合关系合关系(合成关系合成关系)()(Composite)RComposite)R S S是从是从A A到到C C的关的关系，并且：系，并且：R R S S|xAzC|xAzC (y)y)(yBxRyySz)(yBxRyySz)运算运算“”称为称为复合运算复合运算(CompositeOperation)(CompositeOperation)。第49页，共148页，编辑于2022年，星期四6.3.1 6.3.1 关系的复合运算关系的复合运算1.R1.R和和S S是可复合的是可复合的 R R的的后域后域和和S S的的前域前域完全相完全

39、相同；同；2.RoS2.RoS的前域是的前域是R R的前域的前域A A，后域是，后域是S S的后域的后域C C；3.3.RoS=RoS=对对任意的任意的xAxA和和zCzC，不存在不存在yByB，使得使得xRyxRy和和ySzySz同时成立同时成立。4.oR=Ro=4.oR=Ro=第50页，共148页，编辑于2022年，星期四例例6.3.26.3.2试判断下列关系是否是两个关系的复合，如果是，试判断下列关系是否是两个关系的复合，如果是，请指出对应的两个关系。请指出对应的两个关系。（1 1）“祖孙祖孙”关系；关系；（2 2）“舅甥舅甥”关系；关系；（3 3）“兄妹兄妹”关系。关系。解（解（1 1

40、）“祖孙祖孙”关系关系是是“父女父女”关系关系和和“母子母子”关系关系的复合；的复合；（2 2）“舅甥舅甥”关系关系是是“兄妹兄妹”关系关系和和“母子母子”关系关系的复合；的复合；（3 3）不是。）不是。第51页，共148页，编辑于2022年，星期四例例6.3.36.3.3设设A=a,b,c,d,B=b,c,d,C=a,b,d,A=a,b,c,d,B=b,c,d,C=a,b,d,R=,R=,是是A A到到B B的关系，的关系，S=,S=,是是B B到到C C的关系。的关系。试用关系的试用关系的三种表示方法三种表示方法求求R R S S。解（解（1 1）R R S=,S=,；（2 2）R R S

41、 S的关系图如图的关系图如图6.3.26.3.2所示，其中图所示，其中图6.3.16.3.1是以是以y y为为“桥梁桥梁”的情形。据图的情形。据图6.3.26.3.2得得R R S=,S=,；bSRoSRabcdabcddcabdabd图图6.3.1 图图6.3.2第52页，共148页，编辑于2022年，星期四例例6.3.46.3.4设设A=1,2,3,4A=1,2,3,4，R=R=,S=,T=,S=,T=,是是A A上的三个关系。上的三个关系。计算计算（1 1）RoSRoS和和SoRSoR；(1)RoS=,o,(1)RoS=,o,=,=,SoR=,o,SoR=,o,=,=,第53页，共148

42、页，编辑于2022年，星期四例例6.3.46.3.4设设A=1,2,3,4A=1,2,3,4，R=,S=R=,S=,T=,T=,是是A A上的三个关上的三个关系。系。计算计算（2 2）(RoS)oT(RoS)oT和和Ro(SoT)Ro(SoT)。(2)(RoS)oT=(2)(RoS)oT=(,o,o ,)o,o,=,o,=,o,=,=,Ro(SoT)=,Ro(SoT)=,=(RoS)oT=(RoS)oT第54页，共148页，编辑于2022年，星期四定理定理6.3.16.3.1设设A A、B B、C C和和D D是任意四个集合，是任意四个集合，R R、S S和和T T分别是从分别是从A A到到B

43、 B，B B到到C C和和C C到到D D的二元关系，则的二元关系，则（1 1）(RoS)oT=Ro(SoT)(RoS)oT=Ro(SoT)；（2 2）I IA AoR=RoIoR=RoIB B=R=R，其中，其中I IA A和和I IB B分别是分别是A A和和B B上上的恒等关系。的恒等关系。分析：二元关系是集合，二元关系的复合是关系，从而也是集分析：二元关系是集合，二元关系的复合是关系，从而也是集合，因此上面两式就是证明两个集合相等。根据集合相等的合，因此上面两式就是证明两个集合相等。根据集合相等的定义，有定义，有A=B A=B A A B B并且并且B B A A，A A B B x

44、x A A，有，有x x B B。第55页，共148页，编辑于2022年，星期四定理定理6.3.1 6.3.1 证明（证明（1 1）(RoS)oT=Ro(SoT)(RoS)oT=Ro(SoT)(1)(1)任意任意(R(R S)S)T T，由由“”知知,至少存在至少存在cC,使得使得R S,T.对对RR S S，同样，同样至少存一个至少存一个bBbB，使得，使得RR，SS。于是于是,由由S,T,S,T,有有SS T T，由由RR和和SS T T，知，知RR(S(S T),T),所以所以(R(R S)S)T T R R(S(S T)T)。同理可证：同理可证：R R(S(S T)T)(R(R S)S

45、)T T。由集合性质知：由集合性质知：(R(R S)S)T TR R(S(S T)T)。构造性证明方法构造性证明方法第56页，共148页，编辑于2022年，星期四定理定理6.3.1 6.3.1 证明（证明（2 2）I IA AoR=RoIoR=RoIB B=R=R（2 2）任取任取IIA AoRoR，其中，其中aAaA，bBbB，由，由“o”o”的定义知，存在的定义知，存在aAaA，使得，使得IIA A且且RR，从而有，从而有I IA A o o R R R R。反过来，任取反过来，任取RR，由，由I IA A的定义知，的定义知，IIA A ，即，即IIA AoRoR。从而从而RoIRoIA

46、A R R。于是由定理于是由定理1.2.21.2.2知知,I,IA Ao o R R=R R。同理可证同理可证RoIRoIB B R R。于是于是I IA AoR=RoIoR=RoIB B=R=R得证。得证。第57页，共148页，编辑于2022年，星期四设设A A、B B、C C和和D D是任意四个集合，是任意四个集合，R R是从是从A A到到B B的关系，的关系，S S1 1，S S2 2是从是从B B到到C C的关系，的关系，T T是从是从C C到到D D的关系，则：的关系，则：1)、R(S1S2)=(R S1)(R S2)2)、R(S1S2)(R S1)(R S2)3)、(S1S2)T=

47、(S1 T)(S2 T)4)、(S1S2)T (S1 T)(S2 T)定理定理6.3.26.3.2第58页，共148页，编辑于2022年，星期四证明：证明：对任意对任意(S1S2)(S1S2)T T，则由复合运算知，则由复合运算知，至少存在至少存在cCcC,使得使得(S1S2)(S1S2)，TT。即：即：S1,S1,且且S2S2。因此，由因此，由S1,S1,且且TT，则有：，则有：(S1 (S1 T),T),由由S2,S2,且且TT，则有：，则有：(S2(S2 T)T)。所以，所以，(S1(S1 T)(S2T)(S2 T)T)。即，。即，(S1S2)(S1S2)T T(S1(S1 T)(S2T

48、)(S2 T)T)。定理定理6.3.26.3.24)、(S1S2)T(S1 T)(S2 T)第59页，共148页，编辑于2022年，星期四试说明下面的包含关系不一定成立。试说明下面的包含关系不一定成立。（1 1）(RoS(RoS1 1)(RoS)(RoS2 2)Ro(SRo(S1 1SS2 2)（2 2）(S(S1 1oT)(SoT)(S2 2oToT)(S S1 1SS2 2)oT)oT例例6.3.56.3.5分析：分析：如要说明某一事实如要说明某一事实不一定不一定成立，成立，则可举一反例加以说明。则可举一反例加以说明。第60页，共148页，编辑于2022年，星期四设设A a,B b1,b2

49、,C c,关系关系R，S1，S2定义如下：定义如下：R,S1,S2。则由于则由于S1S2,所以所以R(S1S2)R ,但但(R S1),(R S2)，所以所以(R S1)(R S2)，即即(RoS(RoS1 1)(RoS)(RoS2 2)Ro(SRo(S1 1SS2 2),),这说明这说明(RoS(RoS1 1)(RoS)(RoS2 2)Ro(SRo(S1 1SS2 2)不一定成立。不一定成立。例例6.3.5 6.3.5 解解（1 1）(RoS(RoS1 1)(RoS)(RoS2 2)RoRo(S(S1 1SS2 2)不一定成立不一定成立第61页，共148页，编辑于2022年，星期四设设A a

50、,B b1,b2,C c,关系关系S1，S2，T定义如下：定义如下：S1,S2,T,。则由于则由于S1S2,所以所以(S1S2)T T,但但(S1 T),(S2 T)，所以所以(S1 T)(S2 T)，即即(S1 T)(S2 T)(S1S2)T，这说明这说明(S(S1 1oT)(SoT)(S2 2oToT)(S S1 1SS2 2)oT)oT不一定成立。不一定成立。例例6.3.5 6.3.5 解（解（2 2）(S(S1 1oT)(SoT)(S2 2oToT)(S S1 1SS2 2)oT)oT不一定成立不一定成立第62页，共148页，编辑于2022年，星期四说明说明如果说明某事实一定成立，则一

展开阅读全文