第七章-二元关系ppt课件.ppt

《第七章-二元关系ppt课件.ppt》由会员分享，可在线阅读，更多相关《第七章-二元关系ppt课件.ppt（113页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第七章 二元关系7.1 有序对与笛卡尔积 7.2 二元关系 7.3 关系的运算 7.4 关系的性质 7.5 关系的闭包 7.6 等价关系与划分 7.7 偏序关系 27.1 有序对与笛卡尔积一、有序对二、笛卡尔积3 1. 定义（定义7.1）2. 性质一、有序对 由两个元素由两个元素x和和y(允许允许x=y)，按一定顺序，按一定顺序组成的二元组称为有序对，记作组成的二元组称为有序对，记作。(1) 有序性有序性 （当（当x y时）时） (2) = 的充分必要条件是的充分必要条件是 x=u y=v如：平面直角坐标系中点的坐标如：平面直角坐标系中点的坐标。二、笛卡儿积4 设设A, B为集合，用为集合，

2、用A中元素为第一个元素，中元素为第一个元素，B中元素为第二个元素构成有序对。中元素为第二个元素构成有序对。 所有这所有这样的有序对组成的集合叫做样的有序对组成的集合叫做 A和和B 的笛卡儿的笛卡儿积，记作积，记作A B。 A B = | x A y B 1. 定义（定义7.2）5例：A=1,2, B=a,b,c A B =, B A =, 注意：若注意：若|A|=m, |B|=n, 则则 |A B|=mn。62. 性质： 对任意集合对任意集合A， A=A= 不适合交换律不适合交换律 A B B A (当当A B A B时时) 不适合结合律不适合结合律 (A B) C A (B C) (当当A

3、B C 时时) 对于并或交运算满足分配律对于并或交运算满足分配律 A (B C)=(A B) (A C) (B C) A=(B A) (C A) A (B C)=(A B) (A C) (B C) A=(B A) (C A) 7证明：A (B C)=(A B) (A C)证：证： 任取任取 A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC) 所以有所以有A(BC) = (AB)(AC).8 A C B D A B C D 证明：任取证明：任取 A B x A y B x C y D C D 注意：注意：A C B D是否推出是否推出 A B C D

4、？ 不一定！不一定！ 反例如下：反例如下： A=1，B=2, C=D=97.2 二元关系一、二元关系的定义二、二元关系的表示法10一、二元关系的定义1. 二元关系（定义7.3）2. 从A到B的二元关系（定义7.4）3. A上的某些特殊关系（定义7.5）4. A上的某些常用关系（P105）11如果一个集合满足以下条件之一：如果一个集合满足以下条件之一： (1)集合非空集合非空, 且它的元素都是有序对；且它的元素都是有序对； (2)集合是空集，集合是空集， 则称该集合为一个二元关系则称该集合为一个二元关系, 简称为关系，简称为关系，记作记作R。如果。如果R, 可记作可记作 xRy；如果；如果 R,

5、 则记作则记作x y。如：如：R=, S=,a,b. R是二元关系是二元关系, 当当a, b不是有序对时，不是有序对时，S不是二元关系不是二元关系根据上面的记法，可以写根据上面的记法，可以写 1R2, aRb, a c 等等. 1. 二元关系2. 从A到B的二元关系12 设设A，B为集合，为集合，AB的任何子集所定义的任何子集所定义的二元关系叫做从的二元关系叫做从A到到B的二元关系，当的二元关系，当A=B时则叫做时则叫做 A上的二元关系。上的二元关系。如：如：A=0,1, B=1,2,3, R1=, R2=AB, R3=, R4=. 那么那么 R1， R2， R3， R4是从是从 A 到到 B

6、的二的二元关系，元关系，R3和和R4同时也是同时也是 A上的二元关系。上的二元关系。|A|=n, |B|=m ，|AB|=nm，从，从A到到B的的二元关系有二元关系有2nm个，个，A上上的二元关系有的二元关系有 个。个。22n3. A上的某些特殊二元关系13 空关系：对于任何集合空关系：对于任何集合A ，是是A A的子集，的子集， 叫做叫做A上的空关系上的空关系。 全域关系全域关系EA ：EA=|xAyA=AA 恒等关系恒等关系IA：IA=|xA如，如，A=1,2，则，则 EA=, IA=,4. A上的某些常用二元关系14 小于等于关系小于等于关系 LA： LA=| x,yAxy，A R， 整

