二元關系和函數說起關系這個詞，對我們并不陌生，世界上存在著各種各樣的關系，人與人之間的“同志”關系；“同學”關系；“朋友”關系；“師生”關系；“上下級”關系；“父子”關系；兩個數之間有“大于”關系；“等于”關系和“小于”關系；兩個變量之間有一定的“函數”關系；計算機內兩電路間有導線“連接”關系；程序間有“調用”關系等等。所以對關系進行深刻的研究，對數學與計算機科學都有很大的用處。在這一章我們要研究集合內元素間的關系以及集合之間元素之間的關系，這就是“關系”與“函數”。它們是很重要的基本數學概念，在數學領域中均有很大的作用，并且對研究計算機科學中的許多問題如數據結構、數據庫、情報檢索、算法分析、計算理論等都是很好的數學工具。

關系的引入

例4.0設一旅館有n個房間，每個房間可住兩個旅客，所以一共可住2n個旅客，在旅館內，旅客與房間有一定關系，用R

表示“某旅客住在某房間”這種關系。設n=3表示旅館共有3個房間,分別記以1,2,3可住6個旅客分別記以a,b,c,d,e,f,這些旅客住的房間如右下圖所示123abcdef滿足R的所有關系可看成是一個有序偶的集合，這個集合可叫RR={<a,1>,<b,1>,<c,2>,<d,2>,<e,3>,<f,3>}

若令

A={a,b,c,d,e,f}B={1,2,3}則例中關系的每一元素均屬于A×B亦即R是A×B的子集，并稱此關系為從A到B的關系R。§4.1集合的笛卡爾積與二元關系定義4.1由兩個元素x,y（允許x=y）按一定順序排列成的二元組叫做一個有序對或序偶，記作<x,y>,其中x是它的第一元素，y是它的第二元素。有序對<x,y>具有以下性質：(1)當x≠y時，<x,y>≠<y,x>(2)<x,y>=<w,v>

x=w∧y=v例4.1：已知<x+3,y-2>=<y+7,3y-x>，求x和y。解：由有序對相等的充要條件得

x+3=y+7y-2=3y-x

解得x=6,y=2§4.1集合的笛卡爾積與二元關系定義4.2一個有序n元組(n≥3)是一個有序對，其中第一個元素是一個有序n-1元組，一個有序n元組記作<x1,x2,…,xn>,即<x1,x2,…,xn>=<

<x1,x2,…,xn-1>,xn>

例如：空間直角坐標系中點的坐標<1,-1,3>,<2,4.5,0>等都是有序3元組。n維空間中點的坐標或n維向量都是有序n元組。形式上也可以把<x>看成有序1元組。定義4.3

設A，B為集合，用A中元素為第一元素，B中元素為第二元素構成有序對。所有這樣的有序對組成的集合叫做A和B的笛卡兒積，記作A×B。笛卡兒積的符號化表示為：

A×B={<x,y>|x∈A∧y∈B}例如：若A={1,2},B={a,b,c},則A×B={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>}B×A={<a,1>,<a,2>,<b,1>,<b,2>,<c,1>,<c,2>}易知：若|A|=m,(即集合A的元素的個數),|B|=n,則|A×B|=|B×A|=mn§4.1集合的笛卡爾積與二元關系由前面的定義可知：有序對就是有順序的數組，如<x,y>，x,y的位置是確定的，不能隨意放置。

注意：有序對<a，b>

<b,a>，以a,b為元素的集合{a,b}={b,a}；有序對(a,a)有意義，而集合{a,a}不成立，因為它只是單元素集合，應記作{a}。

笛卡兒積是一種集合合成的方法，把集合A，B合成集合A×B，規定

A×B＝{<x,y>

x

A,y

B}由于有序對<x,y>中x,y的位置是確定的，因此A×B的記法也是確定的，不能寫成B×A。

笛卡兒積也可以多個集合合成

A1×A2×…×An。

笛卡兒積的運算性質。笛卡兒積的性質：1、對任意集合A，根據定義有

A×φ=φ×A=φ2、一般來說，笛卡兒積不滿足交換律，即

A×B≠B×A（當A≠BB≠φ、A≠φ時）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)§4.1集合的笛卡爾積與二元關系例4.2證明：(B∩C)×A=(B×A)∩(C×A)對于<x,y><x,y>∈(B∩C)×A

x∈(B∩C)∧y∈A

x∈B∧x∈

