離散數(shù)學(xué) 集合的笛卡兒積與二元關(guān)系

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ù)14.1 集合的笛卡兒積和二元關(guān)系 有序?qū)?笛卡兒積及其性質(zhì) 二元關(guān)系的定義 二元關(guān)系的表示2有序?qū)Χx 由兩個(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 = 3 3有序 n 元組定義 一個(gè)

2、有序 n (n3) 元組 是一個(gè)有序?qū)?，其中第一個(gè)元素是一個(gè)有序 n-1元組，即 = , xn 實(shí)例 ：空間直角坐標(biāo)系中的坐標(biāo) n 維向量是有序 n元組.當(dāng) n=1時(shí), 形式上可以看成有序 1 元組. 4笛卡兒積定義 設(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=, 5笛卡兒積的性質(zhì)不適合交換律 ABBA (AB, A, B)不適合結(jié)合律 (AB)CA(BC) (A, B)對(duì)

3、于并或交運(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 6性質(zhì)的證明證明 A(BC)=(AB)(AC)證 任取 A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC)所以有A(BC) = (AB)(AC).7例題 解 (1) 任取 AC xA yC xB yD BD 例3 (1) 證明 A=B C=D AC=BD (2) AC=BD是否推出 A=B C=D ? 為什么

4、？(2) 不一定. 反例如下： A=1，B=2, C=D=, 則 AC=BD 但是 AB.8例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=9例5 設(shè)A、B、C、D為任意集合，判斷以下等式是否成立， 說(shuō)明為什么。(AB)(C D)=(AC)(B D)(AB)(CD)=(AC)(B D)(A-B)(C-D)=(AC)-(BD)(AB)(CD)=(AC)(BD)解：(1)成立，因?yàn)閷?duì)任意的 (AB)(C D)xA B y C DxA x B y

5、C y D AC BD10(2)(AB)(C D)=(AC)(B D)解：不成立，若A=D= B=C= 1則有： (AB)(C D)= B C=(3)(A-B)(C-D)=(AC)-(BD)解：不成立， A=B=1 C=2 D=3 (A-B)(C-D)= (AC)-(BD) = =(4)(AB)(CD)=(AC)(BD)解：A=1 B= C= D=1(AB)(CD)=1,1(AC)(BD)= 11 設(shè)A1,A2, ,An是集合(n2),它們的n階笛卡爾積記作A1A2 An,其中A1A2 An=x1A1, x2 A2 , ,xnAn.當(dāng)A1=A2 =An時(shí)，可將它們的n階笛卡爾積記作An例如：A

6、=a,b,則A3=,12二元關(guān)系：集合中兩個(gè)元素之間的某種關(guān)系例1 甲、乙、丙3個(gè)人進(jìn)行乒乓球比賽，任何兩個(gè)人之間都要比賽一場(chǎng)。假設(shè)比賽結(jié)果是乙勝甲，甲勝丙，乙勝丙。比賽結(jié)果可表示為： ， ， ，其中表示x勝y，它表示了集合甲,乙,丙中元素之間的一種勝負(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)系13二元關(guān)系的定義定義 如果一個(gè)集合滿足以下條件之一：（1）集合非空,

7、 且它的元素都是有序?qū)Γ?）集合是空集則稱該集合為一個(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ù)上面的記法，可以寫 1R2, aRb, a c 等. 14從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)系

8、. 計(jì)數(shù)|A|=n, |AA|=n2, AA的子集有 個(gè). 所以 A上有 個(gè)不同的二元關(guān)系. 例如 |A|=3, 則 A上有=512個(gè)不同的二元關(guān)系. 15A上重要關(guān)系的實(shí)例設(shè) A 為任意集合，是 A 上的關(guān)系，稱為空關(guān)系EA, IA 分別稱為全域關(guān)系與恒等關(guān)系，定義如下： EA=|xAyA=AA IA=|xA例如, A=1,2, 則 EA=, IA=,16A上重要關(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是集合族.類似的還可以定義大于

9、等于關(guān)系, 小于關(guān)系, 大于關(guān)系, 真包含關(guān)系等等. 17實(shí)例例如 A = 1, 2, 3, B =a, b, 則 LA=, DA=, A=P(B)=,a,b,a,b, 則 A上的包含關(guān)系是 R=, ,18關(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 的有向邊.

10、注意：A, B為有窮集，關(guān)系矩陣適于表示從A到B的關(guān)系或者A上的關(guān)系，關(guān)系圖適于表示A上的關(guān)系 19實(shí)例A=1,2,3,4, R=,R的關(guān)系矩陣MR和關(guān)系圖GR如下：20基本運(yùn)算定義定義域、值域、域逆、合成、限制、像基本運(yùn)算的性質(zhì)冪運(yùn)算定義求法性質(zhì)4.2 關(guān)系的運(yùn)算21關(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 22關(guān)系的基本運(yùn)算定義（續(xù)）定義 設(shè)F、G為任意的關(guān)系，A為集合，則逆與合成 F1 =

11、 | F FG = | | z ( G F) 例2 R=, , , S=, , , , R1=, , , SR =, , RS =, , , 23合成運(yùn)算的圖示方法 利用圖示（不是關(guān)系圖）方法求合成 RS=, , , SR =, , RSSR24限制與像定義 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 25例.設(shè)F、G是N上的關(guān)系，其定義為 F=x,y N y=x2 G =x,y N y=x+1求G1、FG 、 GF、 F1,2、F1,2解：G1=

12、 y,xN y=x+1 G1=, , 對(duì)任何xN有 y=z2=(x+1)2，所以 FG= x,y N y =(x+1)2 GF= x,y N y =x2+1 F1,2=, F 1,2=ran(F1,2)=1,426例.設(shè)F=,求FF、 Fa、Fa解：FF=Fa=A= aFA = ran(FA)=ran=a27關(guān)系基本運(yùn)算的性質(zhì) 定理4.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

13、= ranF. 同理可證 ranF1 = domF.28 (3) (FG)H=F(GH) (4) (FG)1= G1F1 證 (3) 任取, (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ù)） 29 (4) 任取, (FG)1 FG t ( G (t,x) F) t ( F1 (t,y) G1) G1F1 所以 (FG)1 = G1F1 關(guān)系基本運(yùn)算的性質(zhì)（續(xù)） 30關(guān)系基本運(yùn)算的性質(zhì)（續(xù)） 定理4.2 設(shè)F 、G、 H為任意的二元關(guān)系，則有：F (

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

15、3 設(shè)A=a,b,c,d, R=, 求R的各次冪, 分別用矩陣和關(guān)系圖表示.解 R與R2的關(guān)系矩陣分別為33同理，R0=IA, R3和R4的矩陣分別是：因此M4=M2, 即R4=R2. 因此可以得到R2=R4=R6=, R3=R5=R7=對(duì)于有窮集A，A上關(guān)系R的不同冪只有有限個(gè)。冪的求法（續(xù)）34R0, R1, R2, R3,的關(guān)系圖如下圖所示冪的求法（續(xù)）35冪運(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.36定理4 設(shè) R 是 A 上的關(guān)系, m, nN, 則 (1) RmRn=Rm+n (2) (Rm)n=Rmn 證 用歸納法 (1) 對(duì)于任意給定的mN, 施歸納于n.若n=0, 則有