第二章关系 [兼容模式].pdf

《第二章关系 [兼容模式].pdf》由会员分享，可在线阅读，更多相关《第二章关系 [兼容模式].pdf（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章关系关系第二章第二章关系关系在上一章讨论了集合及集合的运算，在这一章在上一章讨论了集合及集合的运算，在这一章中我们将要研究中我们将要研究集合内元素间的关系集合内元素间的关系，这就是这就是中我们将要研究中我们将要研究集合内元素间的关系集合内元素间的关系，这就是这就是“关系”。关系是一个很重要的数学基本概念，“关系”。关系是一个很重要的数学基本概念，它在计算机科学中的许多方面如数据结构、数它在计算机科学中的许多方面如数据结构、数据库据库、情报检索情报检索、算法分析等都有很多应用算法分析等都有很多应用。据库据库、情报检索情报检索、算法分析等都有很多应用算法分析等都有很多应用。本章主要讨论

2、本章主要讨论二元关系二元关系理论。理论。第二章第二章关系关系第二章第二章关系关系主要内容：主要内容：关系的概念关系的概念关系的概念关系的概念关系的运算关系的运算关系的运算关系的运算关系的性质关系的性质关系的性质关系的性质关系的闭包运算关系的闭包运算引言引言引言引言关系是一个非常普遍的概念，如数值的大关系是一个非常普遍的概念，如数值的大于关系于关系、整除关系整除关系，人类的父子关系人类的父子关系、师师于关系于关系、整除关系整除关系，人类的父子关系人类的父子关系、师师生关系、同学关系等。生关系、同学关系等。如令如令=1,2,3,4,A中元素间的中元素间的关系关系R：R=(1,1),(1,2),(1

3、,3),(1,4),(2,2),(2,3),(2 4)(3 3)(3 4)(4 4)AA(2,4),(3,3),(3,4),(4,4)AA基本概念基本概念基本概念基本概念 二元关系:二元关系:设A，B是两个集合，R是笛卡儿积设A，B是两个集合，R是笛卡儿积AB的AB的任一子集任一子集，则称R为从A到B的一个二元，则称R为从A到B的一个二元关系关系，简称关系简称关系。特别当特别当A=BA=B时时，则称则称R R为为A A上上关系关系，简称关系简称关系。特别当特别当A=BA=B时时，则称则称R R为为A A上上的二元关系（或A上的关系）。的二元关系（或A上的关系）。记法：(x,y)记法：(x,y)

4、R,xRy 称之为x与y有关系。R,xRy 称之为x与y有关系。(x,y)R 称之为x与y没有关系(x,y)R 称之为x与y没有关系。基本概念基本概念基本概念基本概念设R是二元关系，由(x,y)R的设R是二元关系，由(x,y)R的所有x所有x组成组成的集称为的集称为R R的定义域的定义域，记作记作D(R)D(R)。的集称为的集称为R R的定义域的定义域，记作记作D(R)D(R)。由(x,y)R的由(x,y)R的所有y所有y组成的集合称为R的值域，组成的集合称为R的值域，记作C(R)记作C(R)例例1 设设A bdB 1 2 3例例1 设设A=a,b,c,d,e，B=1,2,3，R=(a,2),

5、(b,3),(c,2)，求，求R的定义域和值的定义域和值域解域解 D(R)=a，b，c，C(R)=2，3。基本概念基本概念基本概念基本概念例例2 设设A=1,3,5,7，R是是A上的二元关系，上的二元关系，当当，且且时时，求求 和它的和它的当当a，b A且且ab时时，(a,b)R，求求R和它的和它的定义域和值域定义域和值域。定义域和值域定义域和值域。解解 R=(1 3)(1 5)(1 7)(3 5)(3 7)(5 7)解解 R=(1,3),(1,5),(1,7),(3,5),(3,7),(5,7)D(R)=1 3 5，C(R)=3 5 7。D(R)1,3,5，C(R)3,5,7。关系的表示方法

6、关系的表示方法关系的表示方法关系的表示方法1.1.枚举法枚举法:1.1.枚举法枚举法:即将关系中所有序偶一一列举出，如前的即将关系中所有序偶一一列举出，如前的R=(1,1),(1,2),(1,3),(1,4),(2,2),(2 3)(2 4)(3 3)(3 4)(4 4)(2,3),(2,4),(3,3),(3,4),(4,4)。2.描述法：。2.描述法：即用语言描述序偶的第一元素与第二元素间即用语言描述序偶的第一元素与第二元素间的关系的关系。例如例如的关系的关系。例如例如R=(x,y)|xy关系的表示方法关系的表示方法关系的表示方法关系的表示方法3.3.有向图法有向图法：3.3.有向图法有向

