第七章 二元關(guān)系

第七章二元關(guān)系1第一頁，共九十九頁，編輯于2023年，星期四7.1有序?qū)εc笛卡兒積定義7.1由兩個(gè)元素x和y，按照一定的順序組成的二元組稱為有序?qū)?序偶)，記作<x,y>.有序?qū)π再|(zhì):(1)有序性<x,y><y,x>（當(dāng)xy時(shí)）(2)<x,y>與<u,v>相等的充分必要條件是<x,y>=<u,v>

x=uy=v.注：與二元集的區(qū)別2第二頁，共九十九頁，編輯于2023年，星期四例已知<x+1,4>=<5,x+y>,求x和y.

3第三頁，共九十九頁，編輯于2023年，星期四笛卡兒積定義7.2設(shè)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年，星期四笛卡兒積的性質(zhì)(1)不適合交換律

AB

BA(AB,A,B)(2)不適合結(jié)合律(AB)C

A(BC)(A,B,C)(3)對(duì)于并或交運(yùn)算滿足分配律

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

A(BC)=(AB)(AC)(BC)A=(BA)(CA)(4)若A或B中有一個(gè)為空集，則AB就是空集.A=B=

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

(6)AC∧BDA×BC×D

5第五頁，共九十九頁，編輯于2023年，星期四性質(zhì)證明證明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年，星期四性質(zhì)6的逆命題不成立,分以下情況討論.(1)當(dāng)A=B=時(shí),顯然有AC和BD成立.(2)當(dāng)A≠且B≠時(shí),也有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)當(dāng)A=而B≠時(shí),有AC成立,但不一定有BD成立.反例：令A(yù)=,B={1},C={3},D={4}.

(4)當(dāng)A≠而B=時(shí),有BD成立,但不一定有AC成立.

7第七頁，共九十九頁，編輯于2023年，星期四實(shí)例例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)不一定為真.當(dāng)A=,B={1},C={2}時(shí),有A×B==A×C,但B≠C.

(4)不一定為真.當(dāng)A=B={1},C={2}時(shí)有A-(B×C)={1}–{<1,2>}={1}

(A-B)×(A-C)=×{1}=(5)為真.當(dāng)A=時(shí)有AA×A成立9第九頁，共九十九頁，編輯于2023年，星期四7.2二元關(guān)系定義7.3如果一個(gè)集合滿足以下條件之一：(1)集合非空,且它的元素都是有序?qū)?2)集合是空集則稱該集合為一個(gè)二元關(guān)系,簡稱為關(guān)系，記作R.如果<x,y>∈R,可記作xRy；如果<x,y>R,則記作x

y實(shí)例：R={<1,2>,<a,b>},S={<1,2>,a,b}.R是二元關(guān)系,當(dāng)a,b不是有序?qū)r(shí)，S不是二元關(guān)系根據(jù)上面的記法，可以寫1R2,aRb,a

c等.10第十頁，共九十九頁，編輯于2023年，星期四A到B的關(guān)系與A上的關(guān)系定義7.4設(shè)A,B為集合,A×B的任何子集所定義的二元關(guān)系叫做從A到B的二元關(guān)系,當(dāng)A=B時(shí)則叫做A上的二元關(guān)系.例3

A={0,1},B={1,2,3},那么

R1={<0,2>},R2=A×B,R3=,R4={<0,1>}R1,R2,R3,R4是從A到B的二元關(guān)系,R3和R4也是A上的二元關(guān)系.計(jì)數(shù):|A|=n,|A×A|=n2,A×A的子集有個(gè).所以A上有個(gè)不同的二元關(guān)系.例如|A|=3,則A上有=512個(gè)不同的二元關(guān)系.11第十一頁，共九十九頁，編輯于2023年，星期四A上重要關(guān)系的實(shí)例定義7.5設(shè)A為集合,(1)是A上的關(guān)系，稱為空關(guān)系(2)

全域關(guān)系

EA={<x,y>|x∈A∧y∈A}=A×A恒等關(guān)系IA

={<x,x>|x∈A}小于等于關(guān)系LA

={<x,y>|x,y∈A∧x≤y},A為實(shí)數(shù)子集

整除關(guān)系DB={<x,y>|x,y∈B∧x整除y},A為非0整數(shù)子集

