離散數(shù)學(xué)：第四章 關(guān)系與函數(shù)

第四章關(guān)系與函數(shù)關(guān)系當(dāng)今世界里，不論在社會(huì)科學(xué)，還是在自然科學(xué)中，也不論在人們?nèi)粘Ｉ钪?，關(guān)系無處不在無處不有。因此研究關(guān)系是十分必要的。關(guān)系在集合論中給出簡明形式化定義，并且取得了一些重要結(jié)果。函數(shù)是一種特殊的二元關(guān)系，在集合論中給出一個(gè)精確而又非常一般的定義以及相關(guān)的定理。4.1有序?qū)?/p>

恰好有兩個(gè)元x，y，而且x在前，y在后，這種集合稱為有序?qū)?，它的元有確定的次序，記作<x，y>。定義4.1.1<x，y>:={{x}，{x，y}}

通常，稱x為有序?qū)?lt;x，y>的前驅(qū)或第一個(gè)成員，y為有序?qū)?lt;x，y>的后繼或第二個(gè)成員。定理4.1.1<x，y>=<u，v>x=u∧y=v證明：必要性：設(shè)<x，y>=<u，v>，則有

{{x},{x,y}

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

}按集合相等的定義，它們應(yīng)該是具有相同的元，故或者是①{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))證明：因?yàn)閤∈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把有序?qū)Ω拍钔茝V到有序n元組，n∈ω，n≥1.定義4.1.2<x>:=x，且對(duì)任意n∈ω，n≥1時(shí)，

<x1，x2，…，xn，xn+1>:=<<x1，x2，…，xn>，xn+1>定理4.1.4對(duì)任意n∈ω，有

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

x0=y0∧x1=y1∧…∧xn=yn4.2笛卡爾積定義4.2.1給定二集合A，B，所有x∈A，y∈B組成的有序?qū)?lt;x，y>為成員的集合，稱為A，B二集合的笛卡爾積，記作A×B，即

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

}

相當(dāng)于集合的乘法運(yùn)算。例1：設(shè)

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笛卡爾乘積的性質(zhì)：定理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，反證法，假設(shè)┐(A=∨B=∨A=B),

即A≠∧B≠

∧A≠

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

或x∈B且xA，不妨假設(shè)前者成立。因?yàn)锽≠

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

因?yàn)锳×B=B×A，所以<x,

y>∈B×A，

則x∈B,y∈A,矛盾。結(jié)論成立。充分性：若A=或B=，則A×B=B×A=

。

若A=B，則A×B=A×A=B×A，結(jié)論成立。④A×(B∩C)=(A×B)∩(A×C)證明：對(duì)于任意有序?qū)?lt;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二元關(guān)系及其矩陣表示定義4.3.1R

為關(guān)系:

=

(z)(z∈R→(x)(y)(z=<x，y>))。關(guān)系是一個(gè)由有序?qū)ψ鳛槌蓡T構(gòu)成的集合。如果<x,y>∈R,記作:

x

R

y。例如：關(guān)系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中的關(guān)系；若x∈A，y∈B，并且有

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

}則稱R為A×B

中的關(guān)系。關(guān)系是笛卡爾積的子集。例2：整數(shù)集Z中的平方關(guān)系：R

Z×ZR={<1,1>,<2,4>,<3,9>……}={<x,y>|y=x2,x,y∈Z}任意x，存在一個(gè)y，使y=x2一些y,不存在x使y=x2例3：整數(shù)集Z中的平方根關(guān)系：RZ×ZR={<1,1>,<4,2>,<9,3>……}={<x,y>|y=x1/2,x,y∈Z}任意y，存在一個(gè)x，使y=x1/2一些x,不存在y使y=x1/2例1：整數(shù)集Z中的大于關(guān)系R:R

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

