《離散數(shù)學(xué)-二元關(guān)系與運算-專業(yè)數(shù)學(xué)教材.ppt》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)-二元關(guān)系與運算-專業(yè)數(shù)學(xué)教材.ppt（61頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、二元關(guān)系和運算,第四章,1. 二元有序組：由兩個元素x和y按一定順序排成二元組，記作： 。,4.1 二元關(guān)系的概念,如： 平面直角坐標(biāo)系中點的坐標(biāo),一、二元關(guān)系的概念,二元有序組的性質(zhì),(1) 當(dāng)x y時， ,(2) = ，當(dāng)且僅當(dāng)x = u，y = v,(1)、(2)說明有序組區(qū)別于集合,n元有序組：由n個元素x1，x2，，xn，按一定順序排成的n元組，記作：(x1，x2，，xn) 。,2. 一種新的集合運算 積運算 ：,設(shè)A、B為兩集合，用A中元素為第一元素，B中元素作為第二元素構(gòu)成的二元有序組的全體叫做A和B的笛卡兒積。,記作：A B,符號化：A B = | xA y B,例4.1 設(shè)A
2、=a,b，B=0,1,2 ，求AB，BA,解：根據(jù)笛卡兒積的定義知,A B = , , , ,B A = , , ,一般地：如果|A|=m，|B|=n，則 |AB|=|BA|=m n,, , ,, ,,, ,積運算的性質(zhì),(1) 若A，B中有一個空集，則笛卡兒積是空集，即： B = A = ,(2) 當(dāng)AB，且A，B都不是空集時，有ABBA,(3) 當(dāng)A，B，C都不是空集時，有(AB)C A(BC),因為(AB)C中的元素, z，而A(BC)中的元素為 。,(4) A(BC) = (AB)(AC) (對的分配律),(BC)A = (BA)(CA),A
3、(BC) = (AB)(AC),(BC)A = (BA)(C A),我們證明：,A(BC) = (AB)(AC),( ? ),( ? ),( ? ),證明思想,要證明兩個集合相等，通常有兩種方法：一是證兩個集合相互包含；,二是利用已有的集合運算的性質(zhì)(算律和已證明過的公式)，仿照代數(shù)恒等式的證明方法，一步步從左(右)邊推出右(左)邊，或從左、右邊分別推出同一個集合式子。,一般說來，最基本的集合相等關(guān)系要用第一種證法，比較復(fù)雜的集合相等關(guān)系用第二種方法更好，但第二種方法的使用取決于我們對算律和常用公式的熟練程度。,證明： 用第一種方法,對于任意的 A ( BC ), xAy(BC), xA(yB
4、yC ), (xAyB)(xAyC), ABAC, (AB)(AC), A(BC)=(AB)(AC),例4.2 設(shè)A=1,2，求P(A)A,解： P(A)A,= ，1，2，1,2,= ，，,n階笛卡兒積：,= (x1,x2, xn) | x1A1x2A2 xnAn,A1 A2 An,1,2,，，,，，,，,,二元關(guān)系：如果一個集合的元素都是二元有序組，則這個集合稱為一個二元關(guān)系，記作：R 。,如果 R ，記作 x R y,3、二元關(guān)系的數(shù)學(xué)定義,,從A到B的二元關(guān)系：設(shè)A，B為集合，A B的任何子集所定義的二元關(guān)系叫做從A到B的二元關(guān)系。,若A=B，叫做 A上的二元關(guān)系；,若|A|n，則|A
5、A|n2。,就是說，A上有 個不同的二元關(guān)系，其中包括空關(guān)系、全域關(guān)系UA和恒等關(guān)系IA。,AA的所有子集有 個。,例4.3 設(shè)A = a,b，寫出P(A)上的包含關(guān)系R ：,解： P(A) = ,a,ba,b,R = , , ,,,,,,, ,,,A上關(guān)系的表示法,1. 關(guān)系矩陣：,設(shè)A=x1, x2, , xn)，R是A上的關(guān)系，,則 (rij)nxn =,是R的關(guān)系矩陣,令：,二、二元關(guān)系的表示方法,2. 關(guān)系圖：,以E = | xiAxjAxiRxj為有向邊集組成的有向圖G = ,以V=A=x1, x2,, xn 為頂點集，,卡盟排行榜 卡盟,Microsoft Office Pow
6、erPoint，是微軟公司的演示文稿軟件。用戶可以在投影儀或者計算機上進行演示，也可以將演示文稿打印出來，制作成膠片，以便應(yīng)用到更廣泛的領(lǐng)域中。利用Microsoft Office PowerPoint不僅可以創(chuàng)建演示文稿，還可以在互聯(lián)網(wǎng)上召開面對面會議、遠程會議或在網(wǎng)上給觀眾展示演示文稿。 Microsoft Office PowerPoint做出來的東西叫演示文稿，其格式后綴名為：ppt、pptx；或者也可以保存為：pdf、圖片格式等,,,例4.4 設(shè)A=1,2,3,4，R=,,,,是A上的關(guān)系，試寫出R的關(guān)系矩陣并畫出關(guān)系圖：,解： 關(guān)系矩陣 ：,0 0 1 1,0 0 0 0,0
7、 1 0 0,關(guān)系圖 ：,4.2 關(guān)系的運算,,關(guān)系R的定義域： domR = x | (y)R (即R中有序組的第一個元素構(gòu)成的集合),關(guān)系R的值域： ranR =y | (x)R (即R中有序組的第二個元素構(gòu)成的集合),一、關(guān)系的定義域與值域,例4.5 下列關(guān)系都是整數(shù)集Z上的關(guān)系，分別求出它們的定義域和值域：,(1) R1= | x, y Z xy,(2) R2= | x, y Z x2+y2=1,(3) R3= | x, y Z y=2x,(4) R4= | x, y Z |x|=|y|=3,解： domR1 = ranR1 = Z,解： R2 = , ,,domR2 = ( ? ),
8、ranR2 = ( ? ),(1) R1= | x, y Z xy,(2) R2= | x, y Z x2+y2=1,, ,解： domR3 = Z， ranR3 = 偶數(shù),解： domR4 = ranR4 = ( ? ),(3) R3= | x, y Z y=2x,(4) R4= | x, y Z |x|=|y|=3,二、關(guān)系的常用運算,F是任意關(guān)系，F(xiàn)的逆F1= | yFx,F、G是任意兩個關(guān)系，F(xiàn)與G的合成記作：F G= | (z)(xGzzFy),關(guān)系F在集A上的限制，記作：F | A= | xFyxA,集A在關(guān)系F下的象FA = ran(F | A),(1) 逆：,(2) 合成：,(
9、3) 限制：,(4) 象：,例4.6 設(shè)F，G是N上的關(guān)系，其定義為：,F = | x, yNy = x2,G = | x,yNy = x+1,求 G1，F(xiàn) G，G F，F(xiàn) |1,2，F(xiàn)1,2,解：由定義知：,G1 = | y, xNy = x+1,列出G1 中的元素就是,G1 = ,,,,,,為了求F G，可以先直觀表示如下：,對任何xN,即 y = (x+1)2,因此 F G = | x,yNy = (x+1)2,同理可求 G F = | (?) (自己做！),發(fā)現(xiàn) F G G F,F |1,2 = ,,F 1,2 = ran(F |1,2) = 1,4,關(guān)系運算的性質(zhì)：設(shè)F、G、H、為任
10、意關(guān)系，則有：,(1) (F1)1 = F,(2) domF1 = ranF，ranF1 = domF,(3) (F G) H = F (G H),(4) (F G)1 = G1 F1,(5) F (GH) = F GF H (對的分配律),(6) F (GH) F GF H (對的半分配律),(7) (GH) F = G FH F,(8) (GH) F G FH F,( ? ),( ? ),任取, (F G)1, F G, (z)( G F), (z)( G1 F1), G1 F1,(4) (F G)1 = G1 F1的證明：,任取,F (GH), (z)((GH)F), (z)((GH)F
11、) (注意對括號的順序), (z)(GF(HF)), F GF H, F (GH) = F GF H,(5) F (GH) = F GF H的證明：,4.3 關(guān)系的性質(zhì),,R的關(guān)系矩陣：主對角線元素全是1,R的關(guān)系圖：每個頂點都有環(huán),自反性： x A 有R (R是A上的關(guān)系),關(guān)系矩陣：主對角線元素全是0,關(guān)系圖： 每個頂點都沒有環(huán),反自反性：x A R,對稱性：若 R，則 R,關(guān)系矩陣：對稱陣,關(guān) 系 圖：如果兩個頂點之間有邊，一定是一對方向相反的邊。,反對稱性：若 R且xy，則 R,關(guān)系矩陣：如果rij = 1，且 i j，則rji = 0,關(guān)系圖： 如果兩個頂點之間有邊，一定是只有一
12、條有向邊。,,傳遞性：若 R且 R，則 R,關(guān)系圖：如果頂點xi到xj有邊， xj到xk有邊，則從xi到xk有邊,例4.7 設(shè)A=1,2,,10，對于A上的關(guān)系R= | (xy)/3I,I為整數(shù)集，問R有哪些性質(zhì)？,解：逐條性質(zhì)加以驗證R= | (xy)/3I,任取A中元素x，由于(xx)/3=0，所以R是自反的；,又設(shè)A中任意兩個元素x,y，如果 xRy，即xy可被3整除，則yx也一定可被3整除，即yRx，從而R是對稱的；,如果A中三 個元素x，y，z滿足xRy， yRz，則x y，yz被3整除，由于xz=(xy)+(yz)，所以xz被3整除，從而xRz即R具有傳遞性。,,,4.4 關(guān)系的閉
13、包運算,閉包：設(shè)RAA，,自反閉包 記作 r(R),對稱閉包 記作 s(R),傳遞閉包 記作 t(R),由A求r(R)，s(R)，t(R)的過程叫閉包運算。,那么，包含R而使之具有自反性質(zhì)的最小關(guān)系，稱之為R的自反閉包；,包含R而使之具有對稱性質(zhì)(傳遞性質(zhì))的最小關(guān)系，稱之為R的對稱(傳遞)閉包。,一、定義,,冪運算：設(shè)RAA，kN，約定,(1) R0 = IA = | xA,(2) R1 = R,(3) Rk+1 = Rk R,顯然 Rm Rn = Rm+n (Rm)n = Rmn,二、計算方法,為了有效地計算關(guān)系R的各種閉包，先引進關(guān)系的冪運算概念。,閉包運算的方法：設(shè)R是A上的任一關(guān)系
14、，則,(1) r (R) = RIA,(2) s (R) = RR,(3) t (R) = RR2R3 Rn,矩陣形式：(M為R的關(guān)系矩陣),(1) Mr = M + E,(2) Ms = M + M (M 是M的轉(zhuǎn)置),(3) Mt = M+M2+M3,其中“ +” 均表示“ 邏輯加”,例4.8 設(shè)A=a,b,c,d，A上的關(guān)系,求 r (R)，s (R) 和 t (R),解： r(R) = RIA,=, , ,, , , , ,R=,,,, ,= R,,,三、實例,s(R) = RR,=,,,,,,,t(R) = RR2R3,= R,,,,,而R2 = R R,R3 = R2 R,R4
15、= R3 R,= ,,,,,,= ,,,,,,,= , ,, ,, ,實際上，看到當(dāng)k 4時，已有R4 RR2R3,故 t(R) = RR2R3,=,,,,, ,,,,四、閉包運算的性質(zhì),設(shè)A是有限集且|A| = n，RAA，則：,,,4.6 等價關(guān)系和偏序關(guān)系,,等價關(guān)系：集A上的關(guān)系R是自反的, 對稱的和傳遞的。,等價類： R是集A上的等價關(guān)系，對于任一aA，,,aR=x | aRx, xA,被稱為a的等價類。,即A中所有和a有R關(guān)系的元素的集合。,一、等價關(guān)系及用途,等價類的性質(zhì)：R是非空集合，對任意的x，yA，下面的結(jié)論成立：,(1) x且xA (等價類為A的子集),(2) 若xRy，
16、則x = y,(3) 若xRy，則xy = ,集A在等價關(guān)系R下的商集：設(shè)R為非空集A上的等價關(guān)系，以R的不交的等價類為元素的集合叫做A在R下的商集，記作A/R.,即：,A/R = xR | xA,集A的劃分：設(shè)A是非空集合，,(1) ,(2) 中任意兩個元素不交,(3) 中所有元素的并集為A,則 為A的劃分。,如果存在一個A的子集族， P(A)滿足以下條件：,,由等價類的性質(zhì)和商集的定義可知，商集A/R是A的劃分，稱之為由R誘導(dǎo)的劃分。,反過來，給定A的任一劃分 ，則A被分割成若干個劃分塊。,若定義A上的二元關(guān)系R：x，yA且x,y屬 的同一塊，則xRy，那么R是A上的等價關(guān)系，稱之為由 誘
17、導(dǎo)的等價關(guān)系。,集A上的等價關(guān)系與劃分是一一對應(yīng)的。,例4.9 設(shè)A=1,2,3，求出A上所有的等價關(guān)系：,解：先求A的各種劃分：只有1個劃分塊的劃分1，具有兩個劃分塊的劃分2， 3，和4，具有3個劃分塊5。,1 = A,2 = 1,2,3，,4 = 3,1,2，,3 = 2,1,3，,5 = 1,2,3,設(shè)對應(yīng)于劃分i 的等價關(guān)系 Ri，i = 1,2,5，則有,R5 = ，，,R1 = ，，，,R2 = ，,R3 = ，,R4 = ，,，，，,，，,，，,，,，，,，,，,，，,,偏序關(guān)系：集A上的關(guān)系R是自反的，反對稱的和傳遞的，記作“ ”，且稱
18、例4.10 設(shè)A=2,4,6,8，A上關(guān)系R是通常意義下的小于或等于關(guān)系，試寫出R并驗證它是偏序關(guān)系。,解：R=, , , ,,(1)自反性：,(2)反對稱性：,(3)傳遞性：,,, ,,, , ,,,,均屬于R,對任意的R， 必有xy，當(dāng)xy時， yx，從而R,對任意的R， R,由于 xyyz ，所以xz，從而R。,例4.11 設(shè)C=a,b,a,b,，C上關(guān)系T是集合的“ 包含于”，試寫出T，并驗證它是偏序關(guān)系。,解： 同例4.10類似，自己做！,偏序集的哈斯圖,(1) 用小圓圈表示偏序集的元素 (稱為結(jié)點)；,(2) 按每個元素在偏序中的次序從底向上列結(jié)點位置；,(3) 對于偏序集中任意
19、兩個元素x和y，如果xy且不存在另一個元素a，使xaay，則在x與y兩結(jié)點之間劃上一杠，即“ | ” (x在下，y在上),,全序關(guān)系：設(shè)是偏序集，,(x)(y)(xAyA(xyyx)),成立，則稱
20、(B中沒有比y大的其他元),(5) 若yA，使得(x)(xB xy)為真，則稱y是B的上界,(3) 若yB，使得 (x)(xBxy)，則稱y是B的極小元 (B中找不到x小于y ),(6) 若yA，使得(x)(xB yx)為真，則稱y是B的下界,(7) 令C=y | y為B的上界，則稱C的最小元為B的上確界或最小上界,(8) 令D =y | y為B的下界，則D的最大元為B的下確界或最大下界,,,例4.12 畫出和的哈斯圖，并指出其中的特殊元。,解： (1) 的哈斯圖如下：,由圖可知1為最小元，沒有最大元；,7,8,9,10,11, 12均為極大元，極小元為1；,1為1,2,,12的下界，也是下確
21、界；,1,2,,12中沒有上確界或上界。,,(2) 的哈斯圖如下：,P(a,b,c)=,a,b,c,a,b,a,c,b,c,a,b,c,由圖可知： 為P(a,b,c)的最小元，a,b,c為它的最大元；,同時，a,b,c也分別為它們的極小元和極大元、下確界和上確界。,,a,b,c,d,e,例4.13 已知偏序集的哈斯圖如下：,,,,,,,,,,,,h,,,,g,f,,試寫出對應(yīng)的A和A上的偏序關(guān)系R，并指出A中的特殊元。,, ,, , , ,,,解： A = a,b,c,d,e,f, g,h,直接由哈斯圖可知：A中沒有最小元和最大元；,e, g和h均為A的極大元，a, b, f 和h均為A的極小元；沒有上確界和下確界。,R = ,,,,a,b,c,d,e,,,,,,,,,,,,h,,,,g,f,,,,,,, ,,,小結(jié)與學(xué)習(xí)要求：,了解二元關(guān)系的定義和表示方法；熟練掌握關(guān)系的性質(zhì)和運算；特別是復(fù)合和三種閉包運算;理解等價關(guān)系和偏序關(guān)系，明確它們在描述研究對象的結(jié)構(gòu)和特點時重要作用 (即分類和覆蓋)。它們在計算機科學(xué)中有重要應(yīng)用。,
離散數(shù)學(xué)-二元關(guān)系與運算-專業(yè)數(shù)學(xué)教材.ppt
