第七章 二元关系

第七章二元关系1第一页，共九十九页，编辑于2023年，星期四7.1有序对与笛卡儿积定义7.1由两个元素x和y，按照一定的顺序组成的二元组称为有序对(序偶)，记作<x,y>.有序对性质:(1)有序性<x,y><y,x>（当xy时）(2)<x,y>与<u,v>相等的充分必要条件是<x,y>=<u,v>

x=uy=v.注：与二元集的区别2第二页，共九十九页，编辑于2023年，星期四例已知<x+1,4>=<5,x+y>,求x和y.

3第三页，共九十九页，编辑于2023年，星期四笛卡儿积定义7.2设A,B为集合，A与B的笛卡儿积记作AB，且

AB={<x,y>|xAyB}.例1

A={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={},B=P(A)A={<,>,<{},>}P(A)B=

4第四页，共九十九页，编辑于2023年，星期四笛卡儿积的性质(1)不适合交换律

AB

BA(AB,A,B)(2)不适合结合律(AB)C

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

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

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

(5)若|A|=m,|B|=n,则|AB|=mn

(6)AC∧BDA×BC×D

5第五页，共九十九页，编辑于2023年，星期四性质证明证明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).6第六页，共九十九页，编辑于2023年，星期四性质6的逆命题不成立,分以下情况讨论.(1)当A=B=时,显然有AC和BD成立.(2)当A≠且B≠时,也有AC和BD成立,证明如下：

任取x∈A,由于B≠,必存在y∈B,因此有x∈A∧y∈B<x,y>∈A×B<x,y>∈C×Dx∈C∧y∈Dx∈C从而证明了AC.同理可证BD.

(3)当A=而B≠时,有AC成立,但不一定有BD成立.反例：令A=,B={1},C={3},D={4}.

(4)当A≠而B=时,有BD成立,但不一定有AC成立.

7第七页，共九十九页，编辑于2023年，星期四实例例2(1)证明A=B,C=D

AC=BD

(2)AC=BD是否推出A=B,C=D?为什么？(3)A×B=A×CB=C(4)A-(B×C)=(A-B)×(A-C)(5)存在集合A,使得AA×A解(1)任取<x,y><x,y>AC

xAyC

xByD<x,y>BD(2)不一定.反例如下：

A={1}，B={2},C=D=,则AC=BD但是A

B.8第八页，共九十九页，编辑于2023年，星期四

解(3)不一定为真.当A=,B={1},C={2}时,有A×B==A×C,但B≠C.

(4)不一定为真.当A=B={1},C={2}时有A-(B×C)={1}–{<1,2>}={1}

(A-B)×(A-C)=×{1}=(5)为真.当A=时有AA×A成立9第九页，共九十九页，编辑于2023年，星期四7.2二元关系定义7.3如果一个集合满足以下条件之一：(1)集合非空,且它的元素都是有序对(2)集合是空集则称该集合为一个二元关系,简称为关系，记作R.如果<x,y>∈R,可记作xRy；如果<x,y>R,则记作x

y实例：R={<1,2>,<a,b>},S={<1,2>,a,b}.R是二元关系,当a,b不是有序对时，S不是二元关系根据上面的记法，可以写1R2,aRb,a

c等.10第十页，共九十九页，编辑于2023年，星期四A到B的关系与A上的关系定义7.4设A,B为集合,A×B的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做A上的二元关系.例3

A={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个不同的二元关系.11第十一页，共九十九页，编辑于2023年，星期四A上重要关系的实例定义7.5设A为集合,(1)是A上的关系，称为空关系(2)

全域关系

EA={<x,y>|x∈A∧y∈A}=A×A恒等关系IA

={<x,x>|x∈A}小于等于关系LA

={<x,y>|x,y∈A∧x≤y},A为实数子集

整除关系DB={<x,y>|x,y∈B∧x整除y},A为非0整数子集

包含关系R={<x,y>|x,y∈A∧xy},A是集合族.12第十二页，共九十九页，编辑于2023年，星期四实例例如,A={1,2},则

EA

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

IA

={<1,1>,<2,2>}例如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}>}

