离散数学：第四章 关系与函数

第四章关系与函数关系当今世界里，不论在社会科学，还是在自然科学中，也不论在人们日常生活中，关系无处不在无处不有。因此研究关系是十分必要的。关系在集合论中给出简明形式化定义，并且取得了一些重要结果。函数是一种特殊的二元关系，在集合论中给出一个精确而又非常一般的定义以及相关的定理。4.1有序对

恰好有两个元x，y，而且x在前，y在后，这种集合称为有序对，它的元有确定的次序，记作<x，y>。定义4.1.1<x，y>:={{x}，{x，y}}

通常，称x为有序对<x，y>的前驱或第一个成员，y为有序对<x，y>的后继或第二个成员。定理4.1.1<x，y>=<u，v>x=u∧y=v证明：必要性：设<x，y>=<u，v>，则有

{{x},{x,y}

}={{u},{u,v}

}按集合相等的定义，它们应该是具有相同的元，故或者是①{x}={u}且{x,y}={u,v}或者是②{x}={u,v}且{x,y}={u}.由①得到x=u，y=v。②则给出x=u=v且x=y=u.所以都有x=u，y=v。定理4.1.2x∈A∧y∈B

<x，y>∈P(P(A∪B))证明：因为x∈A∧y∈B，

所以x∈A∪B，{x}A∪B,即{x}∈P(A∪B);

y∈A∪B,{x,y}A∪B,即{x,y}∈P(A∪B);

即{{x},{x,y}}P(A∪B);

于是{{x},{x,y}}∈P(P(A∪B))

即<x，y>∈P(P(A∪B))。定理4.1.3①∪<x，y>={x，y}②∩<x，y>={x}③∩∩<A，B>=A

④∩∪<A，B>=A∩B

证明：①∪<x，y>=∪{{x},{x,y}}={x}∪{x,y}={x,y}②∩<x，y>=∩{{x},{x,y}}={x}∩{x,y}={x}④∩∪<A，B>=∩∪{{A},{A,B}}=∩({A}∪{A,B})=∩{A,B}=A∩B把有序对概念推广到有序n元组，n∈ω，n≥1.定义4.1.2<x>:=x，且对任意n∈ω，n≥1时，

<x1，x2，…，xn，xn+1>:=<<x1，x2，…，xn>，xn+1>定理4.1.4对任意n∈ω，有

<x0，x1，…，xn>=<y0，y1，…，yn>

x0=y0∧x1=y1∧…∧xn=yn4.2笛卡尔积定义4.2.1给定二集合A，B，所有x∈A，y∈B组成的有序对<x，y>为成员的集合，称为A，B二集合的笛卡尔积，记作A×B，即

A×B:={<x，y>|x∈A∧y∈B

}

相当于集合的乘法运算。例1：设

A={a,b

},B={1,2}，则有

A×B={<a,1>,<a,2>,<b,1>,<b,2>}

B×A={<1,a>,<1,b>,<2,a>,<2,b>}

A×B≠B×A笛卡尔乘积的性质：定理4.2.1

①<x，y>∈A×Bx∈A∧y∈B②A×B=A=∨B=

③A×B=B×A(A=∨B=∨A=B)

④A×(B∩C)=(A×B)∩(A×C)⑤AA×AA=③A×B=B×A(A=∨B=∨A=B)证明：必要性：若A×B=B×A，反证法，假设┐(A=∨B=∨A=B),

即A≠∧B≠

∧A≠

B。于是存在x，使得x∈A且xB

或x∈B且xA，不妨假设前者成立。因为B≠

，所以存在y∈B,则<x,y>∈A×B。

因为A×B=B×A，所以<x,

y>∈B×A，

则x∈B,y∈A,矛盾。结论成立。充分性：若A=或B=，则A×B=B×A=

。

若A=B，则A×B=A×A=B×A，结论成立。④A×(B∩C)=(A×B)∩(A×C)证明：对于任意有序对<x,y>，

<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)4.3二元关系及其矩阵表示定义4.3.1R

为关系:

=

(z)(z∈R→(x)(y)(z=<x，y>))。关系是一个由有序对作为成员构成的集合。如果<x,y>∈R,记作:

x

R

y。例如：关系R={<1,2>,<2,3>,<4,5>,<6,7>},

则有<1,2>∈R

记作:1

R

2,

