二元关系精品课件

1、二元关系第1页，共148页，2022年，5月20日，8点2分，星期日第三篇 二元关系第6章 二元关系第2页，共148页，2022年，5月20日，8点2分，星期日6.0 内容提要关系的性质3关系的闭包运算4二元关系1关系的运算2第3页，共148页，2022年，5月20日，8点2分，星期日6.1本章学习要求重点掌握一般掌握了解11 二元关系的概念和表示2 关系的复合与逆运算3 关系的性质31 n重有序组2 n个集合的笛卡儿积3 n重有序组相等的判定21 关系的闭包运算第4页，共148页，2022年，5月20日，8点2分，星期日第三篇 二元关系 关系理论历史悠久。它与集合论、数理逻辑、组合学、图论和

2、布尔代数都有密切的联系。关系是日常生活以及数学中的一个基本概念，例如：兄弟关系，师生关系、位置关系、大小关系、等于关系、包含关系等。第5页，共148页，2022年，5月20日，8点2分，星期日第三篇 二元关系另外，关系理论还广泛用于计算机科学技术，如计算机程序的输入、输出关系；数据库的数据特性关系；数据结构本身就是一个关系等。在某种意义下，关系是有联系的一些对象相互之间的各种比较行为。第6页，共148页，2022年，5月20日，8点2分，星期日6.2 二元关系6.2.1 序偶与笛卡尔积上,下；左，右；34；中国地处亚洲；平面上点的坐标（x,y）等。特征：成对出现、具有一定的顺序。定义由两个元素

3、x,y按照一定的次序组成的二元组称为有序偶对(序偶),记作,其中x为第一个元素，y为第二个元素。第7页，共148页，2022年，5月20日，8点2分，星期日例用序偶表示下列语句中的次序关系(1)平面上点A的横坐标是x, 纵坐标是y,x,yR；(2)成都是四川的省会；(3)英语课本在书桌上；(4)左，右关系。解 各语句的序偶表示如下：(1)，x,yR；(2)；(3)；(4)。第8页，共148页，2022年，5月20日，8点2分，星期日序偶相等判定定理定义6.2.2 给定序偶和， 如果a = c，b = d，则 = 。第9页，共148页，2022年，5月20日，8点2分，星期日N重有序组由n个元素

4、a1,a2,a3,an按照一定次序组成的n元组称为n重有序组(n-Type)(Vector)，记作:例 用n重有序组描述下列语句。（1）中国四川成都电子科技大学计算机学院；（2）2006年9月10日18点16分25秒；（3）16减5再加3除以7等于2。解：（1）（2）；（3）。第10页，共148页，2022年，5月20日，8点2分，星期日N重有序组给定n重有序组和。如果aibi(i1,2,，n)，则 = 。第11页，共148页，2022年，5月20日，8点2分，星期日笛卡尔乘积 设A，B是两个集合，称集合：AB |(xA)(yB)为集合A与B的笛卡尔积(DescartesProduct)。注意

5、：（1）集合A与B的笛卡儿积AB仍然是集合；（2）集合AB中的元素是序偶，序偶中的第一个元素取自A，第二个元素取自B。第12页，共148页，2022年，5月20日，8点2分，星期日例设A = a,B = b,c,C = ,D = 1,2，请分别写出下列笛卡儿积中的元素。（1）AB,BA；（2）AC,CA；（3）A(BD),(AB)D。解 根据笛卡儿积的定义，有（1）AB = ,BA=,；（2）AC=,CA=；第13页，共148页，2022年，5月20日，8点2分，星期日例6.2.3 解（续）（3）因为BD = ,，所以A(BD) = a,a,a,a,。同理，(AB)D = ,1,2,1,2。第

6、14页，共148页，2022年，5月20日，8点2分，星期日注意由例我们可以看出：（1）笛卡儿积不满足交换律；（2）AB = 当且仅当A = 或者B = ；（3）笛卡儿积不满足结合律；（4）对有限集A,B，有 |AB| = |BA| = |A|B| 第15页，共148页，2022年，5月20日，8点2分，星期日集合相等两个集合互相包含等式成立两个集合相等定理设A,B,C是任意三个集合，则（1）A(BC)=(AB)(AC)；（2）(BC)A=(BA)(CA)；（3）A(BC)=(AB)(AC)；（4）(BC)A=(BA)(CA)。分析显然，待证等式两端都是集合第16页，共148页，2022年，5

