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

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

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