chapter4_12(1) (1)

1、1 集合論集合論2集合論部分集合論部分第第3章章 集合的基本概念和運(yùn)算集合的基本概念和運(yùn)算第第4章章 二元關(guān)系和函數(shù)二元關(guān)系和函數(shù)3 第四章第四章 二元關(guān)系與函數(shù)二元關(guān)系與函數(shù)44.1 集合的笛卡兒積和二元關(guān)系集合的笛卡兒積和二元關(guān)系l 有序?qū)τ行驅(qū) 笛卡兒積及其性質(zhì)笛卡兒積及其性質(zhì)l 二元關(guān)系的定義二元關(guān)系的定義l 二元關(guān)系的表示二元關(guān)系的表示5定義定義4.1 由兩個(gè)元素由兩個(gè)元素 x 和和 y，按照一定的順序組成的，按照一定的順序組成的 二元組稱為二元組稱為有序?qū)τ行驅(qū)?，記作，記?例例1：點(diǎn)的坐標(biāo)點(diǎn)的坐標(biāo). 有序?qū)π再|(zhì)有序?qū)π再|(zhì) 有序性有序性 (當(dāng)當(dāng)x y時(shí)時(shí)) 與與 相等的充分必要條

2、件是相等的充分必要條件是 = x=u y=v有序?qū)τ行驅(qū)?有序有序 n 元組元組定義定義4.2 一個(gè)一個(gè)有序有序 n (n 3) 元組元組 是一個(gè)是一個(gè) 有序?qū)?，其中第一個(gè)元素是一個(gè)有序有序?qū)?，其中第一個(gè)元素是一個(gè)有序 n-1 元組，即元組，即 = , xn 當(dāng)當(dāng) n=1時(shí)時(shí), 形式上可以看成有序形式上可以看成有序 1 元組元組. 例例2: n 維向量是有序維向量是有序 n元組元組. 7笛卡兒積笛卡兒積定義定義 設(shè)設(shè)A,B為集合，為集合，A與與B 的的笛卡兒積笛卡兒積記作記作A B， 即即 A B = | x A y B 例例3: 1) A=1,2,3, B=a,b,c，計(jì)算，計(jì)算 A B、

3、B A . 2) A=, 計(jì)算計(jì)算P(A) A.8笛卡兒積笛卡兒積解：解：1） A B =, , B A =, , , 2） P(A) A=, 9例例4： (1) A=a，b，B=c，d，求，求AB。 (2) A=a，b，B=c，d，求，求BA。 (3) A=a,b,B=1,2,C=c, 求求(AB)C和和A(BC)。笛卡兒積笛卡兒積10解：解： lAB=a,bc,d=, 。(2) BA=c,da,b=, 。笛卡兒積笛卡兒積11(3) AB=a,b1,2=, 。(AB)C=,c, ,c, ,c, ,cBC=1，2c=，。 A(BC)=a,a, b, b, 12笛卡兒積的性質(zhì)笛卡兒積的性質(zhì)不適合

4、交換律不適合交換律 A B B A (A B, A, B)不適合結(jié)合律不適合結(jié)合律 (A B) C A (B C) (A, B,C)對(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 13性質(zhì)的證明性質(zhì)的證明證明證明: A (B C)=(A B) (A C)證證: 任取任取 A(BC) xAyBC x

5、A(yByC) (xAyB)(xAyC) ABAC (AB)(AC) 所以有所以有A(BC) = (AB)(AC).14練習(xí)練習(xí) 解：解： (1) 任取任取 A C x A y C x B y D B D 例例5： (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.15定義定義4.5 如果一個(gè)集合滿足以下條件之一：如果一個(gè)集合滿足以下條件之一： (1)集合非空集合非空, 且它的元素都是有序?qū)η宜脑囟际?/p>

6、有序?qū)?(2)集合是空集集合是空集則稱該集合為一個(gè)則稱該集合為一個(gè)二元關(guān)系二元關(guān)系, 簡(jiǎn)稱為簡(jiǎn)稱為關(guān)系關(guān)系，記作，記作R.如如R, 可記作可記作 xRy；如果；如果 R, 則記作則記作x y二元關(guān)系的定義二元關(guān)系的定義R 例例6：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ù)上面的記法，可以寫根據(jù)上面的記法，可以寫 1R2, aRb, a c 等等. R 16從從A到到B的關(guān)系與的關(guān)系與A上上的關(guān)系的關(guān)系定義定義4.6 設(shè)設(shè)A,B為集合為集合, AB的任何子集所定義的任何子集所定義的二元關(guān)系叫做的二元關(guān)系叫做從從A到到B

7、的二元關(guān)系的二元關(guān)系, 當(dāng)當(dāng)A=B時(shí)則時(shí)則叫做叫做 A上的二元關(guān)系上的二元關(guān)系.17從從A到到B的關(guān)系與的關(guān)系與A上上的關(guān)系的關(guān)系例例7： A=0,1, B=1,2,3, 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)系. 例例8：若若 |A|=3, 則則 A上有上有29=512個(gè)不同的二元關(guān)系個(gè)不同的二元關(guān)系. 22n22n18A上重