7、除关系整除关系DB：DB=| x,yBx整除整除y， B Z*, Z*为非为非0整数集。整数集。 包含关系包含关系R ： R =| x,yAx y, A是集合族。是集合族。 类似的还可以定义大于等于关系，小于类似的还可以定义大于等于关系，小于关系，大于关系关系，大于关系, 真包含关系等等。真包含关系等等。如：A = 1, 2, 3, B =a, b, 则 LA=, DA=,15 A=P(B)=,a,b,a,b, 则 A上的包含关系 R =, , 二、二元关系的表示法16 1. 集合表示法2. 关系矩阵3. 关系图1. 集合表示法17关系是一种特殊的集合关系是一种特殊的集合(元素为有序对元素为有

8、序对)。 列举法列举法 谓词表示法谓词表示法例：设A=1,2,3,4， R=| x/y是素数是A上的关系，用列举法表示R。 解：解：R=2. 关系矩阵18 设设A=a1, a2, , an，B=b1, b2, , bm，R是是从从A到到B的一个二元关系，称矩阵的一个二元关系，称矩阵MR = rij n m为关系为关系R的关系矩阵，其中：的关系矩阵，其中： 1， R rij = (i=1,2,n,j=1,2,m) 0， R注意：注意：A的元素个数确定行数；的元素个数确定行数； B的元素个数确定列数。的元素个数确定列数。 若若R为为A上的关系，则关系矩阵为上的关系，则关系矩阵为n阶方阵。阶方阵。1

9、93. 关系图 设设A=a1, a2, , an，B=b1, b2, , bm，R是从是从A到到B的一个二元关系，则对应关系的一个二元关系，则对应关系R的关的关系图是系图是GR=，其中，其中V为结点集，为结点集，R为边为边集。如果集。如果属于关系属于关系R，在图中就有一条，在图中就有一条从从 xi 到到 xj 的有向边。的有向边。注意：注意：A, B为有穷集，关系矩阵适于表示从为有穷集，关系矩阵适于表示从A到到B的关系或者的关系或者A上的关系，关系图适于表示上的关系，关系图适于表示A上的关系。上的关系。20例：A=1,2,3,4, R=,R的关系矩阵MR和关系图GR如下： 0010000011

10、000011RM217.3 关系的运算 一、关系的集合运算二、关系的基本运算三、基本运算的性质四、关系的方幂运算一、关系的集合运算22 根据关系的定义知，关系就是集合，所以在第6章中所给出的集合的运算对于关系也适用。 设R和S是集合A到B的关系，则关系的并、交、相对补、绝对补、对称差运算为RS 、 RS、 RS、 R(S)、 RS。注意：注意： 1. A到到B的全域关系为的全域关系为AB，它就是讨论，它就是讨论 集合时的全集集合时的全集。 2. 若若R和和S是集合是集合A上的关系，则其运算后上的关系，则其运算后 仍是仍是A上的关系；上的关系；返回二、关系的基本运算23 1. 定义域、值域和域（

11、定义7.6）2. 关系的逆运算3. 右复合 4. 限制与像返回1. 定义域、值域 和域24定义域定义域domR = x | y ( R) 值域值域ranR = y | x ( R) 域域fldR = domR ranR 例：R=, 则 domR=1, 2, 4 ranR=2, 3, 4 fldR=1, 2, 3, 4 2. 关系的逆运算25 设设R为二元关系，为二元关系，R 1 称为称为R的逆关系。的逆关系。 R AB ，R 1 BA。 R 1 = | R例：设A=1,2,3,4 R=, , , R 1=, , , 26注意：注意： 1. 对任意关系对任意关系R，都存在，都存在R 1 。( -

12、1=) 2. R和和R 1是建立在不同集合上的是建立在不同集合上的(A上的上的关系除外关系除外) 。 3. 将将R的关系图上所有弧线改变方向，就的关系图上所有弧线改变方向，就得到得到R 1的关系图；的关系图； R 1的关系矩阵的关系矩阵MR-1就是就是MR的转置矩阵的转置矩阵(行列颠倒行列颠倒)。3. 右复合27理解：理解：x是是t的母亲，的母亲，t是是y的妻子；的妻子； x是是t的父亲，的父亲，t是是y的父亲。的父亲。F G = | t ( F G) 例：设例：设F=, , G= ，则，则 F G = G F =28注意：注意： 1. 不是任意两个关系都求复合的，不是任意两个关系都求复合的，

