关系与序关系讲稿.ppt

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

1、关系与序关系第一页，讲稿共七十六页哦2.1 2.1 关系的概念关系的概念例设A=Alice,Bob,Tom,B=Algebra,Graphs,Sets Alice选修了Graphs,Bob选修了Algebra,Graph和Sets;Tom选修了Algebra,Graphs;R=,AB,表示了学生集合A与课程集合B之间的选修关系。第二页，讲稿共七十六页哦2.1 2.1 关系的概念关系的概念二元关系的一般性描述二元关系的一般性描述 一对对象之间的关系称为二元关系。例例 teachers=a,b,c，students=x,y,z 建立教学关系 T:aTx iff a TEACHING x 用序偶集合

2、表示为：T=,T teachers students 图示为：第三页，讲稿共七十六页哦2.1 2.1 关系的概念关系的概念 例例 Subroutines=a,b,c,d,e 子程序间调用关系图示为：Calling=,Calling Subroutines Subroutines第四页，讲稿共七十六页哦2.1 2.1 关系的概念关系的概念二元关系的集合定义二元关系的集合定义 设X,Y是两个集合，X Y的任何一个子集 R 都确定了一种二元关系，称为从X到Y的二元关系。R可记为 xRy，显然 R X Y R可记为 xRy当 X=Y 即 X 与 Y 同一时，称 R 为 X 上的一个二元关系。第五页，讲

