[文學]第6章關系課件

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

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

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

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

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

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

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

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

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

10、關系。4.2 關系的運算例2:集合A=a,b,c,d,e； R=,； S=, 則R S = , S R = , R R = , S S = 從例中可得R S S R，關系的復合運算不成立交換律。若R是A到B的關系，S是B到C的關系，則R S是有意義，而S R根本不能復合。若A=C,則R S是A上的關系，S R是B上的關系，二者不可能相等；若A=B=C，R,S均為A上的關系，R S和S R也是A上的關系, 但一般地 R S S R。4.2 關系的運算3.【定理】設R、S、T分別是A到B、B到C、C到D的關系，則(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)復合關系運算滿足結合率，可以去掉括號： R （S T）= R （S T）= R S T4.2 關系的運算4.【定義：Rn】設R是A上的二元關系，nN,則關系的n次冪 Rn定義為：(1)R0 =A，是A上的恒等關系； (2)Rn+1=Rn R說明：如果R是A到B的關系，且AB，則R2是無意義的?？梢杂脭祵W歸納法證明:（1）Rm Rn=Rm+n (稱第一指數律）（2）（Rm）n=Rmn (稱第二指數律）說明：第三指數律，即（RS）n = RnSn是不成立的。 （RS）2=（RS）（RS） = R（

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

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

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

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