《離散數(shù)學(xué),二元關(guān)系與運(yùn)算課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué),二元關(guān)系與運(yùn)算課件.ppt（60頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、 1 ：由兩個(gè)元素x和y按一定順序排成二元組，記作： 。如： 平面直角坐標(biāo)系中點(diǎn)的坐標(biāo)一、二元關(guān)系的概念 (1) 當(dāng)x y時(shí)， (2) = ，當(dāng)且僅當(dāng)x = u，y = v(1)、(2)說明有序組區(qū)別于集合n元 有 序 組 ：由n個(gè)元素x1，x2，xn，按一定順序排成的n元組，記作：(x1，x2，xn) 。 2. 一種新的集合運(yùn)算 積運(yùn)算 ： 設(shè)A、B為兩集合，用A中元素為第一元素，B中元素作為第二元素構(gòu)成的二元有序組的全體叫做A和B的笛卡兒積。記作：A B符號(hào)化：A B = | xA y B 例4.1 設(shè)A=a,b，B=0,1,2 ，求AB，BA解：根據(jù)笛卡兒積的定義知A B = , , ,
2、 B A = , , 一般地：如果|A|=m，|B|=n，則 |AB|=|BA|=m n, , (1) 若A，B中有一個(gè)空集，則笛卡兒積是空集，即： B = A = (2) 當(dāng)AB，且A，B都不是空集時(shí)，有ABBA (3) 當(dāng)A，B，C都不是空集時(shí)，有(AB)C A(BC)因?yàn)?AB)C中的元素 , z，而A(BC)中的元素為 x, 。 (4) A(B C) = (AB) (AC) (對(duì)的分配律)(B C)A = (BA) (CA)A(BC) = (AB)(AC)(BC)A = (BA)(C A)我們證明：A(B C) = (AB) (AC) ( ? )( ? )( ? ) 要證明兩個(gè)集合相等
3、，通常有兩種方法：一是證兩個(gè)集合相互包含；二是利用已有的集合運(yùn)算的性質(zhì)(算律和已證明過的公式)，仿照代數(shù)恒等式的證明方法，一步步從左(右)邊推出右(左)邊，或從左、右邊分別推出同一個(gè)集合式子。一般說來，最基本的集合相等關(guān)系要用第一種證法，比較復(fù)雜的集合相等關(guān)系用第二種方法更好，但第二種方法的使用取決于我們對(duì)算律和常用公式的熟練程度。 證明： 用第一種方法對(duì)于任意的 A ( B C ) xAy(B C) xA(yByC ) (xAyB)(xAyC) ABAC (AB) (AC) A(B C)=(AB) (AC) 例4.2 設(shè)A=1,2，求P(A)A解： P(A)A= ，1，2，1,2= ，n階笛
4、卡兒積：= (x 1,x2, xn) | x1A1x2A2 xnAnA1 A2 An 1,2， 二 元 關(guān) 系 ：如果一個(gè)集合的元素都是二元有序組，則這個(gè)集合稱為一個(gè)二元關(guān)系，記作：R 。如果 R ，記作 x R y如果 R ，記作 x R y3、二元關(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，則|AA|n2。 2n2就是說，A上有 個(gè)不同的二元關(guān)系，其中包括空關(guān)系、全域關(guān)系UA和恒等關(guān)系IA。2n2AA的所有子集有 個(gè)。 例4.3 設(shè)A = a,b，寫出P(A)上的包含關(guān)
5、系R ：解： P(A) = ,a,ba,bR = , , , , , 1. 關(guān) 系 矩 陣 ：設(shè)A=x1, x2, , xn)，R是A上的關(guān)系，rij = 1 若xi R xj0 若xi R xj (i, j = 1,2, n)則 (rij)nxn =是R的關(guān)系矩陣令： nnnn nnrrr rrr rrr 21 22221 11211 二、二元關(guān)系的表示方法 2. 關(guān) 系 圖 ：以E = | xiAxjAxiRxj為有向邊集組成的有向圖G = 以V=A=x1, x2, xn 為頂點(diǎn)集， 例4.4 設(shè)A=1,2,3,4，R=,是A上的關(guān)系，試寫出R的關(guān)系矩陣并畫出關(guān)系圖：解： 關(guān)系矩陣 ：0
6、0 1 10 0 0 00 1 0 01 1 0 0關(guān)系圖 ：1 34 2 關(guān) 系 R的 定 義 域 ： domR = x | (y)R (即R中有序組的第一個(gè)元素構(gòu)成的集合)關(guān) 系 R的 值 域 ： ranR =y | (x)R (即R中有序組的第二個(gè)元素構(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
7、 = , , domR2 = ( ? )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)系的常用運(yùn)算F是任意關(guān)系，F(xiàn)的逆F1= | yFx F、G是任意兩個(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)
8、 逆 ：(2) 合 成 ：(3) 限 制 ：(4) 象 ： 例4.6 設(shè)F，G是N上的關(guān)系，其定義為：F = | x, yNy = x2G = | 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 中的元素就是G 1 = , 為了求F G，可以先直觀表示如下：對(duì)任何xNx x+1=G即 y = (x+1)2因此 F G = | x,yNy = (x+1)2 同理可求 G F = | (?) (自己做！)發(fā)現(xiàn) F G G FF |1,2 = ,F 1,2 = ran(F |1,2) = 1,4F Z Z2 = y
9、關(guān)系運(yùn)算的性質(zhì)：設(shè)F、G、H、為任意關(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 (G H) = F G F H (對(duì)的分配律)(6) F (GH) F GF H (對(duì)的半分配律)(7) (G H) F = G F H 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 (G H) (z)(G H)F) (z)(G
10、 H)F) (注意對(duì)括號(hào)的順序) (z)(GF (HF) F G F H F (G H) = F G F H(5) F (G H) = F G F H的證明： R的關(guān)系矩陣：主對(duì)角線元素全是1R的關(guān)系圖：每個(gè)頂點(diǎn)都有環(huán)自 反 性 ： x A 有R (R是A上的關(guān)系) 關(guān)系矩陣：主對(duì)角線元素全是0關(guān)系圖： 每個(gè)頂點(diǎn)都沒有環(huán)反 自 反 性 ： x A R 對(duì) 稱 性 ：若 R，則 R 關(guān)系矩陣：對(duì)稱陣關(guān) 系 圖：如果兩個(gè)頂點(diǎn)之間有邊，一定是一對(duì)方向相反的邊。 反對(duì)稱性：若 R且xy，則 R 關(guān)系矩陣：如果rij = 1，且 i j，則rji = 0 關(guān)系圖： 如果兩個(gè)頂點(diǎn)之間有邊，一定是只有一條有
11、向邊。 傳遞性：若 R且 R，則 R 關(guān)系圖：如果頂點(diǎn)xi到xj有邊， xj到xk有邊，則從xi到xk有邊 例4.7 設(shè)A=1,2,10，對(duì)于A上的關(guān)系R= | (xy)/3II為整數(shù)集，問R有哪些性質(zhì)？ 解：逐條性質(zhì)加以驗(yàn)證R= | (xy)/3I 任取A中元素x，由于(xx)/3=0，所以R是自反的；又設(shè)A中任意兩個(gè)元素x,y，如果 xRy，即xy可被3整除，則yx也一定可被3整除，即yRx，從而R是對(duì)稱的；如果A中三 個(gè)元素x，y，z滿足xRy， yRz，則x y，yz被3整除，由于xz=(xy)+(yz)，所以xz被3整除，從而xRz即R具有傳遞性。 閉 包 ：設(shè)RAA，自 反 閉 包
12、 記作 r(R)對(duì) 稱 閉 包 記作 s(R)傳 遞 閉 包 記作 t(R)由A求r(R)，s(R)，t(R)的過程叫閉 包 運(yùn) 算。那么，包含R而使之具有自反性質(zhì)的最小關(guān)系，稱之為R的自反閉包；包含R而使之具有對(duì)稱性質(zhì)(傳遞性質(zhì))的最小關(guān)系，稱之為R的對(duì)稱(傳遞)閉包。一、定義 冪 運(yùn) 算 ：設(shè)RAA，kN，約定(1) R0 = IA = | xA(2) R1 = R(3) Rk+1 = Rk R顯然 Rm Rn = Rm+n (Rm)n = Rmn二、計(jì)算方法為了有效地計(jì)算關(guān)系R的各種閉包，先引進(jìn)關(guān)系的冪運(yùn)算概念。 閉包運(yùn)算的方法：設(shè)R是A上的任一關(guān)系，則(1) r (R) = R IA(
13、2) s (R) = R R(3) t (R) = R R2 R3 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) = R IA=, , , , , , R=, = R ,三、實(shí)例 s(R) = R R=,t(R) = R R2 R3 = R , 而R2 = R RR3 = R2 RR4 = R3 R= ,= ,= , , , 實(shí)際上，看到當(dāng)k 4時(shí)，已有R4 R R
14、2 R3故 t(R) = R R 2 R3=, , 四、閉包運(yùn)算的性質(zhì)設(shè)A是有限集且|A| = n，RAA，則：iki RRtnk 1)()1( ，使有)()()2( RsrRrs )()()3( RtrRrt )( )()4( RtsRst 等 價(jià) 關(guān) 系 ：集A上的關(guān)系R是自反的, 對(duì)稱的和傳遞的。等 價(jià) 類 ： R是集A上的等價(jià)關(guān)系，對(duì)于任一aA，aR=x | aRx, xA被稱為a的等價(jià)類。即A中所有和a有R關(guān)系的元素的集合。一、等價(jià)關(guān)系及用途 等價(jià)類的性質(zhì)：R是非空集合，對(duì)任意的x，yA，下面的結(jié)論成立：(1) x且xA (等價(jià)類為A的子集)(2) 若xRy，則x = y(3) 若x
15、Ry，則xy = Ax Ax )4( 集 A在 等 價(jià) 關(guān) 系 R下 的 商 集 ：設(shè)R為非空集A上的等價(jià)關(guān)系，以R的不交的等價(jià)類為元素的集合叫做A在R下的商集，記作A/R.即：A/R = xR | xA 集 A的 劃 分 ：設(shè)A是非空集合，(1) (2) 中任意兩個(gè)元素不交 (3) 中所有元素的并集為A則 為A的劃分。如果存在一個(gè)A的子集族， P(A)滿足以下條件： 由等價(jià)類的性質(zhì)和商集的定義可知，商集A/R是A的劃分，稱之為由R誘導(dǎo)的劃分。反過來，給定A的任一劃分 ，則A被分割成若干個(gè)劃分塊。 若定義A上的二元關(guān)系R：x，yA且x,y屬 的同一塊，則xRy，那么R是A上的等價(jià)關(guān)系，稱之為由
16、 誘導(dǎo)的等價(jià)關(guān)系。集A上的等價(jià)關(guān)系與劃分是一一對(duì)應(yīng)的。 例4.9 設(shè)A=1,2,3，求出A上所有的等價(jià)關(guān)系：解：先求A的各種劃分：只有1個(gè)劃分塊的劃分1，具有兩個(gè)劃分塊的劃分2， 3，和4，具有3個(gè)劃分塊5。1 = A2 = 1,2,3， 4 = 3,1,2，3 = 2,1,3，5 = 1,2,3 設(shè)對(duì)應(yīng)于劃分i 的等價(jià)關(guān)系 Ri，i = 1,2,5，則有R5 = ，R1 = ，R2 = ，R3 = ，R 4 = ， 偏 序 關(guān) 系 ：集A上的關(guān)系R是自反的，反對(duì)稱的和傳遞的，記作“ ”，且稱A, )為偏序集。二、偏序關(guān)系及用途 例4.10 設(shè)A=2,4,6,8，A上關(guān)系R是通常意義下的小于或
17、等于關(guān)系，試寫出R并驗(yàn)證它是偏序關(guān)系。解：R=, , , , (1)自 反 性 ：(2)反 對(duì) 稱 性 ：(3)傳 遞 性 ： , , , , ,均屬于R對(duì)任意的R， 必有xy，當(dāng)xy時(shí)， yx，從而R對(duì)任意的R， R,由于 xyyz ，所以xz，從而R。 例4.11 設(shè)C=a,b,a,b,，C上關(guān)系T是集合的“ 包含于”，試寫出T，并驗(yàn)證它是偏序關(guān)系。解： 同例4.10類似，自己做！ (1) 用小圓圈表示偏序集的元素 (稱為結(jié)點(diǎn))；(2) 按每個(gè)元素在偏序中的次序從底向上列結(jié)點(diǎn)位置；(3) 對(duì)于偏序集中任意兩個(gè)元素x和y，如果xy且不存在另一個(gè)元素a，使xaay，則在x與y兩結(jié)點(diǎn)之間劃上一杠
18、，即“ | ” (x在下，y在上) 全 序 關(guān) 系 ：設(shè)是偏序集，(x)(y)(xAyA(xyyx)成立，則稱A,)為全序集，這時(shí)的偏序關(guān)系叫全序關(guān)系。全序集A,)中全部元素可以排序，它的哈斯圖為一條直線。如果 設(shè)是偏序集，BA(1) 如果yB，使得(x)(xByx)為真，則y是B的最小元 (“ 小于” B中所有元 )(2) 如果yB，使得(x)(xB xy)為真，則y是B的最大元 (“ 大于” B中所有元 ) (4) 若yB，使得 (x)(xBxy)，則稱y是B的極大元 (B中沒有比y大的其他元)(5) 若yA，使得(x)(xB xy)為真，則稱y是B的上界(3) 若yB，使得 (x)(xB
19、xy)，則稱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的下確界或最大下界 12 84 610例4.12 畫出和的哈斯圖，并指出其中的特殊元。解： (1) 的哈斯圖如下：925 1 3 711由圖可知1為最小元，沒有最大元；7,8,9,10,11, 12均為極大元，極小元為1；1為1,2,12的下界，也是下確界；1,2,12中沒有上確界或上界。 (2) 的哈斯圖如下：P(a,b,c)=,a,b,c,a,b,a,c,b,c,a,b,ca,b,ca,ca,b b,cca b由圖可知： 為P(a,b,c)的最小元，a,b,c為它的最大元；同時(shí)，a,b,c也分別為它們的極小元和極大元、下確界和上確界。 a bc de例4.13 已知偏序集的哈斯圖如下：hgf 試寫出對(duì)應(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 bc de hgf, , 小結(jié)與學(xué)習(xí)要求：
離散數(shù)學(xué),二元關(guān)系與運(yùn)算課件.ppt
