二元关系课件

*

二元关系*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},{d}}

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

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