数理逻辑二元关系.ppt

《数理逻辑二元关系.ppt》由会员分享，可在线阅读，更多相关《数理逻辑二元关系.ppt（148页珍藏版）》请在三一办公上搜索。

1、第7章 二元关系,离 散 数 学,六度空间理论,六度空间理论：你和任何一个陌生人之间的关系不会超过六层，也就是说，最多通过六个人你就能够认识任何一个陌生人。,X,眾里尋她千百度,关系理论历史悠久。它与集合论、数理逻辑、组合学、图论和布尔代数都有密切的联系。关系是日常生活以及数学中的一个基本概念，例如：兄弟关系，师生关系、位置关系、大小关系、等于关系、包含关系等。,另外，关系理论还广泛用于计算机科学技术，如计算机程序的输入、输出关系；数据库的数据特性关系；数据结构本身就是一个关系等。在某种意义下，关系是有联系的一些对象相互之间的各种比较行为。,本章说明,本章的主要内容有序对与笛卡尔集二元关系的定

2、义和表示法关系的运算关系的性质关系的闭包等价关系与划分偏序关系本章与后续各章的关系本章是函数的基础本章是图论的基础,7.1 有序对与笛卡尔积,定义7.1 由两个元素x和y按一定顺序排列成的二元组叫做一个有序对(ordered pair)或序偶，记作，其中x是它的第一元素，y是它的第二元素。有序对具有以下性质：（1）当xy时，。（2）的充分必要条件是xu且yv。,说明,有序对中的元素是有序的集合中的元素是无序的,定义7.2 设A，B为集合,以A中元素为第一元素，B中元素为第二元素构成有序对，所有这样的有序对组成的集合叫做A和B的笛卡尔积(Cartesian product)，记作AB。笛卡尔积的

3、符号化表示为AB|xAyB,笛卡尔积的定义,A表示某大学所有学生的集合，B表示大学开设的所有课程的集合，则AB可以用来表示该校学生选课的所有可能情况。令A是直角坐标系中x轴上的点集，B是直角坐标系中y轴上的点集，于是AB就和平面点集一一对应。,举例,笛卡尔(RenDescartes，15961650)在数学史上，笛卡尔因与费马共同创立解析几何而闻名于世。与此同时，笛卡尔还是一位哲学家、物理学家、生物学家，尤其在哲学上的杰出贡献使他成为当之无愧的一代哲学大师。,笛卡尔是法国人，出生于一个贵族家庭，因家境富裕从小多病，学校允许他在床上早读，使得他有更多的时间独自静静地思考各种关于自然、科学与人的问

4、题，从而养成沉思的习惯和孤僻的性格。1628年，笛卡尔移居荷兰，潜心从事哲学、数学、天文学、物理学、化学和生理学等领域的研究。他的主要著作都是在荷兰完成的，其中1637年出版的方法论 一书成为哲学经典。这本书中的3个著名附录几何、折光和气象更奠定了笛卡尔在数学、物理和天文学中的地位。,在几何中，笛卡尔分析了几何学与 代数学的优缺点，指出：希腊人的几何过多的依赖于图形，总是要寻求一些奇妙的想法。代数却完全受法则和公式的控制，以致于阻碍了自由的思想和创造。他同时看到了几何的直观与推理的优势和代数机械化运算的力量。于是笛卡尔着手解决这个问题，并由此创立了解析几何。1649年冬，笛卡尔应瑞典女王克里斯

5、蒂安的邀请，来到了斯德哥尔摩，任宫廷哲学家，为瑞典女王授课。由于他身体孱弱，不能适应那里的气候，1650年初便患肺炎抱病不起，同年二月病逝。终年54岁。1799年法国大革命后，笛卡尔的骨灰被送到了法国历史博物馆。(补充：瑞典女王为了显示对知识的尊重,专门派一艘军舰接笛卡尔到瑞典),笛卡尔积举例,设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=；,笛卡尔积运算不满足交换律,AB=当且仅当A=或者B=,（3）因为BD=,，所以A(BD)=,

6、。同理，(AB)D=,1,2,1,2。,笛卡尔积运算不满足结合律,对有限集A,B，有|AB|=|BA|=|A|B|,笛卡尔积的运算性质,(1)对任意集合A，根据定义有A,A(2)一般的说，笛卡尔积运算不满足交换律，即ABBA(当 A B AB 时)(3)笛卡尔积运算不满足结合律，即(AB)CA(BC)(当 A B C 时)(4)笛卡尔积运算对并和交运算满足分配律，即A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA)(5)AC BD AB CD,A(BC)=(AB)(AC)的证明,任取 A(BC)xA yBC xA(yByC)(xAy

7、B)(xAyC)AB AC(AB)(AC)所以 A(BC)=(AB)(AC),关于ACBD ABCD的讨论,该性质的逆命题不成立，可分以下情况讨论。（1）当A=B=时，显然有AC 和 BD 成立。（2）当A且B时，也有AC和BD成立，证明如下：任取xA，由于B,必存在yB,因此有 xAyB AB，又因为 ABCD CD xCyD xC从而证明了 AC。同理可证 BD。,关于ACBD ABCD的讨论,（3）当A而B时，有AC成立，但不一定有BD成立。反例：令A,B1,C3,D4。（4）当A而B时，有BD成立，但不一定有AC成立。反例略。,例7.2,例7.2 设A=1,2,求P(A)A。,P(A)