C∧y∈A

x∈B∧x∈C

∧y∈A∧y∈A

(x∈B∧y∈A)∧(x∈C∧y∈A)

<x,y>∈B×A∧<x,y>∈C×A

<x,y>∈(B×A)∩(C×A)∴(B∩C)×A=(B×A)∩(C×A)§4.1集合的笛卡爾積與二元關系例4.3：設A，C，B，D為任意集合，判斷以下命題是否為真，并說明理由。(1)A×B=A×C=>B=

C(2)A-(B×C)=(A-B)×(A-C)(3)存在集合A,使得A

A×A.解：(1)不一定為真。反例A=φ,B、C為任意不相等的非空集合。(2)不一定為真。反例A={1},B={2},C={3}.(3)為真。當A=φ時成立。定義4.4

設A1,A2,…,An,是集合(n≥2),它們的n階笛卡兒積記作A1×A2×…×An

，其中

A1×A2×…×An={<x1,x2,…,xn

>

|x1

A1∧x2

A2∧…∧xn

An

}

當A1=A2=…=An=A時,將起n階笛卡兒積記作An例如，A={a,b},則

A3=A×A×A={a,b}×{a,b}×{a,b}

={<a,a,a>,<a,a,b>,<a,b,a>,<a,b,b>,<b,a,a>,<b,a,b>,<b,b,a>,<b,b,b>}§4.1集合的笛卡爾積與二元關系例4.6設集合A={a,b},B={1,2,3},C=tax61gx,求A×B×C，B×A。解先計算A×B＝{<a,1>,<a,2>,<a,3>,<b,1>,<b,2>,<b,3>} A×B×C＝

{<a,1>,<a,2>,<a,3>,<b,1>,<b,2>,<b,3>}×ldbh11r＝{<a,1,d>,<a,2,d>,<a,3,d>,<b,1,d>,<b,2,d>,<b,3,d>}

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

例4.7設集合A＝{1,2},求A×P(A)。解P(A)={

,{1},{2},{1,2}} A×P(A)＝{1,2}×{

,{1},}{2},{1,2} ={<1,

>,<2,

>,<1,{1}>,<2,{1}>,<1,{2}>,<2,{2}>,<1,{1,2}>,<2,{1,2}>}定義4.5

如果一個集合符合以下條件之一：(1)集合非空，且它的元素都是有序對(2)集合是空集則稱該集合為一個二元關系，記作R，簡稱為關系。對于二元關系R，若<x,y>∈R,可記作xRy;如果<x,y>R,則記作xRy。例：R1={<1,2>,<a,b>},R2={5,6,7}aR1b,1R12,5R16§4.1集合的笛卡爾積與二元關系二元關系是兩種客體之間的聯系，例如某學生學習語文、數學、外語，表示為

A＝{語文,數學,外語}功課的成績分四個等級，記作B＝{A，B，C，D}于是該生成績的全部可能為A×BA×B＝{<語文,A>,<語文,B>,<語文,C>,<語文,D>,<數學,A>,<數學,B>,<數學,C>,<數學,D>,<外語,A>,<外語,B>,<外語,C>,<外語,D>}而該生的實際成績

P＝{<語文,B>,<數學,A>,<外語,D>}可以看出P是A×B的一個子集，它表示了功課與其成績的一種關系。由此可見：兩個集合之間的二元關系，實際上就是兩個元素之間的某種相關性。定義4.6設A，B為集合，A×B的任何子集所定義的二元關系叫做從A到B的二元關系，特別當A=B時則叫做A上的二元關系。例4.7：若A={a,b}，B={2,5,8}，則

A×B={<a,2>,<a,5>,<a,8>,<b,2>,<b,5><b,8>}令R1={<a,2>,<a,8>,<b,2>},R2={<a,5>,<b,2><b,5>},R3={<a,2>}因為R1

A×B，R2

A×B，R3

A×B，所以R1，R2和R5均是由A到B的二元關系因為只討論二元關系，所以今后無特別聲明，術語“關系”皆指二元關系？又例：若A={a,b}，B={2,5,8}，則

B×A={<2,a>,<2,b>,<5,a>,<5,b>,<8,a><8,b>}令R4={<2,a>,<2,b>},R5={<5,a>,<8,a><8,b>},因為R4B×A，R5B×A，所以R4和R5均是由B到A的關系又B×B={<2,2>,<2,5>,<2,8>,<5,2>,<5,5>,<5,8>,<8,2>,<8,5>,<8,8>}

