chapter4_12(1) (1)

1、1 集合論集合論2集合論部分集合論部分第第3章章 集合的基本概念和運算集合的基本概念和運算第第4章章 二元關系和函數(shù)二元關系和函數(shù)3 第四章第四章 二元關系與函數(shù)二元關系與函數(shù)44.1 集合的笛卡兒積和二元關系集合的笛卡兒積和二元關系l 有序對有序對l 笛卡兒積及其性質笛卡兒積及其性質l 二元關系的定義二元關系的定義l 二元關系的表示二元關系的表示5定義定義4.1 由兩個元素由兩個元素 x 和和 y，按照一定的順序組成的，按照一定的順序組成的 二元組稱為二元組稱為有序對有序對，記作，記作.例例1：點的坐標點的坐標. 有序對性質有序對性質 有序性有序性 (當當x y時時) 與與 相等的充分必要條

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

3、B A . 2) A=, 計算計算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笛卡兒積的性質笛卡兒積的性質不適合

4、交換律不適合交換律 A B B A (A B, A, B)不適合結合律不適合結合律 (A B) C A (B C) (A, B,C)對于并或交運算滿足分配律對于并或交運算滿足分配律 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中有一個為空集，則中有一個為空集，則A B就是空集就是空集. A=B= 若若|A|=m, |B|=n, 則則 |A B|=mn 13性質的證明性質的證明證明證明: A (B C)=(A B) (A C)證證: 任取任取 A(BC) xAyBC x

5、A(yByC) (xAyB)(xAyC) ABAC (AB)(AC) 所以有所以有A(BC) = (AB)(AC).14練習練習 解：解： (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 如果一個集合滿足以下條件之一：如果一個集合滿足以下條件之一： (1)集合非空集合非空, 且它的元素都是有序對且它的元素都是

6、有序對 (2)集合是空集集合是空集則稱該集合為一個則稱該集合為一個二元關系二元關系, 簡稱為簡稱為關系關系，記作，記作R.如如R, 可記作可記作 xRy；如果；如果 R, 則記作則記作x y二元關系的定義二元關系的定義R 例例6：R=, S=,a,b. R是二元關系是二元關系, 當當a, b不是有序對時，不是有序對時，S不是二元關系不是二元關系根據(jù)上面的記法，可以寫根據(jù)上面的記法，可以寫 1R2, aRb, a c 等等. R 16從從A到到B的關系與的關系與A上上的關系的關系定義定義4.6 設設A,B為集合為集合, AB的任何子集所定義的任何子集所定義的二元關系叫做的二元關系叫做從從A到到B

7、的二元關系的二元關系, 當當A=B時則時則叫做叫做 A上的二元關系上的二元關系.17從從A到到B的關系與的關系與A上上的關系的關系例例7： A=0,1, B=1,2,3, R1=, R2=AB, R3=, R4=. 那么那么 R1, R2, R3, R4是從是從 A到到 B的二元關系的二元關系, R3和和R4同同時也是時也是 A上的二元關系上的二元關系. 計數(shù)計數(shù)|A|=n, |AA|=n2, AA的子集有的子集有 個個. 所以所以 A上上有有 個不同的二元關系個不同的二元關系. 例例8：若若 |A|=3, 則則 A上有上有29=512個不同的二元關系個不同的二元關系. 22n22n18A上重

8、要關系的實例上重要關系的實例設設 A 為任意集合，為任意集合，是是 A 上的關系，稱為上的關系，稱為空關系空關系EA, IA 分別稱為分別稱為全域關系全域關系與與恒等關系恒等關系，定義如下：，定義如下： EA=|xAyA=AA IA=|xA例例9：設設A=1,2, 求求EA、IA。解：解：EA=, IA=,.19A上重要關系的實例上重要關系的實例(續(xù)續(xù))小于等于關系小于等于關系 LA, 整除關系整除關系DB, P(A)上的上的包含關系包含關系R 定義：定義： LA=| x,yAxy, A R，R為實數(shù)集合為實數(shù)集合 DB=| x,yBx整除整除y, B Z*, Z*為非為非0整數(shù)集整數(shù)集 R

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

10、陣是布爾矩陣MR = rij m n, 其中其中 rij = 1 R. 22關系的表示關系的表示p關系圖關系圖：若：若A= x1, x2, , xm，R是是A上的關系，上的關系，R 的關系圖是的關系圖是GR=, 其中其中A為結點為結點 集，集，R為邊集為邊集.如果如果屬于關系屬于關系R，在，在 圖中就有一條從圖中就有一條從 xi 到到 xj 的有向邊的有向邊. 注意：注意：A, B為有窮集，關系矩陣適于表示從為有窮集，關系矩陣適于表示從A到到B的的 關系或者關系或者A上的關系，關系圖適于表示上的關系，關系圖適于表示A上的上的 關系。關系。23實例實例A=1,2,3,4, R=,R的關系矩陣的關

11、系矩陣MR和關系圖和關系圖GR如下：如下：0010000011000011RM例例1124l基本運算定義基本運算定義l定義域、值域、域定義域、值域、域l逆、合成、限制、像逆、合成、限制、像l基本運算的性質基本運算的性質l冪運算冪運算l定義定義l求法求法l性質性質4.2 關系的運算關系的運算25關系的運算關系的運算域域定義定義4.8 關系關系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 設設A=a，b，c，d，e，B=1，2，3， R=，求，求R的的 定義域和值域。定義域和值域。關系的運算關系的運算域域解解 : domR = a，b，c， ranR = 2，3。27關系的運算關系的運算域域例例14 分別求以下關系的定義域和值域。分別求以下關系的定義域和值域。 (1) 1,Rx y x yZxy(2) 222,1Rx y x yZxy(3) 3,2Rx y x yZyx(4) 4,3Rx y x yZxy28關系的運算關系的運算域域22domran0,1, 1RR解：解： 11domranRRZ3domRZ3ran |2Rt tkkZ 即偶數(shù)集 44dom

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

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

15、=， R =，求，求R S圖解圖解,如圖所示：如圖所示：R S = ， 。36例例18 設設R，S都是都是A上的關系，上的關系，A=1，2，3，4。S=，R=，即，即R為為A上的恒等上的恒等關系，則關系，則R S=S R= S 。求求R S關系圖關系圖,如圖所示：如圖所示：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關系基本運算的性質關系基本運算的性質 定理定理1 設設F、G、H是任意的關系是任意的關系, 則則 (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關系基本運算的性質關系基本運算的性質 證明：證明：(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關系基本運算的性質關系基本運算的性質(續(xù)續(xù))定理定理2 設設F F、G G、H H為任意的關系，則有為任意的關系，則有 （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上關系的冪運算上關系的冪運算設設R為為A上的關系上的關系, n為自然數(shù)為自然數(shù), 則

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

19、別用矩陣和關系圖表 示示.44冪的求法冪的求法解解 R與與R2的關系矩陣分別為：的關系矩陣分別為： 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,的關系圖如下圖所示的關系圖如下圖所示冪的求法冪的求法(續(xù)續(xù))47冪運算的性質冪運算的性質定理定理3 設設A為為n元集元集, R是是A上的關系上的關系, 則存在自然則存在自然數(shù)數(shù) s 和和 t, 使得使得 Rs = Rt.22n證明：證明：R為為A上的關系上的關系, 由于由于|A|=n, A上的不同關上的不