8、A,1,2,1,21,2,解答,例7.3,例7.3 设A，B，C，D为任意集合，判断以下命题是否为真，并说明理由。(1)ABAC BC(2)A-(BC)(A-B)(A-C)(3)ABCD ACBD(4)存在集合A，使得A AA,(1)不一定为真。当A，B1,C2时，有 ABAC，但BC。(2)不一定为真。当A=B=1,C2时，有 A-(BC)11(A-B)(A-C)1(3)为真。由代入原理可证。(4)为真。当A时，有 A AA 成立。,解答,7.2 二元关系(binary relation),定义7.3 如果一个集合满足以下条件之一：（1）集合非空，且它的元素都是有序对（2）集合是空集 则称该

9、集合为一个二元关系，记作R。二元关系也可简称为关系。对于二元关系R，如果R，可记作xRy；如果R，则记作xRy。,设R1,，R2,a,b。则R1是二元关系，R2不是二元关系，只是一个集合，除非将a和b定义为有序对。根据上面的记法可以写1R12，aR1b，aR1c等。,举例,R,是否为二元关系？,集合A上的二元关系的数目依赖于A的基数。如果|A|=n，那么|AA|=n2，AA的子集就有 个。每一个子集代表一个A上的二元关系，所以A上有 个不同的二元关系。例如|A|=3，则A上有 个不同的二元关系。,7.2 二元关系,定义7.4 设A，B为集合，AB的任何子集所定义的二元关系叫做从A到B的二元关系

10、；特别当A=B时，则叫做A上的二元关系。,A=0,1，B=1,2,3，那么 R1=，R2=AB，R3=，R4=等都是从A到B的二元关系，而R3和R4同时也是A上的二元关系。,举例,说明,常用的关系,定义7.5 对任意集合A，定义全域关系 EA=|xAyA=AA 恒等关系 IA=|xA空关系,设 A=1,2，那么EA=,IA=,举例,其它常用的关系,小于或等于关系：LA=|x,yAxy，其中 AR。整除关系：DB=|x,yBx整除y，其中 AZ*Z*是非零整数集包含关系：R|x,yAxy，其中 A是集合族。,(1)设 A=1,2,3，Ba,b则 LA=,DA=,(2)令A=P(B)=,a,b,a

11、,b，则A上的包含关系是 R,举例,例7.4,例7.4 设A=1,2,3,4，下面各式定义的R都是A上的关系，试用列元素法表示R。(1)R=|x是y的倍数(2)R=|(x-y)2A(3)R=|x/y是素数(4)R=|xy,解答,(1)R=,(2)R=,(3)R=,(4)R=EA-IA=,关系的表示方法,关系的三种表示方法：集合表达式关系矩阵关系图关系矩阵和关系图可以表示有穷集上的关系。,关系矩阵和关系图的定义,设A=x1,x2,xn,R是A上的关系。令,则,是R的关系矩阵，记作MR。,设A=x1,x2,xn,R是A上的关系。令图G=，其中顶点集合V=A，边集为E。对于 xi,xjV，满足 E

12、xiRxj称图G为R的关系图，记作 GR。,关系矩阵和关系图的实例,设 A=1,2,3,4，R=,，则R的关系矩阵和关系图分别是,7.3 关系的运算,定义7.6 设R是二元关系。(1)R中所有有序对的第一元素构成的集合称为R的定义域(domain)，记为dom R。形式化表示为：dom R x|y(R)(2)R中所有有序对的第二元素构成的集合称为R的值域(range)，记作ran R。形式化表示为ran Ry|x(R)(3)R的定义域和值域的并集称为R的域(field)，记作fld R。形式化表示为fld Rdom R ran R,例7.5 求R=,的定义域、值域和域。解答dom R1,2,4

