第4章 二元關(guān)系與函數(shù).ppt

1、1,第4章 二元關(guān)系與函數(shù),4.1 集合的笛卡兒積與二元關(guān)系 4.2 關(guān)系的運(yùn)算 4.3 關(guān)系的性質(zhì) 4.4 關(guān)系的閉包 4.5 等價(jià)關(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ū)?定義 由兩個(gè)元素 x 和 y，按照一定的順序組成的 二元組稱為有序?qū)?，記?實(shí)例：平面直角坐標(biāo)系中點(diǎn)的坐標(biāo) 有序?qū)π再|(zhì) 1） 有序性 （當(dāng)x y時(shí)） 2） 與 相等的充分必要條件是 = x=u y=v,例1 = ，求 x, y. 解 3y 4 = 2, x+5 = y y = 2, x

2、= 3,4,有序 n 元組,定義 一個(gè)有序 n (n3) 元組 是一個(gè) 有序?qū)?，其中第一個(gè)元素是一個(gè)有序 n-1元組，即 = , xn 實(shí)例 ：空間直角坐標(biāo)系中的坐標(biāo) n 維向量是有序 n元組. 當(dāng) n=1時(shí), 形式上可以看成有序 1 元組.,5,笛卡兒積,定義 設(shè)A, B為集合，用A中元素為第一個(gè)元素，B中元素為第二個(gè)元素，構(gòu)成有序?qū)? 所有這樣的有序?qū)M成的集合叫做 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

3、) 不適合結(jié)合律 (AB)CA(BC) (A, B) 對(duì)于并或交運(yùn)算滿足分配律 A(BC)=(AB)(AC) (BC)A=(BA)(CA) A(BC)=(AB)(AC) (BC)A=(BA)(CA) 若A或B中有一個(gè)為空集，則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

4、 AC=BD (2) AC=BD是否推出 A=B C=D ? 為什么？,(2) 不一定. 反例如下： A=1，B=2, C=D=, 則 AC=BD 但是 AB.,9,例4 (1) 證明 A B C D AC BD (2) AC BD是否推出 A B C D,解 (1) 任取 AC xA yC xB yD BD,(2) 不一定. 反例如下： A=1，B=2, C=D=,10,二元關(guān)系：集合中兩個(gè)元素之間的某種關(guān)系 例1 甲、乙、丙3個(gè)人進(jìn)行乒乓球比賽，任何兩個(gè)人之間都要比賽一場(chǎng)。假設(shè)比賽結(jié)果是乙勝甲，甲勝丙，乙勝丙。 比賽結(jié)果可表示為： ， ， ，其中表示x勝y，它表示了集合甲,乙,丙中元素之間

5、的一種勝負(fù)關(guān)系. 例2 有A、B、C3個(gè)人和四項(xiàng)工作G1、 G2、 G3、 G4，已知A可以從事工作G1和G4，B可以從事工作G3，C可以從事工作G1和G2. 那么，人和工作之間的對(duì)應(yīng)關(guān)系可以記作 R , , , , C,G2 它表示了集合A,B,C到工作G1,G2,G3,G4之間的關(guān)系,11,二元關(guān)系的定義,定義 如果一個(gè)集合滿足以下條件之一： （1）集合非空, 且它的元素都是有序?qū)?（2）集合是空集 則稱該集合為一個(gè)二元關(guān)系, 簡(jiǎn)稱為關(guān)系，記作R. 如R, 可記作 xRy；如果R, 則記作x y 實(shí)例：R=, S=,a,b. R是二元關(guān)系, 當(dāng)a, b不是有序?qū)r(shí)，S不是二元關(guān)系 根據(jù)上面

6、的記法，可以寫 1R2, aRb, a c 等.,12,從A到B的關(guān)系與A上的關(guān)系,定義 設(shè)A,B為集合, AB的任何子集所定義的二元 關(guān)系叫做從A到B的二元關(guān)系, 當(dāng)A=B時(shí)則叫做 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同時(shí)也是 A上的二元關(guān)系. 計(jì)數(shù) |A|=n, |AA|=n2, AA的子集有 個(gè). 所以 A上有 個(gè)不同的二元關(guān)系. 例如 |A|=3, 則 A上有=512個(gè)不同的二元關(guān)系.,13,A上重要關(guān)系的實(shí)例,設(shè) A 為任意集合， 是 A 上的

7、關(guān)系，稱為空關(guān)系 EA, IA 分別稱為全域關(guān)系與恒等關(guān)系，定義如下： EA=|xAyA=AA IA=|xA例如, A=1,2, 則 EA=, IA=,14,A上重要關(guān)系的實(shí)例（續(xù)）,小于等于關(guān)系 LA, 整除關(guān)系DA, 包含關(guān)系R定義： LA=| x,yAxy, AR，R為實(shí)數(shù)集合 DB=| x,yBx整除y, BZ*, Z*為非0整數(shù)集 R=| x,yAxy, A是集合族. 類似的還可以定義大于等于關(guān)系, 小于關(guān)系, 大于關(guān)系, 真包含關(guān)系等等.,15,實(shí)例,例如 A = 1, 2, 3, B =a, b, 則 LA=, DA=,A=P(B)=,a,b,a,b, 則 A上的包含關(guān)系是 R=