7、月20日，8点2分，星期日定理6.2.1 分析对（1）A(BC)=(AB)(AC) A(BC)(AB)(AC),(AB)(AC)A(BC)利用按定义证明方法，首先叙述包含关系的定义，即首先叙述A(BC)(AB)(AC)的定义： 对任意A(BC)， 有(AB)(AC)， 则A(BC)(AB)(AC)。同理可分析(AB)(AC)A(BC)。第17页，共148页，2022年，5月20日，8点2分，星期日定理6.2.1 证明（1）对任意A(BC)，由笛卡儿积的定义知，xA且yBC；由并运算定义知，yB或者yC。于是有xA且yB或者xA且yC。从而，AB或者AC。即(AB)(AC)，所以，A(BC)(A

8、B)(AC)。第18页，共148页，2022年，5月20日，8点2分，星期日定理6.2.1 证明（续）另一方面，对任意(AB)(AC)，由并运算定义知,AB或者AC。由笛卡儿积的定义知,xA且yB或xA且yC。进一步有xA且yBC，从而A(BC)。所以(AB)(AC)A(BC)。于是，根据定理，有A(BC)=(AB)(AC)。(2)、(3)和(4)的证明作为练习，自证。第19页，共148页，2022年，5月20日，8点2分，星期日设A,B,C,D是任意四个集合，则(AB)(CD)AC，BD。证明 充分性()：对任意AB，有xA且yB。又因为AC，BD，所以有xC且yD，即CD，从而(AB)(C

9、D)。第20页，共148页，2022年，5月20日，8点2分，星期日定理6.2.2 证明（续）设A,B,C,D是任意四个集合，则(AB)(CD)AC，BD。证明 必要性()：对任意的xA，yB，有AB。又因为(AB)(CD)，所以CD。根据笛卡儿积的定义有xC且yD，从而AC，BD。综上所述，定理成立。第21页，共148页，2022年，5月20日，8点2分，星期日定义设A1,A2,An是n个集合，称集合A1A2An =|(aiAi)i1,2,3,n为集合A1,A2,An的笛卡儿积(DescartesProduct)当A1=A2=An=A时，有A1A2An=An。第22页，共148页，2022年

10、，5月20日，8点2分，星期日定理当集合A1,A2,An都是有限集时，|A1A2An| = |A1|A2|An|。第23页，共148页，2022年，5月20日，8点2分，星期日关系的定义问题：某学校组织学生看电影，电影院里共有n个座位，看电影的学生共有m个（mn），每个学生坐一个座位。请问，怎样表示学生和座位之间的从属关系？a1a2a3amABbnb3b2b10图6.2.1假设A,B分别表示某学校所有学生的集合和电影院里所有座位的集合，即A = a1,a2,am,B = b1,b2,bn。第24页，共148页，2022年，5月20日，8点2分，星期日定义6.2.7 设A,B为两个非空集合，称A

11、B的任何子集R为从A到B的二元关系，简称关系(Relation)。如AB，则称R为A上的二元关系。二元关系设一有序对：若R，则记为xRy，读作“x对y有关系R”；若R，则记为xRy，读作“x对y没有关系R”。注：当R = 时，称R为空关系(emptyrelation)；当R = A B时，则称R为全关系(TotalRelation)。第25页，共148页，2022年，5月20日，8点2分，星期日假设A = a,b，B = c,d，写出从A到B的所有不同关系。解 因为A = a,b,B = c,d，所以AB=,。于是AB的所有不同子集为：0元子集：；1元子集：,；2元子集：, ,；第26页，共1

12、48页，2022年，5月20日，8点2分，星期日例6.2.4 解（续）3元子集：,；4元子集：,。注意：当集合A,B都是有限集时，AB共有2|A|B|个不同的子集，即，从A到B的不同关系共有2|A|B|个。第27页，共148页，2022年，5月20日，8点2分，星期日其中，A称为R的前域，B称为R的后域。DA，CB满足：Dx|R，Cy|R，称D为R的定义域，记为DdomR；称C为R的值域,记CranR；并称fldRDC为R的域。第28页，共148页，2022年，5月20日，8点2分，星期日假设A = a1,a2,a3,a4,a5,a6,B=b1,b2,b3,b4,b5,C = a3,a4,a6

13、,D=b1,b2,b4,b5,R = ,。显然，RCDAB。第29页，共148页，2022年，5月20日，8点2分，星期日求定义在Z上关系的定义域、值域和域。 （1）R1=|(x,yZ)y = x2；（2）R2=|(x,yZ)|x| = |y| = 7。解（1）domR1 = Z,ranR1 = Z+0,fldR1 = Z； （2）domR2 = 7,7,ranR2 = 7,7, fldR2 = 7,7。例第30页，共148页，2022年，5月20日，8点2分，星期日设H = f,m,s,d表示一个家庭中父母子女四个人的集合，确定H上的一个长幼关系RH，指出该关系的定义域、值域和域。解 RH

14、= ,；domRH = f,m,ranRH = s,d，fldRH = f,m,s,d定义6.2.8 设A1,A2,An为n个非空集合，称A1A2An的任意子集R为以A1A2An为基的n元关系(n-Relation)。第31页，共148页，2022年，5月20日，8点2分，星期日关系的表示法1.集合表示法（枚举法和叙述法）例（1）设A=a,B=b,c，用枚举法写出从A到B的不同关系；（2）用叙述法写出定义在R上的“相等”关系。解（1）A到B的不同关系有：R1=,R2=,R3=,R4=,；（2）设R上的“相等”关系为S，则S=|(x,yR)(x=y)。第32页，共148页，2022年，5月20日

15、，8点2分，星期日6.2.3 关系的表示法2.关系图法（1）AB设Aa1,a2,.,an,Bb1,b2,.,bn，R是从A到B的一个二元关系，则规定R的关系图如下：.设a1,a2,.,an和b1,b2,.,bn分别为图中的结点，用“。”表示；.如R,则从ai到bj可用有向边ai。bj相连。为对应图中的有向边。第33页，共148页，2022年，5月20日，8点2分，星期日（2)A=B设AB=，R是A上的关系，则R的关系图规定如下：.设a1,a2,.,an为图中节点，用“。”表示.如R,则从ai到aj可用有向边ai。bj相连。为对应图中的有向边。.如R,则从ai到ai用一带箭头的小圆环表示，即：a

