第七章二元关系精选PPT.ppt

《第七章二元关系精选PPT.ppt》由会员分享，可在线阅读，更多相关《第七章二元关系精选PPT.ppt（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章二元关系第七章二元关系第1页，本讲稿共61页第七章第七章 二元关系二元关系有序对与笛卡儿积有序对与笛卡儿积二元关系二元关系关系的运算关系的运算关系的性质关系的性质关系的闭包关系的闭包等价关系与划分等价关系与划分偏序关系偏序关系知知 识识 点：序偶与笛卡尔积、关系及表示、关系的性质、复合关系和逆关系、点：序偶与笛卡尔积、关系及表示、关系的性质、复合关系和逆关系、关系的闭包运算、集合的划分、等价关系与等价类、偏序关系关系的闭包运算、集合的划分、等价关系与等价类、偏序关系 教学要求：深刻理解和掌握关系的基本概念和基本运算教学要求：深刻理解和掌握关系的基本概念和基本运算 教学重点：关系及关系的运

2、算、等价关系、偏序关系教学重点：关系及关系的运算、等价关系、偏序关系 学时学时:12第2页，本讲稿共61页7.1 有序有序对与笛卡儿与笛卡儿积定定义7.1:由两个元素由两个元素x和和y(允允许x=y)按一定按一定顺序排列成的二元序排列成的二元组叫做一个叫做一个有序有序对或序偶，或序偶，记作作,其中其中x是它的第一元素，是它的第一元素，y是它的第二元素。有序是它的第二元素。有序对具有以下性具有以下性质:n当当xy时，n=的充分必要条件是的充分必要条件是x=u且且y=v例例7.1 已知已知=，求，求x和和y。解解 由有序由有序对相等的充要条件有相等的充要条件有 x+2=5,2x+y=4 解得解得x

3、=3,y=-2第3页，本讲稿共61页7.1 有序有序对与笛卡儿与笛卡儿积定定义7.2 设A，B为集合集合,用用A中元素中元素为第一元素，第一元素，B中元素中元素为第二元素构成有序第二元素构成有序对。所有所有这样的有序的有序对组成的集合叫做成的集合叫做A和和B的笛卡儿的笛卡儿积。nA和和B的笛卡儿的笛卡儿积记作作ABn笛卡儿笛卡儿积的符号化表示的符号化表示为AB=|x A y Bn由排列由排列组合的知合的知识不不难证明明,如果如果|A|=m,|B|=n,则|AB|=mn例例7.2 设A=a,b,B=0,1,2，则AB=,BA=,例例7.3 设设 A=x|0 x2 ,B=y|0y1,则则 A B=

4、|0 x2且且0y1 O12A Bxy第4页，本讲稿共61页7.1 有序有序对与笛卡儿与笛卡儿积笛卡儿积运算具有以下性质笛卡儿积运算具有以下性质nA =,A=n一般地说一般地说,笛卡儿积运算不满足交换律笛卡儿积运算不满足交换律,即即 A B BA (当当 A B AB 时时)n笛卡儿积运算不满足结合律笛卡儿积运算不满足结合律,即即 (AB)C A(BC)(当当 ABC 时时)n笛卡儿积运算对并和交运算满足分配律笛卡儿积运算对并和交运算满足分配律 A(B C)=(AB)(AC)(B C)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA)nA C B D A B C D第

5、5页，本讲稿共61页7.1 有序有序对与笛卡儿与笛卡儿积例例7.4 设设A=1,2,求求 P(A)A 解解:P(A)A =,1,2,1,2 1,2 =,例例7.5 设设A,B,C,D为任意集合为任意集合,判断以下命题是否为真判断以下命题是否为真,并说明理由并说明理由nA B=A C B=CnA (B C)=(A B)(A C)nA=B C=D A C=B Dn存在集合存在集合A,使得使得 A A A第6页，本讲稿共61页7.2 二元关系二元关系A=a,b,c表示一个班级表示一个班级,B=1,2,3,4表示开设的课程表示开设的课程 a选修课程选修课程1,3 b选修课程选修课程1,3,4 c选修课

6、程选修课程2,4 如何用集合表示学生和课程的关系如何用集合表示学生和课程的关系?R=,S=,R中的元素表示某个学生选修了某门课中的元素表示某个学生选修了某门课 S中的元素表示某门课被某个学生所选修中的元素表示某门课被某个学生所选修R A B,S B A 两个集合的笛卡尔集的子集两个集合的笛卡尔集的子集可以表示这两个集合中元素之间的某种关系可以表示这两个集合中元素之间的某种关系第7页，本讲稿共61页7.2 二元关系二元关系定定义7.3 如果一个集合如果一个集合满足以下条件之一：足以下条件之一：(1)集合非空，且它的元素都是有序集合非空，且它的元素都是有序对(2)集合是空集集合是空集则称称该集合集