令R6={<2,2>,<5,2>,<8,2>},R7={<8,5>,<5,2><2,8>,<2,5>}因為R6B×B，R7B×B，所以R6和R7均是集合B上的關系。若集合|A|=n,則集合A上的二元關系有多少個？答曰：|A|=n，則|A×A|=n2,A×A的任一個子集就是A上的二元關系，即P(A)=2n個。２例4.8

A={1,2}則A×A有2n個不同的二元關系A×A={1,2}×{1,2}={<1

1>,<1,2>,<2,1>,<2,2>}A×A的任一個子集就是A×A的冪集，即P(A)P(A)={

,{<1,1>},{<1,2>},{<2,1>},{<2,2>}

{<1,1>,<1,2>},{<1,1>,<2,1>},{<1,1>,<2,2>}

{<1,2>,<1,1>},{<1,2>,<2,1>},{<1,2>,<2,2>}

{<2,2>,<1,1>},{<2,2>,<1,2>},{<2,2>,<2,1>}

{<1,1>,<1,2>,<2,1>},

{<1,1>,<1,2>,<2,2>},

{<1,1>,<2,1>,<2,2>},{<1,2>,<2,1>,<2,2>}

{<1,1>,<1,2>,<2,1>,<2,2>}}

集合中的元素不分順序２若集合A={a,b,c}

則A的冪集，P(A)為P(A)={

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

（注{a,a}={a}{b,b}={b}{c,c}={c}）三類特殊的關系

對于任何集合A，空集φ

是A×A的子集，叫做A上的空關系定義EA={<x,y>|x∈A∧y∈A}=A×A為全域關系定義IA={<x,x>|x∈A}為恒等關系例：若A={1,2}，則

EA={<1,1>,<1,2>,<2,1>,<2,2>}

IA={<1,1>,<2,2>}除上述三類特殊的關系外，還有一些常用的關系，如：

LA={<x,y>|x,y∈A∧x≤y}(A

R)為實數集上的小于等于關系。

DA={<x,y>|x,y∈A∧x整除y}(A

Z*)為非正整數集上的整除關系。

R

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

y}(A是集合族)為集合上的包含關系。類似地還可以定義大于等于關系、大于關系、小于關系、真包含關系等。§4.1集合的笛卡爾積與二元關系例4.9：設A={1,2,3,4}，請表示下列關系。(1)R={<x,y>|x是y的倍數}(2)R={<x,y>|(x-y)2∈A}(3)R={<x,y>|x除y是素數}(4)R={<x,y>|x≠y}§4.1集合的笛卡爾積與二元關系解(1)DA={<1,1>,<2,2>,<3,3>,<4,4>,<2,1>,<3,1>,<4,1>,<4,2>}(2)R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>,<2,4>,<4,2>,<3,4>,<4,3>}(3)DA={<1,2>,<1,3>,<2,4>}(4)R={<1,2>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4>,<3,1>,<3,2>,<3,4>,<4,1>,<4,2>,<4,3>}|A|=n,|B|=m,A,B中的元素已按一定的次序排列若A={x1,x2,…,xn},B={y1,y2,…,ym}且R

A

B,若

1若xiRyjrij=(i=1,2,…,nj=1,2,…,m)0若xiRyj則稱矩陣M(R)=(rij)n

m為R的關系矩陣。有窮集合上的二元關系的三種表示方法：集合表示法（前已使用）

關系矩陣法關系圖關系矩陣是表示關系的另一種有效的方法，其優點是可以利用矩陣作為研究關系的手段，而且這樣做便于計算機進行處理。設R：AB，A和B都是有限集，且

設A，B為集合，A×B的任何子集Ri

A×B則稱Ri所定義的二元關系叫做從A到B的二元關系，特別當A=B時則叫做A上的二元關系則r11r12…r1n(rij)=r21r22…r2n

…rn1rn2…rnn是R的關系矩陣，記作MR。關系矩陣法若A={x1,x2,…,xn},B={y1,y2,…,yn

}則R的關系矩陣是一個n行n列矩陣M(R)=(rij)nn

,

其中元素rij

為：1若xiRyjrij=(i,j=1,2,…,n)0若xiRyj

0111MR=001100010000例4.10A={1,2,3,4}R為A上的小于關系，則R為：R={<1,2>,<1,3>,<1,4>,<2,3>,<2,4>,<3,4>}R的關系矩陣為：12341234例4.11設集合A＝{2,3,4},B={8,9,12,14}.R是由A到B的二元關系，定義：

