離散數(shù)學(xué)左孝凌3

第三章集合與關(guān)系〔SetsandRelations)本章首先采用樸素集合論的方法，介紹有關(guān)集合的一些根本知識(shí)，內(nèi)容顯得較為直觀，學(xué)起來(lái)易于接受。但集合及其相關(guān)的概念是本門課程后面各章內(nèi)容的根底，同學(xué)們務(wù)必熟練的掌握。本章重點(diǎn)討論關(guān)系〔主要是二元關(guān)系〕，它仍然是一種集合，但它是一種更為復(fù)雜的集合。它的元素是有序二元組的形式，這些有序二元組中的兩個(gè)元素來(lái)自于兩個(gè)不同或者相同的集合。因此，關(guān)系是建立在其它集合根底之上的集合。關(guān)系中的有序二元組反映了不同集合中元素與元素之間的關(guān)系，或者同一集合中元素之間的關(guān)系。本章討論這些關(guān)系的表示方法、關(guān)系的運(yùn)算以及關(guān)系的性質(zhì)，最后討論集合A上幾類特殊的關(guān)系。

3-1集合的概念和表示法3-2集合的運(yùn)算3-4序偶與笛卡爾積3-5關(guān)系及其表示

3-6關(guān)系的性質(zhì)第三章集合與關(guān)系〔SetsandRelations)

3-7復(fù)合關(guān)系和逆關(guān)系3-8關(guān)系的閉包運(yùn)算3-9集合的劃分與覆蓋3-10等價(jià)關(guān)系與等價(jià)類

3-11相容關(guān)系3-12序關(guān)系第三章集合與關(guān)系〔SetsandRelations)3-1集合的概念和表示方法定義(集合set)：把具有共同性質(zhì)的一些對(duì)象聚集成一個(gè)整體，就構(gòu)成一個(gè)集合，這些對(duì)象稱為元素(element)或成員(member)用大寫英文字母A,B,C,…表示集合用小寫英文字母a,b,c,…表示元素aA：表示a是A的元素，讀作“a屬于A〞aA：表示a不是A的元素，讀作“a不屬于A〞3-1.1有關(guān)集合的概念n元集(n-set):有n個(gè)元素的集合稱為n元集。|A|:表示集合A中的元素個(gè)數(shù),A是n元集|A|=n0元集:記作1元集(或單元集),如{a},,{}…有限集(finiteset):|A|是有限數(shù),|A|<,也叫有窮集，否那么為無(wú)限集。3-1.2集合的表示方法通常使用“列舉法〞和“表達(dá)法〞兩種方法來(lái)給出一個(gè)集合〔1〕列舉法(roster)列出集合中的全體元素，元素之間用逗號(hào)分開，然后用花括號(hào)括起來(lái)，例如A={a,b,c,d,…,x,y,z}B={0,1,2,3,4,5,6,7,8,9}集合中的元素不規(guī)定順序C={2,1}={1,2}集合中的元素各不相同C={2,1,1,2}={2,1}3-1.2集合的表示方法〔2〕表達(dá)法(definingpredicate)用謂詞P(x)表示“x具有性質(zhì)P〞，用A={x|P(x)}表示元素具有性質(zhì)P的集合A，如果P(b)為真，那么bA，否那么bA。例如P1(x):x是英文字母A={x|P1(x)}={x|x是英文字母}={a,b,c,d,…,x,y,z}P2(x):x是十進(jìn)制數(shù)字B={x|P2(x)}={x|x是十進(jìn)制數(shù)字}={0,1,2,3,4,5,6,7,8,9}兩種表示法可以互相轉(zhuǎn)化例如：E={2,4,6,8,…}={x|x>0且x是偶數(shù)}={x|x=2(k+1)，k為非負(fù)整數(shù)}={2(k+1)|k為非負(fù)整數(shù)}兩個(gè)集合相等的外延性原理：兩個(gè)集合A、B是相等的，當(dāng)且僅當(dāng)它們有相同的成員，記作A=B；否那么記作AB。集合的元素還可以是一個(gè)集合。例如：S={a,{1,2},p,{q}}3-1.3數(shù)的集合N：自然數(shù)(naturalnumbers)集合N={0,1,2,3,…}Z：整數(shù)(integers,Zahlen)集合Z={0,

1,

2,…}={…,-2,-1,0,1,2,…}Q：有理數(shù)(rationalnumbers,Quotient)集合R：實(shí)數(shù)(Realnumbers)集合C：復(fù)數(shù)(Complexnumbers)集合3-1.4集合之間的關(guān)系子集、相等、真子集；空集、全集；冪集、n元集、有限集；〔1〕子集[定義3-1.1]子集(subset)：設(shè)A、B是任意兩個(gè)集合，如果A的每一個(gè)元素是B的成員，那么稱A為B的子集,或說(shuō)A包含于B,或說(shuō)B包含A,記作AB，或BA。AB(x)(xAxB)假設(shè)A不是B的子集,那么記作ABAB(x)(xAxB)證明ABx(xAxB)成立

[證明]：根據(jù)定義AB(x)(xAxB)那么AB(x)(xAxB)(x)((xA)(xB))(x)((xA)(xB))(x)(xAxB)子集(舉例)設(shè)A={a,b,c},B={a,b,c,d},C={a,b},那么AB,CA,CB〔1〕子集定理3-1.1

集合A和集合B相等的充分必要條件是這兩個(gè)集合互為子集。A=B

A

B

B

AA=B

(

x)(x

Ax

B)[證明]A=B

A

B

B

A(=定義)(x)(x

A

x

B)(x)(x

B

x

A)(

定義)(x)((x

A

x

B)

(x

B

x

A))(量詞分配)(x)(x

Ax

B)(等價(jià)式)〔1〕子集包含(

)的性質(zhì)：1．AA〔自反性〕證明:AA(x)(xAxA)T2．假設(shè)AB,且AB,那么BA〔反對(duì)稱性〕3．假設(shè)AB,且BC,那么AC〔傳遞性〕證明:AB(x)(xAxB)x,xAxB(AB)xC(BC)(x)(xAxC),即AC.〔2〕真子集[定義3-1.2]真子集(propersubset)如果集合A的每一個(gè)元素都屬于B，但集合B至少有一個(gè)元素不屬于A，那么稱A為B的真子集，記作AB。ABABABAB(x)(xAxB)(x)(xBxA)A

B的含義：A

B

(A

B

A

B)(

定義)

(A

B)

(A=B)(德摩根律)

x(x

A

x

B)

(A=B)(

定義)

A

B

(A=B)含義：A不是B的子集或者A和B相等。

