離散數(shù)學第二章關系

離散數(shù)學第二章關系1第1頁，課件共105頁，創(chuàng)作于2023年2月

等價關系叉積關系幺關系元組全關系傳遞閉包逆關系復合關系關系冪自反傳遞閉包自反關系對稱關系反對稱關系傳遞關系半序關系空關系余關系并關系差關系交關系2第2頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

第二章關系(relation)

§1.

集合的叉積

n元組

§2.關系

§3.關系的表示

關系的性質

§4.關系的運算

§5.

等價關系

§6.

半序關系3第3頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

§1.

集合的叉積n元組

定義1.叉積，笛卡爾積

(crossproduct,Cartesianproduct(1637))

n個集合A1，A2，，An的n維叉積定義為

=A1×

A2×

×An

={(a1,a2,,an):aiAi(1in)}；

n維叉積A1×

A2×

×An的每個元素(a1,a2,,an)都稱為一個n元組（n-tuple）；即，叉積是元組的集合；

每個n元組(a1,a2,,an)的第i個位置上的元素ai稱為該n元組的第i個分量（坐標或投影）；元組各分量的順序不能改變；

n稱為該叉積及其元組的維數(shù)；

兩個元組相等它們的維數(shù)相同且對應的分量相等。4第4頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學即(a1,a2,,an)=(b1,b2,,bm)

n=m(iN)(1in)(ai=bi)；注：笛卡爾(1596-1650)，法國數(shù)學家，1637年發(fā)表《方法論》之一《幾何學》，首次提出坐標及變量概念。這里是其概念的推廣。定義2.

二個集合A，B的(二維或二重)叉積定義為

A×B

={(a,b):aAbB}；

其元素——二元組(a,b)通常稱為序偶或偶對(orderedpair)；二元組(a,b)的第一分量上的元素a稱為前者；第二分量上的元素b稱為后者；

二重叉積的AB第一集合A稱為前集；第二集合B稱為后集。5第5頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學例1.A={a,b,c},B={0,1}A×B={(a,0),(a,1),(b,0),(b,1),(c,0),(c,1)}B×A={(0,a),(0,b),(0,c),(1,a),(1,b),(1,c)}例2.A={張三,李四}，B={白狗,黃狗}A×B={(張三,白狗),(張三,黃狗),(李四,白狗),(李四,黃狗)}B×A={(白狗,張三),(白狗,李四),(黃狗,張三),(黃狗,李四)}

一般地說，關于叉積和元組我們有：

(1)(a,b)(b,a)；

(2)A×B

B

×A；

(3)二元組不是集合，因為二元組中的分量計較順6第6頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學序,而集合中的元素是不講順序的。但是我們?yōu)榱藢⑺械母拍疃冀y(tǒng)一于集合概念，我們可采用克亞托斯基(KazimierzKurafowski)在1921年給出的定義

(a,b)={{a},{a,b}}將二元組定義為比其元素高二層的集合；

(4)我們也可用二元組來遞歸的定義n元組如下：

(a,b,c)=((a,b),c)

(a1,a2,,an-1,an)=((a1,a2,,an-1)

,an)(5)這樣，我們也就可用二重叉積來遞歸的定義n維叉積如下：

A×B×C=(A×B)×C

A1×A2×

×An-1×An=(A1×A2×

×An-1)×An7第7頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

(6)利用(5)所給的定義，我們可以遞歸的定義集合的叉積冪如下：

A2=A×AA3=A2×AAn=An-1×A

(7)我們規(guī)定空集與任何集合A的叉積是空集。即A×==×A由于若偶對的第一分量或第二分量不存在就沒有偶對存在，故規(guī)定它們的叉積集合為空集是合理的。定理1.設A,B,C,D是四個非空的集合。那么

A×B=C×DA=CB=D。8第8頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學[證].):顯然。

)：（采用邏輯法）對任何的元素a,baAbB(a,b)A×B

