离散数学-集合的笛卡儿积与二元关系

第4章二元关系与函数4.1集合笛卡儿积与二元关系4.2关系运算4.3关系性质4.4关系闭包4.5等价关系和偏序关系4.6函数定义和性质4.7函数复合和反函数1第1页4.1集合笛卡儿积和二元关系

有序对笛卡儿积及其性质二元关系定义二元关系表示2第2页有序对定义

由两个元素x和y，按照一定次序组成二元组称为有序对，记作<x,y>实例：平面直角坐标系中点坐标<3,

4>有序对性质1）有序性<x,y>

<y,x>（当x

y时）2）<x,y>与<u,v>相等充分必要条件是<x,y>=<u,v>

x=u

y=v例1<2,x+5>=<3y

4,y>，求x,y.解3y

4=2,x+5=y

y=2,x=3

3第3页有序n元组定义一个有序n(n3)元组<x1,x2,…,xn>是一个有序对，其中第一个元素是一个有序n-1元组，即<x1,x2,…,xn>=<<x1,x2,…,xn-1>,xn>

实例：空间直角坐标系中坐标

<3，5，－6>n维向量是有序n元组.当n=1时,<x>形式上能够看成有序1元组.4第4页笛卡儿积定义设A,B为集合，用A中元素为第一个元素，B中元素为第二个元素，组成有序对.全部这么有序对组成集合叫做A与B笛卡儿积

记作A

B，即A

B={<x,y>|x

A

y

B}例2A={1,2,3},B={a,b,c}

A

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

B

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

A={

},P(A)

A={<

,

>,<{

},

>}5第5页笛卡儿积性质不适合交换律

A

B

B

A(A

B,A

,B

)不适合结合律

(A

B)

C

A

(B

C)(A

,B

)对于并或交运算满足分配律

A

(B

C)=(A

B)

(A

C)(B

C)

A=(B

A)

(C

A)

A

(B

C)=(A

B)

(A

C)(B

C)

A=(B

A)

(C

A)若A或B中有一个为空集，则A

B就是空集.

A

=

B=

若|A|=m,|B|=n,则|A

B|=mn

6第6页性质证实证实A

(B

C)=(A

B)

(A

C)证任取<x,y><x,y>∈A×(B∪C)

x∈A∧y∈B∪C

x∈A∧(y∈B∨y∈C)

(x∈A∧y∈B)∨(x∈A∧y∈C)

<x,y>∈A×B∨<x,y>∈A×C

<x,y>∈(A×B)∪(A×C)所以有A×(B∪C)=(A×B)∪(A×C).7第7页例题解(1)任取<x,y><x,y>

A

C

x

A

y

C

x

B

y

D

<x,y>

B

D

例3(1)证实A=B

C=D

A

C=B

D

(2)A

C=B

D是否推出A=B

C=D?为何？(2)不一定.反例以下：

A={1}，B={2},C=D=

,则A

C=B

D不过A

B.8第8页例4(1)证实A

B

C

D

A

C

B

D

(2)A

C

B

D是否推出A

B

C

D解(1)任取<x,y><x,y>

A

C

x

A

y

C

x

B

y

D

<x,y>

B

D

(2)不一定.反例以下：

A={1}，B={2},C=D=

9第9页例5设A、B、C、D为任意集合，判断以下等式是否成立，说明为何。(A

B)(C

D)=(A

C)(B

D)(A

B)(C

D)=(A

C)

(B

D)(A-B)(C-D)=(A

C)-(B

D)(A

B)(C

D)=(A

C)

(B

D)解：(1)成立，因为对任意<x,y><x,y>

(A

B)(CD)x

A

ByCDx

A

x

ByCyD<x,y>

A

C

<x,y>

B

D10第10页(2)(A

B)(C

D)=(A

C)(B

D)解：不成立，若A=D=B=C={1}则有：(A

B)(CD)=B

C={<1,1>}(3)(A-B)(C-D)=(A

C)-(B

D)解：不成立，A=B={1}C={2}D={3}(A-B)(C-D)=(A

C)-(BD)={<1,2>}{<1,3>}={<1,2>}(4)(A

B)(C

D)=(A

C)

(B

D)解：A={1}B=C=D={1}(A

B)(CD)={1,1}(A

C)(BD)=11第11页设A1,A2,…,An是集合(n≥2),它们n阶笛卡尔积记作A1