y∈Z}任何x，能找到一個(gè)y，使x>y；任何y，能找到一個(gè)x，使x>y；關(guān)系與笛卡爾乘積已知關(guān)系：所有序偶的第一個(gè)元素組成集合A，所有序偶的第二個(gè)元素組成集合B，則二元關(guān)系R就是從集合A到集合B的一個(gè)關(guān)系，是A×B的一個(gè)子集。已知集合：已知兩個(gè)集合A和B(或一個(gè)集合A)，通過選取A×B(或A×A)的不同子集產(chǎn)生A

到B(或A到A)的不同關(guān)系。定義4.3.2R

為三元關(guān)系:

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

類似地,將R區(qū)分為A中三元關(guān)系和A×B×C中的三元關(guān)系，以及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①是一個(gè)關(guān)系；②R

為關(guān)系且SR

S

為關(guān)系；③R，S

為關(guān)系

R∪S，R∩S

及R-S

為關(guān)系。關(guān)系是集合，因此可以進(jìn)行集合的交、并、差的運(yùn)算。給出關(guān)系R的定義域、值域和域的定義：

定義4.3.4關(guān)系R的定義域定義為

dm(R)：={x|(y)(xRy)}。定義4.3.5關(guān)系R的值域定義為

rn(R)：={y

|(x)(xRy)}定義4.3.6關(guān)系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}},因此{(lán){x},{x,y}}∈R。根據(jù)定理3.4.1,z∈∪R(B)(B∈R

z

∈B)

可知，｛x｝∈∪R，再次根據(jù)定理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))

根據(jù)集合相等的定義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)

即對(duì)任意元x,有x∈(dm(R)-dm(S))

x∈dm(R-S)

根據(jù)子集定義3.2.2知,dm(R)-dm(S)

dm(R∪S)。全域關(guān)系:對(duì)于集合AEA=AA={<x,y>|x∈A

∧y∈A}特殊關(guān)系：恒等關(guān)系:對(duì)于集合AIA={<x,x>|x∈A}逆關(guān)系：定義4.3.7：給定任意兩個(gè)集合X

和Y，如果

R

是一個(gè)從X

到Y(jié)

的關(guān)系,則從Y

到X的關(guān)系叫逆關(guān)系：

R-1:={<y，x

>|xRy

}例2:設(shè)X={1,2,3},Y={a,b,c},

R={<1,a>,<2,b>,<3,c>}是從X到Y(jié)的關(guān)系，則R的逆關(guān)系:

R-1：={<a,1>,<b,2>,<c,3>}。定理4.3.4逆關(guān)系的性質(zhì)①R-1是一個(gè)關(guān)系；②(R-1)-1=R；

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

④(R-S)-1=R-1-S-1；③證明：對(duì)任意元x,y,

x(R∩S)-1y

y(R∩S)xyRx

∧ySxxR-1y∧xS-1yx(R-1∩S-1)y④證明：對(duì)任意元x,y,

x(R-S)-1y

y(R-S)xyRx

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

xS-1y)x(R-1-S-1)y關(guān)系復(fù)合：定義4.3.8若R,

S是關(guān)系,

則R

和S

的關(guān)系復(fù)合定義為

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

∧zSy

)}

當(dāng)R=S時(shí)，記為R*R=R2。例4.3.2令R={<1，3>，<2，3>}，

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

S*R={<3，3>}。注意：復(fù)合運(yùn)算不可交換。定理4.3.5關(guān)系復(fù)合運(yùn)算性質(zhì)：①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)證明：設(shè)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證明：對(duì)任意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)證明：對(duì)任意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關(guān)系的冪運(yùn)算關(guān)系的復(fù)合運(yùn)算是可結(jié)合的。當(dāng)R=S時(shí)，記為R*R=R2。

Rn+1=Rn*R=R*Rn現(xiàn)在考慮一種定義域與已知集合的關(guān)系以及有關(guān)定理。定義4.3.9R|ˋC:=R∩(C×rn(R))

本定義也可表為：

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

}

即：R|ˋC也是一個(gè)關(guān)系，其定義域?yàn)镃，第一分量的取值范圍為C。下面定義在關(guān)系R下集合C的映像，記為R[C]以及討論相關(guān)定理。定義4.3.10R[C]:=rn(R|ˋC)