<2,3>∈R

记作:2

R

3,…若x，y∈A，并且有RA×A={<x，y>|x∈A∧y∈A

}则称R为A中的关系；若x∈A，y∈B，并且有

RA×B={<x，y>|x∈A∧y∈B

}则称R为A×B

中的关系。关系是笛卡尔积的子集。例2：整数集Z中的平方关系：R

Z×ZR={<1,1>,<2,4>,<3,9>……}={<x,y>|y=x2,x,y∈Z}任意x，存在一个y，使y=x2一些y,不存在x使y=x2例3：整数集Z中的平方根关系：RZ×ZR={<1,1>,<4,2>,<9,3>……}={<x,y>|y=x1/2,x,y∈Z}任意y，存在一个x，使y=x1/2一些x,不存在y使y=x1/2例1：整数集Z中的大于关系R:R

Z×ZR={<1,0>,<2,1>,<3,2>……}={<x,y>|x>y,x∈Z,

y∈Z}任何x，能找到一个y，使x>y；任何y，能找到一个x，使x>y；关系与笛卡尔乘积已知关系：所有序偶的第一个元素组成集合A，所有序偶的第二个元素组成集合B，则二元关系R就是从集合A到集合B的一个关系，是A×B的一个子集。已知集合：已知两个集合A和B(或一个集合A)，通过选取A×B(或A×A)的不同子集产生A

到B(或A到A)的不同关系。定义4.3.2R

为三元关系:

=(w)(w∈R→(x)(y)(z)(w=<x，y，z>))

类似地,将R区分为A中三元关系和A×B×C中的三元关系，以及RA×A×A和RA×B×C。RA×A×A={<x，y，z>|x∈A∧y∈A∧z∈A

}RA×B×C={<x，y，z>|x∈A∧y∈B∧z∈C

}定义4.3.3xRy

<x，y>∈R

。定理4.3.1①是一个关系；②R

为关系且SR

S

为关系；③R，S

为关系

R∪S，R∩S

及R-S

为关系。关系是集合，因此可以进行集合的交、并、差的运算。给出关系R的定义域、值域和域的定义：

定义4.3.4关系R的定义域定义为

dm(R)：={x|(y)(xRy)}。定义4.3.5关系R的值域定义为

rn(R)：={y

|(x)(xRy)}定义4.3.6关系R的域定义为

fl(R)：=dm(R)∪rn(R)例1令R

=

{<0，1>，<2，3>}，求

dm(R)，rn(R)和fl(R)。解：

dm(R)

={0，2}

，

rn(R)={1，3}，

fl(R)={0，1，2，3}。定理4.3.2①(y)(xRy)x∈∪∪R；②x∈dm

(R)(y)(xRy)；

③dm(R∪S)=dm(R)∪dm(S)；

④dm(R)-dm(S)dm(R-S)。证明：①由定义4.3.3知，(xRy)<x,y>∈R，而<x,y>={{x},{x,y}},因此{{x},{x,y}}∈R。根据定理3.4.1,z∈∪R(B)(B∈R

z

∈B)

可知，｛x｝∈∪R，再次根据定理3.4.1便得：x∈∪∪R.③dm(R∪S)=dm(R)∪dm(S)证明：令x为任意元，则

x∈dm(R∪S)

(y)(xR∪Sy

)(y)(xRy

∨

xSy

)(y)(xRy)

∨(y)(xSy)（满足分配律）x∈dm(R)

∨

x∈dm(S)x∈(dm(R)

∪dm(S))

根据集合相等的定义3.2.1知,

dm(R∪S)=dm(R)∪dm(S)。④dm(R)-dm(S)dm(R-S)。证明：令x为任意元，则

x∈(dm(R)-dm(S))

x∈dm(R)∧┐x∈dm(S)(y)(xRy)∧(y)┐(xSy)

xRz

∧

┐(xSz)

(y)(xRy

∧

┐(xSy))

(y)(x(R-S)y

)

x∈dm(R-S)

即对任意元x,有x∈(dm(R)-dm(S))

x∈dm(R-S)

根据子集定义3.2.2知,dm(R)-dm(S)

dm(R∪S)。全域关系:对于集合AEA=AA={<x,y>|x∈A

∧y∈A}特殊关系：恒等关系:对于集合AIA={<x,x>|x∈A}逆关系：定义4.3.7：给定任意两个集合X

