关系和序关系ppt课件

1、1第二章第二章 关系与序关系关系与序关系 关系的概念 关系的表示 关系的性质 等价关系 关系的运算 偏序关系22.1 2.1 关系的概念关系的概念例设A=Alice,Bob,Tom, B=Algebra,Graphs, Sets Alice选修了Graphs, Bob选修了Algebra, Graph和Sets; Tom选修了Algebra,Graphs;R=, AB, 表示了学生集合A与课程集合B之间的选修关系。32.1 2.1 关系的概念关系的概念二元关系的一般性描述二元关系的一般性描述 一对对象之间的关系称为二元关系。一对对象之间的关系称为二元关系。例例 teachers=a,b,c，s

2、tudents=x,y,z 建立教学关系建立教学关系 T: aTx iff a TEACHING x 用序偶集合表示为：用序偶集合表示为： T = , T teachers students 图示为：图示为：42.1 2.1 关系的概念关系的概念 例例 Subroutines=a,b,c,d,e Subroutines=a,b,c,d,e 子程序间调用关系子程序间调用关系图示为：图示为：Calling=, Calling=, , , Calling Calling Subroutines Subroutines Subroutines Subroutines52.1 2.1 关系的概念关系的概

3、念二元关系的集合定义二元关系的集合定义 设设X,Y是两个集合，是两个集合， X Y的的任何一个子集任何一个子集 R 都确定了一种二元关系，称为从都确定了一种二元关系，称为从X到到Y的二元关系。的二元关系。 R可记为可记为 xRy，显然，显然 R X Y R可记为可记为 x Ry当当 X=Y 即即 X 与与 Y 同一时，称同一时，称 R 为为 X 上的一个二元上的一个二元关系。关系。62.1 2.1 关系的概念关系的概念例 F=| x是y的父亲 S=| x,y为正整数且x可整除y T=| y为实数对上述的：x，y，R，有R 或 R，二者必居其一。72.1 2.1 关系的概念关系的概念定义域定义域

