[工學(xué)]二元關(guān)系ii(已修改)
2024-10-30 23:45 本頁面
【正文】 二元關(guān)系 關(guān)系的閉包 ?閉包的定義 ?閉包的構(gòu)造方法 ?閉包的性質(zhì) ?閉包的相互關(guān)系 閉包的定義 定義 設(shè) R是非空集合 A上的關(guān)系， R的 自反 （ 對稱 或 傳遞 ） 閉包是 A上的關(guān)系 R′ ， 使得 R′ 滿足以下條件： （ 1） R′ 是 自反 的（ 對稱 的或 傳遞 的） （ 2） R?R′ （ 3） 對 A上任何包含 R的 自反 （ 對稱 或 傳遞 ）關(guān)系 R″ 有 R′ ? R″ 。 一般將 R的 自反閉包 記作 r(R)， 對稱閉包 記作 s(R)， 傳遞閉包 記作 t(R)。 ?設(shè) A={a,b,c,d}, R={a,b,b,a, b,c,c,d},則 R和 r(R),s(R),t(R)分別是什么？ 閉包的構(gòu)造方法 定理 設(shè) R為 A上的關(guān)系，則有 （ 1） r(R)＝ R∪ R0 （ 2） s(R)＝ R∪ R1 （ 3） t(R)＝ R∪ R2∪R 3∪ … 證明思路 (1)和 (2)：證明右邊的集合滿足閉包定義的三個(gè)條件。 (3) 采用集合相等的證明方法。 證明左邊包含右邊，即 t(R)包含每個(gè) Rn。 證明右邊包含左邊，即 R∪ R2∪ … 具有傳遞的 性質(zhì)。 推論 推論 設(shè) R為有窮集 A上的關(guān)系，則存在正整數(shù) r使得 t(R)=R∪R 2∪ … ∪R r 證明 由定理 (3)得證。 例題 求整數(shù)集合 Z上的關(guān)系 R＝ {a,b | ab}的自反閉包和對稱閉包。 解答 r(R)＝ R∪R 0＝ {a,b|ab}∪{a,b|a ＝ b} ＝ {a,b|a?b} s(R)＝ R∪R 1＝ {a,b|ab}∪{b,a|ab} ＝ {a,b|a≠b} 通過關(guān)系矩陣求閉包的方法 設(shè)關(guān)系 R， r(R)， s(R)， t(R)的關(guān)系矩陣分別為 M， Mr， Ms和Mt， 則 Mr ＝ M＋ E 對角線上的值都改為 1 Ms ＝ M＋ M′ 若 aij＝ 1， 則令 aji＝ 1 Mt ＝ M＋ M2＋ M3＋ … 沃舍爾算法 其中 E是和 M同階的單位矩陣， M′ 是 M的轉(zhuǎn)置矩陣。 注意在上述等式中矩陣的元素相加時(shí)使用邏輯加。 通過關(guān)系圖求閉包的方法 設(shè)關(guān)系 R， r(R)， s(R)， t(R)的關(guān)系圖分別記為 G， Gr， Gs，Gt， 則 Gr， Gs， Gt的頂點(diǎn)集與 G的頂點(diǎn)集相等。 除了 G的邊以外，以下述方法 添加新的邊 。 1)考察 G的每個(gè)頂點(diǎn)，如果 沒有環(huán)就加上一個(gè)環(huán) 。最終得到的是 Gr。 2) 考察 G的每一條邊， 如果有一條 xi到 xj的單向邊 ， i≠j ， 則在 G中 加一條邊 xj到 xi的反方向邊 。最終得到 Gs。 3) 考察 G的每個(gè)頂點(diǎn) xi， 找出從 xi出發(fā)的所有 2步， 3步， … ， n步長的路徑 （ n為 G中的頂點(diǎn)數(shù)）。 設(shè)路徑的終點(diǎn)為 。 如果沒有從 xi到 (l=1,2,… ,k)的邊，就加上這條邊。當(dāng)檢查完所有的頂點(diǎn)后就得到圖 Gt。 k21 jjj x,x,x ?Ijx例 設(shè) A={a,b,c,d}， R={a,b,b,a,b,c,c,d,d,b}， 則 R和 r(R)， s(R)， t(R)的關(guān)系圖如下圖所示。其中 r(R)， s(R)，t(R)的關(guān)系圖就是使用上述方法直接從 R的關(guān)系圖得到的。 閉包的主要性質(zhì) 定理 設(shè) R是非空集合 A上的關(guān)系，則 （ 1） R是自反的當(dāng)且僅當(dāng) r(R)＝ R。 （ 2） R是對稱的當(dāng)且僅當(dāng) s(R)＝ R。 （ 3） R是傳遞的當(dāng)且僅當(dāng) t(R)＝ R。 證明 （ 1）充分性。 因?yàn)?R＝ r(R)， 所以 R是自反的。 必要性。 顯然有 R ? r(R)。 由于 R是包含 R的自反關(guān)系，根據(jù)自反閉包定義有 r
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1