離散數(shù)學(xué)第四章2

第四章

二元關(guān)系和函數(shù)(2/3)4.2關(guān)系的運(yùn)算

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

(1)R中所有的有序?qū)Φ牡谝辉貥?gòu)成的集合稱為R的定義域，記為domR.形式化表示為domR={x|

y(<x,y>∈R)}

(2)R中所有有序?qū)Φ牡诙貥?gòu)成的集合稱為R的值域，記作ranR.形式化表示為ranR={y|

x(<x,y>∈R)}

(3)R的定義域和值域的并集稱為R的域，記作fldR.形式化表示為fldR=domR∪ranR

關(guān)系的基本運(yùn)算例4.2.1設(shè)R={<1,2>,<1,3>,<2,4>,<4,3>}，則

domR={1,2,4}

ranR={2,3,4}

fldR={1,2,3,4}

定義4.2.3設(shè)F,G為二元關(guān)系，G對F的(左)復(fù)合記作F

G，其中

F

G={<x,y>|

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

定義4.2.2設(shè)R為二元關(guān)系，R的逆關(guān)系，簡稱R的逆，記作R-1,其中R-1={<x,y>|<y,x>∈R}

定義4.2.4設(shè)R為二元關(guān)系，A是集合

(1)R在A上的限制記作R

A，其中

R

A={<x,y>|xRy∧x∈A}

(2)A在R下的象記作R[A]，其中

R[A]=ran(R

A)

例4.2.2設(shè)F={<3,3>,<6,2>},G={<2,3>}，則

F-1={<3,3>,<2,6>}

F

G={<6,3>}

G

F={<2,3>}

例4.2.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}

例4.2.4設(shè)F={<a,{a}>,<{a},{a,{a}}>}，求FF,F{a},F[{a}].

解:FF={<{a},{a,{a}}>}F{a}={<a,{a}>}F[{a}]={{a}}

定理4.2.1設(shè)F是任意的關(guān)系，則

(1)(F-1)-1=F

(2)domF-1=ranF，ranF-1=domF

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

定理4.2.2設(shè)F，G，H是任意的關(guān)系，則

(1)(F

G)

H=F

(G

H)

(2)(F

G)-1=G-1F-1

證:(1)任取<x,y>,<x,y>∈(F

G)

H

所以(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)定理4.2.3設(shè)R為A上的關(guān)系，則

R

IA=IA

R=R

定理4.2.4設(shè)F，G，H是任意關(guān)系，則

(1)F

(G∪H)=F

G∪F

H

(2)(G∪H)

F=G

F∪H

F

(3)F

(G∩H)

F

G∩F

H

(4)(G∩H)

F

G

F∩H

F

定理4.2.5.5設(shè)F為關(guān)系，A，B為集合，則

(1)F

(A∪B)=F

A∪F

B

(2)F[A∪B]=F[A]∪F[B]

(3)F

(A∩B)

F

A∩F

B

(4)F[A∩B]

F[A]∩F[B]

關(guān)系冪定義4.2.5設(shè)R為A上的關(guān)系，n為自然數(shù)，則R的n次冪定義為：

（1）R0={<x,x>|x∈A}=IA

（2）Rn+1=Rn

R

怎樣計(jì)算Rn

呢？如果R是用集合表達(dá)式給出的，可以通過n-1次右復(fù)合計(jì)算得到Rn.如果R是用關(guān)系矩陣M給出的，則Rn

的關(guān)系矩陣是Mn，即n個(gè)矩陣M之積.與普通矩陣乘法不同的是，其中的相加是邏輯加，即

1+1=1,1+0=0+1=1,0+0=0

如果R是用關(guān)系圖G給出的，可以直接由圖G得到Rn

的關(guān)系圖G'.G'的頂點(diǎn)集與G相同.考察G的每個(gè)頂點(diǎn)xi，如果在G中從xi

出發(fā)經(jīng)過n步長的路徑到達(dá)頂點(diǎn)xj，則在G'中加一條從xi

到xj

的邊.當(dāng)把所有這樣的便都找到以后，就得到圖G'.

例4.2.5設(shè)A={a,b,c,d}

