关系的闭包运算及偏序关系

关系的闭包运算及偏序关系第1页，共33页，2023年，2月20日，星期三通过关系的一些运算可以得到新的关系。对于A上的关系R,希望R具有某些有用的性质,如自反性，对称性，传递性等。若R不具有想要的性质，如自反性这种对给定的关系R用扩充一些元素(有序对)的办法得到具有某些特殊性质的新关系，就是闭包运算。添加元素的原则是什么？第2页，共33页，2023年，2月20日，星期三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的自反闭包.第3页，共33页，2023年，2月20日，星期三定义

设R

AA,称最小的包含R的自反关系R为R的自反闭包,记为r(R)。R=r(R)满足3个条件:(1)R是自反的(2)RR(3)设R是自反的且RR,则必有RR（R是最小的）第4页，共33页，2023年，2月20日，星期三定理2.1自反闭包r(R)的关系图?第5页，共33页，2023年，2月20日，星期三2.对称闭包s(R)定义

设R

AA,称最小的包含R的对称关系R为R的对称闭包,记为s(R).s(R)满足3个条件:(1)包含R；(2)对称性；(3)最小性.第6页，共33页，2023年，2月20日，星期三定理2.2对称闭包s(R)的关系图?第7页，共33页，2023年，2月20日，星期三3.传递闭包t(R)定义设R

AA,称最小的包含R的传递关系为R的传递闭包,记为t(R).

t(R)满足3个条件:(1)包含R；(2)传递性；(3)最小性.第8页，共33页，2023年，2月20日，星期三例：整数集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第9页，共33页，2023年，2月20日，星期三例设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)}传递了.

第10页，共33页，2023年，2月20日，星期三传递闭包t(R)的关系图?第11页，共33页，2023年，2月20日，星期三定理2.3

若|A|=n

1,

R

AA,则

第12页，共33页，2023年，2月20日，星期三例：设有S={1,2,3}上的关系

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

试求r(R),s(R)与t(R)第13页，共33页，2023年，2月20日，星期三可用图示法：(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第14页，共33页，2023年，2月20日，星期三例:设A={a,b,c,d},R={(a,b),(b,a),(b,c),(c,d)},求t(R).解

第15页，共33页，2023年，2月20日，星期三第16页，共33页，2023年，2月20日，星期三闭包运算与关系的性质的联系定理(1)R自反,则r(R),s(R)及t(R)自反.(2)R对称,则r(R),s(R)及t(R)对称.(3)R传递,则r(R),t(R)传递,s(R)不一定传递.第17页，共33页，2023年，2月20日，星期三2.5两种常用的关系2.5.1次序关系三种次序关系：偏序关系、线性次序关系、拟序关系。

偏序关系—满足自反性的次序关系,即满足自反性、反对称性及传递性。

拟序关系—满足反自反性的次序关系,即满足反自反性、反对称性及传递性。

线性次序关系—所有元素均能顺序排列的偏序关系。

第18页，共33页，2023年，2月20日，星期三第2章关系

1.偏序

定义2.10：偏序关系：集合S上的关系R是自反的、反对称的又是传递的,则称R在S上是偏序的或称R是S上的偏序关系并可记以(S,R)。可用符号：“”表示偏序。

例：集合S所组成的幂集(S)上的关系：“”是自反的、反对称及传递的,故它是偏序的。它可记为：((S),)。第19页，共33页，2023年，2月20日，星期三2偏序集的Hasse图(1)画出偏序关系的关系图(2)由于自反性每个点处都有环,去掉环。(3)由于偏序关系的传递性,去掉由于传递出现的边。(4)若xy将x放置于y之下。由于反对称性图中边的方向是一致的，都是从下到上的方向，去掉箭头。按这种方式得到的图就是哈斯图.第20页，共33页，2023年，2月20日，星期三第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)。第21页，共33页，2023年，2月20日，星期三第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哈斯图示例

第22页，共33页，2023年，2月20日，星期三第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的极小元素；第23页，共33页，2023年，2月20日，星期三第2章关系

例：图2.11(b)中(S,)的几个重要元素：最大元素：无最小元素：无极大元素：24,36

极小元素：2,3

例：((S),)中(S)的几个重要元素：最大元素：{a,b,c}

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

极小元素：第24页，共33页，2023年，2月20日，星期三存在性?(R,),S=Z?(P(X),),S=P(X)?AX.(Z+,|),S=Z+?1|x,S={2,4,6,12}?第25页，共33页，2023年，2月20日，星期三唯一性?定理若S存在最大(小)元,则唯一。证明：设a,b是S的最大元，所以有

a≤b且b≤a,由偏序的反对称性质，知a=b。同理可证最小元的唯一性。第26页，共33页，2023年，2月20日，星期三第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的最大下界)

；

第27页，共33页，2023年，2月20日，星期三S={b,c,d,e}?S={a,b}?第28页，共33页，2023年，2月20日，星期三第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}

下界：

下确界：

第29页，共33页，2023年，2月20日，星期三第2章关系定理2.4：对集合X上的偏序关系有YX有：(1)y是Y的最大(小)元素则它必为Y的极大(小)元素；(2)y是Y的最大(小)元素则它必为Y