16、i2.关系图法（续）第34页，共148页，2022年，5月20日，8点2分，星期日2图6.2.3244336134图6.2.4试用关系图表示下面的关系。 （1）设A = 2,3,4，B = 3,4,5,6，则A到B之间的一种整除关系: R1 = ,（2）假设A = 1,2,3,4，则A上的小于等于关系:R2 = ,。第35页，共148页，2022年，5月20日，8点2分，星期日设A = a1,a2,.,an,B = b1,b2,.,bm,R是从A到B的一个二元关系，称矩阵MR（rij)nm为关系R的关系矩阵(Relation Matrix)，其中又称MR为R的邻接矩阵(Adjacency Ma

17、trix)。3.关系矩阵注意：A中元素序号对应矩阵元素的行下标，B中元素序号对应矩阵元素的列下标；关系矩阵是0-1矩阵，称为布尔矩阵。 第36页，共148页，2022年，5月20日，8点2分，星期日例6.2.9设A = 1, 2, 3, 4，考虑A上的整除关系R和等于关系S。（1）试写出R和S中的所有元素；（2）试写出R和S的关系矩阵。第37页，共148页，2022年，5月20日，8点2分，星期日例6.2.9解 （1）根据整除关系和等于关系的定义，有 R = , , S = ,。（2）设R和S的关系矩阵分别为MR和MS，则有 第38页，共148页，2022年，5月20日，8点2分，星期日布尔矩

18、阵的运算定义 如果A=(aij)和B=(bij)是两个mn矩阵,则A和B的并(join)是矩阵AB=C=(cij),其中： 。(6.2.2)定义 如果A=(aij)和B=(bij)是两个mn矩阵,则A和B的交(meet)是矩阵AB=C=(cij),其中： 。(6.2.3)第39页，共148页，2022年，5月20日，8点2分，星期日布尔矩阵的运算(续) 如果A = (aij)是mp矩阵，B=(bij)是pn矩阵，则A和B的布尔积(Boolean product)是矩阵A B = C = (cij),其中： 两个布尔矩阵可进行并和交运算的前提是有相同的行数和列数；两个布尔矩阵可进行布尔积运算的前

19、提是前一矩阵的列数等于后一矩阵的行数。第40页，共148页，2022年，5月20日，8点2分，星期日令 、 和 。计算（1）AB； （2）AB； （3）AC。（1）（2）（3）第41页，共148页，2022年，5月20日，8点2分，星期日6.2.5 关系的应用集合A到集合B上的关系可以看成是列出了集合A中的一些元素与集合B中的相关元素的表(table)。例 试用关系表示图。dbcfae图6.2.5解 图6.2.5可以用关系表示如下：, , , , , , , , , 。第42页，共148页，2022年，5月20日，8点2分，星期日设集合A = 张红，李明，王强，程飞，赵伟，B = 离散数学，操

20、作系统，计算机图形学，R = ，试用表的形式表示关系R。解 关系R的表的表示形式见表。学生课程张红离散数学李明离散数学王强操作系统程飞操作系统赵伟计算机科学张红算法分析李明组合数学王强数据结构程飞组合数学赵伟计算机图形学第43页，共148页，2022年，5月20日，8点2分，星期日请分别将下列表和表示的关系改写为关系集合表示形式。 表6.2.2 表8840锤子9921钳子452油漆2207地毯a3b1b4c1解 （1）设表表示的关系为R1，则R1=,；(2)设表表示的关系为R2，则R2=, ,第44页，共148页，2022年，5月20日，8点2分，星期日例6.2.1 请将下列关系改写为表。（1

21、）R = , , , ； （2）在1,2,3上定义关系R：如果x2y，则R。解（1）关系R的表表示形式见表；（2）由题意得R=, ,，其对应的表见表a6b2a1c111213122233233 表6.2.4 表 第45页，共148页，2022年，5月20日，8点2分，星期日6.3 关系的运算设R，S都是从集合A到B的两个关系，则：RS|(xRy)(xSy)RS|(xRy)(xSy)注意：AB是相对于R的全集，所以有AB-R,且RAB,R。R-S|(xRy)(xSy) |(xRy)第46页，共148页，2022年，5月20日，8点2分，星期日例6.3.1设A = a,b,c,d，A上关系R和S定

22、义如下： R = , , ， S = , , 。计算 RS, RS, R S, S R, 。第47页，共148页，2022年，5月20日，8点2分，星期日例6.3.1 解RS = ,；RS = |(xRy)(xSy)=；RS = |(xRy)(xy)=,； = A2R = , ,=,。第48页，共148页，2022年，5月20日，8点2分，星期日6.3.1 关系的复合运算定义6.3.1 设A,B,C是三个集合，R是从A到B的关系(R:AB)，S是从B到C的关系(S:BC)，则R与S的复合关系(合成关系)(Composite)RS是从A到C的关系，并且： RS|xAzC (y)(yBxRyySz

23、)运算“”称为复合运算(CompositeOperation)。第49页，共148页，2022年，5月20日，8点2分，星期日6.3.1 关系的复合运算1.R和S是可复合的 R的后域和S的前域完全相同；2.RoS的前域是R的前域A，后域是S的后域C；3.RoS = 对任意的xA和zC，不存在yB，使得xRy和ySz同时成立。4.oR = Ro = 第50页，共148页，2022年，5月20日，8点2分，星期日试判断下列关系是否是两个关系的复合，如果是，请指出对应的两个关系。（1）“祖孙”关系； （2）“舅甥”关系；（3）“兄妹”关系。解（1）“祖孙”关系是“父女”关系和“母子”关系的复合；（2