13、 ran R2,3,4 fld R1,2,3,4,关系的逆,定义7.7 设R为二元关系，R的逆关系，简称R的逆(inverse)，记作R-1,其中R-1|R将R的关系图中每条有向弧的方向反过来就得到R-1的关系图MR-1为MR的转置矩阵例如，小于关系的逆关系是大于关系，大于关系的逆关系是小于关系，相等关系的逆关系仍是相等关系。例：R=(a,b),(b,c),(a,c),(b,d),则 R-1=(b,a),(c,b),(c,a),(d,b),关系的复合运算,定义7.8 设F,G为二元关系，G对F的右复合(composite)记作FG，其中FG|t(FG)例7.6 设F,G=，则FGGF例：兄弟关

14、系和父子关系的複合是叔侄关系，姐妹关系和母子关系的複合是姨与外甥关系。,说明,可以把二元关系看作一种作用，R可以解释为x通过R的作用变换到y。FG表示两个作用的连续发生。,还可使用关系图或关系矩阵求解在关系矩阵中,若对0,1中的元素的加法使用逻辑加（析取）,则对A上的任意的关系R,S,都有:MRS=MR MS结论：关系的复合不满足交换律。,关系的复合运算,课堂练习,设A=a,b,c,d,B=b,c,d,C=a,b,d,R=,是A到B的关系，S=,是B到C的关系。试用关系的三种表示方法求RS。,解（1）RS=,；,（2）RS的关系图如右1图所示，得RS=,；,解（3）,关系的限制和像,定义7.9

15、 设R为二元关系，A是集合(1)R在A上的限制(restriction)记作RA，其中RA=|xRyxA(2)A在R下的像(image)记作RA，其中RA=ran(RA),说明,R在A上的限制RA是R的子关系。A在R下的像RA是ran R的子集。,例7.7,设R，,R1,，,R,R2,3,，,R1,2,3,R,R3,2,关系与集合的说明,关系是集合，集合运算对于关系也是适用的。规定：关系运算中逆运算优先于其它运算所有的关系运算都优先于集合运算，未规定优先级的运算以括号决定运算顺序。例如：ran F-1FGFHran(FA),例题,设A表示是学校的所有学生的集合，B表示学校的所有课程的集合，并设

16、R1由所有有序对组成，其中a是选修课程b的学生。R2由所有的有序对构成，其中课程b是a的必修课。则关系R1R2、R1R2、R1R2、R1R2、R2R1的含义为R1R2：a是一个学生，他或者选修了课程b，或者课程b是他的必修课。R1R2：a是一个学生，他选修了课程b并且课程b也是a的必修课。R1R2：学生a已经选修了课程b，但课程b不是a的选修课，或者课程b是a的必修课，但是a没有选修它。R1R2：学生a已经选修了课程b，但课程b不是a的选修课。R2R1：课程b是学生a的必修课，但是a没有选修它。,课堂练习题,设A表示工人的集合,B表示工作的集合.设R1 表示A到B的二元关系:R1=(a,b)a

17、A,bB,a分配去做工作b.设R2表示A到A的二元关系:R2=(a1,a2)a1,a2A,a1和a2不能友好相处.请你用R1和R2表示关系 R,使得xRy表示 x,y分配去做同样工作且能友好相处.,解答：因为R1是A到B的二元关系,故R1-1表示B到A的二元关系,则R1R1-1表示从A到A的二元关系,即由分配做同一样工作的两个人构成的序偶的全体.因此R=R1R1-1-R2,定理7.1,定理7.1 设F是任意的关系，则(1)(F-1)-1F(2)dom F-1ran F，ran F-1dom F,(1)任取，由逆的定义有(F-1)-1 F-1 F,(2)任取x xdom F-1 y(F-1)y(

18、F)xran F 所以有 dom F-1ran F,证明,定理7.2,定理7.2 设F，G，H是任意的关系，则(1)(FG)HF(GH)(2)(FG)-1G-1 F-1,证明,(1)任取，(FG)H t(FG(t,y)H)t(s(FG)H)ts(FGH)s(Ft(GH)s(FGH)F(GH),定理7.2,定理7.2 设F，G，H是任意的关系，则(1)(FG)HF(GH)(2)(FG)-1G-1F-1,证明,(2)任取，(FG)-1 FG t(FG)t(F-1G-1)G-1 F-1,定理7.3,定理7.3 设R为A上的关系，则R IAIA RR,证明,(1)任取，R IA t(R(t,y)IA)

19、t(Rty)R,R RyA RIA)R IA,综上所述，有 RIAR同理可证 IARR,定理7.4,定理7.4 设F，G，H是任意的关系，则(1)F(GH)FGFH(2)(GH)FGFHF(3)F(GH)FGFH(4)(GH)FGFHF,证明,(3)F(GH)t(F(t,y)GH)t(F(t,y)G(t,y)H)t(F(t,y)G)(F(t,y)H)t(F(t,y)G)t(F(t,y)H)FG FH FGFH,定理7.4的推论,由数学归纳法不难证明定理7.4的结论对于有限多个关系的并和交也是成立的，即有R(R1R2Rn)RR1RR2RRnR1R2Rn)RR1RR2RRnRR(R1R2Rn)RR

