笛卡尔积与二元关系42 关系的运算

1第2章二元关系为了研究离散对象之间的联系,本章引入关系的概念本章讨论的二元关系(简称关系)仍然是一种集合.它的元素是由有序对组成.22.1有序对与笛卡儿积

有序对笛卡儿积及其性质二元关系的定义二元关系的表示3有序对定义

由两个元素x和y，按照一定的顺序组成的二元组称为有序对，记作<x,y>.x叫有序对的第一元素,y叫有序对的第二元素实例：点的直角坐标(3,4)有序对性质

有序性

<x,y><y,x>（当xy时）

<x,y>与<u,v>相等的充分必要条件是

<x,y>=<u,v>x=u且y=v例1<2,x+5>=<3y4,y>，求x,y.解3y

4=2,x+5=y

y=2,x=3

4有序对<x,y>和集合{x,y}的区别:有序对<x,y>中x和y是有顺序的,xy时,<x,y><y,x>

如:<3,6><6,3>而集合中{x,y},x,y是无序的,xy时,{x,y}={y,x}

如:{3,6}={6,3}

5有序对的概念可以扩展成有序n元组定义一个有序n(n3)元组<x1,x2,…,xn>是一个有序对，其中第一个元素是一个有序n-1元组，即

<x1,x2,…,xn>=<<x1,x2,…,xn-1>,xn>

当n=1时,<x>形式上可以看成有序1元组.实例

n维向量是有序

n元组.6笛卡儿积:一种新的集合运算定义设A,B为集合，用A中的元素为第一元素,B中的元素为第二元素,构成有序对,所有这样的有序对组成的集合叫做A与B的笛卡儿积记作AB，即AB={<x,y>|xA且yB}例2A={1,2,3},B={a,b,c}

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

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

A={},P(A)A={<,>,<{},>}

*如果A中有m个元素,B中有n个元素,则AB

有mn个元素.7例4.18笛卡儿积的性质不适合交换律

ABBA(AB,A,B)不适合结合律

(AB)CA(BC)(A,B)对于并或交运算满足分配律

A(BC)=(AB)(AC)(BC)A=(BA)(CA)

A(BC)=(AB)(AC)(BC)A=(BA)(CA)若A或B中有一个为空集，则AB就是空集.

A=B=

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

则|AB|=mn

9分配律的证明证明A(BC)=(AB)(AC)证任取<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).10例题解(1)任取<x,y><x,y>AC

xAyC

xByD<x,y>BD

例3(1)证明A=BC=DAC=BD

(2)AC=BD是否推出A=B

C=D?为什么？(2)不一定.反例如下：

A={1}，B={2},C=D=,则AC=BD但是AB.11二元关系什么是关系:

在涉及离散对象的很多问题中,往往需要研究这些对象之间的某种关系.

日常生活中父子关系,兄弟关系等,

都可以抽象成集合中元素之间的关系.

为简单起见,我们仅讨论两个集合上的二元关系.12二元关系的定义定义如果一个集合满足以下条件之一：（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等.关系也是一种集合,只是关系中的元素为有序对.13从A到B的关系与A上的关系例4A={0,1},B={1,2,3},求A×B,A×AA×B={<0,1>,<0,2>,<0,3>,<1,1>,<1,2>,<1,3>}A×A={<0,0>,<0,1>,<1,0>,<1,1>}定义设A,B为集合,A×B的任何子集所定义的二元关系叫做从A到B的二元关系,A=B时则叫做A上的二元关系.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问题：下列说法有何区别？设A,B为集合,

从A到B的二元关系,A上的二元关系16A上三种特殊关系设A为任意集合，是A上的关系，称为空关系EA,IA分别称为A上的全域关系与恒等关系，定义如下：

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>}

17A上其他特殊关系小于等于关系LA,整除关系DA,包含关系R定义：小于等于关系

LA={<x,y>|x,y∈A∧x≤y},AR，R为实数集合整除关系DB={<x,y>|x,y∈B∧x整除y},BZ*,Z*为非0整数集例如A={1,2,3}则

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

DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}.18包含关系:R={<x,y>|x,y∈A∧xy},A是集合族例: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}>}

除此以外,还可以构成其他关系:

如:大于等于关系,小于关系,大于关系,真包含关系等等.例:P804.419例设S={1，2，3，4}，下面定义的R都是S上的关系，分别列出R中的元素（1）R={<x,y>|x,y∈s∧x|y}R={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>,<2,4>,<3,3>,<4,4>}(2)R={<X,Y>|x,y∈s∧x/y是素数R=<2,1>,<3,1>,<4,2>}求S上的全域关系，恒等关系？20关系的表示方法三种表示方式：关系的集合表达式、关系矩阵、关系图关系矩阵：若A={x1,x2,…,xn}，R是A上的关系，R的关系矩阵是布尔矩阵MR=[rij]nn,其中rij

=1<xi,xj>R.A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R的关系矩阵MR练习：设S={1，2，3，4}，R都是S上的关系，

R={<2,1>,<3,1>,<4,2>}，用关系矩阵表示R21关系矩阵表示从A到B的关系关系矩阵：若A={x1,x2,…,xm}，B={y1,y2,…,yn}，R是从A到B的关系，R的关系矩阵是布尔矩阵MR=[rij]mn,其中rij

=1<xi,yj>R.注意：A,B为有穷集，关系矩阵适于表示从A到B的关系或者A上的关系22用关系图表示A上的关系关系图：若A={x1,x2,…,xm}，R是从A上的关系，R的关系图是GR=<A,R>,其中A为结点集，R为边集.如果<xi,xj>属于关系R，在图中就有一条从xi

到xj

的有向边.注意:以上关系图适于表示A上的关系

A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R的关系图GR如下：23实例A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R的关系矩阵MR和关系图GR如下：24A到B的关系图（不是真正意义的关系图，主要用于计算）例:设A={2,3,4,8},B={1,5,7}A到B上的关系R={<2,5>,<2,7>,<3,5>,<4,1>,<8,7>}A中的4个元素用4个结点表示画左边,B中的3个元素用3个结点画右边.如关系中存在有序对<a,b>,就将结点a和b相连.

如右图:254.8例题分析例4.26P106X={-4,-3,-2,-1,0,1,2,3,4}R1={<x,y>|x,y∈X∧x<y}

={<-4,-3>,<-4,-2>,….<-4,4>,<-3,-2>…..}R(0)={1,2,3,4}

对于x∈X定义集合

R(x)={y|xRy}

求R(0)=26小结为了研究离散对象之间的联系,本章引入二元关系的概念.1什么是关系?关系也是一种集合,二元关系中的元素为有序对,这些有序对中的两个元素来自两个不同或相同的集合.

因此,关系是建立在其他集合之上的集合.

如,A到B上的关系,反映不同集合中元素与元素之间的关系

A上的关系,反映的是同一集合中元素之间的关系.272A上的关系数目为,这个数目往往是很大的,而我们通常关注的是其中少量的有特殊含义的关系.

如EA,IA,整除,小于等于,包含等3关系的表示方法.1)集合表达式

2)关系矩阵

3)关系图接下来的课程,我们将学习关系的运算,关系的性质等.

28作业（清华版）29关系也是集合(其元素为有序对),因此可对关系进行集合的运算,如并∪\交∩\补,从而产生其他新的关系,其运算规则与一般集合一样地进行.7.3关系的运算下面讨论关系的以下运算:

求定义域\值域\域\关系的逆\

关系的复合\关系R在A上的限制\A在R下的像.

以及关系的幂运算30关系的基本运算定义1)定义域domR

:R中所有有序对的第一元素构成的集合:

domR={x|y(<x,y>R)}2)值域ranR:

R中所有有序对的第二元素构成的集合:

ranR={y|x(<x,y>R)}3)R的域fidR: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}31关系的基本运算定义（续）1)关系的逆

R的记作R1={<y,x>|<x,y>R}

求关系的逆就是把其中的有序对颠倒过来.例2R={<1,2>,<2,3>,<1,4>,<2,2>}

={<2,1>,<3,2>,<4,1>,<2,2>}2)关系R和S的复合运算(左复合）

R∘S={<x,y>|

z(<x,z>S<z,y>R)}<x,y>∈R∘S,表示在某”中间变量”z,使x通过S变到z,z再通过R变到y.322)关系R和S的复合运算

R·S={<x,y>|

z(<x,z>S<z,y>R)}<x,y>∈R∘S,表示在某”中间变量”z,使x通过S变到z,z再通过R变到y.x------>z------->ySR33关系的复合运算的两种定义左复合（本教材采用）：

R·S={<x,y>|

z(<x,z>S<z,y>R)}

右复合：