24、）“舅甥”关系是“兄妹”关系和“母子”关系的复合；（3）不是。第51页，共148页，2022年，5月20日，8点2分，星期日设A=a,b,c,d,B=b,c,d,C=a,b,d,R=,是A到B的关系，S=,是B到C的关系。试用关系的三种表示方法求RS。解（1）RS = ,；（2）R所示，其中图6.3.1是以y为“桥梁得RS=,；bSRoSRabcdabcddcabdabd图6.3.1 图6.3.2第52页，共148页，2022年，5月20日，8点2分，星期日设A = 1,2,3,4， R = ,S=, T = ,是A上的三个关系。计算（1）RoS和SoR；(1)RoS = ,o, = , So

25、R = ,o, = ,第53页，共148页，2022年，5月20日，8点2分，星期日设A = 1,2,3,4，R = ,S = , T = ,是A上的三个关系。计算（2）(RoS)oT和Ro(SoT)。(2)(RoS)oT=(,o ,)o, =,o, =, Ro(SoT)=,= (RoS)oT第54页，共148页，2022年，5月20日，8点2分，星期日设A、B、C和D是任意四个集合，R、S和T分别是从A到B，B到C和C到D的二元关系，则（1）(RoS)oT = Ro(SoT)；（2）IAoR = RoIB = R，其中IA和IB分别是A和B上的恒等关系。分析：二元关系是集合，二元关系的复合是

26、关系，从而也是集合，因此上面两式就是证明两个集合相等。根据集合相等的定义，有A=B AB并且BA， AB xA，有xB。第55页，共148页，2022年，5月20日，8点2分，星期日定理6.3.1 证明（1）(RoS)oT = Ro(SoT)(1)任意(RS)T，由“”知,至少存在cC,使得RS,T.对RS，同样至少存一个bB，使得R，S。于是,由S,T,有ST，由R和ST，知R(ST),所以(RS)TR(ST)。同理可证：R(ST)(RS)T。由集合性质知：(RS)TR(ST)。构造性证明方法第56页，共148页，2022年，5月20日，8点2分，星期日定理6.3.1 证明（2）IAoR =

27、 RoIB = R（2）任取IAoR，其中aA，bB，由“o”的定义知，存在aA，使得IA且R，从而有IA o RR。反过来，任取R，由IA的定义知，IA ，即IAoR。从而RoIAR。于是由定理知,IAo R=R 。同理可证RoIB R。于是IAoR=RoIB=R得证。 第57页，共148页，2022年，5月20日，8点2分，星期日设A、B、C和D是任意四个集合，R是从A到B的关系，S1，S2是从B到C的关系，T是从C到D的关系，则：1)、R(S1S2) = (RS1)(RS2)2)、R(S1S2) (RS1)(RS2)3)、(S1S2)T = (S1T)(S2T)4)、(S1S2)T (S

28、1T)(S2T)定理第58页，共148页，2022年，5月20日，8点2分，星期日证明： 对任意(S1S2)T，则由复合运算知， 至少存在cC,使得(S1S2)，T。 即：S1,且S2。 因此，由S1,且T，则有： (S1T), 由S2,且T，则有：(S2T)。 所以，(S1T)(S2T)。即， (S1S2)T(S1T)(S2T)。4)、(S1S2)T(S1T)(S2T)第59页，共148页，2022年，5月20日，8点2分，星期日试说明下面的包含关系不一定成立。（1）(RoS1)(RoS2) Ro(S1S2)（2）(S1oT)(S2oT) (S1S2)oT例分析：如要说明某一事实不一定成立，

29、则可举一反例加以说明。第60页，共148页，2022年，5月20日，8点2分，星期日设A a, B b1, b2, C c,关系R， S1，S2定义如下：R, , S1,S2 。则由于S1S2,所以R(S1S2) R ,但(RS1),(RS2)，所以 (RS1) (RS2) ，即 (RoS1)(RoS2) Ro(S1S2),这说明(RoS1)(RoS2) Ro(S1S2)不一定成立。例6.3.5 解（1）(RoS1)(RoS2)Ro(S1S2)不一定成立第61页，共148页，2022年，5月20日，8点2分，星期日设A a, B b1, b2, C c,关系S1，S2，T定义如下：S1,S2,

30、T,。则由于S1S2,所以(S1S2)TT,但(S1T),(S2T)，所以(S1T)(S2T)， 即(S1T)(S2T) (S1S2)T，这说明(S1oT)(S2oT)(S1S2)oT不一定成立。例6.3.5 解（2） (S1oT)(S2oT)(S1S2)oT不一定成立第62页，共148页，2022年，5月20日，8点2分，星期日说明如果说明某事实一定成立，则一定加以证明。如要说明某一事实不一定成立，则可举一反例加以说明。如要说明某事实一定不成立，则也一定加以证明。第63页，共148页，2022年，5月20日，8点2分，星期日定义6.3.2 设A，B是两个集合，R是A到B的关系，则从B到A的关