(a,b)C×D(條件：A×B=C×D）

aCbD

所以A=CB=D。定理2.

設A,B,C是三個集合。則

(1)左分配律：A×(B∪C)=(A×B)∪(A×C)

(叉積對并的)；

(2)左分配律：A×(B∩C)=(A×B)∩(A×C)

(叉積對交的)；

(3)右分配律：(A∪B)×C=(A×C)∪(B×C)

9第9頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

(叉積對并的)；

(3)右分配律：(A∩B)×C=(A×C)∩(B×C)

(叉積對交的)。[證].只證(1)（采用邏輯法）對任何的元素a,b

(a,b)A×(B∪C)aAbB∪CaA(bBbC)(aAbB)(aAbC)(分配律：p(qr)(pq)(pr))

(a,b)A×B(a,b)A×C

(a,b)(A×B)∪(A×C)

所以A×(B∪C)=(A×B)∪(A×C)。10第10頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

§2.關系

一.關系的基本概念定義1.二元關系(binaryrelation)

設A,B是兩個非空的集合。

二重叉集A×B的任何一個子集R都稱為是從集合A到集合B的一種二元關系。即RA×B；

當(a,b)R時，稱a與b有關系R，記為aRb；

當(a,b)R時，稱a與b沒有關系R，記為或；

當A=B時，即RA×A，則稱R是A上的一個二元關系。例1.

設A是西安交通大學全體同學組成的集合。11第11頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

R={(a,b):

aAbAa與b是同鄉(xiāng)}A×A

于是，R是西安交通大學同學之間的同鄉(xiāng)關系。例2.

設A是某一大家庭。

R1={(a,b):

aAbAa是b的父親或母親}A×AR2={(a,b):

aAbAa是b的哥哥或姐姐}A×AR3={(a,b):

aAbAa是b的丈夫或妻子}A×A

于是，

R1是父母與兒女之間的關系，即父母子女關系；

R2是兄弟姐妹之間的關系，即兄弟姊妹關系；

R3是夫妻之間的關系，即夫妻關系。例3

.

設N是自然數(shù)集合。

12第12頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

R={(a,b):

aNbNa|b}

N×N

則R就是自然數(shù)集合上的整除關系。例4

.

設Ｉ是整數(shù)集合。

R={(a,b):

aIbI(kI)(a-b=km)}

II

則R就是整數(shù)集合上的(模m)同余關系。例5

.

設A是某一大型FORTRAN程序中諸程序塊的集合。

R={(a,b):

aAbBa調用(call)b}AA

則R就是程序塊集合上的調用關系。例6.

設A={風，馬，牛}，

R={(風,馬)，(馬,牛)}AA

則R是A上的一個二元關系。13第13頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

關于關系概念，我們還有如下的幾個定義和說明：

1°全關系(fullrelation)：關系R=AB稱為全關系；

2°空關系(emptyrelation)：關系R=稱為空關系；

空關系和全關系都是平凡關系；

3°幺關系或單位關系(identicalrelation)：關系R={(a,a):aA}AA稱為A上的幺關系；例7.

設A={1,2,3,4}，則

R1={(1,1),(2,2),(3,3),(4,4)}是幺關系；

R2={(1,1),(2,3),(3,4),(4,4)}不是；

R3

={(1,1),(2,2),(3,3),(4,4),(1,2)}也不是；14第14頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

4°關系的交，并，余運算：

叉積是一種（新型的）集合；關系是叉積的子集；因此，關系也是一種（新型的）集合；

從而，有關集合論的一切概念、論述、運算也都適合于關系；

尤其是集合的交，并，余，差運算也都適合于關系；因此，關系也有交，并，余，差運算；例8.

設N是自然數(shù)集合。

R=小于關系={(m,n):mNnNmn}NN

S=整除關系={(m,n):mNnNm|n}NN

則R

=大于等于關系()；

RS=小于等于關系()；15第15頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

RS=不相等的整除關系()；

R\S=小于又不整除關系(?)；

S\R=相等關系(=)。

5°關系的擴充(expansion)：若R1

R2，則稱關系R2是關系R1的一個擴充；

6°n元關系：

n元關系R是n維叉積的一個子集；即

R

A1A2

AnR1R216第16頁，課件共105頁，創(chuàng)作于2023年2月定義3.前域(domain)后域(codomain)

設A,B是兩個非空集合，RA×B是一關系。則關系R的

前域：

(R)={a:aA(bB)(aRb)}A

；

后域：

(R)={b:bB(aA)(aRb)}B。例9.設A={1,2,3,4}，B={2,4,6,8,10}。

R={(1,2),(2,4),(3,6)}。則

(R)={1,2,3}A，

(R)={2,4,6}B。二.關系的一些關聯(lián)性質離散數(shù)學A

(R)B

(R)abR17第17頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學定理1.

設R1,R2

A×B是兩個關系。若

R1

R2

，則

(1)保序性：

(R1)

(R2)；

(2)保序性：

(R1)

(R2)；[證].只證(1)（采用邏輯法）對任何元素aA，

a

(R1

)aA(bB)(aR1b)aA(bB)((a,b)R1)

aA(bB)((a,b)R2)(條件：R1

R2

)aA(bB)(aR2b)a

(R2

)

所以

(R1)

(R2)。18第18頁，課件共105頁，創(chuàng)作于2023年2月定理2.

設R1,R2是A×B上的兩個二元關系。則

(1)

(R1∪R2)=

(R1)∪

(R2)(2)

(R1∪R2)=(R1)∪

(R2)(3)

(R1∩R2)

(R1)∩

(R2)(4)

(R1∩R2)

(R1)∩(R2)

[證].只證(1)，(3)(1)先證：

(R1)∪

(R2)

(R1∪R2)(采用包含法)由于R1

R1∪R2，R2

R1∪R2，依定理1，有

(R1)

(R1∪R2)，

(R2)

(R1∪R2)故根據(jù)第一章§2定理2的(3)，就可得

(R1)∪

(R2)

(R1∪R2)。次證：

(R1∪R2)

(R1)∪

(R2)

(采用元素離散數(shù)學19第19頁，課件共105頁，創(chuàng)作于2023年2月

離散數(shù)學法)對任何元素aA，若

a

(R1∪R2)，則存在bB

，使得

aR1∪R2b因此

(a,b)R1∪R2，從而有

(a,b)R1

或者(a,b)R2

即aR1b

或者aR2b于是

a

(R１)或者a

(R2

)故此

a

(R1)∪

(R2)

20第20頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

所以

(R1∪R2)

(R1)∪

(R2)

。

(3)先證：

(R1∩R2)

(R1)∩

(R2)(采用包含法)由于R1∩R2

R1

，R1∩R2

R2

，依定理1，有

(R1∩R2)

(R1)，

(R1∩R2)

(R2)

故根據(jù)第一章§2定理2的(3)，就可得

(R1∩R2)

(R1)∩

(R2)。其次，反方向的包含不成立。且看下面的反例。例9.設R1={(1,1),(2,2)}，R2={(1,2),(2,1)}。則，由于R1∩R2=

，故

(R1∩R2)=但是，由于

(R1)={1,2}，

(R2)={1,2}故

(R1)∩

(R2)={1,2}21第21頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

所以

(R1)∩

(R2)

(R1∩R2)。元素aA和集合A1A在關系RA×B下的關聯(lián)集

(1)a的R-關聯(lián)集(R-relativesetofa)：

R(a)={b:bBaRb}B；

(2)A1的R-關聯(lián)集(R-relativesetofA1)：

R(A1)={b:bB(aA1)(aRb)}B。于是，類似于定理1(2)，定理2(2)(4)，我們有定理.設R

A×B是一個二元關系，A1,A2

A。則

(1)保序性：A1A2R(A1)R(A2)；

(2)R(A1∪A2)=R(A1)∪R(A2)；

(3)R(A1∩A2)

R(A1)∩R(A2)。

22第22頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學[證].仿定理1(2)，定理2(2)(4)可證。留給讀者。例.設A={a,b,c,d}，并且設

R={(a,a),(a,b),(b,c),(c,a),(d,c),(c,b)}。那么R(a)={a,b}，R(b)={c}；并且如果A1={c,d}，那么R(A1)={a,b,c}。23第23頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

§3.關系的表示關系的性質

一.關系表示法

1°關系的矩陣表示法設關系RA×B，這里A,B是兩個非空的有限集合，

A={a1,a2,a3,…,am}，B={b1,b2,b3,…,bn}。則我們可用一個m×n階0—1矩陣MR來表示關系R，我們稱此矩陣MR為關系R的關系矩陣(relationmatrix)。

MR=(xij)m×n，其中

1當（ai,bj)R時