20、1RR2RRnR1R2Rn)RR1RR2RRnR,定理7.5,定理7.5 设F为关系，A,B为集合，则(1)F(AB)FAFB(2)FABFAFB(3)F(AB)FAFB(4)FABFAFB,定理7.5(1)的证明,(1)F(AB)FAFB,证明,任取，F(AB)F x(AB)F(xAxB)(FxA)(FxB)FA FB FAFB 所以有 F(AB)FAFB。,定理7.5(4)的证明,(4)FABFAFB,证明,任取y，yFAB x(FxAB)x(FxAxB)x(FxA)(FxB)x(FxA)x(FxB)yFA yFB yFAFB所以有 FABFAFB,关系的幂运算,定义7.10 设R为A上的

21、关系，n为自然数，则R的n次幂定义为：（1）R0|xAIA（2）Rn+1Rn R,说明,对于A上的任何关系R1和R2都有R10R20IA 即：A上任何关系的0次幂都相等，都等于A上的恒等关系IA。对于A上的任何关系R都有R1R，因为R1R0 RIA RR,Rn的计算,给定A上的关系R和自然数n，怎样计算Rn呢？若n是0或1，结果是很简单的。下面考虑n2的情况。如果R是用集合表达式给出的，可以通过n-1次复合计算得到Rn。如果R是用关系矩阵M给出的，则Rn的关系矩阵是Mn，即n个矩阵M之积。与普通矩阵乘法不同的是，其中的相加是逻辑加，即1+11，1+00+11，0+00如果R是用关系图G给出的，

22、可以直接由图G得到Rn的关系图G。G的顶点集与G相同。考察G的每个顶点xi，如果在G中从xi出发经过n步长的路径到达顶点xj，则在G中加一条从xi到xj的边。当把所有这样的边都找到以后，就得到图G。,例7.8,例7.8 设Aa,b,c,d，R,，求R的各次幂，分别用矩阵和关系图表示。,解答,例7.8,因此M4M2，即R4R2。因此可以得到R2R4R6R3R5R7 用关系图的方法得到R0,R1,R2,R3,的关系图如图7.2所示。,幂运算的性质,定理7.6 设A为n元集，R是A上的关系，则存在自然数s和t,使得Rs=Rt。,R为A上的关系，对任何自然数k，Rk都是AA的子集。,证明,又知|AA|

23、=n2，|P(AA)|=，,即AA的不同子集仅 个。,当列出R的各次幂R0，R1，R2，时，,必存在自然数s和t使得Rs=Rt。,说明,该定理说明有穷集上只有有穷多个不同的二元关系。当t足够大时，Rt必与某个Rs(st)相等。如例7.8中的R4=R2。,定理7.7,定理7.7 设R是A上的关系，m,nN，则(1)Rm RnRm+n(2)(Rm)nRmn,证明,(1)对于任意给定的mN,施归纳于n。若n=0，则有,所以对一切m,nN有 Rm RnRm+n。,Rm R0,Rm IA,Rm,Rm+0,假设Rm Rn=Rm+n，则有,Rm Rn+1,Rm(Rn R),(Rm Rn)R,Rm+n+1，,

24、定理7.7,定理7.7 设R是A上的关系，m,nN，则(1)Rm RnRm+n(2)(Rm)nRmn,证明,(2)对于任意给定的mN,施归纳于n。若n=0，则有,所以对一切m,nN 有(Rm)n=Rmn。,(Rm)0,IA,R0,Rm0,假设(Rm)nRmn，则有,(Rm)n+1,(Rm)n Rm,Rmn+m,Rm(n+1),定理7.8,定理7.8 设R是A上的关系，若存在自然数s,t(st)使得Rs=Rt，则(1)对任何kN有 Rs+k=Rt+k(2)对任何k,iN有 Rs+kp+i=Rs+i，其中p=t-s(3)令S=R0，R1，Rt-1，则对于任意的qN有 RqS,证明,(1)Rs+kR

25、s RkRt RkRt+k(2)对k归纳。若k=0，则有 Rs+0 p+iRs+i假设 Rs+kp+iRs+i，其中pt-s，则,Rs+(k+1)p+i,Rs+kp+i+p,Rs+i Rp=Rs+p+i,Rs+t-s+i,Rt+i,Rs+i,由归纳法命题得证。,Rs+kp+i Rp,定理7.8,定理7.8 设R是A上的关系，若存在自然数s,t(st)使得Rs=Rt，则(1)对任何kN有 Rs+k=Rt+k(2)对任何k,iN有 Rs+kp+i=Rs+i，其中p=t-s(3)令S=R0，R1，Rt-1，则对于任意的qN有 RqS,证明,(3)任取qN，若qt，显然有RqS，若qt，则存在自然数k