包含關(guān)系R={<x,y>|x,y∈A∧xy},A是集合族.12第十二頁，共九十九頁，編輯于2023年，星期四實(shí)例例如,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},,{a,b}},則A上的包含關(guān)系是

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

類似的還可以定義：大于等于關(guān)系,小于關(guān)系,大于關(guān)系,真包含關(guān)系等.13第十三頁，共九十九頁，編輯于2023年，星期四關(guān)系的表示1.關(guān)系矩陣若A={x1,x2,…,xm}，B={y1,y2,…,yn}，R是從A到B的關(guān)系，R的關(guān)系矩陣是布爾矩陣MR=[rij

]mn,其中

rij

=1<xi,yj>R.即則14第十四頁，共九十九頁，編輯于2023年，星期四關(guān)系的表示2.關(guān)系圖若A={x1,x2,…,xm}，R是從A上的關(guān)系，R的關(guān)系圖是GR=<A,E>,其中A為結(jié)點(diǎn)集，E為邊集.如果<xi,xj>屬于關(guān)系R，在圖中就有一條從xi到xj的有向邊.注意：關(guān)系矩陣適合表示從A到B的關(guān)系或A上的關(guān)系（A,B為有窮集）關(guān)系圖適合表示有窮集A上的關(guān)系即<xi,xj>∈ExiRxj

15第十五頁，共九十九頁，編輯于2023年，星期四實(shí)例例4A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R的關(guān)系矩陣MR和關(guān)系圖GR如下：16第十六頁，共九十九頁，編輯于2023年，星期四7.3關(guān)系的運(yùn)算**基本概念1.定義域、值域、域、逆關(guān)系

關(guān)系的基本運(yùn)算有七種,分別定義如下：

定義7.6設(shè)R是二元關(guān)系.

(1)R中所有的有序?qū)Φ牡谝辉貥?gòu)成的集合稱為R的定義域,記為domR.形式化表示為：

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

17第十七頁，共九十九頁，編輯于2023年，星期四

(2)R中所有有序?qū)Φ牡诙貥?gòu)成的集合稱為R的值域,記作ranR.形式化表示為

ranR={y|x(<x,y>∈R)}(3)R的定義域和值域的并集稱為R的域,記作fldR.形式化表示為

fldR=domR∪ranR例5設(shè)R={<1,2>,<1,3>,<2,4>,<4,3>},則

domR={1,2,4}

ranR={2,3,4}

fldR={1,2,3,4}7.3關(guān)系的運(yùn)算18第十八頁，共九十九頁，編輯于2023年，星期四關(guān)系運(yùn)算(逆與合成)定義7.7關(guān)系的逆運(yùn)算R1={<y,x>|<x,y>R}定義7.8關(guān)系的合成運(yùn)算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年，星期四合成的圖示法利用圖示（不是關(guān)系圖）方法求合成

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

SR={<1,2>,<1,4>,<3,2>,<3,3>}20第二十頁，共九十九頁，編輯于2023年，星期四關(guān)系運(yùn)算(限制與像)定義7.9設(shè)R為二元關(guān)系,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的子關(guān)系，即R?ARA在R下的像R[A]是ranR的子集，即R[A]ranR