xij=(i=1,…,m；j=1,…,n)0當（ai,bj)R時24第24頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學例1.設關系RA×B，A={a1,a2,a3,a4}，B={b1,b2,b3}R={(a1,b2),(a1,b3),(a2,b3),(a3,b1),(a4,b2)}。于是，我們得到R的關系矩陣MR為(下面左矩陣)

MR=；MS=例2.設關系SA×A，A={a1,a2,a3}，

S={(a1,a1),(a2,a2),(a3,a3),(a1,a3),(a3,a1),(a2,a3),(a3,a2)}

于是，我們得到S的關系矩陣MS為(上面右矩陣)b1b2b31a1a2a3a4001011010010a1a2a31a1a2a3１01０1１1１１25第25頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

2°關系的圖形表示法設關系RA×B，這里A,B是兩個非空的有限集合，

A={a1,a2,a3,,am}，B={b1,b2,b3,,bn}。則我們可用一個有向圖GR=(VR,ER)來表示關系R，我們稱此有向圖GR為關系R的關系圖(relationdigraph)。

VR=AB，ER=R；

VR中的元素稱為結點，用小圓點表示；表示A中元素的結點放在左邊一塊；表示B中元素的結點放在右邊一塊；

ER中的元素稱為邊，用有向弧表示；若aRb(即(a,b)R)，則在表示a的結點和表示b的結點之間連一條有向弧。有向弧的始端與結點a相連，有向弧的終端與結點b相連； 26第26頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

