[文學(xué)]第6章關(guān)系課件

1、 第六章 關(guān)系內(nèi)容簡(jiǎn)介 次序關(guān)系 關(guān)系及其性質(zhì) 關(guān)系的運(yùn)算 劃分和等價(jià)關(guān)系 4.1 4.24.34.4關(guān)系：描述兩個(gè)或多個(gè)對(duì)象間的相互聯(lián)系。離散數(shù)學(xué)：對(duì)關(guān)系的共性進(jìn)行研究，不關(guān)系關(guān)系的具體含義，1.【定義：二元關(guān)系】任意有序偶的集合稱為二元關(guān)系，記作R。從X到Y(jié)的關(guān)系滿足RXY。若R，則稱x與y有關(guān)系R，記作xRy；若R，則稱x與y沒有關(guān)系R，記作xRy；對(duì)任意xX，yY，有且僅有兩種情況之一： x與y有關(guān)系R；x與y沒有關(guān)系R。例1：R=x,yN，xy 這是自然數(shù)集合上的一個(gè)“大于”關(guān)系，顯然R,即：3R2。4.1 關(guān)系及其性質(zhì)4.1 關(guān)系及其性質(zhì)例2: 設(shè) A=a1,a2, B=b, 則

2、A到B的二元關(guān)系共有4個(gè): R1=, R2=, R3=, R4=,. B到A的二元關(guān)系也有4個(gè): R5=, R6=, R7=, R8=,. 【補(bǔ)充定義】 AB的任何一個(gè)子集所定義的一個(gè)二元關(guān)系R，稱從A到B的二元關(guān)系。當(dāng)A=B時(shí)，稱之為A上的二元關(guān)系。例3：A=a,b,c B=1,2,3 R1=, 是A到B的一個(gè)二元關(guān)系 R2=, 是B上的一個(gè)二元關(guān)系4.1 關(guān)系及其性2. 特殊的二元關(guān)系1全域關(guān)系：集合XY稱為X上的全域關(guān)系，記作Ux。 Ux=xi,xjX2空關(guān)系：作為XY的子集的空集，稱為X上的空關(guān)系。3恒等關(guān)系：Ix=xiX例4. X=a,b,cUx = ? Ix = ? 3.【定義6.

3、2】關(guān)系R中所有有序偶的第一元素的集合稱為關(guān)系R的定義域，記作Dom(R)；第二元素的集合稱為關(guān)系R的值域，記作Ran(R)；二者統(tǒng)稱為域，記作fld(R)。若R是A到B的關(guān)系，則Dom(R)A；Ran(R)B。 4.1 關(guān)系及其性質(zhì)ABRan(R) dom(R) 4.1 關(guān)系及其性質(zhì)例5. R1=a,b, R2=a,b, R3=,.當(dāng)a,b不是有序?qū)r(shí), R1和R2不是關(guān)系.dom(R3)=1,3,5, ran(R3)=2,4,6,Fld(R3)=1,2,3,4,5,6.例6. 實(shí)數(shù)間的大于關(guān)系：=x,yR,xy4.1 關(guān)系及其性質(zhì)例7. 整除關(guān)系：設(shè)B=1,2,3,4,5,6，定義B上的二

4、元關(guān)系, DB=a,bB,baN。DB=,例8.模2同余關(guān)系：A=1,2,3,4，定義A上的二元關(guān)系R=( a-b)/2Z,a,bA，則R=, 說明：此關(guān)系稱為“模2同余關(guān)系”記作a=b(mod2),類似有“模3同余”模4同余等” 4.1 關(guān)系及其性質(zhì)4.關(guān)系矩陣：設(shè)集合A=a1, ,am,B=b1bn。若R是A到B的關(guān)系，則R的關(guān)系矩陣是一個(gè)mn階的矩陣：MR=(rij)mn 若R是A上的關(guān)系，則其關(guān)系矩陣是一個(gè)方陣。例9. A=a,b,c,d， B=x,y,z， A=4，B=3, R=,，則MR是43的矩陣 xyz4.1 關(guān)系及其性質(zhì)5.關(guān)系圖：設(shè)R是集合X=x1,x2,xm上的關(guān)系，R對(duì)