真包含(

)的性質(zhì)1．AA〔反自反性〕證明:AAAAAATFF.2．假設(shè)AB,那么BA〔反對(duì)稱性〕證明:(反證)設(shè)BA,那么ABABABAB(化簡(jiǎn))BABABABA所以ABBAA=B(=定義)但是ABABABAB(化簡(jiǎn))矛盾!3．假設(shè)AB,且BC,那么AC〔傳遞性〕證明:ABABABAB(化簡(jiǎn)),同理BCBC,所以AC.假設(shè)A=C,那么BCBA,又AB,故A=B,此與AB矛盾,所以AC.所以,AC.#

真包含(

)的性質(zhì)〔3〕空集[定義3-1.3]空集(emptyset)：不包含任何元素的集合是空集,記作

例如：{x

R|x2+1=0}[定理3-1.2]對(duì)任意一個(gè)集合A，

A也就是對(duì)任意集合A,

A證明:

A

x(x

x

A)

x(F

x

A)

T.對(duì)于每一個(gè)非空集合A，至少有兩個(gè)不同的子集，A和，稱為A的平凡子集。[推論]空集是唯一的.〔可作為討論〕證明:設(shè)1與2都是空集,那么12211=2.#〔3〕空集〔4〕全集[定義3-1.4]全集:在一定范圍內(nèi)，如果所有集合均為某一集合的子集,那么稱這個(gè)集合是全集,記作E。E={x|P(x)P(x)}，P(x)為任何謂詞全集是相對(duì)的,視情況而定,因此不唯一。例如,討論(a,b)區(qū)間里的實(shí)數(shù)性質(zhì)時(shí),可以選E=(a,b),E=[a,b),E=(a,b],E=[a,b],E=(a,+),E=(-,+)等〔5〕冪集[定義3-1.5]冪集(powerset)給定集合A，由集合A的所有子集為元素組成的集合,稱為A的冪集,記作P(A)P(A)={x|x

A}注意:x

P

(A)

x

A例如:A={a,b},

P(A)={

,{a},,{a,b}}.[定理]如果有限集合A有n個(gè)元素，那么冪集P(A)有2n個(gè)元素。證明:利用二項(xiàng)式展開定理。〔5〕冪集作業(yè)(3-1)：P85(6)(9)(10)3-2集合的運(yùn)算

[定義3-2.1]集合的交(intersection):

設(shè)任意兩個(gè)集合A和B，由集合A和B的所有共同元素組成的集合S，稱為A和B的交集，記作A

B。S=A

B={x|(x

A)

(x

B)}x

A

B

(x

A)

(x

B)3-2.1交集例2:設(shè)An={xR|0x1/n},n=1,2,…,那么A1A2An=3-2.1交集例1:設(shè)An={xR|n-1xn},n=1,2,…,10,那么A1A2An=

{0}不相交(disjoint)不相交：AB=互不相交：設(shè)A1,A2,…是可數(shù)多個(gè)集合,假設(shè)對(duì)于任意的ij,都有AiAj=,那么說(shuō)它們互不相交。例:設(shè)An={xR|n-1<x<n},n=1,2,…,10,那么A1,A2,…是互不相交的3-2.1交集集合交運(yùn)算的性質(zhì)a)AA=A〔冪等律〕b)A=〔零律〕c)AE=A〔同一律〕d)AB=BA〔交換律〕e)(AB)C=A(BC)〔結(jié)合律〕因?yàn)榧辖贿\(yùn)算滿足結(jié)合律，故n個(gè)集合的交記為：nP=A1A2An=Aii=13-2.1交集3-2.2集合的并

[定義3-2.2]并集(union)：設(shè)任意兩個(gè)集合A和B，由所有集合A和B的元素組成的集合S，稱為A和B的并集，記作A

B。

S=A

B={x|(x

A)

(x

B)}x

A

B

(x

A)

(x

B)例2:設(shè)An={xR|0x1/n},n=1,2,…,那么A1A2An=3-2.2并集例1:設(shè)An={xR|n-1xn},n=1,2,…,10,那么A1A2An=[0，10][0，1]集合并運(yùn)算的性質(zhì)a)AA=A〔冪等律〕b)A=A〔同一律〕c)AE=E〔零律〕d)AB=BA〔交換律〕e)(AB)C=A(BC)〔結(jié)合律〕因?yàn)榧喜⑦\(yùn)算滿足結(jié)合律，故n個(gè)集合的并記為：nP=A1A2An=Aii=13-2.2并集3-2.3集合的補(bǔ)／相對(duì)補(bǔ)

[定義3-2.3]補(bǔ)集／相對(duì)補(bǔ)集(relativecomplement,differenceset)：屬于A而不屬于B的全體元素組成的集合S，稱為B對(duì)于A的補(bǔ)集／相對(duì)補(bǔ)集,記作A-BS=A-B={x|(x

A)

(x

B)}

[定義3-2.4]絕對(duì)補(bǔ)(complement)：設(shè)E為全集，對(duì)任一集合A關(guān)于E的補(bǔ)E-A，稱為集合A的絕對(duì)補(bǔ)，記作~A。~A={x|(x

E

x

A)}集合補(bǔ)運(yùn)算的性質(zhì)〔1〕

對(duì)合律：~~A=A〔2〕

全補(bǔ)律：~E=〔3〕

~=E〔4〕矛盾律：A~A=〔5〕排中律：A~A=E3-2.3集合的補(bǔ)／相對(duì)補(bǔ)3-2.4集合的對(duì)稱差［定義3-2.5］對(duì)稱差(symmetricdifference)：屬于A而不屬于B,或?qū)儆贐而不屬于A的全體元素組成的集合S,稱為A與B的對(duì)稱差,記作A

B。A

B={x|(x

A

x

B)

(x

A

x

B)}A

B=(A-B)

(B-A)=(A

B)-(A

B)對(duì)稱差(

)的性質(zhì)〔1〕

交換律：AB=BA〔2〕

結(jié)合律：A(BC)=(AB)C〔3〕

分配律：A(BC)=(AB)(AC)〔4〕同一律：A=A〔5〕排中律：A~A=E〔6〕AA=〔7〕AE=~A3-2.4集合的對(duì)稱差相對(duì)補(bǔ)、對(duì)稱差(舉例)例:設(shè)A={xR|0x<2},B={xR|1x<3},那么A-B={xR|0x<1}=[0,1)B-A={xR|2x<3}=[2,3)AB={xR|(0x<1)(2x<3)}=[0,1)[2,3)3-2.5集合運(yùn)算的性質(zhì)〔集合恒等式〕(1)冪等律(idempotentlaws)A