和Y，如果

R

是一个从X

到Y

的关系,则从Y

到X的关系叫逆关系：

R-1:={<y，x

>|xRy

}例2:设X={1,2,3},Y={a,b,c},

R={<1,a>,<2,b>,<3,c>}是从X到Y的关系，则R的逆关系:

R-1：={<a,1>,<b,2>,<c,3>}。定理4.3.4逆关系的性质①R-1是一个关系；②(R-1)-1=R；

③(R∩S)-1=R-1∩S-1；

④(R-S)-1=R-1-S-1；③证明：对任意元x,y,

x(R∩S)-1y

y(R∩S)xyRx

∧ySxxR-1y∧xS-1yx(R-1∩S-1)y④证明：对任意元x,y,

x(R-S)-1y

y(R-S)xyRx

∧┐(ySx)xR-1y∧┐(

xS-1y)x(R-1-S-1)y关系复合：定义4.3.8若R,

S是关系,

则R

和S

的关系复合定义为

R*S:={<x，y>|(z)(xRz

∧zSy

)}

当R=S时，记为R*R=R2。例4.3.2令R={<1，3>，<2，3>}，

S={<3，1>}，则R*S={<1，1>，<2，1>}，

S*R={<3，3>}。注意：复合运算不可交换。定理4.3.5关系复合运算性质：①xR

*Sy

(z)(xRz∧zSy)

②dm(R

*S)

dm(R)

③R*(S∩T)(R*S)∩(R*T)

④(R*S)-1=S-1*R-1⑤(R*S)*T=R*(S*T)③R*(S∩T)(R*S)∩(R*T)证明：设x,y为任意元，

xR*(S∩T)

y

(z)(x

Rz∧zS∩Ty)

(z)(xRz∧(zS

y∧zT

y))

(z)((x

Rz∧zS

y)∧(xRz∧zT

y))

(z)(x

Rz∧zS

y)∧(z)(x

Rz∧zT

y)x

R*S

y∧x

R*T

y

x(R

*S)∩(R*T)y④(R*S)-1=S-1*R-1证明：对任意x,y，

x(R*S)-1y

y

(R*S)

x

(z)(

yRz

∧

zSx

)

(z)(

xS-1z

∧

zR-1

y

)

xS-1*R-1

y⑤(R*S)*T=R*(S*T)证明：对任意x,y，

x(R*S)*Ty

(z)(xR*Sz∧zTy)

(z)(w)(xRw∧wSz∧zTy)

(w)(xRw∧(z)(wSz∧zTy))

(w)(xRw∧wS*Ty)

xR*(S*T)

y关系的幂运算关系的复合运算是可结合的。当R=S时，记为R*R=R2。

Rn+1=Rn*R=R*Rn现在考虑一种定义域与已知集合的关系以及有关定理。定义4.3.9R|ˋC:=R∩(C×rn(R))

本定义也可表为：

R|ˋC={<x，y>|xRy∧x∈C

}

即：R|ˋC也是一个关系，其定义域为C，第一分量的取值范围为C。下面定义在关系R下集合C的映像，记为R[C]以及讨论相关定理。定义4.3.10R[C]:=rn(R|ˋC)

本定义也可表为：

R[C]={y

|(x)(xRy∧x∈C)}

可见R[C]是关系R的值域，且关系R的定义域为C

。证明：③令x,y为任意元，则

x(R*S|ˋC)y

xR*Sy∧x∈C

(z)(xRz∧zSy)∧x∈C(z)(xRz∧zSy∧x∈C

)(z)(xRz

∧x∈C∧zSy)(z)(xR

|ˋCz∧zSy

)x(R|ˋC)*Sy

根据定义3.2.1知，(R*S)|ˋC=(R|ˋC)*S。定理4.3.6①xR|ˋCy

xRy∧x∈C②R|ˋ(C∩D)=(R|ˋC)∩(R|ˋD)

③(R*S)|ˋC=(R|ˋC)*S证明：③令x为任意元，则

x(dm(R)∩C)

xdm(R)∧x∈C

(y)(xRy)∧x∈C

xRz∧x∈C

xRz∧(xRz∧x∈C)zR-1x∧(w)(wRz∧

w∈C)

(u)(uR-1x∧(w)(wRu∧w∈C))(u)(uR-1x∧u∈R[C])x∈R-1[R[C]]

