第六节-关系的性质-定义设R是X上的二元关系-如果

第六节关系的性质

定义6.1设R是X上的二元关系,如果对每个x

X,都有xRx,则称R在X上是自反的。

即R在X上自反的

(

x)(x

X

xRx);

例如,实数集的“

”关系是自反的。

定义6.2设R是X上的二元关系,如果对每个x,y

X,当xRy,就有yRx,则称R在X上是对称的。

即R在X上是对称的

(

x)(

y)(x

X

y

X

xRy

yRx);例如,三角形的相似关系是对称的;直线的平行关系是对称的;居民的邻居关系是对称的。

例1.设A={2,3,5,7},R={<x,y>|(x-y)

2是整数},

验证R在A上是自反的和对称的。

证明:1)对于任意的xA,因为(x-x)

2=0,

即<x,x>R,故R是自反的；

2)对于任意的x,yA,

如果<x,y>R,即(x-y)

2是整数,

则(y-x)

2也是整数,即<y,x>R,

故R是对称的#

定义6.3设R是X上的二元关系,如果对每个x,

y,z

X,当xRy且yRz就有xRz,则称R在X上是可传递的。

R在X上是可传递的

(

x)(

y)(

z)(x

X

y

X

z

X

xRy

yRz

xRz);

例如,实数集的关系“<”,“

”,“=”都是可传递的。

例2.设A={1,2,3,4},A上的关系

R1={<1,2>,<2,3>,<1,3>,<3,4>,<1,4>}(不可传递)

R2={<1,1>,<1,2>,<2,2>,<3,4>}(可传递)

R3={<1,2>,<3,4>}(可传递)

R4={<1,2>}(可传递)

例3.设X={1,2,3},R3={<1,2>,<2,3>,<1,3>,

<2,1>}不是X上的可传递关系,这是因为<1,2>R3,<2,1>R3,但<1,1>R3。

定义6.4设R是X上的二元关系,如果对每个x

X,<x,x>

R,则称R是反自反的。

R在X上是反自反的

(

x)(x

X

<x,x>

R);例如,实数集上的“

”及家庭成员中的父子关系都是反自反的。

注意“不是自反的”与“是反自反的”有区别,“反自反的”一定“不是自反的”,但“不是自反的”不一定是“反自反的”。

例4.A={1,2,3},A上的关系

S={<1,1>,<1,2>,<3,2>,<2,3>,<3,3>},

验证:S不是自反的,也不是反自反的。

解:因为2

A,但<2,2>

S,故S不是自反的。

又1

A,但<1,1>

S,

故S也不是反自反的。

定义6.5设R是X上的二元关系,如果对每个x,y

X,当xRy和yRx时,必有x=y,则称R在X上是反对称的。

即R在X上是反对称的

(

x)(

y)(x

X

y

X

xRy

yRxx=y);

例如实数集的“

”关系是反对称的,集合的包含关系“”是反对称的。

例如,A={1,2,3},R={<1,2>,<1,3>,<2,2>}是反对称关系。

因为(xRy

yRxx=y)(x=y)(xRy

yRx)

(x=y)(xRy

yRx)((xy)(xRy))

yRx

(xy)(xRy)

yRx,

故R在X上是反对称的

(

x)(

y)(x

X

y

X

x

y

xRy

yRx);

例如,设A={1,2,3},则S={<1,1>,<2,2>,<3,3>}是A上的对称关系,也是A上的反对称关系。

T={<1,2>,<2,1>,<2,3>}既不是对称关系也不是反对称关系。

例5.设某人有三个儿子分别是T、G、H,组成集合A={T,G,H},在A上的兄弟关系具有哪些性质?

解:A上的兄弟关系是反自反的和对称的。

注意:A上的兄弟关系一般不具有传递性,

这是因为<T,G>A,<G,T>A,但<T,T>A#

例6.设集合I={1,2,3,4},I上的关系R={<1,1>,

<1,3>,<2,2>,<3,3>,<3,1>,<3,4>,<4,3>,<4,4>},