类似的还可以定义：大于等于关系,小于关系,大于关系,真包含关系等.13第十三页，共九十九页，编辑于2023年，星期四关系的表示1.关系矩阵若A={x1,x2,…,xm}，B={y1,y2,…,yn}，R是从A到B的关系，R的关系矩阵是布尔矩阵MR=[rij

]mn,其中

rij

=1<xi,yj>R.即则14第十四页，共九十九页，编辑于2023年，星期四关系的表示2.关系图若A={x1,x2,…,xm}，R是从A上的关系，R的关系图是GR=<A,E>,其中A为结点集，E为边集.如果<xi,xj>属于关系R，在图中就有一条从xi到xj的有向边.注意：关系矩阵适合表示从A到B的关系或A上的关系（A,B为有穷集）关系图适合表示有穷集A上的关系即<xi,xj>∈ExiRxj

15第十五页，共九十九页，编辑于2023年，星期四实例例4A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R的关系矩阵MR和关系图GR如下：16第十六页，共九十九页，编辑于2023年，星期四7.3关系的运算**基本概念1.定义域、值域、域、逆关系

关系的基本运算有七种,分别定义如下：

定义7.6设R是二元关系.

(1)R中所有的有序对的第一元素构成的集合称为R的定义域,记为domR.形式化表示为：

domR={x|y(<x,y>R)}

17第十七页，共九十九页，编辑于2023年，星期四

(2)R中所有有序对的第二元素构成的集合称为R的值域,记作ranR.形式化表示为

ranR={y|x(<x,y>∈R)}(3)R的定义域和值域的并集称为R的域,记作fldR.形式化表示为

fldR=domR∪ranR例5设R={<1,2>,<1,3>,<2,4>,<4,3>},则

domR={1,2,4}

ranR={2,3,4}