7、图法：R R A AB,B,用两组小圆圈用两组小圆圈(称为结点称为结点)分别分别R R A AB,B,用两组小圆圈用两组小圆圈(称为结点称为结点)分别分别表示A和B的元素，当(x,y)R时，从x到y引表示A和B的元素，当(x,y)R时，从x到y引一条有向弧一条有向弧(边边)。这样得到的图形称为这样得到的图形称为R R的的一条有向弧一条有向弧(边边)。这样得到的图形称为这样得到的图形称为R R的的关系图。关系图。例例 设设A 1 2 3 4 B bRAB例例 设设A=1,2,3,4,B=a,b,c，R3 AB，R3=(1,a),(1,c),(2,b),(3,a),(4,c)AB3(,),(,),

8、(,),(,),(,)则则R 的关系图为的关系图为：1。2。ab则则R3的关系图为的关系图为：3。4。c关系的表示方法关系的表示方法关系的表示方法关系的表示方法例 设例 设A=1,2,3,4,R4 AA，R(1 1)(1 4)(2 3)(3 1)(3 4)(4 1)(4 2)R4=(1,1),(1,4),(2,3),(3,1),(3,4),(4,1),(4,2)12则R则R4 4的关系图为：的关系图为：1。4。23R4:4 44。3关系的表示方法关系的表示方法关系的表示方法关系的表示方法4.矩阵表示法4.矩阵表示法：有限集合之间的关系也可以用矩阵来表示，有限集合之间的关系也可以用矩阵来表示，这

9、种表示法便于用计算机来处理关系。设，是个有A=a1,a2,am，B=b1,b2,bn是个有限 集,RAB，定 义 R 的 mn 阶 矩 阵限 集,，定 义的阶 矩 阵MR=(rij)mn，其中rij=1 若(ai,bj)R0 若(ai,bj)R(1im,1jn)关系的表示方法关系的表示方法关系的表示方法关系的表示方法R3=(1,a),(1,c),(2,b),(3,a),(4,c)R4=(1,1),(1,4),(2,3),(3,1),(3,4),(4,1),(4,2)R4(1,1),(1,4),(2,3),(3,1),(3,4),(4,1),(4,2)1 0 11a b c上例中 MR3=，0

10、1 01 0 00 0 1432341 0 0 10 0 1 011 2 3 4MR4=0 0 1 01 1 0 01 0 0 144234三个特殊关系三个特殊关系三个特殊关系三个特殊关系1.1.空关系空关系1.1.空关系空关系因为因为 A AB B，(或或 A AA)A)，所以所以也是也是因为因为 A AB B，(或或 A AA)A)，所以所以也是也是一个从A到B(或A上)的关系，称之为空关系。一个从A到B(或A上)的关系，称之为空关系。即即无任何元素的关系无任何元素的关系，它的关系图中只有结它的关系图中只有结即即无任何元素的关系无任何元素的关系，它的关系图中只有结它的关系图中只有结点,无任

