二元關(guān)系課件VIP

*

二元關(guān)系*7.1有序?qū)εc笛卡兒積定義1

由兩個(gè)元素x和y按照一定順序排列而成的二元組稱為有序?qū)Γㄐ蚺迹?，記?lt;x,y>或(x,y).注:(1)<x,y>中允許x=y(2)當(dāng)x

y時(shí)，<x,y>

<y,x>(3)<x,y>=<u,v>當(dāng)且僅當(dāng)

x=u，y=v(4)有序?qū)χg不能比較大小.對比{x,y}*笛卡兒積定義2

設(shè)A,B為集合，稱集合A

B={<x,y>|x

A

y

B}為A和B的笛卡兒積.例1

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

A

B={<1,a>,<1,b>,<2,a>,<2,b>,<3,a>,<3,b>}

B

A={<a,1>,<b,1>,<a,2>,<b,2>,<a,3>,<b,3>}A={

},B=

P(A)

A={<

,

>,<{

},

>}P(A)

B=

A

B

B

A*笛卡兒積的性質(zhì)(1)A

=

B=

(2)A

B

B

A(A

B,A

,B

)(3)(A

B)

C

A

(B

C)(A

,B

,C

)(4)A

(B

C)=(A

B)

(A

C)(B

C)

A=(B

A)

(C

A)

A

(B

C)=(A

B)

(A

C)(B

C)

A=(B

A)

(C

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

B|=mn.

*性質(zhì)證明證明A

(B

C)=(A

B)

(A

C)證

<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).*實(shí)例例2

設(shè)A,B,C,D為任意集合,判斷以下命題是否為真(1)(A∩B)

(C∩D)=(A

C)∩(B

D)(2)(A∪B)

(C∪D)=(A

C)∪(B

D)(3)(A

B)

(C

D)=(A

C)

(B

D)(4)(A

B)

(C

D)=(A

C)

(B

D)解(1)為真.<x,y>

(A

C)∩(B

D)

<x,y>

A

C<x,y>

B

D

x

A

y

C

x

B

y

D

x

(A∩B)

y

(C∩D)

<x,y>

(A∩B)

(C∩D)*實(shí)例例2

設(shè)A,B,C,D為任意集合,判斷以下命題是否為真(1)(A∩B)

(C∩D)=(A

C)∩(B

D)(2)(A∪B)

(C∪D)=(A

C)∪(B

D)(3)(A

B)

(C

D)=(A

C)

(B

D)(4)(A

B)

(C

D)=(A

C)

(B

D)解(2)不一定.

A=D=

,B={1},C={2},

左={1}

{2}={<1,2>}

右=

.*實(shí)例例2

設(shè)A,B,C,D為任意集合,判斷以下命題是否為真(1)(A∩B)

(C∩D)=(A

C)∩(B

D)(2)(A∪B)

(C∪D)=(A

C)∪(B

D)(3)(A

B)

(C

D)=(A

C)

(B

D)(4)(A

B)

(C

D)=(A

C)

(B

D)解(3)不一定.

A=B={1},C={2},D={3},

左=

右={<1,2>}

{<1,3>}={<1,2>}.*實(shí)例例2

設(shè)A,B,C,D為任意集合,判斷以下命題是否為真(1)(A∩B)

(C∩D)=(A

C)∩(B

D)(2)(A∪B)

(C∪D)=(A

C)∪(B

D)(3)(A

B)

(C

D)=(A

C)

(B

D)(4)(A

B)

(C

D)=(A

C)

(B

D)解(4)不一定.

A=B={1},C={2},D={3},

左=

右={<1,2>}

{<1,3>}={<1,2>,<1,3>}.*7.2

二元關(guān)系定義1(1)若集合中所有元素都是有序?qū)?則稱此集合為二元關(guān)系,簡稱關(guān)系，記作R.

若<x,y>∈R,可記作xRy；R若<x,y>

R,則記作x

y

(2)設(shè)A,B為集合,A×B的任一子集為A到B的二元關(guān)系.

當(dāng)B=A時(shí),稱A×A的子集為A上的二元關(guān)系.

是任何集合上的二元關(guān)系，稱為空關(guān)系.A×A是A上的全域關(guān)系,記作EA

{<x,x>|x∈A}為A上的恒等關(guān)系,記作IA