21第二十一頁，共九十九頁，編輯于2023年，星期四實(shí)例例7設(shè)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年，星期四關(guān)系運(yùn)算的性質(zhì)定理7.1設(shè)F是任意的關(guān)系,則(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設(shè)F,G,H是任意的關(guān)系,則(1)(FG)H=F(GH)(2)(FG)1=G1F1關(guān)系運(yùn)算的性質(zhì)證(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年，星期四關(guān)系運(yùn)算的性質(zhì)定理7.3設(shè)R為A上的關(guān)系,則

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年，星期四關(guān)系運(yùn)算的性質(zhì)定理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的結(jié)論可以推廣到有限多個(gè)關(guān)系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年，星期四關(guān)系運(yùn)算的性質(zhì)定理7.5設(shè)F為關(guān)系,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年，星期四關(guān)系的冪運(yùn)算定義7.10設(shè)R為A上的關(guān)系,n為自然數(shù),則R的n次冪定義為：(1)R0={<x,x>|x∈A}=IA(2)

Rn+1=RnR注意：對(duì)于A上的任何關(guān)系R1和R2都有R10=R20=IA

對(duì)于A上的任何關(guān)系R都有R1=R32第三十二頁，共九十九頁，編輯于2023年，星期四

例8設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R的各次冪,分別用矩陣和關(guān)系圖表示.解R與R2的關(guān)系矩陣分別是：冪的求法33第三十三頁，共九十九頁，編輯于2023年，星期四R3和R4的矩陣是：因此M4=M2,即R4=R2.因此可以得到

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

R0的關(guān)系矩陣是冪的求法34第三十四頁，共九十九頁，編輯于2023年，星期四關(guān)系圖R0,R1,R2,R3,…的關(guān)系圖如下圖所示.R0R1R2=R4=…R3=R5=…35第三十五頁，共九十九頁，編輯于2023年，星期四冪運(yùn)算的性質(zhì)定理7.6設(shè)A為n元集,R是A上的關(guān)系,則存在自然數(shù)s和t,使得Rs=Rt.證R為A上的關(guān)系,由于|A|=n,A上的不同關(guān)系只有個(gè).列出R的各次冪R0,R1,R2,…,,…,必存在自然數(shù)s和t使得Rs=Rt36第三十六頁，共九十九頁，編輯于2023年，星期四定理7.7設(shè)R是A上的關(guān)系,m,n∈N,則(1)RmRn=Rm+n(2)(Rm)n=Rmn

冪運(yùn)算的性質(zhì)證用歸納法(1)對(duì)于任意給定的m∈N,施歸納于n.若n=0,則有

RmR0=RmIA=Rm=Rm+0

假設(shè)RmRn=Rm+n,則有

RmRn+1

=Rm(RnR)=(RmRn)R=Rm+n+1,所以對(duì)一切m,n∈N有RmRn=Rm+n.37第三十七頁，共九十九頁，編輯于2023年，星期四證明(2)對(duì)于任意給定的m∈N,施歸納于n.若n=0,則有(Rm)0=IA=R0

=Rm×0

假設(shè)(Rm)n=Rmn,則有(Rm)n+1

=(Rm)nRm=(Rmn)Rn=Rmn+m=Rm(n+1)所以對(duì)一切m,n∈N有(Rm)n=Rmn.38第三十八頁，共九十九頁，編輯于2023年，星期四定理7.8設(shè)R是A上的關(guān)系,若存在自然數(shù)s,t(s<t)使得Rs=Rt,則(1)對(duì)任何k∈N有Rs+k=Rt+k

(2)對(duì)任何k,i∈N有Rs+kp+i=Rs+i,其中p=ts(3)令S={R0,R1,…,Rt1},則對(duì)于任意的q∈N有Rq∈S冪運(yùn)算的性質(zhì)證(1)Rs+k=RsRk=RtRk=Rt+k(2)對(duì)k歸納.若k=0,則有Rs+0p+i=Rs+i假設(shè)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,則存在自然數(shù)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關(guān)系的性質(zhì)定義7.11設(shè)R為A上的關(guān)系,(1)若x(x∈A→<x,x>R),則稱R在A上是自反的.(2)若x(x∈A→<x,x>R),則稱R在A上是反自反的.實(shí)例：自反：全域關(guān)系EA,恒等關(guān)系IA,小于等于關(guān)系LA,整除關(guān)系DA反自反：實(shí)數(shù)集上的小于關(guān)系、冪集上的真包含關(guān)系.

A={1,2,3},R1,R2,R3是A上的關(guān)系,其中R1＝{<1,1>,<2,2>}R2＝{<1,1>,<2,2>,<3,3>,<1,2>}R3＝{<1,3>}R2自反，R3反自反，R1既不是自反的也不是反自反的.41第四十一頁，共九十九頁，編輯于2023年，星期四對(duì)稱性與反對(duì)稱性定義7.12設(shè)R為A上的關(guān)系,

(1)若xy(x,y∈A∧<x,y>∈R→<y,x>∈R),則稱R為A上對(duì)稱的關(guān)系.(2)若xy(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y),則稱R為A上的反對(duì)稱關(guān)系.實(shí)例：對(duì)稱關(guān)系：A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系反對(duì)稱關(guān)系：恒等關(guān)系IA和空關(guān)系也是A上的反對(duì)稱關(guān)系.設(shè)A＝{1,2,3},R1,R2,R3和R4都是A上的關(guān)系,其中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：對(duì)稱和反對(duì)稱；R2：只有對(duì)稱；R3：只有反對(duì)稱；

R4：不對(duì)稱、不反對(duì)稱42第四十二頁，共九十九頁，編輯于2023年，星期四傳遞性定義7.13設(shè)R為A上的關(guān)系,若

xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),則稱R是A上的傳遞關(guān)系.實(shí)例：A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系，小于等于和小于關(guān)系，整除關(guān)系，包含與真包含關(guān)系設(shè)A＝{1,2,3},R1,R2,R3是A上的關(guān)系,其中R1＝{<1,1>,<2,2>}

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

R3＝{<1,3>}R1和R3是A上的傳遞關(guān)系,R2不是A上的傳遞關(guān)系.43第四十三頁，共九十九頁，編輯于2023年，星期四關(guān)系性質(zhì)成立的充要條件定理7.9設(shè)R為A上的關(guān)系,則(1)R在A上自反當(dāng)且僅當(dāng)IAR(2)R在A上反自反當(dāng)且僅當(dāng)R∩IA=(3)R在A上對(duì)稱當(dāng)且僅當(dāng)R=R1(4)R在A上反對(duì)稱當(dāng)且僅當(dāng)R∩R1IA(5)R在A上傳遞當(dāng)且僅當(dāng)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年，星期四自反性反自反性對(duì)稱性反對(duì)稱性傳遞性集合IARR∩IA=R=R1R∩R1IARRR關(guān)系矩陣主對(duì)角線元素全是1主對(duì)角線元素全是0矩陣是對(duì)稱矩陣若rij＝1,且i≠j,則rji＝0M2中1位置,M中相應(yīng)位置都是1關(guān)系圖每個(gè)頂點(diǎn)都有環(huán)每個(gè)頂點(diǎn)都沒有環(huán)兩點(diǎn)之間有邊,是一對(duì)方向相反的邊兩點(diǎn)之間有邊,是一條有向邊點(diǎn)xi到xj有邊,xj到xk有邊,則xi到xk也有邊關(guān)系性質(zhì)的三種等價(jià)條件46第四十六頁，共九十九頁，編輯于2023年，星期四例7.13設(shè)A是集合,R1和R2是A上的關(guān)系,證明：

（1）若R1,R2是自反的和對(duì)稱的,則R1∪R2也是自反的和對(duì)稱的.

（2）若R1和R2是傳遞的,則R1∩R2也是傳遞的.

47第四十七頁，共九十九頁，編輯于2023年，星期四證

（1）由于R1和R2是A上的自反關(guān)系,故有

IAR1和IA

R2，從而得到IA

R1∪R2.根據(jù)定理7.9可知R1∪R2在A上是自反的.

再由R1和R2的對(duì)稱性有

R1=R1-1和R2=R2-1

根據(jù)本章習(xí)題第20題的結(jié)果有

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

從而證明了R1∪R2也是A上對(duì)稱的關(guān)系.

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上的傳遞關(guān)系49第四十九頁，共九十九頁，編輯于2023年，星期四自反性反自反性對(duì)稱性反對(duì)稱性傳遞性R11

√√√√√R1∩R2

√√√√√R1∪R2

√√√××R1R2

×√√√×R1

R2

√××××關(guān)系的性質(zhì)和運(yùn)算之間的聯(lián)系50第五十頁，共九十九頁，編輯于2023年，星期四例7.14判斷圖7.3中關(guān)系的性質(zhì),并說明理由.

51第五十一頁，共九十九頁，編輯于2023年，星期四解

（1）該關(guān)系是對(duì)稱的,因?yàn)闊o單向邊.它不是自反的也不是反自反的.因?yàn)橛械捻旤c(diǎn)有環(huán),有的頂點(diǎn)無環(huán).它不是反對(duì)稱的,因?yàn)閳D中有雙向邊.它也不是傳遞的,因?yàn)閳D中有邊<3,1>和<1,3>,但沒有從3到3的邊,即通過3的環(huán).

