*

二元關系*7.1有序對與笛卡兒積定義1

由兩個元素x和y按照一定順序排列而成的二元組稱為有序對（序偶），記作<x,y>或(x,y).注:(1)<x,y>中允許x=y(2)當x

y時，<x,y>

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

x=u，y=v(4)有序對之間不能比較大小.對比{x,y}*笛卡兒積定義2

設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*笛卡兒積的性質(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.

*性質證明證明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).*實例例2

設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)*實例例2

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

右=

.*實例例2

設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>}.*實例例2

設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

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

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

R,則記作x

y

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

當B=A時,稱A×A的子集為A上的二元關系.

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

{<x,x>|x∈A}為A上的恒等關系,記作IA

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

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

R,可以定義以下關系：L<={<x,y>|x,y

A

x<y}A上的小于關系L≤={<x,y>|x,y

A

x

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

>

R，則從xi向xj

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

n為R的關系矩陣,記作MR.*實例例2

設A={1,2,3,4},

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

求R的關系矩陣MR和關系圖GR.*7.3

關系的運算定義1

設R是二元關系.

(1)R中所有有序對的第一個元素構成的集合稱為R的定義域,記作domR

(2)R中所有有序對的第二個元素構成的集合稱為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}*關系運算定義2

設R為二元關系.R的逆(關系)R

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

R}性質1

設R為二元關系.(1)(R

1)

1=R(2)domR

1=ranR

ranR

1

=domR定義3

設F,G為二元關系,G對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>}*性質2

設F,G,H為二元關系,則(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關系運算的性質*性質2

設F,G,H為二元關系,則(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*關系運算的性質定理

設R為A上的二元關系,則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*關系運算(限制與像)定義

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

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

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

的子集，即R[A]

ranR

*實例例3

設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}*關系運算的性質定理

設R為關系,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].*關系的冪運算定義設R為A上的關系,n為自然數,則R的n次冪定義為：(1)R0={<x,x>|x∈A

}=IA(2)

Rn+1=Rn

R例4

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

解R與

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

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

R0的關系矩陣是

冪的求法*關系圖R0,R1,R2,R3,…的關系圖如下圖所示.

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

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

Rn

=Rm+n(2)(Rm)n

=Rmn

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

若n=0,則有Rm

R0=Rm

IA

=Rm

=Rm+0

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

假設(Rm)n

=Rmn,則有

(Rm)n+1

=(Rm)n

Rm

=(Rmn)

Rm

=Rmn+m

=Rm(n+1)

所以對一切m,n∈N

有(Rm)n

=Rmn.

定理

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

Rn

=Rm+n(2)(Rm)n

=Rmn

*冪運算的性質定理

設A為n元集,R是A上的關系,則存在自然數s和t,使得Rs

=Rt.證R為A上的關系,

由于|A|=n,A上的不同關系只有個.

列出R的各次冪

R0,R1,R2,…,,…,

必存在自然數s和t使得Rs

=Rt

.

*定理

設R

是A上的關系,若存在自然數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冪運算的性質證(1)Rs+k

=Rs

Rk

=Rt

Rk

=Rt+k有窮集上的關系R的冪序列是一個周期性變化的序列*定理

設R

是A上的關系,若存在自然數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

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

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

設R

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

1},則對于任意q∈N

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

若q≥t,

則存在自然數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.

設A={a,b,d,e,f},

R={<a,b>,<b,a>,<d,e>,<e,f>,<f,d>}.求出最小的自然數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>},

最小的自然數m=0,n=6,R0=R6=IA

*7.4關系的性質定義

設R為A上的關系,(1)若對于每個x∈A,都有<x,x>

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

,都有<x,x>

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

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

設R為A上的關系,