*問：若|A|=n,則A上有多少種關(guān)系？例1.A={微積分,線性代數(shù),離散數(shù)學(xué),英語}

B={5,4,4.5,2}R={<x,y>|課程x的學(xué)分為y}若A

R,可以定義以下關(guān)系：L<={<x,y>|x,y

A

x<y}A上的小于關(guān)系L≤={<x,y>|x,y

A

x

y}A上的小于等于關(guān)系*關(guān)系的表示(2)設(shè)A={x1,x2,…,xn}，以A中元素為頂點(diǎn),若<xi,xj

>

R，則從xi向xj

引有向邊，所得的有向圖為R的關(guān)系圖,記作GR.(1)設(shè)A={x1,x2,…,xn}，R是A上的關(guān)系.則(rij)n

n為R的關(guān)系矩陣,記作MR.*實(shí)例例2

設(shè)A={1,2,3,4},

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

求R的關(guān)系矩陣MR和關(guān)系圖GR.*7.3

關(guān)系的運(yùn)算定義1

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

(1)R中所有有序?qū)Φ牡谝粋€(gè)元素構(gòu)成的集合稱為R的定義域,記作domR

(2)R中所有有序?qū)Φ牡诙€(gè)元素構(gòu)成的集合稱為R的值域,記作ranR

(3)domR

ranR=fldR,稱為R的域例1

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

domR={1,2,4}ranR={2,3,4}

fldR={1,2,3,4}*關(guān)系運(yùn)算定義2

設(shè)R為二元關(guān)系.R的逆(關(guān)系)R

1={<y,x>|<x,y>

R}性質(zhì)1

設(shè)R為二元關(guān)系.(1)(R

1)

1=R(2)domR

1=ranR

ranR

1

=domR定義3

設(shè)F,G為二元關(guān)系,G對F的右復(fù)合

F

G={<x,y>|

t(<x,t>

F

<t,y>

G)}*例2

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

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

R

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

R

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

S

R={<1,2>,<1,4>,<3,2>,<3,3>}*性質(zhì)2

設(shè)F,G,H為二元關(guān)系,則(1)(F

G)

H=F

(G

H)(2)(F

G)

1=G

1

F

1(3)F

(G∪H)

=F

G∪F

H(4)(G∪H)

F=G

F∪H

F(5)F

(G∩H)

F

G∩F

H(6)(G∩H)

F

G

F∩H

F關(guān)系運(yùn)算的性質(zhì)*性質(zhì)2

設(shè)F,G,H為二元關(guān)系,則(1)(F

G)

H=F

(G

H)證明證

<x,y>

(F

G)

H

t(<x,t>∈F

G∧<t,y>∈H)