根据定义3.3.2知，dm(R)∩C

R-1[R[C]]。定理4.3.7①y∈R[C](x)(xRy

∧x∈C

)②R[C∩D]

R[C]∩R[D]

③dm(R)∩C

R-1[R[C]]关系矩阵表示法

设两个有限集合A={x1,x2,…,xm}，B={y1,y2,…,yn}，二元关系R

A×B。则对应于二元关系R有一个关系矩阵MR=(rij)m×n，其中

这里i=1，2，…，m，j=1，2，…，n。例子：A={x1，x2，x3}，

B={y1，y2}，

R={<x1，y1>，<x2，y2>，<x3，y2>}，则R的关系矩阵关系运算(并,交,补,差,逆,复合)的矩阵表示

设R，SA×B，TB×C，MR=(aij)m×n，MS=(bij)m×n，

MT=(cij)n×p，dij

表示运算后所得新关系之关系矩阵的元素，则①MR∪S=MR

∨

MS

dij=aij∨bij1≤i≤m，1≤j≤n②MR∩S=MR

∧

MS

dij=aij∧bij1≤i≤m，1≤j≤n③MR′

dij=┐aij

1≤i≤m，1≤j≤n④MR-S=MR

∧

MS′

dij=aij∧┐bij

1≤i≤m，1≤j≤n⑤dij=aji1≤i≤m，1≤j≤n⑥∧

dij=(aik∧ckj)1≤i≤m，1≤j≤p关系图一个有限集合A上的关系R,可以用一个称作有向图的图形直观表示,这种表示关系的有向图叫关系图。其画法如下:(1)集合A中的每一个元素a用带有元素符号的圆圈（称作结点a）表示。

(2)若a,b∈A,且aRb,则将结点a和结点b用一条带有箭头的直线或弧线连接起来,其方向由结点a

指向结点b。每一条这样的弧线称作图的边。(a)R={<-2,-1>,<-1,0>,<0,1>,<-2,1>,<-1,1>,<-2,0>}(b)R={<-2,-2>,<-1,-1>,<1,1>,<0,0>,<-2,-1>,<-1,0>,<0,1>,<-2,1>,<-1,1>,<-2,0>}(c)R={<-1,-2>,<0,-1>,<1,0>,<1,-2>,<1,-1>,<0,-2>}(d)R={<-2,-2>,<-1,-1>,<1,1>,<0,0>,<-1,-2>,<-2,-1>,<-1,0>,<0,-1>,<0,1>,<1,0>,<1,-2>,<-2,1>,<1,-1>,<-1,1>,<0,-2>,<-2,0>}(e)R={<-2,-2>,<-1,-1>,<1,1>,<0,0>}4.4关系的性质定义4.4.1R在A中自反:=(x)(x∈A→xRx)即对任意的x∈A都有<x,

x>

∈R定义4.4.2R在A中非自反:=(x)(x∈A→┐(xRx))

即对任意的x∈A都有<x,

x>

R约定：x,y,z∈A

表示x∈A∧y∈A∧z∈A；R,S,T都是表示A上关系。给出六个基本定义。例4.4.1：X={1,2,3}上的等于关系R，即

R={<1,1>,<2,2>,<3,3>}是自反的；以下关系都具有自反性：命题公式的等价关系

A≡A；集合的相等关系A=A；集合的包含关系AA；整数的大于等于关系x≥y；MR=例4.4.2：X={1,2,3}上的大于关系，即：

R={<2,1>,<3,1>,<3,2>}是非自反的。以下关系具有非自反性：集合的真包含关系；整数的大于关系；家族的父子关系；MR=定义4.4.3R在A中对称:=(x)(y)(x，y∈A∧xRy

→yRx)对任意x，y∈A,若<x,

y>∈R则有<y,

x>

∈R

定义4.4.4R在A中非对称:=(x)(y)(x，y∈A∧xRy→┐(yRx))

对任意x，y∈A,

若<x,

y>∈R则有<y,

x>

R

即：

R

对称

R-1=R即：R

非对称R∩R-1=例4.4.3：X={1,2,3}上的不等关系，即：

R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>}是对称的。以下关系具有对称性：同学关系；朋友关系；命题公式的等价关系；MR=例4.4.4：X={1,2,3}上的大于关系，即：