fldR={1,2,3,4}7.3关系的运算18第十八页，共九十九页，编辑于2023年，星期四关系运算(逆与合成)定义7.7关系的逆运算R1={<y,x>|<x,y>R}定义7.8关系的合成运算RS={<x,z>|

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

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

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

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

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

SR={<1,2>,<1,4>,<3,2>,<3,3>}19第十九页，共九十九页，编辑于2023年，星期四合成的图示法利用图示（不是关系图）方法求合成

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

SR={<1,2>,<1,4>,<3,2>,<3,3>}20第二十页，共九十九页，编辑于2023年，星期四关系运算(限制与像)定义7.9设R为二元关系,A是集合(1)R在A上的限制记作R↾A,其中

R↾A={<x,y>|xRy∧x∈A}(2)A在R下的像记作R[A],其中

R[A]=ran(R↾A)说明：R在A上的限制R↾A是R的子关系，即R↾ARA在R下的像R[A]是ranR的子集，即R[A]ranR

21第二十一页，共九十九页，编辑于2023年，星期四实例例7设R={<1,2>,<1,3>,<2,2>,<2,4>,<3,2>},则

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

R↾=

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

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

R[]=

R[{3}]={2}22第二十二页，共九十九页，编辑于2023年，星期四关系运算的性质定理7.1设F是任意的关系,则(1)(F1)1=F(2)domF1=ranF,ranF1=domF证(1)任取<x,y>,由逆的定义有<x,y>∈(F1)1

<y,x>∈F1

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

y(<x,y>∈F1)

y(<y,x>∈F)

x∈ranF

所以有domF1=ranF.同理可证ranF1=domF.23第二十三页，共九十九页，编辑于2023年，星期四定理7.2设F,G,H是任意的关系,则(1)(FG)H=F(GH)(2)(FG)1=G1F1关系运算的性质证(1)任取<x,y>,<x,y>(FG)H

t(<x,t>∈FG∧<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>∈GH)

<x,y>∈F(GH)所以(FG)H=F(GH)24第二十四页，共九十九页，编辑于2023年，星期四证明(2)任取<x,y>,

<x,y>∈(FG)1

<y,x>∈FG

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

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

<x,y>∈G1F1

所以(F

G)1=G1F1

25第二十五页，共九十九页，编辑于2023年，星期四关系运算的性质定理7.3设R为A上的关系,则

RIA=IAR=R证任取<x,y>

<x,y>∈RIA

t(<x,t>∈R∧<t,y>∈IA)

t(<x,t>∈R∧t=y∧y∈A)<x,y>∈R26第二十六页，共九十九页，编辑于2023年，星期四关系运算的性质定理7.4

(1)F(GH)=FG∪FH(2)(G∪H)F=GF∪HF(3)F(G∩H)

FG∩FH(4)(G∩H)F

GF∩HF只证(3)任取<x,y>,

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

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

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

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

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

<x,y>∈FG∧<x,y>∈FH

<x,y>∈FG∩FH所以有F(G∩H)=FG∩FH27第二十七页，共九十九页，编辑于2023年，星期四推广定理7.4的结论可以推广到有限多个关系R(R1∪R2∪…∪Rn)=RR1∪RR2∪…∪RRn

(R1∪R2∪…∪Rn)R=R1R∪R2R∪…∪RnR

R(R1∩R2∩…∩Rn)

RR1∩RR2∩…∩RRn

(R1∩R2∩…∩Rn)R

R1R∩R2R∩…∩RnR

28第二十八页，共九十九页，编辑于2023年，星期四关系运算的性质定理7.5设F为关系,A,B为集合,则(1)F↾(A∪B)=F↾A∪F↾B(2)F[A∪B]=F[A]∪F[B](3)F↾(A∩B)=F↾A∩F↾B(4)F[A∩B]

F[A]∩F[B]

29第二十九页，共九十九页，编辑于2023年，星期四证明证只证(1)和(4).(1)任取<x,y>

<x,y>∈F↾(A∪B)<x,y>∈F∧x∈A∪B<x,y>∈F∧(x∈A∨x∈B)(<x,y>∈F∧x∈A)∨(<x,y>∈F∧x∈B)<x,y>∈F↾A∨<x,y>∈F↾B<x,y>∈F↾A∪F↾B所以有F↾(A∪B)=F↾A∪F↾B.30第三十页，共九十九页，编辑于2023年，星期四证明(4)任取y,y∈F[A∩B]

x(<x,y>∈F∧x∈A∩B)

x(<x,y>∈F∧x∈A∧x∈B)

x((<x,y>∈F∧x∈A)∧(<x,y>∈F∧x∈B))

x(<x,y>∈F∧x∈A)∧x(<x,y>∈F∧x∈B)

y∈F[A]∧y∈F[B]

y∈F[A]∩F[B]

所以有F[A∩B]=F[A]∩F[B].31第三十一页，共九十九页，编辑于2023年，星期四关系的幂运算定义7.10设R为A上的关系,n为自然数,则R的n次幂定义为：(1)R0={<x,x>|x∈A}=IA(2)

Rn+1=RnR注意：对于A上的任何关系R1和R2都有R10=R20=IA

对于A上的任何关系R都有R1=R32第三十二页，共九十九页，编辑于2023年，星期四

例8设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R的各次幂,分别用矩阵和关系图表示.解R与R2的关系矩阵分别是：幂的求法33第三十三页，共九十九页，编辑于2023年，星期四R3和R4的矩阵是：因此M4=M2,即R4=R2.因此可以得到

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

R0的关系矩阵是幂的求法34第三十四页，共九十九页，编辑于2023年，星期四关系图R0,R1,R2,R3,…的关系图如下图所示.R0R1R2=R4=…R3=R5=…35第三十五页，共九十九页，编辑于2023年，星期四幂运算的性质定理7.6设A为n元集,R是A上的关系,则存在自然数s和t,使得Rs=Rt.证R为A上的关系,由于|A|=n,A上的不同关系只有个.列出R的各次幂R0,R1,R2,…,,…,必存在自然数s和t使得Rs=Rt36第三十六页，共九十九页，编辑于2023年，星期四定理7.7设R是A上的关系,m,n∈N,则(1)RmRn=Rm+n(2)(Rm)n=Rmn

幂运算的性质证用归纳法(1)对于任意给定的m∈N,施归纳于n.若n=0,则有

RmR0=RmIA=Rm=Rm+0

假设RmRn=Rm+n,则有

RmRn+1

=Rm(RnR)=(RmRn)R=Rm+n+1,所以对一切m,n∈N有RmRn=Rm+n.37第三十七页，共九十九页，编辑于2023年，星期四证明(2)对于任意给定的m∈N,施归纳于n.若n=0,则有(Rm)0=IA=R0

=Rm×0

假设(Rm)n=Rmn,则有(Rm)n+1

=(Rm)nRm=(Rmn)Rn=Rmn+m=Rm(n+1)所以对一切m,n∈N有(Rm)n=Rmn.38第三十八页，共九十九页，编辑于2023年，星期四定理7.8设R是A上的关系,若存在自然数s,t(s<t)使得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幂运算的性质证(1)Rs+k=RsRk=RtRk=Rt+k(2)对k归纳.若k=0,则有Rs+0p+i=Rs+i假设Rs+kp+i=Rs+i,其中p=ts,则

Rs+(k+1)p+i=Rs+kp+i+p=Rs+kp+iRp

=Rs+iRp=Rs+p+i=Rs+ts+i=Rt+i=Rs+i

由归纳法命题得证.39第三十九页，共九十九页，编辑于2023年，星期四证明(3)任取q∈N,

若q<t,

显然有Rq∈S,

若q≥t,则存在自然数k和i使得

q=s+kp+i,其中0≤i≤p1.于是

Rq=Rs+kp+i=Rs+i

而

s+i≤s+p1=s+ts1=t1从而证明了

Rq∈S.40第四十页，共九十九页，编辑于2023年，星期四7.4关系的性质定义7.11设R为A上的关系,(1)若x(x∈A→<x,x>R),则称R在A上是自反的.(2)若x(x∈A→<x,x>R),则称R在A上是反自反的.实例：自反：全域关系EA,恒等关系IA,小于等于关系LA,整除关系DA反自反：实数集上的小于关系、幂集上的真包含关系.

A={1,2,3},R1,R2,R3是A上的关系,其中R1＝{<1,1>,<2,2>}R2＝{<1,1>,<2,2>,<3,3>,<1,2>}R3＝{<1,3>}R2自反，R3反自反，R1既不是自反的也不是反自反的.41第四十一页，共九十九页，编辑于2023年，星期四对称性与反对称性定义7.12设R为A上的关系,

(1)若xy(x,y∈A∧<x,y>∈R→<y,x>∈R),则称R为A上对称的关系.(2)若xy(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y),则称R为A上的反对称关系.实例：对称关系：A上的全域关系EA,恒等关系IA和空关系反对称关系：恒等关系IA和空关系也是A上的反对称关系.设A＝{1,2,3},R1,R2,R3和R4都是A上的关系,其中R1＝{<1,1>,<2,2>}，R2＝{<1,1>,<1,2>,<2,1>}R3＝{<1,2>,<1,3>}，R4＝{<1,2>,<2,1>,<1,3>}

R1：对称和反对称；R2：只有对称；R3：只有反对称；

R4：不对称、不反对称42第四十二页，共九十九页，编辑于2023年，星期四传递性定义7.13设R为A上的关系,若

xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),则称R是A上的传递关系.实例：A上的全域关系EA,恒等关系IA和空关系，小于等于和小于关系，整除关系，包含与真包含关系设A＝{1,2,3},R1,R2,R3是A上的关系,其中R1＝{<1,1>,<2,2>}

