关系的闭包运算及偏序关系讲稿.ppt

《关系的闭包运算及偏序关系讲稿.ppt》由会员分享，可在线阅读，更多相关《关系的闭包运算及偏序关系讲稿.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关系的闭包运算及偏序关系第一页，讲稿共三十三页哦l通过关系的一些运算可以得到新的关系。通过关系的一些运算可以得到新的关系。l对于对于A上的关系上的关系R,希望希望R具有某些有用的性质具有某些有用的性质,如自反如自反性，对称性，传递性等。性，对称性，传递性等。l若若R不具有想要的性质，如自反性不具有想要的性质，如自反性l这种对给定的关系这种对给定的关系R用扩充一些元素用扩充一些元素(有序对有序对)的办法得到的办法得到具有某些特殊性质的新关系，就是具有某些特殊性质的新关系，就是闭包运算闭包运算。l添加元素的原则是什么？添加元素的原则是什么？第二页，讲稿共三十三页哦1.1.自反闭包自反闭包r r(R

2、 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).l显然显然 R1称为称为R的自反闭包的自反闭包.第三页，讲稿共三十三页哦定义定义 设设R A A,称最小的包含称最小的包含R的自反关系的自反关系R R 为为R的的自反自反闭包闭包,记为记为r(R)。R R=r(R)满足满足3个条件个条件:(1)R(1)R 是自反的是自

3、反的(2)R(2)RR R(3)(3)设设R R 是自反的且是自反的且R RR,R,则必有则必有R RR R（R R 是最小的是最小的）第四页，讲稿共三十三页哦定理定理2.1 2.1 自反闭包自反闭包r(R)的关系图的关系图?第五页，讲稿共三十三页哦2.2.对称闭包对称闭包s s(R R)定义定义 设设R A A,称最小的包含称最小的包含R的对称关系的对称关系R R 为为R的的对对称闭包称闭包,记为记为s(R).ls(R)满足满足3个条件个条件:l(1)包含包含R；l(2)对称性；对称性；l(3)最小性最小性.第六页，讲稿共三十三页哦定理2.2对称闭包对称闭包s(R)的关系图的关系图?第七页，

4、讲稿共三十三页哦3.3.传递闭包传递闭包t t(R R)定义定义 设设R A A,称最小的包含称最小的包含R的的传递传递关系为关系为R的的传递传递闭包闭包,记为记为t(R).t(R)满足满足3个条件个条件:l(1)包含包含R；l(2)传递传递性；性；l(3)最小性最小性.第八页，讲稿共三十三页哦例例：整整数数集集 Z Z上上的的“”关关系系的的自自反反闭闭包包是是“”关关系系,对称闭包是对称闭包是“”；传递闭包是它自身。；传递闭包是它自身。例：设有例：设有S=1,2,3,S=1,2,3,且有且有S S上的关系上的关系R R如下：如下：R=(1,2),(1,3)R=(1,2),(1,3)r(R)

5、=(1,2),(1,3),(1,1),(2,2),(3,3)r(R)=(1,2),(1,3),(1,1),(2,2),(3,3)s(R)=(1,2),(2,1),(1,3),(3,1)s(R)=(1,2),(2,1),(1,3),(3,1)t(R)=(1,2),(1,3)=R t(R)=(1,2),(1,3)=R第九页，讲稿共三十三页哦例设例设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),但仅添但仅添加

6、加(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)传递了传递了.第十页，讲稿共三十三页哦传递传递闭包闭包t(R)的关系图的关系图?第十一页，讲稿共三十三页哦定理2.3 若若|A|=n 1,R A A,则则 第十二页，讲稿共三十三页哦l例：设有例：设有S=1,2,3S=1,2,3上的关系上的关系 R=(1,2),(2,3),(3,2),(3,3)R=(1,2

7、),(2,3),(3,2),(3,3)试求试求 r(R),s(R)r(R),s(R)与与t(R)t(R)第十三页，讲稿共三十三页哦可用图示法：可用图示法：(a)R图示图示1 12 23 3(b)r()r(R)图示图示1 12 23(C)s(R)图示图示1 12 23 3(d)t(R)图示图示1 12 23 3图图2.102.10：关系：关系R的的r(R)、S(R)及及t(R)图示图示3 3第十四页，讲稿共三十三页哦例例:设设A=a,b,c,d,R=(a,b),(b,a),(b,c),(c,d),求求t(R).解解 第十五页，讲稿共三十三页哦第十六页，讲稿共三十三页哦 闭包运算与关系的性质的联系