13、 F AB , G BC , F G 才有意义才有意义； 2. 若若F AB , G BA , F G、G F 都有意义；若都有意义；若F、G是是A上的关系，则上的关系，则 F G、G F都有意义；都有意义； 3. 即使即使F G、G F都有意义，也不能都有意义，也不能保保 证证F G=G F ；29例： A=0,1,2,3 , A上的关系F，G定义如下，计算F G、G F。 F= | x, yA , y=x+1或y=x/2 G= | x, yA , x=y+2 解：解： F= , , , , G= , F G=, G F=,注意：求两个关系复合的时候，要注意它们注意：求两个关系复合的时候，要

14、注意它们 的顺序。的顺序。复合运算的图示方法30 利用图示（不是关系图）方法求复合。利用图示（不是关系图）方法求复合。 R=, , , S=, , , , R S = , , , S R =, , 4. 限制与像设设R为二元关系，为二元关系，A是集合是集合(1) R在在A上的限制，记作上的限制，记作R A R A = | xRy x A(2) A 在在R下的像记作下的像记作RA = ran(R A) 31例：R=, , , R 1=, R1=2,4 R = R1,2=2,3,4注意：注意：R A R, RA ranR 红色是限制条件，红色是限制条件，在在R中寻找满足中寻找满足条件的元素。条件的

15、元素。“限制限制”是有序是有序对的集合。对的集合。运算顺序32 本节所定义的关系运算中逆运算优先于其他运算，而所有的关系运算都优先于集合运算，对于没有规定优先权的运算以括号决定运算顺序。返回三、基本运算的性质（定理7.1-7.5） 33定理7.1 设F是任意的关系, 则 (1) (F1)1=F (2) domF1=ranF, ranF1=domF证：证： (1) 任取任取, 由逆的定义有由逆的定义有 (F 1) 1 F 1 F所以有所以有 (F 1) 1=F (2) 任取任取x, xdomF 1 y(F 1) y(F) xranF 所以有所以有domF 1= ranF. 同理可证同理可证 ra

