计算机计算机数学-7关系的闭包运算

3-8关系的闭包运算

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性质P66页反面,P95(6),(7),(8)

3-9集合的划分和覆盖

我们介绍了关系的几种重要运算,求复合运算、逆运算和闭包运算,今天我们介绍

3-9集合的划分和覆盖

内部的关系.将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},{b},{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构成的集合称为5和7的对N的交叉划分。

如4=忸力,储，G={{a},{b,c}},H={{a,b},{c}},则G和H的交叉划分是

{{a},{b},{c}},同样也是A的划分

3-9集合的划分和覆盖

对交叉划分有如下定理

定理：设｛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定义：设｛4,4，--，4｝和｛4，2，…,2｝电的两种划分，若对

每一个4，存在绮使得4=%，则称｛44,…，4”是

｛g,鸟，…，纹｝的加细。

｛4,4,…,4｝是｛4,的加细（如图）。

3-9集合的划分和覆盖.

对于交叉划分和加细有如下定理：

定理：任意两种划分的交叉划分必是原来划分的加细.

证明是简单的口与=口夕=故交叉划分是

4LJ4,L4IJB.Js

的加细，也是T的加细。

下面介绍集合中一个重要的关系：等价关系。

3-10等价类与等价关系

1定义：若R为集合A上一个关系，满足R是自反的、对称的、

传递的，则R称为等价关系。

如三角形的相似关系1A1-A2^A2~AI

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

“=”为等价关系<R,=>

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

<2,3>,<3,2X3,3>},则R是等价关系。

3-10等价类与等价关系

R的关系矩阵：

43

3-10等价类与等价关系

陈的对角线元数全为1,GR中每个节点有自回路・・・R是自反的

MR是对称矩阵，GR中每两个节点要么没有连线，要么有成对

出现，JR是对称的

传递性只能由序偶判断，逐一检查得R是传递的。

・♦・由上所述可知R是等价关系

例2.1:整数集R=｛〈X,Y>|X三Y(modk)｝这里X三Y(modk)

表示X、Y被k除有相同的余数，叫做同余模k关系

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

Y=kt2+a0<a<k

即X—Y=k(ti-t2)则R是一个等价关系。

3-10等价类与等价关系^

证明：

1.XZ"=X——内=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

是传递的，因此尺是等价关系。

3-10等价类与等价关系

由等价关系可以引出一个等价类定义：

R是A上等价关系，x、yeAo若xRy称x和y是属于同一个

等价类的

2.定义：G[a]R={x\<a.x>£火}称为由a关于火

的等价类或由。形成的△的等价类

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

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

3-10等价类与等价关系

{...,-5,-2,1,4,7,...}被3除余数为1的集合

{3n+1|nei)

{..L2卢乃・・•}被3除余数为2的集合

{3n+2|n£1)

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

全体整数集I被分成了三

个不同的等价类

3-10等价类与等价关系

3.定理:

对称性传递

证明：=<a,Z?>e凡设c£［0火=>=>cRa=>cRb

对称

今bRc=cw［b］R

・•・［叫口现

I司30二・・［。］衣=

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

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

注:证明很简单，但是利用R的定义很重要。因而对等价类来说，

要么相等，要么交为空。

3-10等价类与等价关系

4.定义:

等价类:元素的集合，A的子集；商集:集合的集合

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

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

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

由等价关系可以商集，商集与A有何关系?

3-10等价类与等价关系

5.定理：R是A上等价关系，A/R是A的一个划分。

证：①覆盖。A/R={[a]RIaEA}oaU[a]R=A。

②任意两个[@]RW[b]R,要证[@八门[b]—。o

反证法：假设[a]Rn[b]RW0,3：eA

ce[a]R且ce[b]Ro

又寸彳安

.,.aRc且bRcq>Rbb

由定理可得[a]-[b]R与假设矛盾。

[a]Rn[b]R=0,从而A/R是A的一个划分。

反之，有划分便可确定一等价关系。

3-10等价类与等价关系

6.定理：集合A的一个划分可以确定A的一个等价关系。

证明比较简单。

<=>

s={svS2,........，Sm}作一关系R,aRba,b在

同一分块中。

可以证明R是自反的、对称的、传递的（请自证），故R是

等价关系

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

S={{a,b},{c},{d}}是划分。

则确定的等价关系R为

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

3-10等价类与等价关系

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

R为：每一分块自身作直积、取并。