本定義也可表為：

R[C]={y

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

可見R[C]是關(guān)系R的值域，且關(guān)系R的定義域?yàn)镃

。證明：③令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

根據(jù)定義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]]

根據(jù)定義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]]關(guān)系矩陣表示法

設(shè)兩個(gè)有限集合A={x1,x2,…,xm}，B={y1,y2,…,yn}，二元關(guān)系R

A×B。則對(duì)應(yīng)于二元關(guān)系R有一個(gè)關(guān)系矩陣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的關(guān)系矩陣關(guān)系運(yùn)算(并,交,補(bǔ),差,逆,復(fù)合)的矩陣表示

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

MT=(cij)n×p，dij

表示運(yùn)算后所得新關(guān)系之關(guān)系矩陣的元素，則①M(fèi)R∪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關(guān)系圖一個(gè)有限集合A上的關(guān)系R,可以用一個(gè)稱作有向圖的圖形直觀表示,這種表示關(guān)系的有向圖叫關(guān)系圖。其畫法如下:(1)集合A中的每一個(gè)元素a用帶有元素符號(hào)的圓圈（稱作結(jié)點(diǎn)a）表示。

(2)若a,b∈A,且aRb,則將結(jié)點(diǎn)a和結(jié)點(diǎn)b用一條帶有箭頭的直線或弧線連接起來,其方向由結(jié)點(diǎn)a

指向結(jié)點(diǎn)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關(guān)系的性質(zhì)定義4.4.1R在A中自反:=(x)(x∈A→xRx)即對(duì)任意的x∈A都有<x,

x>

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

即對(duì)任意的x∈A都有<x,

x>

R約定：x,y,z∈A

表示x∈A∧y∈A∧z∈A；R,S,T都是表示A上關(guān)系。給出六個(gè)基本定義。例4.4.1：X={1,2,3}上的等于關(guān)系R，即

R={<1,1>,<2,2>,<3,3>}是自反的；以下關(guān)系都具有自反性：命題公式的等價(jià)關(guān)系

A≡A；集合的相等關(guān)系A(chǔ)=A；集合的包含關(guān)系A(chǔ)A；整數(shù)的大于等于關(guān)系x≥y；MR=例4.4.2：X={1,2,3}上的大于關(guān)系，即：

R={<2,1>,<3,1>,<3,2>}是非自反的。以下關(guān)系具有非自反性：集合的真包含關(guān)系；整數(shù)的大于關(guān)系；家族的父子關(guān)系；MR=定義4.4.3R在A中對(duì)稱:=(x)(y)(x，y∈A∧xRy

→yRx)對(duì)任意x，y∈A,若<x,

y>∈R則有<y,

x>

∈R

定義4.4.4R在A中非對(duì)稱:=(x)(y)(x，y∈A∧xRy→┐(yRx))

對(duì)任意x，y∈A,

若<x,

y>∈R則有<y,

x>

R

即：

R

對(duì)稱

R-1=R即：R

非對(duì)稱R∩R-1=例4.4.3：X={1,2,3}上的不等關(guān)系，即：

R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>}是對(duì)稱的。以下關(guān)系具有對(duì)稱性：同學(xué)關(guān)系；朋友關(guān)系；命題公式的等價(jià)關(guān)系；MR=例4.4.4：X={1,2,3}上的大于關(guān)系，即：

R={<2,1>,<3,1>,<3,2>}是非對(duì)稱的。以下關(guān)系具有非對(duì)稱性：集合的真包含關(guān)系；自然數(shù)的大于關(guān)系。MR=定義4.4.5R在A中反對(duì)稱:=(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}上的大于等于關(guān)系，即：

R={<1,1>,<2,1>,<2,2>,<3,1>,<3,2>,<3,3>}是反對(duì)稱的。以下關(guān)系具有反對(duì)稱性：集合的包含關(guān)系；自然數(shù)的大于等于關(guān)系；命題的蘊(yùn)含關(guān)系。MR=定義4.4.7：定義4.4.8IA：={<x，x>|x∈A

}給出一個(gè)集合A上的恒等關(guān)系，記為IA.定理4.4.1恒等關(guān)系的性質(zhì)：①xIAxx∈A②IA