11、何边；它的矩阵中全是0。点,无任何边；它的矩阵中全是0。2.2.完全关系完全关系(全域关系全域关系)2.2.完全关系完全关系(全域关系全域关系)A AB(B(或或A AA)A)本身也是一个从本身也是一个从A A到到B(B(或或A A上上)A AB(B(或或A AA)A)本身也是一个从本身也是一个从A A到到B(B(或或A A上上)的关系，称之为完全关系。即含有 的关系，称之为完全关系。即含有全部序偶全部序偶的关系的关系。它的矩阵中全是它的矩阵中全是1 1。的关系的关系。它的矩阵中全是它的矩阵中全是1 1。三个特殊关系三个特殊关系三个特殊关系三个特殊关系3.3.A上的上的恒等关系恒等关系I：3.

12、3.A上的上的恒等关系恒等关系IA：IA AA，且，且IA=(x,x)|xA称为称为A上的恒等关系。上的恒等关系。例如A=1,2,3,则IA=(1,1),(2,2),(3,3)A上的、完全关系及IA的关系图及矩阵如下：A上的、完全关系及IA的关系图及矩阵如下：1。1。1。2。32。31。2。3M=1 0 00 1 01 1 11 1 10 0 00 0 0M=MAA=AAIAMIA=0 0 1331 1 1330 0 033关系的集合运算关系的集合运算关系的集合运算关系的集合运算由于关系就是集合由于关系就是集合，所以集合的所以集合的 和和运运由于关系就是集合由于关系就是集合，所以集合的所以集合

13、的,-和和运运算对关系也适用。算对关系也适用。例如：例如：X=a,b,c,Y=1,2,且有从且有从X到到Y的关系的关系R=(a 1)(b 2)(c 1)R=(a,1),(b,2),(c,1)S=(a,1),(b,1),(c,1)则有则有RS=(a,1),(b,1),(b,2),(c,1)，RS=(a 1)(c 1)，RS=(a,1),(c,1)，R=(a,2),(b,1),(c,2),()()()R-S=(b,2)关系的集合运算关系的集合运算关系的集合运算关系的集合运算例 设例 设X=1，2，3，4，5，若，若A=(x,y)|x与与y的差的差能被能被 整除整除，与与 的差为正且能被的差为正且能

14、被能被能被2整除整除，B=|x与与y的差为正且能被的差为正且能被3整除整除，整除整除，求求AB，AB，A-B，B-A，A。解解:A(1 1)(1 3)(1 5)(2 2)(2 4)(3 1)(3 3)(3 5)(4 2)A=(1,1),(1,3),(1,5),(2,2),(2,4),(3,1),(3,3),(3,5),(4,2),(4,4),(5,1),(5,3),(5,5)B=(4,1)，(5,2)解A=，B=，AB=，AB=A-B=，=A3，=AB-A=，=BA=1，2，3，4，51，2，3，4，5-，=，关系的运算关系的运算关系的运算关系的运算除了可进行集合并除了可进行集合并、交交、补等

15、运算外补等运算外，还可以还可以除了可进行集合并除了可进行集合并、交交、补等运算外补等运算外，还可以还可以进行一些新的运算，先介绍由两个关系生成一进行一些新的运算，先介绍由两个关系生成一种新的关系种新的关系，即关系的复合运算即关系的复合运算。1.1.定义定义:设是R是从X到Y的关系，S是从Y到Z的关系，种新的关系种新的关系，即关系的复合运算即关系的复合运算。1.1.定义定义:设是R是从X到Y的关系，S是从Y到Z的关系，则R和S的复合关系记作R?S。定义为：R?S=(x,z)|xX,zZ,yY,(x,y)R,(y,z)S显然，R?S 是从X到Z的关系。显然，R?S 是从X到Z的关系。关系的运算关系

16、的运算关系的运算关系的运算2.2.复合关系的计算方法复合关系的计算方法2.2.复合关系的计算方法复合关系的计算方法A=1,2,3，B=1,2,3,4，C=1,2,3,4,5,R AB，S BC枚举法枚举法枚举法枚举法R=(1,2),(2,3),(2,4),(3,1)R(1,2),(2,3),(2,4),(3,1)S=(1,2),(2,1),(2,3),(3,4),(4,2),(4,5)则则R?S=(1,1),(1,3),(2,4),(2,2),(2,5),(3,2)R S(1,1),(1,3),(2,4),(2,2),(2,5),(3,2)S?R=(1,3),(1,4),(2,2),(2,1)

17、,(4,3),(4,4)关系的运算关系的运算关系的运算关系的运算有向图法有向图法有向图法有向图法R=(1,2),(2,3),(2,4),(3,1)S=(1,2),(2,1),(2,3),(3,4),(4,2),(4,5)RSSR。C11。2A1。2A。B12RS。C1SR?。232。3。2。3。234。23。4。45。45则R?S=(1,1),(1,3),(2,4),(2,2),(2,5),(3,2)关系的运算关系的运算关系的运算关系的运算关系矩阵法关系矩阵法R=(1 2)(2 3)(2 4)(3 1)关系矩阵法关系矩阵法R=(1,2),(2,3),(2,4),(3,1)S=(1,2),(2,

18、1),(2,3),(3,4),(4,2),(4,5)MMMR=,MS=MR?S=MR MS=关系的运算关系的运算关系的运算关系的运算谓词公式法谓词公式法设I是实数集合，R和S都是I上的关系，定义设I是实数集合，R和S都是I上的关系，定义如下：R=(x,y)|y=x2+3xS=(x,y)|y=2x+3RSxx2+3x2(x2+3x)+3 =2x2+6x+3RS所以 R?S=(x y)|y=2x2+6x+3所以 R?S(x,y)|y 2x+6x+3关系的运算关系的运算关系的运算关系的运算关系的运算的性质关系的运算的性质关系复合运算关系复合运算不满足交换律不满足交换律，但是，但是满足结满足结合律合律

19、:RAB,SBC,TCD,则()()S T(R?S)?T=R?(S?T)=R?S?T所以可将关系的幂定义如下：所以可将关系的幂定义如下：设一个集合X上的关系R，则Rn可定义为:(1)R1=R;(2)Rn+1RnR(2)Rn+1=Rn?R.关系的运算关系的运算关系的运算关系的运算证明(R S)TR(S T)证明:(R?S)?T=R?(S?T)首先证(R?S)?T R?(S?T)()()(x,u)(R?S)?T z,(x,z)RS(z,u)Ty(x y)R(y z)S(z u)Ty,(x,y)R(y,z)S(z,u)T(x,y)R z,(y,z)S(z,u)T y,(x,y)R (y,u)S T(

20、x,u)R?(S?T)(x,u)R(S T)同理可证:R?(S?T)(R?S)?T 则(R S)TR(S T)则:(R?S)?T=R?(S?T)关系的运算关系的运算关系的运算关系的运算逆关系(反关系)也是我们经常遇到的概念例如与就是互为逆关系。例如与就是互为逆关系。1.定义:R是从A到B的关系，如果将R中的所有如果将R中的所有序偶的两个元素的位置互换序偶的两个元素的位置互换，得到一个从B到A的关系，称之为R的逆关系，记作R。A的关系，称之为R的逆关系，记作R。R=(y,x)|(x,y)R(y,x)R(x,y)R关系的运算关系的运算关系的运算关系的运算2.计算方法R=(1 2)(2 3)(3 4

21、)(4 5)R=(1,2),(2,3),(3,4),(4,5)R=(2,1),(3,2),(4,3),(5,4)R的有向图是将R的有向图的所有边的方向所有边的方向颠倒一下即可颠倒一下即可 R的矩阵 MR=(MR)T 即为R颠倒一下即可颠倒一下即可,R的矩阵 MR(MR)即为R矩阵的转置。如1 0 1 01 0 11 0 1 00 0 0 11 0 1 1MR=340 0 01 0 10 1 1MR=1 0 10 1 143关系的运算关系的运算关系的运算关系的运算逆关系的性质：逆关系的性质：设R，S分别是从X到Y及Y到Z的关系，则有设R，S分别是从X到Y及Y到Z的关系，则有(1)R=R(1)R

22、R(2)(R?S)=S?R(2)(R?S)S?R证明（RS）1RS y（yYRS）y（yYS1R1）S 1 R 1 S1R1。所以，（RS）1=S1R1。关系的重要性质关系的重要性质关系的重要性质关系的重要性质本节将研究关系的一些性质，它们在关系的研究中起着重要的作用。研究中起着重要的作用。这是本章最重要的一节这是本章最重要的一节。本节中所讨论的关系都是集合A中的关系。本节中所讨论的关系都是集合A中的关系。关系的性质主要有：自反性、反自反性、自反性、反自反性、对称性、反对称性、传递性。对称性、反对称性、传递性。关系的重要性质关系的重要性质关系的重要性质关系的重要性质1.自反性1.自反性定义定义

23、:设R是集合上的关系，如果对于任意任意定义定义:设R是集合上的关系，如果对于任意任意xA都有(x,x)R(xRx)，则称R是A中自反关系。即关系。即R是A中自反的 x(xA)xRx例如在实数集合中,“”是自反关系，因为，对任意实数x，有x x.对任意实数x，有x x.从关系有向图看自反性:每个结点都有环。从关系有向图看自反性:每个结点都有环。从关系矩阵看自反性：主对角线都为1从关系矩阵看自反性：主对角线都为1。关系的重要性质关系的重要性质关系的重要性质关系的重要性质令A 1 2 3给定A上八个关系找自反关系找自反关系令A=1,2,3给定A上八个关系，找自反关系找自反关系1。1。1。1。2。2。

24、2。2。3333R2R1R3R41。1。1。1。21342。2。2。2。3333RRRRR5R6R7R8R1、R3、R4关系的重要性质关系的重要性质关系的重要性质关系的重要性质2.2.反自反性反自反性2.2.反自反性反自反性定义定义：设R是集合A中的关系，如果对于任意任意定义定义：设R是集合A中的关系，如果对于任意任意的xA,都有(x,x)R的xA,都有(x,x)R,则称R为A中的反自反关系。即关系。即R是A中反自反的x(xA(x,x)R)从关系有向图看反自反性:每个结点都无环。从关系矩阵看反自反性：主对角线都为0。从关系矩阵看反自反性：主对角线都为0。注意注意：一个关系如果不具有自反性，不一

25、定具有反自反性。具有反自反性。关系的重要性质关系的重要性质关系的重要性质关系的重要性质找反自反关系找反自反关系找反自反关系找反自反关系1。1。1。1。2。2。2。2。3333R2R1R3R41。1。1。1。2。2。2。2。3333R5R6R7R85R6R7R8R2、R5、R8关系的重要性质关系的重要性质关系的重要性质关系的重要性质例例 设设A=1,2,3A=1,2,3，R1R1，R2R2，R3R3是是A A上的关系上的关系，其中其中 例例 设设A=1,2,3A=1,2,3，R1R1，R2R2，R3R3是是A A上的关系上的关系，其中其中 R1,R1,R2R2,R2R2,R3R3说明R1，R2和

26、R3是否为A上的自反关系和反自反关系。说明R1，R2和R3是否为A上的自反关系和反自反关系。解答解答R1既不是自反的也不是反自反的，R1既不是自反的也不是反自反的，R2是自反的，R2是自反的，R3R3是反自反的是反自反的。R3R3是反自反的是反自反的。关系的重要性质关系的重要性质关系的重要性质关系的重要性质3.对称性3.对称性定义:R是集合A上的关系,若对任何任何x,x,yA,yA,如如定义:R是集合A上的关系,若对任何任何x,x,yA,yA,如如果有xRy,必有yRx果有xRy,必有yRx,则称R为A中的对称关系。R是A上对称的xRyyRx(xA,yA)从关系有向图看对称性:在两个不同的结点

27、从关系有向图看对称性:在两个不同的结点之间，若有边的话，则有方向相反的两条边。从关系矩阵看对称性：矩阵关于主对角线对称。从关系矩阵看对称性：矩阵关于主对角线对称。关系的重要性质关系的重要性质关系的重要性质关系的重要性质找对称关系找对称关系1。1。1。1。2。2。2。2。3333R2R1R3R41。1。1。1。2。2。2。2。3333R5R6R7R85R6R7R8R3、R4、R6、R8关系的重要性质关系的重要性质关系的重要性质关系的重要性质4.反对称性定义定义:设R为集合A中关系,若对任何对任何x,x,yA,yA,如如定义定义:设R为集合A中关系,若对任何对任何x,x,yA,yA,如如果有xRy

28、,且x果有xRy,且x y必有yRxy必有yRx,则称R为A中反对称关系。关系。由R的关系图看反对称性：两个不同的结点由R的关系图看反对称性：两个不同的结点之间最多最多有一边。从关系矩阵看反对称性：以主对角线为对称从关系矩阵看反对称性：以主对角线为对称的两个元素中最多有一个1。关系的重要性质关系的重要性质关系的重要性质关系的重要性质1。1。1。1。2。2。2。2。3333R2R1R3R41。1。1。1。2。2。2。2。3333R5R6R7R85R6R7R8R1、R2、R4、R5,R8,空关系和恒等关系既是对称也是反对称的。空关系和恒等关系既是对称也是反对称的。例例 设A1,2,3，R1，R2，

29、R3和R4都是A上的关系，其中R1,设A1,2,3，R1，R2，R3和R4都是A上的关系，其中R1,R2,R2,R3R3,R3R3,R4,R4,说明R1，R2，R3和R4是否为A上对称和反对称的关系。说明R1，R2，R3和R4是否为A上对称和反对称的关系。解答解答R1R1既是对称也是反对称的既是对称也是反对称的。解答解答R1R1既是对称也是反对称的既是对称也是反对称的。R2是对称的但不是反对称的。R2是对称的但不是反对称的。R3是反对称的但不是对称的。R3是反对称的但不是对称的。R4R4既不是对称的也不是反对称的既不是对称的也不是反对称的。R4R4既不是对称的也不是反对称的既不是对称的也不是反

30、对称的。关系的重要性质关系的重要性质关系的重要性质关系的重要性质5.传递性5.传递性定义定义:R是A中关系，对任何任何x,x,y,zA,y,zA,如果有如果有定义定义:R是A中关系，对任何任何x,x,y,zA,y,zA,如果有如果有xRy,和yRz,则有xRzxRy,和yRz,则有xRz,则称R为A中传递关系。即R在A上传递即R在A上传递xyz(xAyAzAxRyyRz)xRz)xyz(xAyAzAxRyyRz)xRz)实数集中的、(，集合、是传递的。关系的重要性质关系的重要性质关系的重要性质关系的重要性质从关系关系图和关系矩阵中不易看清是否有传递性。从关系关系图和关系矩阵中不易看清是否有传递

31、性。有时，必须直接根据传递的定义来检查。1。1。1。1。2。2。2。2。3333R2R1R3R41。1。1。1。2。2。2。2。3333R5R6R7R8R1、R3、R4、R5、R8例例 设A1,2,3，R1，R2，R3是A上的关系，其中设A1,2,3，R1，R2，R3是A上的关系，其中R1R1,R1R1,R2,R2,R3R3说明R1，R2和R3是否为A上的传递关系。说明R1，R2和R3是否为A上的传递关系。解答解答R1R1和和R3R3是是A A上的传递关系上的传递关系，R1R1和和R3R3是是A A上的传递关系上的传递关系，R2不是A上的传递关系。R2不是A上的传递关系。关系的重要性质关系的重

32、要性质关系的重要性质关系的重要性质定理定理设R为A上的关系，则设R为A上的关系，则（1 1）R R在在A A上自反当且仅当上自反当且仅当 I IA A R R（1 1）R R在在A A上自反当且仅当上自反当且仅当 I IA A R R（2）R在A上反自反当且仅当 RI（2）R在A上反自反当且仅当 RIA A（3）R在A上对称当且仅当 RR（3）R在A上对称当且仅当 RR-1-1（4 4）R R在在A A上反对称当且仅当上反对称当且仅当 RRRR-1 1 I IA A（4 4）R R在在A A上反对称当且仅当上反对称当且仅当 RRRR-1 1 I IA A（5）R在A上传递当且仅当 RRR（5）

33、R在A上传递当且仅当 RRR 自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性集合表达式I集合表达式IA A RRI RRIA ARRRR-1-1RRRR-1-1 I IA ARRRRRR关系矩阵关系矩阵主对角线主对角线主对角线主对角线矩阵是对矩阵是对若若r rijij1 1，对对M M2 2中中1 1所所关系矩阵关系矩阵主对角线主对角线元素全是1元素全是1主对角线主对角线元素全是0 元素全是0 矩阵是对矩阵是对称矩阵称矩阵若若r rijij1 1，且ij，则r且ij，则rjiji0 0 对对M M 中中1

34、 1所所在位置，M中相应的位在位置，M中相应的位置都是置都是1 1置都是置都是1 1 关系图每个顶点都有环每个顶点都没有环如果两个顶点之间 关系图每个顶点都有环每个顶点都没有环如果两个顶点之间有边有边，一一如果两点之间有边，一如果两点之间有边，一定是一条有定是一条有如果顶点x如果顶点xi i到x到xj j有边，有边，x x 到到x x 有边有边，有边有边，一一定是一对方向相反定是一对方向相反定是一条有定是一条有向边(无双向边)向边(无双向边)x xj j到到x xk k有边有边，则从x则从xi i到x到xk k也有边也有边的边(无单边)的边(无单边)关系的闭包关系的闭包关系的闭包关系的闭包 闭

35、包（closure）的定义闭包（closure）的定义 闭包的构造方法闭包的构造方法 闭包的构造方法闭包的构造方法 闭包的性质闭包的性质 闭包的相互关系闭包的相互关系关系上的闭包关系上的闭包关系上的闭包关系上的闭包给定给定A A中关系中关系R,R,若若A A上另一个关系上另一个关系R R,满足满足：给定给定A A中关系中关系R,R,若若A A上另一个关系上另一个关系R R,满足满足：RRRR；R R是自反的是自反的(对称的、传递的)；(对称的、传递的)；R R是是“最小的最小的”，即对于任何即对于任何A A上自反上自反R R 是是“最小的最小的”，即对于任何即对于任何A A上自反上自反(对称、

36、传递)的关系R(对称、传递)的关系R”,且RR,且RR”,则R,则RRR”。则称则称R R是是R R的的自反自反(对称对称、传递传递)闭包闭包。则称则称R R是是R R的的自反自反(对称对称、传递传递)闭包闭包。记作记作r(R)(s(R)r(R)(s(R)、t(R)t(R)记作记作r(R)(s(R)r(R)(s(R)、t(R)t(R)关系上的闭包关系上的闭包关系上的闭包关系上的闭包定理设R为A上的关系，则有定理设R为A上的关系，则有（1 1）r(R)r(R)RIRIA A（1 1）r(R)r(R)RIRIA A（2）s(R)RR（2）s(R)RR-1-1（3）t(R)RR（3）t(R)RR2

37、2RR3 3。证明思路证明思路证明思路证明思路(1)和(2)：证明右边的集合满足闭包定义的三个条件。(1)和(2)：证明右边的集合满足闭包定义的三个条件。(3)采用集合相等的证明方法。(3)采用集合相等的证明方法。证明左边包含右边证明左边包含右边，即即t(R)t(R)包含每个包含每个RnRn。证明左边包含右边证明左边包含右边，即即t(R)t(R)包含每个包含每个RnRn。证明右边包含左边，即RR2证明右边包含左边，即RR2具有传递的性质具有传递的性质（1）r(R)RI I（1）r(R)RI IA A证明证明 RRI IA A R R证明证明 RRI IA A R R I IA A RI RIA

38、 A，可知r(R)是自反的，可知r(R)是自反的 设R是A上包含R的自反关系，则有R R且I设R是A上包含R的自反关系，则有R R且IA A R R任取任取(x,y),(x,y),(x,y)(x,y)r(R)r(R)=RI=RI任取任取(x,y),(x,y),(x,y)(x,y)r(R)r(R)=RI=RIA A 若 x=y,(x,y)I若 x=y,(x,y)IA A R,(x,y)R R,(x,y)R若若x xy,(x,y)y,(x,y)R R R R,(x,y),(x,y)R R若若x xy,y,(x,y)(x,y)R R R R,(x,y),(x,y)R R所以 r(R)=RI所以 r(

39、R)=RIA A R R综上所述，r(R)R综上所述，r(R)RIA。(2)s(R)RR-1(2)s(R)RR1 R R RRRR-1-1设设R是包含是包含R的对称关系，的对称关系，证明证明证明证明RRRR-1-1是对称的是对称的，R R RRRR。R R任取任取()，有有证明证明是对称的是对称的，任取(x,y)，有任取(x,y)，有任取任取(x,y)，有有(x,y)RR-1(x,y)RR(x,y)RR-1-1(x,y)R或(x,y)R(x,y)R或(x,y)R-1-1(x,y)R或或(x,y)R-1(x y)R 则则(x y)R(y,x)R(y,x)R-1-1或R或R()RR()RR-1 1

40、(x,y)R,则则(x,y)R(x,y)R-1(y,x)R R(y,xy,x)RR)RR1 1所以 RR所以 RR-1-1 是对称。是对称。(y,x)R R所以所以 RR-1 R。所以所以 RR R。(3)t(R)RR2R3(3)t(R)RR2R3 先证先证()()成立成立为此只需证明对任意的为此只需证明对任意的证明证明先证先证RR2RR2 t t(R R)成立成立，为此为此只只需证明对任意的需证明对任意的正整数n有 R正整数n有 Rn n t(R)即可。用归纳法。t(R)即可。用归纳法。n1时，有 Rn1时，有 R1 1R t(R)。R t(R)。假设假设R Rn n t t(R R)成成立

41、立，那么对任意的那么对任意的x 有有假设假设 ()()成成，那么对任意的那么对任意的,y,y 有有(x,y)R(x,y)Rn+1n+1RRn n R R()()且且()()t t(x,tx,t)RRn n且且(t,yt,y)RR)t(t(R)t(R)t(t(R)t(R)t(R)（因为t(R)是传递的）t(R)（因为t(R)是传递的）这就证明了这就证明了R Rn+1n+1t(R)t(R)这就证明了这就证明了R Rn+1n+1 t(R)t(R)。由归纳法命题得证。由归纳法命题得证。(3)t(R)RR2R3(3)t(R)RR2R3再证再证t t(R R)R RR R2 2成立成立，为此只须证明为此只

42、须证明R RR R2 2是传是传证明证明再证再证()()成立成立，为此只须证明为此只须证明 是传是传递的。递的。任取任取(x y)(y z)(x y)(y z)t(R)则则任取任取(x(x,y)y),(y(y,z)z)t(R),则则(x,y)RR(x,y)RR2 2 且(y,z)RR且(y,z)RR2 2 t(x,y)Rt(x,y)Rt t)且 s(y,z)R)且 s(y,z)Rs s)t t s s(x x,y),y)RRt t且且(y,(y,z z)RRs s)(,y)(,y)且且(y,)(y,)ts(x,z)R ts(x,z)Rt t R Rs s)()()t t s s(x,zx,z)

