計算機計算機數(shù)學(xué)-7關(guān)系的閉包運算

3-8關(guān)系的閉包運算

1=5A中第5列,A[3,5]=1,將第5列加入到第3列,不變

1=6,j=7,第6列，第7列全為0,???A不變

ri/i,o,i,o,o,o

0,1,0,0,0,0,0

/+=A=

0,0,0,0,1,0,0

0,1,0,1,0,0,0

這一算法只是用來求不是重點，P127(5)頁介紹了求"人的方

KR

法。

定理3-8.6r,s,t性質(zhì)P66頁反面,P95(6),(7),(8)

3-9集合的劃分和覆蓋

我們介紹了關(guān)系的幾種重要運算,求復(fù)合運算、逆運算和閉包運算,今天我們介紹

3-9集合的劃分和覆蓋

內(nèi)部的關(guān)系.將A分為若干非空的子集一分塊，定義A的劃分與覆蓋.

tn

定義：A是非空集合,S={S],S2,..............>S,A,USj=A,S稱為

A的覆蓋.又若/則稱s為AZ=1

如A={a,b,c}下列一些集合:

S={{a,b},{a,c}}S是A的覆蓋,S不是A的劃分.

Q={{a},{a,b},{b,c}Q是A的覆蓋,S不是A的劃分.

G={{a,b,c}}劃分一最小劃分

E={{a},,{c}}劃分一最大劃分

3-9集合的劃分和覆蓋

F={{a},{b,c}}劃分

H={{a},{a,b}）不是覆蓋，不是劃分.

注意:對于覆蓋而言，一個元素可以屬于兩個分塊，而對于劃分，一個元

素僅屬于且必屬于一個分塊，劃分一定是覆蓋,但覆蓋未必是劃分.

2.集合4S={S],S2—.,SJ,7={7],7；,...,7；}是4的兩個戈1」分，把

所有S,CIT/工0構(gòu)成的集合稱為5和7的對N的交叉劃分。

如4=忸力,儲，G={{a},{b,c}},H={{a,b},{c}},則G和H的交叉劃分是

{{a},,{c}},同樣也是A的劃分

3-9集合的劃分和覆蓋

對交叉劃分有如下定理

定理：設(shè)｛44,…，4J與｛4，鳥，…，用｝是/的兩種劃分，則它們的交叉劃

分也是力的一種劃分。

證：要證明是劃分必須證兩點,(a)覆蓋;(b)任兩分塊不交

交叉戈分｛404,4062,…，4ng，/2rl4，/2n笈2,…，42口

斗…,4ng,4n鳥，…，4一旦｝將其中空集去掉。

⑴力的覆蓋(4A^1)uu1n52)u...u(4n^)u(^2n51)u(^2n52)

u…uc42fM)u...u(4n4)u(4,n鳥)u…u(4.n紇)

=(4A(^U52u...U5j)u(^2n(^U52u...UB))u...u(4.n(^iU

鳥U...Uq))

=(4U4J..U4)n(4lMJ..U3s)=/nz=/

3-9集合的劃分和覆蓋

（2）4n4,4n紜任兩個分塊，則有如下三種情況:

wj,h=k,4n4=0,4n線n4Pl紇=0

S)2Wj,h^k,AQAj=0,BhCBk=0:.AinBhnA^Bk=0

(c)i=j,h手左，同(a)

（4n紇）n（4n線）=0故交叉劃分也是4的劃分

3定義：設(shè)｛4,4，--，4｝和｛4，2，…,2｝電的兩種劃分，若對

每一個4，存在綺使得4=%，則稱｛44,…，4”是

｛g,鳥，…，紋｝的加細。

｛4,4,…,4｝是｛4,的加細（如圖）。

3-9集合的劃分和覆蓋.

對于交叉劃分和加細有如下定理：

定理：任意兩種劃分的交叉劃分必是原來劃分的加細.

證明是簡單的口與=口夕=故交叉劃分是

4LJ4,L4IJB.Js

的加細，也是T的加細。

下面介紹集合中一個重要的關(guān)系：等價關(guān)系。

3-10等價類與等價關(guān)系

1定義：若R為集合A上一個關(guān)系，滿足R是自反的、對稱的、

傳遞的，則R稱為等價關(guān)系。

如三角形的相似關(guān)系1A1-A2^A2~AI

(Al~A2,A2~A3=>A1~AS

“=”為等價關(guān)系<R,=>

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

<2,3>,<3,2X3,3>},則R是等價關(guān)系。