8、, ,16,關(guān)系的表示,表示方式：關(guān)系的集合表達(dá)式、關(guān)系矩陣、關(guān)系圖 關(guān)系矩陣：若A=x1, x2, , xm，B=y1, y2, , yn，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é)點(diǎn)集，R為邊集.如果屬于關(guān)系R，在圖中就有一條從 xi 到 xj 的有向邊. 注意：A, B為有窮集，關(guān)系矩陣適于表示從A到B的關(guān)系或者A上的關(guān)系，關(guān)系圖適于表示A上的關(guān)系,17,實(shí)例,A=1,2,3,4, R=, R的關(guān)系矩陣MR和關(guān)系圖GR如下：,18,基本運(yùn)算定義

9、 定義域、值域、域 逆、合成、限制、像 基本運(yùn)算的性質(zhì) 冪運(yùn)算 定義 求法 性質(zhì),4.2 關(guān)系的運(yùn)算,19,關(guān)系的基本運(yù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,20,關(guān)系的基本運(yùn)算定義（續(xù)）,逆與合成 R1 = | R RS = | | z ( S R) 例2 R=, , , S=, , , , R1=, , , RS =, , , SR =, , ,21,合成運(yùn)算的圖示方法,利用圖示（不是關(guān)系圖）方法

10、求合成 RS = , , , SR =, , ,22,限制與像,定義 F 在A上的限制 FA = | xFy xA A 在F下的像 FA = ran(FA) 實(shí)例 R=, , , R1=, R1=2,4 R= R1,2=2,3,4 注意：FAF, FA ranF,23,關(guān)系基本運(yù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 所以有domF1= ranF. 同理可證 ranF1

11、 = domF.,24,定理2 設(shè)F, G, H是任意的關(guān)系, 則 (1) (FG)H=F(GH) (2) (FG)1= G1F1 證 (1) 任取, (FG)H t( H FG) t ( H s (G) F) ) t s ( H G F) s (Ft (HG) s (FGH) F(GH) 所以 (FG)H = F(GH),關(guān)系基本運(yùn)算的性質(zhì)（續(xù)）,25,(2) 任取, (FG)1 FG t ( G (t,x) F) t ( F1 (t,y) G1) G1F1 所以 (FG)1 = G1F1,關(guān)系基本運(yùn)算的性質(zhì)（續(xù)）,26,關(guān)系基本運(yùn)算的性質(zhì)（續(xù)）,設(shè)F 、G、 H為任意的二元關(guān)系，則有： F

12、 (G H ) =F G FH (G H ) F = G F HF (合成運(yùn)算對(duì)運(yùn)算滿足分配律） 3. F (G H ) F G FH 4. (G H ) F G F HF (合成運(yùn)算對(duì) 運(yùn)算分配后是包含關(guān)系）,27,A上關(guān)系的冪運(yùn)算,設(shè)R為A上的關(guān)系, n為自然數(shù), 則 R 的 n次冪定義為： (1) R0= | xA =IA (2) Rn+1 = RnR 注意： 對(duì)于A上的任何關(guān)系R1和R2都有 R10 = R20 = IA 對(duì)于A上的任何關(guān)系 R 都有 R1 = R,28,冪的求法,(1) 對(duì)于集合表示的關(guān)系R，計(jì)算 Rn 就是n個(gè)R左復(fù)合 . (2) 矩陣表示就是n個(gè)矩陣相乘, 其中相

13、加采用邏輯加. 例3 設(shè)A=a,b,c,d, R=, 求R的各次冪, 分別用矩陣和關(guān)系圖表示.解 R與R2的關(guān)系矩陣分別為,29,同理，R0=IA, R3和R4的矩陣分別是： 因此M4=M2, 即R4=R2. 因此可以得到R2=R4=R6=, R3=R5=R7=對(duì)于有窮集A，A上關(guān)系R的不同冪只有有限個(gè)。,冪的求法（續(xù)）,30,R0, R1, R2, R3,的關(guān)系圖如下圖所示,冪的求法（續(xù)）,31,冪運(yùn)算的性質(zhì),定理3 設(shè)A為n元集, R是A上的關(guān)系, 則存在自然數(shù) s 和 t, 使得 Rs = Rt. 證 R為A上的關(guān)系, 由于|A|=n, A上的不同關(guān)系只有 個(gè). 當(dāng)列出 R 的各次冪 R0, R1, R2, , , , 必存在自然數(shù) s 和 t 使得 Rs=Rt.,32,定理4 設(shè) R 是 A 上的關(guān)系, m, nN, 則 (1) RmRn=Rm+n (2) (Rm)n=Rmn 證 用歸納法 (1) 對(duì)于任意給定的mN, 施歸納于n.若n=0, 則有 RmR0=RmIA=Rm=Rm+0 假設(shè)RmRn=Rm+n,