8、闭包运算与关系的性质的联系定理定理l(1)R自反自反,则则r(R),s(R)及及t(R)自反自反.l(2)R对称对称,则则r(R),s(R)及及t(R)对称对称.l(3)R传递传递,则则r(R),t(R)传递传递,s(R)不一定传递不一定传递.第十七页，讲稿共三十三页哦2.52.5两种常用的关系两种常用的关系2.5.12.5.1次序关系次序关系 三三种种次次序序关关系系：偏偏序序关关系系、线线性性次次序序关关系系、拟拟序序关关系。系。偏偏序序关关系系满满足足自自反反性性的的次次序序关关系系,即即满满足足自自反反性性、反对称性及传递性。反对称性及传递性。拟拟序序关关系系满满足足反反自自反反性性的

9、的次次序序关关系系,即即满满足足反反自自反反性、反对称性及传递性。性、反对称性及传递性。线性次序关系线性次序关系所有元素均能顺序排列的偏序关系。所有元素均能顺序排列的偏序关系。第十八页，讲稿共三十三页哦第第2章章 关系关系 1.1.偏序偏序 定定义义2.102.10：偏偏序序关关系系：集集合合S S上上的的关关系系R R是是自自反反的的、反反对对称称的的又又是是传传递递的的,则则称称R R在在S S上上是是偏偏序序的的或或称称R R是是S S上上的的偏偏序序关关系系并可记以并可记以(S,R)(S,R)。可用符号：。可用符号：“”表示偏序。表示偏序。例：集合例：集合S S所组成的幂集所组成的幂集

10、(S)(S)上的关系：上的关系：“”是自反是自反 的的、反反对对称称及及传传递递的的,故故它它是是偏偏序序的的。它它可可记记为为：(S),(S),)。第十九页，讲稿共三十三页哦2 偏序集的偏序集的Hasse图图(1)画出偏序关系的关系图画出偏序关系的关系图(2)由于自反性每个点处都有环由于自反性每个点处都有环,去掉环。去掉环。(3)由于偏序关系的传递性由于偏序关系的传递性,去掉由于传递出现的边。去掉由于传递出现的边。(4)(4)若若x x y y将将x x放置于放置于y y之下之下。由于反对称性图中边的由于反对称性图中边的方向是一致的，都是从下到上的方向，去掉箭头。方向是一致的，都是从下到上的