7、合为一个二元关系，一个二元关系，记作作 R。n二元关系也可二元关系也可简称称为关系关系n对于二元关系于二元关系R,如果如果 R,可可记作作 x R yn如果如果 R，则记作作 x yn例如例如:R1=,，R2=,a,b 则R1是二元关系是二元关系;R2不是二元关系不是二元关系,只是一个集合，除非将只是一个集合，除非将a和和b定定义为有序有序对。根据上面的根据上面的记法可以写法可以写 1 R12，a R1b，a R1c 等。等。第8页，本讲稿共61页7.2 二元关系二元关系定定义7.4 设A,B为集合集合,AB的任何子集所定的任何子集所定义的二元关系叫做从的二元关系叫做从A到到B的二元的二元关系

8、关系,特特别当当A=B时则叫做叫做A上的二元关系。上的二元关系。n例如例如:A=0,1，B=1,2,3，那么，那么R1=，R2=AB，R3=，R4=等都是从等都是从A到到B的二元关系，而的二元关系，而 R3和和R4 同同时也是也是A上的二元关系。上的二元关系。集合集合A上的二元关系的数目依上的二元关系的数目依赖于于A中的元素数中的元素数n如果如果|A|=n,那么那么|AA|=n2 ,AA的子集就有的子集就有 个个 2n2。每一个子集代表一个。每一个子集代表一个A上的二上的二元关系，所以元关系，所以A上有上有 2n2 个不同的二元关系。个不同的二元关系。n例如例如|A|=3，则 A上有上有=51

9、2个不同的二元关系个不同的二元关系对任何集合任何集合A,空集空集是是 AA的子集的子集,叫做叫做A上的空关系上的空关系第9页，本讲稿共61页7.2 二元关系二元关系定义定义7.5 对任意集合对任意集合A,定义定义nEA=|x A y A =AAnIA=|x A n例例:设A=1,2,则 EA=,IA=,n例例:设B=a,b,A=P(B)=,a,b,a,b R=,a,a,称为集合称为集合A上的包含关系上的包含关系第10页，本讲稿共61页7.2 二元关系二元关系关系的表示方法关系的表示方法:集合表达式、关系矩阵、关系图集合表达式、关系矩阵、关系图例例7.4 设A=1,2,3,4,下面各式定下面各式

10、定义的的R都是都是A上的关系上的关系,试用列元素法表示用列元素法表示R。(1)R=|x是是y的倍数的倍数 (2)R=|(x-y)2 A(3)R=|x/y是素数是素数 (4)R=|xy解解(1)R=,(2)R=,(3)R=,(4)R=EA-IA =,第11页，本讲稿共61页7.2 二元关系二元关系用关系矩用关系矩阵表示二元关系表示二元关系(对于有于有穷集集)设A=x1,x2,xn,R是是A上的关系。令上的关系。令 则 是是R的关系矩的关系矩阵，记作作MR第12页，本讲稿共61页7.2 二元关系二元关系w例如例如:设设A=1,2,3,4,R=,则关系图则关系图MR如下所示如下所示第13页，本讲稿共

11、61页7.2 二元关系二元关系用关系用关系图表示二元关系表示二元关系(对于有于有穷集集)设A=x1,x2,xn,R是是A上的关系上的关系,令令图G=,其中其中顶点集合点集合V=A,边集集为E。xi,xj V,满足满足 E xi R xj 称图称图G是是R的关系图的关系图,记作记作 GR例如例如:设设A=1,2,3,4 R=,则关系图则关系图GR如下图所示如下图所示1234第14页，本讲稿共61页7.3 关系的运算关系的运算关系的基本运算有七种关系的基本运算有七种,分别定义如下分别定义如下:定定义7.6 设R是二元关系。是二元关系。(1)R中所有的有序中所有的有序对的第一元素构成的集合的第一元素

12、构成的集合 称称为R的定的定义域，域，记为domR 形式化表示形式化表示为：domR=x|y(R)(2)R中所有有序中所有有序对的第二元素构成的集合的第二元素构成的集合 称称为R的的值域，域，记作作ranR 形式化表示形式化表示为:ranR=y|x(R)(3)R的定的定义域和域和值域的并集称域的并集称为R的域，的域，记作作fld R 形式化表示形式化表示为:fldR=domR ranR例例7.5 设R=,，则 dom R=1,2,4 ran R=2,3,4 fld R=1,2,3,4第15页，本讲稿共61页7.3 关系的运算关系的运算定定义7.7 设R为二元关系，二元关系，R的逆关系，的逆关系

