離散數(shù)學(xué)第四章二元關(guān)系_第1頁
離散數(shù)學(xué)第四章二元關(guān)系_第2頁
離散數(shù)學(xué)第四章二元關(guān)系_第3頁
離散數(shù)學(xué)第四章二元關(guān)系_第4頁
離散數(shù)學(xué)第四章二元關(guān)系_第5頁
已閱讀5頁,還剩47頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1、第四章 二元關(guān)系第四章 二元關(guān)系本章討論的關(guān)系(主要是二元關(guān)系),它仍然是一種集合,但它是比前一章更為復(fù)雜的集合。關(guān)系是笛卡爾乘積的子集,它的元素是有序二元組的形式,這些有序二元組中的兩個元素來自于兩個不同或者相同的集合。因此,關(guān)系是建立在其它集合基礎(chǔ)之上的集合。關(guān)系中的有序二元組反映了不同集合中元素與元素之間的關(guān)系,或者同一集合中元素之間的關(guān)系。本章首先討論關(guān)系的基本表達形式,然后給出關(guān)系的運算,最后討論幾種常用的關(guān)系。 回顧主要內(nèi)容關(guān)系的基本概念關(guān)系的性質(zhì)關(guān)系的表示關(guān)系的運算合成關(guān)系的關(guān)系圖、關(guān)系矩陣特殊關(guān)系:等價關(guān)系和劃分,相容關(guān)系和覆蓋,偏序關(guān)系和哈斯圖等。 4.1關(guān)系的基本概念定義:

2、設(shè) 且 A1,A2,An為n個任意集合,(a) 稱R為A1,A2,An間的n元關(guān)系;(b) 若n=2,則稱R為A1到A2的二元關(guān)系;(c) 若 ,則稱R為空關(guān)系;若 ,則稱R為全關(guān)系;(d) 若A1=A2=An =A,則稱R為A上的n元關(guān)系。一、關(guān)系的定義一、關(guān)系的定義例:令則稱R1是N上的一元關(guān)系,R2是N上的二元關(guān)系,R3是N上的三元關(guān)系。如無特殊指定,“關(guān)系”概指二元關(guān)系。若序偶 屬于R,則記作 或 ,否則,記作 或 。一、關(guān)系的定義例:設(shè)集合A=a,b,B=2,5,8則令則 均是由A到B的關(guān)系。同理,則 是由B到A的關(guān)系。同理,則 是由B到B的關(guān)系。一、關(guān)系的定義例:設(shè)集合A=2,3,

3、5,9,試給出集合A上的小于或等于關(guān)系,大于或等于關(guān)系。解:令集合A上的小于或等于關(guān)系為R1,大于或等于關(guān)系為R2,根據(jù)定義有: 二、關(guān)系的相等定義:設(shè)R1為A1,A2,An間的n元關(guān)系,R2為B1, B2,Bm間的m元關(guān)系,如果:(1)n=m (2)若 1in,則Ai=Bi(3)把R1和R2作為集合看,R1=R2。則稱n元關(guān)系R1和m元關(guān)系R2相等,記作R1=R2二、關(guān)系的相等例:設(shè)R1為從Z到I+的二元關(guān)系,R2和R3都是I上的二元關(guān)系從集合的觀點來看,R1=R2=R3。但是就二元關(guān)系來說,R2=R3,不等于R1。三、關(guān)系的定義域和值域關(guān)系R(從A到B的關(guān)系)的定義域(簡稱為域)定義為:關(guān)