43、RRt+st+s)(x,z)RR(x,z)RR2 2从而证明了RR从而证明了RR2 2是传递的。是传递的。关系上的闭包关系上的闭包关系上的闭包关系上的闭包推论推论 设设 为有限集合为有限集合 上的关系上的关系 且且推论推论:设设R为有限集合为有限集合A上的关系上的关系,且且|A|=nt(R)=RR2Rnt(R)RR R性质性质:R是是A上关系，则上关系，则 R是自反的是自反的，则则s(R)和和t(R)也自反也自反。R是自反的是自反的，则则s(R)和和t(R)也自反也自反。R是对称的，则是对称的，则r(R)和和t(R)也对称。也对称。R是传递的，则是传递的，则r(R)也传递。也传递。通过关系矩阵

44、求闭包的方法通过关系矩阵求闭包的方法通过关系矩阵求闭包的方法通过关系矩阵求闭包的方法设关系设关系R，r(R)，s(R)，t(R)的关系矩阵分别的关系矩阵分别设关系设关系，()，()，()的关系矩阵分别的关系矩阵分别为为M，Mr，Ms和和Mt，则，则M ME对角线上的值都改为对角线上的值都改为1Mr ME对角线上的值都改为对角线上的值都改为1Ms MMT若若aij1，则令，则令aji1jjMt MM2M3沃舍尔算法沃舍尔算法其中其中E是和是和M同阶的单位矩阵同阶的单位矩阵，MT是是M的转置的转置其中其中E是和是和M同阶的单位矩阵同阶的单位矩阵，M 是是M的转置的转置矩阵。矩阵。注意在上述等式中矩