13、，简称称R的逆，的逆，记作作R-1 形式化表示形式化表示为 R-1=|R定义定义7.8 设设F,G为二元关系为二元关系,G对对F的右复合记作的右复合记作 F G 形式化表示为形式化表示为 F G=|t(F G)例例7.6 设设F=,G=,则则nF-1=,nF G=G F=xtyFG(A)(B C)(D)例例:设设F AB,G CD,则则 F G AD,F G的生成如下图所示的生成如下图所示第16页，本讲稿共61页7.3 关系的运算关系的运算定义定义7.9 设设R为二元关系为二元关系,A是集合是集合nR在在A上的限制记作上的限制记作 R A,其中其中 R A=|xRy x A nA在在R下的像记

14、作下的像记作 RA,其中其中RA=ran(R A)nR A是是R的子关系的子关系,RA是是ran R的子集的子集例例7.7 设设R=,则则nR 1=,nR =nR 2,3=,nR1=2,3nR=nR3=2第17页，本讲稿共61页7.3 关系的运算关系的运算关系是集合关系是集合,因此关系也具有集合的并、交、差、补、对称差运算因此关系也具有集合的并、交、差、补、对称差运算设设 R,S是是 A 到到 B的的 两个二元关系则两个二元关系则 (R AB,S AB)nR,S的并的并 R S=|xRy xSy nR,S的交的交 RS=|xRy xSy nR,S的差的差 R-S =|xRy x$y nR,S的

15、对称差的对称差 R S=(R S)(RS)nR的补的补 R=(AB)R=|x A y B x y 第18页，本讲稿共61页7.3 关系的运算关系的运算逻辑加逻辑加“”0 0 0=0,00=0,0 1 1=1,1=1,1 0=1,10=1,1 1 1=1=1 逻辑乘逻辑乘“”0 0 0=0,00=0,0 1=0,11=0,1 0 0=0,1=0,1 1=11=1第19页，本讲稿共61页7.3 关系的运算关系的运算应用关系矩阵求关系的并交差补逆应用关系矩阵求关系的并交差补逆例例 设设A=1,2,3,4,B=x,y,z R=,S=,是是 A 到到 B 的两个二元关系的两个二元关系第20页，本讲稿共6

16、1页7.3 关系的运算关系的运算应用关系矩阵求复合关系应用关系矩阵求复合关系设设 A=a,b,c,d B=r,s,t C=x,y,z,R=,S=,rstxyzabcd第21页，本讲稿共61页7.3 关系的运算关系的运算设设A=x1,x2,xm,B=y1,y2,yn,C=z1,z2,zp R,S分别为分别为 A到到B 和和 B到到C 的二元关系的二元关系 它们的关系矩阵分别为它们的关系矩阵分别为 MR=(rij)mn ,MS=(sjk)np 则复合关系则复合关系RS的关系矩阵的关系矩阵 MRS=MR*MS=(tik)mp 其中其中 tik=(ri1 s1k)(ri2 s2k)(rin snk)第