（2）該關(guān)系是反自反的但不是自反的,因?yàn)槊總€(gè)頂點(diǎn)都沒有環(huán).它是反對(duì)稱的但不是對(duì)稱的,因?yàn)閳D中只有單向邊.它也是傳遞的,因?yàn)椴淮嬖陧旤c(diǎn)x,y,z,使得x到y(tǒng)有邊,y到z有邊,但x到z沒有邊,其中x,y,z∈{1,2,3}.

（3）該關(guān)系是自反的但不是反自反的,因?yàn)槊總€(gè)頂點(diǎn)都有環(huán).它是反對(duì)稱的但不是對(duì)稱的,因?yàn)閳D中只有單向邊.但他不是傳遞的,因?yàn)?到1有邊,1到3有邊,但2到3沒有邊.52第五十二頁，共九十九頁，編輯于2023年，星期四7.5關(guān)系的閉包

主要內(nèi)容閉包定義閉包的構(gòu)造方法集合表示矩陣表示圖表示閉包的性質(zhì)53第五十三頁，共九十九頁，編輯于2023年，星期四閉包定義定義7.14設(shè)R是非空集合A上的關(guān)系,R的自反(對(duì)稱或傳遞)閉包是A上的關(guān)系R,使得R滿足以下條件：(1)R是自反的(對(duì)稱的或傳遞的)(2)RR(3)對(duì)A上任何包含R的自反(對(duì)稱或傳遞)關(guān)系R有RRR的自反閉包記作r(R),對(duì)稱閉包記作s(R),傳遞閉包記作t(R).定理7.10設(shè)R為A上的關(guān)系,則有(1)r(R)=R∪R0(2)s(R)=R∪R1(3)t(R)=R∪R2∪R3∪…說明：對(duì)有窮集A(|A|=n)上的關(guān)系,(3)中的并最多不超過Rn54第五十四頁，共九十九頁，編輯于2023年，星期四證明證只證(1)和(3).(1)由IA=R0R∪R0知R∪R0是自反的,且滿足RR∪R0設(shè)R是A上包含R的自反關(guān)系,則有RR