R={<a,b>|a整除b}寫出R的表達式和關系矩陣.解R={<2,8>,<2,12>,<2,14>,<3,9>,<3,12>,<4,8>,<4,12>}89121421011R的關系矩陣為.MR=3011041010

關系圖關系圖是表示關系的一種直觀形象的方法，設R：AB，A和B都是有限集，A={x1,x2,…,xn},B={y1,y2,…,ym}關系R的有序偶<xi,yj

>可用圖中從結點xi到yj

的有向邊表示，這樣即可將關系用圖表示之。例4.12設R:AB，A={x1,x2,x3,x4},B={y1,y2,y3}R={<x1,y2>,<x2,y1>,<x2,y3><x3,y3>}R的關系如下圖所示x1x2x3x4y1y2y3關系圖關系圖是表示關系的一種直觀形象的方法，設R：AB，A和B都是有限集，

A={x1,x2,…,xn},B={y1,y2,…,ym}關系R的有序偶<xi,yj

>可用圖中從結點xi到yj

的有向邊表示，這樣即可將關系用圖表示之。例4.13設R:AA，A={a,b,c,d}R={<a,b>,<a,c>,<b,a>,<b,c>,<c,c>}R的關系如下圖所示abcd其中c到c的邊稱為環定義4.8設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關系的運算例4.14下列關系都是整數集Z上的關系，分別求出它們的定義域和值域R1={<x,y>|x,yZ∧x≤y}(2)R2={<x,y>|x,yZ∧x2+y2=1}(3)R3={<x,y>|x,yZ∧y=2x}R4={<x,y>|x,yZ∧|x|=|y|=3}解(1)domR1=ramR1=ZR2={<0,1>,<0,-1>,<1,0>,<-1,0>}

domR2={0,1,-1}ramR2={0,1,-1}(3)domR3=ZramR3={2z|zZ}

即偶數集(4)domR4={-3,3}ramR4={-3,3}10-1-101domR2ramR2R2…210-1-2……43210-1-2-3-4…domR3=ZramR3R3例4.15設R1={<1,2>,<2,4>,<3,3>}R2={<1,3>,<2,4>,<4,2>}

求其定義域和值域解題目沒有告訴我們R1和R2是由什么集合到什么的關系,這對于我們解此題是無關緊要的,事實上,不論R1和R2是定義在何種集合上的關系,據定義域和值域的定義domR={x|

y(<x,y>∈R)}ranR={y|

x(<x,y>∈R)}有

domR1={1,2,3}

domR2={1,2,4}

ramR1={2,4,3}ramR2={3,4,2}規律:集合R1和R2中序偶中的第一個元素的集合即為其定義域,序偶中的第二個元素的集合即為其值域.如果此題再加上求R1∪R2及

R1∩R2定義域和值域,則因為R1∪R2={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}R1∩R2={<2,4>}

所以domR1∪domR2={1,2,3,4}

ramR1∪

ramR2={2,3,4}定義4.9設F,G為任意的關系,A為集合，則(1)F的逆記作F-1,

F-1={<x,y>|yFx}

(2)

F與G的合成記作F

G，其中F