5、應(yīng)的關(guān)系圖由結(jié)點(diǎn)和邊組成.節(jié)點(diǎn)：X集合中的元素稱為頂點(diǎn)，用圓點(diǎn)或小圈表示；邊：若xiRxj，則用一條帶箭頭的弧線連接頂點(diǎn)xi和xj，箭頭指向xj；若xiRxj且xjRxi，則在頂點(diǎn)xi和xj之間畫兩條方向相反的弧線。自環(huán)：若xiRxi，則畫一條從頂點(diǎn)xi出發(fā)，又返回xi的弧線，稱為自環(huán)；當(dāng)R中所有的有序偶處理完畢后，得到關(guān)系R的關(guān)系圖。4.1 關(guān)系及其性質(zhì)例10. A=2,3,4,5,6， RA: a/b素?cái)?shù)的關(guān)系圖如下：例11. A=2,3,4,5,6， RA: a,b互質(zhì)的關(guān)系圖如下：4.1 關(guān)系及其性質(zhì)例12. A=2,3,4,5,6， RA:(a-b)2A 的關(guān)系圖如下： 5.【定義：

6、自反性，對(duì)稱性，傳遞性】設(shè)A為一集合，RAA：1稱R是自反的，如果對(duì)任意的xA有xRx，即： R是自反的 x (xA R)2稱R是反自反的，如果對(duì)任意的xA有x Rx，即： R是反自反的 x (xA R)3稱R是對(duì)稱的，如果對(duì)任意的x, yA，若xRy 則 yRx，即： R是對(duì)稱的 xy(xA yA R R)4稱R是反對(duì)稱的，如果對(duì)任意的x, yA，若xRy且yRx 則x=y, 即： R是反對(duì)稱的 xy(xA yA R R x=y)5稱R是傳遞的，如果對(duì)任意的x, y, z A，若xRy且yRz 則xRz，即：R是傳遞的 xyz(xA yA zA R R R)4.1 關(guān)系及其性質(zhì)例13.A=a

7、,b,c，判斷以下關(guān)系類型R1=,反對(duì)稱,傳遞R2=,反對(duì)稱R3=, 自反,對(duì)稱,傳遞R4=,對(duì)稱(為什么非傳遞)R5=,自反,反對(duì)稱,傳遞4.1 關(guān)系及其性質(zhì)例14.R是實(shí)數(shù)集合上的關(guān)系，具有的特性為：1 關(guān)系“”是自反的，不是反自反的。2 關(guān)系“”是反對(duì)稱的。若xy,且yx,則必有xy。3 關(guān)系“”是傳遞的。若xy,且yz,則必有xz 。思考：R是實(shí)數(shù)集合上的關(guān)系，具有的特性如何？ 其它，如人與人的父子關(guān)系,領(lǐng)導(dǎo)與被領(lǐng)導(dǎo)關(guān)系的特性如何？6. 關(guān)系特性在關(guān)系矩陣和關(guān)系圖上的體現(xiàn)：1自反性：關(guān)系矩陣主對(duì)角線元素均為1；關(guān)系圖每個(gè)頂點(diǎn)上都有自環(huán)。2反自反性：關(guān)系矩陣主對(duì)角線元素均為0；關(guān)系圖任何