*IA

=IA③R為關(guān)系Idm(R)*R=R②證明：對(duì)于任意x,y,則

xIA*IA

y(z)(xIAz∧

zIAy)xIAx∧

xIAyT

∧

xIAy

xIAy根據(jù)定義3.2.1知，IA

*IA

=IA.定理4.4.2(本定理也常被用來作為定義)

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

③R對(duì)稱

R-1=R④R非對(duì)稱R∩R-1=⑤R反對(duì)稱R∩R-1Idm(R)

⑥R傳遞R*RR①

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

Ifl(R)x，又因?yàn)镮fl(R)R，所以xRx，所以R為自反的。證明：必要性：若R為自反的，

對(duì)任意x有x

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

又因?yàn)镽為自反的，所以xRx.

可得Ifl(R)R。

③

R對(duì)稱

R-1=R

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

若xRy，則yR-1x

。因?yàn)镽-1=R

，所以yR

x

，所以R為對(duì)稱的。證明：必要性：若R對(duì)稱的，對(duì)任意x，y

∈fl(R),

若

x

R-1y，則y

Rx，由對(duì)稱定義可得xRy，所以R-1R

；反之，若

x

Ry，由于R是對(duì)稱的，則y

Rx，從而x

R-1y，所以R

R-1

。綜上，可得R-1

=R

。證明：必要性：若R傳遞的，對(duì)任意x，y∈fl(R),

若

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

使得xRz

并且

zRy，又因?yàn)镽是傳遞的，所以xRy

?？傻肦*RR。⑥R傳遞R*RR充分性：若R*RR，對(duì)任意x，y，z∈fl(R),

若xR

z,zRy，則xR*Ry。又因?yàn)镽*RR，所以xRy。所以R為傳遞的。定理4.4.7設(shè)R1、R2是A上的自反關(guān)系，則R-11、R1∩R2、R1∪R2、R1*R2

也是A上的自反關(guān)系。定理4.4.8設(shè)R1、R2是A上的非自反關(guān)系，則

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

是A上的非自反關(guān)系。定理4.4.9設(shè)R1、R2是A上的對(duì)稱關(guān)系，則

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

也是A上的對(duì)稱關(guān)系。定理4.4.11設(shè)R1、R2是A上的傳遞關(guān)系，則R-11、R1∩R2

是A上的傳遞關(guān)系。

但R1∪R2不一定是傳遞的。定理4.4.10設(shè)R1、R2是A上的反對(duì)稱關(guān)系，則R-11、R1∩R2、R1-R2是A上的反對(duì)稱關(guān)系。但R1∪R2不一定是反對(duì)稱的?！纠緼={a,b,c},討論在下列各種情況下R*S

具有的性質(zhì)。

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

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

