離散數(shù)學(xué)第四章二元關(guān)系和函數(shù).ppt

《離散數(shù)學(xué)第四章二元關(guān)系和函數(shù).ppt》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)第四章二元關(guān)系和函數(shù).ppt（30頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、1,第4章 二元關(guān)系與函數(shù),4.1 集合的笛卡兒積與二元關(guān)系 4.2 關(guān)系的運算 4.3 關(guān)系的性質(zhì) 4.4 關(guān)系的閉包 4.5 等價關(guān)系和偏序關(guān)系 4.6 函數(shù)的定義和性質(zhì) 4.7 函數(shù)的復(fù)合和反函數(shù),2,4.1 集合的笛卡兒積和二元關(guān)系,有序?qū)?笛卡兒積及其性質(zhì) 二元關(guān)系的定義 二元關(guān)系的表示,3,,有序?qū)?定義 由兩個客體 x 和 y，按照一定的順序組成的 二元組稱為有序?qū)Γ涀?實例：點的直角坐標(biāo)(3,4) 有序?qū)π再|(zhì) 有序性 （當(dāng)x y時） 與 相等的充分必要條件是 = x=u y=v,例1 = ，求 x, y. 解 3y 4 = 2, x+5 = y y = 2,

2、 x = 3,4,有序 n 元組,定義 一個有序 n (n3) 元組 是一個 有序?qū)Γ渲械谝粋€元素是一個有序 n-1元組，即 = , xn 當(dāng) n=1時, 形式上可以看成有序 1 元組. 實例 n 維向量是有序 n元組.,5,笛卡兒積,定義 設(shè)A,B為集合，A與B 的笛卡兒積記作AB， 即 AB = | xA yB ,例2 A=1,2,3, B=a,b,c AB =,,,,,, ,, BA =,,,,,, , , A=, P(A)A=, ,6,笛卡兒積的性質(zhì),不適合交換律 ABBA (AB, A, B) 不適合結(jié)合律 (AB)CA(BC) (A, B) 對于并或交運算滿足

3、分配律 A(BC)=(AB)(AC) (BC)A=(BA)(CA) A(BC)=(AB)(AC) (BC)A=(BA)(CA) 若A或B中有一個為空集，則AB就是空集. A=B= 若|A|=m, |B|=n, 則 |AB|=mn,7,性質(zhì)的證明,證明 A(BC)=(AB)(AC) 證 任取 A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC) 所以有A(BC) = (AB)(AC).,8,例題,解 (1) 任取 AC xA yC xB yD BD,例3 (1) 證明 A=B C=D AC=BD

4、(2) AC=BD是否推出 A=B C=D ? 為什么？,(2) 不一定. 反例如下： A=1，B=2, C=D=, 則 AC=BD 但是 AB.,9,二元關(guān)系的定義,定義 如果一個集合滿足以下條件之一： （1）集合非空, 且它的元素都是有序?qū)?（2）集合是空集 則稱該集合為一個二元關(guān)系, 簡稱為關(guān)系，記作R. 如R, 可記作 xRy；如果R, 則記作x y 實例：R=,, S=,a,b. R是二元關(guān)系, 當(dāng)a, b不是有序?qū)r，S不是二元關(guān)系 根據(jù)上面的記法，可以寫 1R2, aRb, a c 等.,10,從A到B的關(guān)系與A上的關(guān)系,定義 設(shè)A,B為集合, AB的任何子集所定義的二元 關(guān)系叫

5、做從A到B的二元關(guān)系, 當(dāng)A=B時則叫做 A上 的二元關(guān)系. 例4 A=0,1, B=1,2,3, R1=, R2=AB, R3=, R4=. 那么 R1, R2, R3, R4是從 A 到 B 的二元關(guān)系, R3和R4同時也是 A上的二元關(guān)系. 計數(shù) |A|=n, |AA|=n2, AA的子集有 個. 所以 A上有 個不同的二元關(guān)系. 例如 |A|=3, 則 A上有=512個不同的二元關(guān)系.,11,A上重要關(guān)系的實例,設(shè) A 為任意集合， 是 A 上的關(guān)系，稱為空關(guān)系 EA, IA 分別稱為全域關(guān)系與恒等關(guān)系，定義如下： EA=|xAyA=AA IA=|xA例如, A=1,2, 則

6、 EA=,,, IA=,,12,A上重要關(guān)系的實例（續(xù)）,小于等于關(guān)系 LA, 整除關(guān)系DA, 包含關(guān)系R定義： LA=| x,yAxy, AR，R為實數(shù)集合 DB=| x,yBx整除y, BZ*, Z*為非0整數(shù)集 R=| x,yAxy, A是集合族. 類似的還可以定義大于等于關(guān)系, 小于關(guān)系, 大于關(guān)系, 真包含關(guān)系等等.,13,實例,例如 A = 1, 2, 3, B =a, b, 則 LA=,,,,, DA=,,,,,A=P(B)=,a,b,a,b, 則 A上的包含關(guān)系是 R=,,,,, ,,,,14,關(guān)系的表示,表示方式：關(guān)系的集合表達(dá)式、關(guān)系矩陣、關(guān)系圖