R={<a,b>,<b,a>,<b,c>,<c,d>}，求R的各次冪，分別用矩陣和關(guān)系圖表示.解:用關(guān)系圖的方法得到關(guān)系圖如下:R0，即IA的關(guān)系矩陣是

M=

則R的關(guān)系矩陣分

M0=

則R2，R3，R4的關(guān)系矩陣分別是

M2=

=

M3=M2M=

=

M4=M3M=

=

因此M4=M2，即R4=R2.因此可以得到

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

定理4.2.6設(shè)A為n元集，R是A上的關(guān)系，則存在自然數(shù)s和t,使得Rs=Rt.

證:R為A上的關(guān)系，對任何自然數(shù)k，Rk都是A×A的子集.又知|A×A|=n2，|P(A×A)|=

，即A×A的不同子集僅

個(gè).當(dāng)列出R的各次冪R0，R1，R2，…，

，…，必存在自然數(shù)s和t使得Rs=Rt.

該定理說明有窮集上只有有窮多個(gè)不同的二元關(guān)系.當(dāng)t足夠大時(shí)Rt必與某個(gè)Rs(s<t)相等.如例4.2.5中的R4=R2.

定理4.2.7設(shè)R是A上的關(guān)系，m,n∈N，則

(1)Rm

Rn=Rm+n

(2)(Rm)n=Rmn

4.3關(guān)系的性質(zhì)一．關(guān)系的五種基本性質(zhì)

定義4.3.1設(shè)R為A上的關(guān)系，

（1）若

x(x∈A→<x,x>∈R)，則稱R在A上是自反的.

（2）若

x(x∈A→<x,x>

R)，則稱R在A上是反自反的.

例4.3.1設(shè)A={1,2,3}，R1，R2，R3是A上的關(guān)系，其中

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

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

R3＝{<1,3>}

說明R1，R2和R3是否為A上的自反關(guān)系和反自反關(guān)系.

R2是自反的R3是反自反的R1兩者都不是定義4.3.2設(shè)R為A上的關(guān)系，

若

x

y(x,y∈A∧<x,y>∈R→<y,x>∈R),則稱R為A上對稱的關(guān)系.

若

x

y(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y)，則稱R為A上的反對稱關(guān)系.

例4.3.2設(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是否為A上對稱和反對稱的關(guān)系.

R1既是對稱也是反對稱的.R2是對稱的但不是反對稱的.R3是反對稱的但不是對稱的.R4既不是對稱的也不是反對稱的注:A上的全域關(guān)系EA，恒等關(guān)系IA和空關(guān)系

都是A上的對稱關(guān)系.恒等關(guān)系IA和空關(guān)系也是A上的反對稱關(guān)系.但全域關(guān)系EA一般不是A上的反對稱關(guān)系，除非A為單元集或空集.定義4.3.3設(shè)R為A上的關(guān)系，若

x

y

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

則稱R是A上的傳遞關(guān)系.

例4.3.3設(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，R2和R3是否為A上的傳遞關(guān)系.

R1和R3是A上的傳遞關(guān)系，R2不是A上的傳遞關(guān)系注:A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系

都是A上的傳遞關(guān)系.小于等于關(guān)系，整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的傳遞關(guān)系.小于關(guān)系和真包含關(guān)系仍舊是相應(yīng)集合上的傳遞關(guān)系

如果頂點(diǎn)xi到xj有邊，xj到xk有邊，則從xi到xk也有邊如果兩點(diǎn)之間有邊，一定是一條有向邊(無雙向邊)如果兩個(gè)頂點(diǎn)之間有邊，一定是一對方向相反的邊(無單邊)每個(gè)頂點(diǎn)都沒有環(huán)每個(gè)頂點(diǎn)都有環(huán)關(guān)系圖對M2中1所在位置，M中相應(yīng)的位置都是1若rij＝1，且i≠j，則rji＝0矩陣是對稱矩陣主對角線元素全是0主對角線元素全是1關(guān)系矩陣RR

RR∩R-1

IA

R=R-1

R∩IA=

IA

R集合表達(dá)式傳遞性反對稱性對稱性反自反性自反性關(guān)系性質(zhì)的等價(jià)描述

1）該關(guān)系是對稱的，因?yàn)闊o單向邊.它不是自反的也不是反自反的.因?yàn)橛械捻旤c(diǎn)有環(huán)，有的頂點(diǎn)無環(huán).它不是反對稱的，因?yàn)閳D中有雙向邊.它也不是傳遞的，因?yàn)閳D中有邊<3,1>和<1,3>，但沒有從3到3的邊，即通過3的環(huán).例4.3.4判斷圖中關(guān)系的性質(zhì)，并說明理由.