A=AA

A=A(2)結(jié)合律(associativelaws)(A

B)

C=A

(B

C)(A

B)

C=A

(B

C)(3)交換律(commutativelaws)A

B=B

AA

B=B

A(4)分配律(distributivelaws)A

(B

C)=(A

B)

(A

C)A

(B

C)=(A

B)

(A

C)(5)對(duì)合律(doublecomplementlaw)~~A=A(6)零律(dominancelaws)A

E=EA

=

3-2.5集合運(yùn)算的性質(zhì)〔集合恒等式〕(7)同一律(identitylaws)A

=AA

E=A(8)排中律(excludedmiddle)A

~A=E(9)矛盾律(contradiction)A

~A=

(10)全補(bǔ)律~

=E~E=

3-2.5集合運(yùn)算的性質(zhì)〔集合恒等式〕(11)吸收律(absorptionlaws)A

(A

B)=AA

(A

B)=A(12)德.摩根律(DeMorgan’slaws)~(A

B)=~A

~B~(A

B)=~A

~B(13)補(bǔ)交轉(zhuǎn)換律(differenceasintersection)A-B=A

~B3-2.5集合運(yùn)算的性質(zhì)〔集合恒等式〕3-2.6集合恒等式證明(方法)〔1〕邏輯演算法:利用邏輯等價(jià)式和邏輯推理規(guī)那么〔2〕集合演算法:利用集合恒等式和的集合結(jié)論〔1〕邏輯演算法(格式)

題型:A=B.

證明：

x,x

A

…(????)

x

B

A=B證畢.或證明：

x,x

A

…(????)

x

B.

另，

x,x

B

…(????)

x

A.

A=B證畢.題型:A

B.

證明:

x,x

A

…(????)

x

B

A

B證畢.例1：分配律(定理3-2.1)A

(B

C)=(A

B)

(A

C)證明:

x,x

A

(B

C)

x

A

x

(B

C)(

定義)

x

A

(x

B

x

C)(

定義)

(x

A

x

B)

(x

A

x

C)(命題邏輯分配律)

(x

A

B)

(x

A

C)(

定義)

x

(A

B)

(A

C)(

定義)

A

(B

C)=(A

B)

(A

C)成立3-2.6集合恒等式證明(方法)例2：零律(證明)

A

=

證明:

x,x

A

x

A

x

(

定義)

x

A

F(

定義)

F(命題邏輯零律)

A

=

成立3-2.6集合恒等式證明(方法)例3.

排中律(證明)A

~A=E證明:

x,x

A

~A

x

A

x

~A(

定義)

x

A

x

A(~定義)

x

A

(x

A)(

定義)

T(命題邏輯排中律)

A

~A=E成立3-2.6集合恒等式證明(方法)(2)集合演算法〔格式〕題型:A=B.題型:A

B.

證明:A證明:A=…(????)

…(????)=B

B

A=B.#

A

B.#例1：吸收律(定理3-2.2)A

(A

B)=A證明:A

(A

B)=(A

E)

(A

B)(同一律)=A

(E

B)(逆用分配律)=A

E(零律)=A(同一律)

A

(A

B)=A3-2.6集合恒等式證明(方法)例2：吸收律(定理3-2.2)A

(A

B)=A證明:A

(A

B)=(A

A)

(A

B)(分配律)=A

(A

B)(冪等律)=A(吸收律第一式)

A

(A

B)=A3-2.6集合恒等式證明(方法)(2)集合演算法〔格式〕續(xù)

題型:A

B

證明:A

B(或A

B)=…(????)=A(或B)

A

B.#

說(shuō)明:化

成=題型:A=B證明:(

)…

A

B(

)…

A

B

A=B.#說(shuō)明:把=分成

與

A

B=A

A

BA

B=B

A

B3-2.7集合恒等式證明(舉例)1.根本集合恒等式例如：①補(bǔ)交轉(zhuǎn)換律A-B=A~B證明:x,xA-BxAxBxAx~BxA~BA-B=A~B.②德

摩根律的相對(duì)形式A-(B

C)=(A-B)

(A-C)A-(B

C)=(A-B)

(A-C)證明:A-(B

C)=A

~(B

C)(補(bǔ)交轉(zhuǎn)換律)=A

(~B

~C)(德

摩根律)=(A

A)

(~B

~C)(冪等律)=(A

~B)

(A

~C)(交換律,結(jié)合律)=(A-B)

(A-C)(補(bǔ)交轉(zhuǎn)換律).#3-2.7集合恒等式證明(舉例)

小結(jié)：本節(jié)介紹了集合的運(yùn)算和運(yùn)算定律。重點(diǎn)掌握集合的各種運(yùn)算及其運(yùn)算規(guī)律。作業(yè)：P94(1)(3)c)d)(4)(5)a)(6)第三章集合與關(guān)系〔SetsandRelations)3-4

序偶與笛卡爾積3-4.1

序偶(二元組)定義［序偶o(jì)rderedpair］：由兩個(gè)固定次序的客體a,b組成的序列稱為序偶，記作<a,b>，其中a,b稱為序偶的分量。<a,b>其中,a是第一元素,b是第二元素,

記作<a,b>也記作(a,b)。定義3-4.1兩個(gè)序偶相等

,<x，y>=<u,v>,iffx＝u,y=v

。推論:a

b

<a,b>

<b,a>

3-4.2三元組(orderedtriple)定義［三元組］：<a,b,c>=<<a,b>,c>.定義［n(

2)元組］：

<a1,a2,…,an>=<<a1,a2,…,an-1>,an>.定理:<a1,a2,…,an>=<b1,b2,…,bn>

ai

=bi,i=1,2,…,n.

3-4.3

笛卡爾積及其性質(zhì)

定義3-4.2令A(yù)和B是任意兩個(gè)集合，假設(shè)序偶的第一個(gè)成員是A的元素，第二個(gè)成員是B的元素，所有這樣的序偶集合，稱為集合A和B的笛卡爾乘積或直積，記為AB，AB={<x,y>|xAyB}例1:A={

,a},B={1,2,3}.A

B=<

,1>,<

,2>,<

,3>,<a,1>,<a,2>,<a,3>}.B

A=<1,

>,<1,a>,<2,

>,<2,a>,<3,

>,<3,a>}.A

A={<

,

>,<

,a>,<a,

>,<a,a>}.B

B={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}.3-4.3

笛卡爾積及其性質(zhì)