31、系 R-1|R称为R的逆关系(InverseRelation) ,运算“-1”称为逆运算(InverseOperation) 。6.3.2 关系的逆运算注意：关系是一种集合，逆关系也是一种集合，因此，如果R是一个关系，则R-1和都是关系，但R-1和是完全不同的两种关系，千万不要混淆。(R-1)-1=R； -1=。第64页，共148页，2022年，5月20日，8点2分，星期日设A = 1,2,3,4,B = a,b,c,d,C = 2,3,4,5,R是从A到B的一个关系且R = ,S是从B到C的一个关系且S = , ,。（1）计算R-1，并画出R和R-1的关系图；解：(1) R-1=,-1 =,

32、，第65页，共148页，2022年，5月20日，8点2分，星期日例6.3.6 解(1)R-1=,-1 =,，R和R-1的关系图见图和图。R-1abcd124 图6.3.3 图6.3.43R1234abdcABBA第66页，共148页，2022年，5月20日，8点2分，星期日(1)R-1=,-1 =,（2）写出R和R-1的关系矩阵；解：第67页，共148页，2022年，5月20日，8点2分，星期日例6.3.6 解(1)R-1=,-1 =,R和R-1的关系图见图和图。R-1abcd124 图6.3.3 图6.3.43R1234abdcABBA第68页，共148页，2022年，5月20日，8点2分，

33、星期日例6.3.6 解（续）解：(3) RoS=,，(RoS)-1=,。 R-1=,， S-1=,， S-1oR-1=,。设A=1,2,3,4,B=a,b,c,d,C=2,3,4,5,R是从A到B的一个关系且R=, ,S是从B到C的一个关系且S=, ,。求：(3) 计算(RoS)-1和S-1oR-1。第69页，共148页，2022年，5月20日，8点2分，星期日注意（1）将R的关系图中有向边的方向改变成相反方向即得R-1的关系图，反之亦然；（2）将R的关系矩阵转置即得R-1的关系矩阵，即R和R-1的关系矩阵互为转置矩阵。（3）R-1的前域与后域正好是R的后域和前域，即domR = ranR-1

34、，domR-1 = ranR；（4）|R| = |R-1|；（5）(RoS)-1 = S-1oR-1.第70页，共148页，2022年，5月20日，8点2分，星期日设A、B和C是任意三个集合，R,S分别是从A到B，B到C的二元关系，则 (RoS)-1 = S-1oR-1。定理第71页，共148页，2022年，5月20日，8点2分，星期日任取(RS)-1，则RS由“”的定义知：则至少存一个bB,使得：R，S，由“R-1”的定义知，R-1,S-1，从而有S-1R-1，即(RS)-1S-1R-1。反之，任取S-1R-1，由“”的定义知：则至少存一个bB,使得： S-1和R-1。由“R-1”的定义知，

35、有R,S。从而RS，即(RS)-1,即S-1R-1(RS)-1。由集合的定义知：(RS)-1S-1R-1。定理的证明 (RoS)-1 = S-1oR-1第72页，共148页，2022年，5月20日，8点2分，星期日设R，S是从集合A到集合B的关系，则有(RS)-1R-1S-1；(分配性) (RS)-1R-1S-1； (R-S)-1R-1-S-1；()-1 ；(可换性) (AB)-1(BA)； SR S-1R-1；(单调性)定理第73页，共148页，2022年，5月20日，8点2分，星期日设R是集合A上的关系，则R的n次幂，记为Rn,定义如下：(1) R0IA|aA；(2) R1；(3) Rn+

36、1RnRRRn。6.3.3 关系的幂运算显然，RmRn Rm+n,(Rm)n Rmn。该Rn也是A上的二元关系，第74页，共148页，2022年，5月20日，8点2分，星期日例设A = 1,2,3,4,5,6，定义在A上的关系R = ,，S = ,，计算：(1)Rn(n=1,2,3,4,)， 和 (2)Sn(n=1,2,3,4,)， 和 。第75页，共148页，2022年，5月20日，8点2分，星期日例6.3.7 解（1）R1R，R2RR ,，R3RRRR2R,，R4R3R,，R5R4R,，R6R5R=,=R5，R7R6RR5，RnR5(n5)。第76页，共148页，2022年，5月20日，8

37、点2分，星期日例6.3.7 解（续） =, ,；第77页，共148页，2022年，5月20日，8点2分，星期日（2) S1S,例6.3.7 解（续）S2SS,，S3SSSS2S,，S4S3S,，S5S4S，S6S5S，S7，Sn(n5)。第78页，共148页，2022年，5月20日，8点2分，星期日由例可以看出：（1）幂集Rn的基数|Rn|并非随着n的增加而增加，而是呈递减趋势；（2）当n |A|时，则Rn 例6.3.7 解（续） =, ,；第79页，共148页，2022年，5月20日，8点2分，星期日证明显然， 。下面证：设A是有限集合，且|A| = n，R是A上的二元关系，则： 说明幂运算