（2）該關(guān)系是反自反的但不是自反的，因?yàn)槊總€(gè)頂點(diǎn)都沒有環(huán).它是反對稱的但不是對稱的，因?yàn)閳D中只有單向邊.它也是傳遞的，因?yàn)椴淮嬖陧旤c(diǎn)x,y,z，使得x到y(tǒng)有邊，y到z有邊，但x到z沒有邊，其中x,y,z∈{1,2,3}.3）該關(guān)系是自反的但不是反自反的，因?yàn)槊總€(gè)頂點(diǎn)都有環(huán).它是反對稱的但不是對稱的，因?yàn)閳D中只有單向邊.但他不是傳遞的，因?yàn)?到1有邊，1到3有邊，但2到3沒有邊.關(guān)系的性質(zhì)和運(yùn)算之間的聯(lián)系

例4.3.5設(shè)A是集合，R1和R2是A上的關(guān)系，證明：（1）若R1，R2是自反的和對稱的，則R1∪R2也是自反的和對稱的.

（2）若R1和R2是傳遞的，則R1∩R2也是傳遞的.

證:（1）由于R1和R2是A上的自反關(guān)系，故有

IA

R1和IA

R2

從而得到IA

R1∪R2..于是R1∪R2在A上是自反的.

再由R1和R2的對稱性有

R1=R1-1和R2=R2-1

于是(R1∪R2)-1=R1-1∪R2-1=R1∪R2

從而證明了R1∪R2也是A上對稱的關(guān)系.（2）由R1和R2的傳遞性有

R1

R1

R1和R2

R2

R2

而

(R1∩R2)

(R1∩R2)

R1

R1∩R1

R2∩R2

R1∩R2

R2

(R1∩R2)∩R1

R2∩R2

R1

R1∩R2

從而證明了R1∩R2也是A上的傳遞關(guān)系.

一般起:自反性反自反性對稱性反對稱性傳遞性R1-1

√√√√√R1∩R2

√√√√√R1∪R2

√√√××R1-R2

×√√√×R1

R2

√××××4.4關(guān)系的閉包關(guān)系閉包定義定義7.14設(shè)R是非空集合A上的關(guān)系，R的自反（對稱或傳遞）閉包是A上的關(guān)系R'，使得R'

滿足以下條件：

（1）R'是自反的（對稱的或傳遞的）（2）R

R'

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

R''.

一般將R的自反閉包記作r(R)，對稱閉包s(R)，傳遞閉包記作t(R).

定理4.4.1設(shè)R為A上的關(guān)系，則有

（1）r(R)=R∪R0

（2）s(R)=R∪R-1

（3）t(R)=R∪R2∪R3∪…

關(guān)系閉包的求法關(guān)系矩陣和關(guān)系圖求閉包的方法:

設(shè)關(guān)系R，r(R)，s(R)，t(R)的關(guān)系矩陣分別為M，Mr，Ms和Mt，則Mr=M+E

Ms=M+M'

Mt=M+M2+M3+…

其中E是和M同階的單位矩陣，M'是M的轉(zhuǎn)置矩陣.注意在上述等式中矩陣的元素相加時(shí)使用邏輯加.

設(shè)關(guān)系R，r(R)，s(R)，t(R)的關(guān)系圖分別記為G，Gr，Gs，Gt，則Gr，Gs，Gt的頂點(diǎn)集與G的頂點(diǎn)集相等.除了G的邊以外，以下述方法添加新的邊.

考察G的每個(gè)頂點(diǎn)，如果沒有環(huán)就加上一個(gè)環(huán).最終得到的是Gr