有時我們會用兩個圓圈分別將表示兩個集合A和B中元素的結點圈起來。

所有有向弧的始端結點構成

(R)；所有有向弧的終端結點構成

(R)。若A=B，這時令VR=A，并規(guī)定只畫表示一個集合元素的結點；表示元素間關系的有向弧也只在此一個集合的結點間畫出。例3.設關系RA×B，A={a1,a2,a3,a4}，B={b1,b2,b3}R={(a1,b2),(a1,b3),(a2,b3),(a3,b1),(a4,b2)}

于是，我們得到R的關系圖GR為下面左圖。27第27頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學例4.設關系SA×A，A={a1,a2,a3}，

S={(a1,a1),(a2,a2),(a3,a3),(a1,a3),(a3,a1),(a2,a3),(a3,a2)}

于是，我們得到S的關系圖GS為上面右圖。注：圖中各結點所帶的小圓圈稱為自反圈；一對結點間的來回邊稱為雙向弧；否則，一對結點間只有一條邊，則此邊稱為單向弧。關系的表示法有三種:集合表示法,矩陣表示法,圖形表示法。a1a2a3a4b1b2b3RABGRa1a2a3GS28第28頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

二.關系的性質

設二元關系RX×X(或者說RX2)，這里X是一集合。則R稱為是X上的

1°自反關系(reflexiverelation)：當且僅當R滿足自反性：(xX)(xRx)

；顯然，對于自反關系R，

(R)=

(R)=

X

。反自反關系(irreflexiverelation)：當且僅當R滿足

反自反性：(xX)(

)

或(xX)(xRx)

；常見的自反關系有相等關系(=)，小于等于關系()，包含關系()等；而不相等關系()，小于關系()，真包含關系()等都不是自反關系，它們都是反自反關系。29第29頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學注：自反性和反自反性是關系的兩個極端性質；因此，自反關系和反自反關系是兩種極端關系；

從關系矩陣來看：自反關系關系矩陣的對角線上元素全是1；反自反關系關系矩陣的對角線上元素全是0；從關系圖來看：自反關系關系圖的各結點上全都有自反圈；反自反關系關系圖的各結點上全都沒有自反圈。例5.設X={a,b,c,d}。則關系

R1={(a,b),(a,a),(b,b),(c,d),(c,c),(d,d)}是X上的自反關系,但不是X上的幺關系,因(a,b),(c,d)R1；而關系

R2={(a,a),(b,b),(c,c),(d,d)}是X上的自反關系,同時也是X上的幺關系；

R3={(a,b),(a,c),(a,d),(c,d)}30第30頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

是X上的反自反關系。注：由此例可知幺關系一定是自反關系，但自反關系不一定是幺關系。

2°對稱關系(symmetricrelation)：當且僅當R滿足對稱性：(xX)(yX)(xRyyRx)

；

3°反對稱關系(antisymmetricrelation)：當且僅當R滿足反對稱性：(xX)(yX)(xRyyRxx=y)

；

常見的對稱關系有相等關系(=)，不相等關系()，同余關系，朋友關系，同學關系，同鄉(xiāng)關系等；而小于等于關系()，包含關系()，上下級關系，父子關系等都不是對稱關系，它們都是反對稱關系。31第31頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學注：對稱性和反對稱性是關系的兩個極端性質；因此，對稱關系和反對稱關系是兩種極端關系；

