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

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

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日定義

設R

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

設R

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

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

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

例：設有S={1,2,3},且有S上的關系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日例設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)是不夠的.因為{(a,b),(b,c),(b,a),(a,c)}不傳遞.根據(a,b)和(b,a),還要加(a,a);根據(b,a)和(a,b),還要加(b,b),這時{(a,b),(b,c),(b,a),(a,c),(a,a),(b,b)}傳遞了.

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

若|A|=n

1,

R

AA,則

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

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：關系R的r(R)、S(R)及t(R)圖示3第十四頁，共三十三頁，2022年，8月28日例:設A={a,b,c,d},R={(a,b),(b,a),(b,c),(c,d)},求t(R).解

第十五頁，共三十三頁，2022年，8月28日第十六頁，共三十三頁，2022年，8月28日閉包運算與關系的性質的聯系定理(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兩種常用的關系次序關系三種次序關系：偏序關系、線性次序關系、擬序關系。

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

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

線性次序關系—所有元素均能順序排列的偏序關系。

第十八頁，共三十三頁，2022年，8月28日第2章關系

1.偏序

定義2.10：偏序關系：集合S上的關系R是自反的、反對稱的又是傳遞的,則稱R在S上是偏序的或稱R是S上的偏序關系并可記以(S,R)。可用符號：“”表示偏序。

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

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

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

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

極小元素：2,3

例：((S),)中(S)的幾個重要元素：最大元素：{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存在最大(小)元,則唯一。證明：設a,b是S的最大元，所以有

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

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

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

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

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

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

；

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

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

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章關系定理2.4：對集合X上的偏序關系有YX有：(1)y是Y的最大(小)元素則它必為Y的極大(小)元素；(2)y是Y的最大(小)元素則它必為Y