45、阵的元素注意在上述等式中矩阵的元素相加时使用逻辑相加时使用逻辑注意在上述等式中矩阵的元素注意在上述等式中矩阵的元素相加时使用逻辑相加时使用逻辑加加。(1+0)=1 (0+1)=1 (1+1)=1 (0+0)=0 加加。()()()()通过关系图求闭包的方法通过关系图求闭包的方法通过关系图求闭包的方法通过关系图求闭包的方法设关系设关系R，(R)，(R)，(R)的关系图分别记为的关系图分别记为G，G，G，G，设关系设关系R，r(R)，s(R)，t(R)的关系图分别记为的关系图分别记为G，Gr，Gs，Gt，则则Gr，Gs，Gt的的顶点集与顶点集与G的顶点集相等的顶点集相等。除了除了G的边以外的边以外

46、，以下述方法添加新的边以下述方法添加新的边。除了除了 的边以外的边以外，以下述方法添加新的边以下述方法添加新的边。1.考察考察G的每个顶点，如果的每个顶点，如果没有环就加上一个环没有环就加上一个环。最终得到的是。最终得到的是Gr。2.考察考察G的每一条边，如果有一条的每一条边，如果有一条xi到到xj的单向边，的单向边，ij，则在，则在G中中加一条边加一条边 j到到 i的反方向边的反方向边。最终得到最终得到G。加一条边加一条边xj到到xi的反方向边的反方向边。最终得到最终得到Gs。3.考察考察G的每个顶点的每个顶点xi，找出从，找出从xi出发的所有出发的所有2步，步，3步，步，n步长步长的路径的

