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

关系的闭包运算及偏序关系第一页，讲稿共三十三页哦l通过关系的一些运算可以得到新的关系。通过关系的一些运算可以得到新的关系。l对于对于A上的关系上的关系R,希望希望R具有某些有用的性质具有某些有用的性质,如自反如自反性，对称性，传递性等。性，对称性，传递性等。l若若R不具有想要的性质，如自反性不具有想要的性质，如自反性l这种对给定的关系这种对给定的关系R用扩充一些元素用扩充一些元素(有序对有序对)的办法得到的办法得到具有某些特殊性质的新关系，就是具有某些特殊性质的新关系，就是闭包运算闭包运算。l添加元素的原则是什么？添加元素的原则是什么？第二页，讲稿共三十三页哦1.1.自反闭包自反闭包r r(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).l显然显然 R1称为称为R的自反闭包的自反闭包.第三页，讲稿共三十三页哦定义定义 设设R A A,称最小的包含称最小的包含R的自反关系的自反关系R R 为为R的的自反自反闭包闭包,记为记为r(R)。R R=r(R)满足满足3个条件个条件:(1)R(1)R 是自反的是自反的(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)的关系图的关系图?第七页，讲稿共三十三页哦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)=(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),但仅添但仅添加加(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),(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).解解 第十五页，讲稿共三十三页哦第十六页，讲稿共三十三页哦 闭包运算与关系的性质的联系闭包运算与关系的性质的联系定理定理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次序关系次序关系 三三种种次次序序关关系系：偏偏序序关关系系、线线性性次次序序关关系系、拟拟序序关关系。系。偏偏序序关关系系满满足足自自反反性性的的次次序序关关系系,即即满满足足自自反反性性、反对称性及传递性。反对称性及传递性。拟拟序序关关系系满满足足反反自自反反性性的的次次序序关关系系,即即满满足足反反自自反反性、反对称性及传递性。性、反对称性及传递性。线性次序关系线性次序关系所有元素均能顺序排列的偏序关系。所有元素均能顺序排列的偏序关系。第十八页，讲稿共三十三页哦第第2章章 关系关系 1.1.偏序偏序 定定义义2.102.10：偏偏序序关关系系：集集合合S S上上的的关关系系R R是是自自反反的的、反反对对称称的的又又是是传传递递的的,则则称称R R在在S S上上是是偏偏序序的的或或称称R R是是S S上上的的偏偏序序关关系系并可记以并可记以(S,R)(S,R)。可用符号：。可用符号：“”表示偏序。表示偏序。例：集合例：集合S S所组成的幂集所组成的幂集(S)(S)上的关系：上的关系：“”是自反是自反 的的、反反对对称称及及传传递递的的,故故它它是是偏偏序序的的。它它可可记记为为：(S),(S),)。第十九页，讲稿共三十三页哦2 偏序集的偏序集的Hasse图图(1)画出偏序关系的关系图画出偏序关系的关系图(2)由于自反性每个点处都有环由于自反性每个点处都有环,去掉环。去掉环。(3)由于偏序关系的传递性由于偏序关系的传递性,去掉由于传递出现的边。去掉由于传递出现的边。(4)(4)若若x x y y将将x x放置于放置于y y之下之下。由于反对称性图中边的由于反对称性图中边的方向是一致的，都是从下到上的方向，去掉箭头。方向是一致的，都是从下到上的方向，去掉箭头。按这种方式得到的图就是哈斯图按这种方式得到的图就是哈斯图.第二十页，讲稿共三十三页哦第第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,)的哈斯图的哈斯图(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的最小元素；的最小元素；(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)的几个重要元素：的几个重要元素：最大元素：最大元素：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。同理可证最小元的唯一性。同理可证最小元的唯一性。第二十六页，讲稿共三十三页哦第第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的的下下界界且且对对每每个个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 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的最大的最大(小小)元素。元素。第三十页，讲稿共三十三页哦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线性次序判别线性次序判别第三十三页，讲稿共三十三页哦