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

1、1第第4章章 二元關(guān)系與函數(shù)二元關(guān)系與函數(shù)n4.1 集合的笛卡兒積與二元關(guān)系集合的笛卡兒積與二元關(guān)系n4.2 關(guān)系的運(yùn)算關(guān)系的運(yùn)算n4.3 關(guān)系的性質(zhì)關(guān)系的性質(zhì)n4.4 關(guān)系的閉包關(guān)系的閉包n4.5 等價(jià)關(guān)系和偏序關(guān)系等價(jià)關(guān)系和偏序關(guān)系n4.6 函數(shù)的定義和性質(zhì)函數(shù)的定義和性質(zhì)n4.7 函數(shù)的復(fù)合和反函數(shù)函數(shù)的復(fù)合和反函數(shù)24.1 集合的笛卡兒積和二元關(guān)系集合的笛卡兒積和二元關(guān)系n 有序?qū)τ行驅(qū) 笛卡兒積及其性質(zhì)笛卡兒積及其性質(zhì)n 二元關(guān)系的定義二元關(guān)系的定義n 二元關(guān)系的表示二元關(guān)系的表示3有序?qū)τ行驅(qū)Χx定義 由兩個(gè)元素由兩個(gè)元素 x 和和 y，按照一定的順序組成的，按照一定的順序組成的

2、 二元組稱為二元組稱為有序?qū)τ行驅(qū)?，記作，記作?shí)例：平面直角坐標(biāo)系中點(diǎn)的坐標(biāo)實(shí)例：平面直角坐標(biāo)系中點(diǎn)的坐標(biāo)有序?qū)π再|(zhì)有序?qū)π再|(zhì) 1） 有序性有序性 （當(dāng)（當(dāng)x y時(shí)）時(shí)） 2） 與與 相等的充分必要條件是相等的充分必要條件是 = x=u y=v例例1 = ，求，求 x, y. 解解 3y 4 = 2, x+5 = y y = 2, x = 3 4有序有序 n 元組元組定義定義 一個(gè)一個(gè)有序有序 n (n 3) 元組元組 是一個(gè)是一個(gè)有序?qū)Γ渲械谝粋€(gè)元素是一個(gè)有序有序?qū)?，其中第一個(gè)元素是一個(gè)有序 n-1元組，即元組，即 = , xn 實(shí)例實(shí)例 ：空間直角坐標(biāo)系中的坐標(biāo)空間直角坐標(biāo)系中的坐標(biāo) n

3、 維向量是有序維向量是有序 n元組元組.當(dāng)當(dāng) n=1時(shí)時(shí), 形式上可以看成有序形式上可以看成有序 1 元組元組. 5笛卡兒積笛卡兒積定義定義 設(shè)設(shè)A, B為集合，用為集合，用A中元素為第一個(gè)元素，中元素為第一個(gè)元素，B中元素為第二個(gè)元素，構(gòu)成有序?qū)χ性貫榈诙€(gè)元素，構(gòu)成有序?qū)? 所有這樣所有這樣的有序?qū)M成的集合叫做的有序?qū)M成的集合叫做 A與與B 的的笛卡兒積笛卡兒積 記作記作A B， 即即 A B = | x A y B 例例2 A=1,2,3, B=a,b,c A B =, , B A =, , , A=, P(A) A=, 6笛卡兒積的性質(zhì)笛卡兒積的性質(zhì)不適合交換律不適合交換律 A

4、B B A (A B, A, B)不適合結(jié)合律不適合結(jié)合律 (A B) C A (B C) (A, B)對(duì)于并或交運(yùn)算滿足分配律對(duì)于并或交運(yùn)算滿足分配律 A (B C)=(A B) (A C) (B C) A=(B A) (C A) A (B C)=(A B) (A C) (B C) A=(B A) (C A) 若若A或或B中有一個(gè)為空集，則中有一個(gè)為空集，則A B就是空集就是空集. A=B= 若若|A|=m, |B|=n, 則則 |A B|=mn 7性質(zhì)的證明性質(zhì)的證明證明證明 A (B C)=(A B) (A C)證證 任取任取 A(BC) xAyBC xA(yByC) (xAyB)(xA

5、yC) ABAC (AB)(AC)所以有所以有A(BC) = (AB)(AC).8例題例題 解解 (1) 任取任取 A C x A y C x B y D B D 例例3 (1) 證明證明 A=B C=D A C=B D (2) A C=B D是否推出是否推出 A=B C=D ? 為什么？為什么？(2) 不一定不一定. 反例如下：反例如下： A=1，B=2, C=D=, 則則 A C=B D 但是但是 A B.9例例4 (1) 證明證明 A B C D A C B D (2) A C B D是否推出是否推出 A B C D 解解 (1) 任取任取 A C x A y C x B y D B D