.

考察G的每一條邊，如果有一條xi到xj的單向邊，i≠j，則在G中加一條邊xj到xi的反方向邊.最終得到Gs.

考察G的每個(gè)頂點(diǎn)xi，找除從xi出發(fā)的所有2步，3步，…，n步長的路徑（n為G中的頂點(diǎn)數(shù)）,檢查完所有的頂點(diǎn)后就得到圖Gt

.

例4.4.1設(shè)A={a,b,c,d}，R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}，求r(R)，s(R)，t(R)以及它們的關(guān)系圖和矩陣.解:r(R)={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>,<a,a>,<b,b>,<c,c>,<d,d>}s(R)={<a,b>,<b,a>,<b,c>,<c,b>,<c,d>,<d,c>,<d,b>,<b,d>}t(R)=R∪R2∪R3={<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c>,<b,d>,<c,d>}4.5等價(jià)關(guān)系和偏序關(guān)系

一．等價(jià)關(guān)系定義4.5.1設(shè)R為非空集合上的關(guān)系.如果R是自反的、對稱的和傳遞的，則稱R為A上的等價(jià)關(guān)系.設(shè)R是一個(gè)等價(jià)關(guān)系，若<x，y>∈R，稱x等價(jià)于y，記做x~y.例4.5.1設(shè)A={1,2,…,8}，如下定義A上的關(guān)系R：R={<x，y>|x，y∈A∧x≡y(mod3)}

其中x≡y(mod3)叫做x與y模3相等，即x除以3的余數(shù)與y除以3的余數(shù)相等.R為A上的等價(jià)關(guān)系，因?yàn)閤∈A，有x≡x(mod3)

x，y∈A,若x≡y(mod3)，則有y≡x(mod3)

x，y，z∈A，若x≡y(mod

3)，y≡z(mod3)，則有x≡z(mod3)

[1]=[4]=[7]={1,4,7}

[2]=[5]=[8]={2,5,8}

[3]=[6]={3,6}

等價(jià)類等價(jià)類的定義定義4.5.2設(shè)R為非空集合A上的等價(jià)關(guān)系，令

x∈A

[x]R={y|y∈A∧xRy}

稱[x]R為x關(guān)于R的等價(jià)類，簡稱為x的等價(jià)類，簡記為[x]或

.

例4.5.2對于任意的整數(shù)x和y，定義模n相等關(guān)系~

x~y

iff

x≡y(modn)

~是整數(shù)集合Z上的等價(jià)關(guān)系.~將整數(shù)分成n個(gè)等價(jià)類，使用等價(jià)類的符號可記為

[i]={nz+i|z∈Z}，i=0，1，…，n-1

{[0],[1],…,[n-1]}=Z/~=Zn=Z/nZ稱為Z在模n的等價(jià)關(guān)系~下的商集定義4.5.3設(shè)R為非空集合A上的等價(jià)關(guān)系，以R的所有等價(jià)類作為元素的集合稱為A關(guān)于R的商集，記做A/R，即

A/R={[x]R|x∈A}

商集的定義

例4.5.3(1)非空集合A上的全域關(guān)系EA是A上的等價(jià)關(guān)系,對任意x∈A有[x]=A,商集A/EA={A}.(2)非空集合A上的恒等關(guān)系IA是A上的等價(jià)關(guān)系,對任意x∈A有[x]={x},商集A/IA={{x}|x∈A}.(3)整數(shù)集Z上模10的等價(jià)關(guān)系,其等價(jià)類為[i]={10k+i|k∈Z},i=0,1,…,9.商集Z10={[0],[1],…,[9]}等價(jià)類的性質(zhì)定理4.5.1設(shè)R是非空集合A上的等價(jià)關(guān)系，則

（1）

x∈A，[x]是A的非空子集.

（2）

x,y∈A，如果xRy，則[x]=[y].

（3）

x,y∈A，如果xRy，則[x]與[y]不交.

（4）∪{[x]|x∈A}=A

集合的劃分定義4.5.4設(shè)A為非空集合，若A的子集族π(π

P(A)，是A的子集構(gòu)成的集合)滿足下面的條件：