讨论R的性质。

解:写出R的关系矩阵为:R的关系图为:

3

4

MR=

可看出R是自反的,对称的;1

2

但没有传递性.

解:法一,先求出RC和RRC,再求出RC和RRC的关

系矩阵MRC和MRRC;

R={<a,a>,<a,c>,<b,a>,<b,b>,<c,a>,

<c,b>,<c,c>},

故RC={<a,a>,<c,a>,<a,b>,<b,b>,<a,c>,

<b,c>,<c,c>;

从而RRC={<a,a>,<a,b>,<a,c>,<b,a>,

<b,b>,<b,c>,<c,a>,<c,b>,<c,c>};解:法一,先求出RC和RRC,再求出RC和RRC的关

系矩阵MRC和MRRC;

R={<a,a>,<a,c>,<b,a>,<b,b>,<c,a>,

<c,b>,<c,c>},

故RC={<a,a>,<c,a>,<a,b>,<b,b>,<a,c>,

<b,c>,<c,c>;

从而RRC={<a,a>,<a,b>,<a,c>,<b,a>,

<b,b>,<b,c>,<c,a>,<c,b>,<c,c>};(5)关系R是传递的当且仅当在关系矩阵中对任意的

i,j,k{1,2,…,n},如果有rij=1且rjk=1,则必有

rik=1;在关系图中对任意结点x,y,z,如果在关系

图中有结点x到y的有向弧,并且有y到z的有向弧,

则必定有x到z的有向弧。(5)关系R是传递的当且仅当在关系矩阵中对任意的

i,j,k{1,2,…,n},如果有rij=1且rjk=1,则必有

rik=1;在关系图中对任意结点x,y,z,如果在关系

图中有结点x到y的有向弧,并且有y到z的有向弧,

则必定有x到z的有向弧。2设R是X到Y的关系,

则称关系RC={<y,x>|<x,y>R}为R的逆关系。1设R是X上的二元关系,如果对每个xX,都有xRx,则称R在X上是自反的。b)任取z(ST)(A)(x)(xA<x,z>ST)

(x)(y)xAyYzZ<x,y>S<y,z>T

(y)(<y,z>TyS(A))zT(S(A)),

所以,(ST)(A)=T(S(A))。注意“不是自反的”与“是反自反的”有区别,“反自反的”一定“不是自反的”,但“不是自反的”不一定是“反自反的”。(6)设R是集合X上的自反关系。解:法一,先求出RC和RRC,再求出RC和RRC的关

系矩阵MRC和MRRC;

R={<a,a>,<a,c>,<b,a>,<b,b>,<c,a>,

<c,b>,<c,c>},

故RC={<a,a>,<c,a>,<a,b>,<b,b>,<a,c>,

<b,c>,<c,c>;

从而RRC={<a,a>,<a,b>,<a,c>,<b,a>,

<b,b>,<b,c>,<c,a>,<c,b>,<c,c>};R在X上是可传递的

(x)(y)(z)(xXyXzXxRyyRzxRz);

例如,实数集的关系“<”,“”,“=”都是可传递的。例如,设R是关系“是的兄弟”,S是关系“是的父亲”,则RS是关系“是的叔伯”,RR是关系“是的祖父”。3设R是X上的二元关系,如果对每个x,

y,zX,当xRy且yRz就有xRz,则称R在X上是可传递的。P119,(2)证明若S是集合X上的二元关系,

a)S是传递的,当且仅当(SS)S;

b)S是自反的,当且仅当IXS;

证明:a)若S是传递的,设<x,z>SS,

则存在yX,使得<x,y>S,且<y,z>S,

因S是可传递的,故<x,z>S,所以SSS。反之,若R=RC,

则对任意任意的<x,y>R

<x,y>RC<y,x>R,

故R是对称的#1设R为X到Y的关系,设S为Y到Z的关系,则称关系{<x,z>|xXzZ(y)(yY<x,y>R