(1)若對于每個x,y∈A,當<x,y>∈R就有<y,x>∈R,則稱R在A上是對稱的.(2)若對于每個x,y∈A,當<x,y>∈R和<y,x>∈R時,必有x=y,則稱R在A上是反對稱的.設A＝{1,2,3},R1,R2,R3和R4都是A上的關系,其中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：既不對稱也不反對稱*傳遞性定義

設R為A上的關系,若對于任意x,y,z∈A,當<x,y>∈R,<y,z>∈R時,就有<x,z>∈R,

則稱R是A上的傳遞關系.例:

設A＝{1,2,3},R1,R2,R3是A上的關系,其中

R1＝{<1,1>,<2,2>}

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

R3＝{<1,3>}R1和R3是A上的傳遞關系,R2不是A上的傳遞關系.*關系性質成立的充要條件定理

設R為A上的關系,則(1)R在A上自反當且僅當

IA

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

R∩IA=

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

R=R

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

R∩R

1

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

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關系矩陣主對角線元素全是1主對角線元素全是0矩陣是對稱矩陣若rij＝1,且i≠j,則rji＝0M2中1位置,M中相應位置都是1關系圖每個頂點都有環每個頂點都無環兩點之間無單向邊兩點之間無雙向邊只要可達均可一步到達

關系性質的三種等價條件*例1.

判斷A={1,2,3}上下列關系的性質，并說明理由.請給出A上關系R,使其同時不滿足自反、反自反、對稱、反對稱和傳遞性.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

√××××關系的性質和運算之間的聯系*7.5關系的閉包

如果關系R不具有自反性、對稱性和傳遞性，那么可以給R增加盡可能少的有序對，使R具有這些性質，這就是關系閉包.定義1

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

：(1)R

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

R

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

有R

R

*7.5關系的閉包

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

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

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

R∪IA

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

R∪IA設R

是A上包含R的自反關系,則有R

R

和IA

R

.從而有R∪IA

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

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

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

t(R).假設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是轉置矩陣，+表示矩陣中對應元素邏輯加.0+0=0,0+1=1,1+0=1,1+1=1閉包的圖表示:關系圖中,考察每個頂點,若無環就加環,得Gr

考察每條邊,若僅有單向邊,則添一條反向邊,得Gs考察所有可達頂點,只要可達必定一步到達,得Gt*實例例1

設A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},

作出R和r(R),s(R),t(R)的關系圖.Rr(R)s(R)t(R)*定理2

設R1和R2是非空集合A上的關系,且R1

R2,(1)r(R1)

r(R2)(2)s(R1)

s(R2)(3)t(R1)

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

R2n.對n歸納.n=1,顯然為真.假設n=k時,命題為真.任取<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

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

等價關系與劃分

定義1

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

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

證明：R是等價關系.這個等價關系將12級信息專業學生以寢室為單位進行了劃分.*例2

下面哪些關系是等價關系？(1)在一群人的集合上年齡相等的關系(2)在一群人的集合上朋友關系(3)同一平面上三角形之間的相似關系(4)同一平面上直線之間的平行關系(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}關系圖被分為三個互不連通的部分,每部分中的數兩兩都有關系,不同部分中的數則沒有關系.定義2

設R為非空集合A上的等價關系,

x∈A,令[x]R

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

設R是非空集合A上的等價關系,則(1)

x

A,[x]

A且非空.(2)

x,y

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

x,y

A,若x

y,則[x]∩[y]=.(4)等價類的性質證(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)假設[x]∩[y]≠

,則存在z

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

[x]∧z

[y],即<x,z>

R∧<y,z>

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

R,與x

y矛盾.*定義3

設R為非空集合A上的等價關系,以R的不交等價類為元素的集合稱為A關于R的商集,記做A/R.

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

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

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

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

(2)A上的等價關系與A的劃分是一一對應的.*

例3

設A＝{a,b,c,d},給定

1,

2,

3,

4,

5,

6如下：

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

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

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}上所有的等價關系.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偏序關系

定義1

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

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

x?y

x

y*例1.

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

),其中

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

),其中

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

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