R·S={<x,y>|

z(<x,z>R<z,y>S)}两种定义都是合理的，性质一样，但结果不同34利用关系图求关系的复合:

利用R和S的关系图求关系的复合:

R·S

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

S·R

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

S={<1,1>,<1,3>,<2,3>,<3,2>,<3,3>}SRRS35例:设F是由A={1,2,3,4}到B={2,3,4}的关系

G是由B到C={3,5,6}的关系.分别定义为F={<a,b>|a+b=6}={<2,4>,<3,3>,<4,2>}G={<b,c>|b整除c}={<2,6>,<3,6>,<3,3>}求复合关系F·G36限制与像关系F在A上的限制

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

xA}含义:表示F对A中元素的作用----第一元素xA对应的有序对.例1:R={<1,2>,<2,3>,<1,4>,<2,2>}A={1},

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

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

R↾=A在F下的像:即F在A上的限制的值域

F[A]=ran(F↾A)实例

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

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

求A在F下的像的步骤,应1)先求出F在A上的限制,2)再求出其值域.注意：F↾AF,F[A]ranF

37例4.6:R在A上的限制，A在R下的像设F,G是N上的关系，定义

F={(x,y>|x,y∈N∧y=x*x}G={<x,y>|x,y∈N∧y=x+1}

求：G的逆，F↾{1,2}，F[{1,2}]38例4.6(复合运算）设F,G是N上的关系，定义

F={(x,y>|x,y∈N∧y=x*x}G={<x,y>|x,y∈N∧y=x+1}

求：F·G,

x------>z------->yGFx+1=zy=z*z

F·G=y=z*z=(x+1)(x+1)39关系基本运算的性质定理1设F是任意的关系,则(1)(F1)1=F(2)domF1=ranF,ranF1=domF证(1)任取<x,y>,由逆的定义有<x,y>∈(F

1)1<y,x>∈F1<x,y>∈F所以有(F1)1=F(2)任取x,x∈domF1y(<x,y>∈F1)y(<y,x>∈F)

x∈ranF

所以有domF1=ranF.同理可证ranF1=domF.40定理2设F,G,H是任意的关系,则

(1)(F∘G)∘H=F∘(G∘H)(2)(F∘G)1=G1∘F1证(1)任取<x,y>,<x,y>(F∘G)∘Ht(<x,t>∈F∘G∧<t,y>∈H)t(s(<x,s>∈F∧<s,t>∈G)∧<t,y>∈H)

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

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

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

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

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

41(2)任取<x,y>,<x,y>∈(F∘G)1

<y,x>∈F∘G

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

t(<x,t>∈G1∧(t,y)∈F1)

<x,y>∈G1∘F1

所以(F∘G)1=G1∘F1

关系基本运算的性质（续）

42A上关系的幂运算设R为A上的关系,n为自然数,则R的n次幂定义为：

(1)R0={<x,x>|x∈A}=IA,即为A上的恒等关系

(2)Rn+1=Rn∘R

注意：对于A上的任何关系R1和R2都有

R10=R20=IA

对于A上的任何关系R都有

R1=R43幂的求法1-图解法(主要考虑n>=2时)例:设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}求={<a,a>,<b,b>,<c,c>,<d,d>}=R可按下图解法求得:={<a,a>,<a,c>,<b,b>,<b,d>}44幂的求法2-关系矩阵相乘法1)首先求出R的关系矩阵M2)的关系矩阵M2=M*M3)R3的关系矩阵M3=M2*M4)R4的关系矩阵M4=M3*M…5)矩阵乘法时,第i行第j列的元素满足:rij=ri1*r1j+ri2r2j+ri3*r3j+ri4*r4j相加采用的是逻辑加:1+1=1,1+0=0+1=1,0+0=0例3:设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},解R与R2的关系矩阵分别为r11=0*0+1*1+0*0+0*0=145同理，R0=IA,R3和R4的矩阵分别是：在本例中,如果对n>5继续求幂,就会发现M4=M2,即R4=R2.因此可以得到

R2=R4=R6=…,R3=R5=R7=…

幂的求法（续）可以证明,对于有穷集A和A上的关系R,R的不同次幂只有有限个.幂序列是一个周期性变化的序列,就象正玄函数一样,利用它的周期性可以将R的高次幂化简成R的低次幂.

注:不同的A和R,周期是不同的.46R0,R1,R2,R3,…的关系图如下图所示幂的求法3-关系图法以求为例