7、關(guān)系矩陣：若A=a1, a2, , am，B=b1, b2, , bn，R是從A到B的關(guān)系，R的關(guān)系矩陣是布爾矩陣MR = rij mn, 其中 rij = 1 R. 關(guān)系圖：若A= x1, x2, , xm，R是從A上的關(guān)系，R的關(guān)系圖是GR=, 其中A為結(jié)點集，R為邊集.如果屬于關(guān)系R，在圖中就有一條從 xi 到 xj 的有向邊. 注意：A, B為有窮集，關(guān)系矩陣適于表示從A到B的關(guān)系或者A上的關(guān)系，關(guān)系圖適于表示A上的關(guān)系,15,實例,A=1,2,3,4, R=,,,,, R的關(guān)系矩陣MR和關(guān)系圖GR如下：,16,基本運算定義 定義域、值域、域 逆、合成、限制、像 基本運算的性質(zhì) 冪運算

8、 定義 求法 性質(zhì),4.2 關(guān)系的運算,17,關(guān)系的基本運算定義,定義域、值域 和 域 domR = x | y (R) ranR = y | x (R) fldR = domR ranR,例1 R=,,,, 則 domR=1, 2, 4 ranR=2, 3, 4 fldR=1, 2, 3, 4,18,關(guān)系的基本運算定義（續(xù)）,逆與合成 R1 = | R RS = | | y (RS) ,例2 R=, , , S=, , , , R1=, , , RS =, , SR =, , , ,19,合成運算的圖示方法,利用圖示（不是關(guān)系圖）方法求

9、合成 RS =, , SR =, , , ,20,限制與像,定義 F 在A上的限制 FA = | xFy xA A 在F下的像 FA = ran(FA) 實例 R=, , , R1=, R1=2,4 R= R1,2=2,3,4 注意：FAF, FA ranF,21,關(guān)系基本運算的性質(zhì),定理1 設(shè)F是任意的關(guān)系, 則 (1) (F1)1=F (2) domF1=ranF, ranF1=domF 證 (1) 任取, 由逆的定義有 (F 1)1 F1 F 所以有 (F1)1=F (2) 任取x, xdomF1 y(F1) y(F) xranF 所以有do

10、mF1= ranF. 同理可證 ranF1 = domF.,22,定理2 設(shè)F, G, H是任意的關(guān)系, 則 (1) (FG)H=F(GH) (2) (FG)1= G1F1 證 (1) 任取, (FG)H t(FGH) t (s(FG)H) t s (FGH) s (Ft (GH)) s (FGH) F(GH) 所以 (FG)H = F(GH),關(guān)系基本運算的性質(zhì)（續(xù)）,23,(2) 任取, (FG)1 FG t (F(t,x)G) t (G1(t,y)F1) G1F1 所以 (FG)1 = G1F1,關(guān)系基本運算的性質(zhì)（續(xù)）,24,A上關(guān)系的冪運算,設(shè)R為A上的關(guān)系, n為自然數(shù),

11、 則 R 的 n次冪定義為： (1) R0= | xA =IA (2) Rn+1 = RnR 注意： 對于A上的任何關(guān)系R1和R2都有 R10 = R20 = IA 對于A上的任何關(guān)系 R 都有 R1 = R,25,冪的求法,對于集合表示的關(guān)系R，計算 Rn 就是n個R右復(fù)合 . 矩陣表示就是n個矩陣相乘, 其中相加采用邏輯加. 例3 設(shè)A=a,b,c,d, R=,,,, 求R的各次冪, 分別用矩陣和關(guān)系圖表示.解 R與R2的關(guān)系矩陣分別為,,26,同理，R0=IA, R3和R4的矩陣分別是： 因此M4=M2, 即R4=R2. 因此可以得到R2=R4=R6=, R3=R5=

12、R7=,,冪的求法（續(xù)）,27,R0, R1, R2, R3,的關(guān)系圖如下圖所示,冪的求法（續(xù)）,28,冪運算的性質(zhì),定理3 設(shè)A為n元集, R是A上的關(guān)系, 則存在自然數(shù) s 和 t, 使得 Rs = Rt. 證 R為A上的關(guān)系, 由于|A|=n, A上的不同關(guān)系只有 個. 當(dāng)列出 R 的各次冪 R0, R1, R2, , , , 必存在自然數(shù) s 和 t 使得 Rs=Rt.,29,定理4 設(shè) R 是 A 上的關(guān)系, m, nN, 則 (1) RmRn=Rm+n (2) (Rm)n=Rmn 證 用歸納法 (1) 對于任意給定的mN, 施歸納于n.若n=0, 則有 RmR0=RmIA=Rm=Rm+0 假設(shè)RmRn=Rm+n, 則有RmRn+1=Rm(RnR)=(RmRn)R=Rm+n+1 , 所以對一切m, nN有RmRn=Rm+n.,冪運算的性質(zhì)（續(xù)）,30,(接上頁證明) (2) 對于任意給定的 mN, 施歸納于n. 若n=0, 則有 (Rm)0=IA=R0=Rm0 假設(shè) (Rm)n=Rmn, 則有 (Rm)n+1=(Rm)nRm=(Rmn)Rm=Rmn+m=Rm(n+1) 所以對一切 m,nN 有 (Rm)n=Rmn.,冪運算的性質(zhì)（續(xù)）,