47、路径（n为为G中的顶点数中的顶点数）。）。的路径的路径（为为 中的顶点数中的顶点数）。）。设路径的终点为。如果没有从设路径的终点为。如果没有从xi到到(l=1,2,k)的边，就加上这条边。当检查完所有的边，就加上这条边。当检查完所有的顶点后就得到图的顶点后就得到图Gt。k21k21jjjjjjx,x,xx,x,x?I Ij jx x的顶点后就得到图的顶点后就得到图Gt。关系上的闭包运算举例关系上的闭包运算举例关系上的闭包运算举例关系上的闭包运算举例A=1,2,3 AA=1,2,3 A中关系中关系R R1 1,R,R2 2,如下如下：A=1,2,3A=1,2,3 A A中关系中关系R R1 1,

48、R,R2 2,如下如下：R R1 1=(1,2),(1.3),(3,2)=(1,2),(1.3),(3,2)R R=(1,2),(2.3),(3,1)=(1,2),(2.3),(3,1)R R2 2=(1,2),(2.3),(3,1)=(1,2),(2.3),(3,1)求r(R)，s(R)，t(R)r(R)，s(R)，t(R)等价关系等价关系(equivalent relation)等价关系等价关系(equivalent relation)等价关系是很重要的关系，它是我们遇到最等价关系是很重要的关系，它是我们遇到最多的关系多的关系，例如例如，数值相等关系数值相等关系=、命题间的命题间的多的关系