3-4.4笛卡爾積的性質(zhì)：當(dāng)|A|=m，|B|=n時(shí)，|A×B|是多少？|A×B|=m×n3-4.4笛卡爾積的性質(zhì)：1.

非交換:A

B

B

A

(除非

A=B

A=

B=

)舉例:A={1},B={2}.A

B={<1,2>},B

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

非結(jié)合:(A

B)

C

A

(B

C)(除非

A=

B=

C=

)舉例:A=B=C={1}.(A

B)

C={<<1,1>,1>},A

(B

C)={<1,<1,1>>}.3.笛卡爾積分配律：〔對(duì)或運(yùn)算滿足〕〔1〕

A(BC)=(AB)(AC)〔2〕

A(BC)=(AB)(AC)〔3〕

(BC)A=(BA)(CA)〔4〕

(BC)A=(BA)(CA)3-4.3

笛卡爾積及其性質(zhì)3.笛卡爾積分配律(證明(1))

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).#3-4.3

笛卡爾積及其性質(zhì)4.其他性質(zhì)：設(shè)A,B,C,D是任意集合,(1)

假設(shè)A,那么ABACBACABC〔即書上的定理3-4.2〕(2)

ACBDABCD.〔即書上的定理3-4.3〕(3)

AB=A=B=3-4.3

笛卡爾積及其性質(zhì)證明(1)假設(shè)A,那么ABACBC.證明:()假設(shè)B=,那么BC.設(shè)B,由A,設(shè)xA,y,yB，<x,y>AB<x,y>ACxAyCyC.

BC()假設(shè)B=,那么AB=AC.設(shè)B.<x,y>,<x,y>ABxAyBxAyC<x,y>ACABAC.#3-4.3

笛卡爾積及其性質(zhì)3-4.5推廣：n維笛卡爾積定義［n維笛卡爾積］：A1

A2

…

An={<x1,x2,…,xn>|x1

A1

x2

A2

…

xn

An}A

A

…

A

=An|Ai|=ni,i=1,2,…,n

|A1

A2

…

An|=n1

n2

…

nn.n維笛卡爾積性質(zhì)與2維笛卡爾積類似.

小結(jié)：本節(jié)介紹了序偶、有序n元組及笛卡爾積的概念。重點(diǎn)理解有序n元組及笛卡爾積的概念。作業(yè)：P104(1)b)(2)(5)第三章集合與關(guān)系〔SetsandRelations)3-5關(guān)系及其表示3-5.1關(guān)系的概念及記號(hào)兄弟關(guān)系、長(zhǎng)幼關(guān)系、同學(xué)關(guān)系、鄰居關(guān)系，上下級(jí)關(guān)系等。在數(shù)學(xué)上有大于關(guān)系、小于關(guān)系，整除關(guān)系。例如：“3小于5〞，“x大于y〞，“點(diǎn)a在b與c之間〞。我們又知道序偶可以表達(dá)兩個(gè)客體、三個(gè)客體或n個(gè)客體之間的聯(lián)系，因此用序偶表達(dá)這個(gè)概念是非常自然的。例如：火車票與座位之間的對(duì)號(hào)關(guān)系。設(shè)X表示火車票的集合，Y表示座位的集合，那么對(duì)于任意的xX和yY，必定有x與y有“對(duì)號(hào)〞關(guān)系x與y沒有“對(duì)號(hào)〞關(guān)系。二者之一令R表示“對(duì)號(hào)〞關(guān)系，那么上述問題可以表示為xRy或xRy。亦可表示為<x,y>

R或<x,y>

R，因此我們看到對(duì)號(hào)關(guān)系是序偶的集合。3-5.1關(guān)系的概念及記號(hào)定義3-5.1［關(guān)系］：二元關(guān)系(binaryrelation)，簡(jiǎn)稱關(guān)系，任一序偶的集合即確定了一個(gè)二元關(guān)系R，R中任一序偶<x,y>可記為<x,y>

R或xRy。不在R中的任一序偶<x,y>可記為<x,y>

R或xRy3-5.1關(guān)系的概念及記號(hào)例1:在實(shí)數(shù)中關(guān)系“≥〞可記作“≥〞={<x,y>|x,y是實(shí)數(shù)且x≥y}。例2:R1={<1,2>,<,>,<a,b>}

R1是二元關(guān)系.例3:A={<a,b>,<1,2,3>,a,1}

A不是關(guān)系.3-5.1關(guān)系的概念及記號(hào)

二元關(guān)系的記號(hào)：

設(shè)R是二元關(guān)系,那么<x,y>Rx與y具有R關(guān)系xRy。比照:xRy(中綴(infix)記號(hào))

<x,y>R(后綴(suffix)記號(hào))R(x,y)(前綴(prefix)記號(hào))例如:2<15<(2,15)<2,15><。<1,2>R1R2。<5,4>R5R4。3-5.1關(guān)系的概念及記號(hào)X到Y(jié)的二元關(guān)系定義3-5.3令X和Y是任意兩個(gè)集合，直積XY的子集R稱為X到Y(jié)的二元關(guān)系。R是X到Y(jié)的二元關(guān)系RXYRP(XY)〔冪集〕假設(shè)|X|=m,|Y|=n,那么|XY|=mn,故|P(XY)|=2mn，即X到Y(jié)不同的二元關(guān)系共有2mn個(gè)3-5.1關(guān)系的概念及記號(hào)X到Y(jié)的二元關(guān)系(舉例)例:設(shè)A={a1,a2},B=,那么A到B的二元關(guān)系共有22×1=4個(gè):R1=,R2={<a1,b>},R3={<a2,b>},R4={<a1,b>,<a2,b>}B到A的二元關(guān)系也有4個(gè):R5=,R6={<b,a1>},R7={<b,a2>},R8={<b,a1>,<b,a2>}。

3-5.1關(guān)系的概念及記號(hào)X上的二元關(guān)系定義［X上的二元關(guān)系］:是XX的任意子集。R是X上的二元關(guān)系RXXRP(XX)。假設(shè)|X|=m,那么|XX|=m2,故|P(XX)|=2m2，即X上不同的二元關(guān)系共有2m2個(gè)。

3-5.1關(guān)系的概念及記號(hào)X上的二元關(guān)系(舉例)例1:設(shè)A={a1,a2},那么A上的二元關(guān)系共有16個(gè):

R1=,R2={<a1,a1>},

R3={<a1,a2>},R4={<a2,a1>},

R5={<a2,a2>},R6={<a1,a1>,<a1,a2>},

R7={<a1,a1>,<a2,a1>},

