離散數(shù)學集合的笛卡兒積與二元關系.ppt

《離散數(shù)學集合的笛卡兒積與二元關系.ppt》由會員分享，可在線閱讀，更多相關《離散數(shù)學集合的笛卡兒積與二元關系.ppt（38頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1 第4章二元關系與函數(shù) 4 1集合的笛卡兒積與二元關系4 2關系的運算4 3關系的性質(zhì)4 4關系的閉包4 5等價關系和偏序關系4 6函數(shù)的定義和性質(zhì)4 7函數(shù)的復合和反函數(shù) 2 4 1集合的笛卡兒積和二元關系 有序?qū)Φ芽▋悍e及其性質(zhì)二元關系的定義二元關系的表示 3 有序?qū)?定義由兩個元素x和y 按照一定的順序組成的二元組稱為有序?qū)?記作實例 平面直角坐標系中點的坐標有序?qū)π再|(zhì)1 有序性 當x y時 2 與相等的充分必要條件是 x u y v 例1 求x y 解3y 4 2 x 5 y y 2 x 3 4 有序n元組 定義一個有序n n 3 元組是一個有序?qū)?其中第一個元素是一個有序n 1元組 即 xn 實例 空間直角坐標系中的坐標n維向量是有序n元組 當n 1時 形式上可以看成有序1元組 5 笛卡兒積 定義設A B為集合 用A中元素為第一個元素 B中元素為第二個元素 構成有序?qū)?所有這樣的有序?qū)M成的集合叫做A與B的笛卡兒積記作A B 即A B x A y B 例2A 1 2 3 B a b c A B B A A P A A 6 笛卡兒積的性質(zhì) 不適合交換律A B B A A B A B 不適合結合律 A B C A B C A B 對于并或交運算滿足分配律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 7 性質(zhì)的證明 證明A B C A B A C 證任取 A B C x A y B C x A y B y C x A y B x A y C A B A C A B A C 所以有A B C A B A C 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 2 不一定 反例如下 A 1 B 2 C D 10 例5設A B C D為任意集合 判斷以下等式是否成立 說明為什么 A B C D A C B D A B C D A C B D A B C D A C B D A B C D A C B D 解 1 成立 因為對任意的 A B C D x A B y C Dx A x B y C y D A C B D 11 2 A B C D A C B 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 設A1 A2 An是集合 n 2 它們的n階笛卡爾積記作A1 A2 An 其中A1 A2 An x1 A1 x2 A2 xn An 當A1 A2 An時 可將它們的n階笛卡爾積記作An例如 A a b 則A3 13 二元關系 集合中兩個元素之間的某種關系例1甲 乙 丙3個人進行乒乓球比賽 任何兩個人之間都要比賽一場 假設比賽結果是乙勝甲 甲勝丙 乙勝丙 比賽結果可表示為 其中表示x勝y 它表示了集合 甲 乙 丙 中元素之間的一種勝負關系 例2有A B C3個人和四項工作G1 G2 G3 G4 已知A可以從事工作G1和G4 B可以從事工作G3 C可以從事工作G1和G2 那么 人和工作之間的對應關系可以記作R C G2 它表示了集合 A B C 到工作 G1 G2 G3 G4 之間的關系 14 二元關系的定義 定義如果一個集合滿足以下條件之一 1 集合非空 且它的元素都是有序?qū)?2 集合是空集則稱該集合為一個二元關系 簡稱為關系 記作R 如 R 可記作xRy 如果 R 則記作xy實例 R S a b R是二元關系 當a b不是有序?qū)r S不是二元關系根據(jù)上面的記法 可以寫1R2 aRb ac等 15 從A到B的關系與A上的關系 定義設A B為集合 A B的任何子集所定義的二元關系叫做從A到B的二元關系 當A B時則叫做A上的二元關系 例4A 0 1 B 1 2 3 R1 R2 A B R3 R4 那么R1 R2 R3 R4是從A到B的二元關系 R3和R4同時也是A上的二元關系 計數(shù) A n A A n2 A A的子集有個 所以A上有個不同的二元關系 例如 A 3 則A上有 512個不同的二元關系 16 A上重要關系的實例 設A為任意集合 是A上的關系 稱為空關系EA IA分別稱為全域關系與恒等關系 定義如下 EA x A y A A A IA x A 例如 A 1 2 則 EA IA 17 A上重要關系的實例 續(xù) 小于等于關系LA 整除關系DA 包含關系R 定義 LA x y A x y A R R為實數(shù)集合DB x y B x整除y B Z Z 為非0整數(shù)集R x y A x y A是集合族 類似的還可以定義大于等于關系 小于關系 大于關系 真包含關系等等 18 實例 例如A 1 2 3 B a b 則 LA DA A P B a b a b 則A上的包含關系是R 19 關系的表示 表示方式 關系的集合表達式 關系矩陣 關系圖關系矩陣 若A x1 x2 xm B y1 y2 yn R是從A到B的關系 R的關系矩陣是布爾矩陣MR rij m n 其中rij 1 R 關系圖 若A x1 x2 xm R是從A上的關系 R的關系圖是GR 其中A為結點集 R為邊集 如果屬于關系R 在圖中就有一條從xi到xj的有向邊 注意 A B為有窮集 關系矩陣適于表示從A到B的關系或者A上的關系 關系圖適于表示A上的關系 20 實例 A 1 2 3 4 R R的關系矩陣MR和關系圖GR如下 21 基本運算定義定義域 值域 域逆 合成 限制 像基本運算的性質(zhì)冪運算定義求法性質(zhì) 4 2關系的運算 22 關系的基本運算定義 定義域 值域和域domR x y R ranR y x R fldR domR ranR例1R 則 domR 1 2 4 ranR 2 3 4 fldR 1 2 3 4 23 關系的基本運算定義 續(xù) 定義設F G為任意的關系 A為集合 則逆與合成F 1 F F G z G F 例2R S R 1 S R R S 24 合成運算的圖示方法 利用圖示 不是關系圖 方法求合成R S S R R S S R 25 限制與像 定義F在A上的限制F A xFy x A A在F下的像F A ran F A 實例R R 1 R 1 2 4 R R 1 2 2 3 4 注意 F A F F A ranF 26 例 設F G是N上的關系 其定義為F x y N y x2 G x y N y x 1 求G 1 F G G F F 1 2 F 1 2 解 G 1 y x N y x 1 G 1 對任何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 4 27 例 設F 求F F F a F a 解 F F F a A a F A ran F A ran a 28 關系基本運算的性質(zhì) 定理4 1設F是任意的關系 則 1 F 1 1 F 2 domF 1 ranF ranF 1 domF證 1 任取 由逆的定義有 F 1 1 F 1 F所以有 F 1 1 F 2 任取x x domF 1 y F 1 y F x ranF所以有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 H G s F G H F G H 所以 F G H F G H 關系基本運算的性質(zhì) 續(xù) 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 關系基本運算的性質(zhì) 續(xù) 31 關系基本運算的性質(zhì) 續(xù) 定理4 2設F G H為任意的二元關系 則有 F G H F G F H G H F G F H F 合成運算對 運算滿足分配律 3 F G H F G F H4 G H F G F H F 合成運算對 運算分配后是包含關系 32 A上關系的冪運算 設R為A上的關系 n為自然數(shù) 則R的n次冪定義為 1 R0 x A IA 2 Rn Rn 1 R n 1注意 對于A上的任何關系R1和R2都有R10 R20 IA對于A上的任何關系R都有R1 R 33 冪的求法 1 對于集合表示的關系R 計算Rn就是n個R左復合 2 矩陣表示就是n個矩陣相乘 其中相加采用邏輯加 例3設A a b c d R 求R的各次冪 分別用矩陣和關系圖表示 解R與R2的關系矩陣分別為 34 同理 R0 IA R3和R4的矩陣分別是 因此M4 M2 即R4 R2 因此可以得到 R2 R4 R6 R3 R5 R7 對于有窮集A A上關系R的不同冪只有有限個 冪的求法 續(xù) 35 R0 R1 R2 R3 的關系圖如下圖所示 冪的求法 續(xù) 36 冪運算的性質(zhì) 定理3設A為n元集 R是A上的關系 則存在自然數(shù)s和t 使得Rs Rt 證R為A上的關系 由于 A n A上的不同關系只有個 當列出R的各次冪R0 R1 R2 必存在自然數(shù)s和t使得Rs Rt 37 定理4設R是A上的關系 m n N 則 1 Rm Rn Rm n 2 Rm n Rmn證用歸納法 1 對于任意給定的m N 施歸納于n 若n 0 則有 Rm R0 Rm IA Rm Rm 0假設Rm Rn Rm n 則有 Rm Rn 1 Rm Rn R Rm Rn R Rm n 1 所以對一切m n N有Rm Rn Rm n 冪運算的性質(zhì) 續(xù) 38 接上頁證明 2 對于任意給定的m N 施歸納于n 若n 0 則有 Rm 0 IA R0 Rm 0假設 Rm n Rmn 則有 Rm n 1 Rm n Rm Rmn Rm Rmn m Rm n 1 所以對一切m n N有 Rm n Rmn 冪運算的性質(zhì) 續(xù)