49、多的关系，例如例如，数值相等关系数值相等关系=、命题间的命题间的等价关系等价关系、三角形相似三角形相似和全等关系和全等关系等价关系等价关系、三角形相似三角形相似和全等关系和全等关系，.等价关系等价关系等价关系等价关系定义定义:设设R R是是A A上关系上关系,若若R R是是自反的自反的、对称的对称的定义定义:设设R R是是A A上关系上关系,若若R R是是自反的自反的、对称的对称的和传递的和传递的，则称R是A中的等价关系。，则称R是A中的等价关系。设设R是一个等价关系，若是一个等价关系，若(x,y)R，称，称x等等价于价于y，记做记做xy。价于价于y，记做记做xy。等价关系等价关系自反性对称性

50、传递性自反性对称性传递性等价关系等价关系例设集合A=a，b，c，d，I IA A RRR RRR-1-1RRRRRR 例设集合A=a，b，c，d，R=，。(1)R是自反的当且仅当是自反的当且仅当(R)R。，。验证R是A上的等价关系。(1)R是自反的当且仅当是自反的当且仅当r(R)R。（2）R是对称的当且仅当是对称的当且仅当s(R)R。（3）R是传递的当且仅当是传递的当且仅当t(R)R。1001证明写出R的关系矩阵证明写出R的关系矩阵（3）R是传递的当且仅当是传递的当且仅当t(R)R。011001101001等价关系等价关系等价关系等价关系例：集合A=1,2,3,4,5,6,7,关系R是A上的模