R、S是反對(duì)稱的。(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是對(duì)稱的。R*S={〈a,a〉,〈a,c〉,〈b,a〉}，所以R*S不是傳遞的。4.5等價(jià)關(guān)系與劃分定義4.5.1R為等價(jià)關(guān)系:=R為關(guān)系且R具有自反的、對(duì)稱的和傳遞的性質(zhì)。定義4.5.2R為A上等價(jià)關(guān)系:=R為等價(jià)關(guān)系且A=fl(R)。若關(guān)系R在集合A中是自反的、對(duì)稱的和傳遞的，則稱R為A上的等價(jià)關(guān)系。常見的等價(jià)關(guān)系的例子：自然數(shù)相等關(guān)系；直線的平行關(guān)系；集合的相等關(guān)系；命題的等價(jià)關(guān)系；其意義在于證實(shí)了應(yīng)用抽象的一般原理的正確性，即在某方面等價(jià)的個(gè)體產(chǎn)生等價(jià)類，對(duì)全體等價(jià)類進(jìn)行分析常常比對(duì)全體本身進(jìn)行分析更簡單。例4.5.1：設(shè)I為整數(shù)集合，R={<x,y>|x≡y(mod

k)，x,y∈I

},證明R是等價(jià)關(guān)系。x

≡

y(mod

k)表示x,y模k同余。證明：設(shè)任意a,b,c∈I,要證R是自反，對(duì)稱和傳遞的。即x/k

與y/k所得到的余數(shù)是相同的,x=kt1+r1,y=kt2+r2,余數(shù)r1=r2?？梢孕问交硎緸閤-y=kt(t為整數(shù))。即x≡y(mod

k)

x-y=kt

(1)自反性：因?yàn)閍-a=k*0,所以<a,a>∈R，即R具有自反性；(2)對(duì)稱性：若<a,b>∈R,即a≡b(mod

k),也即a-b=kt(t為整數(shù))，則b-a=-kt,所以b≡a(mod

k)，即<b,a>∈R，即R具有對(duì)稱性；(3)傳遞性：若<a,b>∈R,<b,c>∈R,即a≡b(mod

k),b≡c(mod

k)，則有a-b=kt,b-c=ks(t,s為整數(shù))，故a-c=a-b+b-c=k(t+s),

所以a≡c(mod

k),即<a,c>∈R，即R具有傳遞性。例4.5.2：設(shè)A={1，2，3，4}，在冪集P(A)上規(guī)定二元關(guān)系如下：R={<s,t>|s,t∈P(A)(|s|=|t|)},其中|s|表示集合s中的元素的個(gè)數(shù)。證明R是P(A)上的等價(jià)關(guān)系。證明：設(shè)任意s,t,r∈P(A),要證R是自反，對(duì)稱和傳遞的。①自反性：因?yàn)閨s|=|s|,所以<s,s>∈R，即R具有自反性；②對(duì)稱性：若<s,t>∈R,即|s|=|t|,也即|t|=|s|,所以<t,s>∈R，

即R具有對(duì)稱性；③傳遞性：若<s,t>∈R,<t,r>∈R,即|s|=|t|,|t|=|r|,則有|s|=|r|,所以<s,r>∈R，即R具有傳遞性。綜上,

R

是P(A)上的等價(jià)關(guān)系。

等價(jià)類

定義4.5.3設(shè)R是集合A上的等價(jià)關(guān)系，由A中元素x產(chǎn)生R的等價(jià)類，記為[x]R，它是由A中那些使xRy

成立的所有y∈A

組成的子集，形式地表為

[x]R

:={y

|xRy

}并且稱x是等價(jià)類[x]R的一個(gè)代表。等價(jià)類[x]R

有時(shí)也記作x/R。定理4.5.2y∈[x]R

xRy。解：已經(jīng)證明了R是I上的等價(jià)關(guān)系，則由I的元素所產(chǎn)生的等價(jià)類是：

[0]R={…,

-6,

-3,

0,

3,

6,

…}[1]R={…,

-5,

-2,

1,

4,

7,

…}[2]R={…,

-4,

-1,

2,

5,

8,

…}例4.5.3：設(shè)I為整數(shù)集合，R是模3同余的關(guān)系，

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

},

確定由I的元素所產(chǎn)生的等價(jià)類。在集合I上模3同余等價(jià)關(guān)系R所構(gòu)成的等價(jià)類有：

[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：設(shè)A={1，2，3，4}，在冪集P(A)上規(guī)定二元關(guān)系如下：R={<s,t>|s,t∈P(A)(|s|=|t|)},其中|s|表示集合s中的元素的個(gè)數(shù)。求R的等價(jià)類。證明：

已經(jīng)證明R是P(A)上的等價(jià)關(guān)系。

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的等價(jià)類為:[]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為等價(jià)關(guān)系，則[x]R=[y]RxRy②R為等價(jià)關(guān)系[x]R=[y]R

∨

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

。對(duì)任意z∈[x]R

,根據(jù)等價(jià)類定義可得xRz，因?yàn)镽是等價(jià)關(guān)系，R是對(duì)稱的，所以zRx，又因?yàn)閤Ry，