t(

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

t

s(<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>∈G

H)

<x,y>∈F

(G

H)

所以(F

G)

H=F

(G

H)*證明(2)(F

G)

1=G

1

F

1證<x,y>∈(F

G)

1

<y,x>∈F

G

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

t(<x,t>∈G

1∧<t,y>∈F

1)

<x,y>∈G

1

F

1

所以(F

G)

1=G

1

F

1

*證明(5)F

(G∩H)

F

G∩F

H<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>∈F

G∧<x,y>∈F

H

<x,y>∈F

G∩F

H

故F

(G∩H)

F

G∩F

H*關(guān)系運(yùn)算的性質(zhì)定理

設(shè)R為A上的二元關(guān)系,則R

IA=IA

R=R證任取<x,y>

<x,y>∈R

IA

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

t(<x,t>∈R∧t=y∧y∈A)

<x,y>∈R*關(guān)系運(yùn)算(限制與像)定義

設(shè)R為二元關(guān)系,A是集合(1)R在A上的限制R?A={<x,y>|xRy∧x∈A

}(2)A在R下的像R[A]=ran(R?A)說明：R在A上的限制R?A是R的子關(guān)系，即R?A

RA在R下的像R[A]是ranR

的子集，即R[A]

ranR

*實(shí)例例3

設(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}*關(guān)系運(yùn)算的性質(zhì)定理

設(shè)R為關(guān)系,A,B為集合,則(1)R?(A∪B)=R?A∪R?B(2)R[A∪B]=R[A]∪R[B](3)R?(A∩B)=R?A∩R?B(4)R[A∩B]

R[A]∩R[B]

*證明證

(1)任取<x,y>

<x,y>∈R?(A∪B)

<x,y>∈R∧x∈A∪B

<x,y>∈R∧(x∈A∨x∈B)

(<x,y>∈R∧x∈A)∨(<x,y>∈R∧x∈B)

<x,y>∈R?A∨<x,y>∈R?B

<x,y>∈R?A∪R?B

故R?(A∪B)=R?A∪R?B.*證明(4)任取y,

y∈R[A∩B]

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

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

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

x(<x,y>∈R∧x∈A)∧

x

(<x,y>∈R∧x∈B)

y∈R[A]∧y∈R[B]

y∈R[A]∩R[B]

所以有R[A∩B]

R[A]∩R[B].*關(guān)系的冪運(yùn)算定義設(shè)R為A上的關(guān)系,n為自然數(shù),則R的n次冪定義為：(1)R0={<x,x>|x∈A

}=IA(2)

Rn+1=Rn

R例4

設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R的各次冪,分別用矩陣和關(guān)系圖表示.*

解R與

R2的關(guān)系矩陣分別是：冪的求法*R3和R4的矩陣是：因此M4=M2,即R4=R2.因此可以得到

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

R0的關(guān)系矩陣是

冪的求法*關(guān)系圖R0,R1,R2,R3,…的關(guān)系圖如下圖所示.

R0R1R2=R4=…R3=R5=…*定理

設(shè)R是A上的關(guān)系,m,n∈N,則(1)Rm

Rn

=Rm+n(2)(Rm)n

=Rmn

冪運(yùn)算的性質(zhì)證用數(shù)學(xué)歸納法(1)對于任意給定的m∈N,施歸納于n.

若n=0,則有Rm

R0=Rm

IA

=Rm

=Rm+0

假設(shè)Rm

Rn

=Rm+n,則有

Rm

Rn+1

=Rm

(Rn

R)=(Rm

Rn)

R=Rm+n+1,

所以對一切m,n∈N

有Rm

Rn

=Rm+n.*證明(2)對于任意給定的m∈N,施歸納于n.

若n=0,則有(Rm)0=IA=R0

=Rm×0

假設(shè)(Rm)n

=Rmn,則有

(Rm)n+1

=(Rm)n

Rm

=(Rmn)

Rm

=Rmn+m

=Rm(n+1)

所以對一切m,n∈N

有(Rm)n

=Rmn.

定理

設(shè)R是A上的關(guān)系,m,n∈N,則(1)Rm

Rn

=Rm+n(2)(Rm)n

=Rmn

*冪運(yùn)算的性質(zhì)定理

設(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

=Rt

.

*定理

設(shè)R

是A上的關(guān)系,若存在自然數(shù)s,t(s<t)使得Rs=Rt,則

(1)對任何k∈N有Rs+k

=Rt+k

(2)對任何k,i∈N有Rs+kp+i

=Rs+i,其中p=t

s(3)令S={R0,R1,…,Rt

1},則對于任意q∈N

有Rq∈S冪運(yùn)算的性質(zhì)證(1)Rs+k

=Rs

Rk

=Rt

Rk

=Rt+k有窮集上的關(guān)系R的冪序列是一個(gè)周期性變化的序列*定理

設(shè)R

是A上的關(guān)系,若存在自然數(shù)s,t(s<t)使得Rs=Rt,則

(2)對任何k,i∈N有Rs+kp+i

=Rs+i,其中p=t

s

證明(2)對k歸納.若k=0,則有Rs+0p+i=Rs+i

假設(shè)Rs+kp+i

=Rs+i,其中p=t

s,則

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

=Rs+kp+i

Rp

=Rs+i

Rp

=Rs+p+i

=Rs+t

s+i=Rt+i

=Rs+i

由歸納法命題得證.*證明定理

設(shè)R

是A上的關(guān)系,若存在自然數(shù)s,t(s<t)使得Rs=Rt,則(3)令S={R0,R1,…,Rt

1},則對于任意q∈N

有Rq∈S證：任取q∈N,若q<t,顯然有Rq∈S,

若q≥t,

則存在自然數(shù)k和i使得

q=s+kp+i,其中0≤i≤p

1.

于是

Rq

=Rs+kp+i

=Rs+i

而

s+i≤s+p

1=s+t

s

1=t

1

從而證明了

Rq∈S.*例5.

設(shè)A={a,b,d,e,f},

R={<a,b>,<b,a>,<d,e>,<e,f>,<f,d>}.求出最小的自然數(shù)m和n,使得m<n且Rm=Rn.解：R2={<a,a>,<b,b>,<d,f>,<e,d>,<f,e>},R3={<a,b>,<b,a>,<d,d>,<e,e>,<f,f>},

R6={<a,a>,<b,b>,<d,d>,<e,e>,<f,f>},

最小的自然數(shù)m=0,n=6,R0=R6=IA

*7.4關(guān)系的性質(zhì)定義

設(shè)R為A上的關(guān)系,(1)若對于每個(gè)x∈A,都有<x,x>

R,則稱R在A上是自反的.(2)若對于每個(gè)x∈A

,都有<x,x>

R,則稱R在A上是反自反的.例：設(shè)A={1,2,3},R1,R2,R3是A上的關(guān)系,其中

R1＝{<1,1>,<2,2>}R2＝{<1,3>}R3＝{<1,1>,<2,2>,<3,3>,<1,2>}R1既不是自反的也不是反自反的,R2是反自反的,R3是自反的.*對稱性與反對稱性定義

設(shè)R為A上的關(guān)系,

(1)若對于每個(gè)x,y∈A,當(dāng)<x,y>∈R就有<y,x>∈R,則稱R在A上是對稱的.(2)若對于每個(gè)x,y∈A,當(dāng)<x,y>∈R和<y,x>∈R時(shí),必有x=y,則稱R在A上是反對稱的.設(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：對稱和反對稱；

R2：只有對稱；

R3：只有反對稱；

R4：既不對稱也不反對稱*傳遞性定義

設(shè)R為A上的關(guān)系,若對于任意x,y,z∈A,當(dāng)<x,y>∈R,<y,z>∈R時(shí),就有<x,z>∈R,

則稱R是A上的傳遞關(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)系.*關(guān)系性質(zhì)成立的充要條件定理

設(shè)R為A上的關(guān)系,則(1)R在A上自反當(dāng)且僅當(dāng)

IA

R(2)R在A上反自反當(dāng)且僅當(dāng)

R∩IA=

(3)R在A上對稱當(dāng)且僅當(dāng)

R=R

1(4)R在A上反對稱當(dāng)且僅當(dāng)

R∩R

1

IA(5)R在A上傳遞當(dāng)且僅當(dāng)

R

R

R

*證明(3)必要性.任取<x,y>,<x,y>∈R

<y,x>∈R

<x,y>∈R

1所以R=R

1

充分性.任取<x,y>,由R=R

1得

<x,y>∈R

<y,x>∈R

1

<y,x>∈R所以R在A上是對稱的.*證明(4)必要性.任取<x,y>,有

<x,y>∈R∩R

1

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

1

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

x=y

x,y

A

<x,y>∈IA這就證明了R∩R

1

IA

充分性.任取<x,y>,<x,y>∈R∧<y,x>∈R

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

1

<x,y>∈R∩R

1

<x,y>∈IA

x=y從而證明了R在A上是反對稱的.*證明(5)

必要性.任取<x,y>有<x,y>∈R

R

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

<x,y>∈R

所以R

R

R

充分性.任取<x,y>,<y,z>∈R,則

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

<x,z>∈R

R

<x,z>∈R

所以R在A上是傳遞的.*

自反性反自反性對稱性反對稱性傳遞性集合IA

RR∩IA=

R=R

1R∩R

1

IAR

R

R關(guān)系矩陣主對角線元素全是1主對角線元素全是0矩陣是對稱矩陣若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)之間無單向邊兩點(diǎn)之間無雙向邊只要可達(dá)均可一步到達(dá)

關(guān)系性質(zhì)的三種等價(jià)條件*例1.

判斷A={1,2,3}上下列關(guān)系的性質(zhì)，并說明理由.請給出A上關(guān)系R,使其同時(shí)不滿足自反、反自反、對稱、反對稱和傳遞性.R1={<1,1>,<1,2>,<1,3>,<2,1>,<3,1>}R2={<2,1>,<3,1>}R3={<1,1>,<2,2>,<3,3>,<2,1>,<3,2>,<1,3>}R={<1,1>,<2,2>,<2,3>,<3,2>,<3,1>}*自反性反自反性對稱性反對稱性傳遞性R1

1

√√√√√R1∩R2

√√√√√R1∪R2

√√√××R1

R2

×√√√×R1

R2

√××××關(guān)系的性質(zhì)和運(yùn)算之間的聯(lián)系*7.5關(guān)系的閉包

如果關(guān)系R不具有自反性、對稱性和傳遞性，那么可以給R增加盡可能少的有序?qū)Γ筊具有這些性質(zhì)，這就是關(guān)系閉包.定義1

設(shè)R是非空集合A上的關(guān)系,R的自反(對稱或傳遞)閉包是A上滿足以下條件的關(guān)系R

：(1)R

是自反的(對稱的或傳遞的)(2)R

R

(3)對A上任何包含R的自反(對稱或傳遞)關(guān)系R

有R

R

*7.5關(guān)系的閉包

注:(1)R的自反閉包記作r(R),對稱閉包記作s(R),傳遞閉包記作t(R).(2)R的自反(對稱或傳遞)閉包是包含R的最小自反(對稱或傳遞)關(guān)系.(3)若R已經(jīng)是自反的(對稱的或傳遞的)，則R的自反(對稱或傳遞)閉包就是R.*定理1

設(shè)R為A上的關(guān)系,則有(1)r(R)=R∪IA(2)s(R)=R∪R

1(3)t(R)=R∪R2∪R3∪…說明：對有窮集A(|A|=n)上的關(guān)系,(3)中的并最多不超過Rn*證明(1)證由IA

R∪IA

知R∪IA是自反的,且滿足R

R∪IA設(shè)R

是A上包含R的自反關(guān)系,則有R

R

和IA

R

.從而有R∪IA

R.R∪IA滿足閉包定義,所以r(R)=R∪IA.*證明(3)先證R∪R2∪…

t(R)成立.用歸納法證明對任意正整數(shù)n有Rn

t(R).n=1時(shí)有R1=R

t(R).假設(shè)Rn

t(R)成立,那么對任意的<x,y>,

<x,y>∈Rn+1=Rn

R

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

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

<x,y>∈t(R)這就證明了Rn+1

t(R).由歸納法命題得證.

*證明再證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)