8、頂點(diǎn)上都沒有自環(huán)。3對(duì)稱性：關(guān)系矩陣元素對(duì)稱于主對(duì)角線【對(duì)稱矩陣】；關(guān)系圖任意兩個(gè)頂點(diǎn)間要么無弧，要么有兩條方向相反的弧。4反自反性：關(guān)系矩陣中rij和rji(ij)這兩個(gè)數(shù)至多有一個(gè)是1；但允許兩個(gè)均為0；關(guān)系圖任意兩個(gè)頂點(diǎn)之間至多有一條弧(允許是沒有弧)。5傳遞性：若關(guān)系圖某兩個(gè)頂點(diǎn)之間有一條路徑，則這二者之間必有一條?。粌?nèi)容簡(jiǎn)介 次序關(guān)系 關(guān)系及其性質(zhì) 關(guān)系的運(yùn)算 等價(jià)關(guān)系 4.1 4.24.34.44.2 關(guān)系的運(yùn)算關(guān)系是有序?qū)?集合的運(yùn)算對(duì)關(guān)系仍然適用。一. 關(guān)系的復(fù)合運(yùn)算1.【定義】設(shè)R和S是從A到B的兩個(gè)關(guān)系,則RS,RS,R-S,R,RS（R+S）仍是從A到B的關(guān)系。 2.

9、【定義】設(shè)A,B,C是三個(gè)集合,R是A到B的關(guān)系,S是B到C的關(guān)系,則R與S的復(fù)合關(guān)系是一個(gè)A到C的關(guān)系,記作R S。R S = xA,zC,yB,使R,SR S = | y( xRy ySz )xzRSy4.2 關(guān)系的運(yùn)算注意: (1)R的值域所屬集合與S定義域所屬集合交集為空集,則R S = 空集。 (2)有復(fù)合關(guān)系R S的定義為:至少有一個(gè)中間橋梁的元素y,使x,y有關(guān)系R,y,z有關(guān)系S。例1: a,b,c三人；a,b是兄妹關(guān)系；b,c是母子關(guān)系。 則a,c是舅甥關(guān)系。如設(shè)R是兄妹關(guān)系,S是母子關(guān)系，則R與S的復(fù)合T是舅甥關(guān)系；而S與R復(fù)合是母女關(guān)系； 如R是父子關(guān)系,R與R復(fù)合是祖孫