<y,z>S)}为R和S的复合关系,记为:RS,

即RS={<x,z>|xXzZ(y)(yY<x,y>R

<y,z>S)};关系的性质反映在关系矩阵和关系图上是:

(1)关系R是自反的当且仅当关系矩阵中主对角线

上的所有元素都为1,在关系图中每个结点都有

自回路(环)。

(2)关系R是反自反的当且仅当关系矩阵中主对角

线上的所有元素都为0,在关系图中每个结点都

没有自回路(环)。

(3)关系R是对称的当且仅当关系矩阵是对称阵,在

关系图中每两个结点间若有有向弧线,则必有反

向弧线,即弧线必成对出现。

(4)关系R是反对称的当且仅当关系矩阵中以主对角

线对称的元素不能同时为1,在关系图中不同结

点间的有向弧,不能成对出现。

(5)关系R是传递的当且仅当在关系矩阵中对任意的

i,j,k{1,2,…,n},如果有rij=1且rjk=1,则必有

rik=1;在关系图中对任意结点x,y,z,如果在关系

图中有结点x到y的有向弧,并且有y到z的有向弧,

则必定有x到z的有向弧。

P113,习题3-6,(4)如果R和S是自反的,对称的和可传递的,证明:R

S也是自反的,对称的和可传递的;

证明:1)设R和S是自反的,

则对任意xX,有<x,

x>R,<x,

x>S,

故<x,

x>RS,即RS是X上的自反关系;

2)设R和S是对称的,对任意<x,

y>RS,

即<x,

y>R<x,

y>S,

因为R和S是对称的,故<y,x>R<y,x>S,

即<y,x>

R

S,故R

S也是对称的#

3)设R和S是可传递的,

对任意<x,

y>RS<y,

z>RS,

则有:<x,

y>R<x,

y>S<y,

z>R<y,

z>S,

因为R和S是可传递的,故<x,

z>R<x,

z>S,

从而<x,

z>RS,

故R

S是X上的传递关系#

(6)设R是集合X上的自反关系。求证:R是对称和

传递的,当且仅当<a,b>和<a,c>在R之中则有

<b,c>在R之中。

证明:设R是X上的自反关系。

若R在X上是对称和传递的,则对任意的a,b,c

X,

如果有<a,b>

R

<a,c>

R,

则<b,a>

R

<a,c>

R,故<b,c>

R。

反之,若<a,b>

R,<a,c>

R,必有<b,c>

R,

则对任意的a,b

X,若<a,b>

R,

因<a,a>R,得<b,a>

R,故R是对称的。

若<a,b>

R

<b,c>

R,则<b,a>

R

<b,c>

R,

所以<a,c>

R,即R是可传递的。

作业:P113,习题3-6,(1);(3);(4);(5);又1A,但<1,1>S,

故S也不是反自反的。P119,(2)证明若S是集合X上的二元关系,

a)S是传递的,当且仅当(SS)S;

b)S是自反的,当且仅当IXS;

证明:a)若S是传递的,设<x,z>SS,

则存在yX,使得<x,y>S,且<y,z>S,

因S是可传递的,故<x,z>S,所以SSS。设R={<1,2>,<3,4>,<2,2>},

S={<4,2>,<2,5>,<3,1>,<1,3>},

都是A={1,2,3,4,5}上的关系,

求:RS,SR,R(SR),(RS)R,RR,

SS,(RR)R。设R={<1,2>,<3,4>,<2,2>},

S={<4,2>,<2,5>,<3,1>,<1,3>},

都是A={1,2,3,4,5}上的关系,

求:RS,SR,R(SR),(RS)R,RR,

SS,(RR)R。也就是关系的复合运算不满足交换律;

但设R是X到Y的关系,则IXR=RIY=R;

关系的复合运算是满足结合律的。定理7.b)设S是自反的,设<x,y>IX,则x=y,

但<x,x>S,因此<x,y>=<x,x>,得IXS。2)对于任意的x,yA,