和IAR

.從而有R∪R0R.R∪R0滿足閉包定義,所以r(R)=R∪R0.(3)先證R∪R2∪…t(R)成立.用歸納法證明對(duì)任意正整數(shù)n有Rnt(R).n=1時(shí)有R1=Rt(R).假設(shè)Rnt(R)成立,那么對(duì)任意的<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年，星期四閉包的矩陣表示和圖表示設(shè)關(guān)系R,r(R),s(R),t(R)的關(guān)系矩陣分別為M,Mr,Ms和Mt

則Mr=M+EMs=M+M'Mt=M+M2+M3+…E是單位矩陣,M'是轉(zhuǎn)置矩陣，相加時(shí)使用邏輯加.設(shè)關(guān)系R,r(R),s(R),t(R)的關(guān)系圖分別記為G,Gr,Gs,Gt,則Gr,Gs,Gt的頂點(diǎn)集與G的頂點(diǎn)集相等.除了G的邊以外,以下述方法添加新的邊：(1)考察G的每個(gè)頂點(diǎn),若沒環(huán)就加一個(gè)環(huán)，得到Gr

(2)考察G的每條邊,若有一條xi到xj的單向邊,i≠j,則在G中加一條xj到xi的反向邊,得到Gs(3)考察G的每個(gè)頂點(diǎn)xi,找xi可達(dá)的所有頂點(diǎn)xj(允許i=j)，

如果沒有從xi到xj

的邊,就加上這條邊,得到圖Gt57第五十七頁，共九十九頁，編輯于2023年，星期四實(shí)例例9設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},R和r(R),s(R),t(R)的關(guān)系圖如下圖所示.Rr(R)s(R)t(R)58第五十八頁，共九十九頁，編輯于2023年，星期四閉包的性質(zhì)定理7.11設(shè)R是非空集合A上的關(guān)系,則(1)R是自反的當(dāng)且僅當(dāng)r(R)=R.(2)R是對(duì)稱的當(dāng)且僅當(dāng)s(R)=R.(3)R是傳遞的當(dāng)且僅當(dāng)t(R)=R.定理7.12設(shè)R1和R2是非空集合A上的關(guān)系,且R1R2,則(1)r(R1)r(R2)(2)s(R1)s(R2)(3)t(R1)t(R2)證明略59第五十九頁，共九十九頁，編輯于2023年，星期四定理7.13設(shè)R是非空集合A上的關(guān)系,(1)若R是自反的,則s(R)與t(R)也是自反的(2)若R是對(duì)稱的,則r(R)與t(R)也是對(duì)稱的(3)若R是傳遞的,則r(R)是傳遞的.說明：如果需要進(jìn)行多個(gè)閉包運(yùn)算，比如求R的自反、對(duì)稱、傳遞的閉包tsr(R)，運(yùn)算順序如下：