4、 设二元关系设二元关系S。由。由 S的所有对象的所有对象 x 组组成的集合称为成的集合称为S的定义域，记为的定义域，记为Dom(S) 。值域值域 由由 S的所有对象的所有对象 y 组成的集合称为组成的集合称为S的值的值域，记为域，记为Ran(S) (Range(S)。记。记 F(S) = D(S) R(S) ，称为，称为 S 的域。的域。描画：描画：Dom(S) = x| ( y)( S) Ran(S) = y| ( x)( S)82.1 2.1 关系的概念关系的概念v若干特殊关系：v X 到Y 的全域关系： Ex,y = XYv 特别地： Ex,x = XXv 空关系： v 恒等关系：Ix

5、= |xiXv例 设 X=1,2,3,4，求 X 上的关系 “ ”(大于)及其定义域、值域。92.2 2.2 关系的表示方法关系的表示方法(1) 集合表示法 借用集合的各种描述方法对表示关系的序偶集合进行描述(2) 关系矩阵 设 X=x1,x2,xm，Y=y1,y2,yn，m,n + R是X到Y的二元关系。构造矩阵MR=mijmn， mij = R 0 其它102.2 2.2 关系的表示方法关系的表示方法例非0行对应元素构成 D(S)非0列对应元素构成 R(S)101010011TeachingMaxbcyz112.2 2.2 关系的表示方法关系的表示方法(3) 关系图表示法 用结点表示X、Y

6、上的元素；假设 R 则从结点x到结点y画一条弧。例 上述Teaching关系的关系图：122.2 2.2 关系的表示方法关系的表示方法例 设 X=1,2,3,4，X 上的关系 “ ”：132.3 2.3 关系的性质关系的性质定义定义 设设R是是X上的二元关系，那么：上的二元关系，那么： R 是自反的是自反的 ( x)(x XxRx) R 是对称的是对称的 ( x)( y)(x,y X xRyyRx) R 是传递的是传递的 ( x)( y)( z)(x,y,z X xRy yRz xRz) R 是反自反的是反自反的 ( x)(x X(xRx) R 是反对称的是反对称的 ( x)( y)(x,y

7、X xRy yRx x = y)142.2 2.2 关系的性质关系的性质习题 设 X=1,2,3,4，画出X 上的关系 “ ”，“”和 整除“|”的关系图和关系矩阵，并判断其性质。习题 集合上的is an element以及is a subset具有什么性质？152.3 2.3 关系的性质关系的性质例 正整数集合上的若干关系及其性质整除=自反性对称性传递性反自反性反对称性 v判定关系“”的反对称性的前提条件总为F, 反对称性成立。162.3 2.3 关系的性质关系的性质v从关系矩阵和关系图看关系的性质：vR是自反的：MR的对角元均为1；v 关系图为自环图。vR是对称的：MR为对称矩阵；v 关系

8、图中弧成对出现。vR是反自反的：MR的对角元均为0；v 关系图为无自环图。vR是反对称的：MR为反对称矩阵；v 关系图中只出现单向弧。172.3 2.3 关系的性质关系的性质存在着既非自反也非反自反的关系，如：0101存在着既对称又反对称的关系，如：100010001182.3 2.3 关系的性质关系的性质存在着既非对称又非反对称的关系，如：111100001192.4 2.4 集合的划分与覆盖集合的划分与覆盖定义定义 给定集合给定集合S，A=A1,A2,An，Ai S，i=1.n。1ASAS;,nii 若有则说 是 的一个覆盖 假设成立且AiAj = (若ij)，则说A是S的一个 划分，并称

9、 A1,A2,An为此划分的块。202.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的一个划分。212.4 2.4 集合的划分与覆盖集合的划分与覆盖例 S=a,b,c 取 A = a,b,c B = a,b,c C = a,b,c 均构成对S的划分。 显然有 |A| |B| |C| 可以将 A 称为最大划分；将 C 称为最小划分。22 关系IX 具有自反、对称和传递性； 设 X

10、=1,2,3,4，写出X上的模同余关系，并判断其是否具有自反、对称和传递等性质。 具有自反、对称和传递性的关系称为等价关系。232.5 2.5 等价关系等价关系等价关系等价关系 集合集合X上的关系上的关系R若具有自反性、对称性若具有自反性、对称性和传递性，则称和传递性，则称R为为X上的一个等价关系。上的一个等价关系。例例 N上的模上的模6同余关系同余关系 R=|x,y N (x y)=6L，L为整数为整数 自反性：自反性： 对称性：对称性： 传递性：传递性：242.5 2.5 等价关系等价关系定理定理 N上的模上的模m同余关系是等价关系。同余关系是等价关系。证明证明 自反性：自反性： x x

11、= 0，故，故 x x = mL，这里，这里L=0。 对称性：设对称性：设 xRy 即即 x y=mL，L为整数为整数 那么那么 y x= mL，故，故 yRx。 传递性：设传递性：设 xRy 且且 yRz，即，即 x y=mL1，y z=mL2 ，L1、L2 为整为整数数 那么那么 x z = mL1+mL2=m(L1+L2) 故故 xRz252.5 2.5 等价关系等价关系等价类等价类 设设R为为X上的一个等价关系，对任何上的一个等价关系，对任何x X，所有与所有与x有关系有关系R的元素的集合，称为的元素的集合，称为X上由上由x生成生成的的R等价类。记为等价类。记为 xR。 xR=y|y

12、X xRy例例 X=1,2,3,4,5,6,7，R为为X上的模上的模3同余关系。同余关系。那么那么 1R=1,4,7，2R=2,5，3R=3,6262.5 2.5 等价关系等价关系性质性质 设设R为为X上的一个等价关系，那么上的一个等价关系，那么 X中的任何一个元素，至少属于一个等价类。中的任何一个元素，至少属于一个等价类。 若若x,y X，则，则x,y或属同一等价类，或属两个不同等或属同一等价类，或属两个不同等价类但此两个不同等价类的交集为价类但此两个不同等价类的交集为（不相交）。（不相交）。证明证明272.5 2.5 等价关系等价关系结论结论 对对X上的等价关系上的等价关系R， 任意任意x

13、 X属于且只属属于且只属于一个等价类；于一个等价类； 若若xRy，那么，那么xR = yR ，否，否则则 xR yR = 。282.5 2.5 等价关系等价关系定理定理 集合集合X上的一个等价关系上的一个等价关系R产生对此集合的一产生对此集合的一个划分，该划分的块对应于个划分，该划分的块对应于R的等价类。的等价类。 证明证明 由上述结论得到。由上述结论得到。将该划分记作：将该划分记作：X/R=xR|x X292.5 2.5 等价关系等价关系定理定理 X上的任意划分均可确定一个等价关系。上的任意划分均可确定一个等价关系。证明证明 设设X上的一个划分为上的一个划分为 A=A1, A2, An，定义

14、，定义 R=|x,y X ( Ai)(Ai A x Ai y Ai) 可以证明可以证明R具有具有 自反性：自反性： 对称性：对称性： 传递性：传递性：302.5 2.5 等价关系等价关系问题X上由不同方法定义的等价关系R1、R2，若产生的等价类相同，则R1=R2。不等价关系也能产生划分。312.6 2.6 相容关系相容关系相容关系相容关系 X上的二元关系上的二元关系R，若，若R是自反的、对称的，是自反的、对称的，则称则称R为为X上的一个相容关系，记作上的一个相容关系，记作 。例例 X=2661,243,315,648,455 R=|x,y X，x与与y至少含有一个相同数字至少含有一个相同数字

15、容易看出，容易看出，R具有自反性、对称性。具有自反性、对称性。 R不具有传递性：不具有传递性： 如如 , R 但但 R 因此因此R不是等价关系，不是等价关系，R是一个相容关系。是一个相容关系。322.6 2.6 相容关系相容关系相容类相容类 设设 A X， 是是X上的一个相容关系。称上的一个相容关系。称A是是X上的一个相容类当且仅当上的一个相容类当且仅当A中任二元素相容。即中任二元素相容。即 ( x)( y)(x,y A x y)。最大相容类最大相容类 设设 A是是X上的一个相容类，若上的一个相容类，若X-A中不存中不存在与在与A中所有元素相容的元素，则称中所有元素相容的元素，则称A为为X的一

16、个的一个最大相容类。最大相容类。在相容关系的关系图中，最大相容类对应于一个最大在相容关系的关系图中，最大相容类对应于一个最大完全子图。完全子图。332.6 2.6 相容关系相容关系例如，在上图表示的相容关系中，最大相容类为: a, b, d , f, d, c ,f, d, e, g问题相容类与覆盖的关系。342.7 2.7 关系的运算关系的运算(1) 关系的一般运算关系的一般运算定义定义 设设 R、S是是X到到Y的二元关系，定义运算如下：的二元关系，定义运算如下： R S=|xRy xSy R S=|xRy xSy R S=|xRy x Sy R=X Y R352.7 2.7 关系的运算关系

17、的运算(2) 关系的复合运算关系的复合运算复合关系复合关系 设二元关系设二元关系R:XY，S:YZ，则称，则称 S R=|x X z Z ( y)(y Y xRy ySz) 为为R和和S的复合关系。的复合关系。留意留意, 关系的复合运算定义和函数复合保持了一致。关系的复合运算定义和函数复合保持了一致。在某些课本上，以上关系的复合记作在某些课本上，以上关系的复合记作R S。362.7 2.7 关系的运算关系的运算例 X=x1, x2, x3，Y=y1, y2, y3, y4，Z=z1, z2, z3 R=, S= ,v 显然有：Dom(S R) Dom(R) v Ran (S R) Ran(S)

18、 S R=,372.7 2.7 关系的运算关系的运算v关系的复合运算没有交换律。v定理 关系复合运算的结合律：设二元关系v R：XY，S：YZ， P：ZW，v 则有 (P S) R= P (S R)v证明382.7 2.7 关系的运算关系的运算定理定理 关系复合运算与一般运算的结合律：设二元关系关系复合运算与一般运算的结合律：设二元关系R1, R2 ：XY， S1 , S2：YZ，则有，则有(S1 S2) R1 =(S1 R1) (S2 R1) (S1 S2) R1 (S1 R1) (S2 R1)S1 (R1 R1) =(S1 R1) (S1 R2) S1 (R1 R2) (S1 R1) (S

19、1 R2)证明证明392.7 2.7 关系的运算关系的运算关系的幂运算 设R为X上的二元关系，RRR 记为Rn，规定 Rn=Rn1R，R0=IX402.7 2.7 关系的运算关系的运算(3) 关系的逆运算关系的逆运算逆关系逆关系 设二元关系设二元关系 R：XY，定义，定义 R-1=|x X y Y R 为为R的逆关系。的逆关系。性质性质(R-1)-1 =R，-1 = (R S)-1 = R-1 S-1 ，(R S)-1 = R-1 S-1 (R)-1 = (R-1)(S R)-1 =R-1 S-1 R=S R-1=S-1 R S R-1 S-1412.7 2.7 关系的运算关系的运算问题 设上

20、关系R，S的关系矩阵分别为 R, MS, 试求SR的关系矩阵。422.7 2.7 关系的运算关系的运算(4) 关系的闭包运算关系的闭包运算闭包闭包 设设R为为X上的二元关系，若另有一关系上的二元关系，若另有一关系R ，满，满足：足： R 是自反的对称是自反的对称/传送）；传送）； R R ； 对于任何自反对称对于任何自反对称/传送的关系传送的关系R ，假设，假设 R R ，则，则R R 。 则称则称 R 为为R的自反对称的自反对称/传送闭包，记为传送闭包，记为r(R) (s(R) / t(R)。432.7 2.7 关系的运算关系的运算例 整数集上的“ ”关系的自反闭包是“ ”，对称闭包是“ ”

21、，传递闭包仍然是“ ”。例 整数“= ”的自反、对称、传递闭包都是它本身。例 有关系矩阵101000011RM 求 Mr (R) 、 Ms (R) 、 Mt (R) 442.7 2.7 关系的运算关系的运算101000011RM101010011r RM()101001111s RM()111000011t RM()452.7 2.7 关系的运算关系的运算定理定理 设设R为为X上的二元关系，上的二元关系，那么那么 r(R) = R Ix s(R) = R R-11()iit RR证明 1) R t(R )(t( R) 表示右式无穷并） 2) t(R ) 是传递的； 3) 如果R是包含R的传递关

22、系，则对于任意n, RnR, 所以，t(R ) 是包含R的最小传递关系。462.7 2.7 关系的运算关系的运算问题：如何求传递闭包呢？设R是A上的关系，|A|=n, 那么t(R) = R R1 Rn这是因为如果从x到y有道路相连，则存在长度不超过n的道路。求传递闭包的Washall算法。参阅课本。472.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)?如