如果<x,y>R,即(x-y)2是整数,

则(y-x)2也是整数,即<y,x>R,

故R是对称的#定义6.例如,=

=1设R是X上的二元关系,如果对每个xX,都有xRx,则称R在X上是自反的。(4)令S为从X到Y的关系,T为从Y到Z的关系,

对于AX,定义S(A)={y|<x,y>SxA},

(S(A)称为集合在关系S下的像,显然S(A)ran(R)),证明:

a)S(A)Y;(S(A)ran(R))b)(ST)(A)=T(S(A));

c)S(AB)=S(A)S(B);d)S(AB)S(A)S(B);

证明:a)设yS(A)(x)(xA<x,y>S)

(x)(xX<x,y>S)yran(R),

所以,S(A)ran(R)Y。ST

XYZ

AS(A)T(S(A))

ST

ST(A)(5)关系R是传递的当且仅当在关系矩阵中对任意的

i,j,k{1,2,…,n},如果有rij=1且rjk=1,则必有

rik=1;在关系图中对任意结点x,y,z,如果在关系

图中有结点x到y的有向弧,并且有y到z的有向弧,

则必定有x到z的有向弧。P113,习题3-6,(4)如果R和S是自反的,对称的和可传递的,证明:RS也是自反的,对称的和可传递的;

证明:1)设R和S是自反的,

则对任意xX,有<x,x>R,<x,x>S,

故<x,x>RS,即RS是X上的自反关系;

2)设R和S是对称的,对任意<x,y>RS,

即<x,y>R<x,y>S,

因为R和S是对称的,故<y,x>R<y,x>S,

即<y,x>RS,故RS也是对称的#解:法一,先求出RC和RRC,再求出RC和RRC的关

系矩阵MRC和MRRC;

R={<a,a>,<a,c>,<b,a>,<b,b>,<c,a>,

<c,b>,<c,c>},