8、要關(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)系恒等關(guān)系，定義如下：，定義如下： EA=|xAyA=AA IA=|xA例例9：設(shè)設(shè)A=1,2, 求求EA、IA。解：解：EA=, IA=,.19A上重要關(guān)系的實(shí)例上重要關(guān)系的實(shí)例(續(xù)續(xù))小于等于關(guān)系小于等于關(guān)系 LA, 整除關(guān)系整除關(guān)系DB, P(A)上的上的包含關(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

9、=| x,yP(A)x y, A是集合族是集合族.類似的還可以定義大于等于關(guān)系類似的還可以定義大于等于關(guān)系, 小于關(guān)系小于關(guān)系, 大于關(guān)大于關(guān)系系, 真包含關(guān)系等等真包含關(guān)系等等. 20實(shí)例實(shí)例例例10：如如 A = 1, 2, 3, B =a, b, 則則 LA=, DA=, A=P(B)=,a,b,a,b, 則則 A上的包含關(guān)系是上的包含關(guān)系是 R =, ,21關(guān)系的表示關(guān)系的表示表示方式：表示方式：p關(guān)系的集合表達(dá)式：關(guān)系的集合表達(dá)式：p關(guān)系矩陣關(guān)系矩陣：若：若A=x1, x2, , xm， B=y1, y2, , yn， R是從是從A到到B的關(guān)系，的關(guān)系，R的關(guān)系矩陣是布爾矩陣的關(guān)系矩

10、陣是布爾矩陣MR = rij m n, 其中其中 rij = 1 R. 22關(guān)系的表示關(guān)系的表示p關(guān)系圖關(guān)系圖：若：若A= x1, x2, , xm，R是是A上的關(guān)系，上的關(guān)系，R 的關(guān)系圖是的關(guān)系圖是GR=, 其中其中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)系。23實(shí)例實(shí)例A=1,2,3,4, R=,R的關(guān)系矩陣的關(guān)

11、系矩陣MR和關(guān)系圖和關(guān)系圖GR如下：如下：0010000011000011RM例例1124l基本運(yùn)算定義基本運(yùn)算定義l定義域、值域、域定義域、值域、域l逆、合成、限制、像逆、合成、限制、像l基本運(yùn)算的性質(zhì)基本運(yùn)算的性質(zhì)l冪運(yùn)算冪運(yùn)算l定義定義l求法求法l性質(zhì)性質(zhì)4.2 關(guān)系的運(yùn)算關(guān)系的運(yùn)算25關(guān)系的運(yùn)算關(guān)系的運(yùn)算域域定義定義4.8 關(guān)系關(guān)系R的的定義域定義域、值域值域 和和域域分別是分別是 domR = x | y ( R) ranR = y | x ( R) fldR = domR ranR 例例12 R=, 則則 domR=1, 2, 4 ranR=2, 3, 4 fldR=1, 2, 3

12、, 4 26例例13 設(shè)設(shè)A=a，b，c，d，e，B=1，2，3， R=，求，求R的的 定義域和值域。定義域和值域。關(guān)系的運(yùn)算關(guān)系的運(yùn)算域域解解 : domR = a，b，c， ranR = 2，3。27關(guān)系的運(yùn)算關(guān)系的運(yùn)算域域例例14 分別求以下關(guān)系的定義域和值域。分別求以下關(guān)系的定義域和值域。 (1) 1,Rx y x yZxy(2) 222,1Rx y x yZxy(3) 3,2Rx y x yZyx(4) 4,3Rx y x yZxy28關(guān)系的運(yùn)算關(guān)系的運(yùn)算域域22domran0,1, 1RR解：解： 11domranRRZ3domRZ3ran |2Rt tkkZ 即偶數(shù)集 44dom

13、ran3, 3RR29關(guān)系的運(yùn)算關(guān)系的運(yùn)算域域例例15：A=1，2，3，4，B=5，6，7， R=，R的圖解如圖所示：的圖解如圖所示：domRranR30關(guān)系的運(yùn)算關(guān)系的運(yùn)算逆和合成逆和合成定義定義4.9 關(guān)系關(guān)系R的逆、的逆、關(guān)系關(guān)系R與關(guān)系與關(guān)系S的的合成合成定義為：定義為： R 1 = | R R S = | | z ( S R) 31關(guān)系的運(yùn)算關(guān)系的運(yùn)算逆和合成逆和合成例例16 設(shè)設(shè)R=, , , ， S=, , , , ， 求求R-1,R S,S R.R. 解：解：R R 1 1=, , , =, , , R R S S =, , , =, , , S S R R =, , =, ,