R2＝{<1,2>,<2,3>}

R3＝{<1,3>}R1和R3是A上的传递关系,R2不是A上的传递关系.43第四十三页，共九十九页，编辑于2023年，星期四关系性质成立的充要条件定理7.9设R为A上的关系,则(1)R在A上自反当且仅当IAR(2)R在A上反自反当且仅当R∩IA=(3)R在A上对称当且仅当R=R1(4)R在A上反对称当且仅当R∩R1IA(5)R在A上传递当且仅当RRR44第四十四页，共九十九页，编辑于2023年，星期四证明证明只证(1)(1)必要性任取<x,y>,由于R在A上自反必有

<x,y>∈IA

x,y∈A∧x=y<x,y>∈R从而证明了IAR充分性.任取x,有

x∈A<x,x>∈IA

<x,x>∈R因此R在A上是自反的.45第四十五页，共九十九页，编辑于2023年，星期四自反性反自反性对称性反对称性传递性集合IARR∩IA=R=R1R∩R1IARRR关系矩阵主对角线元素全是1主对角线元素全是0矩阵是对称矩阵若rij＝1,且i≠j,则rji＝0M2中1位置,M中相应位置都是1关系图每个顶点都有环每个顶点都没有环两点之间有边,是一对方向相反的边两点之间有边,是一条有向边点xi到xj有边,xj到xk有边,则xi到xk也有边关系性质的三种等价条件46第四十六页，共九十九页，编辑于2023年，星期四例7.13设A是集合,R1和R2是A上的关系,证明：