故RC={<a,a>,<c,a>,<a,b>,<b,b>,<a,c>,

<b,c>,<c,c>;

从而RRC={<a,a>,<a,b>,<a,c>,<b,a>,

<b,b>,<b,c>,<c,a>,<c,b>,<c,c>};R在X上是反自反的(x)(xX<x,x>R);

第七节

复合关系和逆关系

一、复合关系

定义7.1设R为X到Y的关系,设S为Y到Z的关系,则称关系{<x,z>|x

X

z

Z

(

y)(y

Y

<x,y>

R

<y,z>

S)}为R和S的复合关系,记为:RS,

即RS={<x,z>|x

X

z

Z

(

y)(y

Y

<x,y>

R

<y,z>

S)};

R:A

BS:BC

ABC

a1○

○b1

○c1

a2○

○

b2○c2

a3○

○

b3○

c3

a4○

○

b4

○c4

a1○

○

c1

a2○

○

c2

a3○

○

c3

a4○

○

c4

R

S:AC

例1.设X={1,2,3,4},Y={2,3,4},Z={1,2,3},R1是X到Y的关系,R2是Y到Z的关系,它们分别是:

R1={<x,y>|x+y=5},R2={<y,z>|y–z=2},求R1

R2;

解:R1={<1,4>,<2,3>,<3,2>},

R2={<3,1>,<4,2>},

则R1

R2={<1,2>,<2,1>}#示意图:

XYZ

1○

R1

○2R2

○1

2○

○3○2

3○

○4○3

4○

R1

R2例如,设R是关系“

是

的兄弟”,S是关系“

是

的父亲”,则R

S是关系“

是

的叔伯”,R

R是关系“

是

的祖父”。

“

”可以看成是关系的二元运算,称为关系的复合运算(或合成运算)。

例2.设R={<1,2>,<3,4>,<2,2>},

S={<4,2>,<2,5>,<3,1>,<1,3>},

都是A={1,2,3,4,5}上的关系,

求:R

S,S

R,R

(S

R),(R

S)

R,R

R,

S

S,(R

R)

R。

解:R

S={<1,5>,<3,2>,<2,5>},

S

R={<4,2>,<3,2>,<1,4>}

R

S,

R

(S

R)={<3,2>},

(R

S)

R={<3,2>},

R

R={<1,2>,<2,2>},

S

S={<4,5>,<3,3>,<1,1>},

(R

R)

R={<1,2>,<2,2>}#

注意,当R

S有意义时,S

R不一定有意义;即使RS和S

R都有意义,两者也不一定相同,一般地,

R

S

S

R。也就是关系的复合运算不满足交换律;

但设R是X到Y的关系,则IX

R=R

IY=R;

关系的复合运算是满足结合律的。即,设R是X到Y的关系,S是Y到Z的关系,P是Z到W的关系,则(R

S)

P和R

(S

P)都是X到W的关系,且(R

S)

P=

R(S

P);证明略;

所以多个关系的复合可以不标明运算次序。

设R是X上的关系,可定义R0=IX,R1=R,Rn=

RRR

R,

则Rn

Rm=Rn+m,(Rn)m=Rnm.例3.设R1和R2是集合X={0,1,2,3}上的关系,

R1={<i,j>|j=i+1或j=i/2},R2={<i,j>|i=j+2},

求:R1

R2,R2

R1,R1

R2

R1,R1

R1,R1

R1

R1;

解:R1={<0,1>,<1,2>,<2,3>,<0,0>,<2,1>},

R2={<2,0>,<3,1>},

R1

R2={<1,0>,<2,1>},

R2

R1={<2,1>,<2,0>,<3,2>},

R1

R2

R1={<1,1>,<1,0>,<2,2>},

R1

R1={<0,2>,<1,3>,<1,1>,<0,1>,<0,0>,<2,2>}

(R1

R1)

R1={<0,3>,<0,1>,<1,2>,<0,2>,<0,0>,

<2,3>,<2,1>}#

设MR=[uij]nm是X到Y的关系R的关系矩阵,MS=[vjk]ml是Y到Z的关系S的关系矩阵,则R

S的关系矩阵MR

S=[wik]nl,其中

m

wik=

(uij

vjk)=(ui1

v1k)

(ui2

v2k)…(uim

vmk)

j=1

(i=1,2,…,n;k=1,2,…,l)

代表逻辑加,0

0=0,0

1=1

0=1

1=1,

代表逻辑乘,0

0=0

1=1

0=0,1

1=1。

即MR

S=MR

MS,这里“

”称为矩阵的布尔乘积,矩阵的布尔乘积与矩阵的普通乘积有点相似。证明:wik=(ui1

v1k)

(ui2

v2k)…(uim

vmk)

(i=1,2,…,n;k=1,2,…,l)

1)设wik=1,即至少存在某个vj0Y,(j0{1,2,…,m})

使得<wi,vj0>R,<vj0,wk>S成立,

于是uij0=1,vj0k=1,故uij0

vj0k=1,

从而,(ui1

v1k)

(ui2

v2k)…(uim

vmk)=1;

2)设wik=0,则不存在vjY,

使得<wi,vj>R,<vj,wk>S同时成立,

即对所有的j(j=1,2,…,m),uij=1,vjk=1不同时成立,

故(uij

vjk)=0,(j=1,2,…,m),

从而(ui1

v1k)

(ui2

v2k)…(uim

vmk)=0,由1),2)知:

wik=

(uij

vjk)=(ui1

v1k)

(ui2

v2k)…(uim

vmk)#

例如,

=

=

例4.设R1是由A={1,2,3,4}到B={2,3,4}的关系,R2是由B到C={1,2,3}的关系,

R1={<a,b>|a+b=6}={<2,4>,<3,3>,<4,2>},

R2={<b,c>|b–c=1}={<2,1>,<3,2>,<4,3>},

求:复合关系R1

R2的关系矩阵。

解:法一,先求出关系R1

R2={<2,3>,<3,2>,

<4,1>},

再求R1

R2的关系矩阵:123

