離散數(shù)學(xué)-二元關(guān)系與運(yùn)算-專業(yè)數(shù)學(xué)教材.ppt

《離散數(shù)學(xué)-二元關(guān)系與運(yùn)算-專業(yè)數(shù)學(xué)教材.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)-二元關(guān)系與運(yùn)算-專業(yè)數(shù)學(xué)教材.ppt（61頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

二元關(guān)系和運(yùn)算 第四章 1 二元有序組 由兩個(gè)元素x和y按一定順序排成二元組 記作 4 1二元關(guān)系的概念 如 平面直角坐標(biāo)系中點(diǎn)的坐標(biāo) 一 二元關(guān)系的概念 二元有序組的性質(zhì) 1 當(dāng)x y時(shí) 2 當(dāng)且僅當(dāng)x u y v 1 2 說明有序組區(qū)別于集合 n元有序組 由n個(gè)元素x1 x2 xn 按一定順序排成的n元組 記作 x1 x2 xn 2 一種新的集合運(yùn)算 積運(yùn)算 設(shè)A B為兩集合 用A中元素為第一元素 B中元素作為第二元素構(gòu)成的二元有序組的全體叫做A和B的笛卡兒積 記作 A B 符號(hào)化 A B x A y B 例4 1設(shè)A a b B 0 1 2 求A B B A 解 根據(jù)笛卡兒積的定義知 A B B A 一般地 如果 A m B n 則 A B B A mn 積運(yùn)算的性質(zhì) 1 若A B中有一個(gè)空集 則笛卡兒積是空集 即 B A 2 當(dāng)A B 且A B都不是空集時(shí) 有A B B A 3 當(dāng)A B C都不是空集時(shí) 有 A B C A B C 因?yàn)?A B C中的元素 z 而A B C 中的元素為 4 A B C A B A C 對(duì) 的分配律 B C A B A C A A B C A B A C B C A B A C A 我們證明 A B C A B A C 證明思想 要證明兩個(gè)集合相等 通常有兩種方法 一是證兩個(gè)集合相互包含 二是利用已有的集合運(yùn)算的性質(zhì) 算律和已證明過的公式 仿照代數(shù)恒等式的證明方法 一步步從左 右 邊推出右 左 邊 或從左 右邊分別推出同一個(gè)集合式子 一般說來 最基本的集合相等關(guān)系要用第一種證法 比較復(fù)雜的集合相等關(guān)系用第二種方法更好 但第二種方法的使用取決于我們對(duì)算律和常用公式的熟練程度 證明 用第一種方法 對(duì)于任意的 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 例4 2設(shè)A 1 2 求P A A 解 P A A 1 2 1 2 n階笛卡兒積 x1 x2 xn x1 A1 x2 A2 xn An A1 A2 An 1 2 二元關(guān)系 如果一個(gè)集合的元素都是二元有序組 則這個(gè)集合稱為一個(gè)二元關(guān)系 記作 R 如果 R 記作xRy 3 二元關(guān)系的數(shù)學(xué)定義 從A到B的二元關(guān)系 設(shè)A B為集合 A B的任何子集所定義的二元關(guān)系叫做從A到B的二元關(guān)系 若A B 叫做A上的二元關(guān)系 若 A n 則 A A n2 就是說 A上有個(gè)不同的二元關(guān)系 其中包括空關(guān)系 全域關(guān)系UA和恒等關(guān)系IA A A的所有子集有個(gè) 例4 3設(shè)A a b 寫出P A 上的包含關(guān)系R 解 P A a b a b R A上關(guān)系的表示法 1 關(guān)系矩陣 設(shè)A x1 x2 xn R是A上的關(guān)系 則 rij nxn 是R的關(guān)系矩陣 令 二 二元關(guān)系的表示方法 2 關(guān)系圖 以E xi A xj A xiRxj 為有向邊集組成的有向圖G 以V A x1 x2 xn 為頂點(diǎn)集 卡盟排行榜卡盟 MicrosoftOfficePowerPoint 是微軟公司的演示文稿軟件 用戶可以在投影儀或者計(jì)算機(jī)上進(jìn)行演示 也可以將演示文稿打印出來 制作成膠片 以便應(yīng)用到更廣泛的領(lǐng)域中 利用MicrosoftOfficePowerPoint不僅可以創(chuàng)建演示文稿 還可以在互聯(lián)網(wǎng)上召開面對(duì)面會(huì)議 遠(yuǎn)程會(huì)議或在網(wǎng)上給觀眾展示演示文稿 MicrosoftOfficePowerPoint做出來的東西叫演示文稿 其格式后綴名為 ppt pptx 或者也可以保存為 pdf 圖片格式等 例4 4設(shè)A 1 2 3 4 R 是A上的關(guān)系 試寫出R的關(guān)系矩陣并畫出關(guān)系圖 解 關(guān)系矩陣 0011 0000 0100 關(guān)系圖 4 2關(guān)系的運(yùn)算 關(guān)系R的定義域 domR x y R 即R中有序組的第一個(gè)元素構(gòu)成的集合 關(guān)系R的值域 ranR y x R 即R中有序組的第二個(gè)元素構(gòu)成的集合 一 關(guān)系的定義域與值域 例4 5下列關(guān)系都是整數(shù)集Z上的關(guān)系 分別求出它們的定義域和值域 1 R1 x y Z x y 2 R2 x y Z x2 y2 1 3 R3 x y Z y 2x 4 R4 x y Z x y 3 解 domR1 ranR1 Z 解 R2 domR2 ranR2 1 R1 x y Z x y 2 R2 x y Z x2 y2 1 解 domR3 Z ranR3 偶數(shù) 解 domR4 ranR4 3 R3 x y Z y 2x 4 R4 x y Z x y 3 二 關(guān)系的常用運(yùn)算 F是任意關(guān)系 F的逆F 1 yFx F G是任意兩個(gè)關(guān)系 F與G的合成記作 F G z xGz zFy 關(guān)系F在集A上的限制 記作 F A xFy x A 集A在關(guān)系F下的象F A ran F A 1 逆 2 合成 3 限制 4 象 例4 6設(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中的元素就是 G 1 為了求F G 可以先直觀表示如下 對(duì)任何x N 即y x 1 2 因此F G x y N y x 1 2 同理可求G F 自己做 發(fā)現(xiàn)F G G F F 1 2 F 1 2 ran F 1 2 1 4 關(guān)系運(yùn)算的性質(zhì) 設(shè)F G H 為任意關(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 5 F G H F G F H 對(duì) 的分配律 6 F G H F G F H 對(duì) 的半分配律 7 G H F G F H F 8 G H F G F H F 任取 F G 1 F G z G F z G 1 F 1 G 1 F 1 4 F G 1 G 1 F 1的證明 任取 F G H z G H F z G H F 注意對(duì)括號(hào)的順序 z G F H F F G F H F G H F G F H 5 F G H F G F H的證明 4 3關(guān)系的性質(zhì) R的關(guān)系矩陣 主對(duì)角線元素全是1 R的關(guān)系圖 每個(gè)頂點(diǎn)都有環(huán) 自反性 x A有 R R是A上的關(guān)系 關(guān)系矩陣 主對(duì)角線元素全是0 關(guān)系圖 每個(gè)頂點(diǎn)都沒有環(huán) 反自反性 x A R 對(duì)稱性 若 R 則 R 關(guān)系矩陣 對(duì)稱陣 關(guān)系圖 如果兩個(gè)頂點(diǎn)之間有邊 一定是一對(duì)方向相反的邊 反對(duì)稱性 若 R且x y 則 R 關(guān)系矩陣 如果rij 1 且i j 則rji 0 關(guān)系圖 如果兩個(gè)頂點(diǎn)之間有邊 一定是只有一條有向邊 傳遞性 若 R且 R 則 R 關(guān)系圖 如果頂點(diǎn)xi到xj有邊 xj到xk有邊 則從xi到xk有邊 例4 7設(shè)A 1 2 10 對(duì)于A上的關(guān)系R x y 3 I I為整數(shù)集 問R有哪些性質(zhì) 解 逐條性質(zhì)加以驗(yàn)證R x y 3 I 任取A中元素x 由于 x x 3 0 所以R是自反的 又設(shè)A中任意兩個(gè)元素x y 如果xRy 即x y可被3整除 則y x也一定可被3整除 即yRx 從而R是對(duì)稱的 如果A中三個(gè)元素x y z滿足xRy yRz 則x y y z被3整除 由于x z x y y z 所以x z被3整除 從而xRz即R具有傳遞性 4 4關(guān)系的閉包運(yùn)算 閉包 設(shè)R A A 自反閉包記作r R 對(duì)稱閉包記作s R 傳遞閉包記作t R 由A求r R s R t R 的過程叫閉包運(yùn)算 那么 包含R而使之具有自反性質(zhì)的最小關(guān)系 稱之為R的自反閉包 包含R而使之具有對(duì)稱性質(zhì) 傳遞性質(zhì) 的最小關(guān)系 稱之為R的對(duì)稱 傳遞 閉包 一 定義 冪運(yùn)算 設(shè)R A A k N 約定 1 R0 IA x A 2 R1 R 3 Rk 1 Rk R 顯然Rm Rn Rm n Rm n Rmn 二 計(jì)算方法 為了有效地計(jì)算關(guān)系R的各種閉包 先引進(jìn)關(guān)系的冪運(yùn)算概念 閉包運(yùn)算的方法 設(shè)R是A上的任一關(guān)系 則 1 r R R IA 2 s R R R 3 t R R R2 R3 Rn 矩陣形式 M為R的關(guān)系矩陣 1 Mr M E 2 Ms M M M 是M的轉(zhuǎn)置 3 Mt M M2 M3 其中 均表示 邏輯加 例4 8設(shè)A a b c d A上的關(guān)系 求r R s R 和t R 解 r R R IA R R 三 實(shí)例 s R R R t R R R2 R3 R 而R2 R R R3 R2 R R4 R3 R 實(shí)際上 看到當(dāng)k 4時(shí) 已有R4 R R2 R3 故t R R R2 R3 四 閉包運(yùn)算的性質(zhì) 設(shè)A是有限集且 A n R A A 則 4 6等價(jià)關(guān)系和偏序關(guān)系 等價(jià)關(guān)系 集A上的關(guān)系R是自反的 對(duì)稱的和傳遞的 等價(jià)類 R是集A上的等價(jià)關(guān)系 對(duì)于任一a A a R x aRx x A 被稱為a的等價(jià)類 即A中所有和a有R關(guān)系的元素的集合 一 等價(jià)關(guān)系及用途 等價(jià)類的性質(zhì) R是非空集合 對(duì)任意的x y A 下面的結(jié)論成立 1 x 且 x A 等價(jià)類為A的子集 2 若xRy 則 x y 3 若x Ry 則 x y 集A在等價(jià)關(guān)系R下的商集 設(shè)R為非空集A上的等價(jià)關(guān)系 以R的不交的等價(jià)類為元素的集合叫做A在R下的商集 記作A R 即 A R x R x A 集A的劃分 設(shè)A是非空集合 1 2 中任意兩個(gè)元素不交 3 中所有元素的并集為A 則 為A的劃分 如果存在一個(gè)A的子集族 P A 滿足以下條件 由等價(jià)類的性質(zhì)和商集的定義可知 商集A R是A的劃分 稱之為由R誘導(dǎo)的劃分 反過來 給定A的任一劃分 則A被分割成若干個(gè)劃分塊 若定義A上的二元關(guān)系R x y A且x y屬 的同一塊 則xRy 那么R是A上的等價(jià)關(guān)系 稱之為由 誘導(dǎo)的等價(jià)關(guān)系 集A上的等價(jià)關(guān)系與劃分是一一對(duì)應(yīng)的 例4 9設(shè)A 1 2 3 求出A上所有的等價(jià)關(guān)系 解 先求A的各種劃分 只有1個(gè)劃分塊的劃分 1 具有兩個(gè)劃分塊的劃分 2 3 和 4 具有3個(gè)劃分塊 5 1 A 2 1 2 3 4 3 1 2 3 2 1 3 5 1 2 3 設(shè)對(duì)應(yīng)于劃分 i的等價(jià)關(guān)系Ri i 1 2 5 則有 R5 R1 R2 R3 R4 偏序關(guān)系 集A上的關(guān)系R是自反的 反對(duì)稱的和傳遞的 記作 且稱 A 為偏序集 二 偏序關(guān)系及用途 例4 10設(shè)A 2 4 6 8 A上關(guān)系R是通常意義下的小于或等于關(guān)系 試寫出R并驗(yàn)證它是偏序關(guān)系 解 R 1 自反性 2 反對(duì)稱性 3 傳遞性 均屬于R 對(duì)任意的 R 必有x y 當(dāng)x y時(shí) y x 從而 R 對(duì)任意的 R R 由于x y y z 所以x z 從而 R 例4 11設(shè)C a b a b C上關(guān)系T是集合的 包含于 試寫出T 并驗(yàn)證它是偏序關(guān)系 解 同例4 10類似 自己做 偏序集的哈斯圖 1 用小圓圈表示偏序集的元素 稱為結(jié)點(diǎn) 2 按每個(gè)元素在偏序中的次序從底向上列結(jié)點(diǎn)位置 3 對(duì)于偏序集中任意兩個(gè)元素x和y 如果x y且不存在另一個(gè)元素a 使x a a y 則在x與y兩結(jié)點(diǎn)之間劃上一杠 即 x在下 y在上 全序關(guān)系 設(shè)是偏序集 x y x A y A x y y x 成立 則稱 A 為全序集 這時(shí)的偏序關(guān)系叫全序關(guān)系 全序集 A 中全部元素可以排序 它的哈斯圖為一條直線 如果 偏序集中的一些特殊元素 設(shè)是偏序集 B A 1 如果 y B 使得 x x B y x 為真 則y是B的最小元 小于 B中所有元 2 如果 y B 使得 x x B x y 為真 則y是B的最大元 大于 B中所有元 4 若 y B 使得 x x B x y 則稱y是B的極大元 B中沒有比y大的其他元 5 若 y A 使得 x x B x y 為真 則稱y是B的上界 3 若 y B 使得 x x B x y 則稱y是B的極小元 B中找不到x小于y 6 若 y A 使得 x x B y x 為真 則稱y是B的下界 7 令C y y為B的上界 則稱C的最小元為B的上確界或最小上界 8 令D y y為B的下界 則D的最大元為B的下確界或最大下界 例4 12畫出和的哈斯圖 并指出其中的特殊元 解 1 的哈斯圖如下 由圖可知1為最小元 沒有最大元 7 8 9 10 11 12均為極大元 極小元為1 1為 1 2 12 的下界 也是下確界 1 2 12 中沒有上確界或上界 2 的哈斯圖如下 P a b c a b c a b a c b c a b c 由圖可知 為P a b c 的最小元 a b c 為它的最大元 同時(shí) a b c 也分別為它們的極小元和極大元 下確界和上確界 a b c d e 例4 13已知偏序集的哈斯圖如下 h g f 試寫出對(duì)應(yīng)的A和A上的偏序關(guān)系R 并指出A中的特殊元 解 A a b c d e f g h 直接由哈斯圖可知 A中沒有最小元和最大元 e g和h均為A的極大元 a b f和h均為A的極小元 沒有上確界和下確界 R a b c d e h g f 小結(jié)與學(xué)習(xí)要求 了解二元關(guān)系的定義和表示方法 熟練掌握關(guān)系的性質(zhì)和運(yùn)算 特別是復(fù)合和三種閉包運(yùn)算 理解等價(jià)關(guān)系和偏序關(guān)系 明確它們?cè)诿枋鲅芯繉?duì)象的結(jié)構(gòu)和特點(diǎn)時(shí)重要作用 即分類和覆蓋 它們?cè)谟?jì)算機(jī)科學(xué)中有重要應(yīng)用