11、方向，去掉箭头。按这种方式得到的图就是哈斯图按这种方式得到的图就是哈斯图.第二十页，讲稿共三十三页哦第第2章章 关系关系 例：例：(Z,(Z,)的哈斯图可见图的哈斯图可见图2.112.11(a)。例例：S=2,3,6,12,24,36S=2,3,6,12,24,36上上的的整整除除关关系系R R的的哈哈斯斯图图可可见图见图2.112.11(b)。例例：集集合合S=a,b,cS=a,b,c上上的的(S)(S)所所组组成成的的(S),(S),)的的哈哈斯图可见图斯图可见图2.112.11(C)。第二十一页，讲稿共三十三页哦第第2章章 关系关系-4-3-2-101234(a)(Z,(Z,)的哈斯图的

12、哈斯图(b)(S,(S,)的哈斯图的哈斯图236122436baca,ba,cb,ca,b,c(C)(S),(S),)的哈斯图的哈斯图图图2.11哈斯图示例哈斯图示例 第二十二页，讲稿共三十三页哦第第2章章 关系关系定义定义2.112.11：最大元素、最小元素、：最大元素、最小元素、极大元素、极小元素：极大元素、极小元素：设有设有(X,(X,)且集合且集合Y Y X,X,有有y y Y Y：(1)(1)对每个对每个y yY Y都有都有y y y,y,则称则称y y是是Y Y的最大元素；的最大元素；(2)(2)对每个对每个y yY Y都有都有y y y y,则称则称y y是是Y Y的最小元素；的

13、最小元素；(3)(3)不存在不存在y yY Y有有y y y y 且且y y y y,则称则称y y是是Y Y的极大元素；的极大元素；(4)(4)不存在不存在y yY Y有有y y y y 且且y y y,y,则称则称y y是是Y Y的极小元素；的极小元素；第二十三页，讲稿共三十三页哦第第2章章 关系关系 例：图例：图2.11(b)2.11(b)中中(S,(S,)的几个重要元素：的几个重要元素：最大元素：无最大元素：无 最小元素：无最小元素：无 极大元素：极大元素：24,3624,36 极小元素：极小元素：2,32,3 例：例：(S),(S),)中中(S)(S)的几个重要元素：的几个重要元素：

14、最大元素：最大元素：a,b,ca,b,c 最小元素：最小元素：极大元素：极大元素：a,b,ca,b,c 极小元素：极小元素：第二十四页，讲稿共三十三页哦l存在性存在性?(R,),S=Z?(P(X),),S=P(X)?l A X.l(Z+,|),S=Z+?1|x,S=2,4,6,12?第二十五页，讲稿共三十三页哦l唯一性唯一性?定理定理 若若S存在最大存在最大(小小)元元,则唯一。则唯一。证明：设证明：设a,b是是S的最大元，所以有的最大元，所以有 ab 且且 ba,由偏序的反对称性质，知由偏序的反对称性质，知 a=b。同理可证最小元的唯一性。同理可证最小元的唯一性。第二十六页，讲稿共三十三页哦

15、第第2章章 关系关系 定定义义2.122.12：上上界界、上上确确界界、下下界界、下下确确界界：设设有有(X,(X,)且且集集合合Y Y X,X,有有x x X X：(1)(1)对每个对每个y yY Y均有均有y y x,x,则称则称x x是是Y Y的上界；的上界；(2)(2)对每个对每个y yY Y均有均有x x y y,则称则称x x是是Y Y的下界；的下界；(3)x(3)x X X是是Y Y的的上上界界且且对对每每个个Y Y的的上上界界x x 均均有有x x x x,则则称称x x是是Y Y的上确界的上确界(即即Y Y的最小上界的最小上界)；(4)x(4)x X X是是Y Y的的下下界界

16、且且对对每每个个Y Y的的下下界界x x 均均有有x x x,x,则则称称x x是是Y Y的下确界的下确界(即即Y Y的最大下界的最大下界)；第二十七页，讲稿共三十三页哦lS=b,c,d,e?lS=a,b?第二十八页，讲稿共三十三页哦第第2章章 关系关系例：例：(S),(S),)中中Y=a,b,b,c,b,c,Y=a,b,b,c,b,c,，Y Y=a,c=a,c的所有的所有8 8个重要元素：个重要元素：Y YY Y 最大元素：最大元素：无无 无无 极大元素：极大元素：a,b,b,c a,Ca,b,b,c a,C 最小元素：最小元素：无无 极小元素：极小元素：a,Ca,C 上界：上界：a,b,c

17、 a,c,a,b,ca,b,c a,c,a,b,c 上确界：上确界：a,b,c a,ca,b,c a,c 下界：下界：下确界：下确界：第二十九页，讲稿共三十三页哦第第2章章 关系关系定理定理2.42.4：对集合对集合X X上的偏序关系上的偏序关系 有有Y Y X X有：有：(1)y(1)y是是Y Y的最大的最大(小小)元素则它必为元素则它必为Y Y的极大的极大(小小)元素；元素；(2)y(2)y是是Y Y的最大的最大(小小)元素则它必为元素则它必为Y Y的上的上(下下)界；界；(3)x(3)x是是Y Y的上的上(下下)确界确界,且且x x Y,Y,则则x x必为必为Y Y的最大的最大(小小)元

18、素。元素。第三十页，讲稿共三十三页哦l设设S=2,3,4,6,9,12,18,则则S上的整除关系上的整除关系R为偏序关为偏序关系，试求其子集系，试求其子集R1=2,4,R2=4,6,9,R3=12,18及及R4=S的重要元素的重要元素.第三十一页，讲稿共三十三页哦第第2章章 关系关系 2.2.线性次序线性次序 定义定义2.132.13：线性次序：线性次序：设集合设集合S S上有偏序关系上有偏序关系R,R,如对如对 x,yx,y S S必有必有x x y y或或y y x x则称则称R R是线性次序的是线性次序的(也可叫全序也可叫全序 的的)或称或称R R上集合上集合S S上的线性次序关系。上的线性次序关系。例：集合S=a,b,c上的关系 R=(a,b),(b,c)(a,c),(a,a),(b,b),(c,c)是线性次 序？S=a,b的幂集(S)=,a,b,a,b上的包 含关系是否线性次序？第三十二页，讲稿共三十三页哦第第2章章 关系关系 abc(a)(S,R)上的哈斯图上的哈斯图 a b a,b(b)()(S),(S),)上的哈斯图上的哈斯图图图2.14线性次序判别线性次序判别第三十三页，讲稿共三十三页哦