（1）若R1,R2是自反的和对称的,则R1∪R2也是自反的和对称的.

（2）若R1和R2是传递的,则R1∩R2也是传递的.

47第四十七页，共九十九页，编辑于2023年，星期四证

（1）由于R1和R2是A上的自反关系,故有

IAR1和IA

R2，从而得到IA

R1∪R2.根据定理7.9可知R1∪R2在A上是自反的.

再由R1和R2的对称性有

R1=R1-1和R2=R2-1

根据本章习题第20题的结果有

(R1∪R2)-1=R1-1∪R2-1=R1∪R2

从而证明了R1∪R2也是A上对称的关系.

48第四十八页，共九十九页，编辑于2023年，星期四

（2）由R1和R2的传递性有

R1oR1R1和R2oR2R2

再使用定理7.4得

(R1∩R2)o(R1∩R2)

R1oR1∩R1oR2∩R2oR1∩R2oR2

(R1∩R2)∩R1oR2∩R2oR1(将前面的包含式代入)

R1∩R2

从而证明了R1∩R2也是A上的传递关系49第四十九页，共九十九页，编辑于2023年，星期四自反性反自反性对称性反对称性传递性R11

√√√√√R1∩R2

√√√√√R1∪R2

√√√××R1R2

×√√√×R1

R2

√××××关系的性质和运算之间的联系50第五十页，共九十九页，编辑于2023年，星期四例7.14判断图7.3中关系的性质,并说明理由.

51第五十一页，共九十九页，编辑于2023年，星期四解

（1）该关系是对称的,因为无单向边.它不是自反的也不是反自反的.因为有的顶点有环,有的顶点无环.它不是反对称的,因为图中有双向边.它也不是传递的,因为图中有边<3,1>和<1,3>,但没有从3到3的边,即通过3的环.

（2）该关系是反自反的但不是自反的,因为每个顶点都没有环.它是反对称的但不是对称的,因为图中只有单向边.它也是传递的,因为不存在顶点x,y,z,使得x到y有边,y到z有边,但x到z没有边,其中x,y,z∈{1,2,3}.

（3）该关系是自反的但不是反自反的,因为每个顶点都有环.它是反对称的但不是对称的,因为图中只有单向边.但他不是传递的,因为2到1有边,1到3有边,但2到3没有边.52第五十二页，共九十九页，编辑于2023年，星期四7.5关系的闭包

主要内容闭包定义闭包的构造方法集合表示矩阵表示图表示闭包的性质53第五十三页，共九十九页，编辑于2023年，星期四闭包定义定义7.14设R是非空集合A上的关系,R的自反(对称或传递)闭包是A上的关系R,使得R满足以下条件：(1)R是自反的(对称的或传递的)(2)RR(3)对A上任何包含R的自反(对称或传递)关系R有RRR的自反闭包记作r(R),对称闭包记作s(R),传递闭包记作t(R).定理7.10设R为A上的关系,则有(1)r(R)=R∪R0(2)s(R)=R∪R1(3)t(R)=R∪R2∪R3∪…说明：对有穷集A(|A|=n)上的关系,(3)中的并最多不超过Rn54第五十四页，共九十九页，编辑于2023年，星期四证明证只证(1)和(3).(1)由IA=R0R∪R0知R∪R0是自反的,且满足RR∪R0设R是A上包含R的自反关系,则有RR

和IAR

.从而有R∪R0R.R∪R0满足闭包定义,所以r(R)=R∪R0.(3)先证R∪R2∪…t(R)成立.用归纳法证明对任意正整数n有Rnt(R).n=1时有R1=Rt(R).假设Rnt(R)成立,那么对任意的<x,y>

<x,y>∈Rn+1=RnR

t(<x,t>∈Rn∧<t,y>∈R)

t(<x,t>∈t(R)∧<t,y>∈t(R))<x,y>∈t(R)这就证明了Rn+1t(R).由归纳法命题得证.