6、 (2) 不一定不一定. 反例如下：反例如下： A=1，B=2, C=D=10例例5 設(shè)設(shè)A、B、C、D為任意集合，判斷以下等式是否成立，為任意集合，判斷以下等式是否成立， 說(shuō)明為什么。說(shuō)明為什么。(1)(A B) (C D)=(A C) (B D)(2)(A B) (C D)=(A C) (B D)(3)(A-B) (C-D)=(A C)-(B D)(4)(A B) (C D)=(A C) (B D)解：解：(1)成立，因?yàn)閷?duì)任意的成立，因?yàn)閷?duì)任意的 (A B) (C D)x A B y C Dx A x B y C y D A C B D11(2)(A B) (C D)=(A C) (B

7、D)解：不成立，若解：不成立，若A=D= B=C= 1則有：則有： (A B) (C D)= B C=(3)(A-B) (C-D)=(A C)-(B D)解：不成立，解：不成立， A=B=1 C=2 D=3 (A-B) (C-D)= (A C)-(B D) = =(4)(A B) (C D)=(A C) (B D)解：解：A=1 B= C= D=1(A B) (C D)=1,1(A C) (B D)= 12 設(shè)設(shè)A1,A2, ,An是集合是集合(n2),它們的它們的n階笛卡爾積記階笛卡爾積記作作A1 A2 An,其中其中A1 A2 An=x1 A1, x2 A2 , ,xn An.當(dāng)當(dāng)A1=A

8、2 =An時(shí)，可將它們的時(shí)，可將它們的n階笛卡爾積記作階笛卡爾積記作An例如：例如：A=a,b,則則A3=,13二元關(guān)系二元關(guān)系：集合中兩個(gè)元素之間的某種關(guān)系：集合中兩個(gè)元素之間的某種關(guān)系例例1 甲、乙、丙甲、乙、丙3個(gè)人進(jìn)行乒乓球比賽，任何兩個(gè)人之間都要比賽一場(chǎng)。個(gè)人進(jìn)行乒乓球比賽，任何兩個(gè)人之間都要比賽一場(chǎng)。假設(shè)比賽結(jié)果是乙勝甲，甲勝丙，乙勝丙。假設(shè)比賽結(jié)果是乙勝甲，甲勝丙，乙勝丙。比賽結(jié)果可表示為：比賽結(jié)果可表示為： ， ， ，其中，其中表示表示x勝勝y，它表示了集合，它表示了集合甲甲,乙乙,丙丙中元素之間的一種勝負(fù)關(guān)系中元素之間的一種勝負(fù)關(guān)系.例例2 有有A、B、C3個(gè)人和四項(xiàng)工作個(gè)人

9、和四項(xiàng)工作G1、 G2、 G3、 G4，已知，已知A可以從事可以從事工作工作G1和和G4，B可以從事工作可以從事工作G3，C可以從事工作可以從事工作G1和和G2. 那么，人和工作之間的對(duì)應(yīng)關(guān)系可以記作那么，人和工作之間的對(duì)應(yīng)關(guān)系可以記作 R , , , , C,G2 它表示了集合它表示了集合A,B,C到工作到工作G1,G2,G3,G4之間的關(guān)系之間的關(guān)系14二元關(guān)系的定義二元關(guān)系的定義定義定義 如果一個(gè)集合滿足以下條件之一：如果一個(gè)集合滿足以下條件之一：（1）集合非空）集合非空, 且它的元素都是有序?qū)η宜脑囟际怯行驅(qū)Γ?）集合是空集）集合是空集則稱該集合為一個(gè)則稱該集合為一個(gè)二元關(guān)系二元關(guān)

10、系, 簡(jiǎn)稱為簡(jiǎn)稱為關(guān)系關(guān)系，記作，記作R.如如R, 可記作可記作 xRy；如果；如果 R, 則記作則記作x y實(shí)例：實(shí)例：R=, S=,a,b. R是二元關(guān)系是二元關(guān)系, 當(dāng)當(dāng)a, b不是有序?qū)r(shí)，不是有序?qū)r(shí)，S不是二元關(guān)系不是二元關(guān)系根據(jù)上面的記法，可以寫(xiě)根據(jù)上面的記法，可以寫(xiě) 1R2, aRb, a c 等等. 15從從A到到B的關(guān)系與的關(guān)系與A上上的關(guān)系的關(guān)系定義定義 設(shè)設(shè)A,B為集合為集合, AB的任何子集所定義的二元的任何子集所定義的二元關(guān)系叫做關(guān)系叫做從從A到到B的二元關(guān)系的二元關(guān)系, 當(dāng)當(dāng)A=B時(shí)則叫做時(shí)則叫做 A上上的二元關(guān)系的二元關(guān)系.例例4 A=0,1, B=1,2,3,