從關系矩陣來看：對稱關系的關系矩陣是對稱矩陣。即xij

=

xji(1i,jn)；反對稱關系的關系矩陣滿足如下性質

xij

=1

xji

=0(1i,jn)；從關系圖來看：對稱關系關系圖的結點間若有弧則都是雙向弧；反對稱關系關系圖的結點間若有弧則都是單向?。焕?.設X={a,b,c}。則關系

R1={(a,b),(b,a)}，R2={(a,a),(b,b)}都是X上的對稱關系；而關系

R3={(a,b),(b,a),(b,c)}不是X上的對稱關系；因(b,c)R3

,但(c,b)R3

。32第32頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學例7.設X={a,b,c}。則關系

R1={(a,a),(a,b),(a,c),(c,b),(c,c)}

是X上的反對稱關系；而關系

R2={(a,a),(a,b),(a,c),(b,a),(c,b)}

不是X上的反對稱關系；因(a,b)R2

且(b,a)R2

,但ab。

4°傳遞關系(transitiverelation)：當且僅當R滿足傳遞性：(xX)(yX)(zX)(xRyyRzxRz)；

反傳遞關系(antisymmetricrelation)：當且僅當R滿足反傳遞性：(xX)(yX)(zX)(xRyyRz

)

；常見的傳遞關系有相等關系(=)，小于等于關系()，包含關系()，整除關系，同余關系，上下級33第33頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學關系，同鄉(xiāng)關系，后裔關系等；而不相等關系()，父子關系，朋友關系，同學關系等都不是傳遞關系。注：傳遞性和反傳遞性是關系的兩個極端性質；因此，傳遞關系和反傳遞關系是兩種極端關系；

概念反傳遞性和反傳遞關系一般不甚用，所以不加討論；例8.設X={a,b,c,d}。則關系

R1={(a,b),(b,c),(a,c),(c,d),(a,d),(b,d)}

是X上的傳遞關系；而關系

R2={(a,b),(b,c),(a,c),(c,d),(a,d)}

不是X上的傳遞關系；因(b,c)R2且(c,d)R2，但(b,d)R2

。34第34頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學例9.設X是平面上直線的集合。平行關系

R={(x,y):xXyXx∥y}

由平面幾何的知識知:若x∥y且y∥z，則x∥z

。

由傳遞關系的定義知R是X上的傳遞關系。例10.設X是平面上三角形的集合。相似關系

R={(x,y):xXyXx∽y}

由平面幾何的知識知:若x∽y

且y∽z

，則x∽z

。

由傳遞關系的定義知R是X上的傳遞關系。例11.相等關系是自反的、對稱的、反對稱的、傳遞關系。全關系X2是自反的、對稱的、傳遞的。

幺關系I是自反的、對稱的、反對稱的、傳遞的。

35第35頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學空關系是反自反的、對稱的、反對稱的、傳遞的。36第36頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

§4.關系的運算

1°關系的逆運算定義1.逆運算(converseoperation)設A，B是兩個非空的集合。我們稱一元運算

:2A×B2B×A對任何二元關系RA×B，使得

={(b,a):bBaAaRb}B×A為關系的逆運算；稱是R的逆關系(converseofrelation)。顯然，對任何(b,a)B×A，baaRb；并且。37第37頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學例1.設A={a,b,c}，B={1,2}。則關系R={(a,1),(a,2),(b,2),(c,1)}的逆關系

={(1,a),(2,a),(2,b),(1,c)}。定理1.逆運算基本定理

設兩個關系R

A×B，SA×B，這里

A,B是兩個非空的集合。則有

(1)反身律：=R；

(2)保序性：RS

；

R=S

=；

(3)分配律：RS=

（逆對并的）；

(4)分配律：RS=（逆對交的）；

(5)X×Y=Y×X；

38第38頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

(6)=；

(7)交換律：(R)=()

（逆與余的）；

(8)分配律：R\S=\（逆對差的）；[證].只證(1)，(4)，(7)（采用邏輯法）

(1)對任何(a,b)A×B，有

(a,b)(b,a)(a,b)R

所以=R。

(4)對任何(a,b)B×A，有

(a,b)RS

(b,a)RS39第39頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學(b,a)R(b,a)S

(a,b)(a,b)(a,b)

所以RS=。

(7)對任何(a,b)B×A，有