55第五十五页，共九十九页，编辑于2023年，星期四证明再证t(R)R∪R2∪…成立,为此只须证明R∪R2∪…传递.任取<x,y>,<y,z>,则

<x,y>∈R∪R2∪…∧<y,z>∈R∪R2∪…

t(<x,y>∈Rt)∧s(<y,z>∈Rs)

ts(<x,z>∈RtRs)

ts(<x,z>∈Rt+s)

<x,z>∈R∪R2∪…从而证明了R∪R2∪…是传递的.56第五十六页，共九十九页，编辑于2023年，星期四闭包的矩阵表示和图表示设关系R,r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms和Mt

则Mr=M+EMs=M+M'Mt=M+M2+M3+…E是单位矩阵,M'是转置矩阵，相加时使用逻辑加.设关系R,r(R),s(R),t(R)的关系图分别记为G,Gr,Gs,Gt,则Gr,Gs,Gt的顶点集与G的顶点集相等.除了G的边以外,以下述方法添加新的边：(1)考察G的每个顶点,若没环就加一个环，得到Gr

(2)考察G的每条边,若有一条xi到xj的单向边,i≠j,则在G中加一条xj到xi的反向边,得到Gs(3)考察G的每个顶点xi,找xi可达的所有顶点xj(允许i=j)，

如果没有从xi到xj

的边,就加上这条边,得到图Gt57第五十七页，共九十九页，编辑于2023年，星期四实例例9设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},R和r(R),s(R),t(R)的关系图如下图所示.Rr(R)s(R)t(R)58第五十八页，共九十九页，编辑于2023年，星期四闭包的性质定理7.11设R是非空集合A上的关系,则(1)R是自反的当且仅当r(R)=R.(2)R是对称的当且仅当s(R)=R.(3)R是传递的当且仅当t(R)=R.定理7.12设R1和R2是非空集合A上的关系,且R1R2,则(1)r(R1)r(R2)(2)s(R1)s(R2)(3)t(R1)t(R2)证明略59第五十九页，共九十九页，编辑于2023年，星期四定理7.13设R是非空集合A上的关系,(1)若R是自反的,则s(R)与t(R)也是自反的(2)若R是对称的,则r(R)与t(R)也是对称的(3)若R是传递的,则r(R)是传递的.说明：如果需要进行多个闭包运算，比如求R的自反、对称、传递的闭包tsr(R)，运算顺序如下：

闭包的性质60第六十页，共九十九页，编辑于2023年，星期四证（2）

由于R是A上的对称关系,所以R=R-1,同时IA=IA-1.根据(R∪IA)-1=R-1∪IA-1

从而推出r(R)-1=(R∪R0)-1=(R∪IA)-1=R-1∪IA-1=R∪IA=r(R)

这就证明了r(R)是对称的.

61第六十一页，共九十九页，编辑于2023年，星期四命题：若R是对称的,则Rn也是对称的,其中n是任何正整数.

证明用归纳法.

n=1,R1=R显然是对称的.

假设Rn是对称的,则对任意的<x,y>有

<x,y>∈Rn+1

<x,y>∈Rno

R

t((<x,t>)∈Rn∧<t,y>∈R)