G={<x,y>|

z(xGz∧zFy}

或F

G={<x,y>|

z(xFz∧zGy} p87

(3)F在A上限制記作F『A

F『A={<x,y>|xFy

∧x∈A)}(4)A在F下的象記作F[A]

F[A]=ran(F『A)§4.2關系的運算逆關系：

設R是一個X到Y的關系，則Y到X的關系R-1：

R-1={<y,x>|<x,y>R}

稱為R的逆關系。例4.16

設X={1,2,3}Y={a,b,c}

且設R是從X到

Y的關系R={<1,a>,<2,b>,<3,c>}

則R-1={<a,1>,<b,2>,<c,3>}例4.17

設X={x1,x2,x3}Y={y1,y2,y3}

且設R是從X到Y的關系R={<x1,y2>,<x2,y3>,<x3,y1>}的逆關系

R-1={<y2,x1>,<y3,x2>,<y1,x3>}如下圖所示：x1x2x3y1y2y3y1y2y3x1x2x3

RR-1合成關系（或復合關系）

設R是一個X到Y的關系，S是一個Y到Z的關系,則R與S的合成關系(或復合關系):R

S

為：R

S

={<x,y>|

z(xSz∧zRy}

例4.18

設X={x1,x2,x3},Y={y1,y2,y3},Z={z1,z2,z3}

從X到Z的關系S={<x1,z1>,<x1,z2>,<x2,z2>}從Z到Y的關系R={<z1,y2>,<z2,y3>,<z3,y3>}則X到Z的關系R

S={<x1,y2>,<x1,y3>,<x2,y3>}XZYXYRSR

S

x1x2x3z1z2z3y1y2y3x1x2x3y1y3y2例4.19：設A={2,3}

,G={<2,1>,<3,4>},R={<1,2>,<1,3>,<3,2>}

則R-1,R

G，G

R，R『A,R『φ,R[A],R[φ]分別是

R-1={<2,1>,<3,1>,<2,3>}R

G={<2,2>,<2,3>}G

R={<1,1>,<1,4>,<3,1>}R『A={<x,y>|xRyxA}={

<3,2>}R『φ=φR[A]=ran(R『A)={2}R[φ]=φ注意：逆運算的優先級高于其他運算，而所有的關系運算都優于集合運算。例4.20設有集合A={4,5,8,15},B={3,4,5,9,11}C={1,6,8,13},F是由A到B的關系,G是由B到C的關系,分別定義為

F={<a,b>||b-a|=1}G={<b,c>||b-c|=2或|b-c|=4}求合成關系G

F和F

G

解先求G

F,由題意知F={<4,3>,<4,5>,<5,4>,<8,9>}G={<3,1>,<4,6>,<4,8>,<5,1>,<9,13>,<11,13>}G

F={<4,1>,<5,6>,<5,8>,<8,13>}

例4.20(續)設有集合A={4,5,8,15},B={3,4,5,9,11}C={1,6,8,13},F是由A到B的關系,G是由B到C的關系,分別定義為

F={<a,b>||b-a|=1}G={<b,c>||b-c|=2或|b-c|=4}求合成關系G

F和F

G

解再求F

G,由題意知G={<3,1>,<4,6>,<4,8>,<5,1>,<9,13>,<11,13>}F={<4,3>,<4,5>,<5,4>,<8,9>}F

G={<4,9>}例4.21：設F={<a,{a}>,<{a},{a,{a}}>}

求F

F，F『{a}，F『[{a}]解因為F={<a,{a}>,<{a},{a,{a}}>}

F={<a,{a}>,<{a},{a,{a}}>}

所以F

F={<a,{a,{a}}>}

由公式F『A={<x,y>|xFy

∧x∈A)}有F『{a}={<a,{a}>}

由公式F[A]=ran(F『A)有F『[{a}]=ran(F『{a})=ran{<a,{a}>}={{a}}定義域值域定理4.1

設F、G、H是任意關系,則(1)(F-1)-1=F(2)dom(F-1)=ranF,ranF-1=domF

(3)(F

G)

H=F

(G

H)(4)(F

G)-1=G-1

F-1證明:(1)任取<x,y>,由逆的定義有<x,y>∈(F-1)-1

<y,x>∈F-1

<x,y>∈F∴(F-1)-1=F(2)任取x,x∈ranF-1

y(<y,x>∈F-1)

y(<x,y>∈F)

x∈domF∴ranF-1=domF同理可證dom(F-1)=ranF

(3)(F

G)

H=F

(G

H)(4)(F

G)-1=G-1

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

G)

H

t(<x,t>∈F

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)(4)任取<x,y>,<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

定理4.2

設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證明:(1)任取<x,y>,<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證明:(3)任取<x,y>,<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本定理對有限個關系的并和交都成立。R

(R1∪R2∪…∪Rn)=R

R1∪R

R2∪…∪R

Rn(R1∪R2∪…∪Rn)

R=R1

R∪R2

R∪…∪Rn

RR

(R1∩

R2∩…∩Rn)

R

R1∩R

R2∩…∩R

Rn(R1∩R2∩…∩Rn)

R

R1

R∩R2

R∩…∩Rn

R定義4.10

設R是A上的關系,n為自然數，則R的n次冪規定如下(1)R0={<x,x>|x∈A}(2)Rn=Rn-1

Rn≥1

由定義可以知道R0就是A上的恒等關系IA，不難證明下面的等式

R

R0=R=R0

R由這個等式立即可以得到R1=R0

R=R例4.22設A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}