26、和i使得qs+kp+i其中0ip-1,pt-s。于是RqRs+kp+iRs+i,而s+is+p-1,s+t-s-1,t-1,这就证明了 RqS。,定理7.8的说明,有穷集A上的关系R的幂序列R0，R1，是一个周期性变化的序列。就象正弦函数一样，利用它的周期性可以将R的高次幂化简为R的低次幂。例7.9 设A=a,b,d,e,f，R=,。求出最小的自然数m和n，使得mn且Rm=Rn。,解答,由R的定义可以看出A中的元素可分成两组，即a,b和d,e,f。它们在R的右复合运算下有下述变化规律：ababdefdef对于a或b,每个元素的变化周期是2。对于d，e，f，每个元素的变化周期是3。因此必有Rm=

27、Rm+6，其中6是2和3的最小公倍数。取m=0,n=6即满足题目要求。,作业八,習題1：,習題2：,作业八續,習題3：,習題4：,作业八續,習題5(只做給出的八個關系圖),習題6：,7.4 关系的性质,自反性反自反性对称性反对称性传递性,自反性和反自反性,定义7.11 设R为A上的关系，(1)若x(xAR)，则称R在A上是自反(reflexivity)的。(2)若x(xAR)，则称R在A上是反自反(irreflexivity)的。例如 全域关系EA，恒等关系IA，小于等于关系LA，整除关系DA都是为A上的自反关系。包含关系R是给定集合族A上的自反关系。小于关系和真包含关系都是给定集合或集合族上

28、的反自反关系。,例7.10,例7.10 设A=1,2,3，R1，R2，R3是A上的关系，其中R1,R2,R3说明R1，R2和R3是否为A上的自反关系和反自反关系。解答 R1既不是自反的也不是反自反的，R2是自反的，R3是反自反的。,对称性和反对称性,定义7.12 设R为A上的关系，（1）若xy(x,yARR)，则称R为A上对称(symmetry)的关系。（2）若xy(x,yARRx=y)，则称R为A上的反对称(antisymmetry)关系。例如 A上的全域关系EA，恒等关系IA和空关系都是A上的对称关系。恒等关系IA和空关系也是A上的反对称关系。但全域关系EA一般不是A上的反对称关系，除非A

29、为单元集或空集。,例7.11,例7.11 设A1,2,3，R1，R2，R3和R4都是A上的关系，其中R1,R2,R3,R4,说明R1，R2，R3和R4是否为A上对称和反对称的关系。解答 R1既是对称也是反对称的。R2是对称的但不是反对称的。R3是反对称的但不是对称的。R4既不是对称的也不是反对称的。,传递性,定义7.13 设R为A上的关系，若 xyz(x,y,zARRR)则称R是A上的传递(transitivity)关系。例如 A上的全域关系EA,恒等关系IA和空关系都是A上的传递关系。小于等于关系，整除关系和包含关系也是相应集合上的传递关系。小于关系和真包含关系仍旧是相应集合上的传递关系。,

30、例7.12,例7.12 设A1,2,3，R1，R2，R3是A上的关系，其中R1,R2,R3说明R1，R2和R3是否为A上的传递关系。解答 R1和R3是A上的传递关系，R2不是A上的传递关系。,关系性质的等价描述,定理7.9 设R为A上的关系，则（1）R在A上自反当且仅当 IA R（2）R在A上反自反当且仅当 RIA（3）R在A上对称当且仅当 RR-1（4）R在A上反对称当且仅当 RR-1 IA（5）R在A上传递当且仅当 RRR,说明,利用该定理可以从关系的集合表达式来判断或证明关系的性质。,定理7.9(4)的证明,（4）R在A上反对称当且仅当 RR-1 IA必要性。任取，有 RR-1 R R-

31、1 R R xy(R是反对称的)IA所以 RR-1 IA,充分性。任取,则有R R R R-1 RR-1 IA(RR-1 IA)xy所以 R在A上是反对称的。,定理7.9(5)的证明,（5）R在A上传递当且仅当 RRR必要性。任取，有 RR t(RR)R(因为R在A上是传递的)所以 RRR。充分性。任取,R，则RR RR R(因为RRR)所以 R在A上是传递的。,例7.13,例7.13 设A是集合，R1和R2是A上的关系，证明：(1)若R1，R2是自反的和对称的，则R1R2也是自反的和对称的。(2)若R1和R2是传递的，则R1R2也是传递的。,例7.13(1)的证明,(1)若R1，R2是自反的