3-10等價類與等價關(guān)系

R的關(guān)系矩陣：

43

3-10等價類與等價關(guān)系

陳的對角線元數(shù)全為1,GR中每個節(jié)點有自回路???R是自反的

MR是對稱矩陣，GR中每兩個節(jié)點要么沒有連線，要么有成對

出現(xiàn)，JR是對稱的

傳遞性只能由序偶判斷，逐一檢查得R是傳遞的。

???由上所述可知R是等價關(guān)系

例2.1:整數(shù)集R=｛〈X,Y>|X三Y(modk)｝這里X三Y(modk)

表示X、Y被k除有相同的余數(shù)，叫做同余模k關(guān)系

X=kti+aX=Y(modk)tl、t2、I

Y=kt2+a0<a<k

即X—Y=k(ti-t2)則R是一個等價關(guān)系。

3-10等價類與等價關(guān)系^

證明：

1.XZ"=X——內(nèi)=k-O.,xJ^x

???衣^^目及白勺。

2.jCjRy^x—y=kt?y一x=—kt=kQ-t)

「.yAc,小是對稱的。

3.xRy.yRz.

x—y—kt}.y—z—kt2x—z—x—y+y—z—ktx+kt2—kt

是傳遞的，因此尺是等價關(guān)系。

3-10等價類與等價關(guān)系

由等價關(guān)系可以引出一個等價類定義：

R是A上等價關(guān)系，x、yeAo若xRy稱x和y是屬于同一個

等價類的

2.定義：G[a]R={x\<a.x>￡火}稱為由a關(guān)于火

的等價類或由。形成的△的等價類

如例1中：口口={1,4}=甩,⑵x={2,3}=[3]火

例2中：取k=3.R={<x.y>\x=y(mod3)}

3-10等價類與等價關(guān)系

{...,-5,-2,1,4,7,...}被3除余數(shù)為1的集合

{3n+1|nei)

{..L2盧乃???}被3除余數(shù)為2的集合

{3n+2|n￡1)

[O]A=[3k=[―34

全體整數(shù)集I被分成了三

個不同的等價類

3-10等價類與等價關(guān)系

3.定理:

對稱性傳遞

證明：=<a,Z?>e凡設(shè)c￡［0火=>=>cRa=>cRb

對稱

今bRc=cw［b］R

???［叫口現(xiàn)

I司30二??［。］衣=

<^曰矢口二?=［萬］衣

自反，件:cz三［0］尺.*.CL巨［旬尺「?bRci=>ciRb

注:證明很簡單，但是利用R的定義很重要。因而對等價類來說，

要么相等，要么交為空。

3-10等價類與等價關(guān)系

4.定義:

等價類:元素的集合，A的子集；商集:集合的集合

如例1中：T/R={[1]…[2]尺},集合元素互異，只有兩個

口卜=[3k，[2k=[4k

例2中：//尺={[OLJ1]欠」2]欠）取典型元素為代表。

由等價關(guān)系可以商集，商集與A有何關(guān)系?

3-10等價類與等價關(guān)系

5.定理：R是A上等價關(guān)系，A/R是A的一個劃分。

證：①覆蓋。A/R={[a]RIaEA}oaU[a]R=A。

②任意兩個[@]RW[b]R,要證[@八門[b]—。o

反證法：假設(shè)[a]Rn[b]RW0,3：eA

ce[a]R且ce[b]Ro

又寸彳安

.,.aRc且bRcq>Rbb

由定理可得[a]-[b]R與假設(shè)矛盾。

[a]Rn[b]R=0,從而A/R是A的一個劃分。

反之，有劃分便可確定一等價關(guān)系。

3-10等價類與等價關(guān)系

6.定理：集合A的一個劃分可以確定A的一個等價關(guān)系。

證明比較簡單。

<=>

s={svS2,........，Sm}作一關(guān)系R,aRba,b在

同一分塊中。

可以證明R是自反的、對稱的、傳遞的（請自證），故R是

等價關(guān)系

例A={a、b、c、d},

S={{a,b},{c},cempamt}是劃分。

則確定的等價關(guān)系R為

{<a,b>,<a,a>,<c,c>,<d,d>,<b,a>,<b,b>}

3-10等價類與等價關(guān)系

也就是也1xS1)U(S2x^2U(S3x^3)

R為：每一分塊自身作直積、取并。