4、系R的值域定義為:顯然,有例:設(shè)A=2,3,5,B=2,6,7,8,9,由A到B的關(guān)系R定義為:當(dāng)且僅當(dāng)a整除b時,有aRb。可得:D(R)=2,3R(R)=2,6,8,9AB235268974.2關(guān)系的表示定義:設(shè)A和B為任意的非空有限集,R為任意一個從A到B的二元關(guān)系。以 中的每個元素為結(jié)點對每個 皆畫一條從x到y(tǒng)的有向邊,這樣得到的一個圖稱為關(guān)系R的關(guān)系圖。 一、關(guān)系圖例:A=1,2,4; B=3,5,6;關(guān)系R=,A124B356一、關(guān)系圖例:設(shè)A=2,3,4,5,6,B=6,7,8,12,從A到B的二元關(guān)系R為 ,畫出其關(guān)系圖。解:先求出R一、關(guān)系圖 對稱關(guān)系 反對稱關(guān)系二、關(guān)系矩陣

5、定義: 給定兩個有限集合X=x1,x2,xm和Y= y1,y2,yn,R是從X到Y(jié)的二元關(guān)系,如果有: 則稱 是R的關(guān)系矩陣,記作MR。 例:設(shè)A=1,2,3,4,R為定義在A上的二元關(guān)系,R=,,寫出關(guān)系矩陣。二、關(guān)系矩陣例:設(shè)A=1,2,3,B=a,b,c, R是A到B的二元關(guān)系,并且 ,試畫出R的關(guān)系圖,給出關(guān)系矩陣。二、關(guān)系矩陣如果關(guān)系矩陣主對角線上的記入值全為1,則R是自反的; 如果主對角線上的記入值全為0,則R是反自反的; 如果矩陣關(guān)于主對角線是對稱的,則R是對稱的;如果矩陣關(guān)于主對角線是反對稱的,(亦即rij=1時則一定有rji=0),則R是反對稱的;如果對于任意的i,j,k,

6、rij=1并且rjk=1時一定有rik=1 ,則R是可傳遞的; 如果存在i,j,k, rij=1并且rjk=1時,有rik 不等于1 ,則R是不可傳遞的;4.3關(guān)系的性質(zhì)定義:設(shè)R為A上的二元關(guān)系(1)若對每個 ,皆有 ,則稱R為自反的。用式子來表述即是: R是自反的 (2)若對每個 ,皆有 ,則稱R為反自反的。用式子來表述即是: R是反自反的 關(guān)系的性質(zhì)(3) 對任意的 ,若 ,則 ,就稱R為對稱的。用式子來表述即是: R是對稱的 (4) 對任意的 ,若 且 , 則x=y,就稱R為反對稱的。用式子來表述即是: R是反對稱的 關(guān)系的性質(zhì)(5) 對任意的 ,若 且 , 則 ,就稱R為可傳遞的。用

7、式子來表述即是: R是可傳遞的 (6) 存在 ,并且 而 , 就稱R為不可傳遞的。用式子來表述即是: R是不可傳遞的 關(guān)系的性質(zhì)例1:考慮自然數(shù)集合上的普通相等關(guān)系“=”,大于關(guān)系“”和大于等于關(guān)系“ ”具有的性質(zhì)。 解:(1) “=”關(guān)系是自反的、對稱的、反對稱的、可傳遞的;(2)“”關(guān)系是反自反的、反對稱的、可傳遞的;(3)“ ”關(guān)系是自反的、反對稱的、可傳遞的。例2:空集上的二元關(guān)系的性質(zhì)。自反的、對稱的、反對稱的、反自反的、可傳遞的 區(qū)分概念:空關(guān)系vs空集上的關(guān)系空關(guān)系:對于任何集合A, 稱空集為A上的空關(guān)系.性質(zhì):若A非空,空關(guān)系是反自反的,對稱的,反對稱的,可傳遞的;若A是空集,

8、該空關(guān)系是自反的,反自反的,對稱的,反對稱的,可傳遞的空集上的關(guān)系:自反的,反自反的,對稱的,反對稱的, 可傳遞的。在空集上可定義任意元關(guān)系。集合的壓縮和開拓定義:設(shè)R為集合A上的二元關(guān)系且SA ,則稱S上的二元關(guān)系R(SS)為R在S上的壓縮,記為R|S, 并稱R為R|S在A上的開拓。 定理:設(shè)R為A的二元關(guān)系且 ,那么:(1)若R是自反的,則 也是自反的; (2)若R是反自反的,則 也是反自反的; (3)若R是對稱的,則 也是對稱的; (4)若R是反對稱的,則 也是反對稱的; (5)若R是可傳遞的,則 也是可傳遞的; 4.4關(guān)系的運算注意:由于關(guān)系也是特殊的集合,因此集合的運算也適用于關(guān)系中