23、果将并换成交呢？482.8 2.8 偏序关系偏序关系偏序关系偏序关系(partial order) 集合集合A上的一个关系上的一个关系R满足满足自反性、反对称性和传递性时，称自反性、反对称性和传递性时，称R是是A上的一个上的一个偏序关系，记为偏序关系，记为“ ”，用二元组，用二元组A, 表示该表示该偏序结构，或称之为偏序集。偏序结构，或称之为偏序集。例例 A=2,3,6,8, “ ”=|x,y A (x整除整除y) “ ”= . 容易验证，上述关系为偏序关系。容易验证，上述关系为偏序关系。492.8 2.8 偏序关系偏序关系vx、y之间存在偏序关系时，说 x、y在该关系下可比较，否则说 x、y

24、 不可比较。上例中，2和3不可比较在上述定义的“ ”下）。v盖住 盖住紧邻遮盖）。设A, ，x，yA，v y盖住x xyxy(z)(xzzy)(x=zy=z)v 记 covA=|x,yA(y盖住x)502.8 2.8 偏序关系偏序关系v表达偏序关系的 Hasse图v 设有偏序关系 v 用结点表示集合元素v 假设 covA，则用线段连接结点x,y，且令x(小者)在y的下方。512.8 2.8 偏序关系偏序关系Hasse图如右图 默认aa, bb, cc自反性 ac, cb ab传递性 a c bHasse Diagram例集合A= a,b,c上的偏序关系为： , covA ,522.8 2.8