16、nF 1 = domF.34定理7.2 设F, G, H是任意的关系, 则 (1) (F G) H=F (G H) (2) (F G)1= G1 F1 证：证： (1) 任取任取, (F G) H t(F G H) t ( s (FG) H) t s (F GH) s (F t (GH) s (FG H) F (G H) 所以所以 (F G) H = F (G H)35 (2) 任取任取, (F G) 1 F G t ( F (t,x) G) t ( G 1 (t,y) F 1) G 1 F 1 所以所以 (F G) 1 = G 1 F 1 36定理7.3 设R为A上的关系, 则 R IA=I

17、A R=R定理7.4 设F、G、 H为任意的关系，则： (1) F (G H ) =F G F H (2) (G H ) F = G F H F (复合运算对复合运算对 运算满足分配律运算满足分配律） (3) F (G H ) F G F H (4) (G H ) F G F H F (复合运算对复合运算对 运算分配后是包含关系运算分配后是包含关系）37定理7.5 设F为关系，A、B为集合，则： (1) F (A B)= F A F B (2) FA B= FA F B (3) F (A B)= F A F B (4) FA B FA F B返回四、关系的方幂运算38在右复合运算的基础上定义关

18、系的幂运算。1. 定义（定义7.10）2. 求法3. 性质（定理7.6-7.7）按定义直接求解；按定义直接求解；关系矩阵；关系矩阵；关系图。关系图。1. 定义39 设设R为为A上的关系，上的关系， n为自然数，为自然数， 则则 R 的的 n次幂定义为：次幂定义为： (1) R0= | xA =IA (2) Rn+1 = Rn R 注意：注意： 1. 对于对于A上的任何关系上的任何关系R1和和R2都有都有 R10 = R20 = IA； 2. 对于对于A上的任何关系上的任何关系 R 都有都有R1 = R 。2. 求法40R0=IA ，R1 = R，n2时时 按定义直接求解按定义直接求解 如果如果

19、R是用集合表达式给出的，可以通过是用集合表达式给出的，可以通过n-1次右复合计算得到次右复合计算得到Rn 关系矩阵关系矩阵 Rn的关系矩阵是的关系矩阵是Mn，即，即n个矩阵个矩阵M之积。之积。41 关系图关系图 第一步：画出第一步：画出R的关系图的关系图(R1)； 第二步：从第二步：从R的每一结点出发，如果能的每一结点出发，如果能经过经过n段有向弧止于某一结点，则从始点到终段有向弧止于某一结点，则从始点到终点画一条有向弧；点画一条有向弧； 若结点有自环，则从该结点出发后，经若结点有自环，则从该结点出发后，经过过1、2、3段有向弧，均能回到该结点自段有向弧，均能回到该结点自身。身。42例：设A=

20、a,b,c,d, R=, 求R的各次幂, 分别用关系矩阵和关系图表示。 解：解： R与与R2的关系矩阵分别为的关系矩阵分别为 0000100001010010M 0000000010100101000010000101001000001000010100102M43同理，同理，R0=IA， R3和和R4的矩阵分别是：的矩阵分别是：因此因此M4=M2, 即即R4=R2. 因此可以得到因此可以得到 R2=R4=R6=, R3=R5=R7= 0000000010100101,000000000101101043MM 10000100001000010M注意：对于有穷集注意：对于有穷集A，A上关系上关

21、系R的不同幂只的不同幂只 有有限个。有有限个。44R0，R1，R2，R3的关系图如下图所示：的关系图如下图所示：3.性质45定理定理7.6 设设A为为n元集，元集，R是是A上的关系上的关系, 则存则存 在自然数在自然数 s 和和 t，使得，使得 Rs = Rt。定理定理7.7 设设 R 是是 A 上的关系上的关系, m, nN, 则则 (1) Rm Rn=Rm+n（第一指数律）（第一指数律） (2) (Rm)n=Rmn （第二指数律）（第二指数律）467.4 关系的性质 一、自反性与反自反性二、对称性与反对称性三、传递性四、关系性质的判别五、关系性质的证明六、关系的运算与性质的关系对于集合对于

22、集合A上上的关系的关系R AA，最常，最常见的性质有见的性质有5种。种。一、自反性与反自反性471.定义 设设R为为A上的关系上的关系, (1) 若若 x(xA R), 则称则称R在在A上是上是 自反的。自反的。 (2) 若若 x(xA R), 则称则称R在在A上是上是 反自反的。反自反的。48注意：注意： 1. 在集合在集合A上的自反关系上的自反关系R中，中，A的每一的每一个元素个元素x都与它自身有关系都与它自身有关系R；任一有序对；任一有序对R，xy是允许的，但必须包括对任一是允许的，但必须包括对任一元素元素xA，有，有R； 2. 在反自反关系中，不能有任何一个相在反自反关系中，不能有任何

23、一个相同元素同元素x组成的有序对组成的有序对，即，即 R。49自反关系：自反关系：A上的全域关系上的全域关系EA, 恒等关系恒等关系IA ， 小于等于关系小于等于关系LA, 整除关系整除关系DA， 幂集幂集P(A)上的包含关系。上的包含关系。反自反关系：实数集上的小于关系，反自反关系：实数集上的小于关系， 幂集幂集P(A)上的真包含关系，上的真包含关系， 空集上的关系只有空关系一个，既是自空集上的关系只有空关系一个，既是自反的，又是反自反的。反的，又是反自反的。例：A=1,2,3, R1, R2, R3是A上的关系, 其中 R1, R2, R350R2自反自反, R3反自反反自反, R1既不是

24、自反也不是反自反的。既不是自反也不是反自反的。此例说明：任一二元关系，仅为自反的，反此例说明：任一二元关系，仅为自反的，反自反的，既不是自反的又不是反自反的，三自反的，既不是自反的又不是反自反的，三者之一。者之一。512. 定理（定理7.9） 设设R为为A上的关系上的关系, 则则 (1) R在在A上自反当且仅当上自反当且仅当 IA R (2) R在在A上反自反当且仅当上反自反当且仅当 RIA=二、对称性与反对称性521.定义 设设R为为A上的关系上的关系, (1) 若若 x y(x,yARR), 则称则称R为为A上对称的关系。上对称的关系。 (2)若若 x y(x,yARRx=y), 则称则称

25、R为为A上的反对称关系。上的反对称关系。53注意：注意： 1. 在在A上的对称关系上的对称关系R中，若中，若A中元素中元素x与与 y有关系有关系R时，则时，则y与与x也一定有关系也一定有关系R； 2. 在反对称关系在反对称关系R中，若中，若xy，则，则 R与与R不能同时存在不能同时存在 。对称关系：对称关系：A上的全域关系上的全域关系EA 恒等关系恒等关系IA 空关系空关系。反对称关系：恒等关系反对称关系：恒等关系IA，空关系空关系。例：设A1,2,3, R1, R2, R3和R4都是A上的关系, R1,， R2, R3,， R4, 54R1 对称、反对称。对称、反对称。 R2 对称，不反对称

26、。对称，不反对称。R3 反对称，不对称。反对称，不对称。 R4 不对称、也不反对称。不对称、也不反对称。552. 定理 设设R为为A上的关系上的关系, 则则 (1) R在在A上对称当且仅当上对称当且仅当 R=R 1 (2) R在在A上反对称当且仅当上反对称当且仅当 RR 1 IA R在对称的又是反对称当且仅当在对称的又是反对称当且仅当 R IA三、传递性 561.定义 设设R为为A上的关系上的关系, 若若 x y z(x,y,zAR RR), 则称则称R是是A上的传递上的传递关系。关系。例：设A1,2,3, R1, R2, R3是A上的关系, 其中R1, R2, R357R1 和和 R3 是是

27、A上的传递关系，上的传递关系， R2不是不是A上的传递关系。上的传递关系。 A上的全域关系上的全域关系EA,恒等关系恒等关系IA和空关系和空关系，小于等于关系小于等于关系, 小于关系，整除关系，包含关小于关系，整除关系，包含关系，真包含关系都是传递关系。系，真包含关系都是传递关系。582. 定理 设设R为为A上的关系上的关系, 则则 (1) R在在A上传递当且仅当上传递当且仅当 R R R 返回四、关系性质的判别59自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性表达式表达式IA RRIA=R=R 1 RR 1 IA R R R关系关系矩阵矩阵主对角线主对角线元素全是元素全

28、是1主对角线主对角线元素全是元素全是0对称矩阵对称矩阵若若rij1, 且且ij, 则则rji0对对M2中中1所在位置所在位置,M中相应中相应位置都是位置都是1关系图关系图每个顶点每个顶点都有环都有环每个顶点每个顶点都没有环都没有环如果两个如果两个顶点之间顶点之间有边有边, 是是一对方向一对方向相反的边相反的边(无单边无单边)如果两点之如果两点之间有边间有边, 是一是一条有向边条有向边(无无双向边双向边)如果顶点如果顶点 xi 连通到连通到xk , 则从则从 xi到到 xk 有有边边 60例：判断下图中关系的性质，并说明理由。(2)反自反，不是自反的；反对称，不是对称的；反自反，不是自反的；反对

29、称，不是对称的； 是传递的。是传递的。(1)不自反也不反自反；对称不自反也不反自反；对称, 不反对称；不传递。不反对称；不传递。(3)自反，不反自反；反对称，不是对称；不传递。自反，不反自反；反对称，不是对称；不传递。返回五、关系性质的证明61自反性证明模式：证明R在A上自反 任取x, xA . R 前提 推理过程 结论例：证明若 IA R ，则 R在A上自反。证：证： 任取任取x, x A IA R 因此因此 R 在在 A 上是自反的。上是自反的。62对称性证明模式 ：证明R在A上对称 任取 R . R 前提 推理过程 结论例：证明若 R=R1 , 则R在A上对称。证：任取证：任取 R R

30、1 R 因此因此 R 在在 A 上是对称的。上是对称的。63反对称性证明模式：证明R在A上反对称 任取 RR . x=y 前提 推理过程 结论例：证明若 RR1IA , 则R在A上反对称。 证：任取证：任取 R R R R 1 RR 1 IA x=y 因此因此 R 在在 A 上是反对称的。上是反对称的。64传递性证明模式：证明R在A上传递 任取， RR . R 前提 推理过程 结论例：证明若 RRR , 则R在A上传递。 证：任取证：任取， R R R R R 因此因此 R 在在 A 上是传递的。上是传递的。六、关系的运算与性质的关系65自反性自反性 反自反性反自反性对称性对称性反对称性反对称

31、性传递性传递性R1 1 R1R2 R1R2 R1 R2 R1 R2 667.5 关系的闭包 一、关系的闭包概念二、闭包的构造方法三、闭包的性质四、多重闭包67 关系的闭包运算，是一种比较特殊而有用的运算，它采用对已知关系扩充一些有序对的办法，从而得到具有某种性质的新关系。 闭包：包含一些给定对象，具有指定性质的最小集合。一、关系的闭包概念68 设设R是非空集合是非空集合A上的关系，上的关系，R的自反的自反(对对称或传递称或传递)闭包是闭包是A上的关系上的关系R ，使得，使得R 满足以满足以下条件：下条件：(1) R 是自反的（对称的或传递的）是自反的（对称的或传递的）(2) R R (3) 对

32、对A上任何包含上任何包含R的自反的自反(对称或传递对称或传递)关系关系 R 有有 RR 。 一般将一般将 R 的自反闭包记作的自反闭包记作 r(R) ，对称闭，对称闭包记作包记作 s(R) ，传递闭包记作，传递闭包记作 t(R) 。69例：设集合A=a,b,c，A上的关系 R=,，则，则 r(R)= s(R)= t(R)= , ，,，,，返回二、闭包的构造方法70 1. 集合表达式法2. 关系矩阵法3. 关系图法711. 集合表达式法 设设R为为A上的关系上的关系, 则有则有 (1) r(R) = RR0= RIA (2) s(R) = RR 1(3) t(R) = RR2R3注意：注意： 对

33、于有穷集合对于有穷集合A (|A|=n) 上的关系，上的关系，(3)中中的并是有限的的并是有限的(书书P119推论推论)。 2. 关系矩阵72 设关系设关系R，r(R) ， s(R) ， t(R)的关系矩阵的关系矩阵分别为分别为M，Mr，Ms 和和 Mt ，则，则 Mr = M + E Ms = M + M Mt = M + M2 + M3 + 注意：注意： 1. E 是和是和 M 同阶的单位矩阵，同阶的单位矩阵，M是是 M 的转置矩阵。的转置矩阵。 2. 在上述等式中矩阵的元素相加时使用在上述等式中矩阵的元素相加时使用 逻辑加。逻辑加。3. 关系图73 设关系设关系R，r(R) ， s(R)

34、 ， t(R)的关系图分的关系图分别记为别记为G，Gr， Gs， Gt ， 则则Gr，Gs，Gt 的顶的顶点集与点集与G 的顶点集相等。除了的顶点集相等。除了G 的边以外，依的边以外，依下述方法添加新边：下述方法添加新边： 74 考察考察G的每个顶点，如果没有环就加的每个顶点，如果没有环就加上一个环，最终得到上一个环，最终得到Gr。 考察考察G的每条边的每条边, 如果有一条如果有一条 xi 到到 xj 的单向边，的单向边，ij, 则在则在G中加一条中加一条 xj 到到 xi 的反的反方向边，最终得到方向边，最终得到Gs。 考察考察G的每个顶点的每个顶点 xi，找从，找从 xi 出发的出发的每一

35、条路径，如果从每一条路径，如果从 xi 到路径中任何结点到路径中任何结点 xj 没有边，就加上这条边。当检查完所有的顶没有边，就加上这条边。当检查完所有的顶点后就得到图点后就得到图Gt 。75例：设A=a,b,c,d， R=,， R和 r(R), s(R), t(R)的关系图如下图所示。Rr(R)s(R)t(R)返回三、闭包的性质761. 定理7.11 设设R是非空集合是非空集合A上的关系，则上的关系，则 (1) R是自反的当且仅当是自反的当且仅当r(R)=R； (2) R是对称的当且仅当是对称的当且仅当s(R)=R; (3) R是传递的当且仅当是传递的当且仅当t(R)=R。2. 定理7.12

36、 设设R1和和R2是非空集合是非空集合A上的关系，且上的关系，且R1 R2，则，则 (1) r(R1) r(R2) (2) s(R1) s(R2) (3) t(R1) t(R2) 773. 定理7.13 设设R是非空集合是非空集合A上的关系，上的关系， (1) 若若R是自反的，则是自反的，则s(R)与与t(R)也是自反的；也是自反的； (2) 若若R是对称的，则是对称的，则r(R)与与t(R)也是对称的；也是对称的； (3) 若若R是传递的，则是传递的，则r(R)是传递的。是传递的。返回四、多重闭包78注意：注意： 对于多重闭包，规定从右至左依次进行对于多重闭包，规定从右至左依次进行运算，注意

37、顺序。运算，注意顺序。tsr(R) =t(s(r(R) 返回797.6 等价关系与划分一、等价关系二、等价类三、集合的划分 等价关系在数学上是分类用的。我们从等价关系在数学上是分类用的。我们从小就开始使用的最简单、最常用的等价关系小就开始使用的最简单、最常用的等价关系就是数的就是数的“相等相等”关系。关系。一、等价关系（定义7.15）80 设设 R 为非空集合为非空集合A上的关系，如果上的关系，如果 R 是是自反的、对称的和传递的，则称自反的、对称的和传递的，则称 R 为为 A 上的上的等价关系。设等价关系。设 R 是一个等价关系，若是一个等价关系，若R，称，称 x 等价于等价于y，记做，记做

38、 xy。判断：判断： 恒等关系恒等关系IA与全域关系与全域关系EA 数的数的“大于等于大于等于”关系；关系； 集合之间的集合之间的“包含包含”关系；关系； 人与人之间的人与人之间的“同学同学”、“同姓同姓”、“同年龄同年龄”、“同性别同性别”关系。关系。验证模验证模 3 相等关系相等关系 R 为为 A上的等价关系，因为上的等价关系，因为 xA，有，有x x(mod 3) x, yA，若，若 x y(mod 3)，则有，则有 y x(mod 3) x, y, zA, 若若x y(mod 3)，y z(mod 3)， 则有则有 xz(mod 3)自反性、对称性、传递性得到验证。自反性、对称性、传递

39、性得到验证。81例：设 A=1,2,8，如下定义A上的关系 R： R = | x,yAxy(mod 3) 其中 xy(mod 3) 叫做 x 与 y 模3相等，即 x 除以3的余数与 y 除以3的余数相等。82设设 A=1,2,8, R= | x,yAxy(mod 3) R的关系图如下图所示。的关系图如下图所示。 关系图被分为三个互不连通的部分，每部关系图被分为三个互不连通的部分，每部分中的数两两都有关系，不同部分中的数则分中的数两两都有关系，不同部分中的数则没有关系，每一部分中的所有顶点构成一个没有关系，每一部分中的所有顶点构成一个等价类。等价类。返回二、等价类83 1. 定义（定义7.16

40、）2. 性质（定理7.14）3. 商集（定义7.17）84 设设R为非空集合为非空集合A上的等价关系，上的等价关系， xA，令令xR = y | yAxRy ，称，称 xR 为为 x 关于关于R 的等价类，简称为的等价类，简称为 x 的等价类，简记为的等价类，简记为x。A= 1, 2, , 8 上模上模 3 等价关系的等价类：等价关系的等价类： 1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,61. 定义(定义7.16) 注意：注意： x 的等价类就是所有与的等价类就是所有与x有等价关系有等价关系R 的元素组成的集合。它一定是的元素组成的集合。它一定是A的子集。的子集。85例：设A

41、=a,b,c， R=,， R是A上的等价关系，求A中各元素所在的等价类。解：解： aR=a bR=b,c cR=b,c2. 等价类的性质 86定理定理7.14 设设R是非空集合是非空集合A上的等价关系，则上的等价关系，则 (1) xA，x 是是A的非空子集。的非空子集。 (2) x, yA，如果，如果 x R y，则，则 x=y。 (3) x, yA，如果，如果 x y，则，则 x与与y不交。不交。 (4) x | xA=A，即所有等价类的并集就，即所有等价类的并集就 是是A。 3. 商集87 设设R为非空集合为非空集合A上的等价关系，以上的等价关系，以R的所的所有等价类作为元素的集合称为有等

42、价类作为元素的集合称为A关于关于R的商集，的商集，记做记做A/R，A/R = xR | xA 。例：A=1,2,8， A关于模3等价关系R的商集为： A/R = 1,4,7, 2,5,8, 3,6 A关于恒等关系和全域关系的商集为： A/IA = 1,2, ,8 A/EA = 1, 2, ,8 返回三、集合的划分88 举重比赛时，需要将运动员按重量级别来进行分类，每个运动员必定属于某一级别，而任何运动员不能同时属于两个不同的重量级别。1. 定义（定义7.18）2. 等价关系与划分的一一对应 891. 定义 (定义7.18) 注意：注意：“划分划分”的概念和的概念和“等价关系等价关系”的概的概

43、念本质上是一样的。念本质上是一样的。 设设A为非空集合，若为非空集合，若A的子集族的子集族( P(A) 满足下面条件：满足下面条件： (1) (2) x y (x,yxyxy=) (3) =A 则称则称是是A的一个划分，称的一个划分，称中的元素为中的元素为A的划分块。的划分块。例：设Aa, b, c, d, 给定1 6如下： 1= a, b, c, d ， 2= a, b, c, d 3= a, a, b, c, d , 4= a, b, c 5= ,a, b, c, d , 6= a, a, b, c, d 90解：解：1和和2 是是A的划分，其他都不是的划分，其他都不是 A 的划分。的划分

44、。2. 等价关系与划分的一一对应91 商集商集 A/R 就是就是 A 的一个划分；的一个划分； 不同的商集对应于不同的划分；不同的商集对应于不同的划分； 任给任给 A 的一个划分的一个划分, 如下定义如下定义 A 上的关上的关系系 R： R = | x,yAx 与与 y 在在的同一的同一划分块中划分块中，则，则 R 为为 A上的等价关系，且该等上的等价关系，且该等价关系确定的商集就是价关系确定的商集就是。92 R3=,IA例：给出A1,2,3上所有的等价关系。求解思路：先做出求解思路：先做出A的所有划分，然后根据划的所有划分，然后根据划分写出对应的等价关系。分写出对应的等价关系。 R4=全域关

45、系全域关系 EAR5=恒等关系恒等关系 IAR1=,IAR2=,IA93例：设 A=1, 2, 3, 4，在 A A上定义二元关 系R：, R x+y = u+v， 求 R 导出的划分。解解：A A=, , , , , , , , , , , , , , 根据根据 的的 x + y = 2,3,4,5,6,7,8 将将A A划分成划分成7个等价类：个等价类： (A A)/R= , , , , , , , , , , , , , , 94返回957.7 偏序关系一、偏序关系二、偏序关系的哈斯图三、偏序集中的特殊元素96 在解决实际问题时，常依据某个标准对事物进行比较，同时按这个标准对两个事物之间

46、的先后进行排序。在计算机科学中，对数据进行排序是十分有意义的。 偏序关系是最基本、最常用的一种序关系，它本质上是两实数之间的“小于等于”关系的一种推广。一、偏序关系97 1. 定义（定义7.19）2. x与y可比3. 全序关系（定义7.21）1. 定义(定义7.19)98 非空集合非空集合A上的自反、反对称和传递的关上的自反、反对称和传递的关系，称为系，称为A上的偏序关系，记作上的偏序关系，记作 。设。设 为偏为偏序关系，如果序关系，如果 ，则记作，则记作 x y，读作，读作 x“小于等于小于等于”y。 集合集合A上的恒等关系上的恒等关系 IA 和空关系和空关系是是A上上的偏序关系。的偏序关系

47、。 小于等于关系小于等于关系, 整除关系和包含关系也是整除关系和包含关系也是相应集合上的偏序关系。相应集合上的偏序关系。 注意：这里的注意：这里的“小于等于小于等于”不是指数的大小，而是不是指数的大小，而是指在偏序关系中的顺序性。指在偏序关系中的顺序性。992. x与 y 可比： 设设R为非空集合为非空集合A上的偏序关系上的偏序关系, x,y A, x与与y可比可比 x y y x.结论：任取两个元素结论：任取两个元素x和和y, 可能有下述情况：可能有下述情况： x y (或或y x), xy, x与与y不是可比的。不是可比的。3. 全序关系(定义7.21)： 100R为非空集合为非空集合A上

48、的偏序上的偏序, 如果如果 x,y A, x与与 y 都是可比的，则称都是可比的，则称 R 为全序关系。为全序关系。例：数集上的小于等于关系是全序关系；例：数集上的小于等于关系是全序关系； 整除关系不是正整数集合上的全序关系。整除关系不是正整数集合上的全序关系。101二、偏序集与哈斯图1. 偏序集（定义7.22）2. 覆盖（定义7.23）3. 哈斯图102 集合集合A和和A上的偏序关系上的偏序关系 一起叫做偏序一起叫做偏序集集, 记作记作 。例：例： 1. 整数集和整数的小于等于关系构成偏序整数集和整数的小于等于关系构成偏序 集集， 2. 集合集合A的幂集的幂集P(A)和包含关系和包含关系R

49、构成偏构成偏 序集序集.1. 偏序集2. 覆盖 103例：例： 1, 2, 4, 6 集合上的整除关系集合上的整除关系, 2 覆盖覆盖 1, 4 和和 6 覆盖覆盖 2， 4 不覆盖不覆盖 1， 6 不覆盖不覆盖 4。 设设为偏序集为偏序集, x, yA, 如果如果 x y且不存在且不存在 z A 使得使得 x z y, 则称则称 y 覆盖覆盖x。1043. 哈斯图 由于偏序关系本身具备的特性，在用关系图来描述偏序关系且不引起混乱时，可以将其中的一些显然的因素略去不管。 利用偏序自反、反对称、传递性简化的关系图。注意：在哈斯图中，每个结点没有环；两个注意：在哈斯图中，每个结点没有环；两个连通的

50、结点之间的偏序关系通过结点位置的连通的结点之间的偏序关系通过结点位置的高低表示，位置低的元素的顺序在前，具有高低表示，位置低的元素的顺序在前，具有覆盖关系的两个结点之间连边。覆盖关系的两个结点之间连边。105例7.19 画出下列偏序关系的哈斯图。 106A=a, b, c, d, e, f, g, h R=,IA 例7.20： 已知偏序集的哈斯图如右图所示, 试求出集合A和关系R的表达式. 三、偏序集的特殊元素107 在偏序集中，设B A，对于A中的偏序而言，B中处于某些特殊位置的元素是很重要的。注意：建议在理解这些元素时，将偏序当作注意：建议在理解这些元素时，将偏序当作 “小于等于小于等于”