(a,b)(R)(b,a)R(b,a)R(a,b)(a,b)()

所以(R)=()。40第40頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學2°關系的合成運算定義2.合成運算(compositionoperation)設A，B是兩個非空的集合。我們稱二元運算

o

:2A×B×

2B×C2A×C

對任何兩個二元關系RA×B，SB×C，使得RoS={(a,c):

aAcC(bB)(aRbbSc)}A×C為關系的合成運算；稱RoS是R與S的合成關系。顯然，對任何(a,c)A×C，aRoSc(bB)(aRbbSc)。例2.設A={a1,a2,a3}，B={b1,b2}，C={c1,c2,c3,c4}

關系RA×B，SB×CR={(a1,b1),(a2,b2),(a3,b1)}S={(b1,c4),(b2,c2),(b2,c3)}41第41頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

于是，我們得到R與S的合成關系為

RoS={(a1,c4),(a2,c2),(a2,c3),(a3,c4)}

其合成關系的關系圖為例3.設A是老年男子的集合，B是中年男子的集合，C是青少年男子的集合。

R是由A到B的父子關系，RA×Bb1b2Ba1a2a3Ac1c2c3c4CRSRoS42第42頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學S是由B到C的父子關系，

SB×C

則復合關系RoS是A到C的祖孫關系。定理2.合成運算基本定理設R,R1,R2

A×B，S,S1,S2

B×C，TC×D，這里A,B,C,D是四個非空的集合。則

(1)Ro

=oS=；

(2)(RoS)(R)；(RoS)(S)；

(3)保序性：R1

R2

S1

S2

R1

oS1

R2

oS2

；

(4)結合律：Ro(SoT)=(RoS)oT；

(5)左分配律：Ro(S1∪S2)=(RoS1)∪(RoS2)；

(合成運算對并的)右分配律：(S1∪S2)oT=(S1

oT)∪(S2

oT)；

(合成運算對并的)(6)左分配不等式：Ro(S1∩S2)(RoS1)∩(RoS2)；43第43頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

(合成運算對交的)

右分配不等式：(S1∩S2)oT(S1

oT)∩(S2

oT)；

(合成運算對交的)

(7)鞋襪律：(RoS)=S

oR。[證].只證(4)，(5)（采用邏輯法）

(4)對任何元素aA,dD，有

aRo(SoT)d

(bB)(aRbb(SoT)d)(bB)(aRb(cC)(bSccTd))(bB)(cC)(aRb(bSccTd))

(量詞前移：pxA(x)x(pA(x)))(cC)(bB)(aRb(bSccTd))(量詞交換：xyA(x,y)yxA(x,y))44第44頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

(cC)(bB)((aRbbSc)cTd)(的結合律：p(qr)(pq)r)(cC)((bB)(aRbbSc)cTd)(量詞后移：x(pA(x))pxA(x))(cC)(a(Ro

S)ccTd)a(Ro

S)oTd

所以Ro(SoT)=(RoS)oT；

(5)對任何元素aA,cC，有

aRo(S1∪S2)c

(bB)(aRbb(S1∪S2)c)(bB)(aRb(bS1cbS2c))(bB)((aRbbS1c)(aRbbS2c))

(對的分配律：p(qr)(pq)(pr))45第45頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