A2

…

An,其中A1

A2

…

An={<x1,x2,…,xn>︱x1A1,x2

A2,…,xnAn}.当A1=A2

=…=An时，可将它们n阶笛卡尔积记作An比如：A={a,b},则A3={<a,a,a>,<a,a,b>,<a,b,a>,<a,b,b>,<b,a,a>,<b,a,b>,<b,b,a>,<b,b,b>}12第12页二元关系：集合中两个元素之间某种关系例1甲、乙、丙3个人进行乒乓球比赛，任何两个人之间都要比赛一场。假设比赛结果是乙胜甲，甲胜丙，乙胜丙。比赛结果可表示为：{<乙,甲>，<甲,丙>，<乙,丙>}，其中<x,y>表示x胜y，它表示了集合{甲,乙,丙}中元素之间一个胜败关系.例2有A、B、C3个人和四项工作G1、G2、G3、G4，已知A能够从事工作G1和G4，B能够从事工作G3，C能够从事工作G1和G2.那么，人和工作之间对应关系能够记作R＝

{<A,G1>,<A,G4>,<B,G3>,<C,G1>,<C,G2}它表示了集合{A,B,C}到工作{G1,G2,G3,G4}之间关系13第13页二元关系定义定义假如一个集合满足以下条件之一：（1）集合非空,且它元素都是有序对（2）集合是空集则称该集合为一个二元关系,简称为关系，记作R.如<x,y>∈R,可记作xRy；假如<x,y>

R,则记作xy实例：R={<1,2>,<a,b>},S={<1,2>,a,b}.R是二元关系,当a,b不是有序对时，S不是二元关系依据上面记法，能够写1R2,aRb,ac等.14第14页从A到B关系与A上关系定义设A,B为集合,A×B任何子集所定义二元关系叫做从A到B二元关系,当A=B时则叫做A上二元关系.例4A={0,1},B={1,2,3},R1={<0,2>},R2=A×B,R3=

,R4={<0,1>}.那么R1,R2,R3,R4是从A到B二元关系,R3和R4同时也是A上二元关系.计数|A|=n,|A×A|=n2,A×A子集有个.所以A上有个不一样二元关系.比如|A|=3,则A上有=512个不一样二元关系.15第15页A上主要关系实例设A为任意集合，

是A上关系，称为空关系EA,IA分别称为全域关系与恒等关系，定义以下：

EA={<x,y>|x∈A∧y∈A}=A×A

IA={<x,x>|x∈A}

比如,A={1,2},则

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

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

16第16页A上主要关系实例（续）小于等于关系LA,整除关系DA,包含关系R

定义：LA={<x,y>|x,y∈A∧x≤y},A

R，R为实数集合DB={<x,y>|x,y∈B∧x整除y},B

Z+,Z+为非0整数集R

={<x,y>|x,y∈A∧x

y},A是集合族.类似还能够定义大于等于关系,小于关系,大于关系,真包含关系等等.17第17页实例比如A={1,2,3},B={a,b},则

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

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

A=P(B)={

,{a},{b},{a,b}},则A上包含关系是R

={<

,

>,<

,{a}>,<

,{b}>,<

,{a,b}>,<{a},{a}>,<{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>}

18第18页关系表示表示方式：关系集合表示式、关系矩阵、关系图关系矩阵：若A={x1,x2,…,xm}，B={y1,y2,…,yn}，R是从A到B关系，R关系矩阵是布尔矩阵MR=[rij]m

n,其中rij

=1

<xi,yj>

R.关系图：若A={x1,x2,…,xm}，R是从A上关系，R关系图是GR=<A,R>,其中A为结点集，R为边集.假如<xi,xj>属于关系R，在图中就有一条从xi

到xj有向边.注意：A,B为有穷集，关系矩阵适于表示从A到B关系或者A上关系，关系图适于表示A上关系19第19页实例A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R关系矩阵MR和关系图GR以下：20第20页基本运算定义定义域、值域、域逆、合成、限制、像基本运算性质幂运算定义求法性质4.2关系运算21第21页关系基本运算定义定义域、值域

和域domR={x|

y(<x,y>

R)}ranR={y|

x(<x,y>

R)}fldR=domR

ranR例1R={<1,2>,<1,3>,<2,4>,<4,3>},则domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}22第22页关系基本运算定义（续）定义设F、G为任意关系，A为集合，则逆与合成