32、和对称的，则R1R2也是自反的和对称的。,证明,由于R1和R2是A上的自反关系，故有IA R1 和 IA R2从而得到 IA R1R2。根据定理7.9可知 R1R2在A上是自反的。再由R1和R2的对称性有R1R1-1 和 R2R2-1根据练习七第20题的结果有(R1R2)-1R1-1R2-1R1R2从而证明了R1R2也是A上对称的关系。,例7.13(2)的证明,(2)若R1和R2是传递的，则R1R2也是传递的。,证明,由R1和R2的传递性有R1 R1 R1 和 R2 R2 R2再使用定理7.4得(R1R2)(R1R2)R1 R1R1 R2R2 R1R2 R2(R1R2)(R1 R2R2 R1)

33、(将前面的包含式代入)R1R2从而证明了R1R2也是A上的传递关系。,关系性质的特点,例7.14,例7.14 判断下图中关系的性质，并说明理由。,（1）对称的，不是自反的，不是反自反的，不是反对称的，不是传递的。（2）是反自反的，不是自反的，是反对称的，不是对称的，是传递的。（3）是自反的，不是反自反的，是反对称的，不是对称的，不是传递的。,关系的性质和运算之间的关系,闭包运算,一般来说，A上的关系不一定具有上面讨论过的某些性质，所以想到在给定的关系R的基础上，扩充一些序偶得到一个新的关系R，使新关系具有所要求的性质，但又不希望它太大。因此，讨论最小的包含R的R，使它具有所要求的性质，这就是关

34、系的闭包。,问题,已知有如上的电话网络如何增加线路构造任意两地之间都能通信(可能不直接)的电话网络，且构造代价最低？构造包含R的最小的传递关系（R的传递闭包）即可。,7.5 关系的闭包,闭包（closure）的定义闭包的构造方法闭包的性质闭包的相互关系,讓世界充滿愛,闭包的定义,定义7.14 设R是非空集合A上的关系，R的自反（对称或传递）闭包是A上的关系R，使得 R满足以下条件：（1）R是自反的（对称的或传递的）（2）RR（3）对A上任何包含R的自反（对称或传递）关系R有R R。一般将R的自反闭包记作r(R)，对称闭包记作s(R)，传递闭包记作t(R)。,闭包的构造方法,定理7.10 设R为

35、A上的关系，则有（1）r(R)RR0（2）s(R)RR-1（3）t(R)RR2R3 证明思路(1)和(2)：证明右边的集合满足闭包定义的三个条件。(3)采用集合相等的证明方法。证明左边包含右边，即t(R)包含每个Rn。证明右边包含左边，即RR2具有传递的性质。,定理7.10(1)的证明,（1）r(R)RR0,证明,由IAR0 RR0，可知RR0是自反的，RRR0。设R是A上包含R的自反关系，则有RR和IAR。任取，必有 RR0 RIA RRR 所以 RR0 R。综上所述，r(R)RR0。,定理7.10(2)的证明,（2）s(R)RR-1,证明,RRR-1。,证明RR-1是对称的，任取，有 RR

36、-1 RR-1 R-1R RR-1 所以 RR-1 是对称的。,综上所述，s(R)RR-1。,设R是包含R的对称关系，任取，有 RR-1 RR-1 RR RR RR R 所以 RR-1 R。,定理7.10(3)的证明,（3）t(R)RR2R3,证明,先证RR2 t(R)成立，为此只需证明对任意的正整数n有 Rn t(R)即可。用归纳法。n1时，有 R1R t(R)。假设Rnt(R)成立，那么对任意的有 Rn+1Rn R t(RnR)t(t(R)t(R)t(R)（因为t(R)是传递的）这就证明了Rn+1 t(R)。由归纳法命题得证。,定理7.10(3)的证明,（3）t(R)RR2R3,证明,再证

37、t(R)RR2成立，为此只须证明RR2是传递的。任取,，则 RR2 RR2 t(Rt)s(Rs)ts(Rt Rs)ts(Rt Rs)ts(Rt+s)RR2从而证明了RR2是传递的。,为什么？,根据t(R)的定义，t(R)是任意一个包含R的传递的关系的子集。,推论,推论 设R为有穷集A上的关系，则存在正整数r使得t(R)=RR2Rr证明 由定理7.6和7.10(3)得证。例题 求整数集合Z上的关系R|a|a|ab|ab s(R)RR-1|a|b|ab,通过关系矩阵求闭包的方法,设关系R，r(R)，s(R)，t(R)的关系矩阵分别为M，Mr，Ms和Mt，则Mr ME对角线上的值都改为1Ms MM若

38、aij1，则令aji1Mt MM2M3沃舍尔算法其中E是和M同阶的单位矩阵，M是M的转置矩阵。注意在上述等式中矩阵的元素相加时使用逻辑加。,通过关系图求闭包的方法,设关系R，r(R)，s(R)，t(R)的关系图分别记为G，Gr，Gs，Gt，则Gr，Gs，Gt的顶点集与G的顶点集相等。除了G的边以外，以下述方法添加新的边。1)考察G的每个顶点，如果没有环就加上一个环。最终得到的是Gr。2)考察G的每一条边，如果有一条xi到xj的单向边，ij，则在G中加一条边xj到xi的反方向边。最终得到Gs。3)考察G的每个顶点xi，找出从xi出发的所有2步，3步，n步长的路径（n为G中的顶点数）。设路径的终点