R8={<a1,a1>,<a2,a2>},3-5.1關(guān)系的概念及記號(hào)R9={<a1,a2>,<a2,a1>},R10={<a1,a2>,<a2,a2>},R11={<a2,a1>,<a2,a2>},R12={<a1,a1>,<a1,a2>,<a2,a1>}，R13={<a1,a1>,<a1,a2>,<a2,a2>}，R14={<a1,a1>,<a2,a1>,<a2,a2>}，R15={<a2,a1>,<a2,a1>,<a2,a2>}，R16={<a1,a1>,<a1,a2>,<a2,a1>,<a2,a2>}。3-5.1關(guān)系的概念及記號(hào)例2:設(shè)A={a},

那么A上的二元關(guān)系共有2個(gè):

R1=,R2={<a,a>}.例3:設(shè)A={a,b,c},

那么A上的二元關(guān)系共有29=512個(gè)!

3-5.1關(guān)系的概念及記號(hào)3-5.2

與二元關(guān)系有關(guān)的概念對(duì)任意集合R,可以定義:前域／定義域〔domain〕:domR={x|y(xRy)}值域〔range〕:ranR={y|x(xRy)}域〔field〕:FLDR=domRranR前域／定義域,值域,域圖示見書106頁(yè)例題1。定義域,值域,域(舉例)例:R1={a,b},R2={<c,d>,<e,f>},

R3={<1,2>,<3,4>,<5,6>}.當(dāng)a,b不是序偶時(shí),R1不是關(guān)系.domR1=

,ranR1=

,FLDR1=

domR2={c,e},ranR2={d,f},FLDR2={c,d,e,f}domR3={1,3,5},ranR3={2,4,6},

FLDR3={1,2,3,4,5,6}.3-5.2

與二元關(guān)系有關(guān)的概念3-5.3

一些特殊關(guān)系設(shè)A是任意集合,那么可以定義A上的：空關(guān)系(emptyrelation):恒等關(guān)系(identityrelation):IA={<a,a>|aA}全域關(guān)系(universalrelation):UA=AA={<x,y>|xAyA}此外，設(shè)AI,那么可以定義A上的：整除關(guān)系:DA={<x,y>|xAyAx|y}例:A={1,2,3,4,5,6},那么DA={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,2>,<2,4>,<2,6>,<3,3>,<3,6>,<6,6>}。3-5.3

一些特殊關(guān)系設(shè)AR,那么可以定義A上的：小于等于(lessthanorequalto)關(guān)系：LEA={<x,y>|xAyAxy}小于(lessthan)關(guān)系：LA={<x,y>|xAyAx<y}大于等于(greaterthanorequalto)關(guān)系，大于(greatthan)關(guān)系,…3-5.3

一些特殊關(guān)系設(shè)A為任意集合,那么可以定義P(A)上的:包含關(guān)系:：A={<x,y>|xAyAxy}真包含關(guān)系：A={<x,y>|xAyAxy}見P107例2和例33-5.3

一些特殊關(guān)系3-5.4關(guān)系的運(yùn)算定理3-5.1：假設(shè)Z和S是從集合X到集合Y的兩個(gè)關(guān)系，那么Z和S的并、交、補(bǔ)、差仍是X到Y(jié)的關(guān)系。

證明見書108頁(yè)。3-5.5

二元關(guān)系的表示(1)序偶集合的形式表達(dá)(2)關(guān)系矩陣：設(shè)A={a1,a2,…,an},B={b1,b2,…,bm},RAB,那么R的關(guān)系矩陣MR=(rij)nm,其中rij=1,aiRbj或<ai,bj>R

0,aiRbj或<ai,bj>R例題：P103例題5例如:A={a,b,c},R1={<a,a>,<a,b>,<b,a>,<b,c>},R2={<a,b>,<a,c>,<b,c>},那么110011MR1=101MR2=0010000003-5.5

二元關(guān)系的表示(3)關(guān)系圖：A={a1,a2,…,an}，B={b1,b2,…,bn}，RAB,首先在平面上做結(jié)點(diǎn)a1,a2,…,an，b1,b2,…,bn以“〞表示(稱為頂點(diǎn))，假設(shè)aiRbj，那么從結(jié)點(diǎn)ai向結(jié)點(diǎn)bj畫有向邊<ai,bj>，箭頭指向bj，假設(shè)aiRbj,那么ai與bj之間沒有線段連接，這樣得到的圖稱為R的關(guān)系圖GR。P109例題73-5.5

二元關(guān)系的表示abcGR2abcGR1定義在集合A上的關(guān)系圖有所不同例如〔上例〕,A={a,b,c},R1={<a,a>,<a,b>,<b,a>,<b,c>},R2={<a,b>,<a,c>,<b,c>},那么關(guān)系圖如下：3-5.5

二元關(guān)系的表示關(guān)系矩陣、關(guān)系圖(討論):當(dāng)A中元素標(biāo)定次序后,R

A

A的關(guān)系圖GR與R的序偶集合表達(dá)式可以唯一互相確定。R的序偶集合表達(dá)式，關(guān)系矩陣，關(guān)系圖三者均可以唯一互相確定。3-5.5

二元關(guān)系的表示第三章集合與關(guān)系(Sets&Relations)小結(jié):本節(jié)介紹了關(guān)系的定義、幾種特殊的關(guān)系及關(guān)系的表示。重點(diǎn)掌握關(guān)系的表示方法。作業(yè)：P109(2)(5)b)d)給出關(guān)系圖和關(guān)系矩陣〔1〕

自反性(reflexivity)〔2〕

反自反性(irreflexivity)〔3〕

對(duì)稱性(symmetry)〔4〕

反對(duì)稱性(antisymmetry)〔5〕

傳遞性(transitivity)3-6關(guān)系的性質(zhì)需要指出：從X到Y(jié)的關(guān)系R是XY的子集，即RXY，而XY〔XY〕〔XY〕所以R〔XY〕〔XY〕令Z=XY，那么RZZ因此，我們今后通常限于討論同一集合上的關(guān)系。3-6關(guān)系的性質(zhì)3-6.1自反性(reflexivity)定義3-6.1〔自反性reflexivity〕：設(shè)R為定義在A上的二元關(guān)系，即RAA,如果對(duì)于每一個(gè)xA，有xRx(<x,x>R)，那么稱二元關(guān)系R是自反的。R在A上是自反的(x)(xAxRx)R在A上是非自反的(x)(xA<x,x>R)。定理：

R是自反的

IA

