[理學(xué)]第二章關(guān)系(編輯修改稿)
2024-11-15 01:00 本頁面
【文章內(nèi)容簡介】 稱的、傳遞的 )且 R’’?R，則必有 R’’?R’. 通常用 r(R)表示 R的自反閉包 s(R)表示 R的對稱閉包 t(R)表示 R的傳遞閉包 關(guān)系上的閉包運算 ? 例： 整數(shù)集 Z上的“ ”關(guān)系的自反閉包是“ ≤”關(guān)系；對稱閉包是“ ≠”關(guān)系；傳遞閉包是它本身。 ? 定理： – 設(shè) R是集合 X上的關(guān)系，則 r(R)=RUQ，其中 Q={(x,x) | x∈ X} s(R)=RU t(R)= =RUR2UR3U… 設(shè) X是有限集，并設(shè) X有 n個元素，則 t(R)= R1Rii??1Rn ii? 關(guān)系上的閉包運算 ? 例 ：設(shè)集合 A={a,b,c,d}，定義R={(a,b),(b,a),(b,c),(c,d)}，求 r(R)， s(R)， t(R) ? 解： r(R)=RUQ ={(a,a),(b,b),(c,c),(a,b),(b,a),(b,c),(c,d)} s(R)=RU ={(a,b),(b,a),(b,c),(c,b),(c,d),(d,c)} t(R)=RUR2UR3UR4 ={(a,b),(b,a),(b,c),(c,d)} U {(a,a),(a,c),(b,b),(b,d)} U {(a,b),(a,d),(b,a),(b,c)} U {(a,a),(a,c),(b,b),(b,d)} ={(a,a),(b,b),(a,b),(a,c),(a,d),(b,a),(b,c),(b,d),(c,d)} R 關(guān)系上的閉包運算 ? 例：設(shè)有 X上的關(guān)系 R1,R2, 且 R1?R2,試證 1) r(R1)?r(R2) 2) s(R1)?s(R2) 3) t(R1)?t(R2) ? 證明： 1) 因為 R1?R2, 所以 R1∪ E?R2∪ E, 即 r(R1)=r(R2) 2) 因為 R1?R2, 所以 所以 , 即 s(R1)=s(R2) 3) 對任意的 n∈ N, 根據(jù)數(shù)學(xué)歸納法可知： 又因為 t(R)=RUR2UR3U…, 所以 t(R1)?t(R2) 12RR?1 1 2 2R R R R? ? ?11 2 2R R R Rnn? ? ? 關(guān)系上的閉包運算 ? 集合 A上的二元關(guān)系 R的閉包運算可以 復(fù)合 ，例如 ts(R)=t(s(R))表示 R的對稱閉包的傳遞閉包，可以簡稱為 R的對稱傳遞閉包。 tsr(R)則表示 R的自反對稱傳遞閉包。 ? 定理： 設(shè) R是集合 A的二元關(guān)系，則有 1) 如果 R是自反的，那么 s(R)和 t(R)也是自反的； 2) 如果 R是對稱的，那么 r(R)和 t(R)也是對稱的； 3) 如果 R是傳遞的，那么 r(R)也是傳遞的 4) rs(R)=st(R) 5) rt(R)=tr(R) 6) ts(R)?st(R) 次序關(guān)系 ? 定義 – 集合 X上的關(guān)系 R如果是自反的、反對稱的、傳遞的，則稱 R在 X上是 偏序 的或稱 R是集合 X上的偏序關(guān)系。而稱集合 X為 R的 偏序集 用(X,R)表示 . – 一般用符號“ ≤”表示偏序 (有時我們用 x＜ y表示 x≤y,且 x≠y) ? 例： – 由集合 A所組成的冪集 ρ(A)上的關(guān)系“ ?”是自反的、反對稱的，又是傳遞的，所以它是偏序的 次序關(guān)系 ? 可比： 在偏序集合 (A,≤)中，元素 x,y∈ A，如果 x≤y或y≤x， x與 y是可比的，否則稱它們是不可比的 . ? 蓋?。? 在偏序集合 (A,≤)中，元素 x,y∈ A， x＜ y且沒有其他元素 z∈ A滿足 x＜ z＜ y，稱 y蓋住 X. (A, ≤)上的蓋住集 CovA定義為 CovA={(x,y)∣ x,y∈ A， y蓋住 x} ? 例 ：集合 A={a,b,c}，偏序集合 (ρ(A), ?)中，判斷A的以下子集是否蓋住 {a}? ? 1) 216。 2) {b,c} 3) {a,b} 4) {a,b,c} 次序關(guān)系 ? 定義 – 集合 X上的關(guān)系 R如果是反自反的、傳遞的，則稱 R在 X上是 擬序 的或稱 R是集合 X上的 擬序關(guān)系 . – 一般用符號“ ＜ ”表示擬序 ? 例： ? 由集合 A所組成的冪集 ρ(A)上的關(guān)系“ ?”是擬序的 次序關(guān)系 ? 定理： – 如果集合 X上的關(guān)系 R是擬序的，則其必是反對稱的 ? 偏序是擬序的擴充而擬序是偏序的縮減 ? 定理： – 設(shè) R是集合 X上的關(guān)系 1)如果 R是一個擬序關(guān)系，則 r(R)=RUQ是一個片序關(guān)系 2)如果 R是一個偏序關(guān)系，則 RQ是一個擬序關(guān)系 次序關(guān)系 ? 定義
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1