39、为。如果没有从xi到(l=1,2,k)的边，就加上这条边。当检查完所有的顶点后就得到图Gt。,例7.15,例7.15 设A=a,b,c,d，R=,，则R和r(R)，s(R)，t(R)的关系图如下图所示。其中r(R)，s(R)，t(R)的关系图就是使用上述方法直接从R的关系图得到的。,Warshall 算法,自学。,闭包的主要性质,定理7.11 设R是非空集合A上的关系，则（1）R是自反的当且仅当r(R)R。（2）R是对称的当且仅当s(R)R。（3）R是传递的当且仅当t(R)R。证明（1）充分性。因为Rr(R)，所以R是自反的。必要性。显然有R r(R)。由于R是包含R的自反关系，根据自反闭包定

40、义有r(R)R。从而得到r(R)=R。,闭包的主要性质,定理7.12 设R1和R2是非空集合A上的关系，且R1 R2，则（1）r(R1)r(R2)（2）s(R1)s(R2)（3）t(R1)t(R2)证明：(1)任取，有 r(R1)R1IA R1 IA R2 IA R2IA r(R2),关系性质与闭包运算之间的联系,定理7.13 设R是非空集合A上的关系，（1）若R是自反的，则s(R)与t(R)也是自反的。（2）若R是对称的，则r(R)与t(R)也是对称的。（3）若R是传递的，则r(R)是传递的。证明：只证（2）。,定理7.13(2)的证明,（2）若R是对称的，则r(R)与t(R)也是对称的。证

41、明r(R)是对称的。由于R是A上的对称关系，所以RR-1，同时IAIA-1。r(R)-1(RR0)-1(RIA)-1R-1IA-1RIAr(R)所以，r(R)是对称的。,定理7.13(2)的证明,（2）若R是对称的，则r(R)与t(R)也是对称的。下面证明t(R)的对称性。任取 t(R)n(Rn)n(Rn)（因为Rn是对称的，证明见课本）t(R)所以，t(R)是对称的。,课堂练习,证明定理7.13的（3）若R是传递的，则r(R)是传递的。证明：根据传递性的充要条件，證明 r(R)r(R)r(R)r(R)r(R)=(RIA)(RIA)=R R R IA IA R IA IA R R R IA=R

42、 IA=r(R),定理7.13的讨论,从这里可以看出，如果计算关系R的自反、对称、传递的闭包，为了不失去传递性，传递闭包运算应该放在对称闭包运算的后边，若令tsr(R)表示R的自反、对称、传递闭包，则 tsr(R)=t(s(r(R),反例 A=1，2，3，R=是传递的s(R)=,显然s(R)不是传递的。,判定下列关系具有哪些性质,1、在全体中国人所组成的集合上定义的“同姓”关系；2、对任何非空集合A，A上的全关系；3、三角形的“相似关系”、“全等关系”；4、直线的“平行关系”；5、“朋友”关系；,解：1，2，3都具有自反性，对称性和传递性；4 具有反自反性、对称性、传递性，不具有自反性5 具有

43、对称性，不具有自反性和传递性。,等价关系,7.6 等价关系与划分,定义7.15 设R为非空集合上的关系。如果R是自反的、对称的和传递的，则称R为A上的等价关系(equivalent relation)。设R是一个等价关系，若R，称x等价于y，记做xy。,1.幂集上定义的“”关系；2.整数集上定义的“”关系；3.全体中国人所组成的集合上定义的“同性别”关系。,判定下列关系是否是等价关系?,不具有对称性,不具有对称性，自反性,是等价关系,例,在时钟集合A1,24上定义整除关系：R|x,yA)(x-y)被12所整除)。（1）写出R中的所有元素；（2）画出R的关系图；（3）证明R是一个等价关系。,（2

44、）此等价关系的关系图：,（1）R=,1,13,2,14,3,15,12,24,（3）等价关系的证明：1、对xA，有(x-x)被12所整除，所以R，即R是自反的。2、对x,yA,若R,有(x-y)被12整除，则(y-x)-(x-y)被12整除,所以,R,即R是对称的。3、对x,y,zA,若R且R,有(x-y)被12所整除且(y-z)被12所整除,所以(x-z)(x-y)(y-z)被12所整除,所以,R,即R是传递的.由1,2,3知R是等价关系。,从本例可以看出,关系R将集合A分成了如下的12个子集：1,13,2,14,3,15,4,16,5,17,6,18,7,19,8,20,9,21,10,2