R={<2,1>,<3,1>,<3,2>}是非对称的。以下关系具有非对称性：集合的真包含关系；自然数的大于关系。MR=定义4.4.5R在A中反对称:=(x)(y)(x，y∈A∧xRy∧x≠y→┐(yRx))(x)(y)(x，y∈A∧xRy∧(yRx)

→x=y)

若<x,

y>

∈R且x≠y

则有<y,

x>

R

若<x,

y>

∈R且<y,

x>∈R

则有x=y定义4.4.6R在A中传递:=(x)(y)(z)(x，y，z∈A∧xRy∧yRz→xRz)

若<x,

y>

∈R且<y,

z>∈R

则有<x,

z>∈R

即：R

传递R*RR

例4.4.5：X={1,2,3}上的大于等于关系，即：

R={<1,1>,<2,1>,<2,2>,<3,1>,<3,2>,<3,3>}是反对称的。以下关系具有反对称性：集合的包含关系；自然数的大于等于关系；命题的蕴含关系。MR=定义4.4.7：定义4.4.8IA：={<x，x>|x∈A

}给出一个集合A上的恒等关系，记为IA.定理4.4.1恒等关系的性质：①xIAxx∈A②IA

*IA

=IA③R为关系Idm(R)*R=R②证明：对于任意x,y,则

xIA*IA

y(z)(xIAz∧

zIAy)xIAx∧

xIAyT

∧

xIAy

xIAy根据定义3.2.1知，IA

*IA

=IA.定理4.4.2(本定理也常被用来作为定义)

①R自反Ifl(R)R②R非自反R∩Ifl(R)=

③R对称

R-1=R④R非对称R∩R-1=⑤R反对称R∩R-1Idm(R)

⑥R传递R*RR①

R自反Ifl(R)R充分性：若Ifl(R)R，对任意x∈fl(R),有x

Ifl(R)x，又因为Ifl(R)R，所以xRx，所以R为自反的。证明：必要性：若R为自反的，

对任意x有x

Ifl(R)x，则x∈fl(R),

又因为R为自反的，所以xRx.

可得Ifl(R)R。

③

R对称

R-1=R

充分性：若R-1=R，对任意x,y∈fl(R),

若xRy，则yR-1x

。因为R-1=R

，所以yR

x

，所以R为对称的。证明：必要性：若R对称的，对任意x，y

∈fl(R),

若

x

R-1y，则y

Rx，由对称定义可得xRy，所以R-1R

；反之，若

x

Ry，由于R是对称的，则y

Rx，从而x

R-1y，所以R

R-1

。综上，可得R-1

=R

。证明：必要性：若R传递的，对任意x，y∈fl(R),

若

xR*Ry，则存在z∈fl(R),

使得xRz

并且

zRy，又因为R是传递的，所以xRy

。可得R*RR。⑥R传递R*RR充分性：若R*RR，对任意x，y，z∈fl(R),

若xR

z,zRy，则xR*Ry。又因为R*RR，所以xRy。所以R为传递的。定理4.4.7设R1、R2是A上的自反关系，则R-11、R1∩R2、R1∪R2、R1*R2

也是A上的自反关系。定理4.4.8设R1、R2是A上的非自反关系，则

R-11、R1∩R2、R1∪R2、R1-R2

是A上的非自反关系。定理4.4.9设R1、R2是A上的对称关系，则

R-11、R1∩R2、R1∪R2、R1-R2

也是A上的对称关系。定理4.4.11设R1、R2是A上的传递关系，则R-11、R1∩R2

是A上的传递关系。

但R1∪R2不一定是传递的。定理4.4.10设R1、R2是A上的反对称关系，则R-11、R1∩R2、R1-R2是A上的反对称关系。但R1∪R2不一定是反对称的。【例】A={a,b,c},讨论在下列各种情况下R*S

具有的性质。

(1)R={〈a,b〉},S={〈b,a〉},

R、S是非自反的。R*S={〈a,a〉}，所以R*S不是非自反的。R*S={〈a,c〉}，所以R*S不是对称的。(2)R={<a,b>,<b,a>},S={<b,c>,<c,b>}，R、S是对称的。(3)R={<a,b>,<b,c>},S={<b,b>,<c,a>}，

R、S是反对称的。(4)R={〈a,b〉，〈b,c〉，〈a,c〉},