求R0，R1，R2，R3，R4和R5解R0

={<a,a>,<b,b>,<c,c>,<d,d>}R1

=R0

R={<a,b>,<b,a>,<b,c>,<c,d>}

{<a,a>,<b,b>,<c,c>,<d,d>}={<a,b>,<b,a>,<b,c>,<c,d>}R2

=R

R

={<a,b>,<b,a>,<b,c>,<c,d>}

{<a,b>,<b,a>,<b,c>,<c,d>}={<a,a>,<a,c>,<b,b>,<b,d>}R3

=R2

R

={<a,a>,<a,c>,<b,b>,<b,d>}

{<a,b>,<b,a>,<b,c>,<c,d>}={<a,b>,<b,a>,<b,c>,<a,d>}R4

=R3

R

={<a,b>,<b,a>,<b,c>,<a,d>}

{<a,b>,<b,a>,<b,c>,<c,d>}={<a,a>,<a,c>,<b,b>,<b,d>}R5

=R4

R

={<a,a>,<a,c>,<b,b>,<b,d>}

{<a,b>,<b,a>,<b,c>,<c,d>}={<a,b>,<b,a>,<b,c>,<a,d>}定理4.3

設R是A上的關系,m,n為自然數，則下面的等式成立(1)Rm

Rn=Rm+n

(2)(Rm)n=Rmn證明：(1)任給m，對n作歸納法。

n=0時，Rm

?R0=Rm

=Rm+0。

假設Rm

?Rn=Rm+n，那么Rm?Rn+1=Rm?(Rn?R1)=(Rm?Rn)?R1=Rm+n?R1=Rm+n+1=Rm+(n+1)

。(2)任給m，對n作歸納法。

n=0時，(Rm)0=R0=Rm

0。

假設(Rm)n=Rmn。

那么(Rm)n+1=(Rm)n

?

Rm

=Rmn

?Rm=Rmn+m=Rm(n+1)

011001101110M

2

=MM=10001000=0110011001101110000000000000111001101110M

3

=M2M=01101000=1110111001101110000000000000例4.23：設A={1,2,3,4},R是A上二元關系，關系矩陣為0110M

=100001100000解：R，R2,R3

的關系矩陣分別為：求R3。(M為R的關系矩陣)設R是A上的關系，R的性質主要有以下5種(1)若

x(x∈A<x,x>∈R),則稱R在A上是自反的。也就是說，對R

A

A，若A中每個x，都有xRx，則稱R是自反的，即

A上關系R是自反的

x(x

A

xRx)該定義表明了，在自反的關系R中，除其他有序對外，必須包括有全部由每個x

A所組成的元素相同的有序對例如：設A={1,2,3},R

是A上的關系，

R={<1,1>,<2,2>,<3,3>,<1,2>}

則R

是自反的§4.3關系的性質設R是A上的關系，R的性質主要有以下5種(2)若

x(x∈A<x,x>∈R),則稱R在A上是反自反的也就是說，對R

A

A，若A中每個x，有xRx，則稱R是反自反的，即A上關系R是反自反的

x(x

A

xRx)該定義表明了，一個反自反的關系R中，不應包括有任何相同元素的有序對。例如：設A={1,2,3}，R

是A上的關系，

R={<2,3>,<3,2>}

R是反自反的

§4.3關系的性質應該指出，任何一個不是自反的關系，未必是反自反的；反之，任何一個不是反自反的關系，未必是自反的。這就是說，存在既不是自反的也不是反自反的二元關系。例如：設A={1,2,3},R

是A上的關系，R={<1,1>,<2,2>}缺少{<3,3>}則R是既不是自反的，也不是反自反的§4.3關系的性質(3)若

xy(x,y∈A∧<x,y>∈R<y,x>∈R),則稱R在A上是對稱的。也就是說,對R

A

A,對A中每個x和y,若xRy,則yRx,稱R是對稱的,即A上關系R是對稱的(x)(

y)(x,y

A

xRy→yRx)該定義表明了，在表示對稱的關系R的有序對集合中，若有有序對<x,y>，則必定還會有有序對<y,x>。例如：設A={1,2,3},R是A上的關系，

R4={<1,2>,<2,1>,<3,3>}

則R

是對稱的(4)若

xy(x,y∈A∧<x,y>∈R∧x≠y<y,x>R),

則稱R在A上是反對稱的。(隱含x=y<y,x>∈R)也就是說,對R

A