閉包的性質(zhì)60第六十頁，共九十九頁，編輯于2023年，星期四證（2）

由于R是A上的對(duì)稱關(guān)系,所以R=R-1,同時(shí)IA=IA-1.根據(jù)(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)是對(duì)稱的.

61第六十一頁，共九十九頁，編輯于2023年，星期四命題：若R是對(duì)稱的,則Rn也是對(duì)稱的,其中n是任何正整數(shù).

證明用歸納法.

n=1,R1=R顯然是對(duì)稱的.

假設(shè)Rn是對(duì)稱的,則對(duì)任意的<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是對(duì)稱的.由歸納法命題得證.

62第六十二頁，共九十九頁，編輯于2023年，星期四下面證明t(R)的對(duì)稱性.

任取<x,y>

<x,y>∈t(R)

n(<x,y>∈Rn)

n(<y,x>∈Rn)（因?yàn)镽n是對(duì)稱的）

<y,x>∈t(R)

從而證明了t(R)的對(duì)稱性.

63第六十三頁，共九十九頁，編輯于2023年，星期四

定理7.13討論了關(guān)系性質(zhì)和閉包運(yùn)算之間的關(guān)系.如果關(guān)系R是自反的和對(duì)稱的,那么經(jīng)過求閉包的運(yùn)算以后所得到的關(guān)系仍就是自反的和對(duì)稱的.但是對(duì)于傳遞的關(guān)系則不然.它的自反閉包仍舊保持傳遞性,而對(duì)稱閉包就有可能失去傳遞性.

64第六十四頁，共九十九頁，編輯于2023年，星期四7.6等價(jià)關(guān)系與劃分

主要內(nèi)容等價(jià)關(guān)系的定義與實(shí)例等價(jià)類及其性質(zhì)商集與集合的劃分等價(jià)關(guān)系與劃分的一一對(duì)應(yīng)65第六十五頁，共九十九頁，編輯于2023年，星期四等價(jià)關(guān)系的定義與實(shí)例定義7.15設(shè)R為非空集合上的關(guān)系.如果R是自反的、對(duì)稱的和傳遞的,則稱R為A上的等價(jià)關(guān)系.設(shè)R是一個(gè)等價(jià)關(guān)系,若<x,y>∈R,稱x等價(jià)于y,記做x～y.實(shí)例設(shè)A={1,2,…,8},如下定義A上的關(guān)系R：

R={<x,y>|x,y∈A∧x≡y(mod3)}其中x≡y(mod3)叫做x與y模3相等,即x除以3的余數(shù)與y除以3的余數(shù)相等.不難驗(yàn)證R為A上的等價(jià)關(guān)系,因?yàn)?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等價(jià)關(guān)系的關(guān)系圖等價(jià)關(guān)系的實(shí)例67第六十七頁，共九十九頁，編輯于2023年，星期四把模3的等價(jià)關(guān)系推廣,對(duì)任何正整數(shù)n可以定義整數(shù)集合Z上模n的等價(jià)關(guān)系.

R＝｛<x,y>|x,y∈Z∧x≡y(modn)}例如,當(dāng)n＝5時(shí),整數(shù)之間的等價(jià)性滿足:…～－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年，星期四等價(jià)類定義定義7.16設(shè)R為非空集合A上的等價(jià)關(guān)系,x∈A，令[x]R