14、 32合成運(yùn)算的圖示方法合成運(yùn)算的圖示方法 利用圖示利用圖示(不是關(guān)系圖不是關(guān)系圖)方法求合成方法求合成R=, , , S=, , , , R S =, , , S R =, , 33逆和合成運(yùn)算的矩陣方法逆和合成運(yùn)算的矩陣方法0000000001101010RM0000011001000101SM00010010001100001RM0000000001100100RsM=MR*Ms，元元素和為邏輯素和為邏輯和。和。34例例 設(shè)設(shè)R，S關(guān)系為：關(guān)系為： R=, ， S=，, 求求S R。35合成運(yùn)算的圖示方法合成運(yùn)算的圖示方法例例17 A=1，2，3，4，B=3，5，7，C=1，2，3， S

15、=， R =，求，求R S圖解圖解,如圖所示：如圖所示：R S = ， 。36例例18 設(shè)設(shè)R，S都是都是A上的關(guān)系，上的關(guān)系，A=1，2，3，4。S=，R=，即，即R為為A上的恒等上的恒等關(guān)系，則關(guān)系，則R S=S R= S 。求求R S關(guān)系圖關(guān)系圖,如圖所示：如圖所示：R S = S R = S。124337限制與像限制與像定義定義4.9 F 在在A上的上的限制限制 F A = | xFy x A A 在在F下的下的像像 FA = ran(F A) 38限制與像限制與像例例19 R=, , , 求：求：R 1、R1、 R 、R1,2。 R 1=, R1=2,4 R = R1,2=2,3,4

16、注意：注意：F A F, FA ranF 39關(guān)系基本運(yùn)算的性質(zhì)關(guān)系基本運(yùn)算的性質(zhì) 定理定理1 設(shè)設(shè)F、G、H是任意的關(guān)系是任意的關(guān)系, 則則 (1) (F 1) 1=F (2) domF 1=ranF, ranF 1=domF (3) (F G) H=F (G H) (4) (F G) 1= G 1 F 1 40關(guān)系基本運(yùn)算的性質(zhì)關(guān)系基本運(yùn)算的性質(zhì) 證明：證明：(1) 任取任取, 由逆的定義有由逆的定義有 (F 1) 1 F 1 F 所以有所以有 (F 1) 1=F (2) 任取任取x, xdomF 1 y(F 1) y(F) xranF 所以有所以有domF 1= ranF. 同理可證同理

17、可證 ranF 1 = domF.41關(guān)系基本運(yùn)算的性質(zhì)關(guān)系基本運(yùn)算的性質(zhì)(續(xù)續(xù))定理定理2 設(shè)設(shè)F F、G G、H H為任意的關(guān)系，則有為任意的關(guān)系，則有 （1 1）F F (G(GH) = FH) = F G G F F H; H; （2) F2) F (G(GH) H) F F G G F F H;H; (3) (GH) (3) (GH) F = GF = G FHFH F; F; (4) (GH) (4) (GH) F F G G FHFH F F。P47: P47: 量詞分配等值式量詞分配等值式42A上關(guān)系的冪運(yùn)算上關(guān)系的冪運(yùn)算設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, n為自然數(shù)為自然數(shù), 則

18、則 R 的的 n次冪次冪定義為：定義為： (1) R0= | xA =IA (2) Rn+1 = Rn R 注意：注意： 對(duì)于對(duì)于A上的任何關(guān)系上的任何關(guān)系R1和和R2都有都有 R10 = R20 = IA 對(duì)于對(duì)于A上的任何關(guān)系上的任何關(guān)系 R 都有都有 R1 = R 43冪的求法冪的求法對(duì)于集合表示的關(guān)系對(duì)于集合表示的關(guān)系R，計(jì)算，計(jì)算 Rn ：1）關(guān)系圖表示，即）關(guān)系圖表示，即n個(gè)個(gè)R的復(fù)合，的復(fù)合，2）矩陣表示，即）矩陣表示，即n個(gè)矩陣相乘個(gè)矩陣相乘, 其中相加采用邏輯其中相加采用邏輯 加加. 例例20 設(shè)設(shè)A=a,b,c,d, R=, 求求R的各次冪的各次冪, 分別用矩陣和關(guān)系圖表分

19、別用矩陣和關(guān)系圖表 示示.44冪的求法冪的求法解解 R與與R2的關(guān)系矩陣分別為：的關(guān)系矩陣分別為： 0000100001010010M 0000000010100101000010000101001000001000010100102M45同理，同理，R0=IA, R3和和R4的矩陣分別是：的矩陣分別是：因此因此M4=M2, 即即R4=R2. 因此可以得到因此可以得到R2=R4=R6=, R3=R5=R7= 0000000010100101,000000000101101043MM 10000100001000010M冪的求法冪的求法(續(xù)續(xù))46R0, R1, R2, R3,的關(guān)系圖如下圖所示的關(guān)系圖如下圖所示冪的求法冪的求法(續(xù)續(xù))47冪運(yùn)算的性質(zhì)冪運(yùn)算的性質(zhì)定理定理3 設(shè)設(shè)A為為n元集元集, R是是A上的關(guān)系上的關(guān)系, 則存在自然則存在自然數(shù)數(shù) s 和和 t, 使得使得 Rs = Rt.22n證明：證明：R為為A上的關(guān)系上的關(guān)系, 由于由于|A|=n, A上的不同關(guān)上的不