25、偏序关系偏序关系v上述Hasse图表示的对应关系集合为：v ,v 对应关系图如下： a c bHasse Diagram a c b关系图532.8 2.8 偏序关系偏序关系例 由偏序关系的关系图构造相应的Hasse图 c a b关系图 d a b cHasse Diagram d542.8 2.8 偏序关系偏序关系例 2,3,6,12,24,36,17上的整除关系的Hasse图。Hasse Diagram 2 6 24 36 12 3 17552.8 2.8 偏序关系偏序关系例 A的幂集上的关系的Hasse图。 A=a a a,bA=a,bba 562.8 2.8 偏序关系偏序关系例 A的幂

26、集上的关系的Hasse图。 a,b,cA=a,b,cba c a,b a,c b,c572.8 2.8 偏序关系偏序关系最大最小元最大最小元 对偏序集对偏序集 y0 A为最小元为最小元 ( x)(x Ay0 x)y0 A为最大元为最大元 ( x)(x Ax y0)定理定理 中最大中最大(最小最小)元若存在则唯一。元若存在则唯一。证明证明极大极小元极大极小元 对对 y0 A为极小元为极小元 ( x)(x A x y0 (x y0)y0 A为极大元为极大元 ( x)(x A x y0 (y0 x)582.8 2.8 偏序关系偏序关系例 2,3,6,12,24,36上的整除关系的Hasse图。 2

27、6 24 36 12 3 2, 3 为极小元 24, 36 为极大元 没有最小元和最大元592.8 2.8 偏序关系偏序关系例 A的幂集上的关系的Hasse图。 a,b,cA=a,b,cba c a,b a,c b,c 为最小元 a,b,c 为最大元602.8 2.8 偏序关系偏序关系上下界上下界 对对 , B A, a A a是是B的一个上界的一个上界 ( x)(x Bx a) a是是B的一个下界的一个下界 ( x)(x Ba x)阐明：阐明：a不一定是不一定是B的元素，即可能的元素，即可能 a A-BB的上的上(下下)界不一定存在，存在也不一定唯一。界不一定存在，存在也不一定唯一。612.

28、8 2.8 偏序关系偏序关系例 2,3,6,12,24,36上的整除关系的Hasse图。 2 6 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，下界是2622.8 2.8 偏序关系偏序关系上确界上确界 对对 , B A, a A是是B的一个上界。的一个上界。 a是是B的上确界的上确界 ( y)(y是是B的上界的上界a y)上确界若存在则唯一。上确界若存在则唯一。下确界下确界 对对 , B A, b A是是B的一个下界。的一个下界。 b是是B的下确界的下确界 ( x)(x是是B

29、的下界的下界x b)下确界若存在则唯一。下确界若存在则唯一。632.8 2.8 偏序关系偏序关系例 2,3,6,12,24,36上的整除关系的Hasse图。 2 6 24 36 12 3令B1=2,3,6 B1的上界是 6,12,24,36 B1的上确界是 6 B1没有下界也没有下确界令B2=2,6,12,24 B2的上界和上确界是24 B2的下界和下确界是2642.8 2.8 偏序关系偏序关系链与反链链与反链 对对 , B A, 若若B中任两个元素之间都中任两个元素之间都是可比较的，则称是可比较的，则称B是是A中的一条链。若中的一条链。若B中任两中任两个元素之间都是不可比较的，则称个元素之间

30、都是不可比较的，则称B是是A中的一条中的一条反链。反链。 2 6 24 36 12 3例 右边所示Hasse图中， 2,6,12,24 是一条链 2,3和24,36是反链留意： 2,3,24,36并非反链652.9 2.9 其他序关系其他序关系(1) 全序关系全序关系全序关系全序关系 设偏序集设偏序集 ，若，若A是一条链，则称是一条链，则称“ ” 为为A上的一个全序关系，此时称上的一个全序关系，此时称 是是一个全序集合。一个全序集合。(2) 偏序关系的逆关系偏序关系的逆关系定义定义 设偏序集设偏序集 ，定义，定义A上的关系上的关系“ ” x y x,y A y x 集合集合A和关系和关系“ ”

31、仍然构成一个偏序集仍然构成一个偏序集 。662.9 2.9 其他序关系其他序关系拓扑排序 一个偏序集可以表示一个工程中各个任务之间的依赖关系。如果一个时刻只能进行一个任务，那么整个工程的流程是一个与原偏序协调的全序。找出这个全序的过程称为拓扑排序。 定义设有偏序集, 如果存在一个全序*使得 x y 蕴含 x *y, 则称*是A上的一个拓扑排序。拓扑排序算法 问题 是否每个偏序集都存在拓扑排序？672.9 2.9 其他序关系其他序关系(3) 拟序关系拟序关系strict partial order）拟序关系拟序关系 集合集合A上的关系上的关系R满足反自反性和传递性满足反自反性和传递性时，称为时，

32、称为A上的一个拟序关系，用二元组上的一个拟序关系，用二元组 A, 表示该结构。表示该结构。定理定理 若若R为为A上的偏序关系，则上的偏序关系，则R-IA为为A上的拟序上的拟序关系。若关系。若R为为A上的拟序关系，则上的拟序关系，则R IA为为A上的上的偏序关系。偏序关系。682.9 2.9 其他序关系其他序关系定理定理 设有拟序集设有拟序集 A, ，对任何，对任何 x,y,z A, xy, x=y, yx 中至多有一种情况成立中至多有一种情况成立 (三分律三分律) ； x y x 那么那么 x=y，这里，这里 x y 表示表示 xy 或或 x=y。证明证明 利用拟序集的反自反性和传递性。利用拟序集的反自反性和传递性。692.9 2.9 其他序关系其他序关系(4) (4) 词典次序词典次序设字母表为设字母表为X X，“ ” 为为X X上的自然次序。显然上的自然次序。显然 X, 为全序集合。为全序集合。 长度为长度为2 2的词库的词库 A=X A=X X X 在在A A上定义全序关系上定义全序关系S S： S S (x1x2)(x