RMR主對(duì)角線上的元素全為1GR的每個(gè)頂點(diǎn)處均有自環(huán)。自反性(舉例)：平面上三角形的全等關(guān)系，實(shí)數(shù)集中實(shí)數(shù)的小于等于關(guān)系，冪集上的集合的相等、包含關(guān)系，命題集合上的命題的等價(jià)、蘊(yùn)含關(guān)系。3-6.1自反性(reflexivity)3-6.2

反自反性(irreflexivity)定義〔反自反性irreflexivity〕：設(shè)RAA,如果對(duì)于每一個(gè)xA，有<x,x>R，那么稱二元關(guān)系R是反自反的。R在A上是反自反的(x)(xA<x,x>R)。R在A上是非反自反的(x)(xAxRx)定理：R是反自反的IAR=MR主對(duì)角線上的元素全為0GR的每個(gè)頂點(diǎn)處均無(wú)自回路〔無(wú)環(huán)〕。反自反性(舉例)：數(shù)的大于關(guān)系，冪集上的集合之間的真包含關(guān)系。注意：非自反不一定是反自反的。即存在有關(guān)系既不是自反的也不是反自反的。3-6.2

反自反性(irreflexivity)3-6.3

對(duì)稱性(symmetry)

定義〔對(duì)稱性symmetry〕：設(shè)RAA,如果對(duì)于每個(gè)x,yA,每當(dāng)xRy，就有yRx，那么稱集合A上的關(guān)系R是對(duì)稱的。R在A上對(duì)稱(x)(y)(xAyAxRyyRx).R非對(duì)稱(x)(y)(xAyAxRyyRx)定理：R是對(duì)稱的MR是對(duì)稱的GR的任何兩個(gè)頂點(diǎn)之間假設(shè)有邊,那么必有兩條方向相反的有向邊.對(duì)稱性(舉例)：平面上三角形的相似關(guān)系，人群中人之間的同學(xué)、同事、鄰居關(guān)系，冪集中集合相等的關(guān)系。命題集合上的命題的等價(jià)關(guān)系。3-6.3

對(duì)稱性(symmetry)

3-6.4反對(duì)稱性(antisymmetry)定義〔反對(duì)稱性antisymmetry〕：設(shè)RAA,如果對(duì)于每個(gè)x,yA,每當(dāng)xRy和yRx，必有x=y，那么稱集合A上的關(guān)系R是反對(duì)稱的。R是反對(duì)稱的(x)(y)(xAyAxRyyRxx=y)(x)(y)(xAyAx≠yxRyyRx).R非反對(duì)稱(x)(y)(xAyAxRyyRxxy)定理：R是反對(duì)稱的在MR中,xixj(ijrij=1rji=0)在GR中,xixj(ij),假設(shè)有有向邊<xi,xj>,那么必沒有<xj,xi>。3-6.4反對(duì)稱性(antisymmetry)反對(duì)稱性(舉例)：

實(shí)數(shù)集中的小于等于關(guān)系、整數(shù)的整除關(guān)系，集合的包含關(guān)系、命題的蘊(yùn)含關(guān)系。注意：非對(duì)稱不一定反對(duì)稱；可能有某種關(guān)系即是對(duì)稱的又是反對(duì)稱的。例如：A={1,2,3},S={<1,1>,<2,2>,<3,3>}S在A上即是對(duì)稱的又是反對(duì)稱的。

N={<1,2>,<1,3>,<3,1>}N在A上即不是對(duì)稱的又不是反對(duì)稱的。3-6.4反對(duì)稱性(antisymmetry)3-6.5

傳遞性(transitivity)定義〔傳遞性transitivity〕：設(shè)RAA,如果對(duì)于任意的x,y,zA,每當(dāng)xRy，yRz時(shí)就有xRz，稱關(guān)系R在A上是傳遞的。R在A上是傳遞的(x)(y)(z)(xAyAzAxRyyRzxRz)R非傳遞(x)(y)(z)(xAyAzAxRyyRzxRz)。定理：R是傳遞的在GR中,xixjxk(ijk),假設(shè)有有向邊<xi,xj>和<xj,xk>,那么必有<xi,xk>。傳遞性(舉例)：實(shí)數(shù)集中的實(shí)數(shù)之間的小于等于、小于、等于關(guān)系;冪集上的集合之間的包含、真包含關(guān)系;命題集合上的命題的等價(jià)、蘊(yùn)含關(guān)系。人群中人之間的同姓關(guān)系。3-6.5

傳遞性(transitivity)3-6.6

舉例例1：在N={0,1,2,…}上：

={<x,y>|x

N

y

N

x

y}自反,反對(duì)稱,傳遞

={<x,y>|x

N

y

N

x

y}自反,反對(duì)稱,傳遞<={<x,y>|x

N

y

N

x<y}反自反,反對(duì)稱,傳遞接上頁(yè)>={<x,y>|x

N

y

N

x>y}(大于關(guān)系)反自反,反對(duì)稱,傳遞D={<x,y>|x

N

y

N

x|y}(整除關(guān)系)反對(duì)稱,傳遞(

0|0)IN={<x,y>|x

N

y

N

x=y}(恒等關(guān)系)自反,對(duì)稱,反對(duì)稱,傳遞EN={<x,y>|x

N

y

N}=N

N(全域關(guān)系)自反,對(duì)稱,傳遞3-6.6

舉例例2：判斷以下關(guān)系所具有的性質(zhì)。A={a,b,c}R1={<a,a>,<a,b>,<b,c>,<a,c>},R2={<a,a>,<a,b>,<b,c>,<c,a>},R3={<a,a>,<b,b>,<a,b>,<b,a>,<c,c>},R4={<a,a>,<a,b>,<b,a>,<c,c>},R5={<a,a>,<a,b>,<b,b>,<c,c>},R6={<a,b>,<b,a>,<b,c>,<a,a>},R7=

3-6.6

舉例解答：R1={<a,a>,<a,b>,<b,c>,<a,c>}反對(duì)稱,傳遞R2={<a,a>,<a,b>,<b,c>,<c,a>}反對(duì)稱R3={<a,a>,<b,b>,<a,b>,<b,a>,<c,c>}自反,對(duì)稱,傳遞R4={<a,a>,<a,b>,<b,a>,<c,c>}對(duì)稱R5={<a,a>,<a,b>,<b,b>,<c,c>}自反,反對(duì)稱,傳遞R6={<a,b>,<b,a>,<b,c>,<a,a>}R7=〔空關(guān)系〕反自反，對(duì)稱，傳遞，反對(duì)稱.3-6.6

舉例

例6