t

s(<x,z>∈Rt

Rs

)

t

s(<x,z>∈Rt+s

)

<x,z>∈R∪R2∪…從而證明了R∪R2∪…是傳遞的.*閉包的矩陣表示和圖表示閉包的矩陣表示:Mr=M+EMs=M+MT

Mt=M+M2+M3+…E是單位矩陣,MT是轉(zhuǎn)置矩陣，+表示矩陣中對應(yīng)元素邏輯加.0+0=0,0+1=1,1+0=1,1+1=1閉包的圖表示:關(guān)系圖中,考察每個(gè)頂點(diǎn),若無環(huán)就加環(huán),得Gr

考察每條邊,若僅有單向邊,則添一條反向邊,得Gs考察所有可達(dá)頂點(diǎn),只要可達(dá)必定一步到達(dá),得Gt*實(shí)例例1

設(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)*定理2

設(shè)R1和R2是非空集合A上的關(guān)系,且R1

R2,(1)r(R1)

r(R2)(2)s(R1)

s(R2)(3)t(R1)

t(R2)(3)證只需證明對于任意正整數(shù)n,R1n

R2n.對n歸納.n=1,顯然為真.假設(shè)n=k時(shí),命題為真.任取<x,y>,<x,y>R1k+1

<x,y>R1k°R1

