关系的性质离散数学精选PPT.ppt
关系的性质离散数学关系的性质离散数学4/11/2023 5:19 PM Discrete Math.,huang liujia1第1页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia2第 七 章 二 元 关 系7.1有序对与笛卡儿积有序对与笛卡儿积7.2二元关系二元关系7.3关系的运算关系的运算7.4关系的性质关系的性质7.5关系的闭包关系的闭包7.6等价关系与划分等价关系与划分7.7偏序关系偏序关系第2页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia3定定义义7.1 由由两两个个元元素素x和和y（允允许许xy）按按一一定定顺顺序序排排列列成成的的二二元元组组叫做一个叫做一个有序对有序对，记为，记为。注注：有序对的性质：有序对的性质：1.当当x y时，时，。2.的充分必要条件是的充分必要条件是x=u且且y=v。7.1有序对与笛卡尔积有序对与笛卡尔积定义定义7.27.2 设设A,BA,B是集合。由是集合。由A A中元作为第一元素，中元作为第一元素，B B中元作为第二元素组中元作为第二元素组成的所有有序对的集合，称为集合成的所有有序对的集合，称为集合A A与与B B的的笛卡尔积笛卡尔积，记为，记为AB。即。即 AB|x Ay B。第3页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia4注：笛卡尔积的性质：注：笛卡尔积的性质：1.1.A=,A=;2.AB BA,除非除非 A=或或B=或或A=B;3.(AB)C A(BC),除非除非 A=或或B=或或C=.4.A(BC)=(AB)(AC);(BC)A=(BA)(CA);A(BC)=(AB)(AC);(BC)A=(BA)(CA);5.(A C)(B D)(AB)(CD).7.1有序对与笛卡尔积有序对与笛卡尔积第4页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia5例例 证明证明A(BC)=(AB)(AC)。证：任取证：任取 ，A(BC)x Ay(BC)x A(y By C)(x Ay B)(x Ay C)(AB)(AC)(AB)(AC)A(BC)=(AB)(AC)例例7.2 设设 A=1,2,求求 P(A)A。解：解：P(A)A =,1,2,1,21,2=,7.1有序对与笛卡尔积有序对与笛卡尔积第5页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia6例例7.37.3 设设A,B,C,D为任意集合，判断下列命题是否为真。为任意集合，判断下列命题是否为真。（1）ABACB=C（2）A(BC)=(AB)(AC)（3）(A=B)(C=D)AC=BD（4 4）存在集合）存在集合A,A,使使 A A AAAA7.1有序对与笛卡尔积有序对与笛卡尔积解解:(1):(1)不一定为真，不一定为真，(3)(3)为真。为真。(4)(4)为真。为真。当当A=,B=1,C=2,3时，便不真。时，便不真。(2)(2)不一定为真，不一定为真，当当A=B=1,C=2时，时，A(BC)=1=1,而而(AB)(AC)=1=.等量代入。等量代入。当当A=时时,使使A AA.第6页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia7一、基本概念一、基本概念定定义义7.37.3 如如果果一一个个非非空空集集合合的的元元素素都都是是有有序序对对，则则称称该该集集合合为为一一个个二二元元关关系系。特特别地，空集也是一个二元关系。别地，空集也是一个二元关系。注：对一个二元关系注：对一个二元关系R，如果，如果 R,则记为则记为xRy；如果如果 R，则记为，则记为xRy。定定义义7.47.4 设设A,B为为集集合合，AB的的任任何何子子集集所所定定义义的的二二元元关关系系称称为为从从A到到B的的二二元元关系关系。特别地，当。特别地，当A=B时，称为时，称为A上的二元关系上的二元关系。定义定义7.57.5 对任何集合对任何集合A，(1)(1)称空集称空集 为为A上的上的空关系空关系。(2)(2)A上的上的全域关系全域关系EA=x Ay A=AA(3)(3)A上的上的恒等关系恒等关系IA=x A.7.2二元关系二元关系第7页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia8二二.关系的表达方式关系的表达方式1.1.集合表达式集合表达式：列出关系中的所有有序对。：列出关系中的所有有序对。例例7.47.4 设设A=1,2,3,4,试列出下列关系试列出下列关系R R的元素。的元素。(1)(1)R=x是是y的倍数的倍数(2)(2)R=(xy)2 A(3)(3)R=x/y是素数是素数(4)(4)R=x y(5)(5)R=(x,y A)(x y)解解:(1)R=,(2)R=,(3)R=,(4)R=EA-IA=,(5)R=,7.2二元关系二元关系第8页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia92.2.关系矩阵法：关系矩阵法：设设A=A=x1,x2,xn,R 是是 A 上上的关系。令：的关系。令：则则矩矩阵阵 称为称为R 的的关系矩阵关系矩阵。7.2二元关系二元关系第9页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia10例例 设设A=1,2,3,4,R=,则则R的关系矩阵为的关系矩阵为7.2二元关系二元关系第10页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia113.关系图法关系图法 设设A=x1,x2,xn,R是是A上上的的关关系系。以以A的的元元素素作作为为顶顶点点，当当且且仅仅当当xiRxj时，时，xi 向向xj 连一条有向边，所得的图形称为连一条有向边，所得的图形称为R的关系图，记为的关系图，记为GR。例例7.6 设设 A=1,2,3,4,R=,则则R R的关系图为的关系图为12437.2二元关系二元关系第11页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia12一、基本概念一、基本概念定义定义7.6设设R是二元关系。定义是二元关系。定义(1)R的的定定义义域域:domR=x|y(R),即即R中中所所有有有有序序对对的的第第一一元元素构成的集合。素构成的集合。(2)R的的值值域域，ranR=y|x(R),即即R中中所所有有有有序序对对的的第第二二元元素构成的集合。素构成的集合。(3)R的域的域:fld R=dom Rran R。例例7.5R=,则则domR=1,2,4，ranR=2,3,4,fld R=1,2,3,4。7.3 关系的运算关系的运算第12页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia13定义定义7.77.7 设设R R为二元关系，称为二元关系，称 R-1=|R为为R的的逆关系逆关系。定义定义7.87.8 设设F,G为二元关系。称为二元关系。称为为G 对对F 的的右复合右复合(或或F 对对G 的的左复合左复合)。例如例如,F=,G=,则则 F-1=,7.3 关系的运算关系的运算第13页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia14定义定义7.9设设R是二元关系是二元关系,A是集合是集合(通常通常A domR)7.3 关系的运算关系的运算例例7.7 设设R为为,则则(1)R在在A上的限制上的限制:RA=|xRyx AR 1=2,3,R=,R 2,3=2,4。R1=,R=,R2,3=,，(2)A在在R下的像下的像:R A=ran(RA)第14页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia15定义定义7.107.10 设设R是是A上的关系上的关系,n,n为自然数为自然数,则则R的的n n次幂次幂定义为定义为:(1)R0=|x A=IA;(2)注注:1.1.对对A A上的任何关系上的任何关系R,R,都有都有 R0=IA,R1=R。2.2.Rn的求法的求法:除了根据定义按关系的复合来求之外除了根据定义按关系的复合来求之外,还可以用矩阵法和关系图法还可以用矩阵法和关系图法。7.3 关系的运算关系的运算第15页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia16例例7.87.8 设设A=a,b,c,d,R=,求求R的的各各次次幂幂,分分别别用用矩矩阵和关系图表示阵和关系图表示.解解:R的关系矩阵的关系矩阵:R2,R3,R4 的关系矩阵分别是：的关系矩阵分别是：第16页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia17可见可见M4=M2。故。故R2=R4=R6=;R3=R5=R7=。第17页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia18此外此外,R0=IA的关系矩阵为的关系矩阵为:用关系图法得到用关系图法得到 R0,R1,R2,的关系图如下的关系图如下:dabcR0R1abcdR2=R4=bcdaabcdR3=R5=第18页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia19关系是集合关系是集合,故有关集合的所有运算性质对关系都成立。故有关集合的所有运算性质对关系都成立。定理定理7.1 设设F F是关系是关系,则则(1)(F-1)-1=F;(2)dom F-1=ran F,ran F-1=domF。证证:(1)(F-1)-1 F-1 F(F-1)-1=F。(2)x domF-1 y(F-1)y(F)x ran FdomF-1=ran F。同理可证同理可证 ran F-1=dom F。二二.关系的运算性质关系的运算性质第19页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia20定理定理7.27.2 设设F,G,H是关系，则是关系，则(1)(F G)H=F(G H);(2)(F G)1=G1 F1.证证:(1)(F G)H)t(F G)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 G)t(G1 F1)(G1 F1)(F G)1=G1 F1第20页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia21定理定理7.37.3 设设R是是A上的关系上的关系,则则 R IA=IA R=R.证证:(R IA)t(R IA)t(Rt=y)R R Ry A R IA(R IA)R IA=R同理可证同理可证 IA R=R第21页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia22定理定理7.47.4 设设F,G,H是关系是关系,则则(1)F(GH)=F GF H;(2)(GH)F=G FH F;(3)F(GH)F GF H;(4)(GH)F G FH F.证证:以以(3)为例为例.F(GH)t(F(GH)t(F G H)t(F G)(F H)t(F G)t(F H)F G F H F GF HF(GH)=F GF H第22页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia23定理定理7.5设设F为关系为关系,A,B为集合为集合,则则(1)F(AB)=FAFB;(2)F AB=F A F B(3)F(AB)=FAFB;(4)F AB F A F B(1)F(AB)F(AB)=FAFB证证:以以(1)和和(4)为例为例 F(x Ax B)(Fx A)(Fx B)FA FB(FAFB)Fx(AB)第23页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia24(4)y F AB x(F(x AB)x(Fx Ax B)x(Fx A)(Fx B)x(Fx A)x(Fx B)y F A y F B y(F A F B)F AB=F A F B 第24页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia25定理定理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 R1=Rm+n+1由归纳法原理由归纳法原理,知命题成立。知命题成立。(2)对任意取定的对任意取定的m N,关于关于n作数学归纳法。作数学归纳法。当当n=0时时,(Rm)0=IA=R0=Rm0假设假设(Rm)n=Rmn,则则(Rm)n+1=(Rm)n Rm=Rmn Rm=Rmn+m=Rm(n+1)由归纳法原理由归纳法原理,知命题成立。知命题成立。定理定理7.6 设设A是是n元集合元集合,R为为A上的关系上的关系,则存在自然数则存在自然数s和和t,使得使得Rs=Rt。第25页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia26定理定理7.8设设R为为A上的关系上的关系,若存在自然数若存在自然数s,t(st),使得使得Rs=Rt,则则(1)k N都有都有Rs+k=Rt+k(2)k,i N都有都有Rs+kp+i=Rs+i,其中其中p=ts(3)令令S=R0,R1,Rt1,则对则对 q N都有都有Rq S。证明：见教材证明：见教材P112。注注:定定理理7.6和和定定理理7.8的的(3)表表明明,有有限限集集合合A上上的的二二元元关关系系只只有有有有限限多多个个,而而且且一个关系的幂序列一个关系的幂序列R0,R1R2,是一个周期性变化的序列。是一个周期性变化的序列。例例7.9见教材见教材P113。第26页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia27一、关系的五种性质一、关系的五种性质 关系的性质主要有关系的性质主要有5 5种种:自反性自反性,反自反性反自反性,对称性对称性,反对称性和传递性。反对称性和传递性。定定义义7.117.11 设设R是是A上上的的关关系系,若若 x(x A R),则则称称 R R在在A上上是是自自反反的的(Reflexive);若若 x(x A R),则称则称R在在A上是上是反自反的反自反的(antiReflexive).7.4 关系的性质关系的性质第27页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia28例例7.107.10(1)(1)A上的全域关系上的全域关系EA、恒等关系恒等关系IA都是都是A上的自反关系上的自反关系.(2)(2)小于等于关系小于等于关系 LA=x,y Axy,A R.整除关系整除关系 DA=x,y Ax整除整除y,A Z*.包含关系包含关系 R=x,y A Ax y,A A 是集合族。是集合族。都是自反关系都是自反关系.(3)(3)小于关系小于关系 SA=x,y Ax y,A R.真包含关系真包含关系 R=x,y A Ax y,A A是集合族。是集合族。都是反自反关系都是反自反关系.(4)(4)设设 A=1,2,3,R1=,是是A上的自反关系上的自反关系;R2=是是A上的反自反关系上的反自反关系;R3=,既不是自反既不是自反的的,也不是反自反的也不是反自反的.第28页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia29定义定义7.12 设设R是是A上的关系上的关系,若若 x y(x,y A R(y,x)R),则称则称R是是A上的上的对称关系对称关系(Symmetric);若若 x y(x,y A R(y,x)Rx=y),则称则称R是是A上的上的反对称关系反对称关系(antiSymmetric).例例7.11(1)(1)A上的全域关系上的全域关系EA,恒等关系恒等关系IA及空关系及空关系 都是都是A上的对称上的对称关系关系;IA和和 同时也是同时也是A上的反对称关系上的反对称关系.(2)(2)设设A=1,2,3,A=1,2,3,则则 R1=,既是既是A上的对称关系上的对称关系,也是也是A上的反对称关系上的反对称关系;R2=,是对称的是对称的,但不是反对称的但不是反对称的;R3=,是反对称的是反对称的,但不是对称的但不是对称的;R4=,既不是对称的也不是反对称的。既不是对称的也不是反对称的。第29页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia30定义定义7.13设设R是是A上的关系上的关系,若若 x y z(x,y,z A R R R),则称则称R是是A上的上的传递关系传递关系。例例7.12(1)(1)A上的全域关系上的全域关系EA,恒等关系恒等关系IA和空关系和空关系 都是传递关系。都是传递关系。(2)(2)小小于于等等于于关关系系,整整除除关关系系和和包包含含关关系系是是传传递递关关系系,小小于于关关系系和和真真包包含含关关系也是传递关系。系也是传递关系。(3)(3)设设A=1,2,3,则则R1=,和和R2=都是都是A上的传递关系上的传递关系,但但R3=,不是不是A上的传递关系。上的传递关系。第30页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia31定理定理7.9 设设R为为A上的关系上的关系,则则(1)(1)R在在A上自反当且仅当上自反当且仅当 IA R(2)(2)R在在A上反自反当且仅当上反自反当且仅当 RIA=(3)(3)R在在A上对称当且仅当上对称当且仅当 R=R-1(4)(4)R在在A上反对称当且仅当上反对称当且仅当 RR-1 IA(5)(5)R在在A上传递当且仅当上传递当且仅当 R R R证证:(1):(1)必要性必要性:因因R在在A上自反上自反,故故 IAx,y Ax=y R，从而从而IA R。充分性充分性:因因 x A IA R,故故R在在A上自反。上自反。二、各种性质的充分必要条件二、各种性质的充分必要条件第31页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia32(2)必要性必要性(用反证法用反证法):):假设假设RIA,则必存在则必存在 RIA,即即 R且且 IA。由由 IA知知x=y.从而从而 R.这与这与R在在A上是反自反矛盾。上是反自反矛盾。充充分分性性:x A IA R(因因RIA=),这这说说明明R在在A上上是是反自反的反自反的。(3)必要性必要性:R是是A上的对称关系上的对称关系,R R R-1,故故R=R-1。充分性充分性:由于由于R=R-1,R R-1 R.故故R在在A上是对称的。上是对称的。第32页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia33(4)必要性必要性:因因R在在A上是反对称的上是反对称的,故故 RR1 R R1 R Rx=y IA.RR1 IA 充分性充分性:因因 RR1 I IA A,故故 R R R R1 RR1 IAx=y.从而从而 R在在A上是反对称的上是反对称的.第33页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia34(5)必要性必要性:因因R在在A上是传递的上是传递的,故故 R R t(R R)R因此因此R R R充分性充分性:因因R R R,故故 R R R R RR在在A上是传递的。上是传递的。第34页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia35 例例7.13 设设A是集合是集合,R1和和R2是是A上的关系上的关系,证明证明(1)(1)若若R1和和R2都是自反的和对称的都是自反的和对称的,则则R1R2也是自反的和对称的也是自反的和对称的.(2)若若R1和和R2是传递的是传递的,则则R1R2也是传递的也是传递的.证证:(1)(1)因因R1和和R2是是A上的自反关系上的自反关系,故故IA R1,IA R2,从而从而IA R1R2.由定理由定理7.9,R1R2在在A上是自反的上是自反的.由由R1和和R2的对称性的对称性,有有R1=R11和和R2=R2-1,因此因此(R1R2)-1=R1-1R2-1=R1R2(见习题见习题7.20).由定理由定理7.9,R1R2在在A上是对称的上是对称的.(2)由由R1和和R2的传递性的传递性,有有R1 R1 R1和和R2 R2 R2.由定理由定理7.4,(R1R2)(R1R2)(R1 R1)(R1 R2)(R2 R1)(R2 R2)(R1R2)(R1 R2)(R2 R1)R1R2由定理由定理7.9,R1R2在在A上是传递的上是传递的.第35页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia36 性质表示自反性反自反性对称性反对称性传递性集合表达式IA RRIA=R=R1 RR1 IAR RR关系矩阵主对角线元素全是1主对角线元素全是0矩阵是对称矩阵。若rij=1,且ij,则 rji=0.对M2中1所在的位置,M中相应的位置都是1。关系图每个顶点都有环每个顶点都没有环如果两个顶点之间有边,则必是一对方向相反的边。每对顶点之间至多有一条边,(不会有双向边)。如果顶点xi到xj有边,xj到 xk有边,则从xi到 xk也有边。三三.各种性质在关系矩阵和关系图中的体现各种性质在关系矩阵和关系图中的体现 第36页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia37例例7.14 判断图判断图7.37.3中关系的性质中关系的性质解解:(a):(a)该关系是对称的该关系是对称的.其它性质均不具备。其它性质均不具备。(b)(b)该关系是反自反的该关系是反自反的,反对称的反对称的,同时也是传递的。同时也是传递的。(c)(c)该关系是自反的该关系是自反的,反对称的反对称的,但不是传递的。但不是传递的。(a)(b)(c)321231231第37页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia38四四.各种性质与运算之间关系各种性质与运算之间关系 性质 运算 自反性反自反性对称性反对称性传递性R1R1R2R1R2R1 R2R1 R2第38页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia39一一.闭包的定义闭包的定义定定义义7.14设设R是是非非空空集集合合A上上的的关关系系,R的的自自反反闭闭包包(对对称称闭闭包包、传传递递闭闭包包)是是A上的关系上的关系R，它满足：，它满足：(1)R 是自反的是自反的(对称的、传递的对称的、传递的)；(2)R R;(3)对对A上任何包含上任何包含R的自反关系的自反关系(对称关系、传递关系对称关系、传递关系)R 都有都有R R.注注：R的自反的自反闭闭包包记为记为r(R)，对对称称闭闭包包记为记为s(R)，传递闭传递闭包包记记为为t(R)。7.5 关系的闭包关系的闭包Reflexive,Symmetric,Transtive:r(R),s(R),t(R).第39页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia40二二.闭包的构造方法闭包的构造方法定理定理7.10设设R是是A上的关系，则上的关系，则(1)r(R)=RR0;(2)s(R)=RR-1;(3)t(R)=RR2R3.证明证明：(1)由由IA=R0 RR0知，知，RR0是自反的，且是自反的，且R RR0。设设R是是A上包含上包含R的自反关系，则的自反关系，则R R,IA R,因而因而 RR0 RIA RR=R.即即RR0 R。可见。可见RR0满足自反闭包的定义，从而满足自反闭包的定义，从而r(R)=RR0.(2)略。略。第40页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia41(3)先先证证RR2 t(R),为为此此只只需需证证明明对对任任意意正正整整数数n都都有有Rn t(R)即即可。可。用归纳法。用归纳法。当当n=1时，时，R1=R t(R).假设假设Rn t(R),下证下证Rn+1 t(R)事实上，由于事实上，由于 Rn+1=Rn R t(Rn R)t(t(R)t(R)t(R)从而从而Rn+1 t(R).由归纳法完成证明。由归纳法完成证明。(因因t(R)是传递的是传递的)第41页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia42下证下证RR2是传递的。是传递的。事实上，对任意事实上，对任意,(RR2)(RR2)t(Rt)s(Rs)t s(Rt Rs)t s(Rt+s)RR2从而从而RR2是传递的。是传递的。因因t(R)是传递闭包，是传递闭包，故故t(R)RR2。由以上两方面知，由以上两方面知，t(R)RR2。第42页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia43 证证：由定理：由定理7.67.6和定理和定理7.107.10立即得证。立即得证。通过关系矩阵求闭包通过关系矩阵求闭包设关系设关系R,r(R),s(R),t(R)的关系矩阵分别为的关系矩阵分别为M,Mr,Ms,Mt,则：则：Mr=M+E,Ms=M+M,Mt=M+M2+M3+,其其中中E是是与与M同同阶阶的的单单位位矩矩阵阵。M是是M的的转转置置矩矩阵阵，矩矩阵阵元元素素相加时使用相加时使用逻辑加逻辑加。推论推论推论推论 设设设设R R R R是有限集合是有限集合是有限集合是有限集合A A A A 上的关系，则存在正整数上的关系，则存在正整数上的关系，则存在正整数上的关系，则存在正整数r r r r使得使得使得使得 t(R)=RR t(R)=RR t(R)=RR t(R)=RR2 2 2 2RRRRr r r r.第43页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia44设设关关系系R,r(R),s(R),t(R)的的关关系系图图分分别别记记为为G,Gr,Gs,Gt,则则Gr,Gs,Gt的的顶顶点集与点集与G的顶点集相同。除了的顶点集相同。除了G的边外，依下述方法添加新边：的边外，依下述方法添加新边：(1)对对G的每个顶点，如果无环，则添加一条环，由此得到的每个顶点，如果无环，则添加一条环，由此得到Gr;(2)对对G的的每每条条边边，如如果果它它是是单单向向边边，则则添添加加一一条条反反方方向向的的边边。由由此此得到得到Gs;通过关系求闭包通过关系求闭包例例7.15见教材见教材P120(3)对对G的每个顶点的每个顶点xi,找出从找出从xi 出发的所有出发的所有2步步,3步步,n步长步长的有向路的有向路(n为为G的顶点数的顶点数)。设路的终点分别为。设路的终点分别为,如如果从果从xi 到到无边，则添上这条边。如果处理完所有无边，则添上这条边。如果处理完所有顶点后得到顶点后得到GtWarshall算法求算法求t(R).第44页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia45定理定理7.11设设R是非空集合是非空集合A上的关系，则上的关系，则(1)R是自反的当且仅当是自反的当且仅当r(R)=R(2)R是对称的当且仅当是对称的当且仅当s(R)=R(3)R是传递的当且仅当是传递的当且仅当t(R)=R 证证：(1)充分性显然。下证必要性。充分性显然。下证必要性。因因R是包含了是包含了R的自反关系，故的自反关系，故r(R)R。另一方面，显然另一方面，显然R r(R).从而，从而，r(R)=R。(2),(3)略略(Def7.14).定理定理7.12设设R1和和R2是非空集合是非空集合A上的关系，且上的关系，且R1 R2,则则(1)r(R1)r(R2);(2)s(R1)s(R2);(3)t(R1)t(R2)证明略证明略三三.闭包的性质闭包的性质第45页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia46定理定理7.13设设R是非空集合是非空集合A上的关系上的关系（1）若）若R是自反的，则是自反的，则s(R)和和t(R)也是自反的。也是自反的。（2）若）若R是对称的，则是对称的，则r(R)和和t(R)也是自反的。也是自反的。（3）若）若R是传递的，则是传递的，则r(R)也是传递的。也是传递的。证明：只证证明：只证(2)。先考虑先考虑r(R).因因R是是A上的对称关系。故上的对称关系。故R=R-1,同时同时IA=IA-1,于是于是(RIA)-1=R-1IA-1(根据习题根据习题7.20).从而从而r(R)-1=(RR0)-1=(RIA)-1=R-1IA-1=RIA=r(R)。这便说明这便说明r(R)是对称的。是对称的。下面证明下面证明t(R)的对称性。为此，先用数学归纳法证明：的对称性。为此，先用数学归纳法证明：若若R是对称的，是对称的，则对任何正整数则对任何正整数n,Rn也是对称的。也是对称的。事实上，当事实上，当n=1时，时，R=R显然是对称的。显然是对称的。第46页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia47假设假设Rn是对称的，下证是对称的，下证Rn+1的对称性。由于的对称性。由于 Rn+1 Rn R t(Rn)R)t(Rn)R)R Rn Rn+1故故Rn+1是对称的。归纳法定成。是对称的。归纳法定成。现在来证现在来证t(R)的对称性。由于的对称性。由于 t(R)n(Rn)n(Rn)t(R)因此因此t(R)是对称的。是对称的。注：由于传递闭包运算和对称闭包运算不保持传递性，故在运算顺序注：由于传递闭包运算和对称闭包运算不保持传递性，故在运算顺序上它们应放在自反闭包之后，即上它们应放在自反闭包之后，即tsr(R)=t(s(r(R)。第47页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia48二元关系的闭包仍然是二元关系，还可以求它的闭包。二元关系的闭包仍然是二元关系，还可以求它的闭包。例如，例如，R是是A上的二元关系上的二元关系,r(R)是它的自反闭包，还可以是它的自反闭包，还可以求求r(R)的对称闭包。的对称闭包。r(R)的对称闭包记为的对称闭包记为s(r(R)，简记为，简记为sr(R)，读做，读做R的自反闭包的对称闭包。的自反闭包的对称闭包。类似的，类似的，R的对称闭包的自反闭包的对称闭包的自反闭包r(s(R)简记为简记为rs(R)，R的的对称闭包的传递闭包对称闭包的传递闭包t(s(R)，简记为，简记为ts(R)，通常用通常用R*表示表示R的传递闭包的自反闭包的传递闭包的自反闭包rt(R)，读作，读作“R星星”。在研究形式语言和计算模型时经常使用在研究形式语言和计算模型时经常使用R*。第48页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia497.6 等价关系与划分例例7.16设设A=1,2,8,定义定义A上的关系上的关系R如下：如下：验证验证R是是A上的等价关系。上的等价关系。一一.等价关系等价关系 定定义义7.15 设设R为为非非空空集集合合A上上的的关关系系。如如果果R是是自自反反的的,对对称称的的和和传传递递的的，则称则称R为为A上的等价关系。上的等价关系。对等价关系对等价关系R，若，若 R,则称则称x 等价于等价于y，记为，记为x y or xRy.解解：x A,有有,故故R是自反的。是自反的。x,y A,若若,则则,故故R是对称的。是对称的。x,y,z A,若若,则则故故R是传递的。是传递的。R是是A上的一个等价关系。上的一个等价关系。第49页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia50定义定义7.16设设R为非空集合为非空集合A上的等价关系，上的等价关系，x A,令令称称 x R为为x在在R下的等价类下的等价类(简称为简称为x的等价类的等价类)，有时简记为，有时简记为 x。x 称为该等价类的代表元。称为该等价类的代表元。注注：一个等价类是：一个等价类是A中在等价关系中在等价关系R下彼此等价的所有元素的集下彼此等价的所有元素的集合，等价类中各元素的地位是平等的，每个元素都可以作为合，等价类中各元素的地位是平等的，每个元素都可以作为其所在等价类的代表元。其所在等价类的代表元。例如例如，在上例中的等价关系，在上例中的等价关系R下，下，A中元素形成了三个等价类：中元素形成了三个等价类：1=4=7=1,4,7；2=5=8=2,5,8;3=6=3,6.二二.等价类等价类第50页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia51定理定理7.147.14 设设R为非空集合为非空集合A上的等价关系，则上的等价关系，则（1）x A,x 是是A的非空子集。的非空子集。（2）x,y A，如果，如果xRy,则则 x=y（3）x,y A，如果，如果x与与y不具有关系不具有关系R,则则 x 与与 y 不相交。不相交。（4）证证：(1)显然。显然。(2)zx R R（R是对称的）是对称的）R R R Rzy,从而从而 x y 同理可得，同理可得，y x.故故 x=y 三三.等价类的性质等价类的性质第51页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia52(3)(3)反证法。反证法。假设假设 x y，则存在，则存在zx y.因而因而z x 且且z y，即，即 R R.根据根据R的对称性和传递性，必有的对称性和传递性，必有 R。这与前提条件矛盾。这与前提条件矛盾。故原命题成立。故原命题成立。(4)先证先证再证再证因此因此第52页，此课件共64页哦4/11/2023 5:19 PM Discrete Math.,huang liujia53定义定义7.17设设R为非空集合为非空集合A上的等价关系，以上的等价关系，以R的所有等价类作为元素，的所有等价类作为元素，形成的集合称为形成的集合称为A关于关于R的的商集商集，记为，记为A/R，即：，即：例如例如：例：例7.16中等价关系形成的商集为：中等价关系形成的商集为：A/R1,4,7,2,5,8,3,6四四.商集商集定义定义7.18设设A为非空集合，若为非空集合，若A
