關(guān)系的閉包運(yùn)算及偏序關(guān)系

關(guān)系的閉包運(yùn)算及偏序關(guān)系第一頁，共三十三頁，2022年，8月28日通過關(guān)系的一些運(yùn)算可以得到新的關(guān)系。對于A上的關(guān)系R,希望R具有某些有用的性質(zhì),如自反性，對稱性，傳遞性等。若R不具有想要的性質(zhì)，如自反性這種對給定的關(guān)系R用擴(kuò)充一些元素(有序?qū)?的辦法得到具有某些特殊性質(zhì)的新關(guān)系，就是閉包運(yùn)算。添加元素的原則是什么？第二頁，共三十三頁，2022年，8月28日1.自反閉包r(R)例設(shè)A={a,b,c},

R={(a,a),(b,a),(b,c),(c,a),(a,c)},求出所有包含R的自反關(guān)系。

R1=R

{(b,b),(c,c)};R2=R

{(b,b),(c,c),(a,b)};R3=R

{(b,b),(c,c),(c,b)};R4=R

{(b,b),(c,c),(a,b),(c,b)}.顯然R1稱為R的自反閉包.第三頁，共三十三頁，2022年，8月28日定義

設(shè)R

AA,稱最小的包含R的自反關(guān)系R為R的自反閉包,記為r(R)。R=r(R)滿足3個(gè)條件:(1)R是自反的(2)RR(3)設(shè)R是自反的且RR,則必有RR（R是最小的）第四頁，共三十三頁，2022年，8月28日定理2.1自反閉包r(R)的關(guān)系圖?第五頁，共三十三頁，2022年，8月28日2.對稱閉包s(R)定義

設(shè)R

AA,稱最小的包含R的對稱關(guān)系R為R的對稱閉包,記為s(R).s(R)滿足3個(gè)條件:(1)包含R；(2)對稱性；(3)最小性.第六頁，共三十三頁，2022年，8月28日定理2.2對稱閉包s(R)的關(guān)系圖?第七頁，共三十三頁，2022年，8月28日3.傳遞閉包t(R)定義設(shè)R

AA,稱最小的包含R的傳遞關(guān)系為R的傳遞閉包,記為t(R).

t(R)滿足3個(gè)條件:(1)包含R；(2)傳遞性；(3)最小性.第八頁，共三十三頁，2022年，8月28日例：整數(shù)集Z上的“”關(guān)系的自反閉包是“”關(guān)系,對稱閉包是“”；傳遞閉包是它自身。

例：設(shè)有S={1,2,3},且有S上的關(guān)系R如下：

R={(1,2),(1,3)}r(R)={(1,2),(1,3),(1,1),(2,2),(3,3)}s(R)={(1,2),(2,1),(1,3),(3,1)}t(R)={(1,2),(1,3)}=R第九頁，共三十三頁，2022年，8月28日例設(shè)A={a,b,c},R={(a,b),(b,c),(b,a)},求t(R).解t(R)={(a,b),(b,c),(b,a),(a,c),(a,a),(b,b)}.

由于(a,b),(b,c)R,要保證傳遞必須添加(a,c),但僅添加(a,c)是不夠的.因?yàn)閧(a,b),(b,c),(b,a),(a,c)}不傳遞.根據(jù)(a,b)和(b,a),還要加(a,a);根據(jù)(b,a)和(a,b),還要加(b,b),這時(shí){(a,b),(b,c),(b,a),(a,c),(a,a),(b,b)}傳遞了.

第十頁，共三十三頁，2022年，8月28日傳遞閉包t(R)的關(guān)系圖?第十一頁，共三十三頁，2022年，8月28日定理2.3

若|A|=n

1,

R

AA,則

第十二頁，共三十三頁，2022年，8月28日例：設(shè)有S={1,2,3}上的關(guān)系

R={(1,2),(2,3),(3,2),(3,3)}

試求r(R),s(R)與t(R)第十三頁，共三十三頁，2022年，8月28日可用圖示法：(a)R圖示123(b)r(R)圖示123(C)s(R)圖示123(d)t(R)圖示123圖2.10：關(guān)系R的r(R)、S(R)及t(R)圖示3第十四頁，共三十三頁，2022年，8月28日例:設(shè)A={a,b,c,d},R={(a,b),(b,a),(b,c),(c,d)},求t(R).解

第十五頁，共三十三頁，2022年，8月28日第十六頁，共三十三頁，2022年，8月28日閉包運(yùn)算與關(guān)系的性質(zhì)的聯(lián)系定理(1)R自反,則r(R),s(R)及t(R)自反.(2)R對稱,則r(R),s(R)及t(R)對稱.(3)R傳遞,則r(R),t(R)傳遞,s(R)不一定傳遞.第十七頁，共三十三頁，2022年，8月28日2.5兩種常用的關(guān)系次序關(guān)系三種次序關(guān)系：偏序關(guān)系、線性次序關(guān)系、擬序關(guān)系。