(bB)(aRbbS1c)(bB)(aRbbS2c)(量詞對的分配律：x(A(x)B(x))x(A(x)xB(x))

a(RoS1)ca(RoS2)ca(RoS1)∪(RoS2)c所以Ro(S1∪S2)=(RoS1)∪(RoS2)。

但是合成運算不滿足交換律。即，一般

RoSSoR例4.設A={a,b,c,d,e}。則關系

R={(a,b),(c,d),(b,b)}，S={(b,e),(c,a),(a,c),(d,b)}的合成關系為46第46頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

RoS={(a,e),(b,e),(c,b)}，SoR={(a,d),(c,b),(d,b)}

所以RoSSoR。

3°關系矩陣的合成運算設RA×B，SB×C

是兩個二元關系，其合成關系為RoS。這里A={a1,a2,,am}，B={b1,b2,,bl}，C={c1,c2,,cn}。并設它們的關系矩陣分別為

MR=(xij)m×l，MS=(yij)l×n，MRoS=(uij)m×n則我們有：

MRoS=MRoMS

其中：我們令MRoMS=(tij)m×n

tij=(xikykj)(1im,1jn)47第47頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學注：這里關系矩陣的合成運算與《線性代數(shù)》中的一般矩陣的乘法運算頗為相似。所不同的是：乘法現(xiàn)在換成布爾乘()；加法現(xiàn)在換成布爾加()。值得注意的是：這里的布爾加11=1（不進位），而非11=0（進位）。例5.設A={a,b,c,d,e}。則關系

R={(a,b),(c,d),(b,b)}，S={(b,e),(c,a),(a,c),(d,b)}的合成關系

RoS={(a,e),(b,e),(c,b)}其關系矩陣分別為

MR=

MS=

MRoS=48第48頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

現(xiàn)在我們計算

MRoMS==

其中：

t25=

(x2kyk5)

=(x21y15)(x22y25)(x23y35)(x24y45)(x25y55)=(00)(11)(00)(00)(00)=01000=1

這說明MRoS=MRoMS

。下面我們就來證明這個等式：[證].（采用邏輯法）49第49頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

對任何的i

，j(1im,1jn)，有

uij=1

aiRoScj

(bB)(aiRbbScj)(aiRb1

b1Scj)(aiRb2

b2Scj)(aiRblblScj)(xi1=1

y1j=1)(xi2=1

y2j=1)(xil

=1

ylj=1)(這里：是命題的真值聯(lián)結詞‘且’；

是命題的真值聯(lián)結詞‘或’。)(xi1y1j)(xi2y2j)(xil

ylj)=1(這里：是布爾乘；是布爾加。)(xikykj)=1

tij=1

即uij=tij

因此(uij)m×n=(tij)m×n

所以MRoS=MRoMS

。50第50頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學4°關系的閉包運算（宏運算）定義3.關系的合成冪(nthpower)設二元關系RA×A，nN。這里A是一個非空的集合，N

是自然數(shù)集。我們規(guī)定：

(1)R0=I（這里I=IA={(a,a):

aA}是A上的幺關系）；

(2)R1=R；

(3)Rn+1=RnoR(特別地：R2=RoR)。定理3.指數(shù)律設二元關系RA×A，m,nN。這里A是一個非空的集合，N

是自然數(shù)集。則

(1)交換律：RmoRn

=

RnoRm=Rm+n；特別地：IoR=

RoI=R(幺關系是合成運算的幺元)；

(2)交換律：(Rm)n

=(Rn)m=Rmn。

51第51頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學[證].（采用數(shù)學歸納法）

只證(1)的一個等式：RmoRn

=

Rm+n；另一個等式：RnoRm=Rm+n同理可證。歸納變量選取n（讓m固定）

n=0時，RmoR0

=RmoI(定義3的(1)：R0=I)=Rmn=1時，RmoR1

=RmoR(定義3的(2)：R1=R)

=Rm+1(定義3的(3))

結論成立；

n=k時，假設結論成立。即RmoRk

=

Rm+k；

n=k+1時，RmoRk+1=Rmo(RkoR)(定義3的(3))

=(RmoRk)oR(結合律)=Rm+koR(歸納假設)

=Rm+k+1(定義3的(3))52第52頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

結論成立；

根據(jù)數(shù)學歸納法，即證明了該結論。例6.設二元關系RA×A,這里A={a,b,c},R={(a,b),(c,b)}。從而有

I={(a,a),(b,b),(c,c)}，={(b,a),(b,c)}

oR={(b,b)}，Ro={(a,a),(a,c),(c,a),(c,c)}

于是oRI

，Ro

I

，oRRo

。

注：

這個例子說明一般情況下逆關系不是關系合成運算的逆元；

由定理2的(1)有：oR=Ro

=，這說明空集是合成運算的零元。一般地aRnb(c1)(c2)(cn-1)(aRc1c1Rc2cn-1Rb)

；特別地aR２b(c)(aRccRb)。53第53頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學定義4.閉包運算(closureoperation)設二元關系RA×A。這里A是一個非空的集合。我們定義：

(1)傳遞閉包(transitiveclosure)：

R＋=

Rk=R∪R２∪R3∪∪Rk∪

；

(2)自反傳遞閉包(reflexiveandtransitiveclosure)：

R

=

Rk=I∪R∪R２∪R3∪∪Rk∪

。ac1c2bcn-1cn-2RnRRRRRabcR２RR54第54頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學注：傳遞閉包有時也記為t(R)；自反傳遞閉包有時也記為rt(R)；其實還有別的閉包；

aR＋b(kN)(k1)(aRkb)；

aR

b(kN)(aRkb)(a=b)(kN)(k1)(aRkb)(a=b)(aR＋b)。定理4.傳遞閉包基本定理設二元關系RA×A，R。則

(1)若mN，m1，則RmR＋

；特別地R

R＋

；

(2)R＋是傳遞關系：即，對任何元素a，b，cA，

aR＋bbR＋caR＋c；

(3)R＋是包含R的最小傳遞關系：即，對任何二元關系SA×A，若RS且S也是傳遞關系，那么R＋S；

(4)若|A|=n，則R＋=

Rk

；這時55第55頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

aR＋b(kN)(1kn)(aRkb)；

(5)若R是傳遞關系,

則R＋=R。[證].只證(2)(采用邏輯法)(2)對任何元素a，b，cA，有

aR＋bbR＋c

(k)(aRkb)(l)(bRlc)(這里k1,l1)(x1)(x2)(xk-1)(aRx1x1Rx2xk-1Rb)(y1)(y2)(yl-1)(bRy1y1Ry2yl-1Rc)

(x1)(x2)(xk-1)(aRx1x1Rx2xk-1Rb(y1)(y2)(yl-1)(bRy1y1Ry2yl-1Rc))(量詞前移：xA(x)px(A(x)p))(x1)(x2)(xk-1)(y1)(y2)(yl-1)(aRx1x1Rx2xk-1RbbRy1y1Ry2yl-1Rc)56第56頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

(量詞前移：pxA(x)x(pA(x)))(x1)(x2)(xk-1)(xk)(xk+1)(xk+2)(xk+l-1)(aRx1

x1Rx2xk-1RxkxkRxk+1xk+1Rxk+2xk+l-1Rc)(這里，我們令：xk=b,xk+1=y1,xk+2=y2,,xk+l-1=yl-1)(n)(aRnc)(這里，我們令：n=k+l1+11)aR＋c所以，R＋是傳遞的。定理5.自反傳遞閉包基本定理設二元關系RA×A，R。則

(1)若mN，則RmR*

；特別地IR*，

R

R*

；

(2)R*是自反傳遞關系：即，對任何元素aA，

aR*a；

57第57頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

對任何元素a，b，cA，

aR*bbR*caR*c；

(3)R*是包含R的最小自反傳遞關系：即，對任何二元關系SA×A，若RS且S也是自反傳遞關系，那么R*S；

(4)若|A|=n，則R*=

Rk

；這時

aR*b(kN)(0kn)(aRkb)(a=b)(kN)(1kn)(aRkb)；

(5)若R是自反傳遞關系,

則R*=R。[證].只證(3)（采用邏輯法）

(3)對任何元素a，bA，有

aR*b

(a=b)(k)(aRkb)(這里k1)58第58頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學(a=b)(x1)(x2)(xk-1)(aRx1x1Rx2xk-1Rb)aSb(x1)(x2)(xk-1)(aSx1x1Sx2xk-1Sb)(S是自反的且RS)aSbaSb(S是傳遞的且xpp)aSb(冪等性：ppp)

所以R*S。59第59頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學

§5.

等價關系

1°等價關系和等價類定義1.等價關系(equivalencerelation)

設二元關系RA×A。這里A是非空的集合。

R是A上的等價關系R是自反的、對稱的、傳遞的。顯然(R)=(R)=A

(因為等價關系是自反的)；例1.同鄉(xiāng)關系是等價關系。例2.平面幾何中的三角形間的相似關系是等價關系。例3.平面幾何中的三角形間的全等關系是等價關系。60第60頁，課件共105頁，創(chuàng)作于2023年2月離散數(shù)學例4.平面幾何中的直線間的平行關系是等價關系。例5.設N是自然數(shù)集，m是一正整數(shù)，

R={(a,b):aNbNab(modm)}由等價關系的定義知R是N上等價關系；我們稱R是N上的模m同余關系。例6.非空集合A上的幺關系、全關系都是等價關系。例7.非空集合A上的空關系不是等價關系(因為空關系不自反)

。例8.設二元關系RA×A,這里

A={a,b,c},R={(a,a),(b,b),(c,c),(b,c),(c,b)}則R是A上的等價關系。其關系圖如下