設(shè)，下面分別給出集合A上三個(gè)關(guān)系的關(guān)系圖，試判斷它們的性質(zhì)。（2）非自反，也不是反自反，非對(duì)稱，反對(duì)稱，可傳遞。（3）是自反的，對(duì)稱的，可傳遞的，不是反自反，也不是反對(duì)稱。解（1）是自反的，非對(duì)稱，不是反對(duì)稱，不可傳遞但第三章集合與關(guān)系(Sets&Relations)小結(jié):本節(jié)介紹了關(guān)系的根本性質(zhì)及其判別方法。作業(yè)：P113〔3〕〔6〕3-7復(fù)合關(guān)系和逆關(guān)系3-7.1復(fù)合關(guān)系定義1[復(fù)合(合成)(composite)關(guān)系]:設(shè)R為X到Y(jié)的關(guān)系，S為從Y到Z上的關(guān)系，那么R°S稱為R和S的復(fù)合關(guān)系，表示為：R°S={<x,z>|xXzZ(y)(yY<x,y>R<y,z>S)}.3-7.2逆關(guān)系定義2[逆(inverse)關(guān)系]:設(shè)R是X到Y(jié)的二元關(guān)系，那么從Y到X的二元關(guān)系Rc定義為：Rc={<y,x>|<x,y>R}.整數(shù)集合上的“>〞關(guān)系的逆關(guān)系是“<〞關(guān)系。人群中的父子關(guān)系的逆關(guān)系是子父關(guān)系。容易看出(Rc)c=R3-7復(fù)合關(guān)系和逆關(guān)系例1:設(shè)R={<a,b>,<c,d>},S={<b,e>,<d,c>}.求:(1)Rc，Sc.(2)R°S,S°R解:(1)Rc={<b,a>,<d,c>}Sc={<e,b>,<c,d>}.(2)R°S={<a,e>,<c,c>}S°R={<d,d>}.例2:〔書上的例題2，第115頁(yè)〕3-7復(fù)合關(guān)系和逆關(guān)系定理1:設(shè)R1,R2,R3為關(guān)系，R1是X到Y(jié)的關(guān)系，R2是Y到Z的關(guān)系，R3是Z到W的關(guān)系那么(R1°R2)°R3=R1°(R2°R3)．證明:<x,w>,<x,w>(R1°R2)°R3z(zZx(R1°R2)zzR3w)z(zZy(yYxR1yyR2z)zR3w)zy(zZyYxR1yyR2zzR3w)yz(zZyYxR1y(yR2zzR3w))y(yYxR1yz(zZyR2zzR3w))y(yYxR1yy(R2°R3)w)xR1°(R2°R3)w<x,w>R1°(R2°R3)(R1°R2)°R3=R1°(R2°R3).#說(shuō)明:本定理說(shuō)明復(fù)合運(yùn)算滿足結(jié)合律.3-7復(fù)合關(guān)系和逆關(guān)系

由復(fù)合關(guān)系滿足結(jié)合律，可以把關(guān)系R本身所組成的復(fù)合關(guān)系寫成：R°R，R°R°R，

，R°R°

°R(m個(gè))，分別記作R(2)，R(3)，

，R(m)。可以證明復(fù)合關(guān)系不滿足交換律。R1°R2

R2°R13-7復(fù)合關(guān)系和逆關(guān)系7-3.3關(guān)系矩陣的性質(zhì)：(1)MRc=(MR)T.(T表示矩陣轉(zhuǎn)置)(2)MR1°R2=MR1

MR2

(

表示布爾乘法,其中加法使用邏輯

,乘法使用邏輯

)3-7復(fù)合關(guān)系和逆關(guān)系3-7.4逆關(guān)系關(guān)系圖的性質(zhì)：關(guān)系Rc的圖形是將關(guān)系R圖形中弧的箭頭方向反置。3-7復(fù)合關(guān)系和逆關(guān)系定理2:設(shè)R、R1、R2都是從A到B的二元關(guān)系，那么有(1)(R1R2)c=R1cR2c(2)(R1R2)c=R1cR2c(3)(A×B)c=B×A(4)(~R)c=~Rc,這里~R＝A×B-R(5)(R1-R2)c=R1c-R2c注：證明(1)(4)(5)見書117頁(yè)。3-7復(fù)合關(guān)系和逆關(guān)系定理3:設(shè)R,S為二元關(guān)系,那么(R°S)c=Sc°Rc.證明:<x,y>,<x,y>(R°S)c<y,x>(R°S)z(yRzzSx)z(zRcyxScz)z(xSczzRcy)<x,y>Sc°Rc.3-7復(fù)合關(guān)系和逆關(guān)系定理4:設(shè)R為X上的二元關(guān)系，那么(1)R是對(duì)稱的R=Rc〔證明見書118頁(yè)〕(2)是反對(duì)稱的RRcIX〔留作練習(xí)〕定理5:[P119(2)]設(shè)R為X上的二元關(guān)系，那么(1)R是傳遞的(R°R)R(2)R是自反的IXR3-7復(fù)合關(guān)系和逆關(guān)系例題:設(shè)A={a,b,c},R1={<a,a>,<a,b>,<b,a>,<b,c>},R2={<a,b>,<a,c>,<b,c>},用MR1,MR2確定MR1c,MR2c,MR1°R1,MR1°R2,MR2°R1,從而求出它們的集合表達(dá)式.3-7復(fù)合關(guān)系和逆關(guān)系110110MR1=101MR1c=100000010011000MR2=001MR2c=100000110011MR1

R2=MR1

MR2=011000R1°R2

={<a,b>,<a,c>,<b,b>,<b,c>}.3-7復(fù)合關(guān)系和逆關(guān)系110110111MR1

R1=MR1

MR1=101

101=110000000000R1°R1

={<a,a>,<a,b>,<a,c>,<b,a>,<b,b>}.011110101MR2

R1=MR2

MR1=001

101=000000000000R2°R1

={<a,b>,<a,c>}.3-7復(fù)合關(guān)系和逆關(guān)系解:R1c={<a,a>,<a,b>,<b,a>,<c,b>}R2c={<b,a>,<c,a>,<c,b>}R1°R1

={<a,a>,<a,b>,<a,c>,<b,a>,<b,b>}.R1°R2

={<a,b>,<a,c>,<b,b>,<b,c>}.R2°R1

={<a,b>,<a,c>}.3-7復(fù)合關(guān)系和逆關(guān)系第三章集合與關(guān)系(Sets&Relations)小結(jié):本節(jié)主要介紹了關(guān)系的復(fù)合運(yùn)算與逆運(yùn)算。重點(diǎn)掌握關(guān)系的復(fù)合運(yùn)算及其性質(zhì)、關(guān)系的逆運(yùn)算的性質(zhì)。作業(yè)：P118(1)(2)(4) (8)3-8關(guān)系的閉包運(yùn)算自反閉包r(R)(reflexivityclosure)對(duì)稱閉包s(R)(symmetryclosure)傳遞閉包t(R)(transitivityclosure)閉包的性質(zhì),求法,相互關(guān)系3-8.1自反閉包(reflexiveclosure)定義1[自反閉包]:

包含給定關(guān)系R的最小自反關(guān)系,稱為R的自反閉包,記作r(R).(1)r(R)是自反的;(2)R

r(R);(3)(

S)((R

S

S自反)

r(R)

S).3-8關(guān)系的閉包運(yùn)算3-8.2對(duì)稱閉包(symmetricclosure)定義2[對(duì)稱閉包]:

包含給定關(guān)系R的最小對(duì)稱關(guān)系,稱為R的對(duì)稱閉包,記作s(R).(1)s(R)是對(duì)稱的;(2)R

s(R);(3)(

S)((R

S

S對(duì)稱)

s(R)

S).3-8關(guān)系的閉包運(yùn)算3-8.3傳遞閉包(transitiveclosure)定義3[傳遞閉包]:

包含給定關(guān)系R的最小傳遞關(guān)系,稱為R的傳遞閉包,記作t(R).(1)t(R)是傳遞的;(2)R

t(R);(3)(

S)((R

S

S傳遞)

t(R)

S).3-8關(guān)系的閉包運(yùn)算定理1:設(shè)RAA且A,那么(1)R自反r(R)=R;(2)R對(duì)稱s(R)=R;(3)R傳遞t(R)=R;證明:(1)RRR自反r(R)R又Rr(R),r(R)=R.(2)(3)完全類似.3-8關(guān)系的閉包運(yùn)算*〔補(bǔ)充〕定理1:設(shè)R1R2AA且A,那么(1)r(R1)r(R2);(2)s(R1)s(R2);(3)t(R1)t(R2);證明:(1)R1R2r(R2)自反,r(R1)r(R2)(2)(3)類似可證.3-8關(guān)系的閉包運(yùn)算*〔補(bǔ)充〕定理2:設(shè)R1,R2AA且A,那么(1)r(R1R2)=r(R1)r(R2);(2)s(R1R2)=s(R1)s(R2);(3)t(R1R2)t(R1)t(R2).證明:(1)利用補(bǔ)充定理1,r(R1)r(R2)r(R1R2).r(R1)r(R2)自反且包含R1R2,所以r(R1R2)r(R1)r(R2).r(R1R2)=r(R1)r(R2)3-8關(guān)系的閉包運(yùn)算證明(2):利用補(bǔ)充定理1,

s(R1)

s(R2)

s(R1

R2).s(R1)

s(R2)對(duì)稱且包含R1

R2,所以

s(R1

R2)

s(R1)

s(R2).

s(R1

R2)=s(R1)

s(R2)證明(3):利用補(bǔ)充定理1,t(R1

R2)

t(R1)

t(R2).

反例:t(R1)

t(R2)不滿足傳遞性.3-8關(guān)系的閉包運(yùn)算定理2:設(shè)RAA且A,那么(1)r(R)=RIA;(2)s(R)=RRc;(3)t(R)=RR2R3….比照:R自反IARR對(duì)稱R=RcR傳遞R2R3-8關(guān)系的閉包運(yùn)算證明:(1)r(R)=R

IA;i)R

R

IA;ii)IA

R

IA

R

IA自反

r(R)

R

IA;iii)R

r(R)

r(R)自反

R

r(R)

IA

r(R)

R

IA

r(R)

r(R)=R

IA.3-8關(guān)系的閉包運(yùn)算證明:(2)s(R)=R

Rc;i)R

R

Rc;ii)(R

Rc)c=R

Rc

R

Rc對(duì)稱

s(R)

R

Rc;iii)R

s(R)

s(R)對(duì)稱

R

s(R)

Rc

s(R)

R

Rc

s(R)

s(R)=R

Rc.3-8關(guān)系的閉包運(yùn)算證明(3)之前，說(shuō)明以下事實(shí)：復(fù)合運(yùn)算對(duì)并運(yùn)算滿足分配律R1

°(R2

R3)=(R1

°R2)(R1

°R3)(R1

R2)°R3=(R1

°R3)(R2

°R3)復(fù)合運(yùn)算對(duì)交運(yùn)算滿足弱分配律R1

°(R2

R3)

(R1°R2)(R1

°R3)(R1

R2)°R3

(R1°R2)(R1

°R3)3-8關(guān)系的閉包運(yùn)算證明:(3)t(R)=R

R2

R3

….證明:i)先證t(R)

R

R2

R3

…;∵R

R

R2

R3

…;∵(R

R2

R3

…)2=R2

R3

…

R

R2

R3

…

R

R2

R3

…傳遞

∴

t(R)

R

R2

R3

…;ii)再證R

R2

R3

…

t(R)∵R

t(R)

t(R)傳遞

R

t(R)

R2

t(R)

R3

t(R)

…

R

R2

R3

…

t(R)

t(R)=R

R2

R3

….#3-8關(guān)系的閉包運(yùn)算定理3：設(shè)X是含有n個(gè)元素的集合，R是X上的二元關(guān)系，那么存在一個(gè)正整數(shù)kn，使得t(R)=RR2R3…Rk證明：見P122。3-8關(guān)系的閉包運(yùn)算例題1:設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}.

求r(R),s(R),t(R).解:r(R)=R

IA={<a,a>,<b,b>,<c,c>,<d,d>,<a,b>,<b,a>,<b,c>,<c,d>}s(R)=R

Rc={<a,b>,<b,a>,<b,c>,<c,b>,<c,d><d,c>}t(R)=R

R2

R3

R4

={<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c>,<b,d>,<c,d>}見P1233-8關(guān)系的閉包運(yùn)算求傳遞閉包的另一種方法：當(dāng)有限集X的元素較多時(shí)，矩陣運(yùn)算很繁瑣，Warshall在1962年提出了R+的一個(gè)有效算法如下：〔1〕置新矩陣A=M〔2〕置i=1〔3〕對(duì)所有j如果A[j,i]=1，那么對(duì)k=1,2,…,nA[j,k]=A[j,k]+A[i,k]〔4〕i=i+1〔5〕如果in,那么轉(zhuǎn)到步驟〔3〕,否那么停止。3-8關(guān)系的閉包運(yùn)算引出下面定理：閉包運(yùn)算是否可以交換順序?即：(1)rs(R)=sr(R)?(2)rt(R)=tr(R)