9、。設(shè)R1和R2是從A到B的二元關(guān)系,那么R1R2, R1R2 , R1-R2, R1R2也是從A到B的二元關(guān)系,它們分別被稱為二元關(guān)系R1和R2的交、并、差分和對稱差分。4.4關(guān)系的運算例:設(shè)集合A=a,b,c,B=d,e,定義A到B的二元關(guān)系R1=,R2=,則4.4關(guān)系的運算定義:設(shè)R是從X到Y(jié)的關(guān)系,S是從Y到Z的關(guān)系,于是可用RS表示從X到Z的關(guān)系,通常稱它是R和S的合成關(guān)系,用式子表示即是: 一、關(guān)系的合成例: 給定集合X=1,2,3,4,Y=2,3,4和Z=1,2,3。設(shè)R是從X到Y(jié)的關(guān)系,并且S是從Y到Z的關(guān)系,并且R和S給定成: 試求R和S的合成關(guān)系,并畫出合成關(guān)系圖給出合成關(guān)系

10、的關(guān)系矩陣。 一、關(guān)系的合成解:找出所有這樣的偶對 x, z 對于某一個y來說,能有x+y=6和y-z=1,由上述的偶對就可構(gòu)成從X到Z的關(guān)系RS 。 一、關(guān)系的合成定義布爾運算:0+0=0,1+0=0+1=1+1=111=1, 01= 10= 00=0對兩個關(guān)系矩陣求其合成時,其運算法則與一般矩陣的乘法是相同的,但其中的加法運算和乘法運算應(yīng)改為布爾加和布爾乘。一、關(guān)系的合成注意:設(shè)R是從集合X到集合Y的關(guān)系,S是從集合Y到集合Z的關(guān)系,于是有:如果R關(guān)系的值域與S關(guān)系的定義域的交集是個空集,則合成關(guān)系RS也是個空關(guān)系;若至少有一個序偶 x, yR ,其中笫二個成員是S中的某一個序偶的笫一個成