A，對A中每個x和y，若xRy且yRx，則x=y，稱R是反對稱的，即A上關系R是反對稱的

(

x)(

y)(x,y

A

xRy

yRx→x=y)該定義表明了，在表示反對稱關系R的有序對集合中，若存在有序對<x,y>和<y,x>，則必定是x=y。或者說，在R中若有有序對<x,y>，則除非x=y，否則必定不會出現<y,x>。例如：設A={1,2,3},R={<1,2>,<1,3>}

是A上的關系，則R是反對稱的

判斷一個關系是否反對稱,通俗地講就是對于所有的a,b∈A,若a≠b,則序偶<a,b>,<b,a>至多只有一個出現在關系R中。如R={<1,2>,<1,1>,<3,1>}

有些關系既是對稱的又是反對稱的還有的關系既不是對稱的又不是反對稱的，例如：設A={1,2,3},R6,R7是A上的關系，

R6={<1,1>}R7={<1,2>,<2,1>,<1,3>}則R6是對稱的，也是反對稱的R7既不是對稱的又不是反對稱的再如，A={a,c,b>,中R={<a,b>,<a,c>,<c,a>}

既不是對稱的又不是反對稱的。例4.24設A={1,2,3,4,5},A上的關系R為

R={<a,b>|a-b是偶數}①用列舉法表示R

②R是否自反、對稱、反對稱？解:①R={<1,1>,<1,3>,<1,5>,<2,2>,<2,4>,<3,3><3,1>,<3,5>,<4,2>,<4,4>,<5,1>,<5,3><5,5>}

②∵對任意a∈A,a-a=0是偶數∴R是自反關系又∵對任意a,b∈A,若a-b是偶數,則b-a也是偶數∴R是對稱關系。

∵當a≠b時，有<a,b>和<b,a>

同時出現在

R中,例如<1,3>,<3,1>,<2,4>,<4,2>,<3,5>,<5,3>

∴R不是反對稱關系。(5)

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

則稱R在A上是傳遞的關系。也就是說,對R

A

A，對于A中每個x,y,z，若xRy且yRz，則xRz，稱R是傳遞的，即A上關系R是傳遞的

(

x)(

y)(

z)(x,y,z

A

xRy

yRz→xRz)該定義表明了，在表示可傳遞關系R的有序對集合中，若有有序對<x,y>和<y,z>，則必有有序對<x,z>。(5)

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

則稱R在A上是傳遞的關系。例4.25設A={1,2,3,4,5},A上的關系R為

R={<a,b>|a-b是偶數}①用列舉法表示R

②R是否是可傳遞的？解:①R={<1,1>,<1,3>,<1,5>,<2,2>,<2,4>,<3,3><3,1>,<3,5>,<4,2>,<4,4>,<5,1>,<5,3><5,5>}

②對于任意的a,b,c∈A

若a-b=2m,b-c=2n,則a-c=(a-b)+(b-c)=2(m+n)

也是偶數。因此A是可傳遞的。

∵<a,b>∈R∧<b,c>∈R<a,c>∈R例4.26設A={1,2,3,4,5,6,7,8,9,10}R是A上的關系，

R={<x,y>|x,y∈A∧x+y=10}

說明R具有哪些性質。解：

R={<1,9>,<2,8>,<3,7>,<4,6>,<5,5>

,<9,1>,<8,2>,<7,3>,<6,4>}易知R既不是自反也不是反自反的

R是對稱的

R不是反對稱的

R不是傳遞的。§4.3關系的性質P1P3P4P2這個關系如右圖所示。我們知道，調用關系是傳遞的，如P1能調用P2，P2能調用P4，則P1亦能調用P4。我們希望在R的基礎上建立一個滿足傳遞性的新關系，譬如說，下面的關系R′即是這樣一個關系§4.4關系的閉包什么叫一個關系上的閉包呢？設有四個程序所組成的集合P={P1,P2,P3,P4}上的“調用”關系R：R={<P1,P2>,<P2,P4>,<P1,P3>,<P3,P4>}R′={<P1,P2>,<P2,P4>,<P1,P3>,<P3,P4>,<P1,P4>}當然滿足這個條件的關系不僅僅R′一個，如下面的關系R″亦是R″={<P1,P2>,<P2,P4>,<P1,P3>,<P3,P4>,<P1,P4>,<P2,P2>}我們選用滿足這個條件的最小者，在這個例子中即為R′。這個R′我們就叫做R上的傳遞閉包。R′是一個新關系，它是在集合P上的一個新的調用關系顯然有R

R'R'

R''

選用滿足這個條件的最小者R',這個新關系叫做R上的傳遞閉包，它是在集合P上的一個新的調用關系。

對于關系的自反性、對稱性、傳遞性均可建立閉包。定義4.11設R是非空集合A上的關系，R的自反(對稱或傳遞)閉包是A上的關系R′,使得R′滿足以下條件:(1)R′是自反(對稱或傳遞)的(2)RR′

(3)對A上的任何包含R的自反(對稱或傳遞)關系R″有R′R″

一般將R的自反閉包記作r(R),對稱閉包記作s(R)，傳遞閉包記作t(R)。§4.4關系的閉包定理4.4

設R是非空集合A上的關系，則有(1)r(R)=R∪R0(2)s(R)=R∪R-1(3)t(R)=R∪R2∪R3∪…

此定理提供了一種集合表示形式下關系閉包的求解方法§4.4關系的閉包例4.27設A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},則r(R)=R∪R0={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>,<c,c>,<d,d>,<b,b>,<a,a>}s(R)=R∪R-1={<a,b>,<b,a>,<b,c>,

<c,d>,<d,b>}