38、具有周期性由于， 为此，只要证明对任意的kn，有Rk 即可。对任意Rk，则由“”的定义知，存在a1,a2,ak-1A（为了统一，并假设a0a，akb)，使得：R，R，R，,R。构造性证明方法第80页，共148页，2022年，5月20日，8点2分，星期日由于|A|n，所以由鸽笼原理知：a0,a1,ak共k+1个元素中至少有两个以上元素相同.不妨假设aiaj(ij)，则可在R，R，R，,R中删去R，R，,R后仍有R，R，R，,R，R，,R定理6.3.5 证明续第81页，共148页，2022年，5月20日，8点2分，星期日即有： ，由此有：Rk 。由k的任意性知： ， 由关系的复合运算得， = Rk

39、，其中kk-(j-i)，此时：定理6.3.5 证明续若kn，则： ；若kn，则重复上述做法，最终总能找到kn，使得：Rk，所以， 。第82页，共148页，2022年，5月20日，8点2分，星期日有R8 即可。设A = a0，a1，a2，a3，a4,a5，|A|6，R是A上的二元关系。例：取k86n，对R8，则由“”的定义知，存在a1,a2,a7A（为了统一，并假设a0a，a8b)，使得：R，R，R，R，R，R，R，R。第83页，共148页，2022年，5月20日，8点2分，星期日由于|A|6，所以由鸽笼原理知：9个元素中至少有两个以上元素相同，不妨假设a4a7(47)，则可在R，R，R，R，R

40、，R，R，R。中删去R，R，R，后有R，R，R，R，R。例（续）：第84页，共148页，2022年，5月20日，8点2分，星期日由关系的复合运算得，=R5，其中58-(7-4)，此时：显然，56，则： ；例（续）：第85页，共148页，2022年，5月20日，8点2分，星期日6.3.5关系运算的应用例6.3.8 设有关系R和S分别如表和表所示，现在在R中增加关系S中的所有元组，试求增加后的关系。ABC462213615ABC125213562表6.3.1 表第86页，共148页，2022年，5月20日，8点2分，星期日分析 在关系R中增加S中的所有元组，在关系数据库中称为对关系表的插入操作(I

41、nsertOperation)，该操作可以通过关系的并运算完成，即求在R中增加关系S的所有元组等价于求RS。解关系R增加S的元组后所构成的关系RS，见右表。 ABC125213562462615第87页，共148页，2022年，5月20日，8点2分，星期日设有关系R和S如表和表所示，现在在R中去掉关系S中所出现的元组，试求去掉S后的关系。解 关系R中除去S中所出现的元组后所得的关系R-S如表所示。ABCABCABC123123456456789789表6.3.4 表6.3.5 表第88页，共148页，2022年，5月20日，8点2分，星期日6.4 关系的性质 本节涉及到的关系，如无特别声明，都

42、是假定其前域和后域相同。 即都为定义在集合A上的关系，且A是非空集合。对于前后域不相同的关系，其性质无法加以定义。第89页，共148页，2022年，5月20日，8点2分，星期日6.4.1 关系性质的定义1、自反性和反自反性 设R是集合A上的关系，（1）如果对xA,都有R，那么称R在A上是自反的(Reflexive)，或称R具有自反性(Reflexivity)；例如：同学关系。（2）如果对任意的xA，都有 R，那么称R在A上是反自反的(Antireflexive)，或称R具有反自反性(Antireflexivity)。例如：父子关系。第90页，共148页，2022年，5月20日，8点2分，星期日

43、符号化：（1）R在A上是自反的 (x)(xAR)=1，（2）R在A上是反自反的 (x)(xA R)=1。根据上面两式分别可得：（1）R在A上不是自反的 (x)(xA R)=1，（2）R在A上不是反自反的 (x)(xAR)=1。第91页，共148页，2022年，5月20日，8点2分，星期日设A = 1,2,3，定义A上的关系R,S和T如下：（1）R = ,；（2）S = ,；（3）T = ,。判断这三个关系是否具有自反性或者反自反性。解：R：自反 S：反自反 T：既不是自反的，也不是反自反的。R在A上是自反的(x)(xAR)=1R在A上是反自反的(x)(xA R)=1第92页，共148页，202

44、2年，5月20日，8点2分，星期日例6.4.1 解（1）a)因为A中x，都有R， 所以R是自反的； b）因为A中x，都有 S， 所以S是反自反的； c）因为存在2A，使 T， 所以T不是自反的； 又因为存在1A，使T， 所以T不是反自反的， 即T既不是自反的，也不是反自反的。第93页，共148页，2022年，5月20日，8点2分，星期日（2）设R,S和T的关系矩阵分别为MR,MS和MT，则：（3）R,S和T的关系图分别是下图的(a),(b)和(c)。例6.4.1 解（续）133123212 (a) (b) (c)第94页，共148页，2022年，5月20日，8点2分，星期日结论：（1）关系R是

45、自反的 R一定不是反自反的；（2）存在既不是自反的也不是反自反的关系；（3）关系R是自反的 关系图中每个结点都有自环， 关系R是反自反的 关系图中每个结点都无自环；（4）关系R是自反的 关系矩阵的主对角线上全为1， 关系R是反自反的关系矩阵的主对角线上全为0。第95页，共148页，2022年，5月20日，8点2分，星期日设A = a,b，试计算A上所有具有自反性的关系R的个数。解 A上具有自反性的关系R的个数为：C（2，0）+ C（2，1）+ C（2，2）= 4.第96页，共148页，2022年，5月20日，8点2分，星期日2、对称性和反对称性定义6.4.2 设R是集合A上的关系。（1）对任意