11、員,則合成關(guān)系就是個非空關(guān)系。對于合成關(guān)系RS來說,它的定義域是集合X的子集,而它的值域則是Z的子集,事實上,它的定義域是關(guān)系R的定義域的子集,它的值域是關(guān)系S的值域的子集。 一、關(guān)系的合成定理:給定集合X,Y,Z和W,設(shè)R1是從 X到Y(jié)的關(guān)系,R2和R3是Y到Z的關(guān)系,R4是從Z到W的關(guān)系,于是有:一、關(guān)系的合成證明:當(dāng)且僅當(dāng)存在某一個yY,能使 R1和 R2 R3 ,才有 R1 (R2 R3),而 對任意的x,zR1o(R2R3)y(x,yR1y,zR2R3)y(x,yR1(y,zR2 y,zR3) y(x,yR1y,zR2) (x,yR1 y,zR3) y(x,yR1y,zR2) y(x

12、,yR1y,zR3) x,zR1oR2 x,zR1oR3 x,z(R1oR2)(R1oR3) 得證一、關(guān)系的合成證明:當(dāng)且僅當(dāng)存在某一個yY ,能使 R1和 R2 R3 ,才有 R1 (R2 R3) ,而 對以上證明過程(a)式使用的是存在量詞對滿足分配律對(b)存在量詞對不滿足分配律,但它滿足蘊涵式x(A(x) B(x)xA(x) x B(x)這里應(yīng)注意是一、關(guān)系的合成合成運算是對關(guān)系的二元運算,使用這種運算,能夠由兩個關(guān)系生成一個新的關(guān)系,對于這個新的關(guān)系又可進行合成運算,從而生成其它關(guān)系。 定理:設(shè)R1是從X到Y(jié)的關(guān)系,R2是從Y到Z的關(guān)系,R3是從Z到W的關(guān)系,于是有一、關(guān)系的合成一、

13、關(guān)系的合成例:給定關(guān)系R和S,并且則關(guān)系的冪定義:如果R1是從X1到X2的關(guān)系,R2是從X2到的X3關(guān)系,Rn是從Xn到Xn+1的關(guān)系,則無括號表達式 表達了從X1到Xn+1的關(guān)系。當(dāng)X1=X2=Xn+1和R1=R2 =Rn時,也就是說當(dāng)集合X中的所有Ri都是同樣的關(guān)系時,X中的合成關(guān)系 可表達成Rn,并稱作關(guān)系R的冪。 定義:給定集合X,R是X中的二元關(guān)系。設(shè) ,于是R的n次冪Rn可定義成 (a) R0是集合X中的恒等關(guān)系IX,亦即(b) 關(guān)系的冪定理:給定集合X,R是X中的二元關(guān)系。設(shè) ,于是可有 例:給定集合X=a,b,c,R1,R2,R3,R4是X中的關(guān)系,并給定給出這些關(guān)系的各次冪關(guān)

14、系的冪解:關(guān)系的冪定理:設(shè)X是含有n個元素的有限集合,R是X中的二元關(guān)系。于是存在這樣的s和t,能使 , 證明:集合X中的每一個二元關(guān)系都是 的子集,X有n個元素, 有n2個元素, 有 個元素,每一個元素都是 的一個子集,也是一種二元關(guān)系,因而,在X中有 個不同的二元關(guān)系。所以,不同的二元關(guān)系R的冪不會多于個 。但是序列 中有 項,因此這些的方冪中至少有兩個是相等的。證畢。 二、合成關(guān)系的矩陣表達和圖解設(shè)集合X=x1,x2,xm,Y=y1,y2 ,yn,Z=z1,z2,zp, R是從X到Y(jié)的關(guān)系,S是從Y到Z的關(guān)系,MR和MS第i行第j列的元素分別是aij和bij,它們是0或者1。則合成關(guān)系

15、關(guān)系矩陣上的元素為定義布爾運算:0+0=0,1+0=0+1=1+1=111=1, 01= 10= 00=0對兩個關(guān)系矩陣求其合成時,其運算法則與一般矩陣的乘法是相同的,但其中的加法運算和乘法運算應(yīng)改為布爾加和布爾乘。二、合成關(guān)系的矩陣表達和圖解例:求合成關(guān)系 的關(guān)系矩陣二、合成關(guān)系的矩陣表達和圖解當(dāng)用 表示這些矩陣的合成矩陣二、合成關(guān)系的矩陣表達和圖解例:設(shè)集合X=0,1,2,3,R是X中的關(guān)系,并且畫出 和 的關(guān)系圖解:0231(a)0231(b)0231(c)三、關(guān)系的求逆運算關(guān)系R的逆關(guān)系 定義如下:對于所有的 和 來說,逆關(guān)系的關(guān)系矩陣:原關(guān)系矩陣轉(zhuǎn)置逆關(guān)系的關(guān)系圖:原關(guān)系圖中顛倒弧線上箭頭的方向。區(qū)分 :逆關(guān)系vs補關(guān)系 在關(guān)系圖和關(guān)系矩陣上的體現(xiàn)?三、合成關(guān)系的求逆運算定理:設(shè)R是從集合X到Y(jié)的關(guān)系。S是從集合Y到Z的關(guān)系。于是有 證明:對于任何 , 和 來說,如果xRy和ySz,則會有 和 ,因為還有 和 ,所以又有 。因此可有 。利用關(guān)系矩陣也可以理解, 的轉(zhuǎn)置和 是一樣的。三、合成關(guān)

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論