t(<x,t>R1k

<t,y>R1)

t(<x,t>R2k

<t,y>R2)<x,y>R2k°R2

<x,y>R2k+1

*反例：A={1,2,3},R={<1,3>}是傳遞的;

s(R)={<1,3>,<3,1>}不是傳遞的.定理3

設(shè)R是非空集合A上的關(guān)系,(1)若R是自反的,則s(R)與t(R)也是自反的.(2)若R是對稱的,則r(R)與t(R)也是對稱的.(3)若R是傳遞的,則r(R)是傳遞的.*7.6

等價(jià)關(guān)系與劃分

定義1

設(shè)R為非空集合A上的關(guān)系.如果R是自反的、對稱的和傳遞的,則稱R為A上的等價(jià)關(guān)系.若<x,y>∈R,稱x等價(jià)于y,記做x～y.例1

設(shè)A={12級信息專業(yè)學(xué)生},R={<x,y>|x與y同住一個(gè)寢室,x,y∈A}.

證明：R是等價(jià)關(guān)系.這個(gè)等價(jià)關(guān)系將12級信息專業(yè)學(xué)生以寢室為單位進(jìn)行了劃分.*例2

下面哪些關(guān)系是等價(jià)關(guān)系？(1)在一群人的集合上年齡相等的關(guān)系(2)在一群人的集合上朋友關(guān)系(3)同一平面上三角形之間的相似關(guān)系(4)同一平面上直線之間的平行關(guān)系(5)A={1,2,,8},R={<x,y>|x,y

A

x

y(mod3)}*1~4~7[1]=[4]=[7]={1,4,7}2~5~8[2]=[5]=[8]={2,5,8}3~6[3]=[6]={3,6}關(guān)系圖被分為三個(gè)互不連通的部分,每部分中的數(shù)兩兩都有關(guān)系,不同部分中的數(shù)則沒有關(guān)系.定義2