17、22页，本讲稿共61页7.3 关系的运算关系的运算关系运算的性质关系运算的性质定理定理7.1 设F是任意的关系，是任意的关系，则(1)(F-1)-1=F (2)domF-1=ranF，ranF-1=domF 证(1)任取任取，由逆的定，由逆的定义有有(F-1)-1 F-1 F 所以有所以有(F-1)-1=F。(2)任取任取x x domF-1 y(F-1)y(F)x ranF 所以有所以有domF-1=ranF 同理可同理可证 ranF-1=domF第23页，本讲稿共61页7.3 关系的运算关系的运算定理定理7.2 设F,G,H是任意的关系，是任意的关系，则(1)(F G)H=F (G H)(

18、2)(F G)-1=F-1 G-1证 (1)任取任取,(F G)H t(F G(t,y)H)t(s(F G)H)t s(F G H)s(F t(G H)s(F G H)F (G H)所以所以(F G)H=F(G H)（2）任取）任取,(F G)-1 F G t(F(t,x)G)t(G-1(t,y)F-1)G-1 F-1 所以（所以（F G）-1=F-1 G-1第24页，本讲稿共61页7.3 关系的运算关系的运算定理定理7.3 设设R为为A上的关系上的关系,则则 R IA=IA R=R定理定理7.4 设设F,G,H为任意关系为任意关系,则则nF (GH)=(F G)F G)n(GH)F=(G F

19、)(H F)nF (GH (F G)(F H)n(GH)F (G F)(H F)第25页，本讲稿共61页7.3 关系的运算关系的运算定定义7.10 设R为A上的关系，上的关系，n为自然数，自然数，则R的的n次次幂定定义为：（1）R0=|x A=IA（2）Rn+1=Rn R 由以上定由以上定义可知，可知，对于于A上的任何关系上的任何关系R1和和R2都有都有 R10=R20=IA 也就是也就是说，A上任何关系的上任何关系的0次次幂都相等，都等于都相等，都等于A上的恒等关系上的恒等关系IA。此外。此外对于于A上的任何关系上的任何关系R都有都有 R1=R，因，因为 R1=R0 R=IA R=R定理定理

20、7.6 设A为n元集，元集，R是是A上的关系，上的关系，则存在自然数存在自然数 s和和t,使得使得 Rs=Rt第26页，本讲稿共61页7.3 关系的运算关系的运算定理定理7.7 设R是是A上的关系，上的关系，m,n N，则(1)Rm Rn=Rm+n(2)(Rm)n=Rmn证 用用归纳法法(1)对于任意于任意给定的定的m N,施施归纳于于n。若若n=0，则有有 Rm R0=Rm IA=Rm=Rm+0 假假设 Rm Rn=Rm+n，则有有 Rm Rn+1=Rm(Rn R)=(Rm Rn)R=Rm+n+1，所以所以对一切一切m,n N有有Rm Rn=Rm+n。(2)对于任意于任意给定的定的m N,施

21、施归纳于于n。若若n=0，则有有(Rm)0=IA=R0=Rm0 假假设(Rm)n=Rmn，则有有 (Rm)n+1=(Rm)n Rm=(Rmn)Rn=Rmn+m=Rm(n+1)所以所以对一切一切m,n N有有(Rm)n=Rmn第27页，本讲稿共61页7.4 关系的性关系的性质关系的性质主要有以下五种关系的性质主要有以下五种:自反性自反性,反自反性反自反性,对称性对称性,反对称性和传递性反对称性和传递性定义定义7.11 设设R为为A上的关系，上的关系，（1）若）若 x(x A R)，则称，则称R在在A上是自反的上是自反的n关系矩阵的特点是主对角线上的元素全为关系矩阵的特点是主对角线上的元素全为 1

22、nR是自反关系是自反关系 IA Rn关系图的中的每个顶点都有环关系图的中的每个顶点都有环 n例例:设设A=1,2,3,则则R=,是是A上的自反关系上的自反关系 （2）若）若 x(x A R)，则称，则称R在在A上是反自反的上是反自反的n关系矩阵的特点是主对角线上的元素全为关系矩阵的特点是主对角线上的元素全为 0nR是自反关系是自反关系 IA R=n关系图中每个项点都没有环关系图中每个项点都没有环n例例:设设A=1,2,3,则则R=,是是A上的反自反关系上的反自反关系第28页，本讲稿共61页7.4 关系的性关系的性质定义定义7.12 设设R为为A上的关系，上的关系，(1)若若 x y(x,y A

23、 R R)则称则称 R 为为A上对称的关系上对称的关系n关系矩阵的特点是关系矩阵的特点是 关系矩阵是对称矩阵关系矩阵是对称矩阵nR是对称关系是对称关系 R=R-1n关系图中如果两个顶点之间有边，一定是一对方向相反的边关系图中如果两个顶点之间有边，一定是一对方向相反的边n例例:设设A=1,2,3,则则R=,是是A上的对称关系上的对称关系 (2)若若 x y(x,y A R R x=y)则称则称R为为A上的反对称关系上的反对称关系n关系矩阵的特点是关系矩阵是除了主对角线上的元素外关系矩阵的特点是关系矩阵是除了主对角线上的元素外,关于主对关于主对角线对称的两个元素不同时为角线对称的两个元素不同时为

24、1nR是反对称关系是反对称关系 RR-1 IAn如果两个顶点之间有边，一定是一条有向边如果两个顶点之间有边，一定是一条有向边(无双向边无双向边)n例例:设设A=1,2,3,则则R=,是是A上的反对称关系上的反对称关系第29页，本讲稿共61页7.4 关系的性关系的性质定义定义7.13 设设R为为A上的关系上的关系 若若 x y z (x,y,z A R R R)则称则称R是是A上的传递关系上的传递关系nR是传递关系是传递关系 R 2 Rn关系矩阵的特点是关系矩阵的特点是 在关系矩阵中在关系矩阵中,当当rik=1且且rkj=1时一定有时一定有rij=1 n对对R 2的关系矩阵中取值为的关系矩阵中取

25、值为1的元素的元素,在在R的关系矩阵中对应位置上的的关系矩阵中对应位置上的元素取值也为元素取值也为1n如果顶点如果顶点xi到到xj有边有边,xj到到xk有边有边,则则xi到到xk也有边也有边n例例:设设A=1,2,3,则则 R=,S=,都是都是A上的传递关系上的传递关系 T=,不是不是A上的传递关系上的传递关系第30页，本讲稿共61页7.4 关系的性关系的性质定理定理7.9 设设R为为A上的关系，则上的关系，则（1）R在在A上自反当且仅当上自反当且仅当 IAR（2）R在在A上反自反当且仅当上反自反当且仅当 RIA=（3）R在在A上对称当且仅当上对称当且仅当 R=R-1（4）R在在A上反对称当且

26、仅当上反对称当且仅当 RR-1 IA（5）R在在A上传递当且仅当上传递当且仅当 R R R证证:(1)必要性必要性 任取任取，由于，由于R在在A上自反必有上自反必有 IA x,y A x=y R 从而证明了从而证明了 IA R 充分性充分性 任取任取x，有，有 x A IA R 因此因此R在在A上是自反的上是自反的第31页，本讲稿共61页7.4 关系的性关系的性质(2）必要性）必要性 用反证法用反证法 假设假设 RIA，必存在，必存在 RIA 由于由于 IA是是A上恒等关系，从而推出上恒等关系，从而推出 x A且且 R 这与这与R在在A上是反自反的相矛盾上是反自反的相矛盾 充分性充分性 任取任

27、取x，则有，则有 x A IA R(由于由于RIA=)从而证明了从而证明了R在在A上是反自反的上是反自反的第32页，本讲稿共61页7.4 关系的性关系的性质设设A是非空集合，举例说明是非空集合，举例说明n不是自反关系未必是反自反关系不是自反关系未必是反自反关系 n对称性与反对称性是不互相排斥的对称性与反对称性是不互相排斥的 第33页，本讲稿共61页7.4 关系的性关系的性质例例1 设设A=1,2,3,4nR=,试判定试判定R具有哪几种性质具有哪几种性质 解解:nIA=,nR-1=,n因为因为 IA R,所以它不具有自反性所以它不具有自反性nIA R=,所以它具有反自反性所以它具有反自反性n因为

28、因为RR-1,所以它不具有对称性所以它不具有对称性n因为因为RR-1=IA,所以它具有反对称性所以它具有反对称性n因为因为R 2=R,所以它具有传递性所以它具有传递性nR具有反自反性，反对称性，传递性具有反自反性，反对称性，传递性第34页，本讲稿共61页7.4 关系的性关系的性质令令P是是A上二元关系的集合上二元关系的集合,在在P中考虑关系性质的保持问题中考虑关系性质的保持问题,例如例如,两个自反关两个自反关系的并仍是自反关系系的并仍是自反关系,两个非自反关系的并就不见得还是非自反关系两个非自反关系的并就不见得还是非自反关系.现在就关系现在就关系性质的保持与否填入下表性质的保持与否填入下表,当

29、填上当填上“否否”时请给出反例时请给出反例RSRSR SRSR1自反性是是否否是是反自反性是是是否否是对称性是是是是否是反对称性否是是否否是传递性否是否否否是第35页，本讲稿共61页7.5 关系的关系的闭包包设设R是集合是集合A上的二元关系上的二元关系,如果关系如果关系R 满足下列条件满足下列条件n(1)R 具有自反性具有自反性n(2)R R n(3)若若A上的二元关系上的二元关系R 符合符合和和,则必有则必有R R,则称则称R 为为R的自反闭包的自反闭包 记为记为 r(R)r(R)=R IARR R A A第36页，本讲稿共61页7.5 关系的关系的闭包包设设R是集合是集合A上的二元关系上的

30、二元关系,如果关系如果关系R 满足下列条件满足下列条件n(1)R 具有对称性具有对称性n(2)R R n(3)若若A上的二元关系上的二元关系R 符合符合和和,则必有则必有R R,则称则称R 为为R的对称闭包的对称闭包 记为记为 s(R)s(R)=R R-1RR R A A第37页，本讲稿共61页7.5 关系的关系的闭包包设设R是集合是集合A上的二元关系上的二元关系,如果关系如果关系R 满足下列条件满足下列条件n(1)R 具有传递性具有传递性n(2)R R n(3)若若A上的二元关系上的二元关系R 符合符合和和,则必有则必有R R,则称则称R 为为R的传递闭包的传递闭包 记为记为 t(R)t(R

31、)=R R2 R3 RR R A A第38页，本讲稿共61页7.5 关系的关系的闭包包例例2 设设R为集合为集合A=1,2,3上的一个二元关系上的一个二元关系,R=,试求试求R的自反闭包的自反闭包r(R)、对称闭包、对称闭包s(R)、传递闭包、传递闭包t(R)解解:nr(R)=R IA=,ns(R)=R R-1=,n为求为求t(R)得先求得先求R2,R3,.这里这里 R2=,R3=,R4=R,R5=R2,.一般地有一般地有 R3n+1=R,R3n+2 =R2,R3n =R3(n=1,2,3,),所以有所以有 t(R)=R R2 R3=A A 第39页，本讲稿共61页7.5 关系的关系的闭包包W

32、arshall算法算法 检查第检查第k列元素列元素第第k行元素行元素第第i行元素行元素1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0检查第检查第k列元素列元素:从第一行开始从第一行开始,如果第如果第i行上的元素为行上的元素为1,则把第则把第k行整行元素加到对应第行整行元素加到对应第i行行元素上。直到检查完第元素上。直到检查完第n行元素行元素,得到的矩阵为得到的矩阵为Mk.从第一列开始直到第从第一列开始直到第n列重复上述步骤列重复上述步骤,最终得到的矩阵最终得到的矩阵Mn即为即为t(R)的关系矩阵的关系矩阵第40页，本讲稿共61页7

33、.5 关系的关系的闭包包w例例3 设设A=1,2,3,4,5,R=,w请用请用Warshall算法求算法求t(R)w解：解：记记 wt(R)=,+第41页，本讲稿共61页7.5 关系的关系的闭包包定理定理7.13 设设R是非空集合是非空集合A上的关系，上的关系，（1）若）若R是自反的，则是自反的，则s(R)与与t(R)也是自反的。也是自反的。（2）若）若R是对称的，则是对称的，则r(R)与与t(R)也是对称的。也是对称的。（3）若）若R是传递的，则是传递的，则r(R)是传递的。是传递的。从这里可以看出，如果计算关系从这里可以看出，如果计算关系R的自反、对称、传递的闭包，为了不的自反、对称、传递

34、的闭包，为了不失去传递性，传递闭包运算应该放在对称闭包运算的后边，失去传递性，传递闭包运算应该放在对称闭包运算的后边，若令若令 tsr(R)表示表示R的自反、对称、传递闭包，则的自反、对称、传递闭包，则 tsr(R)=t(s(r(R)第42页，本讲稿共61页7.6 等价关系与划分等价关系与划分设设 A=1,2,3,4,5,6,7,8如何定义集合如何定义集合A上的关系上的关系R，使得，使得n在同一区域中的任意两个元素在同一区域中的任意两个元素x,y都有都有 x R yn在不同一区域中的任意两个元素在不同一区域中的任意两个元素x,y都有都有 x yR=,=(1,4,71,4,7)(2,5,82,5

35、,8)(3,63,6)R=(x,y)|x-y被被3整除整除,x,y A 关系关系R具有哪些性质具有哪些性质?1437658214376582(自反性、对称性、传递性自反性、对称性、传递性)第43页，本讲稿共61页7.6 等价关系与划分等价关系与划分定义定义7.15 设设R是非空集合是非空集合A上的关系上的关系,如果关系如果关系R同时具有自反性、对称性和传同时具有自反性、对称性和传递性递性,则称则称R为A上的等价关系等价关系.设设R是一个等价关系如果是一个等价关系如果 R,则称则称x等价于等价于y,记为记为x y 定义定义7.16 设设R是非空集合是非空集合A上的等价关系上的等价关系,x A,令

36、令 xR=y|x A xRy 称称xR为为x关系关系R的一个等价类的一个等价类,简称为简称为x的等价类的等价类,简记为简记为a例例:设设A=1,2,3,4,5,6,7,8 R=(x,y)|x-y被被3整除整除,x,y A 则则 1=1,4,7 2=2,5,8 3=3,6 1=4=7,2=5=8,3=6第44页，本讲稿共61页7.6 等价关系与划分等价关系与划分定理定理7.14 设设R是非空集合是非空集合A上的等价关系上的等价关系,则则n x A,x是是A的非空子集的非空子集n x,y A,如果如果 xRy,则则 x=yn x,y A,如果如果x y,则则 x y=n x|x A =A定义定义7

37、.17 设设R是集合是集合A上的等价关系上的等价关系,以以R的所有等价类作为元素的集合称为的所有等价类作为元素的集合称为A关关于于R的商集的商集 记为记为A/R,即即 A/R =xR|x A 例例:设设A=1,2,3,4,5,6,7,8,R=(x,y)|x-y被被3整除整除,x,y A ,则则 A/R =1,4,7,2,5,8,3,6 第45页，本讲稿共61页7.6 等价关系与划分等价关系与划分定义定义7.18 设设A为非空集合为非空集合,若若A的子集族的子集族 (P(A),是是A的子集构成的集合的子集构成的集合)满足下面的条件满足下面的条件n n x y(x,y xy xy=)n =A 则称

38、是则称是A的一个划分的一个划分,称称中的元素为中的元素为A的划分块的划分块例例7.17 设设A=a,b,c,d,给定给定 1,2,3,4,5,6如下如下:1=a,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 则则1,2是是A的划分的划分,其他都不是其他都不是A的划分的划分第46页，本讲稿共61页7.6 等价关系与划分等价关系与划分w把商集把商集A/R和划分的定义相比较和划分的定义相比较,易见商集就是易见商集就是A的一个划分的一个划分,并且不同并且不同的商集将对应于不同的划分。反之的商集将对应于不同的划分。反之,任给任给A的

39、一个划分的一个划分,如下定义如下定义A上的上的关系关系R:设设=A1,A2,Ak 则不难证明则不难证明R为为A上的等价关系，且该等价关系的商集就是上的等价关系，且该等价关系的商集就是.由由此可见此可见,A上的等价关系与上的等价关系与A的划分是一一对应的的划分是一一对应的第47页，本讲稿共61页7.6 等价关系与划分等价关系与划分w等价关系的关系矩阵等价关系的关系矩阵w例例3 设设A=1,2,3,4,5,6,7,8w R=(x,y)|x-y被被3整除整除,x,y A 第48页，本讲稿共61页7.6 等价关系与划分等价关系与划分等价关系的关系图等价关系的关系图例例2 设设A=1,2,3,4,5,6

40、,7,8 R=(x,y)|x-y被被3整除整除,x,y A 1472583614725836第49页，本讲稿共61页7.7 偏序关系偏序关系设设A=1,2,3,4,5,R=(x,y)|xy x,y A 设设B=a,b,c,S=(x,y)|x y x,y 2B 关系关系R和和S分别确定了集合分别确定了集合A,B中元素的一种次序中元素的一种次序R和和S都具有自反性、反对称性、传递性都具有自反性、反对称性、传递性1 15 54 43 32 2 a,ba,b aa bb cc a,ca,c b,cb,c a,b,ca,b,c 第50页，本讲稿共61页7.7 偏序关系偏序关系定义定义7.19 7.19

41、设设R R是为非空集合是为非空集合A A上的关系上的关系n如果如果R R是自反性的、反对称性的和传递性的是自反性的、反对称性的和传递性的,则称则称R R为为A A上的一个偏上的一个偏序关系序关系,记作记作“”n设设 为偏序关系为偏序关系,如果如果 ,则记作则记作x x y y,读作读作x”x”小于或等于小于或等于y y定义定义7.20 7.20 设设 为非空集合为非空集合A A上的偏序关系上的偏序关系,定义定义nx,y A,xy x y xy (其中其中x xy,y,读作读作x x小于小于y)y)n x,y A,x,y可比可比 x y y x定义定义7.21 7.21 设设R R为非空集合为非

42、空集合A A上的偏序关系上的偏序关系,如果如果x,yx,yA,xA,x与与y y都是可比的都是可比的,则称则称R R为为A A上的全序关系上的全序关系(或线序关系或线序关系)定义定义7.22 7.22 集合集合A A和和A A上的偏序关系上的偏序关系 一起叫作偏序集一起叫作偏序集,记作记作A,n例例1 设设A=1,2,3,4,6,12,是一个偏序集是一个偏序集n例例2 2 设设A=1,2,3,4,5,是一个偏序集是一个偏序集(全序集全序集)n例例3 3 设设 B=a,b,c,是一个偏序集是一个偏序集第51页，本讲稿共61页7.7 偏序关系偏序关系定义定义7.22 设设A,为偏序集为偏序集,x,

43、y A,如果如果xy且不存在且不存在z A,使得使得x y z,则称则称y覆盖覆盖x哈斯图哈斯图:在画偏序集在画偏序集A,的哈斯图时的哈斯图时,首先适当排列项点的顺序使得首先适当排列项点的顺序使得nx,y A,如果如果xy 则将则将x画在画在y的下方的下方n对于对于A中的两个不同元素中的两个不同元素x和和y,如果如果y覆盖覆盖x,就用一条线段连接就用一条线段连接x和和y设设A=1,2,3,4,5,B=a,b,c,偏序集偏序集和和的哈斯图的哈斯图 如下所示如下所示:1 15 54 43 32 2 a,ba,b aa bb cc a,ca,c b,cb,c a,b,ca,b,c 的哈斯图的哈斯图的

44、哈斯图的哈斯图第52页，本讲稿共61页7.7 偏序关系偏序关系例例7.20 已知偏序集已知偏序集的哈斯图如图的哈斯图如图7.8所示所示,试求出集合试求出集合A和关系和关系R的表达式的表达式解解:A=a,b,c,d,e,f,g,h R=,IAa a b b c c g g d d e e h h f f 图图7.8第53页，本讲稿共61页7.7 偏序关系偏序关系定义定义7.24 7.24 设设A,为偏序集为偏序集,B,BA,yBA,yBn x(x B y x)成立成立,则称则称y为为B的最小元的最小元nx(x B x y)成立成立,则称则称y为为B的最大元的最大元nx(x B x y x=y)成

45、立成立,则称则称y为为B的极小元的极小元nx(x B y x x=y)成立成立,则称则称y为为B的极大元的极大元最小元和极小元是不一样的最小元和极小元是不一样的(最大元和极大元也有这种区别最大元和极大元也有这种区别)n最小元是最小元是B中最小的元素中最小的元素,它与它与B中其他元素都可比中其他元素都可比;n极小元不一定与极小元不一定与B中元素都可比中元素都可比,只要没有比它小的元素就是极小元只要没有比它小的元素就是极小元n对于有穷集对于有穷集B,极小元一定存在极小元一定存在,但最小元不一定存在但最小元不一定存在n最小元如果存在最小元如果存在,一定是唯一的一定是唯一的,但极小元可能有多个但极小元

46、可能有多个n如果如果B中只有一个极小元中只有一个极小元,则它一定是则它一定是B的最小元的最小元第54页，本讲稿共61页7.7 偏序关系偏序关系例例:设设A=a,b,cnR1=,IAnR2=,IAnR3=IA请分别给出有无穷多个极大元、无穷多个极小元、有无穷多个极大元并且有无请分别给出有无穷多个极大元、无穷多个极小元、有无穷多个极大元并且有无穷多个极小元的偏序集穷多个极小元的偏序集acb有最大元但没有最小元有最大元但没有最小元acb有最小元但没有最大元有最小元但没有最大元acb没有最小元和最大元没有最小元和最大元R1R2R3第55页，本讲稿共61页7.7 偏序关系偏序关系例例7.21 7.21

47、设偏序集设偏序集A,如图如图7.87.8所示所示,求求A A的极小元的极小元,最小元最小元,极大元极大元,最大元最大元 解解:极小元极小元:a,b,c,g:a,b,c,g 极大元极大元:a,f,h:a,f,h 没有最大元与最小元没有最大元与最小元a a b b c c g g d d e e h h f f 图图7.8第56页，本讲稿共61页定义定义7.25 7.25 设设A,为偏序集为偏序集,B,BA,yAA,yAnx(xx(xB B x x y)y)成立成立,则称则称y y为为B B的上界的上界nx(xx(xB B y y x)x)成立成立,则称则称y y为为B B的下界的下界n令令C C

48、y|yy|y是是B B的上界的上界,则称则称C C的最小元为的最小元为B B的最小上界或上确界的最小上界或上确界n令令D Dy|yy|y是是B B的下界的下界,则称则称D D的最大元为的最大元为B B的最大下界或下确界的最大下界或下确界B B的最小元一定是的最小元一定是B B的下界的下界,同时也是同时也是B B的下确界的下确界B B的最大元一定是的最大元一定是B B的上界的上界,同时也是同时也是B B的上确界的上确界B B的上、下界不一定是的上、下界不一定是B B中的元素中的元素B B的上的上(下下)界、上界、上(下下)确界都可能不存在确界都可能不存在上上(下下)确界如果存在一定是唯一的确界如

49、果存在一定是唯一的例例:考虑图考虑图7.87.8的偏序集的偏序集,B=b,c,d,B=b,c,d 上界上界:d,f :d,f 上确界上确界:d:da a b b c c g g d d e e h h f f 7.7 偏序关系偏序关系第57页，本讲稿共61页7.7 偏序关系偏序关系例例:设设A=1,2,2,3,2,3,4,2,3,4,5,“”为通常的集合包含关系为通常的集合包含关系,则则(A,)是偏序集是偏序集,哈斯图如右图所示哈斯图如右图所示 n1是其唯一的极大元是其唯一的极大元,(A,)没有最大元没有最大元n1和和2是其极小元是其极小元,(A,)没有最小元没有最小元nB1=2,3,2,3,

50、4 则则2,3,4,2,3,4,5都是都是B1的上界的上界,2,2,3都是都是B1的下界的下界.n取取 B2=1,2,2,3 则则B2没有上界也没有下界没有上界也没有下界22,32,3,42,3,4,52,3,4,5,61第58页，本讲稿共61页7.7 偏序关系偏序关系例例 设设A=1,2,3,4,5,6 偏序集偏序集的哈斯图如右所示的哈斯图如右所示n的最小元的最小元,极小元都是极小元都是2,2,无最大元无最大元,极大元是极大元是5,65,6nB B1 1=1,3,4,6,2=1,3,4,6,2是下界是下界,2,2是下确界是下确界,无上界无上界,无上确界无上确界nB B2 2=3,6,1,2,