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

刘师少,Tel：86613747（h）E-mail：lss,授课:51学时,教学目标:知识、能力、素质,DiscreteMathematics,第四章二元关系和函数,4.1集合的笛卡尔积与二元关系4.2关系的运算4.3关系的性质4.4关系的闭包4.5等价关系和偏序关系4.4函数的定义和性质4.4函数的复合和反函数4.4例题分析,说起关系这个词，对我们并不陌生，世界上存在着各种各样的关系，人与人之间的“同志”关系；“同学”关系；“朋友”关系；“师生”关系；“上下级”关系；“父子”关系；两个数之间有“大于”关系；“等于”关系和“小于”关系；两个变量之间有一定的“函数”关系；计算机内两电路间有导线“连接”关系；程序间有“调用”关系等等。所以对关系进行深刻的研究，对数学与计算机科学都有很大的用处。,再如:电影票与座位之间有对号关系。设：X表示电影票的集合Y表示座位的集合，则，对于任意的xX和yY，必有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,fB=1,2,3则例中关系的每一元素均属于AB亦即R是AB的子集，并称此关系为从A到B的关系R。,4.1集合的笛卡尔积与二元关系,定义4.1由两个元素x,y（允许x=y）按一定顺序排列成的二元组叫做一个有序对或序偶，记作,其中x是它的第一元素，y是它的第二元素。有序对具有以下性质：(1)当xy时，(2)=x=wy=v例4.1：已知=，求x和y。解：由有序对相等的充要条件得x+3=y+7y-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。笛卡儿积的符号化表示为：AB=|xAyB例如：若A=1,2,B=a,b,c,则AB=,BA=,易知：若|A|=m,(即集合A的元素的个数),|B|=n,则|AB|=|BA|=mn,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（当ABB、A时）3、笛卡儿积不满足结合律，即(AB)CA(BC)（当ABC时）4、笛卡儿积运算对并和交运算满足分配律，即A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA),4.1集合的笛卡尔积与二元关系,例4.2证明：(BC)A=(BA)(CA)对于(BC)Ax(BC)yAxBxCyAxBxCyAyA(xByA)(xCyA)BACA(BA)(CA)(BC)A=(BA)(CA),4.1集合的笛卡尔积与二元关系,例4.3：设A，C，B，D为任意集合，判断以下命题是否为真，并说明理由。(1)AB=AC=B=C(2)A-(BC)=(A-B)(A-C)(3)存在集合A,使得AAA.,解：(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,7aR1b,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，则AB=,令R1=,R2=,R3=因为R1AB，R2AB，R3AB，所以R1，R2和R5均是由A到B的二元关系因为只讨论二元关系，所以今后无特别声明，术语“关系”皆指二元关系？,又例：若A=a,b，B=2,5,8，则BA=,令R4=,R5=,因为R4BA，R5BA，所以R4和R5均是由B到A的关系又BB=,令R6=,R7=,因为R6BB，R7BB，所以R6和R7均是集合B上的关系。,若集合|A|=n,则集合A上的二元关系有多少个？答曰：|A|=n，则|AA|=n2,AA的任一个子集就是A上的二元关系，即P(A)=2n个。,例4.8A=1,2则AA有n2个不同的二元关系AA=1,21,2=,AA的任一个子集就是AA的幂集，即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=ab,b=bc,c=c）,三类特殊的关系对于任何集合A，空集是AA的子集，叫做A上的空关系定义EA=|xAyA=AA为全域关系定义IA=|xA为恒等关系例：若A=1,2，则EA=,IA=,除上述三类特殊的关系外，还有一些常用的关系，如：LA=|x,yAxy(AR)为实数集上的小于等于关系。DA=|x,yAx整除y(AZ*)为非正整数集上的整除关系。R=|x,yAxy(A是集合族)为集合上的包含关系。类似地还可以定义大于等于关系、大于关系、小于关系、真包含关系等。,4.1集合的笛卡尔积与二元关系,例4.9：设A=1,2,3,4，请表示下列关系。(1)R=|x是y的倍数(2)R=|(x-y)2A(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若xiRyjrij=(i=1,2,nj=1,2,m)0若xiRyj则称矩阵M(R)=(rij)nm为R的关系矩阵。,有穷集合上的二元关系的三种表示方法：集合表示法（前已使用）关系矩阵法关系图关系矩阵是表示关系的另一种有效的方法，其优点是可以利用矩阵作为研究关系的手段，而且这样做便于计算机进行处理。设R：AB，A和B都是有限集，且,设A，B为集合，AB的任何子集RiAB则称Ri所定义的二元关系叫做从A到B的二元关系，特别当A=B时则叫做A上的二元关系,则r11r12r1n(rij)=r21r22r2nrn1rn2rnn是R的关系矩阵，记作MR。,关系矩阵法若A=x1,x2,xn,B=y1,y2,yn则R的关系矩阵是一个n行n列矩阵M(R)=(rij)nn,其中元素rij为：1若xiRyjrij=(i,j=1,2,n)0若xiRyj,0111MR=001100010000,例4.10A=1,2,3,4R为A上的小于关系，则R为：R=,R的关系矩阵为：,1234,1234,例4.11设集合A2,3,4,B=8,9,12,14.R是由A到B的二元关系，定义：R=|a整除b写出R的表达式和关系矩阵.解R=,89121421011R的关系矩阵为.MR=3011041010,关系图关系图是表示关系的一种直观形象的方法，设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,y3R=,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,dR=,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=domRranR,4.2关系的运算,例4.14下列关系都是整数集Z上的关系，分别求出它们的定义域和值域R1=|x,yZxy(2)R2=|x,yZx2+y2=1(3)R3=|x,yZy=2xR4=|x,yZ|x|=|y|=3解(1)domR1=ramR1=ZR2=,domR2=0,1,-1ramR2=0,1,-1(3)domR3=ZramR3=2z|zZ即偶数集(4)domR4=-3,3ramR4=-3,3,1,0,-1,-1,0,1,domR2,ramR2,R2,210-1-2,43210-1-2-3-4,domR3=Z,ramR3,R3,例4.15设R1=,R2=,求其定义域和值域解题目没有告诉我们R1和R2是由什么集合到什么的关系,这对于我们解此题是无关紧要的,事实上,不论R1和R2是定义在何种集合上的关系,据定义域和值域的定义domR=x|y(R)ranR=y|x(R)有domR1=1,2,3domR2=1,2,4ramR1=2,4,3ramR2=3,4,2,规律:集合R1和R2中序偶中的第一个元素的集合即为其定义域,序偶中的第二个元素的集合即为其值域.,如果此题再加上求R1R2及R1R2定义域和值域,则因为R1R2=,R1R2=所以domR1domR2=1,2,3,4ramR1ramR2=2,3,4,定义4.9设F,G为任意的关系,A为集合，则(1)F的逆记作F-1,F-1=|yFx(2)F与G的合成记作FG，其中FG=|z(xGzzFy或FG=|z(xFzzGyp87(3)F在A上限制记作FAFA=|xFyxA)(4)A在F下的象记作FAFA=ran(FA),4.2关系的运算,逆关系：设R是一个X到Y的关系，则Y到X的关系R-1：R-1=|R称为R的逆关系。例4.16设X=1,2,3Y=a,b,c且设R是从X到Y的关系R=,则R-1=,例4.17设X=x1,x2,x3Y=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的合成关系(或复合关系):RS为：RS=|z(xSzzRy例4.18设X=x1,x2,x3,Y=y1,y2,y3,Z=z1,z2,z3从X到Z的关系S=,从Z到Y的关系R=,则X到Y的关系RS=,XZYXY,R,S,RS,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|=1G=|b-c|=2或|b-c|=4求合成关系GF和FG解先求GF,由题意知F=,G=,GF=,例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|=1G=|b-c|=2或|b-c|=4求合成关系GF和FG解再求FG,由题意知G=,F=,FG=,例4.20:设A=2,3,G=,R=,则R-1,RG，GR，RA,R,RA,R分别是R-1=,RG=,GR=,RA=|xRyxA=R=RA=ran(RA)=2R=注意：逆运算的优先级高于其他运算，而所有的关系运算都优于集合运算。,例4.21：设F=,求FF，Fa，Fa解因为F=,F=,所以FF=由公式FA=|xFyxA)有Fa=由公式FA=ran(FA)有Fa=ran(Fa)=ran=a,定义域,值域,综上所述,两个关系的合成,如F与G的合成记作FG，其中FG=|z(xGzzFy称为关系的合成运算。它是对关系的一种二元运算，通过这种运算，可由两个已知关系产生一个新的关系。,例4.22设A=1,2,3,4，B=2,3,4，C=1,2,3，且R1=|aAbB(a+b)=5，R2=|bBcC(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)(FG)H=F(GH)(4)(FG)-1=G-1F-1证明:(1)任取,由逆的定义有(F-1)-1F-1F(F-1)-1=F(2)任取x,xranF-1y(F-1)y(F)xdomFranF-1=domF同理可证dom(F-1)=ranF,定理4.2设F、G、H是任意关系,则(1)F(GH)=FGFH(2)(GH)F=GFHF(3)F(GH)FGFH(4)(GH)FGFHF本定理对有限个关系的并和交都成立。R(R1R2Rn)=RR1RR2RRn(R1R2Rn)R=R1RR2RRnRR(R1R2Rn)RR1RR2RRn(R1R2Rn)RR1RR2RRnR,定义4.10设R是A上的关系,n为自然数，则R的n次幂规定如下(1)R0=|xA(2)Rn=Rn-1Rn1由定义可以知道R0就是A上的恒等关系IA，不难证明下面的等式RR0=R=R0R由这个等式立即可以得到R1=R0R=R例4.24设A=a,b,c,d,R=,求R0，R1，R2，R3，R4和R5,解R0=,R1=R0R=,=,R2=RR=,=,R3=R2R=,=,R4=R3R=,=,R5=R4R=,=,例4.25设A=1，2，3，4，A上的关系R=|aAbA(ab)=1，求：R2，R3，R4解：因为R=，所以R2=，R3=，R4=。,定理4.3设R是A上的关系,m,n为自然数，则下面的等式成立(1)RmRn=Rm+n(2)(Rm)n=Rmn证明：(1)任给m，对n作归纳法。n=0时，RmR0=Rm=Rm+0。假设RmRn=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)nRm=RmnRm=Rmn+m=Rm(n+1),011001101110M2=MM=10001000=0110011001101110000000000000,111001101110M3=M2M=01101000=1110111001101110000000000000,例4.25：设A=1,2,3,4,R是A上二元关系，关系矩阵为,0110M=100001100000,解：R，R2,R3的关系矩阵分别为：,求R3。(M为R的关系矩阵),设R是A上的关系，R的性质主要有以下5种(1)若x(xAR),则称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(xAR),则称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)若xy(x,yARR),则称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)若xy(x,yARxyR),则称R在A上是反对称的。(隐含x=yR)也就是说,对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是偶数用列举法表示RR是否自反、对称、反对称？解: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是偶数用列举法表示RR是否是可传递的？解:R=,对于任意的a,b,cA若a-b=2m,b-c=2n,则a-c=(a-b)+(b-c)=2(m+n)也是偶数。因此A是可传递的。RRR,例4.31设A=1,2,3,4,5,6,7,8,9,10R是A上的关系，R=|x,yAx+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上的一个新的调用关系显然有RRRR选用满足这个条件的最小者R,这个新关系叫做R上的传递闭包，它是在集合P上的一个新的调用关系。对于关系的自反性、对称性、传递性均可建立闭包,定义4.11设R是非空集合A上的关系，R的自反(对称或传递)闭包是A上的关系R,使得R满足以下条件:(1)R是自反(对称或传递)的(2)RR(3)对A上的任何包含R的自反(对称或传递)关系R有RR一般将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)=RR0(2)s(R)=RR-1(3)t(R)=RR2R3此定理提供了一种集合表示形式下关系闭包的求解方法,4.4关系的闭包,例4.34设A=a,b,c,d,R=,则r(R)=RR0=,s(R)=RR-1=,=,t(R)=RR2R3(甚不方便),当关系用关系矩阵表示时，相应闭包求法为：(1)Mr=M+E(2)Ms=M+M(3)Mt=M+M2+M3+其中M为R的关系矩阵，E是单位矩阵，M是M的转置矩阵.,4.4关系的闭包,010010001100Mr=M+E=1010+0100=1110000100100011010000010101,010001000100Ms=M+M=1010+1001=1011000101000101010000100110,1111Mt=M+M2+M3+=111111111111,例4.35设A=a,b,c,d,R=,则,4.4关系的闭包,E表示同阶单位阵；M表示M的转置矩阵,abcd,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,yAx=y(mod3)其中，x=y(mod3)的含义就是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,解:,求复合关系R2R1和R1R2并用关系矩阵表示,因此R2R1,R1R2=？,布尔运算,例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,R2RR=,例对以下整数集上的关系R和S确定RS和SRR=|y=2X-1S=|y=X+3RS=|y=2(X+3)-1SR=|y=2X-1+3R=|y=2XS=|y=x2SR=|y=(2x)2RS=|y=2x,2,定义4.13设R是非空集合A上的等价关系,对任一个xA,可以构造一个A的子集xRxR=y|yAxRy称xR为x关于R的等价类,简称为x的等价类,简记为x例4.42设A=1,2,3,4,5,6,7,8,R为A上的关系R=|x,yAx=y(mod3)其中,x=y(mod3)的含义就是x-y可以被3整除等价类为：1=4=7=1,4,72=5=8=2,5,83=6=3,6,4.5等价关系和偏序关系,定理4.5设R是非空集合A上的等价关系,对任意的x,yA,下面的结论成立(1)x，且xA。(2)若xRy，则x=y。(3)若xRy,则x与y不交,即xy=(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|xA此定义告诉我们，商集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,eA5=a,b,c,d,eA6=a,bc,d,eA7=a,b,cc,d,eA8=a,b,c,d,e,4.5等价关系和偏序关系,定义4.16设R是非空集合A上的关系。若R是自反的、反对称的和传递的，则称R是A上的偏序关系，记作。若,则记作xy,读作“x小于等于y”.这里的小于等于不是指数的大小，而是指它们在偏序中位置的先后。(意即:依据这个序,x排在y的前面)等价关系和偏序关系是具有不同性质的两个关系,4.5等价关系和偏序关系,例如,集合A=1,2,3,偏序是A上的大于等于关系,则=,那么有32,22,31。它们分别表示,和属于偏序，因为是1,2,3上的大于等于关系,在前边的数恰好是比较大的数。,4.5等价关系和偏序关系,例4.47集合A=2,3,6,8上的“整除”关系R(x整除y）,R=,那么R有哪些关系？解：,RR是自反的又,R而,RR是反对称的由R有y|x=n由R有z|y=m将y=z|m代入y|x=n得z|x=mn即R(z|x=mn)R是可传递的.(事实上,R则,RR是可传递的）综上所述：R是偏序关系,例4.28集合A18的正整数因子,为整除关系(x整除y）证明：是偏序关系.分析偏序关系只需验证自反性、反对称性和传递性.,解:集合A1,2,3,6,9,18，整除关系为IA,容易验证IA，故有自反性；(a,b),ab,则(b,a)，故有反对称性xyzA,若且则整除关系且是正整数因子x,y,zA有y|x=n由有z|y=my=z|m并将其代入上式z|x=mn所以具有传递性.是偏序关系.,定义4.17一个集合A与A上的偏序关系R一起叫做偏序集，记作。如：集合A=2,3,6,8上的“整除”关系整数集合上的小于等于关系R=|x,yZxyxZRR是自反的又R而R(表示yx与关系R矛盾）R是反对称的又x,y,tZ,若R且R则RR是可传递的R是偏序关系,定义4.18设R是非空集合A上的偏序关系,对任意的x,yA,如果偏序xy或者yx成立,则称x与y是可比的,如果x是偏序集。那么对xA都有1x,所以1和1,2,3,4,5都是可比的,但是2不能整除3,3也不能整除2,所以2和3是不可比的,对于1和2来说,12,并且不存在zA使得1整除z并且z整除2,所以2盖住1,同样,4盖住2,但4盖不住1,因为124成立。显然,如果x与y不可比,则一定不会有x盖住y或y盖住x。,定义4.19设为偏序集,若对任意的x,yA,x和y都可比,(即xy或yx)则称R为A上的全序关系,且称为全序集。例如，A=1,2,3,4,5上的小于等于关系是全序关系,因为由前例知集合A上的小于等于关系是偏序关系,所以为偏序集。又因为对任意的x,yA,x,y均可比较大小,即xy或yx所以是全序关系。而整除关系亦为偏序集，但对任意的x,yA,x,y相互不能整除,所以不是全序关系。,对于集合A上的任一全序,集合A中任意两个元素都是可比的,关于盖住概念的补充说明设为偏序集。a,bA，若ab且不存在cA，使得acb，则称b盖住a。例如在A=1，2，4,6上的整除关系中，有哪些盖住关系呢？2盖住14盖住26盖住24不盖住16不盖住1Why?,因为有124126,偏序关系关系图的简化哈斯图(Hassediagram)哈斯图的画法：在画偏序集的哈斯图时，首先适当排列A中元素的顺序。对于x,yA，若xy，则将x画在y的下方。其次考虑y是否盖住了x，若y盖住x，则用一条线段连接y和x。,也就是说分以下两步:(其中表示偏序关系)若xy，且xy，则将x画在y的下面。若xy，xy，并且没有不同于x，y的z使得xzy，则在x，y之间用直线连结。,例4.49A=1,2,3,4,6上的整除关系为R,画出的哈斯图,1,2,3,4,6,在画偏序集的哈斯图时，首先适当排列顶点的顺序使得：x,yA，若xy，则将x画在y的下方。对于A中的两个不同元素x和y,如果y盖住x,就用一条线段连接x和y。,例4.50设Aa,b,a,b,a,b,c,a,b,c,d,a,b,c,e，画出的哈斯图。,例4.51A=1,2,画出A的幂集P(A)上的包含关系的哈斯图P(A)=,1,2,1,2,例4.52A=2,3,6,12,24,36,画出“整除”R的偏序集的哈斯图。,解：A=,1,2,3,1,2,2,3R=,IA,1,22,3123,例4.53已知偏序集的哈斯图如下所示,写出集合A和关系R的表达式。,定义4.20设为偏序集，BA，bB，若(x)(xBbx)为真,则称b为B的最小元。若(x)(xBxb)为真，则称b为B的最大元。若(x)(bxxb)为真，则称b为B的极小元。若(x)(bxbx)为真，则称b为B的极大元。,从本定义可知，最小元与极小元是有区别的，最小元是B中最小的元素，它与B中其他元素都可比；而极小元不一定与B中元素都可比，只要没有比它小的元素，它就是极小元。对于有穷集B，极小元一定存在，且可能有多个，