3、稿共七十六页哦2.1 2.1 关系的概念关系的概念例 F=|x是y的父亲 S=|x,y为正整数且x可整除y T=|y为实数v对上述的：x，y，R，有R 或 R，二者必居其一。第六页，讲稿共七十六页哦2.1 2.1 关系的概念关系的概念定义域定义域 设二元关系S。由 S的所有对象 x 组成的集合称为S的定义域，记为Dom(S)。值域值域 由S的所有对象 y 组成的集合称为S的值域，记为Ran(S)(Range(S)。记 F(S)=D(S)R(S)，称为 S 的域。v描述：Dom(S)=x|(y)(S)Ran(S)=y|(x)(S)第七页，讲稿共七十六页哦2.1 2.1 关系的概念关系的概念v若干

4、特殊关系：X 到Y 的全域关系：Ex,y=XY 特别地：Ex,x=XX 空关系：恒等关系：Ix=|xiX例 设 X=1,2,3,4，求 X 上的关系“”(大于)及其定义域、值域。第八页，讲稿共七十六页哦2.2 2.2 关系的表示方法关系的表示方法(1)集合表示法 借用集合的各种描述方法对表示关系的序偶集合进行描述(2)关系矩阵 设 X=x1,x2,xm，Y=y1,y2,yn，m,n+R是X到Y的二元关系。构造矩阵MR=mijmn，mij=R0 其它第九页，讲稿共七十六页哦2.2 2.2 关系的表示方法关系的表示方法例非0行对应元素构成 D(S)非0列对应元素构成 R(S)101010011Te

5、achingMaxbcyz第十页，讲稿共七十六页哦2.2 2.2 关系的表示方法关系的表示方法(3)关系图表示法 用结点表示X、Y上的元素；若 R 则从结点x到结点y画一条弧。例 上述Teaching关系的关系图：第十一页，讲稿共七十六页哦2.2 2.2 关系的表示方法关系的表示方法例 设 X=1,2,3,4，X 上的关系“”：第十二页，讲稿共七十六页哦2.3 2.3 关系的性质关系的性质定义定义 设R是X上的二元关系，则：R 是自反的(x)(xXxRx)R 是对称的(x)(y)(x,yXxRyyRx)R 是传递的(x)(y)(z)(x,y,zXxRyyRz xRz)R 是反自反的(x)(xX

6、(xRx)R 是反对称的(x)(y)(x,yXxRyyRx x=y)第十三页，讲稿共七十六页哦2.2 2.2 关系的性质关系的性质习题 设 X=1,2,3,4，画出X 上的关系“”，“”和 整除“|”的关系图和关系矩阵，并判断其性质。习题 集合上的”is an element”以及”is a subset”具有什么性质？第十四页，讲稿共七十六页哦2.3 2.3 关系的性质关系的性质例 正整数集合上的若干关系及其性质整除=自反性对称性传递性反自反性反对称性 v判定关系“”的反对称性的前提条件总为F,反对称性成立。第十五页，讲稿共七十六页哦2.3 2.3 关系的性质关系的性质v从关系矩阵和关系图看

7、关系的性质：R是自反的：MR的对角元均为1；关系图为自环图。R是对称的：MR为对称矩阵；关系图中弧成对出现。R是反自反的：MR的对角元均为0；关系图为无自环图。R是反对称的：MR为反对称矩阵；关系图中只出现单向弧。第十六页，讲稿共七十六页哦2.3 2.3 关系的性质关系的性质存在着既非自反也非反自反的关系，如：0101存在着既对称又反对称的关系，如：100010001第十七页，讲稿共七十六页哦2.3 2.3 关系的性质关系的性质存在着既非对称又非反对称的关系，如：111100001第十八页，讲稿共七十六页哦2.4 2.4 集合的划分与覆盖集合的划分与覆盖定义定义 给定集合S，A=A1,A2,A

8、n，AiS，i=1.n。1ASAS;,nii 若有则说 是 的一个覆盖 若成立且AiAj=(若ij)，则说A是S的一个 划分，并称 A1,A2,An为此划分的块。第十九页，讲稿共七十六页哦2.4 2.4 集合的划分与覆盖集合的划分与覆盖例 N=0,1,2,3,4,自然数集合。取 A0=0,6,12,18,A1=1,7,13,19,A2=2,8,14,20,A5=5,11,17,23,则 A=A0，A1，A2，A3，A4，A5是N的一个划分。第二十页，讲稿共七十六页哦2.4 2.4 集合的划分与覆盖集合的划分与覆盖例 S=a,b,c 取 A=a,b,c B=a,b,c C=a,b,c 均构成对S

9、的划分。显然有|A|B|C|可以将 A 称为最大划分；将 C 称为最小划分。第二十一页，讲稿共七十六页哦 关系IX 具有自反、对称和传递性；设 X=1,2,3,4，写出X上的模同余关系，并判断其是否具有自反、对称和传递等性质。具有自反、对称和传递性的关系称为等价关系。第二十二页，讲稿共七十六页哦2.5 2.5 等价关系等价关系等价关系等价关系 集合X上的关系R若具有自反性、对称性和传递性，则称R为X上的一个等价关系。例 N上的模6同余关系 R=|x,yN (xy)=6L，L为整数 自反性：对称性：传递性：第二十三页，讲稿共七十六页哦2.5 2.5 等价关系等价关系定理定理 N上的模m同余关系是

10、等价关系。证明 自反性：xx=0，故 xx=mL，这里L=0。对称性：设 xRy 即 xy=mL，L为整数 则 yx=mL，故 yRx。传递性：设 xRy 且 yRz，即 xy=mL1，yz=mL2，L1、L2 为整数 则 xz=mL1+mL2=m(L1+L2)故 xRz第二十四页，讲稿共七十六页哦2.5 2.5 等价关系等价关系等价类等价类 设R为X上的一个等价关系，对任何xX，所有与x有关系R的元素的集合，称为X上由x生成的R等价类。记为 xR。xR=y|yX xRy例 X=1,2,3,4,5,6,7，R为X上的模3同余关系。则 1R=1,4,7，2R=2,5，3R=3,6第二十五页，讲稿

11、共七十六页哦2.5 2.5 等价关系等价关系性质性质 设R为X上的一个等价关系，则 X中的任何一个元素，至少属于一个等价类。若x,yX，则x,y或属同一等价类，或属两个不同等价类但此两个不同等价类的交集为（不相交）。证明第二十六页，讲稿共七十六页哦2.5 2.5 等价关系等价关系结论结论 对X上的等价关系R，任意xX属于且只属于一个等价类；若xRy，则xR=yR，否则 xR yR=。第二十七页，讲稿共七十六页哦2.5 2.5 等价关系等价关系定理定理 集合X上的一个等价关系R产生对此集合的一个划分，该划分的块对应于R的等价类。证明 由上述结论得到。v将该划分记作：X/R=xR|xX第二十八页，

12、讲稿共七十六页哦2.5 2.5 等价关系等价关系定理定理 X上的任意划分均可确定一个等价关系。证明 设X上的一个划分为 A=A1,A2,An，定义 R=|x,yX(Ai)(AiAxAiyAi)可以证明R具有 自反性：对称性：传递性：第二十九页，讲稿共七十六页哦2.5 2.5 等价关系等价关系问题X上由不同方法定义的等价关系R1、R2，若产生的等价类相同，则R1=R2。不等价关系也能产生划分。第三十页，讲稿共七十六页哦2.6 2.6 相容关系相容关系相容关系相容关系 X上的二元关系R，若R是自反的、对称的，则称R为X上的一个相容关系，记作 。例 X=2661,243,315,648,455 R=

13、|x,yX，x与y至少含有一个相同数字 容易看出，R具有自反性、对称性。R不具有传递性：如,R 但 R 因此R不是等价关系，R是一个相容关系。第三十一页，讲稿共七十六页哦2.6 2.6 相容关系相容关系相容类相容类 设 A X，是X上的一个相容关系。称A是X上的一个相容类当且仅当A中任二元素相容。即(x)(y)(x,yA x y)。最大相容类最大相容类 设 A是X上的一个相容类，若X-A中不存在与A中所有元素相容的元素，则称A为X的一个最大相容类。在相容关系的关系图中，最大相容类对应于一个最大完全子图。第三十二页，讲稿共七十六页哦2.6 2.6 相容关系相容关系例如，在上图表示的相容关系中，最

14、大相容类为:a,b,d,f,d,c,f,d,e,g问题相容类与覆盖的关系。第三十三页，讲稿共七十六页哦2.7 2.7 关系的运算关系的运算(1)关系的一般运算关系的一般运算定义定义 设 R、S是X到Y的二元关系，定义运算如下：RS=|xRyxSy RS=|xRyxSy RS=|xRyxSy R=XYR第三十四页，讲稿共七十六页哦2.7 2.7 关系的运算关系的运算(2)关系的复合运算关系的复合运算复合关系复合关系 设二元关系R:XY，S:YZ，则称 S R=|xXzZ(y)(yYxRyySz)为R和S的复合关系。v注意,关系的复合运算定义和函数复合保持了一致。在某些课本上，以上关系的复合记作R

15、 S。第三十五页，讲稿共七十六页哦2.7 2.7 关系的运算关系的运算例 X=x1,x2,x3，Y=y1,y2,y3,y4，Z=z1,z2,z3 R=,S=,v 显然有：Dom(S R)Dom(R)Ran(S R)Ran(S)S R=,第三十六页，讲稿共七十六页哦2.7 2.7 关系的运算关系的运算v关系的复合运算没有交换律。定理定理 关系复合运算的结合律：设二元关系 R：XY，S：YZ，P：ZW，则有 (P S)R=P(S R)证明第三十七页，讲稿共七十六页哦2.7 2.7 关系的运算关系的运算定理定理 关系复合运算与一般运算的结合律：设二元关系R1,R2：XY，S1,S2：YZ，则有(S1

16、 S2)R1=(S1 R1)(S2 R1)(S1S2)R1(S1R1)(S2R1)S1(R1R1)=(S1R1)(S1R2)S1(R1R2)(S1R1)(S1R2)证明第三十八页，讲稿共七十六页哦2.7 2.7 关系的运算关系的运算关系的幂运算 设R为X上的二元关系，RRR 记为Rn，规定 Rn=Rn1R，R0=IX第三十九页，讲稿共七十六页哦2.7 2.7 关系的运算关系的运算(3)关系的逆运算关系的逆运算逆关系逆关系 设二元关系 R：XY，定义 R-1=|xXyYR 为R的逆关系。性质性质(R-1)-1=R，-1=(RS)-1=R-1S-1，(RS)-1=R-1S-1(R)-1=(R-1)

17、(SR)-1=R-1S-1 R=S R-1=S-1 RS R-1S-1第四十页，讲稿共七十六页哦2.7 2.7 关系的运算关系的运算问题 设上关系R，S的关系矩阵分别为 R,MS,试求SR的关系矩阵。第四十一页，讲稿共七十六页哦2.7 2.7 关系的运算关系的运算(4)关系的闭包运算关系的闭包运算闭包闭包 设R为X上的二元关系，若另有一关系R，满足：R 是自反的（对称/传递）；R R；对于任何自反（对称/传递）的关系R，若 R R，则R R 。则称 R为R的自反（对称/传递）闭包，记为r(R)(s(R)/t(R)。第四十二页，讲稿共七十六页哦2.7 2.7 关系的运算关系的运算例 整数集上的“

18、”关系的自反闭包是“”，对称闭包是“”，传递闭包仍然是“”。例 整数“=”的自反、对称、传递闭包都是它本身。例 有关系矩阵101000011RM 求 Mr(R)、Ms(R)、Mt(R)第四十三页，讲稿共七十六页哦2.7 2.7 关系的运算关系的运算101000011RM101010011r RM()101001111s RM()111000011t RM()第四十四页，讲稿共七十六页哦2.7 2.7 关系的运算关系的运算定理定理 设R为X上的二元关系，则 r(R)=RIx s(R)=RR-11()iit RR证明 1)R t(R)(t(R)表示右式无穷并）2)t(R)是传递的；3)如果R是包含

19、R的传递关系，则对于任意n,RnR,所以，t(R)是包含R的最小传递关系。第四十五页，讲稿共七十六页哦2.7 2.7 关系的运算关系的运算问题：如何求传递闭包呢？设R是A上的关系，|A|=n,则t(R)=R R1 Rn这是因为如果从x到y有道路相连，则存在长度不超过n的道路。求传递闭包的Washall算法。参阅课本。第四十六页，讲稿共七十六页哦2.7 2.7 关系的运算关系的运算容易证明：R是自反的当且仅当r(R)=R；R是对称的当且仅当s(R)=R;R 是传递的当且仅当t(R)=R.问题：设R是A上的关系 r(RS)=r(R)r(S)?s(RS)=s(R)s(S)?t(RS)=t(R)t(S

20、)?如果将并换成交呢？第四十七页，讲稿共七十六页哦2.8 2.8 偏序关系偏序关系偏序关系偏序关系(partial order)集合A上的一个关系R满足自反性、反对称性和传递性时，称R是A上的一个偏序关系，记为“”，用二元组A,表示该偏序结构，或称之为偏序集。例 A=2,3,6,8,“”=|x,yA(x整除y)“”=.容易验证，上述关系为偏序关系。第四十八页，讲稿共七十六页哦2.8 2.8 偏序关系偏序关系vx、y之间存在偏序关系时，说 x、y（在该关系下）可比较，否则说 x、y 不可比较。上例中，2和3不可比较（在上述定义的“”下）。盖住盖住 盖住（紧邻遮盖）。设A,，x，yA，y盖住x x

21、yxy(z)(xzzy)(x=zy=z)记 covA=|x,yA(y盖住x)第四十九页，讲稿共七十六页哦2.8 2.8 偏序关系偏序关系v表达偏序关系的 Hasse图 设有偏序关系 用结点表示集合元素 若 covA，则用线段连接结点x,y，且令x(小者)在y的下方。第五十页，讲稿共七十六页哦2.8 2.8 偏序关系偏序关系Hasse图如右图 默认aa,bb,cc自反性 ac,cb ab传递性 a c bHasse Diagram例例集合A=a,b,c上的偏序关系为：,covA,第五十一页，讲稿共七十六页哦2.8 2.8 偏序关系偏序关系v上述Hasse图表示的对应关系集合为：,对应关系图如下：

22、a c bHasse Diagram a c b关系图第五十二页，讲稿共七十六页哦2.8 2.8 偏序关系偏序关系例例 由偏序关系的关系图构造相应的Hasse图 c a b关系图 d a b cHasse Diagram d第五十三页，讲稿共七十六页哦2.8 2.8 偏序关系偏序关系例例 2,3,6,12,24,36,17上的整除关系的Hasse图。Hasse Diagram 2 6 24 36 12 3 17第五十四页，讲稿共七十六页哦2.8 2.8 偏序关系偏序关系例例 A的幂集上的关系的Hasse图。A=a a a,bA=a,bba 第五十五页，讲稿共七十六页哦2.8 2.8 偏序关系偏

23、序关系例例 A的幂集上的关系的Hasse图。a,b,cA=a,b,cba c a,b a,c b,c第五十六页，讲稿共七十六页哦2.8 2.8 偏序关系偏序关系最大最小元最大最小元 对偏序集 y0A为最小元 (x)(xAy0 x)y0A为最大元 (x)(xAxy0)定理定理 中最大(最小)元若存在则唯一。证明极大极小元极大极小元 对 y0A为极小元 (x)(xAxy0(x y0)y0A为极大元 (x)(xAxy0(y0 x)第五十七页，讲稿共七十六页哦2.8 2.8 偏序关系偏序关系例 2,3,6,12,24,36上的整除关系的Hasse图。2 6 24 36 12 3 2,3 为极小元 24

24、,36 为极大元 没有最小元和最大元第五十八页，讲稿共七十六页哦2.8 2.8 偏序关系偏序关系例 A的幂集上的关系的Hasse图。a,b,cA=a,b,cba c a,b a,c b,c 为最小元 a,b,c 为最大元第五十九页，讲稿共七十六页哦2.8 2.8 偏序关系偏序关系上下界上下界 对,BA,aA a是B的一个上界 (x)(xBx a)a是B的一个下界 (x)(xBa x)v说明：a不一定是B的元素，即可能 aA-BB的上(下)界不一定存在，存在也不一定唯一。第六十页，讲稿共七十六页哦2.8 2.8 偏序关系偏序关系例 2,3,6,12,24,36上的整除关系的Hasse图。2 6

25、24 36 12 3令B1=2,3,6 B1的上界是 6,12,24,36 6B1，而12,24,36B1 B1没有下界令B2=2,6,12,24 B2的上界是24，下界是2第六十一页，讲稿共七十六页哦2.8 2.8 偏序关系偏序关系上确界上确界 对,BA,aA是B的一个上界。a是B的上确界 (y)(y是B的上界a y)上确界若存在则唯一。下确界下确界 对 ,BA,bA是B的一个下界。b是B的下确界 (x)(x是B的下界x b)下确界若存在则唯一。第六十二页，讲稿共七十六页哦2.8 2.8 偏序关系偏序关系例例 2,3,6,12,24,36上的整除关系的Hasse图。2 6 24 36 12

26、3令B1=2,3,6 B1的上界是 6,12,24,36 B1的上确界是 6 B1没有下界也没有下确界令B2=2,6,12,24 B2的上界和上确界是24 B2的下界和下确界是2第六十三页，讲稿共七十六页哦2.8 2.8 偏序关系偏序关系链与反链链与反链 对,BA,若B中任两个元素之间都是可比较的，则称B是A中的一条链。若B中任两个元素之间都是不可比较的，则称B是A中的一条反链。2 6 24 36 12 3例 右边所示Hasse图中，2,6,12,24 是一条链 2,3和24,36是反链v注意：2,3,24,36并非反链第六十四页，讲稿共七十六页哦2.9 2.9 其他序关系其他序关系(1)全序

27、关系全序关系全序关系全序关系 设偏序集，若A是一条链，则称“”为A上的一个全序关系，此时称 是一个全序集合。(2)偏序关系的逆关系偏序关系的逆关系定义定义 设偏序集 ，定义A上的关系“”xy x,yAyx 集合A和关系“”仍然构成一个偏序集。第六十五页，讲稿共七十六页哦2.2.9 9 其他序其他序关系关系拓扑排序 一个偏序集可以表示一个工程中各个任务之间的依赖关系。如果一个时刻只能进行一个任务，那么整个工程的流程是一个与原偏序协调的全序。找出这个全序的过程称为拓扑排序。定义设有偏序集,如果存在一个全序*使得 x y 蕴含 x *y,则称*是A上的一个拓扑排序。拓扑排序算法 问题 是否每个偏序集

28、都存在拓扑排序？第六十六页，讲稿共七十六页哦2.9 2.9 其他序关系其他序关系(3)拟序关系（拟序关系（strict partial order）拟序关系拟序关系 集合A上的关系R满足反自反性和传递性时，称为A上的一个拟序关系，用二元组 A,表示该结构。定理定理 若R为A上的偏序关系，则R-IA为A上的拟序关系。若R为A上的拟序关系，则RIA为A上的偏序关系。第六十七页，讲稿共七十六页哦2.9 2.9 其他序关系其他序关系定理定理 设有拟序集 A,，对任何 x,y,zA,xy,x=y,yx 中至多有一种情况成立(三分律)；xyx 则 x=y，这里 xy 表示 xy 或 x=y。证明 利用拟序

29、集的反自反性和传递性。第六十八页，讲稿共七十六页哦2.9 2.9 其他序关系其他序关系(4)(4)词典次序词典次序v设字母表为X，“”为X上的自然次序。显然 为全序集合。长度为2的词库 A=X X 在A上定义全序关系S：S (x1x2)(x1=x2y1y2)第六十九页，讲稿共七十六页哦2.9 2.9 其他序关系其他序关系 长度不大于n的词库 A=XX2.Xn 在A上定义全序关系S：设,A,其中pqn。S 当且仅当下列三个条件之一得到满足：()=()x1y1且在X中有x1y1 ()xi=yi,i=1.k,kp,xi+1yi+1且在X中有 xi+1yi+1 否则 S第七十页，讲稿共七十六页哦2.9

30、 2.9 其他序关系其他序关系(5)(5)格格格 设偏序集合,若其中任何二个元素在A中都有上、下确界，则称 为一个格。例 如下的Hasse 图描述了三个格：第七十一页，讲稿共七十六页哦2.9 2.9 其他序关系其他序关系例 如下的Hasse 图描述的不是格：（没有下确界）例，I+正整数，a“”b iff a 整除 b。任何 x,yI+，其上确界为其最小公倍数，下确界为其最大公约数，均存在于I+中。故 为格。第七十二页，讲稿共七十六页哦2.9 2.9 其他序关系其他序关系上下确界上下确界 设 为格，对任意 a,bA，记 a,b的上确界元素为ab，下确界元素为ab。性质性质 设 为格，对任意 a,

31、b,c,dA，有 a ab,ab a 若 a b,c d，则 ac bd,ac bd ab=ba,ab=ba （交换律）a(bc)=(ab)c,a(bc)=(ab)c（结合律）a(ab)=a,a(ab)=a （吸收律）第七十三页，讲稿共七十六页哦2.9 2.9 其他次序关系其他次序关系(6)(6)良序集合良序集合良序集合良序集合 设偏序集合 ，若其任意非空子集都存在最小元，则称 为良序集合。例 如图的偏序集不是良序集。第七十四页，讲稿共七十六页哦2.9 2.9 其他次序关系其他次序关系定理定理 每个良序集合本身也是一个全序集合。有限的全序集合是一个良序集合。证明 留作习题。第七十五页，讲稿共七十六页哦要求 关系 关系的概念，关系的表示法；关系的性质，性质的判定；等价关系及其划分，等价关系例子；关系的运算，特别是复合和闭包；偏序的概念，偏序关系例子，Hasse图；全序、拟序和良序的概念。第七十六页，讲稿共七十六页哦