45、2,11,23,12,24。,这12个A的子集具有如下特点：1、在同一个子集中的元素之间都有关系R；2、不同子集的元素之间无关系R。,等价类,定义7.16 设R为非空集合A上的等价关系，xA，令 xR=y|yAxRy称xR为x关于R的等价类，简称为x的等价类，简记为x或 x。,x的等价类是A中所有与x等价的元素构成的集合。前例中的等价类是：1131,132142,143153,154164,16,整数集合Z上的模n等价关系,设x是任意整数，n为给定的正整数，则存在唯一的整数q和r，使得xqn+r其中0rn-1，称r为x除以n的余数。例如n3，那么8除以3的余数为1，因为-8-33+1对于任意的

46、整数x和y，定义模n相等关系xy xy(mod n)不难验证它是整数集合Z上的等价关系。将Z中的所有整数根据它们除以n的余数分类如下：余数为0的数，其形式为nz，zZ余数为1的数，其形式为nz+1，zZ 余数是n-1的数，其形式为nz+n-1，zZ以上构成了n个等价类，使用等价类的符号可记为inz+i|zZ，i=0，1，n-1,等价类的性质,定理7.14 设R是非空集合A上的等价关系，则（1）xA，x是A的非空子集。（2）x,yA，如果xRy，则xy。（3）x,yA，如果R，则x与y不交。（4）x|xAA。证明（1）由等价类的定义可知，xA有xA。又由于等价关系的自反性有xx，即x非空。,定理

47、7.14,（2）x,yA，如果xRy，则x=y。任取z，则有 zx R R(因为R是对称的)R R R(因为R是传递的)R(因为R是对称的)zy。所以 xy。同理可证 yx。因此，x=y。,定理7.14,（3）x,yA，如果R，则x与y不交。假设 xy，则存在 zxy，从而有 zxzy，即RR成立。根据R的对称性和传递性，必有R，与R矛盾，即假设错误，原命题成立。,定理7.14,（4）x|xAA。先证 x|xAA任取y，yx|xA x(xAyx)yA(因为xA)从而有x|xA A。再证 Ax|xA 任取y，yA yyyA yx|xA从而有Ax|xA成立。综上所述得 x|xAA。,商集,定义7.

48、17 设R为非空集合A上的等价关系，以R的所有等价类作为元素的集合称为A关于R的商集(quotient set)，记做A/R，即A/R=xR|xA例7.16中的商集为1,4,7,2,5,8,3,6整数集合Z上模n等价关系的商集是 nz+i|zZ|i=0,1,n-1,计算商集A/R的通用过程：,（1）任选A中一个元素a，计算aR；（2）如果aRA，任选一个元素bA-aR，计算bR；（3）如果aRbRA，任选一个元素cA-aR-bR，计算cR；以此类推，直到A中所有元素都包含在计算出的等价类中。,划分,定义7.18 设A为非空集合，若A的子集族(P(A)，是A的子集构成的集合)满足下面的条件：（1

49、）（2）xy(x,yxyxy)（3）=A则称是A的一个划分(partition)，称中的元素为A的划分块。,说明,设集合是A的非空子集的集合，若这些非空子集两两不相交，且它们的并等于A，则称是集合A的划分。,试给出非空集合A上2个不同的划分解（1）在A中设定一个非空子集A1，令A2=A-A1，则根据集合划分的定义，A1,A2就构成了集合A的一个划分，见图(a)；（2）在A中设定两个不相交非空子集A1和A2，令A3=A-(A1A2)，则根据集合划分的定义，A1,A2,A3就构成了集合A的一个划分，见图(b)。,例7.17,例7.17 设Aa,b,c,d，给定1,2,3,4,5,6,如下：1=a,

50、b,c,d 2=a,b,c,d 3=a,a,b,c,d 4=a,b,c 5=,a,b,c,d 6=a,a,b,c,d判断哪一个是A的划分1和2是A的划分，其它都不是A的划分。因为3中的子集a和a,b,c,d有交，4A，5中含有空集，而6根本不是A的子集族。,商集与划分,商集就是A的一个划分，并且不同的商集将对应于不同的划分。反之，任给A的一个划分，如下定义A上的关系R：R=|x,yAx与y在的同一划分块中则不难证明R为A上的等价关系，且该等价关系所确定的商集就是。由此可见，A上的等价关系与A的划分是一一对应的。,例7.18,例7.18 给出A1,2,3上所有的等价关系,这些划分与A上的等价关系