10、關(guān)系。4.2 關(guān)系的運(yùn)算例2:集合A=a,b,c,d,e； R=,； S=, 則R S = , S R = , R R = , S S = 從例中可得R S S R，關(guān)系的復(fù)合運(yùn)算不成立交換律。若R是A到B的關(guān)系，S是B到C的關(guān)系，則R S是有意義，而S R根本不能復(fù)合。若A=C,則R S是A上的關(guān)系，S R是B上的關(guān)系，二者不可能相等；若A=B=C，R,S均為A上的關(guān)系，R S和S R也是A上的關(guān)系, 但一般地 R S S R。4.2 關(guān)系的運(yùn)算3.【定理】設(shè)R、S、T分別是A到B、B到C、C到D的關(guān)系，則(R S) T = R (S T)證明： (R S) T z(R S T) z(s(R

11、 S) T)z s(R S T)s z(R S T)s(R z(S T)s(R S T)R (S T)復(fù)合關(guān)系運(yùn)算滿足結(jié)合率，可以去掉括號(hào)： R （S T）= R （S T）= R S T4.2 關(guān)系的運(yùn)算4.【定義：Rn】設(shè)R是A上的二元關(guān)系，nN,則關(guān)系的n次冪 Rn定義為：(1)R0 =A，是A上的恒等關(guān)系； (2)Rn+1=Rn R說明：如果R是A到B的關(guān)系，且AB，則R2是無意義的。可以用數(shù)學(xué)歸納法證明:（1）Rm Rn=Rm+n (稱第一指數(shù)律）（2）（Rm）n=Rmn (稱第二指數(shù)律）說明：第三指數(shù)律，即（RS）n = RnSn是不成立的。 （RS）2=（RS）（RS） = R（

12、SR）S， R2S2=RRSS=R（RS）S。 所以只要交換律不成立,第三指數(shù)律不成立4.2 關(guān)系的運(yùn)算例3：設(shè)A=1,2,3,4,5，A上關(guān)系R為， R=，則： R0 = A =， R1 = R =， R2 = ， R3 = R2R = ， R4= R3R1=，4.2 關(guān)系的運(yùn)算二.逆關(guān)系1.【定義：逆關(guān)系】設(shè)R是集合A到B的二元關(guān)系，則定義B到A的二元關(guān)系R-1=| R，稱為R的逆關(guān)系，記作R-1R-1就是將所有R中有序?qū)Φ膬蓚€(gè)元素交換次序成為R-1，故|R|=|R-1|R-1的關(guān)系矩陣是R的關(guān)系矩陣的轉(zhuǎn)置，即 MR-1=MRR-1的關(guān)系圖就是將R的關(guān)系圖中的弧改變方向。2.【定理】設(shè)R是

13、A到B的關(guān)系，S是B到C的關(guān)系，則 (R S)-1 = S-1 R-1。復(fù)合關(guān)系的逆等于它們逆關(guān)系的反復(fù)合;（RS）-1 R-1S-1 因R-1是B到A的關(guān)系，S-1是C到B的關(guān)系， S-1R-1是可以復(fù)合的，而R-1S-1是不能復(fù)合。4.2 關(guān)系的運(yùn)算三.關(guān)系的閉包1.【定義：關(guān)系的閉包】設(shè)A ，R A A，R的自反閉包(對(duì)稱閉包、傳遞閉包)R是滿足如下條件的關(guān)系：1 R是自反的（對(duì)稱的、傳遞的）； 2 R R；3 對(duì)于A上的任意自反的(對(duì)稱的、傳遞的)關(guān)系R”，若RR”，則R R”。 【最小性】分別用r(R)、s(R)和t(R)表示R的自反閉包、對(duì)稱閉包和傳遞閉包。4.2 關(guān)系的運(yùn)算例4：

14、設(shè)集合A=a,b,c,A上的關(guān)系R=,，則 自反閉包 r(R)=, 對(duì)稱閉包 s(R)=, 傳遞閉包 t(R)=, 關(guān)系圖r(R)a b ca b cs(R)a b ct(R)a b cRR4.2 關(guān)系的運(yùn)算例5：R=, 求t(R)a能到達(dá)a,c,d,e,則要加,b能到達(dá)b,d,e,則要加,c能到達(dá)e,則要加，這些加入后 才成為t(R) a b c d e4.2 關(guān)系的運(yùn)算2.【定理：自反閉包的構(gòu)建】設(shè)R是非空集A的關(guān)系,則r(R)=RA 證明1 RA是自反的，滿足定義第1條；2 R (RA)，滿足定義第2條；3 證明第3條，最小性 設(shè)R”滿足：R R”，R”是自反的 (RA) 則R 或 A,

15、 如果R, 則由 RR” 可知 R”, 如果A, 則必有a = b,即A, 由R”的自反性, 則R”, 總之 均有R” （RA) R”,滿足第3條.4.2 關(guān)系的運(yùn)算3.【引理】R是在A上的二元關(guān)系,R是對(duì)稱,當(dāng)且僅當(dāng)R=R-14.定理：對(duì)稱閉包構(gòu)建】設(shè)R是非空集A的關(guān)系,則s(R)=R R-1 證明：1 RR-1 R R-1 R-1 R RR-1 RR-1是對(duì)稱的,滿足定義的第1條2 顯然 R RR-1 滿足定義第2條3 若R R”,且R”是對(duì)稱的, RR-1 則R 或 R-1 如 R, 則由RR”, 可知R” 如 R-1， 則R， 可知R” 又因R”對(duì)稱 R” RR-1 R” 則滿足定義第3 4.2 關(guān)系的運(yùn)算例6:設(shè)A=1,2,3,A上的關(guān)系R的關(guān)系圖如圖,寫出關(guān)系R,并求r(R),s(R),t(R)