S={〈b,a〉，〈b,c〉，〈c,a〉}，R、S是传递的。R*S={〈a,b〉,〈b,a〉}，所以R*S是对称的。R*S={〈a,a〉,〈a,c〉,〈b,a〉}，所以R*S不是传递的。4.5等价关系与划分定义4.5.1R为等价关系:=R为关系且R具有自反的、对称的和传递的性质。定义4.5.2R为A上等价关系:=R为等价关系且A=fl(R)。若关系R在集合A中是自反的、对称的和传递的，则称R为A上的等价关系。常见的等价关系的例子：自然数相等关系；直线的平行关系；集合的相等关系；命题的等价关系；其意义在于证实了应用抽象的一般原理的正确性，即在某方面等价的个体产生等价类，对全体等价类进行分析常常比对全体本身进行分析更简单。例4.5.1：设I为整数集合，R={<x,y>|x≡y(mod

k)，x,y∈I

},证明R是等价关系。x

≡

y(mod

k)表示x,y模k同余。证明：设任意a,b,c∈I,要证R是自反，对称和传递的。即x/k

与y/k所得到的余数是相同的,x=kt1+r1,y=kt2+r2,余数r1=r2。可以形式化表示为x-y=kt(t为整数)。即x≡y(mod

k)

x-y=kt

(1)自反性：因为a-a=k*0,所以<a,a>∈R，即R具有自反性；(2)对称性：若<a,b>∈R,即a≡b(mod

k),也即a-b=kt(t为整数)，则b-a=-kt,所以b≡a(mod

k)，即<b,a>∈R，即R具有对称性；(3)传递性：若<a,b>∈R,<b,c>∈R,即a≡b(mod

k),b≡c(mod

k)，则有a-b=kt,b-c=ks(t,s为整数)，故a-c=a-b+b-c=k(t+s),

所以a≡c(mod

k),即<a,c>∈R，即R具有传递性。例4.5.2：设A={1，2，3，4}，在幂集P(A)上规定二元关系如下：R={<s,t>|s,t∈P(A)(|s|=|t|)},其中|s|表示集合s中的元素的个数。证明R是P(A)上的等价关系。证明：设任意s,t,r∈P(A),要证R是自反，对称和传递的。①自反性：因为|s|=|s|,所以<s,s>∈R，即R具有自反性；②对称性：若<s,t>∈R,即|s|=|t|,也即|t|=|s|,所以<t,s>∈R，

即R具有对称性；③传递性：若<s,t>∈R,<t,r>∈R,即|s|=|t|,|t|=|r|,则有|s|=|r|,所以<s,r>∈R，即R具有传递性。综上,

R

是P(A)上的等价关系。

等价类

定义4.5.3设R是集合A上的等价关系，由A中元素x产生R的等价类，记为[x]R，它是由A中那些使xRy

成立的所有y∈A

组成的子集，形式地表为

[x]R

:={y

|xRy

}并且称x是等价类[x]R的一个代表。等价类[x]R

有时也记作x/R。定理4.5.2y∈[x]R

xRy。解：已经证明了R是I上的等价关系，则由I的元素所产生的等价类是：

[0]R={…,

-6,

-3,

0,

3,

6,

…}[1]R={…,

-5,

-2,

1,

4,

7,

…}[2]R={…,

-4,

-1,

2,

5,

8,

…}例4.5.3：设I为整数集合，R是模3同余的关系，

R={<x,y>|x≡y(mod3)，x,y∈I

},

确定由I的元素所产生的等价类。在集合I上模3同余等价关系R所构成的等价类有：

[0]R=[-6]R=[-3]R=[3]R=[6]R=……[1]R=[-5]R=[-2]R=[4]R=[7]R=……[2]R=[-4]R=[-1]R=[5]R=[8]R=……例4.5.4：设A={1，2，3，4}，在幂集P(A)上规定二元关系如下：R={<s,t>|s,t∈P(A)(|s|=|t|)},其中|s|表示集合s中的元素的个数。求R的等价类。证明：

已经证明R是P(A)上的等价关系。