R是傳遞的，所以zRy，即yRz，故z∈[y]R

。因此[x]R

[y]R

。同理可證[y]R

[x]R

。因此，[x]R

=[y]R

。必要性：由等價(jià)類定義可知，y∈[y]R,又已知[x]R=[y]R，則y∈[x]R,由定理4.5.2可得xRy。②R為等價(jià)關(guān)系[x]R=[y]R∨[x]R∩[y]R=。證明：對(duì)任意x,y，若x,y不屬于fl(R)，則[x]R=

，[y]R=

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

令x,y∈fl(R)，若xRy，則[x]R=[y]R成立。若┐(xRy)，假設(shè)[x]R∩[y]R

=不成立。設(shè)z∈[x]R∩[y]R，即xRz，yRz

。因?yàn)镽是等價(jià)關(guān)系，則R是對(duì)稱的、傳遞的。由xRz，zRy，可得xRy，產(chǎn)生矛盾！所以[x]R∩[y]R=。結(jié)論成立。劃分

一個(gè)集合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″更細(xì)。為了建立等價(jià)類與劃分的密切關(guān)系，現(xiàn)給出由A上等價(jià)關(guān)系R產(chǎn)生的等價(jià)類集合的定義：定義4.5.6

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

∧R為A上等價(jià)關(guān)系}類似地，定義等價(jià)關(guān)系R產(chǎn)生的等價(jià)類集合：

π(R):={[x]R

|x∈f

l(R)∧R為等價(jià)關(guān)系}證明：②πA(R):={[x]R|x∈A

∧R為A上等價(jià)關(guān)系}定理4.5.5①[x]R∈πA(R)x∈A∧R為A上等價(jià)關(guān)系。②πA(R)是A的一種劃分。因?yàn)镽是A上的等價(jià)關(guān)系，所以對(duì)任意x∈A，有xRx，即x∈[x]R

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

A，所以∪πA(R)A，即A=∪πA(R)。又因?yàn)閷?duì)任意[x]R,都有x∈[x]R,所以x∈[x]R

≠

。由定理4.5.3可知，對(duì)任意[x]R，[y]R,都有

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

根據(jù)劃分的定義可得，πA(R)是A的一種劃分。

常常把由等價(jià)關(guān)系R產(chǎn)生集合A的劃分，記為A/R，讀作A模R，稱為A對(duì)R的商集。例4.5.3等價(jià)關(guān)系R={<x,y>|x≡y(mod3)，x,y∈I

}的商集為：

I/R={[0]R,[1]R,[2]R}例4.5.4A={1,2,3,4},等價(jià)關(guān)系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函數(shù)函數(shù)概念是最基本的數(shù)學(xué)概念之一，也是最重要的數(shù)學(xué)工具。初中數(shù)學(xué)中函數(shù)定義為“對(duì)自變量每一確定值都有一確定的值與之對(duì)應(yīng)”的因變量；高中數(shù)學(xué)中函數(shù)又被定義為兩集合元素之間的映射。用一個(gè)特殊關(guān)系具體規(guī)定這一映射，稱這個(gè)特殊關(guān)系為函數(shù)，因?yàn)殛P(guān)系是一個(gè)集合，從而又將函數(shù)作為集合來研究。定義4.6.1f為函數(shù)：=f為關(guān)系∧(x)(y)(z)(xfy∧xfz→y

=z)

對(duì)于函數(shù)符號(hào)不僅使用xfy，也常常使用f(x)=y。有時(shí)為了表示出函數(shù)的定義域A和值域B，也記為f：A→B。

（1）從X

到Y(jié)

的函數(shù)的定義域是X，不能是X的某個(gè)真子集。（2）若<x,y>∈f，<x,y′>∈f，則y＝y(tǒng)′（單值性）。一個(gè)函數(shù)是一個(gè)多對(duì)一的關(guān)系，即對(duì)該關(guān)系的定義域中的任何元恰恰只對(duì)應(yīng)于值域中的一個(gè)元，定義域中的不同元可以對(duì)應(yīng)于值域中同一元，其形式定義是：例1