11、 R1=, R2=AB, R3=, R4=. 那么那么 R1, R2, R3, R4是從是從 A 到到 B 的二元關(guān)系的二元關(guān)系, R3和和R4同時(shí)也是同時(shí)也是 A上的二元關(guān)系上的二元關(guān)系. 計(jì)數(shù)計(jì)數(shù)|A|=n, |AA|=n2, AA的子集有的子集有 個(gè)個(gè). 所以所以 A上有上有 個(gè)不同的二元關(guān)系個(gè)不同的二元關(guān)系. 例如例如 |A|=3, 則則 A上有上有=512個(gè)不同的二元關(guān)系個(gè)不同的二元關(guān)系. 22n22n16A上重要關(guān)系的實(shí)例上重要關(guān)系的實(shí)例設(shè)設(shè) A 為任意集合，為任意集合，是是 A 上的關(guān)系，稱為上的關(guān)系，稱為空關(guān)系空關(guān)系EA, IA 分別稱為分別稱為全域關(guān)系全域關(guān)系與與恒等關(guān)系恒等

12、關(guān)系，定義如下：，定義如下： EA=|xAyA=AA IA=|xA例如例如, A=1,2, 則則 EA=, IA=,17A上重要關(guān)系的實(shí)例（續(xù)）上重要關(guān)系的實(shí)例（續(xù)）小于等于關(guān)系小于等于關(guān)系 LA, 整除關(guān)系整除關(guān)系DA, 包含關(guān)系包含關(guān)系R 定義：定義： LA=| x,yAxy, A R，R為實(shí)數(shù)集合為實(shí)數(shù)集合 DB=| x,yBx整除整除y, B Z+, Z+為非為非0整數(shù)集整數(shù)集 R =| x,yAx y, A是集合族是集合族.類似的還可以定義大于等于關(guān)系類似的還可以定義大于等于關(guān)系, 小于關(guān)系小于關(guān)系, 大于大于關(guān)系關(guān)系, 真包含關(guān)系等等真包含關(guān)系等等. 18實(shí)例實(shí)例例如例如 A =

13、1, 2, 3, B =a, b, 則則 LA=, DA=, A=P(B)=,a,b,a,b, 則則 A上的包含關(guān)系是上的包含關(guān)系是 R =, ,19關(guān)系的表示關(guān)系的表示表示方式：關(guān)系的集合表達(dá)式、關(guān)系矩陣、關(guān)系圖表示方式：關(guān)系的集合表達(dá)式、關(guān)系矩陣、關(guān)系圖 關(guān)系矩陣關(guān)系矩陣：若若A=x1, x2, , xm，B=y1, y2, , yn，R是從是從A到到B的關(guān)系，的關(guān)系，R的關(guān)系矩陣是布爾矩陣的關(guān)系矩陣是布爾矩陣MR = rij m n, 其中其中 rij = 1 R. 關(guān)系圖關(guān)系圖：若若A= x1, x2, , xm，R是從是從A上的關(guān)系，上的關(guān)系，R的關(guān)系圖是的關(guān)系圖是GR=, 其中其中

14、A為結(jié)點(diǎn)集，為結(jié)點(diǎn)集，R為邊集為邊集.如果如果屬于關(guān)系屬于關(guān)系R，在圖中就有一條從，在圖中就有一條從 xi 到到 xj 的有向邊的有向邊. 注意：注意：A, B為有窮集，關(guān)系矩陣適于表示從為有窮集，關(guān)系矩陣適于表示從A到到B的的關(guān)系或者關(guān)系或者A上的關(guān)系，關(guān)系圖適于表示上的關(guān)系，關(guān)系圖適于表示A上的關(guān)系上的關(guān)系 20實(shí)例實(shí)例A=1,2,3,4, R=,R的關(guān)系矩陣的關(guān)系矩陣MR和關(guān)系圖和關(guān)系圖GR如下：如下： 0010000011000011RM21n基本運(yùn)算定義基本運(yùn)算定義定義域、值域、域定義域、值域、域逆、合成、限制、像逆、合成、限制、像n基本運(yùn)算的性質(zhì)基本運(yùn)算的性質(zhì)n冪運(yùn)算冪運(yùn)算定義定義