P(A)={,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}}。R的等价类为:[]R={}[{1}]R={{1},{2},{3},{4}}[{1,2}]R={{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}[{1,2,3}]R={{1,2,3},{1,2,4},{1,3,4},{2,3,4}}[{1,2,3,4}]R={{1,2,3,4}}定理4.5.3①若x，y∈fl(R)且R为等价关系，则[x]R=[y]RxRy②R为等价关系[x]R=[y]R

∨

[x]R∩[y]R=。证明：①充分性：若xRy，则要证明[x]R=[y]R

。对任意z∈[x]R

,根据等价类定义可得xRz，因为R是等价关系，R是对称的，所以zRx，又因为xRy，

R是传递的，所以zRy，即yRz，故z∈[y]R

。因此[x]R

[y]R

。同理可证[y]R

[x]R

。因此，[x]R

=[y]R

。必要性：由等价类定义可知，y∈[y]R,又已知[x]R=[y]R，则y∈[x]R,由定理4.5.2可得xRy。②R为等价关系[x]R=[y]R∨[x]R∩[y]R=。证明：对任意x,y，若x,y不属于fl(R)，则[x]R=

，[y]R=

，所以[x]R=[y]R。

令x,y∈fl(R)，若xRy，则[x]R=[y]R成立。若┐(xRy)，假设[x]R∩[y]R

=不成立。设z∈[x]R∩[y]R，即xRz，yRz

。因为R是等价关系，则R是对称的、传递的。由xRz，zRy，可得xRy，产生矛盾！所以[x]R∩[y]R=。结论成立。划分

一个集合A的划分，记为πA，是指A

的互不相交的非空子集簇，且这些子集的并等于A。形式定义为：定义4.5.4

πA:

=

(∪πA=A)①∧(B)(C)(B，C∈πA

∧B≠C→B∩C=

)②∧((B)(B∈πA→(x)(x∈B))(B是非空的)③例4.5.5：

A={1，2，3}，

πA

={{1}，{2，3}}，

πA′={{1，2}，{3}}，

πA″={{1,2,3}}。πA

与πA′不可比的，而πA

比πA″更细。为了建立等价类与划分的密切关系，现给出由A上等价关系R产生的等价类集合的定义：定义4.5.6

πA(R):={[x]R|x∈A

∧R为A上等价关系}类似地，定义等价关系R产生的等价类集合：

π(R):={[x]R

|x∈f

l(R)∧R为等价关系}证明：②πA(R):={[x]R|x∈A

∧R为A上等价关系}定理4.5.5①[x]R∈πA(R)x∈A∧R为A上等价关系。②πA(R)是A的一种划分。因为R是A上的等价关系，所以对任意x∈A，有xRx，即x∈[x]R

,因此A∪πA(R)。又由于[x]R

A，所以∪πA(R)A，即A=∪πA(R)。又因为对任意[x]R,都有x∈[x]R,所以x∈[x]R

≠

。由定理4.5.3可知，对任意[x]R，[y]R,都有

或者[x]R=[y]R,或者[x]R∩[y]R=。

根据划分的定义可得，πA(R)是A的一种划分。

常常把由等价关系R产生集合A的划分，记为A/R，读作A模R，称为A对R的商集。例4.5.3等价关系R={<x,y>|x≡y(mod3)，x,y∈I

}的商集为：

I/R={[0]R,[1]R,[2]R}例4.5.4A={1,2,3,4},等价关系R={<s,t>|s,t∈P(A)(|s|=|t|)}的商集为：

I/R={[]R,

[{1}]R,[{1,2}]R,[{1,2,3}]R,[{1,2,3,4}]R}4.6函数函数概念是最基本的数学概念之一，也是最重要的数学工具。初中数学中函数定义为“对自变量每一确定值都有一确定的值与之对应”的因变量；高中数学中函数又被定义为两集合元素之间的映射。用一个特殊关系具体规定这一映射，称这个特殊关系为函数，因为关系是一个集合，从而又将函数作为集合来研究。定义4.6.1f为函数：=f为关系∧(x)(y)(z)(xfy∧xfz→y

=z)

对于函数符号不仅使用xfy，也常常使用f(x)=y。有时为了表示出函数的定义域A和值域B，也记为f：A→B。

（1）从X

到Y

的函数的定义域是X，不能是X的某个真子集。（2）若<x,y>∈f，<x,y′>∈f，则y＝y′（单值性）。一个函数是一个多对一的关系，即对该关系的定义域中的任何元恰恰只对应于值域中的一个元，定义域中的不同元可以对应于值域中同一元，其形式定义是：例1

设A={a,b},B={1,2,3}，判断下列集合是否是A到B的函数。解：

F1={〈a,1〉,〈b,2〉},

F2={〈a,1〉,〈b,1〉}，

F3={〈a,1〉,〈a,2〉},

F4={〈a,3〉}是是否否定义4.6.2设f:A→B，g:C→D，如果A=C，B＝D，且对所有x∈A，有f(x)＝g(x)，称函数f等于g,记为f=g。如果AC，B＝D，且对每一个x∈A，有f(x)＝g(x)，称函数f包含于g，记为fg。当不强调函数是定义在哪个集合上的时候，由于函数是序偶的集合（特殊的关系），所以f=g的充分必要条件是fg

且gf。函数的复合运算定义4.6.2f○g=g*f

要求：rn(g)dm(f)定理4.6.1

(1)f，g为函数且rn(g)dm(f)

f○g也为函数且

(f○g)(x)=f(g(x))

(2)(f○g)|ˋC

=

f○(g|ˋC)现在定义1-1函数和反函数的概念

定义4.6.3f为1-1函数:=

f和f

-1皆为函数。定义4.6.4若f为1-1函数，则称f

-1为反函数。定理4.6.2若f为1-1函数且x1，x2∈dm(f)，则

f

(x1)

=

f

(x2)

x1=x2。①若f为1-1函数，则f

-1(y)=xf(x)=y；定理4.6.3①若f

为1-1函数，则f

-1(y)=x

f(x)=y；②f

为1-1函数∧x∈dm(f)f

-1(f(x))=x；③f，g为1-1函数f∩g为1-1函数。证明：必要性：若f-1(y)=x，则<y,x>∈f-1，于是<x,y>∈f,

因为f为1-1函数，因此，f(x)=y。充分性：若f(x)=y，则<x,y>∈f,于是<y,x>∈f

-1，因为f为1-1函数，所以f

-1为函数，因此f

-1(y)=x.定义4.6.5

①f为从A到B的函数:=f为函数∧dm(f)=A∧rn(f)B

②f为从A到B中的函数:=f为函数∧dm(f)=A∧rn(f)B

③f为从A到B上的函数或f为满射:=

f为函数∧dm(f

)=A∧rn(f

)=B④f为单射或f为一对一映射（单射）:=

f为函数∧(x)(y)(x,y∈A∧x≠y→f(x)≠f(y))

⑤f为双射或f为一一对应:=

f既为单射又为满射或f为1-1函数。⑥实数x的底函数，记为x，指小于或等于x的最大整数。

实数x的顶函数，记为x，指大于或等于x的最小整数。⑦散列函数h:K→D，h(k)=d，其中K为关键码集，D为地址集合。常用散列函数是用除法求余，中平方方法和折迭方法得到。⑧恒等函数，设AB，若idA：A→B，使idA(x)=x，则称idA为A上的一个恒等函数。恒等函数是单射函数，而且仅当A=B时恒等函数才是满射，并且idA=IA。⑨特征函数，设AB，函数fA：B→{0，1}定义为则称fA：B→{0，1}是集合A的一个特征函数。【例】设A={a,b},B={1,2,3}。由A→B能生成多少个不同的函数？

由B→A能生成多少个不同的函数？解：设fi

:A→B,gi

:B→A

f1={〈a,1〉,〈b,1〉}

g1={〈1,a〉,〈2,a〉,〈3,a〉}

f2={〈a,1〉,〈b,2〉}g2={〈1,a〉,〈2,a〉,〈3,b〉}

f3={〈a,1〉,〈b,3〉}g3={〈1,a〉,〈2,b〉,〈3,a〉}

f4={〈a,2〉,〈b,1〉}g4={〈1,a〉,〈2,b〉,〈3,b〉}

f5={〈a,2〉,〈b,2〉}g5={〈1,b〉,〈2,a〉,〈3,a〉}

f6={〈a,2〉,〈b,3〉}g6={〈1,b〉,〈2,a〉,〈3,b〉}

f7={〈a,3〉,〈b,1〉}g7={〈1,b〉,〈2,a〉,〈3,b〉}

f8={〈a,3〉,〈b,2〉}g8={〈1,b〉,〈2,b〉,〈3,b〉}

f9={〈a,3〉,〈b,3〉}定理设|A|=m，|B|=