（1）

π

（2）

x

y(x，y∈π∧x≠y→x∩y=

)

（3）∪π=A

則稱π是A的一個(gè)劃分，稱π中的元素為A的劃分塊.

例4.5.4設(shè)A＝{a,b,c,d}，給定π1,π2,π3,π4,π5,π6,如下：π1={{a,b,c},1bdgyx1}

π2={{a,b},{c},ulpdxzb}

π3={{a},{a,b,c,d}}

π4={{a,b},{c}}π5={

,{a,b},{c,d}}

π6={{a,{a}},{b,c,d}}

其中哪些是A的劃分?π1和π2是A的劃分，其它都不是A的劃分商集A/R和劃分的定義相比較，易見商集就是A的一個(gè)劃分，并且不同的商集將對應(yīng)于不同的劃分.反之，任給A的一個(gè)劃分π，如下定義A上的關(guān)系R：R={<x,y>|x,y∈A∧x與y在π的同一劃分塊中}

則不難證明R為A上的等價(jià)關(guān)系，且該等價(jià)關(guān)系所確定的商集就是π.由此可見，A上的等價(jià)關(guān)系與A的劃分是一一對應(yīng)的.A上的等價(jià)關(guān)系與A的劃分的關(guān)系例4.5.5給出A＝{1,2,3}上所有的等價(jià)關(guān)系

解:先做出A的所有劃分.

這些劃分與A上的等價(jià)關(guān)系之間的一一對應(yīng)是：π1對應(yīng)于全域關(guān)系EA，π5的對應(yīng)于恒等關(guān)系IA，π2，π3和π4分別對應(yīng)于等價(jià)關(guān)系R2，R3和R4.

其中R2={<2,3>,<3,2>}∪IA

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

R4={<1,2>,<2,1>}∪IA

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

.設(shè)

為偏序關(guān)系，如果<x，y>∈

，則記作x

y，讀作“小于或等于”.集合A上的恒等關(guān)系IA和空關(guān)系

都是A上的偏序關(guān)系.小于或等于關(guān)系，整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的偏序關(guān)系.一般來說，全域關(guān)系EA不是A上的偏序關(guān)系.

偏序集例4.5.6(1)整數(shù)集合Z和數(shù)的小于或等于關(guān)系≤構(gòu)成偏序集<Z,≤>，(2)集合A的冪集P(A)和包含關(guān)系R

構(gòu)成偏序集<P(A),R

>.

定義4.5.6集合A和A上的偏序關(guān)系

一起叫做偏序集，記作<A,

>.

定義4.5.6設(shè)R為非空集合A上的偏序關(guān)系，定義

(1)

x，y∈A，x

y

x

y∧x≠y.

(2)

x，y∈A，x與y可比

x

y∨y

x.

其中x

y讀作x“小于”y.這里所說的“小于”是指在偏序中x排在y的前邊.

在具有偏序關(guān)系

的集合A中任取兩個(gè)元素x和y，可能有下述幾種情況發(fā)生：

x

y(或y

x)，x＝y(tǒng)，x與y不是可比的.

例如A＝{1，2，3}，

是A上的整除關(guān)系，則有

1

2，1

3，

1=1，2=2，3=3，

2和3不可比.

例如數(shù)集上的小于或等于關(guān)系是全序關(guān)系，因?yàn)槿魏蝺蓚€(gè)數(shù)總是可比大小的.但整除關(guān)系一般來說不是全序關(guān)系，如集合{1,2,3}上的整除關(guān)系就不是全序關(guān)系，因?yàn)?和3不可比.定義4.5.7設(shè)R為非空集合A上的偏序關(guān)系，如果

x，y∈A，x與y都是可比的，則稱R為A上的全序關(guān)系(或線序關(guān)系).哈斯圖偏序關(guān)系關(guān)系圖的簡化圖定義4.5.8設(shè)<A,

>為偏序集.

x,y∈A，如果x

y且不存在z∈A使得xz

y，則稱y覆蓋x.

例如{1,2,4,6}集合上的整除關(guān)系，有