t((<t,x>∈Rn∧<y,t>∈R)

<y,x>∈RoRn

<y,x>∈R1+n=Rn+1

所以Rn+1是对称的.由归纳法命题得证.

62第六十二页，共九十九页，编辑于2023年，星期四下面证明t(R)的对称性.

任取<x,y>

<x,y>∈t(R)

n(<x,y>∈Rn)

n(<y,x>∈Rn)（因为Rn是对称的）

<y,x>∈t(R)

从而证明了t(R)的对称性.

63第六十三页，共九十九页，编辑于2023年，星期四

定理7.13讨论了关系性质和闭包运算之间的关系.如果关系R是自反的和对称的,那么经过求闭包的运算以后所得到的关系仍就是自反的和对称的.但是对于传递的关系则不然.它的自反闭包仍旧保持传递性,而对称闭包就有可能失去传递性.

64第六十四页，共九十九页，编辑于2023年，星期四7.6等价关系与划分

主要内容等价关系的定义与实例等价类及其性质商集与集合的划分等价关系与划分的一一对应65第六十五页，共九十九页，编辑于2023年，星期四等价关系的定义与实例定义7.15设R为非空集合上的关系.如果R是自反的、对称的和传递的,则称R为A上的等价关系.设R是一个等价关系,若<x,y>∈R,称x等价于y,记做x～y.实例设A={1,2,…,8},如下定义A上的关系R：

R={<x,y>|x,y∈A∧x≡y(mod3)}其中x≡y(mod3)叫做x与y模3相等,即x除以3的余数与y除以3的余数相等.不难验证R为A上的等价关系,因为(1)x∈A,有x≡x(mod3)(2)x,y∈A,若x≡y(mod3),则有y≡x(mod3)(3)x,y,z∈A,若x≡y(mod3),y≡z(mod3),则有x≡z(mod3)

66第六十六页，共九十九页，编辑于2023年，星期四模3等价关系的关系图等价关系的实例67第六十七页，共九十九页，编辑于2023年，星期四把模3的等价关系推广,对任何正整数n可以定义整数集合Z上模n的等价关系.

R＝｛<x,y>|x,y∈Z∧x≡y(modn)}例如,当n＝5时,整数之间的等价性满足:…～－10～－5～0～5～10～……～－9～－4～1～6～11～……～－8～－3～2～7～12～……～－7～－2～3～8～13～……～－6～－1～4～9～14～….68第六十八页，共九十九页，编辑于2023年，星期四等价类定义定义7.16设R为非空集合A上的等价关系,x∈A，令[x]R

={y|y∈A∧xRy}称[x]R为x关于R的等价类,简称为x的等价类,简记为[x]或实例A={1,2,…,8}上模3等价关系的等价类：[1]=[4]=[7]={1,4,7}[2]=[5]=[8]={2,5,8}[3]=[6]={3,6}69第六十九页，共九十九页，编辑于2023年，星期四等价类的性质定理7.14设R是非空集合A上的等价关系,则(1)xA,[x]是A的非空子集(2)x,yA,如果xRy,则[x]=[y](3)x,yA,如果x

y,则[x]与[y]不交(4)∪{[x]|xA}=A证(1)由定义,xA有[x]A.又x[x],即[x]非空.(2)任取z,则有

z∈[x]

<x,z>∈R

<z,x>∈R<z,x>R∧<x,y>R

<z,y>R

<y,z>R从而证明了z∈[y].综上所述必有[x][y].同理可证[y][x].这就得到了[x]=[y].70第七十页，共九十九页，编辑于2023年，星期四商集与划分定义7.17设R为非空集合A上的等价关系,以R的所有等价类作为元素的集合称为A关于R的商集,记做A/R,

A/R={[x]R|x∈A}实例(1)设A={1,2,…,8}，A关于模3等价关系R的商集为

A/R={{1,4,7},{2,5,8},{3,6}}A关于恒等关系和全域关系的商集为：

A/IA

={{1},{2},…,{8}}，A/EA

={{1,2,…,8}}(2)在整数集合z上模n的等价关系的商集是{{nz+i|zZ}|i=0,1,…n-1}71第七十一页，共九十九页，编辑于2023年，星期四商集与划分定义7.18设A为非空集合,若A的子集族π(π

P(A))满足:(1)

π(2)xy(x,yπ∧x≠y→x∩y=)(3)∪π=A则称π是A的一个划分,称π中的元素为A的划分块.72第七十二页，共九十九页，编辑于2023年，星期四划分实例

例10设A＝{a,b,c,d},给定1,2,3,4,5,6如下：

1={{a,b,c},{d}}

2={{a,b},{c},{d}}

3={{a},{a,b,c,d}}

4={{a,b},{c}}

5={,{a,b},{c,d}}

6={{a,{a}},{b,c,d}}

则1和2是A的划分,其他都不是A的划分.73第七十三页，共九十九页，编辑于2023年，星期四例11给出A＝{1,2,3}上所有的等价关系实例1231

12351232123412331对应EA,5对应IA,2,3和

4分别对应R2,R3和R4.

R2={<2,3>,<3,2>}∪IA

R3={<1,3>,<3,1>}∪IA