46、的x,yA，如果R，那么R，则称关系R是对称的(Symmetric)，或称R具有对称性(Symmetry)；（2）对任意的x,yA，如果R且R，那么x = y，则称关系R是反对称的(Antisymmetric)，或称R具有反对称性(Antisymmetry)。第97页，共148页，2022年，5月20日，8点2分，星期日（1）R在A上是对称的对x,yA，有：R并且R或 R并且 R。（2）R在A上是反对称的对x,yA，如果xy，则 R或 R。符号化：（1）R在A上是对称的(x)(y)(xAyARR)=1，（2）R在A上是反对称的(x)(y)(xAyARRx=y)=1。第98页，共148页，202

47、2年，5月20日，8点2分，星期日结论：（3）R在A上不是对称的x,yA，有R但 R或者 R但R；（4）R在A上不是反对称的 x,yA，有R且R。第99页，共148页，2022年，5月20日，8点2分，星期日设A = 1,2,3,4，定义A上的关系R,S,T和V如下：（1）R = ,；（2）S = ,；（3）T = ,；（4）V = ,。试判定它们是否具有对称性和反对称性，并写出R,S,T和V的关系矩阵和画出相应的关系图。对称反对称不是对称的，也不是反对称是对称的，也是反对称第100页，共148页，2022年，5月20日，8点2分，星期日例6.4.2 解（1）a）关系R是对称的；b）关系S是反

48、对称的；c）在关系T中，有，但没有,即S不是对称的； 另外有，且有，但是13， 即S不是反对称的。 因此T既不是对称的，也不是反对称的；d）在关系V中，对x,yA，xy时都有 R，根据式(6.4.5)和(6.4.6)知V既是对称的，也是反对称的。第101页，共148页，2022年，5月20日，8点2分，星期日例6.4.2 解（2）1234 (a) (b) (c) (d)123412341234设R,S,T和V的关系矩阵分别为MR,MS,MT和MV，则(3)R,S,T和的关系图分别是图(a),(b),(c)和(d)。第102页，共148页，2022年，5月20日，8点2分，星期日注意（1）存在既

49、不是对称也不是反对称的关系，也存在既是对称也是反对称的关系；（2）关系R是对称的关系图中任何一对结点之间，要么有方向相反的两条边，要么无任何边；关系R是反对称的关系图中任何一对结点之间，至多有一条边；（3）关系R是对称的R的关系矩阵为对称矩阵，关系R是反对称的R的关系系矩阵为反对称矩阵。第103页，共148页，2022年，5月20日，8点2分，星期日3、传递性定义6.4.3 设R是集合A上的关系。对任意的x,y,zA，如果R且R，那么R，则称关系R是传递的(Transitive)，或称R具有传递性(Transitivity)。将定义6.4.3符号化为：R在A上是传递的(x)(y)(z)(xAy

50、AzARRR)=1。 （）第104页，共148页，2022年，5月20日，8点2分，星期日结论：（1）对任意的x,y,zA，如果R，R且R，则R在A上是传递的；（2）对任意的x,y,zA，如果 R或者 R，则R在A上是传递的（3）R在A上不是传递的当且仅当存在x,y,zA，有R且R，但 R。 第105页，共148页，2022年，5月20日，8点2分，星期日设A=1,2,3，定义A上的关系R,S,T和V如下：（1）R = ,；（2）S = ；（3）T = ,；（4）V = ,。试判定它们是否具有传递性，并写出R,S,T和V的关系矩阵和画出相应的关系图。是传递的是传递的不是传递的不是传递的第106

51、页，共148页，2022年，5月20日，8点2分，星期日（1）a)关系R是传递的； b)关系S是传递的； c)在关系T中，存在x=1,y=2,z=3A且, T，但 T，根据式(6.4.7)知T不是传递的； d)在关系V中，存在x=1,y=2和z=1A，使得V且V，但是 V，根据式(6.4.7)知关系V不是传递的。例6.4.3 解,第107页，共148页，2022年，5月20日，8点2分，星期日例6.4.3 解（续）（2）设R,S,T和V的关系矩阵分别为MR,MS,MT和MV，则。（3）R,S,T和的关系图分别是图 a),(b),(c)和(d).123 (a) (b) (c) (d)123123

52、123第108页，共148页，2022年，5月20日，8点2分，星期日设A=a,b,试画出A上所有具有传递性的关系R的关系图。解 A上所有具有传递性的关系R共8种，其关系图见下图。第109页，共148页，2022年，5月20日，8点2分，星期日自反性反自反性对称性反对称性传递性集合IARRIA=R=R1RR1IARRR关系矩阵主对角线元素全是1主对角线元素全是0矩阵是对称矩阵若rij1, 且ij, 则rji0M2中1位置, 在M中相应位置都是1关系图每个顶点都有环每个顶点都没有环两点之间有边, 是一对方向相反的边两点之间有边, 并且是一条有向边点xi到xj有边, xj 到xk有边, 则xi到x

53、k也有边 关系性质的三种等价条件五种性质在关系矩阵和关系图中的特点：第110页，共148页，2022年，5月20日，8点2分，星期日总结对任意给定的A上的关系R，可以采用下面的四种方法判定它所具有的性质：（1）定义判定法；（2）关系矩阵判定法；（3）关系图判定法；（4）符号化语言判定法。第111页，共148页，2022年，5月20日，8点2分，星期日判定下列关系所具有的特殊性质。（1）集合A上的全关系；（2）集合A上的空关系；（3）集合A上的恒等关系。解(1)集合A上的全关系具有自反性，对称性和传递性；(2)集合A上的空关系具有反自反性、对称性、反对称性和传递性；特别地，如果A为空集，则A上的

