离散数学课件第四章-二元关系和函数.ppt

刘师少,Tel：86613747（h）E-mail：,授课:51学时,教学目标:知识、能力、素质,Discrete Mathematics,第四章 二元关系和函数,4.1集合的笛卡尔积与二元关系4.2 关系的运算4.3 关系的性质4.4 关系的闭包4.5 等价关系和偏序关系4.4 函数的定义和性质4.4 函数的复合和反函数4.4 例题分析,说起关系这个词，对我们并不陌生，世界上存在着各种各样的关系，人与人之间的“同志”关系；“同学”关系；“朋友”关系；“师生”关系；“上下级”关系；“父子”关系；两个数之间有“大于”关系；“等于”关系和“小于”关系；两个变量之间有一定的“函数”关系；计算机内两电路间有导线“连接”关系；程序间有“调用”关系等等。所以对关系进行深刻的研究，对数学与计算机科学都有很大的用处。,再如:电影票与座位之间有对号关系。设：X 表示电影票的集合 Y 表示座位的集合，则，对于任意的x X和y Y，必有 x 与 y 有对号“对号”关系 则上述问题可表达为xRy或xRy，亦可记为(x，y)R或(x，y)R 因此我们可以看到对号关系R是序偶的集合,在这一章我们要研究集合内元素间的关系以及集合之间元素之间的关系，这就是“关系”与“函数”。它们是很重要的基本数学概念，在数学领域中均有很大的作用，并且对研究计算机科学中的许多问题如数据结构、数据库、情报检索、算法分析、计算理论等都是很好的数学工具。,关系的引入 例4.0 设一旅馆有n个房间，每个房间可住两个旅客，所以一共可住2n个旅客，在旅馆内，旅客与房间有一定关系，用 R 表示“某旅客住在某房间”这种关系。设 n=3 表示旅馆共有3个房间,分别记以 1,2,3 可住6个旅客分别记以 a,b,c,d,e,f,这些旅客住的房间如右下图所示,1,2,3,a,b,c,d,e,f,满足 R 的所有关系可看成是一个有序偶的集合，这个集合可叫 RR=,若令 A=a,b,c,d,e,f B=1,2,3 则例中关系的每一元素均属于AB亦即 R 是AB的子集，并称此关系为从 A 到 B 的关系 R。,4.1 集合的笛卡尔积与二元关系,定义4.1由两个元素x,y（允许x=y）按一定顺序排列成的二元组叫做一个有序对或序偶，记作,其中x是它的第一元素，y是它的第二元素。有序对具有以下性质：(1)当xy时，(2)=x=w y=v例4.1：已知=，求 x 和 y。解：由有序对相等的充要条件得 x+3=y+7 y-2=3y-x 解得 x=6,y=2,4.1 集合的笛卡尔积与二元关系,定义4.2 一个有序n元组(n3)是一个有序对，其中第一个元素是一个有序n-1元组，一个有序n元组记作,即=,xn 例如：空间直角坐标系中点的坐标,等都是有序3元组。n维空间中点的坐标或n维向量都是有序n元组。形式上也可以把看成有序1元组。,定义4.3 设A，B为集合，用A中元素为第一元素，B中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做A和B的笛卡儿积，记作AB。笛卡儿积的符号化表示为：A B=|x A y B例如：若A=1,2,B=a,b,c,则AB=,BA=,易知：若|A|=m,(即集合A的元素的个数),|B|=n,则|AB|=|BA|=m n,4.1 集合的笛卡尔积与二元关系,主菜鱼香肉丝家常豆腐宫保鸡丁酸辣土豆丝蒜茸油麦菜,汤紫菜蛋花汤鱼头豆腐汤鸡蛋西红柿汤酸辣蔬菜汤,由前面的定义可知：有序对就是有顺序的数组，如，x,y 的位置是确定的，不能随意放置。注意：有序对，以a,b为元素的集合a,b=b,a；有序对(a,a)有意义，而集合a,a不成立，因为它只是单元素集合，应记作a。笛卡儿积是一种集合合成的方法，把集合A，B合成集合AB，规定ABxA,yB由于有序对中x,y的位置是确定的，因此AB的记法也是确定的，不能写成BA。笛卡儿积也可以多个集合合成 A1A2An。笛卡儿积的运算性质。,笛卡儿积的性质：1、对任意集合A，根据定义有 A=A=2、一般来说，笛卡儿积不满足交换律，即 ABBA（当A B B、A 时）3、笛卡儿积不满足结合律，即(AB)CA(B C)（当ABC时）4、笛卡儿积运算对并和交运算满足分配律，即 A(BC)=(AB)(A C)(BC)A=(BA)(C A)A(BC)=(AB)(A C)(BC)A=(BA)(C A),4.1 集合的笛卡尔积与二元关系,例4.2 证明：(BC)A=(BA)(C A)对于(BC)A x(B C)y A xB x C y A xB x C y A y A(xB y A)(x C y A)B A C A(BA)(C A)(BC)A=(BA)(C A),4.1 集合的笛卡尔积与二元关系,例4.3：设A，C，B，D为任意集合，判断以下命题是否为真，并说明理由。(1)AB=AC=B=C(2)A-(BC)=(A-B)(A-C)(3)存在集合A,使得A A A.,解：(1)不一定为真。反例A=,B、C为任意不相 等的非空集合。(2)不一定为真。反例A=1,B=2,C=3.(3)为真。当 A=时成立。,定义4.4 设A1,A2,An,是集合(n2),它们的n阶笛卡儿积记作A1A2An，其中 A1A2An=|x1A1x2A2xnAn 当A1=A2=An=A时,将起n阶笛卡儿积记作An例如，A=a,b,则 A3=AAA=a,ba,ba,b=,4.1 集合的笛卡尔积与二元关系,例4.6 设集合 A=a,b,B=1,2,3,C=d,求ABC，BA。解 先计算AB,ABC,d,BA,例4.7 设集合A1,2,求AP(A)。解 P(A)=,1,2,1,2AP(A)1,2,1,2,1,2=,定义4.5 如果一个集合符合以下条件之一：(1)集合非空，且它的元素都是有序对(2)集合是空集 则称该集合为一个二元关系，记作R，简称为关系。对于二元关系R，若 R,可记作xRy;如果 R,则记作xRy。例：R1=,R2=5,6,7 aR1b,1R12,5R16,4.1 集合的笛卡尔积与二元关系,二元关系是两种客体之间的联系，例如某学生学习语文、数学、外语，表示为 A语文,数学,外语功课的成绩分四个等级，记作 BA，B，C，D于是该生成绩的全部可能为ABAB,而该生的实际成绩 P,可以看出P是AB的一个子集，它表示了功课与其成绩的一种关系。由此可见：两个集合之间的二元关系，实际上就是两个元素之间的某种相关性。,再如：若A=，B=1，2，3，求AB,BA，AA，BB，（AB）（BA）,解：AB=(，1)，(，2)，(，3)，(，1)，(，2)，(，3)BA=(1，)，(1，)，(2，)，(2，)，(3，)，(3，)AA=(，)，(，)，(，)，(，)BB=(1，1)，(1，2)，(1，3)，(2，1)，(2，2)，(2，3)，(3，1)，(3，2)，(3，3)（AB）（BA）=由上例可看出：ABBA,程序实现,定义4.6 设A，B为集合，AB的任何子集所定义的二元关系叫做从A到B的二元关系，特别当A=B时则叫做A上的二元关系。例4.7：若A=a,b，B=2,5,8，则 A B=,令 R1=,R2=,R3=因为R1 A B，R2 A B，R3 A B，所以R1，R2和 R5均是由A到B的二元关系因为只讨论二元关系，所以今后无特别声明，术语“关系”皆指二元关系？,又例：若A=a,b，B=2,5,8，则 BA=,令 R4=,R5=,因为R4 BA，R5 BA，所以R4和 R5均是由B到A的关系又 BB=,令 R6=,R7=,因为R6 BB，R7 BB，所以R6和 R7均是集合B上的关系。,若集合|A|=n,则集合A上的二元关系有多少个？答曰：|A|=n，则|A A|=n2,A A的任一个子集就是A上的二元关系，即P(A)=2n 个。,例4.8 A=1,2 则A A有n2 个不同的二元关系 AA=1,21,2=,AA的任一个子集就是A A的幂集，即P(A)P(A)=,集合中的元素不分顺序,若集合A=a,b,c 则A的幂集，P(A)为P(A)=,a,b,c,a,b,a,c,b,c,a,b,c（注a,a=a b,b=b c,c=c）,三类特殊的关系 对于任何集合A，空集 是A A的子集，叫做A上的空关系 定义EA=|xA yA=AA为全域关系 定义IA=|xA 为恒等关系例：若A=1,2，则 EA=,IA=,除上述三类特殊的关系外，还有一些常用的关系，如：LA=|x,yA xy(A R)为实数集上的小于等于关系。DA=|x,yA x整除y(A Z*)为非正整数集上的整除关系。R=|x,yA xy(A 是集合族)为集合上的包含关系。类似地还可以定义大于等于关系、大于关系、小于关系、真包含关系等。,4.1 集合的笛卡尔积与二元关系,例4.9：设A=1,2,3,4，请表示下列关系。(1)R=|x是y的倍数(2)R=|(x-y)2 A(3)R=|x除y是素数(4)R=|xy,4.1 集合的笛卡尔积与二元关系,解(1)DA=,(2)R=,(3)DA=,(4)R=,例4.9_1 设A=1，2，3，B=4，5，6，并定义R1，R2为从A到B的关系；R3为从B到A的关系；（aA，bB）(1)当且仅当：a能整除b时，aR1b；(2)当且仅当：a是b的整数倍时，aR2b；(3)当且仅当：b是a的整数倍时，bR3a；试写出R1，R2，R3。解：R1=(1,4),(1,5),(1,6),(2,4),(2,6),(3,6)R2=；R3=(4,1),(5,1),(6,1),(4,2),(6,2),(6，3),|A|=n,|B|=m,A,B中的元素已按一定的次序排列若A=x1,x2,xn,B=y1,y2,ym 且RAB,若 1 若 xiRyj r ij=(i=1,2,n j=1,2,m)0 若xiRyj则称矩阵M(R)=(rij)n m 为R的关系矩阵。,有穷集合上的二元关系的三种表示方法：集合表示法（前已使用）关系矩阵法 关系图 关系矩阵是表示关系的另一种有效的方法，其优点是可以利用矩阵作为研究关系的手段，而且这样做便于计算机进行处理。设R：AB，A和B都是有限集，且,设A，B为集合，AB的任何子集Ri AB则称Ri所定义的二元关系叫做从A到B的二元关系，特别当A=B时则叫做A上的二元关系,则 r11 r12 r1n(r ij)=r21 r22 r2n rn1 rn2 rnn是R的关系矩阵，记作MR。,关系矩阵法若A=x1,x2,xn,B=y1,y2,yn 则R的关系矩阵是一个n行n列矩阵M(R)=(rij)nn,其中元素 rij 为：1 若 xiRyj r ij=(i,j=1,2,n)0 若xiRyj,0 1 1 1MR=0 0 1 1 0 0 0 1 0 0 0 0,例4.10 A=1,2,3,4 R为A上的小于关系，则R为：R=,R的关系矩阵为：,1 2 3 4,1 2 3 4,例4.11 设集合A2,3,4,B=8,9,12,14.R是由A到B的二元关系，定义：R=|a整除b写出R的表达式和关系矩阵.解 R=,8 9 12 14 2 1 0 1 1R的关系矩阵为.MR=3 0 1 1 0 4 1 0 1 0,关系图关系图是表示关系的一种直观形象的方法，设R：AB，A和B都是有限集，A=x1,x2,xn,B=y1,y2,ym 关系R的有序偶 可用图中从结点xi 到yj 的有向边表示，这样即可将关系用图表示之。例4.12 设 R:AB，A=x1,x2,x3,x4,B=y1,y2,y3 R=,R的关系如下图所示,x1,x2,x3,x4,y1,y2,y3,关系图关系图是表示关系的一种直观形象的方法，设R：AB，A和B都是有限集，A=x1,x2,xn,B=y1,y2,ym 关系R的有序偶 可用图中从结点xi 到yj 的有向边表示，这样即可将关系用图表示之。例4.13 设 R:AA，A=a,b,c,d R=,R的关系如下图所示,a,b,c,d,其中 c 到 c的边称为环,定义4.8设R是二元关系(1)R中所有的有序对的第一元素构成的集合称为R的 定义域，记作domR,形式化表示为：domR=x|y(R)(2)R中所有的有序对的第二元素构成的集合称为R的值域，记作ranR,形式化表示为：ranR=y|x(R)(3)R的定义域和值域的并集称为R的域，记作fldR,形式化表示为：fldR=domR ranR,4.2 关系的运算,例4.14 下列关系都是整数集Z上的关系，分别求出它们的定义域和值域 R1=|x,yZxy(2)R2=|x,yZx2+y2=1(3)R3=|x,yZy=2x R4=|x,yZ|x|=|y|=3解(1)dom R1=ram R1=Z R2=,dom R2=0,1,-1 ram R2=0,1,-1(3)dom R3=Z ram R3=2z|zZ 即偶数集(4)dom R4=-3,3 ram R4=-3,3,1,0,-1,-1,0,1,dom R2,ram R2,R2,210-1-2,43210-1-2-3-4,dom R3=Z,ram R3,R3,例4.15 设 R1=,R2=,求其定义域和值域解 题目没有告诉我们 R1 和 R2 是由什么集合到什么的 关系,这对于我们解此题是无关紧要的,事实上,不论R1 和 R2 是定义在何种集合上的关系,据定义域和值域的定义domR=x|y(R)ranR=y|x(R)有 dom R1=1,2,3 dom R2=1,2,4 ram R1=2,4,3 ram R2=3,4,2,规律:集合R1 和 R2 中序偶中的第一个元素的集合即为其定义域,序偶中的第二个元素的集合即为其值域.,如果此题再加上求R1R2及 R1R2定义域和值域,则因为R1R2=,R1R2=所以 domR1domR2=1,2,3,4 ramR1 ramR2=2,3,4,定义4.9 设F,G为任意的关系,A 为集合，则(1)F的逆记作F-1,F-1=|yFx(2)F与G的合成记作F G，其中 F G=|z(xGzzFy 或 F G=|z(xFzzGy p87(3)F在A上限制记作FA FA=|xFy xA)(4)A在F下的象记作FA FA=ran(FA),4.2 关系的运算,逆关系：设R是一个X到Y的关系，则Y到X的关系R-1：R-1=|R 称为R的逆关系。例4.16 设X=1,2,3 Y=a,b,c 且设R是从X到 Y的关系 R=,则 R-1=,例4.17 设X=x1,x2,x3 Y=y1,y2,y3 且设R是从X到Y的 关系 R=,的逆关系 R-1=,如下图所示：,x1,x2,x3,y1,y2,y3,y1,y2,y3,x1,x2,x3,R,R-1,合成关系（或复合关系）设R是一个X到Y的关系，S是一个Y到Z的关系,则R与S的合成关系(或复合关系):R S 为：R S=|z(xSzzRy 例4.18 设 X=x1,x2,x3,Y=y1,y2,y3,Z=z1,z2,z3 从X 到 Z的关系 S=,从Z 到 Y的关系 R=,则X到Y的关系 R S=,X Z Y X Y,R,S,R S,x1,x2,x3,z1,z2,z3,y1,y2,y3,x1,x2,x3,y1,y3,y2,例4.19 设有集合 A=4,5,8,15,B=3,4,5,9,11C=1,6,8,13,F 是由 A 到 B 的关系,G 是由 B 到 C 的关系,分别定义为 F=|b-a|=1 G=|b-c|=2或|b-c|=4求合成关系G F和F G 解 先求G F,由题意知 F=,G=,G F=,例4.19(续)设有集合 A=4,5,8,15,B=3,4,5,9,11C=1,6,8,13,F 是由 A 到 B 的关系,G 是由 B 到 C 的关系,分别定义为 F=|b-a|=1 G=|b-c|=2或|b-c|=4求合成关系G F和F G 解 再求F G,由题意知 G=,F=,F G=,例4.20:设A=2,3,G=,R=,则R-1,R G，G R，RA,R,RA,R分别是 R-1=,R G=,G R=,RA=|x R y xA=R=RA=ran(RA)=2 R=注意：逆运算的优先级高于其他运算，而所有的关系运算都优于集合运算。,例4.21：设F=,求F F，Fa，Fa解 因为 F=,F=,所以F F=由公式FA=|xFy xA)有 Fa=由公式FA=ran(FA)有 F a=ran(Fa)=ran=a,定义域,值域,综上所述,两个关系的合成,如F与G的合成记作F G，其中 F G=|z(xGzzFy 称为关系的合成运算。它是对关系 的一种二元运算，通过这种运算，可由两个已知关系产生一个新的关系。,例4.22 设A=1,2,3,4，B=2,3,4，C=1,2,3，且R1=|aA bB(a+b)=5，R2=|bB cC(bc)=2，求R1R2。,解：由题意知：R1=，R2=，R1R2=,例4.23 设 R1=，R2=，求 R1R2；R2R1；R1R1；(R1R2)R1；R1(R2R1)。解：R2R1=，R1R2=(不满足交换律)R1R1=，(R1oR2)R1=R1(R2oR1)=(满足结合律),定理4.1 设F、G、H是任意关系,则(1)(F-1)-1=F(2)dom(F-1)=ranF,ranF-1=domF(3)(F G)H=F(G H)(4)(F G)-1=G-1 F-1证明:(1)任取,由逆的定义有(F-1)-1 F-1 F(F-1)-1=F(2)任取x,xran F-1 y(F-1)y(F)x dom F ran F-1=dom F同理可证 dom(F-1)=ran F,定理4.2 设F、G、H是任意关系,则(1)F(GH)=F G F H(2)(GH)F=G F H F(3)F(GH)F G F H(4)(GH)F G F H F本定理对有限个关系的并和交都成立。R(R1R2 Rn)=R R1R R2R Rn(R1R2 Rn)R=R1 RR2 RRn RR(R1R2 Rn)R R1R R2 R Rn(R1R2 Rn)R R1 RR2 RRn R,定义4.10 设R是A上的关系,n为自然数，则R的n次幂 规定如下(1)R0=|xA(2)Rn=Rn-1 R n1 由定义可以知道R0就是A上的恒等关系IA，不难证明下面的等式 R R0=R=R0 R 由这个等式立即可以得到 R1=R0 R=R例4.24 设A=a,b,c,d,R=,求R0，R1，R2，R3，R4和R5,解 R0=,R1=R0 R=,=,R2=R R=,=,R3=R2 R=,=,R4=R3 R=,=,R5=R4 R=,=,例4.25 设A=1，2，3，4，A上的关系 R=|aA bA(ab)=1，求：R2，R3，R4解：因为R=，所以R2=，R3=，R4=。,定理4.3 设R是A上的关系,m,n 为自然数，则下面的等式成立(1)Rm Rn=Rm+n(2)(Rm)n=Rmn证明：(1)任给m，对n作归纳法。n=0时，Rm R0=Rm=Rm+0。假设Rm Rn=Rm+n，那么RmRn+1=Rm(RnR1)=(RmRn)R1=Rm+nR1=Rm+n+1=Rm+(n+1)。(2)任给m，对n作归纳法。n=0时，(Rm)0=R0=Rm0。假设(Rm)n=Rmn。那么(Rm)n+1=(Rm)n Rm=Rmn Rm=Rmn+m=Rm(n+1),0 1 1 0 0 1 1 0 1 1 1 0M 2=MM=1 0 0 0 1 0 0 0=0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0,1 1 1 0 0 1 1 0 1 1 1 0M 3=M2M=0 1 1 0 1 0 0 0=1 1 1 0 1 1 1 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0,例4.25：设 A=1,2,3,4,R 是 A 上二元关系，关系矩阵为,0 1 1 0M=1 0 0 0 0 1 1 0 0 0 0 0,解：R，R2,R3 的关系矩阵分别为：,求 R 3。(M为R的关系矩阵),设 R 是 A 上的关系，R 的性质主要有以下 5 种(1)若x(x A R),则称 R 在 A 上是自反的。也就是说，对RAA，若A中每个x，都有xRx，则称R是自反的，即 A上关系R是自反的x(xAxRx)该定义表明了，在自反的关系R中，除其他有序对外，必须包括有全部由每个xA所组成的元素相同的有序对例如：设A=1,2,3,R 是 A 上的关系，R=,则 R 是自反的,4.3 关系的性质,设 R 是 A 上的关系，R 的性质主要有以下 5 种(2)若x(x A R),则称 R 在 A 上是反自反的也就是说，对RAA，若A中每个x，有xRx，则称R是反自反的，即 A上关系R是反自反的x(xAxRx)该定义表明了，一个反自反的关系R中，不应包括有任何相同元素的有序对。例如：设A=1,2,3，R 是 A 上的关系，R=,R是反自反的,4.3 关系的性质,对关系图：若 R 是自反的,则每个结点都有自回路出现.若R是反自反,则每个结点没有自回路出现。对关系矩阵：若R是自反的,当且仅当在关系矩阵中，对角线上的所有元素都是1，若R是反自反的,当且仅当在关系矩阵中，对角线上的所有元素都是0。,应该指出，任何一个不是自反的关系，未必是反自反的；反之，任何一个不是反自反的关系，未必是自反的。这就是说，存在既不是自反的也不是反自反的二元关系。例如：设A=1,2,3,R 是 A 上的关系，R=,缺少 则 R是既不是自反的，也不是反自反的,4.3 关系的性质,(3)若x y(x,yA R R),则称R 在A上是对称的。也就是说,对RAA,对A中每个x和y,若xRy,则yRx,称R是对称的,即 A上关系R是对称的(x)(y)(x,yAxRyyRx)该定义表明了，在表示对称的关系R的有序对集合中，若有有序对，则必定还会有有序对。例如：设A=1,2,3,R是A上的关系，R4=,则 R 是对称的,(4)若x y(x,yA R xy R),则称R在A上是反对称的。(隐含x=y R)也就是说,对RAA，对A中每个x和y，若xRy且yRx，则x=y，称R是反对称的，即A上关系R是反对称的(x)(y)(x,yAxRyyRxx=y)该定义表明了，在表示反对称关系R的有序对集合中，若存在有序对和，则必定是x=y。或者说，在R中若有有序对，则除非x=y，否则必定不会出现。例如：设A=1,2,3,R=,是A上的关系，则 R是反对称的,判断一个关系是否反对称,通俗地讲就是对于所有的a,bA,若ab,则序偶,至多只有一个出现在关系R中。如R=,有些关系既是对称的又是反对称的还有的关系既不是对称的又不是反对称的，例如：设A=1,2,3,R6,R7是A上的关系，R6=R7=,则 R6是对称的，也是反对称的 R7既不是对称的又不是反对称的再如，A=a,c,b,中 R=,既不是对称的又不是反对称的。,例4.26 设A=1，2，3则R1=,在A上是自反的，对称的，反对称的。R2=,在A上既不是对称的，也不是对反称的。R3=,在A上是对称的，但不是反对称的。R4=,),在A上不是对称的，但是反对称的。,例4.27 设A=1,2,3,4,5,A 上的关系R为 R=|a-b是偶数 用列举法表示 R R是否自反、对称、反对称？解:R=,对任意aA,a-a=0是偶数R 是自反关系 又对任意a,bA,若a-b是偶数,则b-a也 是偶数R 是对称关系。当ab时，有和 同时出现在 R中,例如,R 不是反对称关系。,若关系R是对称的，当且仅当关系矩阵关于主对角线是对称的，且在关系图上，任何两个结点间若有定向弧线，必是成对反向出现。若关系R是反对称的，当且仅当关系矩阵中以主对角线对称的元素不能同时为1，在关系图上两个不同结点间的定向弧不能成对出现。,R1=,;R2=,R3=,;R4=,2,(5)xyz(x,y,zARRR)则称R在A上是传递的关系。也就是说,对RAA，对于A中每个x,y,z，若xRy且yRz，则xRz，称R是传递的，即A上关系R是传递的(x)(y)(z)(x,y,zAxRyyRzxRz)该定义表明了，在表示可传递关系R的有序对集合中，若有有序对和，则必有有序对。,换句话说,设R为定义在集合A上的二元关系，如果对于任意a，b，cA，每当有 aRb 且有 bRc时，就有aRc，则称关系R在A上是可传递的。即：R在A上传递 abc(aA)(bA)(cA)(aRb)(bRc)aRc)例4.28 设A=a，b，c，dR1=，R2=，,，R3=，R1，R2,R3是可传递的。,传递性在关系图上表现为：从一个结点到另一个结点，如果是可达的，则必有长度为1的路。,c,a,b,d,例4.29 设A=a，b，c，d，试讨论下列关系的性质R1=，R2=，R1是自反的，对称的，可传递的。R2不是自反，是反自反。反对称，可传递的,(5)xyz(x,y,zARRR)则称R在A上是传递的关系。例4.30 设A=1,2,3,4,5,A 上的关系R为 R=|a-b是偶数 用列举法表示 R R是否是可传递的？解:R=,对于任意的 a,b,c A 若a-b=2m,b-c=2n,则a-c=(a-b)+(b-c)=2(m+n)也是偶数。因此A是可传递的。R R R,例4.31 设 A=1,2,3,4,5,6,7,8,9,10 R是A上的关系，R=|x,yA x+y=10 说明R具有哪些性质。,4.3 关系的性质,解：R=,易知 R既不是自反也不是反自反的 R是对称的 R不是反对称的 R不是传递的。,P1,P3,P4,P2,这个关系如右图所示。我们知道，调用关系是传递的，如P1能调用P2，P2能调用P4，则P1亦能调用P4。我们希望在R的基础上建立一个满足传递性的新关系，譬如说，下面的关系R即是这样一个关系,4.4 关系的闭包 什么叫一个关系上的闭包呢？设有四个程序所组成的集合 P=P1,P2,P3,P4 上的“调用”关系 R：R=,R=,当然满足这个条件的关系不仅仅R一个，如下面的关系R亦是R=,我们选用满足这个条件的最小者，在这个例子中即为R。这个R我们就叫做R上的传递闭包。R是一个新关系，它是在集合P上的一个新的调用关系 显然有R R R R 选用满足这个条件的最小者R,这个新关系叫做R上的传递闭包，它是在集合P上的一个新的调用关系。对于关系的自反性、对称性、传递性均可建立闭包,定义4.11 设R是非空集合A上的关系，R的自反(对称或传递)闭包是A上的关系R,使得R满足以下条件:(1)R是自反(对称或传递)的(2)R R(3)对A上的任何包含R的自反(对称或传递)关系R 有R R 一般将R的自反闭包记作r(R),对称闭包记作s(R)，传递闭包记作t(R)。,4.4 关系的闭包,例4.33 设A=a，b，c，d，试讨论下列关系的性质 R=，R=，,R=，,c,a,b,d,R=，,R=，,闭包：包含一些给定对象，具有指定性质的最小 集合。“最小”：任何包含同样对象，具有同样性质的集 合，都包含这个闭包集合。,c,a,b,d,定理4.4 设R是非空集合A上的关系，则有(1)r(R)=R R0(2)s(R)=R R-1(3)t(R)=R R2 R3 此定理提供了一种集合表示形式下关系闭包的求解方法,4.4 关系的闭包,例4.34 设 A=a,b,c,d,R=,则r(R)=R R0=,s(R)=R R-1=,=,t(R)=R R2 R3(甚不方便),当关系用关系矩阵表示时，相应闭包求法为：(1)Mr=M+E(2)Ms=M+M(3)Mt=M+M2+M3+其中M为R的关系矩阵，E是单位矩阵，M 是M的转置矩阵.,4.4 关系的闭包,0 1 0 0 1 0 0 0 1 1 0 0Mr=M+E=1 0 1 0+0 1 0 0=1 1 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 1 0 1 0 1,0 1 0 0 0 1 0 0 0 1 0 0Ms=M+M=1 0 1 0+1 0 0 1=1 0 1 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 1 0,1 1 1 1Mt=M+M2+M3+=1 1 1 1 1 1 1 1 1 1 1 1,例4.35 设A=a,b,c,d,R=,则,4.4 关系的闭包,E表示同阶单位阵；M表示M的转置矩阵,a b c d,abcd,当关系用关系图表示时，相应闭包求法为:设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中的顶点数).设路径的终点为xj1,xj2,xjk，如果没有从xi到xjl(i=1,2,k)的边，就加上这条边，最终得到Gt。例题参见P93例4.10,4.5 等价关系和偏序关系,定义4.12 设R是非空集合A上的关系。若R是自反的、对称的和传递的,则称R是A上的等价关系 如果R是一个等价关系，若 R,称x等价于y,记作xy。等价关系=自反性+对称性+传递性也就是说,若R,或aRb,称a等价b,记ab 由于R是对称的，a等价b即b等价a，反之亦然，a与b彼此等价。,.,例4.36 设有一个整数集 Z 上的关系R：R=|x-y 可被3整除 求证这个关系是等价关系。证：对每个xZ,x-x可被3整除，所以是自反的。对于x,yZ,如果x-y能被3整除，则y-x也能被3 整除所以是对称的。对于x,yZ,如果有x-y，y-c均能被3整除，则 x-c=(x-y)+(y-c)亦能被3整除，所以是传递的。将这个例子推广到一般，比如：例4.30 设A=1,2,3,4,5,6,7,8,R为A上的关系 R=|x,y A x=y(mod 3)其中，x=y(mod 3)的含义就是x-y可以被3整除。这个关系亦是等价关系,例4.37 设集合Aa,b,R是P(A)上的包含关系,写出R的表达式和关系矩阵.解 用描述法表示；用列举法表示：因为 所以,关系矩阵,关系图,a,b,A,例4.38 设A1,2,3,用列举法给出A上的恒等关系IA,全域关系EA,A上的小于关系及其逆关系和关系矩阵,关系矩阵,a,A,LA的逆关系,有,例4.39 设集合A2,3,4,B=4,6,7,C=8,9,12,14.R1是由A到B的二元关系,R2是由B到C的二元关系,定义如下:,a,A,解:,求复合关系 R2 R1 和 R1 R2 并用关系矩阵表示,因此R2 R1,R1 R2=？,布尔运算,例4.40 试判断下图中关系的性质：,a,A,1,2,3,1,2,3,1,2,3,(a),(b),(c),解 图(a)中的关系在集合1,2,3上是对称的,因为 结点1与2,1与3之间的有向弧是成对出现且方向相反.图(b)中是反自反的,因为每个结点都没有自回路 它也是反对称的,因为两条边都是单向边.因此具备传 递的潜能，如边2到3或3到2均可构成传递关系.,图(c)中的关系自反的，反对称的、但不是传递 的因为2到1有边，1到3有边，但2到3没有边.,例4.41 设集合Aa,b,c,d,定义R,求 r(R),s(R),t(R).解 求自反闭包，R不具有自反性，由自反性的定义，只需在R上添加IA，(其中下画线者为添加元素)于是r(R)=RIA=,s(R)=RR-1=R,=,t(R)=RR2R3R4=R,=,=,A,R,R,R2R R=,例 对以下整数集上的关系R和S 确定R S和S R R=|y=2X-1 S=|y=X+3 R S=|y=2(X+3)-1 S R=|y=2X-1+3 R=|y=2X S=|y=x2 S R=|y=(2x)2 R S=|y=2x,2,定义4.13 设R是非空集合A上的等价关系,对任一个 xA,可以构造一个A的子集xR xR=y|y A x R y称xR为x关于R的等价类,简称为x的等价类,简记为x例4.42 设A=1,2,3,4,5,6,7,8,R为A上的关系 R=|x,y A x=y(mod 3)其中,x=y(mod 3)的含义就是x-y可以被3整除等价类为：1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,6,4.5 等价关系和偏序关系,定理4.5 设R是非空集合A上的等价关系,对任意的x,yA,下面的结论成立(1)x，且xA。(2)若x R y，则x=y。(3)若x R y,则x与y不交,即x y=(4)x|xA=A。,4.5 等价关系和偏序关系,设A是非空集合，若B=A1,A2,An，且 Ai，AiAj=，ij，=A，则称B是A的划分。称B中元素为A的划分块。,4.5 等价关系和偏序关系,定义4.14 集合A上的等价关系R所构成的类产生一个集合A的划分,此划分叫A关于R的商集,记作A/R,即 A/R=xR|x A 此定义告诉我们，商集A/R是以R的所有等价类为元素的集合。例4.43 中的商集为：A/R=1,4,7，2，5，8，3,6,4.5 等价关系和偏序关系,例4.44 中的商集为：A/R=1,4,7，2，5，8，3,6例4.45 设A=a,b,c,d,给定A 如下：A1=a,b,c,d,A2=a,b,c,d,A3=a,b,c,a,d,A4=,a,b,c,d,A5=a,b,c 问：哪些是A的划分？P97,例4.46 设A是浙江中医药大学信息技术学院2008级的所有学生组成的集合，用 a,b,c,d,e分别表示一班、二班、三班、四班和五班，用Ai表示按照班级划分的不同方案，试确定下列哪些是A的一个划分。设A=a,b,c,d,e,给定A 如下：A1=a,b,c,d,e,A2=a,b,c,d,e,A3=a,b,c,a,d,e,A4=,a,b,c,d,e A5=a,b,c,d,e A6=a,b c,d,e A7=a,b,c c,d,e A8=a,b,c,d,e,4.5 等价关系和偏序关系,定义4.16 设R是非空集合A上的关系。若R是自反的、反对称的和传递的，则称R是A上的偏序关系，记作。若,则记作x y,读作“x小于等于y”.这里的小于等于不是指数的大小，而是指它们在偏序中位置的先后。(意即:依据这个序,x排在y的前面)等价关系和偏序关系是具有不同性质的两个关系,4.5 等价关系和偏序关系,例如,集合A=1,2,3,偏序是A上的大于等于关系,则=,那么有3 2,2 2,3 1。它们分别表示,和属于偏序，因为是1,2,3上的大于等于关系,在 前边的数恰好是比较大的数。,4.5 等价关系和偏序关系,例4.47 集合A=2,3,6,8上的“整除”关系R(x整除y）,R=,那么R有哪些关系？解：,R R是自反的 又,R 而,R R是反对称的由R 有 y|x=n 由 R 有 z|y=m 将 y=z|m 代入 y|x=n 得 z|x=m n 即 R(z|x=m n)R是可传递的.(事实上,R 则,R R是可传递的）综上所述：R是偏序关系,例4.28 集合A18的正整数因子,为整除关系(x整除y）证明：是偏序关系.分析 偏序关系只需验证自反性、反对称性和传递性.,解:集合A1,2,3,6,9,18，整除关系为 IA,容易验证 IA，故有自反性；(a,b),ab,则(b,a)，故有反对称性 x y zA,若 且 则 整除关系且是正整数因子 x,y,zA 有 y|x=n 由 有z|y=m y=z|m并将其代入上式 z|x=m n 所以 具有传递性.是偏序关系.,定义4.17 一个集合A与A上的偏序关系R一起叫做偏序集，记作。如：集合A=2,3,6,8上的“整除”关系 整数集合上的小于等于关系 R=|x,y Z x y x Z R R是自反的又 R 而 R(表示yx与关系R矛盾）R是反对称的 又 x,y,t Z,若 R 且 R 则 R R是可传递的 R是偏序关系,定义4.18