1

2

MR1

R2=3

4

法二:234123

12

MR1=2MR2=3

34

4

MR1

R2=MR1

MR2=

=

二、逆关系

定义7.2设R是X到Y的关系,

则称关系RC={<y,x>|<x,y>

R}为R的逆关系。

例如,在实数集上的关系“<”的逆关系是“>”,

设X={1,2,3,4},Y={a,b,c},

则X到Y的关系R={<1,a>,<2,b>,<3,c>}的逆关系:

RC={<a,1>,<b,2>,<c,3>},

显然(RC)C=R,

因为<x,y>

R

<y,x>

RC

<x,y>

(RC)C#

定理7.1设R,R1和R2都是从A到B的关系,则

a)(R1

R2)C=R1C

R2C

b)(R1

R2)C=R1C

R2C

c)(A

B)C=B

A

d)(R)C=RC,这里R=A

B–R;

e)(R1–R2)C=R1C–R2C

证明:a)因为<x,y>

(R1

R2)C

<y,x>

R1

R2

<y,x>

R1

<y,x>

R2

<x,y>

R1C

<x,y>

RC

<x,y>

R1C

R2C,

所以,(R1

R2)C=R1C

R2C#

c)<x,y>(AB)C

<y,x>AB<x,y>BA#

d)<x,y>(R)C

<y,x>

(R)

<y,x>R<x,y>RC

<x,y>RC#

定理7.2设T是X到Y的关系,S是Y到Z的关系,

则:(T

S)C=SC

TC;

证明:对任意的<z,x>

(T

S)C

<x,z>

T

S

(

y)(y

Y

<x,y>

T

<y,z>

S)

(

y)(y

Y

<y,x>

TC

<z,y>

SC)

<z,x>

SC

TC

#

定理7.3设R是X上的关系,则:

a)R是对称的,当且仅当R=RC;

b)R是反对称的,当且仅当R

RC

IX;

证明:a)若R是对称的,则对任意的

<x,y>

R

<y,x>

R

<x,y>

RC,

所以R=RC。

反之,若R=RC,

则对任意任意的<x,y>

R

<x,y>

RC

<y,x>

R,

故R是对称的#

b)若R是反对称的,对任意的

<x,y>

R

RC(<x,y>

R)

(<x,y>

RC)

(<x,y>

R)

(<y,x>

R)x=y,即<x,y>

IX。

故R

RC

IX,

反之,若R

RC

IX,

则对任意的(<x,y>

R)

(<y,x>

R)

(<x,y>

R)

(<x,y>

RC)

<x,y>

R

RC

<x,y>

IXx=y,

故R是反对称的#

例题4.设X={a,b,c},R是X上的关系,R的关系矩阵

MR=,求RC和R

RC的关系矩阵。

解:

法一,先求出RC和R

RC,再求出RC和R

RC的关

系矩阵MRC和MR

RC;

R={<a,a>,<a,c>,<b,a>,<b,b>,<c,a>,

<c,b>,<c,c>},