54、空关系具有自反性、反自反性、对称性、反对称性和传递性；(3)集合A上的恒等关系具有自反性、对称性、反对称性和传递性。第112页，共148页，2022年，5月20日，8点2分，星期日判定下列关系所具有的特殊性质。（1）在实数集R上定义的“等于”关系；（2）幂集上的“真包含”关系。解（1）R上的“等于”关系具有自反性、对称性、反对称性和传递性；（2）幂集上的“真包含”关系具有反自反性，反对称性和传递性。第113页，共148页，2022年，5月20日，8点2分，星期日假设A = a,b,c,d，R = , 是定义在A上的关系。试判定R所具有的特殊性质。解 由前面的分析可知，R既不是自反的，也不是反自

55、反的；既不是对称的，也不是反对称的；而且也不是传递的。即R不具备关系的任何性质。第114页，共148页，2022年，5月20日，8点2分，星期日设R = ,，试分别判断R在集合A或集合B上具备的特殊性质，其中A = 1,2,B = 1,2,3。解 当R是定义在集合A上的关系时，R是自反、对称、反对称和传递的；当R是定义在集合B上的关系时，R是对称、反对称和传递的。注意：绝对不能脱离基集来谈论关系的性质。第115页，共148页，2022年，5月20日，8点2分，星期日 设R是集合A上的二元关系，则：（1）R是自反的 IAR；（2）R是反自反的 RIA；（3）R是对称的 RR-1；（4）R是反对称

56、的 RR-1IA；（5）R是传递的 RRR。6.4.2 关系性质的判断定理第116页，共148页，2022年，5月20日，8点2分，星期日证明（4）R是反对称的 RR-1IA（4） “” 设R是反对称的。对RR-1,则(R)(R-1),即:(R)(R，由于R是反对称的，则ab。所以，IA，即RR-1IA。第117页，共148页，2022年，5月20日，8点2分，星期日证明（4）R是反对称的 RR-1IA“” 设RR-1IA。对a,bA,若(R)(R)，则有：(R)(R-1)即：RR-1。又因RR-1IA，所以，IA，即ab。即R是反对称的。第118页，共148页，2022年，5月20日，8点2

57、分，星期日（5）“” 设R是传递的。对任意RR，根据“”的定义，则必存在bA,使得R并且R,由R的传递性，有：R。所以，RRR。“” 设RRR。对任意a,b,cA, 若R并且R，则有：RR,因RRR,所以,R,即R是传递的。证明（5）R是传递的 RRR第119页，共148页，2022年，5月20日，8点2分，星期日定理6.4.2 设R,S是定义在A上的二元关系，则：(1)若R,S是自反的,则R-1,RS,RS,RS也是自反的；(2)若R,S是反自反的,则R-1,RS,RS也是反自反的。(3)若R,S是对称的,则R-1,RS,RS也是对称的。(4)若R,S是反对称的,则R-1,RS也是反对称的。

58、(5)若R,S是传递的,则R-1,RS也是传递的。6.4.3 关系性质的保守性注意：（1）逆运算与交运算具有较好的保守性；（2）并运算、差运算和复合运算的保守性较差。第120页，共148页，2022年，5月20日，8点2分，星期日试举例说明下列事实不一定成立。（1）R和S是反自反、反对称和传递的，但是，RoS不一定具备反自反性，反对称性；RS不一定具有反对称性和传递性；解 （1）设A = 1,2,3,R = ,， S = ,是定义在A上的两个关系。显然R,S都是反自反的、反对称的、传递的。则 RoS = ,， 不具备反自反性和反对称性；RS = ,， 不具备传递性和反对称性；第121页，共14

59、8页，2022年，5月20日，8点2分，星期日例6.4.10(续)试举例说明下列事实不一定成立。（2）R和S是自反、对称和传递的，但是RoS不一定是对称和传递的，R-S不一定是自反和传递的。解（2）设A=1,2,3,R=, ,S=,是A上的两个关系。显然R，S都是自反的、对称的、传递的。此时，RoS=, 不具备对称性和传递性；R-S=,不具备自反性和传递性；第122页，共148页，2022年，5月20日，8点2分，星期日6.4.5关系性质的应用例 假设点i和j之间有路当且仅当从结点i通过图中的边能够到达结点j，其中点i到点j的路上边的数目称为该路的长度。（1）找出图中从点c开始的长度为1的所有

60、的路；（2）找出图中从点c开始的长度为2的所有的路；（3）找出图中长度为2的所有的路。dbcfae 图6.4.5第123页，共148页，2022年，5月20日，8点2分，星期日例6.4.11 解 （1）图中从点c开始的长度为1的所有的路有两条:cd和ce；（2）图中从点c开始的长度为2的所有的路有两条： cdb和cef；（3）图中长度为2的所有的路有： ace,acd,abb,abf,bbf, bfd,cdb,cef,dcd,dce, dbb,dbf,efd,fdb,fdc共15条。第124页，共148页，2022年，5月20日，8点2分，星期日6.5关系的闭包运算闭包(closure): 包