設(shè)R為非空集合A上的等價(jià)關(guān)系,

x∈A,令[x]R

={y|y∈A∧x~y},稱為x(關(guān)于R)的等價(jià)類,簡記為[x]或*定理1

設(shè)R是非空集合A上的等價(jià)關(guān)系,則(1)

x

A,[x]

A且非空.(2)

x,y

A,若x~y,則[x]=[y].(3)

x,y

A,若x

y,則[x]∩[y]=.(4)等價(jià)類的性質(zhì)證(1)由定義,

x

A有[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].*(4)先證∪{[x]|x

A}

A.任取y,

y

∪{[x]|x

A}

x(x

A∧y

[x])

y

[x]∧[x]

A

y

A

從而有∪{[x]|x∈A}

A

再證A

∪{[x]|x∈A}.任取y,

y

A

y

[y]∧y

A

y∈∪{[x]|x

A}

從而有∪{[x]|x∈A}

A成立.

故∪{[x]|x

A}=A.證明(3)假設(shè)[x]∩[y]≠

,則存在z

[x]∩[y],從而有z

[x]∧z

[y],即<x,z>

R∧<y,z>

R成立.根據(jù)R的對稱性和傳遞性必有<x,y>

R,與x

y矛盾.*定義3

設(shè)R為非空集合A上的等價(jià)關(guān)系,以R的不交等價(jià)類為元素的集合稱為A關(guān)于R的商集,記做A/R.

設(shè)A={1,2,…,8},A/R={[1],[2],[3]}={[4],[5],[6]}={{1,4,7},{2,5,8},{3,6}}*定義4

設(shè)A為非空集合,若A的子集族π(π

P(A))滿足以下條件:(1)

π(2)π中任意兩個(gè)元素不交(3)∪π=A則稱π是A的一個(gè)劃分,稱π中的元素為劃分塊.注:(1)商集A/R是A的一個(gè)劃分；

(2)A上的等價(jià)關(guān)系與A的劃分是一一對應(yīng)的.*

例3

設(shè)A＝{a,b,c,d},給定

1,

2,

3,

4,

5,

6如下：

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

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

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的劃分.*例4

給出A＝{1,2,3}上所有的等價(jià)關(guān)系.123

1

123

5123

2123

4123

3R1=EA,R5=IA,R2={<2,3>,<3,2>}∪IA

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

R4={<1,2>,<2,1>}∪IA解先做出A的劃分,從左到右分別記作

1,

2,

3,

4,

5.*7.7偏序關(guān)系

定義1

設(shè)R為非空集合上的關(guān)系.如果R是自反的、反對稱的和傳遞的,則稱R為A上的偏序關(guān)系,記作?.稱<A,?>為偏序集合.

若<x,y>∈?,則記作x?y,讀作x“小于等于”y.在偏序關(guān)系中,x排在y的前邊或x就是yx?y

x?y

x

y*例1.

判斷下列集合是否為偏序集合.(1)(Z,

),其中

是Z上的小于等于關(guān)系；(2)(P(A),

),其中

是集合上的包含關(guān)系；(3)(Z+,|),其中|是Z+上的整除關(guān)系.定義2

在偏序集合<A,?>中,x,y∈A,若x?y或y?x,則稱x與y是可比的,否則稱它們是不可比的.*定義3在偏序集合<A,?>中,x,y∈A