偏序關(guān)系—滿足自反性的次序關(guān)系,即滿足自反性、反對稱性及傳遞性。

擬序關(guān)系—滿足反自反性的次序關(guān)系,即滿足反自反性、反對稱性及傳遞性。

線性次序關(guān)系—所有元素均能順序排列的偏序關(guān)系。

第十八頁，共三十三頁，2022年，8月28日第2章關(guān)系

1.偏序

定義2.10：偏序關(guān)系：集合S上的關(guān)系R是自反的、反對稱的又是傳遞的,則稱R在S上是偏序的或稱R是S上的偏序關(guān)系并可記以(S,R)?？捎梅枺骸啊北硎酒?。

例：集合S所組成的冪集(S)上的關(guān)系：“”是自反的、反對稱及傳遞的,故它是偏序的。它可記為：((S),)。第十九頁，共三十三頁，2022年，8月28日2偏序集的Hasse圖(1)畫出偏序關(guān)系的關(guān)系圖(2)由于自反性每個(gè)點(diǎn)處都有環(huán),去掉環(huán)。(3)由于偏序關(guān)系的傳遞性,去掉由于傳遞出現(xiàn)的邊。(4)若xy將x放置于y之下。由于反對稱性圖中邊的方向是一致的，都是從下到上的方向，去掉箭頭。按這種方式得到的圖就是哈斯圖.第二十頁，共三十三頁，2022年，8月28日第2章關(guān)系例：(Z,)的哈斯圖可見圖2.11(a)

。例：S={2,3,6,12,24,36}上的整除關(guān)系R的哈斯圖可見圖2.11(b)。例：集合S={a,b,c}上的(S)所組成的((S),)的哈斯圖可見圖2.11(C)。第二十一頁，共三十三頁，2022年，8月28日第2章關(guān)系-4-3-2-101234(a)(Z,)的哈斯圖(b)(S,)的哈斯圖236122436{a}{c}{a,b}{a,c}{b,c}{a,b,c}(C)((S),)的哈斯圖圖2.11哈斯圖示例

第二十二頁，共三十三頁，2022年，8月28日第2章關(guān)系定義2.11：最大元素、最小元素、極大元素、極小元素：設(shè)有(X,)且集合YX,有yY：(1)對每個(gè)yY都有yy,則稱y是Y的最大元素；(2)對每個(gè)yY都有yy,則稱y是Y的最小元素；(3)不存在yY有yy且yy,則稱y是Y的極大元素；(4)不存在yY有yy且yy,則稱y是Y的極小元素；第二十三頁，共三十三頁，2022年，8月28日第2章關(guān)系

例：圖2.11(b)中(S,)的幾個(gè)重要元素：最大元素：無最小元素：無極大元素：24,36

極小元素：2,3

例：((S),)中(S)的幾個(gè)重要元素：最大元素：{a,b,c}

最小元素：極大元素：{a,b,c}

極小元素：第二十四頁，共三十三頁，2022年，8月28日存在性?(R,),S=Z?(P(X),),S=P(X)?AX.(Z+,|),S=Z+?1|x,S={2,4,6,12}?第二十五頁，共三十三頁，2022年，8月28日唯一性?定理若S存在最大(小)元,則唯一。證明：設(shè)a,b是S的最大元，所以有

a≤b且b≤a,由偏序的反對稱性質(zhì)，知a=b。同理可證最小元的唯一性。第二十六頁，共三十三頁，2022年，8月28日第2章關(guān)系

定義2.12：上界、上確界、下界、下確界：設(shè)有(X,)且集合YX,有xX：

(1)對每個(gè)yY均有yx,則稱x是Y的上界；

(2)對每個(gè)yY均有xy,則稱x是Y的下界；

(3)xX是Y的上界且對每個(gè)Y的上界x均有xx,則稱x是Y的上確界(即Y的最小上界)；

(4)xX是Y的下界且對每個(gè)Y的下界x均有xx,則稱x是Y的下確界(即Y的最大下界)

；

第二十七頁，共三十三頁，2022年，8月28日S={b,c,d,e}?S={a,b}?第二十八頁，共三十三頁，2022年，8月28日第2章關(guān)系例：((S),)中Y={{a,b},{b,c},,{c},}，

Y={{a},{c}}的所有8個(gè)重要元素：

YY

最大元素：無無極大元素：{a,b},{b,c}{a},{C}

最小元素：無極小元素：

{a},{C}

上界：{a,b,c}{a,c},{a,b,c}

上確界：{a,b,c}{a,c}

下界：

下確界：

第二十九頁，共三十三頁，2022年，8月28日第2章關(guān)系定理2.4：對集合X上的偏序關(guān)系有YX有：(1)y是Y的最大(小)元素則它必為Y的極大(小)元素；(2)y是Y的最大(小)元素則它必為Y