R4={<1,2>,<2,1>}∪IA解先做出A的划分,从左到右分别记作1,2,3,4,5.74第七十四页，共九十九页，编辑于2023年，星期四练习11．设A={1,2,3},R={<x,y>|x,yA且x+2y

6}，S={<1,2>,<1,3>,<2,2>},求:(1)R的集合表达式(2)R1(3)domR,ranR,fldR(4)RS,R3(5)r(R),s(R),t(R)75第七十五页，共九十九页，编辑于2023年，星期四解答(1)R={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>}(2)R1={<1,1>,<2,1>,<1,2>,<2,2>,<1,3>}(3)domR={1,2,3},ranR={1,2},fldR={1,2,3}(4)RS={<1,2>,<1,3>,<2,2>,<2,3>,<3,2>,<3,3>}R3={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>}(5)r(R)={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,3>}

s(R)={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<1,3>}

t(R)={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>}76第七十六页，共九十九页，编辑于2023年，星期四练习22．设A={1,2,3,4}，在AA上定义二元关系R：<<x,y>,<u,v>>R

x+y=u+v，求R导出的划分.AA={<1,1>,<1,2>,<1,3>,<1,4>,<2,1>,<2,2>,<2,3>,<2,4>,<3,1>,<3,2>,<3,3>,<3,4>,<4,1>,<4,2>,<4,3>,<4,4>}根据<x,y>中的x+y=2,3,4,5,6,7,8将A划分成等价类：

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

77第七十七页，共九十九页，编辑于2023年，星期四3．设R是Z上的模n等价关系,即xy

x

y(modn),试给出由R确定的Z的划分.练习3解设除以n余数为r的整数构成等价类[r]，则[r]={kn+r|kZ},r=0,1,…,n1

={[r]|r=0,1,…,n1}

78第七十八页，共九十九页，编辑于2023年，星期四练习44．设R是A上的二元关系，设S={<a,b>|c(<a,c>R<c,b>R)}.证明如果R是等价关系，则S也是等价关系。证R是A上的等价关系.(1)证自反任取x,xA<x,x>R

x(<x,x>R<x,x>R)<x,x>S(2)证对称任取<x,y>,<x,y>S

c(<x,c>R<c,y>R)

c(<c,x>R<y,c>R)<y,x>S

(3)证传递任取<x,y>,<y,z>,<x,y>S<y,z>S

c(<x,c>R<c,y>R)

d(<y,d>R<d,z>R)<x,y>R<y,z>

R<x,z>S79第七十九页，共九十九页，编辑于2023年，星期四关系性质的证明方法1.证明R在A上自反任取x,xA

……..….…….<x,x>R前提推理过程结论2.证明R在A上对称任取<x,y>，

<x,y>R

……………….<y,x>R

前提推理过程结论80第八十页，共九十九页，编辑于2023年，星期四3.证明R在A上反对称任取<x,y>，<x,y>R<y,x>R

……..

x=y

前提推理过程结论4.证明R在A上传递任取<x,y>,<y,z>，<x,y>R<y,z>R

……..<x,z>R

前提推理过程结论关系性质的证明方法81第八十一页，共九十九页，编辑于2023年，星期四5．R,S为A上的关系，证明RS

t(R)t(S)练习5证只需证明对于任意正整数n,RnSn.对n归纳.n=1,显然为真.假设对于n，命题为真，任取<x,y><x,y>Rn+1<x,y>Rn∘R

t(<x,t>Rn<t,y>R)

t(<x,t>Sn<t,y>S)<x,y>Sn∘S

<x,y>Sn+1

82第八十二页，共九十九页，编辑于2023年，星期四数学归纳法（主要用于幂运算）证明中用到关系运算的定义和公式,如：

xdomR

y(<x,y>R)yranR

x(<x,y>R)<x,y>R

<y,x>R1<x,y>R∘S

t(<x,t>R<t,y>S)<x,y>R↾A

xA<x,y>RyRA]

x(xA<x,y>R)r(R)=RIAs(R)=RR1t(R)=RR2…关系等式或包含式的证明方法83第八十三页，共九十九页，编辑于2023年，星期四7.7偏序关系定义7.19偏序关系：非空集合A上的自反、反对称和传递的关系，记作≼.设≼为偏序关系,如果<x,y>∈≼,则记作x≼y,读作x“小于或等于”y.实例集合A上的恒等关系IA，空关系是A上的偏序关系.小于(大于)或等于关系,整除关系和包含关系也是相应集合上的偏