第四章

二元關系和函數(2/3)4.2關系的運算

定義4.2.1設R是二元關系.

(1)R中所有的有序對的第一元素構成的集合稱為R的定義域，記為domR.形式化表示為domR={x|

y(<x,y>∈R)}

(2)R中所有有序對的第二元素構成的集合稱為R的值域，記作ranR.形式化表示為ranR={y|

x(<x,y>∈R)}

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

關系的基本運算例4.2.1設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設F,G為二元關系，G對F的(左)復合記作F

G，其中

F

G={<x,y>|

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

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

定義4.2.4設R為二元關系，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設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設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設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設F是任意的關系，則

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

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

關系運算的性質

定理4.2.2設F，G，H是任意的關系，則

(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設R為A上的關系，則

R

IA=IA

R=R

定理4.2.4設F，G，H是任意關系，則

(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設F為關系，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]

關系冪定義4.2.5設R為A上的關系，n為自然數，則R的n次冪定義為：

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

（2）Rn+1=Rn

R

怎樣計算Rn

呢？如果R是用集合表達式給出的，可以通過n-1次右復合計算得到Rn.如果R是用關系矩陣M給出的，則Rn

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

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

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

的關系圖G'.G'的頂點集與G相同.考察G的每個頂點xi，如果在G中從xi

出發經過n步長的路徑到達頂點xj，則在G'中加一條從xi

到xj

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

例4.2.5設A={a,b,c,d}

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

M=

則R的關系矩陣分

M0=

則R2，R3，R4的關系矩陣分別是

M2=

=

M3=M2M=

=

M4=M3M=

=

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

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

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

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

，即A×A的不同子集僅

個.當列出R的各次冪R0，R1，R2，…，

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

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

定理4.2.7設R是A上的關系，m,n∈N，則

(1)Rm

Rn=Rm+n

(2)(Rm)n=Rmn

4.3關系的性質一．關系的五種基本性質

定義4.3.1設R為A上的關系，

（1）若

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

（2）若

x(x∈A→<x,x>

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

例4.3.1設A={1,2,3}，R1，R2，R3是A上的關系，其中

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

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

R3＝{<1,3>}

說明R1，R2和R3是否為A上的自反關系和反自反關系.

R2是自反的R3是反自反的R1兩者都不是定義4.3.2設R為A上的關系，

若

x

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

若

x

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

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

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

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

x

y

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

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

例4.3.3設A＝{1,2,3}，R1，R2，R3是A上的關系，其中R1＝{<1,1>,<2,2>}

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

R3＝{<1,3>}說明R1，R2和R3是否為A上的傳遞關系.

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

都是A上的傳遞關系.小于等于關系，整除關系和包含關系也是相應集合上的傳遞關系.小于關系和真包含關系仍舊是相應集合上的傳遞關系

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

RR∩R-1

IA

R=R-1

R∩IA=

IA

R集合表達式傳遞性反對稱性對稱性反自反性自反性關系性質的等價描述

1）該關系是對稱的，因為無單向邊.它不是自反的也不是反自反的.因為有的頂點有環，有的頂點無環.它不是反對稱的，因為圖中有雙向邊.它也不是傳遞的，因為圖中有邊<3,1>和<1,3>，但沒有從3到3的邊，即通過3的環.例4.3.4判斷圖中關系的性質，并說明理由.

（2）該關系是反自反的但不是自反的，因為每個頂點都沒有環.它是反對稱的但不是對稱的，因為圖中只有單向邊.它也是傳遞的，因為不存在頂點x,y,z，使得x到y有邊，y到z有邊，但x到z沒有邊，其中x,y,z∈{1,2,3}.3）該關系是自反的但不是反自反的，因為每個頂點都有環.它是反對稱的但不是對稱的，因為圖中只有單向邊.但他不是傳遞的，因為2到1有邊，1到3有邊，但2到3沒有邊.關系的性質和運算之間的聯系

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

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

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

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上對稱的關系.（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上的傳遞關系.

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

√√√√√R1∩R2

√√√√√R1∪R2

√√√××R1-R2

×√√√×R1

R2

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

滿足以下條件：

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

R'

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

R''.

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

定理4.4.1設R為A上的關系，則有

（1）r(R)=R∪R0

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

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

關系閉包的求法關系矩陣和關系圖求閉包的方法:

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

Ms=M+M'

Mt=M+M2+M3+…

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

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

考察G的每個頂點，如果沒有環就加上一個環.最終得到的是Gr

.

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

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

.

例4.4.1設A={a,b,c,d}，R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}，求r(R)，s(R)，t(R)以及它們的關系圖和矩陣.解: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等價關系和偏序關系

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

其中x≡y(mod3)叫做x與y模3相等，即x除以3的余數與y除以3的余數相等.R為A上的等價關系，因為x∈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}

等價類等價類的定義定義4.5.2設R為非空集合A上的等價關系，令

x∈A

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

稱[x]R為x關于R的等價類，簡稱為x的等價類，簡記為[x]或

.

例4.5.2對于任意的整數x和y，定義模n相等關系~

x~y

iff

x≡y(modn)

~是整數集合Z上的等價關系.~將整數分成n個等價類，使用等價類的符號可記為

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

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

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

商集的定義

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

（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設A為非空集合，若A的子集族π(π

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

（1）

π

（2）

x

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

)

（3）∪π=A

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

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

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

π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的一個劃分，并且不同的商集將對應于不同的劃分.反之，任給A的一個劃分π，如下定義A上的關系R：R={<x,y>|x,y∈A∧x與y在π的同一劃分塊中}

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

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

這些劃分與A上的等價關系之間的一一對應是：π1對應于全域關系EA，π5的對應于恒等關系IA，π2，π3和π4分別對應于等價關系R2，R3和R4.

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

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

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

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

.設

為偏序關系，如果<x，y>∈

，則記作x

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

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

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

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

>.

定義4.5.6集合A和A上的偏序關系

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

>.

定義4.5.6設R為非空集合A上的偏序關系，定義

(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的前邊.

在具有偏序關系

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

x

y(或y

x)，x＝y，x與y不是可比的.

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

是A上的整除關系，則有

1

2，1

3，

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

2和3不可比.

例如數集上的小于或等于關系是全序關系，因為任何兩個數總是可比大小的.但整除關系一般來說不是全序關系，如集合{1,2,3}上的整除關系就不是全序關系，因為2和3不可比.定義4.5.7設R為非空集合A上的偏序關系，如果

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

>為偏序集.

x,y∈A，如果x

y且不存在z∈A使得xz

y，則稱y覆蓋x.

例如{1,2,4,6}集合上的整除關系，有