故RC={<a,a>,<c,a>,<a,b>,<b,b>,<a,c>,

<b,c>,<c,c>;

从而R

RC={<a,a>,<a,b>,<a,c>,<b,a>,

<b,b>,<b,c>,<c,a>,<c,b>,<c,c>};

法二,先求出RC和R

RC的关系矩阵MRC和MR

RC;

再求出RC和R

RC;

MRC=,

MR

RC=

=,

从而,RC={<a,a>,<c,a>,<a,b>,<b,b>,<a,c>,

<b,c>,<c,c>;

R

RC={<a,a>,<a,b>,<a,c>,<b,a>,

<b,b>,<b,c>,<c,a>,<c,b>,<c,c>}=X×X;

复合运算与交并运算的运算性质

设R,S,T都是X上的关系,则

(1)R

(S

T)=R

S

R

T,

(2)(S

T)

R=S

R

T

R,

(3)R

(S

T)

R

S

R

T,

(4)(S

T)

R

S

R

T

R;

(5)如果R

S,则R

T

S

T,T

R

T

S;

注意(3)(4)式的反方向包含关系是不成立的。

关系的运算(逆,交,并,复合,相对补)是否保持关系的五个性质由下面的表给出,保持的都可以证明,不保持的都可以找出反例。

自反性反自反性对称性反对称性传递性RC

R1

R2

R1

R2

××R1–R2×

×R1

R2

××××R在X上是可传递的

(x)(y)(z)(xXyXzXxRyyRzxRz);

例如,实数集的关系“<”,“”,“=”都是可传递的。解:法一,先求出RC和RRC,再求出RC和RRC的关

系矩阵MRC和MRRC;

R={<a,a>,<a,c>,<b,a>,<b,b>,<c,a>,

<c,b>,<c,c>},

故RC={<a,a>,<c,a>,<a,b>,<b,b>,<a,c>,

<b,c>,<c,c>;

从而RRC={<a,a>,<a,b>,<a,c>,<b,a>,

<b,b>,<b,c>,<c,a>,<c,b>,<c,c>};反之,令IXS,设任意xX,<x,x>IX,

故<x,x>S,因此S是自反的。设MR=[uij]nm是X到Y的关系R的关系矩阵,MS=[vjk]ml是Y到Z的关系S的关系矩阵,则RS的关系矩阵MRS=[wik]nl,其中

m

wik=(uijvjk)=(ui1v1k)(ui2v2k)…(uimvmk)

j=1

(i=1,2,…,n;k=1,2,…,l)

代表逻辑加,00=0,01=10=11=1,

代表逻辑乘,00=01=10=0,11=1。例如,设A={1,2,3},则S={<1,1>,<2,2>,<3,3>}是A上的对称关系,也是A上的反对称关系。(5)关系R是传递的当且仅当在关系矩阵中对任意的

i,j,k{1,2,…,n},如果有rij=1且rjk=1,则必有

rik=1;在关系图中对任意结点x,y,z,如果在关系

图中有结点x到y的有向弧,并且有y到z的有向弧,

则必定有x到z的有向弧。法二:234123

12

MR1=2MR2=3

34

4

MR1R2=MR1MR2=

=(5)关系R是传递的当且仅当在关系矩阵中对任意的

i,j,k{1,2,…,n},如果有rij=1且rjk=1,则必有

rik=1;在关系图中对任意结点x,y,z,如果在关系

图中有结点x到y的有向弧,并且有y到z的有向弧,

则必定有x到z的有向弧。法二,先求出RC和RRC的关系矩阵MRC和MRRC;

再求出RC和RRC;

MRC=,

MRRC==,

从而,RC={<a,a>,<c,a>,<a,b>,<b,b>,<a,c>,

<b,c>,<c,c>;

RRC={<a,a>,<a,b>,<a,c>,<b,a>,

<b,b>,<b,c>,<c,a>,<c,b>,<c,c>}=X×X;第七节复合关系和逆关系

一、复合关系

定义7.关系的运算(逆,交,并,复合,相对补)是否保持关系的五个性质由下面的表给出,保持的都可以证明,不保持的都可以找出反例。b)设S是自反的,设<x,y>IX,则x=y,

但<x,x>S,因此<x,y>=<x,x>,得IXS。设某人有三个儿子分别是T、G、H,组成集合A={T,G,H},在A上的兄弟关系具有哪些性质?

解:A上的兄弟关系是反自反的和对称的。P118,习题3-7(1)设R1和R2是A上的任意关系,

说明以下命题的真假,并予以证明。

a)若设R1和R2是自反的,则R1

R2也是自反的;

b)若设R1和R2是反自反的,则R1

R2也是反自反的;

c)若设R1和R2是对称的,则R1

R2也是对称的;

b)若设R1和R2是传递的,则R1

R2也是传递的;

a)结论成立,证明如下:设R1和R2是自反的,

则对任意的a

A,有<a,a>

R1,<a