設(shè)A={a,b},B={1,2,3}，判斷下列集合是否是A到B的函數(shù)。解：

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

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

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

F4={〈a,3〉}是是否否定義4.6.2設(shè)f:A→B，g:C→D，如果A=C，B＝D，且對(duì)所有x∈A，有f(x)＝g(x)，稱函數(shù)f等于g,記為f=g。如果AC，B＝D，且對(duì)每一個(gè)x∈A，有f(x)＝g(x)，稱函數(shù)f包含于g，記為fg。當(dāng)不強(qiáng)調(diào)函數(shù)是定義在哪個(gè)集合上的時(shí)候，由于函數(shù)是序偶的集合（特殊的關(guān)系），所以f=g的充分必要條件是fg

且gf。函數(shù)的復(fù)合運(yùn)算定義4.6.2f○g=g*f

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

(1)f，g為函數(shù)且rn(g)dm(f)

f○g也為函數(shù)且

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

(2)(f○g)|ˋC

=

f○(g|ˋC)現(xiàn)在定義1-1函數(shù)和反函數(shù)的概念

定義4.6.3f為1-1函數(shù):=

f和f

-1皆為函數(shù)。定義4.6.4若f為1-1函數(shù)，則稱f

-1為反函數(shù)。定理4.6.2若f為1-1函數(shù)且x1，x2∈dm(f)，則

f

(x1)

=

f

(x2)

x1=x2。①若f為1-1函數(shù)，則f

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

為1-1函數(shù)，則f

-1(y)=x

f(x)=y；②f

為1-1函數(shù)∧x∈dm(f)f

-1(f(x))=x；③f，g為1-1函數(shù)f∩g為1-1函數(shù)。證明：必要性：若f-1(y)=x，則<y,x>∈f-1，于是<x,y>∈f,

因?yàn)閒為1-1函數(shù)，因此，f(x)=y。充分性：若f(x)=y，則<x,y>∈f,于是<y,x>∈f

-1，因?yàn)閒為1-1函數(shù)，所以f

-1為函數(shù)，因此f

-1(y)=x.定義4.6.5

①f為從A到B的函數(shù):=f為函數(shù)∧dm(f)=A∧rn(f)B

②f為從A到B中的函數(shù):=f為函數(shù)∧dm(f)=A∧rn(f)B

③f為從A到B上的函數(shù)或f為滿射:=

f為函數(shù)∧dm(f

)=A∧rn(f

)=B④f為單射或f為一對(duì)一映射（單射）:=

f為函數(shù)∧(x)(y)(x,y∈A∧x≠y→f(x)≠f(y))

⑤f為雙射或f為一一對(duì)應(yīng):=

f既為單射又為滿射或f為1-1函數(shù)。⑥實(shí)數(shù)x的底函數(shù)，記為x，指小于或等于x的最大整數(shù)。

實(shí)數(shù)x的頂函數(shù)，記為x，指大于或等于x的最小整數(shù)。⑦散列函數(shù)h:K→D，h(k)=d，其中K為關(guān)鍵碼集，D為地址集合。常用散列函數(shù)是用除法求余，中平方方法和折迭方法得到。⑧恒等函數(shù)，設(shè)AB，若idA：A→B，使idA(x)=x，則稱idA為A上的一個(gè)恒等函數(shù)。恒等函數(shù)是單射函數(shù)，而且僅當(dāng)A=B時(shí)恒等函數(shù)才是滿射，并且idA=IA。⑨特征函數(shù)，設(shè)AB，函數(shù)fA：B→{0，1}定義為則稱fA：B→{0，1}是集合A的一個(gè)特征函數(shù)。【例】設(shè)A={a,b},B={1,2,3}。由A→B能生成多少個(gè)不同的函數(shù)？

由B→A能生成多少個(gè)不同的函數(shù)？解：設(shè)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〉}定理設(shè)|A|=m，|B|=