離散第四章二元關(guān)系小結(jié).ppt

《離散第四章二元關(guān)系小結(jié).ppt》由會員分享，可在線閱讀，更多相關(guān)《離散第四章二元關(guān)系小結(jié).ppt（63頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第四章二元關(guān)系小結(jié) 第四章二元關(guān)系 本章討論的關(guān)系 主要是二元關(guān)系 它仍然是一種集合 但它是比前一章更為復(fù)雜的集合 關(guān)系是笛卡爾乘積的子集 它的元素是有序二元組的形式 這些有序二元組中的兩個元素來自于兩個不同或者相同的集合 因此 關(guān)系是建立在其它集合基礎(chǔ)之上的集合 關(guān)系中的有序二元組反映了不同集合中元素與元素之間的關(guān)系 或者同一集合中元素之間的關(guān)系 本章首先討論關(guān)系的基本表達形式 然后給出關(guān)系的運算 最后討論幾種常用的關(guān)系 2 63 4 1關(guān)系的基本概念 定義 設(shè)且為n個任意集合 a 稱R為間的n元關(guān)系 b 若n 2 則稱R為A1到A2的二元關(guān)系 c 若 則稱R為空關(guān)系 若 則稱R為全關(guān)系 d 若 則稱R為A上的n元關(guān)系 一 關(guān)系的定義 3 63 二 關(guān)系的相等 定義 設(shè)R1為A1 A2 An間的n元關(guān)系 R2為B1 B2 Bm間的m元關(guān)系 如果 1 n m 2 若 則 3 把R1和R2作為集合看 R1 R2 則稱n元關(guān)系R1和m元關(guān)系R2相等 記作R1 R2 4 63 4 2關(guān)系的性質(zhì) 定義 設(shè)R為A上的二元關(guān)系 1 若對每個 皆有 則稱R為自反的 用式子來表述即是 R是自反的 2 若對每個 皆有 則稱R為反自反的 用式子來表述即是 R是反自反的 5 63 4 2關(guān)系的性質(zhì) 3 對任意的 若 則 就稱R為對稱的 用式子來表述即是 R是對稱的 4 對任意的 若且 則x y 就稱R為反對稱的 用式子來表述即是 R是反對稱的 6 63 4 2關(guān)系的性質(zhì) 7 63 集合的壓縮和開拓 定義 設(shè)R為集合A上的二元關(guān)系且 則稱S上的二元關(guān)系為R在S上的壓縮 記為 并稱R為在A上的開拓 定理 設(shè)R為A的二元關(guān)系且 那么 1 若R是自反的 則也是自反的 2 若R是反自反的 則也是反自反的 3 若R是對稱的 則也是對稱的 4 若R是反對稱的 則也是反對稱的 5 若R是可傳遞的 則也是可傳遞的 8 63 4 3關(guān)系的表示 定義 設(shè)A和B為任意的非空有限集 R為任意一個從A到B的二元關(guān)系 以中的每個元素為結(jié)點 對每個皆畫一條從x到y(tǒng)的有向邊 這樣得到的一個圖稱為關(guān)系R的關(guān)系圖 一 關(guān)系圖 例 A 1 2 4 B 3 5 6 關(guān)系R 9 63 二 關(guān)系矩陣 例 設(shè)A 1 2 3 4 R為定義在A上的二元關(guān)系 R 寫出關(guān)系矩陣 10 63 4 4關(guān)系的運算 注意 由于關(guān)系也是特殊的集合 因此集合的運算也適用于關(guān)系中 設(shè)R1和R2是從A到B的二元關(guān)系 那么 也是從A到B的二元關(guān)系 它們分別被稱為二元關(guān)系R1和R2的交 并 差分和對稱差分 11 63 4 4關(guān)系的運算 定義 設(shè)R是從X到Y(jié)的關(guān)系 S是從Y到Z的關(guān)系 于是可用R S表示從X到Z的關(guān)系 通常稱它是R和S的合成關(guān)系 用式子表示即是 一 關(guān)系的合成 例 給定集合X 1 2 3 4 Y 2 3 4 和Z 1 2 3 設(shè)R是從X到Y(jié)的關(guān)系 并且S是從Y到Z的關(guān)系 并且R和S給定成 試求R和S的合成關(guān)系 并畫出合成關(guān)系圖給出合成關(guān)系的關(guān)系矩陣 12 63 一 關(guān)系的合成 定理 給定集合X Y Z和W 設(shè)R1是從X到Y(jié)的關(guān)系 R2和R3是Y到Z的關(guān)系 R4是從Z到W的關(guān)系 于是有 13 63 一 關(guān)系的合成 合成運算是對關(guān)系的二元運算 使用這種運算 能夠由兩個關(guān)系生成一個新的關(guān)系 對于這個新的關(guān)系又可進行合成運算 從而生成其它關(guān)系 定理 設(shè)R1是從X到Y(jié)的關(guān)系 R2是從Y到Z的關(guān)系 R3是從Z到W的關(guān)系 于是有 14 63 關(guān)系的冪 定義 如果R1是從X1到X2的關(guān)系 R2是從X2到的X3關(guān)系 Rn是從Xn到Xn 1的關(guān)系 則無括號表達式表達了從X1到Xn 1的關(guān)系 當X1 X2 Xn 1和R1 R2 Rn時 也就是說當集合X中的所有Ri都是同樣的關(guān)系時 X中的合成關(guān)系可表達成Rn 并稱作關(guān)系R的冪 定義 給定集合X R是X中的二元關(guān)系 設(shè) 于是R的n次冪Rn可定義成 15 63 關(guān)系的冪 定理 給定集合X R是X中的二元關(guān)系 設(shè) 于是可有 例 給定集合X a b c R1 R2 R3 R4是X中的關(guān)系 并給定 給出這些關(guān)系的各次冪 16 63 關(guān)系的冪 定理 設(shè)X是含有n個元素的有限集合 R是X中的二元關(guān)系 于是存在這樣的s和t 能使 證明 集合X中的每一個二元關(guān)系都是的子集 X有n個元素 有n2個元素 有個元素 每一個元素都是的一個子集 也是一種二元關(guān)系 因而 在X中有個不同的二元關(guān)系 所以 不同的二元關(guān)系R的冪不會多于個 但是序列中有項 因此這些的方冪中至少有兩個是相等的 證畢 17 63 二 合成關(guān)系的矩陣表達和圖解 設(shè)集合X x1 x2 xm Y y1 y2 yn Z z1 z2 zp R是從X到Y(jié)的關(guān)系 S是從Y到Z的關(guān)系 MR和MS第i行第j列的元素分別是aij和bij 它們是0或者1 則合成關(guān)系關(guān)系矩陣上的元素為 定義布爾運算 0 0 0 1 0 0 1 1 1 11 1 1 0 1 1 0 0 0 0對兩個關(guān)系矩陣求其合成時 其運算法則與一般矩陣的乘法是相同的 但其中的加法運算和乘法運算應(yīng)改為布爾加和布爾乘 18 63 三 關(guān)系的求逆運算 關(guān)系R的逆關(guān)系定義如下 對于所有的和逆關(guān)系的關(guān)系矩陣 原關(guān)系矩陣轉(zhuǎn)置逆關(guān)系的關(guān)系圖 原關(guān)系圖中顛倒弧線上箭頭的方向 19 63 三 合成關(guān)系的求逆運算 定理 設(shè)R是從集合X到Y(jié)的關(guān)系 S是從集合Y到Z的關(guān)系 于是有 證明 對于任何 和來說 如果xRy和ySz 則會有和 因為還有和 所以又有 因此可有 利用關(guān)系矩陣也可以理解 的轉(zhuǎn)置和是一樣的 20 63 四 關(guān)系的閉包運算 閉包的定義 給定集合X R是X中的二元關(guān)系 如果有另一個關(guān)系滿足 1 是自反的 對稱的 可傳遞的 2 3 對于任何自反的 對稱的 可傳遞的 關(guān)系 如果 則 則稱關(guān)系為R的自反的 對稱的 可傳遞的 閉包 并用r R 表示的R自反閉包 用s R 表示R的對稱閉包 用t R 表示R的可傳遞閉包 21 63 四 關(guān)系的閉包運算 定理 給定集合X R是X中的關(guān)系 于是可有 a 當且僅當 R才是自反的 b 當且僅當 R才是對稱的 c 當且僅當 R才是傳遞的 證明 僅給出 a 的證明過程如果是R自反的 則R具有定義給出的應(yīng)具備的全部性質(zhì) 因此有 反之 如果 則由定義的 1 得R是自反的 22 63 四 關(guān)系的閉包運算 定理 設(shè)X是任意集合 R是X中的二元關(guān)系 IX是X中的恒等關(guān)系 于是可有 在整數(shù)集合中 小于關(guān)系 的自反閉包是 恒等關(guān)系IX的自反閉包是IX 不等關(guān)系 的自反閉包是全域關(guān)系 空關(guān)系的自反閉包是恒等關(guān)系 23 63 四 關(guān)系的閉包運算 定理 給定集合X R是X中的二元關(guān)系 于是可有 在整數(shù)集合中 小于關(guān)系 的對稱閉包是不等關(guān)系 小于或等于關(guān)系 的對稱閉包是全域關(guān)系 恒等關(guān)系IX的對稱閉包是IX 不等關(guān)系 的對稱閉包是不等關(guān)系 24 63 四 關(guān)系的閉包運算 定理 給定集合X R是X中的二元關(guān)系 于是可有 當A是有限集時 A上只有有限個不同的關(guān)系 因此 存在某個正整數(shù)m 使得 事實上 可以證明 若 則 25 63 四 關(guān)系的閉包運算 定理 設(shè)X是集合 R是X中的二元關(guān)系 于是有 1 如果R是自反的 那么s R t R 也是自反的 2 如果R是對稱的 那么r R t R 也是對稱的 3 如果R是可傳遞的 那么r R 也是可傳遞的 26 63 四 關(guān)系的閉包運算 定理 設(shè)X是集合 R是集合中的二元關(guān)系 于是有 證明 27 63 這一部分介紹了關(guān)系的一般概念 即關(guān)系是笛卡爾的子集 那關(guān)系就是集合 于是集合上理論可以推廣到關(guān)系上來 注意集合的相等和關(guān)系的相等有一點區(qū)別 關(guān)系的相等還要求定義域要相等 我們還介紹了關(guān)系的表示方法 集合表示法 關(guān)系圖表示法 關(guān)系矩陣表示法 集合上的運算可以平移到關(guān)系上來 除此之外關(guān)系還有它獨特的運算 復(fù)合運算 求逆運算和閉包運算 28 63 我們學(xué)習了關(guān)系性質(zhì)的形式化定義法 設(shè) 是定義在X上的二元關(guān)系自反的 x x R R是反自反的 x x R R是不自反的 x x X R y y X R R是對稱的 x y x y X R R R是反對稱的 x y x y X R R x y 29 63 R是不對稱的 x y x X y X R R z w z X w X R R R是傳遞的 x y z x y z X R R R R是不可傳遞的 x y z x y z X R R R 30 63 第二部分是關(guān)于特殊關(guān)系的4 5特殊關(guān)系 一 集合的劃分和覆蓋 定義 給定非空集合S 設(shè)非空集合A A1 A2 An 如果有 則稱集合A是集合S的覆蓋 注意 集合的覆蓋不唯一 例如 S a b c A a b b c B a b c A和B都是集合S的覆蓋 31 63 定義 給定非空集合S 設(shè)非空集合A A1 A2 An 如果有 則稱集合A是集合S的一個劃分 劃分中的元素Ai稱為劃分的類 劃分的類的數(shù)目叫劃分的秩 劃分是覆蓋的特定情況 即覆蓋中元素互不相交的特定情況 32 63 一 集合的劃分和覆蓋 定義 設(shè)A和A 是非空集合S的兩種劃分 并可以表示成 如果A 的每一個類Aj 都是A的某一個類Ai的子集 那么稱劃分A 是劃分A的加細 并稱A 加細了A 如果A 是A的加細并且A A 則稱A 是A的真加細 33 63 極小項 完全交集 定義 劃分全集E的過程 可看成是在表達全集的文氏圖上劃出分界線的過程 設(shè)A B C是全集E的三個子集 由A B和C生成的E的劃分的類 稱為極小項或完全交集 n個子集生成2n個極小項 用表示 34 63 一 集合的劃分和覆蓋 定理 由全集E的n個子集A1 A2 An所生成的全部極小項集合 能夠構(gòu)成全集E的一個劃分 證明 證明這個定理 只需證明全集E中的每一個元素 都僅屬于一個完全交集就夠了 如果 則 或 或 或 由此可見 定有 這里或是Ai或是 Ai 試考察兩個不同的完全交集T 因為兩個完全交集是不同的 就是說存在這樣一個i 使得和 因此可有 即 因而任何一個都不能同時屬于兩個不同的完全交集 35 63 二 等價關(guān)系 定義 設(shè)X是任意集合 R是集合中的二元關(guān)系 如果R是自反的 對稱的和可傳遞的 則稱R是等價關(guān)系 即滿足以下幾點 如果R是集合X中的等價關(guān)系 則R的域是集合X自身 所以 稱R是定義于集合X中的關(guān)系 例如數(shù)的相等關(guān)系是任何數(shù)集上的等價關(guān)系 又例如一群人的集合中姓氏相同的關(guān)系也是等價關(guān)系 但朋友關(guān)系不是等價關(guān)系 因為它不可傳遞 36 63 元素的等價 設(shè)R是集合A上的等價關(guān)系 若元素aRb 則稱a與b等價 或稱b與a等價 定義 設(shè)m是個正整數(shù) 如果對于某一個整數(shù)n 有x y n m 則稱x模m等價于y 并記作 整數(shù)m稱為等價的模數(shù) 表示模m等價關(guān)系R 37 63 二 等價關(guān)系 定理 任何集合中的模m相等關(guān)系 是一個等價關(guān)系 證明 設(shè)R是任何集合中的模m相等價關(guān)系 如果X 則R是個空關(guān)系 顯然有是自反的 對稱的和可傳遞的 如果X 則需考察下列三條 1 對于任何來說 因為x x 0 m 所以有 因此 模m相等關(guān)系是自反的 2 對于任何來說 如果 則存在某一個 能使x y n m 于是可有y x n m 因此有 即模m相等關(guān)系是對稱的 3 設(shè) 和 于是存在 能使和 而 從而可有 即模m相等關(guān)系是可傳遞的 38 63 等價類 定義設(shè)是集合A上的等價關(guān)系 則A中等價于元素的所有元素組成的集合稱為生成的等價類 用表示 即 說明 簡單起見 有時候把 a R簡單寫作 a 39 63 等價類 例 設(shè)X a b c d R是X中的等價關(guān)系 并把R給定成 則 40 63 二 等價關(guān)系 定理 設(shè)R是非空集合X中的等價關(guān)系 R的等價類的集合 是X的一個劃分 定義 設(shè)R是非空集合X中的等價關(guān)系 R的各元素生成的等價類集合稱按R去劃分X的商集 記作X R 也可以寫成X modR 由定義可知 按R對集合X的劃分X R是一個集合 并且X R的基數(shù)是X的不同的R等價類的數(shù)目 因此X R的基數(shù)又稱為等價關(guān)系R的秩 41 63 特殊的等價關(guān)系 全域關(guān)系 令等價關(guān)系R1 XX 這里X的每一個元素與X的所有元素都有R1的關(guān)系 按R1劃分X的商集乃是集合 X 等價關(guān)系R1是全域關(guān)系 全域關(guān)系會造成集合X的最小劃分 恒等關(guān)系R X的每一個元素僅關(guān)系到它自身 而不關(guān)系到其它元素 顯然 R是個恒等關(guān)系 按R劃分X的商集 僅由單元素集合組成 恒等關(guān)系R會造成集合X的最大劃分 最大劃分和最小劃分均稱為X的平凡劃分 42 63 等價關(guān)系與集合的劃分 證明 要證明R是個等價關(guān)系 就必須證明R是自反的 對稱的和可傳遞的 a 由于C是X的劃分 C必定覆蓋X 對任意的 必有x屬于C的某一個元素S 所以對于每一個 都有xRx 即R是自反的 43 63 三 相容關(guān)系 定義 給定集合X中的二元關(guān)系R 如果R是自反的 對稱的 則稱R是相容關(guān)系 記作 也就是說 可以把R規(guī)定成 顯然 所有的等價關(guān)系都是相容關(guān)系 但相容關(guān)系并不一定是等價關(guān)系 例如 設(shè)集合X 2166 243 375 648 455 X中的關(guān)系 可以看出R是自反的和對稱的 因此是一相容關(guān)系 44 63 最大相容類 定義 設(shè) 是集合中的相容關(guān)系 假定 如果任何一個 都與其它所有的元素有相容關(guān)系 而X A中沒有能與A中所有元素都有相容關(guān)系的元素 則子集稱為最大相容類 尋找最大相容類的方法 關(guān)系圖法關(guān)系矩陣法 45 63 四 次序關(guān)系 次序關(guān)系是集合中的可傳遞關(guān)系 它能提供一種比較集合各元素的手段 定義 設(shè)R是集合P中的二元關(guān)系 如果R是自反的 反對稱的和可傳遞的 亦即有 則稱R是集合P中的偏序關(guān)系 簡稱偏序 序偶稱為偏序集合 46 63 偏序關(guān)系 通常用符號 表示偏序 這樣 符號 就不單純意味著實數(shù)中的 小于或等于 關(guān)系 事實上 這是從特定情況中 借用符號 去表示更為普遍的偏序關(guān)系 對于偏序關(guān)系來說 如果有且x y 則按不同情況稱它是 小于或等于 包含 在之前 等等 如果R是集合P中的偏序關(guān)系 則也是P中的偏序關(guān)系 如上所述 如果用 表示R 則用 表示 如果是一個偏序集合 則也是一個偏序集合 稱是的對偶 47 63 偏序關(guān)系 例 設(shè)I 2 3 6 8 是I 中的 整除 關(guān)系 試表達出 整除 和 整倍數(shù) 關(guān)系 解 整除 關(guān)系 為 整倍數(shù) 關(guān)系是 實數(shù)集合R中的 小于 關(guān)系 都不是偏序關(guān)系 因為它們都不是自反的 但它們是實數(shù)集合中的另一種關(guān)系 擬序關(guān)系 48 63 擬序關(guān)系 定義 設(shè)R是集合X中的二元關(guān)系 如果R是反自反的和可傳遞的 亦即有 則稱R是擬序關(guān)系 并借用符號 表示 注意 在上述定義中 沒有明確列舉反對稱性的條件 事實上關(guān)系 若是反自反的和可傳遞的 則一定是反對稱的 否則會出現(xiàn)矛盾 這是因為 假定x y和y x 因為是可傳遞的 可得出x x 而R是反自反的 故總是反對稱的 49 63 擬序關(guān)系 擬序關(guān)系和偏序關(guān)系的關(guān)系 定理 設(shè)R是集合中的二元關(guān)系 于是可有 a 如果R是個擬序關(guān)系 則是一個偏序關(guān)系 b 如果R是個偏序關(guān)系 則R Ix是個擬序關(guān)系 50 63 全序關(guān)系 定義 設(shè)是個偏序集合 如果對于每一個 或者x y或者y x 亦即 則稱偏序關(guān)系 是全序關(guān)系 簡稱全序 序偶稱為全序集合 注意 P中具有全序關(guān)系的各元素 總能按線性次序x1 x2 排列起來 這里當且僅當i j 才有xi xj 故全序也稱為簡單序或線性序 因此 序偶在這種情況下也被稱為線性序集或鏈 51 63 字母次序關(guān)系 定義 設(shè)R是實數(shù)集合且P R R 假定R中的關(guān)系 是一般的 大于或等于 關(guān)系 對于P中的任何兩個序偶和 可以定義一個關(guān)系S 如果 則有 因此S是P中的全序關(guān)系 并稱它是字母次序關(guān)系或字母序 例如 52 63 字母次序關(guān)系 設(shè)R是X中的全序關(guān)系 并設(shè) 這個方程式說明 P是由長度小于或等于n的元素串組成的 假定n取某個固定值 可把長度為P的元素串看成是P重序元 這樣就可以定義P中的全序關(guān)系S 并稱它是字母次序關(guān)系 為此 設(shè)和是集合中的任何兩個元素 且有p q 為了滿足P中的次序關(guān)系 首先對兩個元素串進行比較 如果需要的話 把兩個元素串加以交換 使得q p 53 63 字母次序關(guān)系 如果要使 就必須滿足下列條件之一 如果上述條件中一個也沒有得到滿足 則應(yīng)有 54 63 五 偏序集合與哈斯圖 像表達相容關(guān)系時用簡化關(guān)系圖一樣 通常使用較為簡便的偏序集合圖 哈斯 Hass 圖來表達偏序關(guān)系 定義 設(shè)是一個偏序集 如果對任何 x y和x y 而且不存在任何其它元素能使x z和z y 即成立 則稱元素y蓋覆x 55 63 偏序集合與哈斯圖 在哈斯圖中 用小圈表示每個元素 如果有 且x y和x y 則把表示x的小圈畫在表示y的小圈之下 如果y蓋覆x 則在x和y之間畫上一條直線 如果x y和x y 但是y不蓋覆x 則不能把x和y直接用直線連結(jié)起來 而是要經(jīng)過P的一個或多個元素把它們連結(jié)起來 這樣 所有的邊的方向都是自下朝上 故可略去邊上的全部箭頭表示 56 63 偏序集合與哈斯圖 定義 設(shè)是一個偏序集合 并有 a 如果對于每一個元素有 則元素稱為Q的最小成員 通常記作0 b 如果對于每一個元素有 則元素稱為Q的最大成員 通常記作1 如果能畫出哈斯圖 就可以看出是否存在最大成員和最小成員 57 63 偏序集合與哈斯圖 定理 設(shè)X是一個偏序集合 且有 如果x和y都是Q的最小 最大 成員 則x y 證 假定x和y都是Q的最小成員 于是可有x y和y x 根據(jù)偏序關(guān)系的反對稱性 可以得出x y 當x和y都是Q的最大成員時 定理的證明類似于上述的證明 58 63 偏序集合與哈斯圖 定義 設(shè)是一個偏序集合 并有 極大成員和極小成員都不是唯一的 不同的極大成員 或不同的極小成員 是不可比的 a 如果 且不存在元素能使q q和q q 則稱q是Q的極小成員 b 如果 且不存在元素能使q q和q q 則稱q是Q的極大成員 59 63 偏序集合與哈斯圖 定義 設(shè)是一個偏序集合 并有 a 如果對于每一個元素有 則元素稱為Q的上界 b 如果對于每一個元素有 則元素稱為Q的下界 60 63 偏序集合與哈斯圖 定義 設(shè)是一個偏序集合 并有 如果是Q的一個上界 且對于Q的每一個上界q 都有q q 則稱q是Q的最小上界 通常記作LUB 如果是Q的一個下界 且對于Q的每一個下界q 都有q q 則稱q是Q的最大下界 通常記作GLB 如果存在最小上界的話 它是唯一的 如果存在最大下界的話 它也是唯一的 61 63 良序關(guān)系 定義 給定集合X R是X中的二元關(guān)系 如果R是個全序關(guān)系 且X的每一個非空子集都有一個最小成員 則稱R是個良序關(guān)系 與此對應(yīng) 序偶稱為良序集合 每一個良序集合必定是全序集臺 因為對于任何子集來說 其本身必定有一個元素是它的最小成員 但是每一個全序集合不一定都是良序的 有限全序集合必定是良序的 62 63 這一部分介紹了特殊關(guān)系的運算 滿足某些性質(zhì)就是特種關(guān)系 等價關(guān)系 劃分 相容關(guān)系 覆蓋 偏序關(guān)系 哈斯圖 63 63