F

1={<y,x>|<x,y>

F}

F∘G=|<x,y>|

z(<x,z>

G

<z,y>

F)}例2R={<1,2>,<2,3>,<1,4>,<2,2>}

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

R

1={<2,1>,<3,2>,<4,1>,<2,2>}S∘R={<1,3>,<2,2>,<2,3>}R∘S={<1,2>,<1,4>,<3,2>,<3,3>}23第23页合成运算图示方法

利用图示（不是关系图）方法求合成

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

S∘R={<1,3>,<2,2>,<2,3>}R∘SS∘R24第24页限制与像定义F在A上限制

F↾A={<x,y>|xFy

x

A}A在F下像

F[A]=ran(F↾A)实例R={<1,2>,<2,3>,<1,4>,<2,2>}

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

R[{1}]={2,4}

R↾=

R[{1,2}]={2,3,4}注意：F↾A

F,F[A]ranF

25第25页例.设F、G是N上关系，其定义为F={<x,y>︱x,yNy=x2}G={<x,y>︱x,yNy=x+1}求G

1、F∘G、G∘F、F↾{1,2}、F[{1,2}]解：G

1={<y,x>︱y,xNy=x+1}G

1={<1,0><2,1><3,2>,…<x+1,x>,…}对任何xN有y=z2=(x+1)2，所以

F∘G={<x,y>︱x,yNy=(x+1)2

}G∘F={<x,y>︱x,yNy=x2+1}F↾{1,2}={<1,1>,<2,4>}F[{1,2}]=ran(F↾{1,2})={1,4}26第26页例.设F={<a,{a}>,<{a},{a,{a}}>},求F∘F、F↾{a}、F[{a}]解：F∘F={<a,{a,{a}}>}F↾{a}={<a,{a}>}A={a}F[A]=ran(F↾A)=ran{<a,{a}>}={{a}}27第27页关系基本运算性质定理4.1设F是任意关系,则(1)(F

1)

1=F(2)domF

1=ranF,ranF

1=domF证(1)任取<x,y>,由逆定义有<x,y>∈(F

1)

1

<y,x>∈F

1

<x,y>∈F所以有(F

1)

1=F(2)任取x,x∈domF

1

y(<x,y>∈F

1)

y(<y,x>∈F)

x∈ranF

所以有domF

1=ranF.同理可证ranF

1=domF.28第28页(3)(F∘G)∘H=F∘(G∘H)(4)(F∘G)

1=G

1∘F

1证(3)任取<x,y>,<x,y>

(F∘G)∘H

t(<x,t>∈H∧<t,y>∈F∘G)

t(<x,t>∈H∧

s(<t,s>∈G)∧<s,y>∈F))

t

s(<x,t>∈H∧<t,s>∈G∧<s,y>∈F)

s(<s,y>∈F∧

t(<x,t>∈H∧<t,s>∈G))

s(<s,y>∈F∧<x,s>∈G∘H)

<x,y>∈F∘(G∘H)

所以(F∘G)∘H=F∘(G∘H)关系基本运算性质（续）

29第29页(4)任取<x,y>,<x,y>∈(F∘G)

1

<y,x>∈F∘G

t(<y,t>∈G∧(t,x)∈F)

t(<x,t>∈F

1∧(t,y)∈G

1)

<x,y>∈G

1∘F

1所以(F∘G)

1=G

1∘F

1

关系基本运算性质（续）

30第30页关系基本运算性质（续）

定理4.2设F、G、H为任意二元关系，则有：F∘(G

H)

=F∘G

F∘H(G

H)

∘F=G∘F

H∘F(合成运算对运算满足分配律）3.F∘(G

H)

F∘G

F∘H4.(G

H)

∘F

G∘F

H∘F(合成运算对

运算分配后是包含关系）31第31页A上关系幂运算设R为A上关系,n为自然数,则R

n次幂定义为：(1)R0={<x,x>|x∈A}=IA

(2)Rn

=Rn-1∘R,n≥1注意：对于A上任何关系R1和R2都有

R10=R20=IA

对于A上任何关系R都有

R1=R32第32页幂求法(1)对于集合表示关系R，计算Rn就是n个R左复合.(2)矩阵表示就是n个矩阵相乘,其中相加采取逻辑加.例3设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R各次幂,分别用矩阵和关系图表示.