={y|y∈A∧xRy}稱[x]R為x關(guān)于R的等價(jià)類,簡稱為x的等價(jià)類,簡記為[x]或?qū)嵗鼳={1,2,…,8}上模3等價(jià)關(guān)系的等價(jià)類：[1]=[4]=[7]={1,4,7}[2]=[5]=[8]={2,5,8}[3]=[6]={3,6}69第六十九頁，共九十九頁，編輯于2023年，星期四等價(jià)類的性質(zhì)定理7.14設(shè)R是非空集合A上的等價(jià)關(guān)系,則(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設(shè)R為非空集合A上的等價(jià)關(guān)系,以R的所有等價(jià)類作為元素的集合稱為A關(guān)于R的商集,記做A/R,

A/R={[x]R|x∈A}實(shí)例(1)設(shè)A={1,2,…,8}，A關(guān)于模3等價(jià)關(guān)系R的商集為

A/R={{1,4,7},{2,5,8},{3,6}}A關(guān)于恒等關(guān)系和全域關(guān)系的商集為：

A/IA

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

={{1,2,…,8}}(2)在整數(shù)集合z上模n的等價(jià)關(guān)系的商集是{{nz+i|zZ}|i=0,1,…n-1}71第七十一頁，共九十九頁，編輯于2023年，星期四商集與劃分定義7.18設(shè)A為非空集合,若A的子集族π(π

P(A))滿足:(1)

π(2)xy(x,yπ∧x≠y→x∩y=)(3)∪π=A則稱π是A的一個(gè)劃分,稱π中的元素為A的劃分塊.72第七十二頁，共九十九頁，編輯于2023年，星期四劃分實(shí)例

例10設(shè)A＝{a,b,c,d},給定1,2,3,4,5,6如下：

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

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

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}上所有的等價(jià)關(guān)系實(shí)例1231

12351232123412331對(duì)應(yīng)EA,5對(duì)應(yīng)IA,2,3和

4分別對(duì)應(yīng)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年，星期四練習(xí)11．設(shè)A={1,2,3},R={<x,y>|x,yA且x+2y

6}，S={<1,2>,<1,3>,<2,2>},求:(1)R的集合表達(dá)式(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年，星期四練習(xí)22．設(shè)A={1,2,3,4}，在AA上定義二元關(guān)系R：<<x,y>,<u,v>>R

x+y=u+v，求R導(dǎo)出的劃分.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>}根據(jù)<x,y>中的x+y=2,3,4,5,6,7,8將A劃分成等價(jià)類：

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．設(shè)R是Z上的模n等價(jià)關(guān)系,即xy

x

y(modn),試給出由R確定的Z的劃分.練習(xí)3解設(shè)除以n余數(shù)為r的整數(shù)構(gòu)成等價(jià)類[r]，則[r]={kn+r|kZ},r=0,1,…,n1

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

78第七十八頁，共九十九頁，編輯于2023年，星期四練習(xí)44．設(shè)R是A上的二元關(guān)系，設(shè)S={<a,b>|c(<a,c>R<c,b>R)}.證明如果R是等價(jià)關(guān)系，則S也是等價(jià)關(guān)系。證R是A上的等價(jià)關(guān)系.(1)證自反任取x,xA<x,x>R

x(<x,x>R<x,x>R)<x,x>S(2)證對(duì)稱任取<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年，星期四關(guān)系性質(zhì)的證明方法1.證明R在A上自反任取x,xA

……..….…….<x,x>R前提推理過程結(jié)論2.證明R在A上對(duì)稱任取<x,y>，

<x,y>R

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

前提推理過程結(jié)論80第八十頁，共九十九頁，編輯于2023年，星期四3.證明R在A上反對(duì)稱任取<x,y>，<x,y>R<y,x>R

……..

x=y

前提推理過程結(jié)論4.證明R在A上傳遞任取<x,y>,<y,z>，<x,y>R<y,z>R

……..<x,z>R

前提推理過程結(jié)論關(guān)系性質(zhì)的證明方法81第八十一頁，共九十九頁，編輯于2023年，星期四5．R,S為A上的關(guān)系，證明RS

t(R)t(S)練習(xí)5證只需證明對(duì)于任意正整數(shù)n,RnSn.對(duì)n歸納.n=1,顯然為真.假設(shè)對(duì)于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年，星期四數(shù)學(xué)歸納法（主要用于冪運(yùn)算）證明中用到關(guān)系運(yùn)算的定義和公式,如：

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…關(guān)系等式或包含式的證明方法83第八十三頁，共九十九頁，編輯于2023年，星期四7.7偏序關(guān)系定義7.19偏序關(guān)系：非空集合A上的自反、反對(duì)稱和傳遞的關(guān)系，記作?.設(shè)?為偏序關(guān)系,如果<x,y>∈?,則記作x?y,讀作x“小于或等于”y.實(shí)例集合A上的恒等關(guān)系IA，空關(guān)系是A上的偏序關(guān)系.小于(大于)或等于關(guān)系,整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的偏