15、求法求法性質(zhì)性質(zhì)4.2 關(guān)系的運(yùn)算關(guān)系的運(yùn)算22關(guān)系的基本運(yùn)算定義關(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 23關(guān)系的基本運(yùn)算定義（續(xù)）關(guān)系的基本運(yùn)算定義（續(xù)）定義定義 設(shè)設(shè)F、G為任意的關(guān)系，為任意的關(guān)系，A為集合，則為集合，則逆逆與與合成合成 F 1 = | F F G = | | z ( G F) 例例2 R=, , , S=, , , , R 1=, , , S R

16、 =, , R S =, , , 24合成運(yùn)算的圖示方法合成運(yùn)算的圖示方法 利用圖示（不是關(guān)系圖）方法求合成利用圖示（不是關(guān)系圖）方法求合成 R S=, , , S R =, , R SS R25限制與像限制與像定義定義 F 在在A上的上的限制限制 F A = | xFy x A A 在在F下的下的像像 FA = ran(F A) 實(shí)例實(shí)例 R=, , , R 1=, R1=2,4 R = R1,2=2,3,4注意：注意：F A F, FA ranF 26例例.設(shè)設(shè)F、G是是N上的關(guān)系，其定義為上的關(guān)系，其定義為 F=x,y N y=x2 G =x,y N y=x+1求求G 1、F G 、 G

17、 F、 F 1,2、F1,2解：解：G 1= y,x N y=x+1 G 1=, , 對(duì)任何對(duì)任何x N有有 y=z2=(x+1)2，所以，所以 F G= x,y N y =(x+1)2 G F= x,y N y =x2+1 F 1,2=, F 1,2=ran(F 1,2)=1,427例.設(shè)F=,求F F、 F a、Fa解：解：F F=F a=A= aFA = ran(F A)=ran=a28關(guān)系基本運(yùn)算的性質(zhì)關(guān)系基本運(yùn)算的性質(zhì) 定理定理4.1 設(shè)設(shè)F是任意的關(guān)系是任意的關(guān)系, 則則(1) (F 1) 1=F(2) domF 1=ranF, ranF 1=domF證證 (1) 任取任取, 由逆

18、的定義有由逆的定義有 (F 1) 1 F 1 F所以有所以有 (F 1) 1=F (2) 任取任取x, xdomF 1 y(F 1) y(F) xranF 所以有所以有domF 1= ranF. 同理可證同理可證 ranF 1 = domF.29 (3) (F G) H=F (G H) (4) (F G) 1= G 1 F 1 證證 (3) 任取任取, (F G) H t( H F G) t ( H s (G) F) ) t s ( H G F) s (F t (HG) s (FG H) F (G H) 所以所以 (F G) H = F (G H)關(guān)系基本運(yùn)算的性質(zhì)（續(xù)）關(guān)系基本運(yùn)算的性質(zhì)（續(xù)

19、） 30 (4) 任取任取, (F G) 1 F G t ( G (t,x) F) t ( F 1 (t,y) G 1) G 1 F 1 所以所以 (F G) 1 = G 1 F 1 關(guān)系基本運(yùn)算的性質(zhì)（續(xù)）關(guān)系基本運(yùn)算的性質(zhì)（續(xù)） 31關(guān)系基本運(yùn)算的性質(zhì)（續(xù)）關(guān)系基本運(yùn)算的性質(zhì)（續(xù)） 定理定理4.2 設(shè)設(shè)F 、G、 H為任意的二元關(guān)系，則有：為任意的二元關(guān)系，則有：1. F (G H ) =F G F H2. (G H ) F = G F H F(合成運(yùn)算對(duì)合成運(yùn)算對(duì) 運(yùn)算滿足分配律）運(yùn)算滿足分配律）3. F (G H ) F G F H4. (G H ) F G F H F(合成運(yùn)算對(duì)合成

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

21、相加采用邏輯加其中相加采用邏輯加. 例例3 設(shè)設(shè)A=a,b,c,d, R=, 求求R的各次冪的各次冪, 分別用矩陣和關(guān)系圖表示分別用矩陣和關(guān)系圖表示.解解 R與與R2的關(guān)系矩陣分別為的關(guān)系矩陣分別為 0000100001010010M 0000000010100101000010000101001000001000010100102M34同理，同理，R0=IA, R3和和R4的矩陣分別是：的矩陣分別是：因此因此M4=M2, 即即R4=R2. 因此可以得到因此可以得到R2=R4=R6=, R3=R5=R7=對(duì)于有窮集對(duì)于有窮集A，A上關(guān)系上關(guān)系R的不同冪只有有限個(gè)。的不同冪只有有限個(gè)。 0000000010100101,000000000101101043MM 10000100