∪{<b,a>,<a,b>,<c,b>,

<d,c>,<b,d>}={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>,<c,b>,<d,c>,<b,d>}t(R)=R∪R2∪R3∪…(甚不方便)當關系用關系矩陣表示時，相應閉包求法為：

(1)Mr=M+E(2)Ms=M+M′(3)Mt=M+M2+M3+…其中M為R的關系矩陣，E是單位矩陣，M`是M的轉置矩陣.§4.4關系的閉包010010001100Mr=M+E=1010+0100=1110000100100011010000010101010001000100Ms=M+M′=1010+1001=10110001010001010100001001101111Mt=M+M2+M3+…=111111111111例4.28

設A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},則§4.4關系的閉包E表示同階單位陣；M'表示M的轉置矩陣

abcdabcd請編程實現Warshall算法:一種求Mt的算法：(矩陣+轉置矩陣)設R為n元集上的關系，M是R的關系矩陣，則(1)置新矩陣N=M;(2)置I=1;(3)對j(1≤j≤n),若N的第j行第i列處為1，則對k=1,2,…,n做如下計算：將N的第j行k列處元素與第i行k列處元素進行邏輯加，然后將結果放到第j行k列處，即

N[j,k]=N[j,k]+N[i,k];(4)i=i+1;(5)若i≤n,go(3),否則停止。最終得到的矩陣N就是Mt。作業：請用C語言編寫相應的程序段。#defineN3main(){inta[N][N]={{1,0,0},{0,1,0},{0,1,1}};

inti,j,k,s;

for(I=0;I<N;i++)for(j=0;j<N;j++)if(a[j][I])

for(k=0;k<N;k++) {a[j][k]+=a[I][k];if(a[j][k]>1)a[j][k]=1;}}當關系用關系圖表示時，相應閉包求法為:設R,r(R),s(R),t(R)的關系圖分別為G,Gr,Gs,Gt,則Gr,Gs,Gt與G的頂點集相等,除了G的邊以外依據下列方法添加新的邊:(1)考察G的每個頂點,如果沒有環就加上一個環,最終得到的是Gr。(2)考察G的每一條邊，如果有一條xi到xj的單向邊，i≠j，則在G中加一條xj到xi的反方向邊，最終得到Gs

。(3)考察G的每個頂點xi,找出從xi出發的所有2步,3步,…,n步長的路徑(n為G中的頂點數).設路徑的終點為xj1,xj2,…,xjk，如果沒有從xi到xjl

(i=1,2,…,k)的邊，就加上這條邊，最終得到Gt。例題參見P93例4.10§4.5等價關系和偏序關系定義4.12

設R是非空集合A上的關系。若R是自反的、對稱的和傳遞的,則稱R是A上的等價關系如果R是一個等價關系，若<x,y>∈R,稱x等價于y,記作x~y。

等價關系=自反性+對稱性+傳遞性也就是說,若<a,b>

R,或aRb,稱a等價b,記a

b

由于R是對稱的，a等價b即b等價a，反之亦然，a與b彼此等價。.例4.29

設有一個整數集Z

上的關系R：R={<x,y>|x-y可被3整除}

求證這個關系是等價關系