第第7 7章章 二元关系二元关系离离 散散 数数 学学大学本科生课程大学本科生课程计算机系计算机系计算机系计算机系本章说明本章说明本章说明本章说明q本章的主要内容本章的主要内容有序对与笛卡儿集有序对与笛卡儿集二元关系的定义和表示法二元关系的定义和表示法关系的运算关系的运算关系的性质关系的性质关系的闭包关系的闭包等价关系与划分等价关系与划分偏序关系偏序关系q本章与后续各章的关系本章与后续各章的关系本章是函数的基础本章是函数的基础本章是图论的基础本章是图论的基础 本章内容本章内容本章内容本章内容7.1 7.1 有序对与笛卡儿积有序对与笛卡儿积7.2 7.2 二元关系二元关系7.3 7.3 关系的运算关系的运算7.4 7.4 关系的性质关系的性质7.5 7.5 关系的闭包关系的闭包7.6 7.6 等价关系与划分等价关系与划分7.7 7.7 偏序关系偏序关系 本章小结本章小结 习题习题 作业作业7.1 7.1 有序对与笛卡儿积有序对与笛卡儿积有序对与笛卡儿积有序对与笛卡儿积 定义定义7.17.1 由两个元素由两个元素x x和和y y（允许允许x=yx=y）按一定顺序排列成的二元按一定顺序排列成的二元组叫做一个组叫做一个有序对有序对( (ordered pair) )或或序偶序偶，记作，记作 x,y，其中其中x x是它的第一元素，是它的第一元素，y y是它的第二元素。是它的第二元素。有序对有序对 x,y具有以下性质：具有以下性质： （1 1）当当xyxy时，时， x,y。 （2 2） x,y的充分必要条件是的充分必要条件是x xu u且且y yv v。 说明说明q有序对中的元素是有序的有序对中的元素是有序的q集合中的元素是无序的集合中的元素是无序的例例例例7.17.17.17.1例例7.17.1 已知已知 x+2,4，求求x x和和y y。 由有序对相等的充要条件有由有序对相等的充要条件有 x+2x+25 52 2x+yx+y4 4 解得解得 x x3,y3,y-2-2。 解答解答定义定义7.27.2 设设A A，B B为集合为集合, ,用用A A中元素为第一元素，中元素为第一元素，B B中元素为第中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做二元素构成有序对。所有这样的有序对组成的集合叫做A A和和B B的的笛卡儿积笛卡儿积( (Cartesian product)，记作，记作ABAB。笛卡儿积的符号化表示为笛卡儿积的符号化表示为ABAB|xAyB |xAyB 笛卡儿积笛卡儿积笛卡儿积笛卡儿积的定义的定义的定义的定义qA A表示某大学所有学生的集合，表示某大学所有学生的集合，B B表示大学开设的所有表示大学开设的所有课程的集合，课程的集合，则则A AB B可以用来表示该校学生选课的所有可能情况。可以用来表示该校学生选课的所有可能情况。q令令A A是直角坐标系中是直角坐标系中x x轴上的点集，轴上的点集，B B是直角坐标系中是直角坐标系中y y轴上的点集，轴上的点集，于是于是A AB B就和平面点集一一对应。就和平面点集一一对应。 举例举例笛卡尔积举例笛卡尔积举例笛卡尔积举例笛卡尔积举例设设A=a,b, B=0,1,2A=a,b, B=0,1,2，则则A AB=,B=,B BA=, A=, 举例举例说明说明q如果如果| |A|=m,|B|=n,A|=m,|B|=n,则则| |A AB|=B|=mnmn。笛卡儿积的运算性质笛卡儿积的运算性质笛卡儿积的运算性质笛卡儿积的运算性质 (1)(1)对任意集合对任意集合A A，根据定义有根据定义有AA, , AA(2)(2)一般的说，一般的说，笛卡儿积运算不满足交换律笛卡儿积运算不满足交换律，即，即ABBA ABBA ( (当当 AA B B AB AB 时) )(3)(3)笛卡儿积运算不满足结合律笛卡儿积运算不满足结合律，即，即( (AB)CA(BC)AB)CA(BC)( (当当 AA B B C C 时) )(4)(4)笛卡儿积运算对并和交运算满足分配律笛卡儿积运算对并和交运算满足分配律，即，即A(BA(BC)=(AB)C)=(AB)(AC)(AC)( (B BC)A=(BA)C)A=(BA)(CA)(CA)A(BA(BC)=(AB)C)=(AB)(AC)(AC)( (B BC)A=(BA)C)A=(BA)(CA)(CA)(5)(5)A A C BC B D D AB AB CD CDA(BC)=(AB)(AC)A(BC)=(AB)(AC)A(BC)=(AB)(AC)A(BC)=(AB)(AC)的证明的证明的证明的证明任取任取 x,y A(BC)x,yA(BC) xA yBC xA yBC xA (yByC) xA (yByC) (xAyB) (xAyC) (xAyB) (xAyC) AB AC AB AC (AB)(AC) (AB)(AC) 所以所以 A(BA(BC)=(AB)C)=(AB)(AC)(AC)关于关于关于关于A A A A CBCBCBCB D D D D AB AB AB AB CDCDCDCD的讨论的讨论的讨论的讨论该性质的逆命题不成立，可分以下情况讨论。该性质的逆命题不成立，可分以下情况讨论。（1 1）当）当A=B=A=B=时，显然有时，显然有A A C C 和和 B B D D 成立。成立。（2 2）当）当AA且且BB时，也有时，也有A A C C和和B B D D成立，证明如下：成立，证明如下：任取任取x xA A，由于由于BB, ,必存在必存在y yB,B,因此有因此有 x xA Ay yB B ABAB CDCD x xC Cy yD D x xC C从而证明了从而证明了 A A C C。同理可证同理可证 B B D D。关于关于关于关于A A A A CBCBCBCB D D D D AB AB AB AB CDCDCDCD的讨论的讨论的讨论的讨论该性质的逆命题不成立，可分以下情况讨论。该性质的逆命题不成立，可分以下情况讨论。（3 3）当）当A A而而BB时，有时，有A A C C成立，但不一定有成立，但不一定有B B D D成立。成立。 反例：令反例：令A A,B,B1,C1,C3,D3,D44。（4 4）当）当AA而而B B时，有时，有B B D D成立，但不一定有成立，但不一定有A A C C成立。成立。 反例略。反例略。 例例例例7.27.27.27.2例例7.2 7.2 设设A=1,2,A=1,2,求求P(A)P(A)A A。 P(A)P(A)A A ,1,2,1,2,1,2,1,21,21,2 ,2, , 解答解答例例例例7.37.37.37.3例例7.3 7.3 设设A A，B B，C C，D D为任意集合，判断以下命题是否为真，并为任意集合，判断以下命题是否为真，并说明理由。说明理由。(1) (1) A AB BA AC C B BC C(2) (2) A-(BA-(BC)C)(A-B)(A-B)(A-C)(A-C)(3) (3) A AB BC CD D A AC CB BD D(4) (4) 存在集合存在集合A A，使得使得A A A AA A(1) (1) 不一定为真。当不一定为真。当A A，B B1,C1,C22时，有时，有 A AB BA AC C，但但BCBC。(2) (2) 不一定为真。当不一定为真。当A=B=1,CA=B=1,C22时，有时，有 A-(B A-(BC)C)1111 ( (A-B)A-B)(A-C)(A-C)11(3) (3) 为真。由等量代入的原理可证。为真。由等量代入的原理可证。 (4) (4) 为真。当为真。当A A时，有时，有 A AA AA A 成立。成立。 解答解答7.2 7.2 7.2 7.2 二元关系二元关系二元关系二元关系( ( ( (binary relation)binary relation)binary relation)binary relation)定义定义7.37.3 如果一个集合满足以下条件之一：如果一个集合满足以下条件之一：（1 1）集合非空，且它的元素都是）集合非空，且它的元素都是有序对有序对（2 2）集合是空集）集合是空集 则称该集合为一个则称该集合为一个二元关系二元关系，记作，记作R R。二元关系也可简称为二元关系也可简称为关关系系。对于二元关系。对于二元关系R R，如果如果 Rx,yR，可记作可记作xRyxRy；如果如果 x,y R R，则记作则记作xRxRy y。设设R R1 1,，R R2 2,a,b,a,b。则则R R1 1是二元关系，是二元关系，R R2 2不是二元关系，只是一个集合，不是二元关系，只是一个集合，除非将除非将a a和和b b定义为有序对。定义为有序对。根据上面的记法可以写根据上面的记法可以写1 1R R1 12 2，aRaR1 1b b，aRaR1 1c c等。等。 举例举例R R,是否为二元关系？是否为二元关系？集合集合A A上的二元关系的数目依赖于上的二元关系的数目依赖于A A中的元素数。中的元素数。如果如果| |A|=nA|=n，那么那么| |A AA|=nA|=n2 2， A AA A的子集就有的子集就有 个。个。每一个子集代表一个每一个子集代表一个A A上的二元关系，所以上的二元关系，所以A A上有上有 个不个不同的二元关系。同的二元关系。例如例如| |A|=3A|=3，则则A A上有上有 个不同的二元关系。个不同的二元关系。7.2 7.2 7.2 7.2 二元关系二元关系二元关系二元关系定义定义7.4 7.4 设设A A，B B为集合，为集合，A AB B的任何子集所定义的二元关系叫做的任何子集所定义的二元关系叫做从从A A到到B B的二元关系的二元关系；特别当；特别当A=BA=B时，则叫做时，则叫做A A上的二元关系上的二元关系。 A=0,1A=0,1，B=1,2,3B=1,2,3，那么那么 R R1 1=，R R2 2=A=AB B，R R3 3= = ，R R4 4=等都是从等都是从A A到到B B的二元关系，而的二元关系，而R R3 3和和R R4 4同时也是同时也是A A上的二上的二元关系。元关系。 举例举例说明说明常用的关系常用的关系常用的关系常用的关系定义定义7.57.5 对任意集合对任意集合A A，定义定义全域关系全域关系 E EA A=|xAyA=AA =|xAyA=AA 恒等关系恒等关系 I IA A=|xA=|xA空关系空关系 设设 A=1,2A=1,2，那么那么E EA A=,=,I IA A=,=, 举例举例其它常用的关系其它常用的关系其它常用的关系其它常用的关系q小于或等于关系小于或等于关系：L LA A=|x,yAxy=|x,yAxy，其中其中 A A R R。q整除关系整除关系：D DB B=|x,yBx=|x,yBx整除整除yy，其中其中 A A Z Z* * Z Z* *是非零整数集是非零整数集q包含关系包含关系：R R |x,yAx|x,yAx yy，其中其中 A A是集合族。是集合族。 (1)(1)设设 A=1,2,3A=1,2,3，B Ba,ba,b则则 L LA A=,=, D DA A=,=, (2)(2)令令A=P(B)=A=P(B)=,a,b,a,b,a,b,a,b，则则A A上的包含关系是上的包含关系是 R R ,a,b, , , , , 举例举例例例例例7.47.47.47.4例例7.47.4 设设A=1,2,3,4A=1,2,3,4，下面各式定义的下面各式定义的R R都是都是A A上的关系，试上的关系，试用列元素法表示用列元素法表示R R。(1) (1) R= | xR= | x是是y y的倍数的倍数 (2) (2) R= | (x-y)R= | (x-y)2 2AA(3) (3) R= | x/yR= | x/y是素数是素数 (4) (4) R= | xy R= | xy 解答解答(1)(1)R=, R=, (2)(2)R=,R=,(3)(3)R=,R=,(4)R=E(4)R=EA A-I-IA A=,=, , , 关系的表示方法关系的表示方法关系的表示方法关系的表示方法q关系的三种表示方法：关系的三种表示方法：集合表达式集合表达式关系矩阵关系矩阵关系图关系图q关系矩阵和关系图可以表示有穷集上的关系。关系矩阵和关系图可以表示有穷集上的关系。关系矩阵和关系图的定义关系矩阵和关系图的定义关系矩阵和关系图的定义关系矩阵和关系图的定义设设A=xA=x1 1,x,x2 2, , ,x xn n,R,R是是A A上的关系。令上的关系。令 则则 是是R R的的关系矩阵关系矩阵，记作，记作M MR R。 设设A=xA=x1 1,x,x2 2, , ,x xn n,R,R是是A A上的关系。令图上的关系。令图G=G=，其中顶点其中顶点集合集合V=AV=A，边集为边集为E E。对于对于 x xi i, ,x xj jVV，满足满足 E E x xi iRxRxj j称图称图G G为为R R的的关系图关系图，记作，记作 G GR R。关系矩阵和关系图的实例关系矩阵和关系图的实例关系矩阵和关系图的实例关系矩阵和关系图的实例设设 A=1,2,3,4A=1,2,3,4，R=,R=,，则则R R的关系矩阵和的关系矩阵和关系关系图分别是图分别是 7.3 7.3 7.3 7.3 关系的运算关系的运算关系的运算关系的运算定义定义7.67.6 设设R R是二元关系。是二元关系。(1)(1)R R中所有中所有有序对有序对的第一元素构成的集合称为的第一元素构成的集合称为R R的的定义域定义域( (domaindomain) )，记为记为domdom R R。形式化表示为：形式化表示为：domdom R R x | x | y(Ry(R )(2)(2)R R中所有有序对的第二元素构成的集合称为中所有有序对的第二元素构成的集合称为R R的的值域值域( (rangerange) ) ，记作，记作ran Rran R。形式化表示为形式化表示为ran Rran Ry | y | x(x(R)R)(3)(3)R R的定义域和值域的并集称为的定义域和值域的并集称为R R的的域域( (fieldfield) )，记作，记作fldfld R R。形式化表示为形式化表示为fld fld R Rdomdom R R ran Rran R 例例7.57.5 求求R=,R=,的定义域、值域和域。的定义域、值域和域。 解答解答domdom R R1,2,4 ran R1,2,4 ran R2,3,4 2,3,4 fldfld R R1,2,3,4 1,2,3,4 关系的逆和右复合运算关系的逆和右复合运算关系的逆和右复合运算关系的逆和右复合运算定义定义7.77.7 设设R R为二元关系，为二元关系，R R的逆关系，简称的逆关系，简称R R的的逆逆( (inverse) )，记作记作R R-1-1, ,其中其中R R-1-1|R|R定义定义7.87.8 设设F,GF,G为二元关系，为二元关系，G G对对F F的的右复合右复合( (composite) )记作记作F F G G，其中其中F F G G | | t t(x,(FFG),yG)例例7.67.6 设设F F,G=,G=，则则F F-1 -1 ,F F G GG G F F说明说明q可以把二元关系看作一种作用，可以把二元关系看作一种作用， x,yRR可以解释为可以解释为x x通过通过R R的作用变到的作用变到y y。qF F G G表示两个作用的连续发生。表示两个作用的连续发生。关系的限制和像关系的限制和像关系的限制和像关系的限制和像定义定义7.97.9 设设R R为二元关系，为二元关系，A A是集合是集合(1) (1) R R在在A A上的上的限制限制( (restriction) )记作记作R RA A，其中其中R RA=|A=|xRyxRyxA xA (2) A(2) A在在R R下的下的像像( (image) )记作记作RARA，其中其中RA=ran(RRA=ran(RA) A) 说明说明qR R在在A A上的限制上的限制R RA A是是R R的子关系。的子关系。qA A在在R R下的像下的像RARA是是ran Rran R的子集。的子集。例例例例7.77.77.77.7设设R R，R R11，R R R R2,32,3 ，RR112,32,3RR RR3322关系与集合的说明关系与集合的说明关系与集合的说明关系与集合的说明q关系是集合，集合运算对于关系也是适用的。关系是集合，集合运算对于关系也是适用的。 q规定：规定：关系运算中逆运算优先于其它运算关系运算中逆运算优先于其它运算所有的关系运算都优先于集合运算，所有的关系运算都优先于集合运算，优先权的运算以括号决定运算顺序。优先权的运算以括号决定运算顺序。 q例如：例如：ran Fran F-1-1F F GFGF H Hran (Fran (FA)A)例题例题例题例题q设设A A表示是学校的所有学生的集合，表示是学校的所有学生的集合，B B表示学校的所有课程的集表示学校的所有课程的集合，并设合，并设R R1 1由所有有序对由所有有序对 a,b组成，其中组成，其中a a是选修课程是选修课程b b的学生。的学生。R R2 2由所有的有序对由所有的有序对 a,b构成，其中课程构成，其中课程b b是是a a的必修课。则关系的必修课。则关系R R1 1RR2 2、R R1 1RR2 2、R R1 1RR2 2、R R1 1R R2 2、R R2 2R R1 1的含义为的含义为qR R1 1RR2 2：a a是一个学生，他或者选修了课程是一个学生，他或者选修了课程b b，或者课程或者课程b b是他的是他的必修课。必修课。qR R1 1RR2 2：a a是一个学生，他选修了课程是一个学生，他选修了课程b b并且课程并且课程b b也是也是a a的必修课。的必修课。 qR R1 1RR2 2：学生学生a a已经选修了课程已经选修了课程b b，但课程但课程b b不是不是a a的选修课，或者的选修课，或者课程课程b b是是a a的必修课，但是的必修课，但是a a没有选修它。没有选修它。qR R1 1R R2 2：学生学生a a已经选修了课程已经选修了课程b b，但课程但课程b b不是不是a a的选修课。的选修课。 qR R2 2R R1 1：课程课程b b是学生是学生a a的必修课，但是的必修课，但是a a没有选修它。没有选修它。 定理定理定理定理7.17.17.17.1定理定理7.17.1 设设F F是任意的关系，则是任意的关系，则 (1)(1)(F F-1-1) )-1-1F F (2)(2)domdom F F-1-1ran Fran F，ran Fran F-1-1domdom F F (1)(1)任取任取 x,y，由由逆逆的定义有的定义有 x,y(F(F-1-1) )-1-1 F F-1-1 F F (2)(2)任取任取x x x xdomdom F F-1-1 y y(x,(FF-1-1) ) y y(F) ,xF) xran F xran F 所以有所以有 domdom F F-1-1ran Fran F证明证明定理定理定理定理7.27.27.27.2定理定理7.27.2 设设F F，G G，H H是任意的关系，则是任意的关系，则(1)(1)(F F G)G) H HF F (G(G H)H)(2)(F(2)(F G)G)-1-1G G-1 -1 F F-1-1证明证明(1)(1)任取任取 x,y， x,y( (F F G)G) H H t t(x,(FF G(G(t t,y)H),y)H) t t( ( s s(x,(FFG)G)H),yH) t t s s(x,(FFGGH),yH) s s(x,(FF t t(GGH) ,yH) s s(x,(FFG,yG H) H) x,yF F ( (G G H)H)定理定理定理定理7.27.27.27.2定理定理7.27.2 设设F F，G G，H H是任意的关系，则是任意的关系，则(1)(1)(F F G)G) H HF F (G(G H)H)(2)(F(2)(F G)G)-1-1G G-1-1 F F-1-1证明证明(2)(2)任取任取 x,y， x,y(F(F G)G)-1-1 FF G G t t(y,(FFG),xG) t t(F,yF-1-1x,GG-1-1) ) G G-1 -1 F F-1-1定理定理定理定理7.37.37.37.3定理定理7.3 7.3 设设R R为为A A上的关系，则上的关系，则R R I IA AI IA A R RR R证明证明(1)(1)任取任取 x,y， x,y R R I IA A t(x,t(R(R(t t,y)I,y)IA A) ) t(x,t(RRt ty)y) R R x,yR R RyARyA RI RIA A) ) R R I IA A综上所述，有综上所述，有 R R I IA AR R同理可证同理可证 I IA A R RR R定理定理定理定理7.47.47.47.4定理定理7.47.4 设设F F，G G，H H是任意的关系，则是任意的关系，则(1) (1) F F ( (G GH)H)F F GFGF H H(2) (GH)(2) (GH) F FG G F FHH F F(3) (3) F F ( (GH)GH) F F GFGF H H(4) (4) (GH)(GH) F F G G FFH H F F证明证明(3)(3) x,yF F ( (GH)GH) t t(x,(F(F(t t,y)GH),y)GH) t t(x,(F(F(t t,y)G(,y)G(t t,y)H),y)H) t t( ( (x,F(F(t t,y)G,y)G) ) ( (x,F(F(t t,y)H,y)H) ) ) t t(x,(F(F(t t,y)G) ,y)G) t t(x,(F(F(t t,y)H),y)H) F F G G F F H H x,yF F GFGF H H定理定理定理定理7.47.47.47.4的推论的推论的推论的推论q由数学归纳法不难证明定理由数学归纳法不难证明定理7.47.4的结论对于有限多个关系的的结论对于有限多个关系的并和交也是成立的，即有并和交也是成立的，即有R R (R(R1 1RR2 2R Rn n) )R R R R1 1RR R R2 2RR R Rn nR R1 1 RR2 2R Rn n) ) R RR R1 1 RRRR2 2 RRR Rn n R RR R (R(R1 1RR2 2R Rn n) ) R R R R1 1RR R R2 2RR R Rn nR R1 1RR2 2R Rn n) ) R R R R1 1 RRRR2 2 RRR Rn n R R 定理定理定理定理7.57.57.57.5定理定理7.57.5 设设F F为为关系，关系，A,BA,B为集合，则为集合，则(1) (1) F(AB)F(AB)FAFBFAFB (2) FAB(2) FABFAFB FAFB (3) (3) F(AB)F(AB)FAFB FAFB (4) (4) FABFAB FAFBFAFB 定理定理定理定理7.5 (1)7.5 (1)7.5 (1)7.5 (1)的证明的证明的证明的证明(1) (1) F(AB)F(AB)FAFB FAFB 证明证明任取任取 x,y， F F(AB) (AB) F x(AB) F x(AB) F (xAxB) F (xAxB) (FxA) (FxB) (FxA) (FxB) F FA FA FB B F FAFAFB B 所以有所以有 F(AB)F(AB)FAFBFAFB。 定理定理定理定理7.5 (4)7.5 (4)7.5 (4)7.5 (4)的证明的证明的证明的证明(4) (4) FABFAB FAFB FAFB 证明证明任取任取y y， yFAB yFAB x x(F,yFx xAB)AB) x x(F,yFx xAAx xB) B) x x(F,yFx xA)(A)(F,yFx xB) B) x x(F,yFx xA) A) x x(F,yFx xB) B) yFA yFB yFA yFB yFAFByFAFB所以有所以有 FABFAB FAFB FAFB 关系的幂运算关系的幂运算关系的幂运算关系的幂运算定义定义7.107.10 设设R R为为A A上的关系，上的关系，n n为自然数，则为自然数，则R R的的n n次幂次幂定义为：定义为：（1 1） R R0 0|xA|xAI IA A（2 2） R Rn n+1+1R Rn n R R说明说明q对于对于A A上的任何关系上的任何关系R R1 1和和R R2 2都有都有R R1 10 0R R2 20 0I IA A 即：即：A A上任何关系的上任何关系的0 0次幂都相等，都等于次幂都相等，都等于A A上的上的恒等恒等关系关系I IA A。q对于对于A A上的任何关系上的任何关系R R都有都有R R1 1R R，因为因为R R1 1R R0 0 R RI IA A R RR RR Rn n的计算的计算的计算的计算q给定给定A A上的关系上的关系R R和自然数和自然数n n，怎样计算怎样计算R Rn n呢？呢？q若若n n是是0 0或或1 1，结果是很简单的。下面考虑，结果是很简单的。下面考虑n2n2的情况。的情况。如果如果R R是用是用集合表达式集合表达式给出的，可以通过给出的，可以通过n-1n-1次右复合次右复合计算计算得到得到R Rn n。如果如果R R是用是用关系矩阵关系矩阵M M给出的，则给出的，则R Rn n的关系矩阵是的关系矩阵是M Mn n，即即n n个个矩阵矩阵M M之积之积。与普通矩阵乘法不同的是，其中的相加是逻。与普通矩阵乘法不同的是，其中的相加是逻辑加，即辑加，即1+11+11 1，1+01+00+10+11 1，0+00+00 0如果如果R R是用是用关系图关系图G G给出的，可以直接由图给出的，可以直接由图G G得到得到R Rn n的关系的关系图图GG。GG的顶点集与的顶点集与G G相同。考察相同。考察G G的每个顶点的每个顶点x xi i，如果如果在在G G中从中从x xi i出发经过出发经过n n步长的路径到达顶点步长的路径到达顶点x xj j，则在则在GG中加一中加一条从条从x xi i到到x xj j的边的边。当把所有这样的便都找到以后，就得到。当把所有这样的便都找到以后，就得到图图GG。 例例例例7.87.87.87.8例例7.87.8 设设A Aa,b,c,da,b,c,d，R R,，求求R R的各次幂，分别用矩阵和关系图表示。的各次幂，分别用矩阵和关系图表示。 解答解答例例例例7.87.87.87.8因此因此M M4 4M M2 2，即即R R4 4R R2 2。因此可以得到因此可以得到R R2 2R R4 4R R6 6R R3 3R R5 5R R7 7 用用关系图关系图的方法得到的方法得到R R0 0, R, R1 1, R, R2 2, R, R3 3,的关系图如下图所示。的关系图如下图所示。幂运算的性质幂运算的性质幂运算的性质幂运算的性质定理定理7.67.6 设设A A为为n n元集，元集，R R是是A A上的关系，则存在自然数上的关系，则存在自然数s s和和t,t,使使得得R Rs s= =R Rt t。R R为为A A上的关系，对任何自然数上的关系，对任何自然数k k，R Rk k都是都是A AA A的子集。的子集。证明证明又知又知| |A AA|=nA|=n2 2，|P(A|P(AA)|= A)|= ，即即A AA A的不同子集仅的不同子集仅 个。个。当列出当列出R R的各次幂的各次幂R R0 0，R R1 1，R R2 2， ，时时，必存在自然数必存在自然数s s和和t t使得使得R Rs s= =R Rt t。说明说明q该定理说明有穷集上只有有穷多个不同的二元关系。该定理说明有穷集上只有有穷多个不同的二元关系。当当t t足够大时，足够大时，R Rt t必与某个必与某个R Rs s(st)(st)相等。相等。q如如例例7.87.8中的中的R R4 4=R=R2 2。 定理定理定理定理7.77.77.77.7定理定理7.77.7 设设R R是是A A上的关系，上的关系，m,nNm,nN，则则(1)(1)R Rm m R Rn nR Rm m+n+n(2)(2)(R Rm m) )n nR Rmnmn证明证明(1)(1)对于任意给定的对于任意给定的mN,mN,施归纳于施归纳于n n。若若n=0n=0，则有则有所以对一切所以对一切m,nNm,nN有有 R Rm m R Rn nR Rm m+n+n。R Rm m R R0 0 R Rm m I IA A R Rm m R Rm m+0+0假设假设R Rm m R Rn n= =R Rm m+n+n，则有则有R Rm m R Rn n+1+1 R Rm m ( (R Rn n R)R)( (R Rm m R Rn n) ) R R R Rm m+n+1+n+1，定理定理定理定理7.77.77.77.7定理定理7.77.7 设设R R是是A A上的关系，上的关系，m,nNm,nN，则则(1)(1)R Rm m R Rn nR Rm m+n+n(2)(2)(R Rm m) )n nR Rmnmn证明证明(2)(2)对于任意给定的对于任意给定的mN,mN,施归纳于施归纳于n n。若若n=0n=0，则有则有所以对一切所以对一切m,nN m,nN 有有( (R Rm m) )n n= =R Rmnmn。( (R Rm m) )0 0 I IA A R R0 0 R Rm m0 0假设假设( (R Rm m) )n nR Rmnmn，则有则有( (R Rm m) )n+1n+1 ( (R Rm m) )n n R Rm m R Rmnmn+m+m R Rm m(n+1)(n+1)定理定理定理定理7.87.87.87.8定理定理7.8 7.8 设设R R是是A A上的关系，若存在自然数上的关系，若存在自然数s,t(st)s,t(st)使得使得R Rs s= =R Rt t，则则(1) (1) 对任何对任何kNkN有有 R Rs s+k+k= =R Rt t+k+k(2) (2) 对任何对任何k,iNk,iN有有 R Rs s+ +kpkp+i+i= =R Rs s+i+i，其中其中p=t-sp=t-s(3) (3) 令令S=RS=R0 0，R R1 1，R Rt t-1-1 ，则对于任意的则对于任意的qNqN有有 R Rq qSS证明证明(1) (1) R Rs s+k+kR Rs s R Rk kR Rt t R Rk kR Rt t+k+k(2)(2)对对k k归纳。归纳。若若k=0k=0，则有则有 R Rs s+0 p+i+0 p+iR Rs s+i+i假设假设 R Rs s+ +kpkp+i+iR Rs s+i+i，其中其中p pt-st-s，则则R Rs s+(k+1)p+i+(k+1)p+i R Rs s+ +kpkp+i+p+i+pR Rs s+i +i R Rp p= =R Rs s+p+i+p+iR Rs s+t-s+i+t-s+i R Rt t+i+i R Rs s+i+i由归纳法命题得证。由归纳法命题得证。R Rs s+ +kpkp+i +i R Rp p定理定理定理定理7.87.87.87.8定理定理7.8 7.8 设设R R是是A A上的关系，若存在自然数上的关系，若存在自然数s,t(st)s,t(st)使得使得R Rs s= =R Rt t，则则(1) (1) 对任何对任何kNkN有有 R Rs s+k+k= =R Rt t+k+k(2) (2) 对任何对任何k,iNk,iN有有 R Rs s+ +kpkp+i+i= =R Rs s+i+i，其中其中p=t-sp=t-s(3) (3) 令令S=RS=R0 0，R R1 1，R Rt t-1-1 ，则对于任意的则对于任意的qNqN有有 R Rq qSS证明证明(3)(3)任取任取qNqN，若若qtqt，显然有显然有R Rq qSS，若若qtqt，则存在自然数则存在自然数k k和和i i使得使得q qs+s+kpkp+i+i其中其中00ip-1,pip-1,pt-st-s。于是于是R Rq qR Rs s+ +kpkp+i+iR Rs s+i+i而而s+is+p-1s+is+p-1 s+t-s-1s+t-s-1 t-1t-1这就证明了这就证明了 R Rq qSS。定理定理定理定理7.87.87.87.8的说明的说明的说明的说明q有穷集有穷集A A上的关系上的关系R R的的幂幂序列序列R R0 0，R R1 1，是一个周期性变化的序列。是一个周期性变化的序列。就象正弦函数一样，利用它的周期性可以将就象正弦函数一样，利用它的周期性可以将R R的高次幂化简为的高次幂化简为R R的低次幂。的低次幂。例例7.97.9 设设A=a,b,d,e,fA=a,b,d,e,f，R=,R=,。求出最小的自然数求出最小的自然数m m和和n n，使得使得mnmn且且R Rm m= =R Rn n。 解答解答由由R R的定义可以看出的定义可以看出A A中的元素可分成两组，即中的元素可分成两组，即 a,ba,b和和 d,e,fd,e,f。它们在它们在R R的右复合运算下有下述变化规律：的右复合运算下有下述变化规律：ababababdefdefdefdef对于对于a a或或b,b,每个元素的变化周期是每个元素的变化周期是2 2。对于。对于d d，e e，f f，每个元每个元素的变化周期是素的变化周期是3 3。因此必有。因此必有R Rm m= =R Rm m+6+6，其中其中6 6是是2 2和和3 3的最小公的最小公倍数。取倍数。取m=0,n=6m=0,n=6即满足题目要求。即满足题目要求。7.4 7.4 7.4 7.4 关系的性质关系的性质关系的性质关系的性质q自反性自反性q反自反性反自反性q对称性对称性q反对称性反对称性q传递性传递性自反性和反自反性自反性和反自反性自反性和反自反性自反性和反自反性定义定义7.117.11 设设R R为为A A上的关系，上的关系，( (1)1)若若 x x(xA(xAR)R)，则称则称R R在在A A上是上是自反自反( (reflexivity) )的。的。( (2)2)若若 x(xAx(xA R)R)，则称则称R R在在A A上是上是反自反反自反( (irreflexivity) )的。的。例如例如 全域关系全域关系E EA A，恒等关系恒等关系I IA A，小于等于关系小于等于关系L LA A，整除关系整除关系D DA A都是为都是为A A上的上的自反关系自反关系。包含关系包含关系R R是给定集合族是给定集合族A A上的上的自反关系自反关系。小于关系小于关系和和真包含关系真包含关系都是给定集合或集合族上的都是给定集合或集合族上的反自反反自反关系关系。例例例例7.107.107.107.10例例7.107.10 设设A=1,2,3A=1,2,3，R R1 1，R R2 2，R R3 3是是A A上的关系，其中上的关系，其中R R1 1,R R2 2,R R3 3说明说明R R1 1，R R2 2和和R R3 3是否为是否为A A上的自反关系和反自反关系。上的自反关系和反自反关系。解答解答 R R1 1既不是自反的也不是反自反的，既不是自反的也不是反自反的，R R2 2是自反的，是自反的，R R3 3是反自反的。是反自反的。对称性和反对称性对称性和反对称性对称性和反对称性对称性和反对称性定义定义7.127.12 设设R R为为A A上的关系，上的关系，（1 1）若）若 x x y(x,yARR)y(x,yARR)，则称则称R R为为A A上上对对称称( (symmetry) )的关系。的关系。（2 2）若）若 x x y(x,yARRx=y)y(x,yARRx=y)，则称则称R R为为A A上的上的反对称反对称( (antisymmetry) )关系。关系。 例如例如 A A上的上的全域关系全域关系E EA A，恒等关系恒等关系I IA A和和空关系空关系都是都是A A上的上的对称关对称关系系。恒等关系恒等关系I IA A和和空关系空关系也是也是A A上的上的反对称反对称关系。关系。但全域关系但全域关系E EA A一般不是一般不是A A上的反对称关系，除非上的反对称关系，除非A A为单元集为单元集或空集。或空集。例例例例7.117.117.117.11例例7.117.11 设设A A1,2,31,2,3，R R1 1，R R2 2，R R3 3和和R R4 4都是都是A A上的关系，其中上的关系，其中R R1 1,R R2 2,R R3 3,R R4 4,说明说明R R1 1，R R2 2，R R3 3和和R R4 4是否为是否为A A上对称和反对称的关系。上对称和反对称的关系。解答解答 R R1 1既是对称也是反对称的。既是对称也是反对称的。R R2 2是对称的但不是反对称的。是对称的但不是反对称的。R R3 3是反对称的但不是对称的。是反对称的但不是对称的。R R4 4既不是对称的也不是反对称的。既不是对称的也不是反对称的。传递性传递性传递性传递性定义定义7.137.13 设设R R为为A A上的关系，若上的关系，若 x x y y z(x,y,zARRR)z(x,y,zARRR)则称则称R R是是A A上的上的传递传递( (transitivity) )关系。关系。例如例如 A A上的上的全域关系全域关系E EA A, ,恒等关系恒等关系I IA A和和空关系空关系都是都是A A上的上的传递关系传递关系。小于等于关系小于等于关系，整除关系整除关系和和包含关系包含关系也是相应集合上的也是相应集合上的传递传递关系关系。小于关系小于关系和和真包含关系真包含关系仍旧是相应集合上的传递关系。仍旧是相应集合上的传递关系。 例例例例7.127.127.127.12例例7.127.12 设设A A1,2,31,2,3，R R1 1，R R2 2，R R3 3是是A A上的关系，其中上的关系，其中R R1 1,R R2 2,R R3 3说明说明R R1 1，R R2 2和和R R3 3是否为是否为A A上的传递关系。上的传递关系。解答解答 R R1 1和和R R3 3是是A A上的传递关系，上的传递关系，R R2 2不是不是A A上的传递关系。上的传递关系。 关系性质的等价描述关系性质的等价描述关系性质的等价描述关系性质的等价描述 定理定理7.97.9 设设R R为为A A上的关系，则上的关系，则（1 1）R R在在A A上自反当且仅当上自反当且仅当 I IA A R R（2 2）R R在在A A上反自反当且仅当上反自反当且仅当 RIRIA A（3 3）R R在在A A上上对称对称当且仅当当且仅当 R RR R-1-1（4 4）R R在在A A上上反对称反对称当且仅当当且仅当 RRRR-1 -1 I IA A（5 5）R R在在A A上上传递传递当且仅当当且仅当 R R R R R R 说明说明q利用该定理可以从关系的集合表达式来判断或证明关利用该定理可以从关系的集合表达式来判断或证明关系的性质。系的性质。分析分析关系性质的证明方法关系性质的证明方法定理定理定理定理7.9 (1)7.9 (1)7.9 (1)7.9 (1)的证明的证明的证明的证明（1 1） R R在在A A上自反当且仅当上自反当且仅当 I IA A R R必要性必要性。 任取任取 x,y，有有 Ix,yIA A x,yA xx,yA xy y RR 所以所以 I IA A R R充分性充分性。 任取任取x x，有有 x xAA IIA A RR 所以所以 R R在在A A上是自反的。上是自反的。定理定理定理定理7.9 (2)7.9 (2)7.9 (2)7.9 (2)的证明的证明的证明的证明（2 2）R R在在A A上反自反当且仅当上反自反当且仅当 RIRIA A充分性。充分性。 任取任取x x，有有 xA xA I IA A R (RIR (RIA A= = ) ) 所以所以 R R在在A A上是反自反的。上是反自反的。必要性。用反证法。必要性。用反证法。 假设假设RIRIA A， 必存在必存在 RIx,yRIA A。 由于由于I IA A是是A A上恒等关系，上恒等关系， 可知可知 xAxA且且 Rx,xR。 这与这与R R在在A A上是反自反的相矛盾。上是反自反的相矛盾。定理定理定理定理7.9 (3)7.9 (3)7.9 (3)7.9 (3)的证明的证明的证明的证明（3 3） R R在在A A上上对称对称当且仅当当且仅当 R RR R-1-1必要性。必要性。任取任取 x,y，有有 R x,yR R R( (因为因为R R在在A A上对称上对称) ) Rx,yR-1-1 所以所以 R RR R-1-1充分性。充分性。 任取任取 x,y， 由由 R RR R-1 -1 得得 Rx,yR RR-1-1 RR 所以所以 R R在在A A上是对称的。上是对称的。定理定理定理定理7.9 (4)7.9 (4)7.9 (4)7.9 (4)的证明的证明的证明的证明（4 4） R R在在A A上上反对称反对称当且仅当当且仅当 RRRR-1 -1 I IA A必要性。必要性。 任取任取 x,y，有有 RRx,yRR-1-1 R R R R-1-1 R RR R x xy y (R(R是反对称的是反对称的) ) Ix,yIA A所以所以 RRRR-1 -1 I IA A充分性。充分性。任取任取 ,x,y, 则有则有 R Rx,yR R R R R R-1-1 RR RR-1-1 I IA A (RR(RR-1 -1 I IA A) ) x xy y所以所以 R R在在A A上是反对称的。上是反对称的。定理定理定理定理7.9 (5)7.9 (5)7.9 (5)7.9 (5)的证明的证明的证明的证明（5 5） R R在在A A上上传递传递当且仅当当且仅当 R R R R R R必要性必要性。任取任取 x,y，有有 Rx,yR R R t t(x,(RRR),yR) R R( (因为因为R R在在A A上是传递的上是传递的) )所以所以 R R R R R R。充分性充分性。任取。任取 ,Rx,y,R，则则 RRx,yRR RR R R R R ( (因为因为R R R R R R) )所以所以 R R在在A A上是传递的。上是传递的。例例例例7.137.137.137.13例例7.137.13 设设A A是集合，是集合，R R1 1和和R R2 2是是A A上的关系，证明：上的关系，证明：( (1)1)若若R R1 1，R R2 2是是自反自反的和的和对称对称的，则的，则R R1 1RR2 2也是自反的和对称的。也是自反的和对称的。( (2)2)若若R R1 1和和R R2 2是是传递传递的，则的，则R R1 1RR2 2也是传递的。也是传递的。例例例例7.13 (1)7.13 (1)7.13 (1)7.13 (1)的证明的证明的证明的证明( (1)1)若若R R1 1，R R2 2是是自反自反的和的和对称对称的，则的，则R R1 1RR2 2也是自反的和对称的。也是自反的和对称的。证明证明由于由于R R1 1和和R R2 2是是A A上的自反关系，故有上的自反关系，故有I IA A R R1 1 和和 I IA A R R2 2从而得到从而得到 I IA A R R1 1RR2 2。根据根据定理定理7.97.9可知可知 R R1 1RR2 2在在A A上是自反的。上是自反的。再由再由R R1 1和和R R2 2的对称性有的对称性有R R1 1R R1 1-1 -1 和和 R R2 2R R2 2-1-1根据练习七第根据练习七第1818题的结果有题的结果有( (R R1 1RR2 2) )-1-1R R1 1-1-1RR2 2-1-1R R1 1RR2 2从而证明了从而证明了R R1 1RR2 2也是也是A A上对称的关系。上对称的关系。例例例例7.13 (2)7.13 (2)7.13 (2)7.13 (2)的证明的证明的证明的证明( (2)2)若若R R1 1和和R R2 2是是传递传递的，则的，则R R1 1RR2 2也是传递的。也是传递的。证明证明由由R R1 1和和R R2 2的传递性有的传递性有R R1 1 R R1 1 R R1 1 和和 R R2 2 R R2 2 R R2 2再使用定理再使用定理7.47.4得得 ( (R R1 1RR2 2) ) (R(R1 1RR2 2) ) R R1 1 R R1 1RR1 1 R R2 2RR2 2 R R1 1RR2 2 R R2 2 (R(R1 1RR2 2)R)R1 1 R R2 2RR2 2 R R1 1 ( (将前面的包含式代入将前面的包含式代入) ) R R1 1RR2 2从而证明了从而证明了R R1 1RR2 2也是也是A A上的传递关系。上的传递关系。 关系性质的特点关系性质的特点关系性质的特点关系性质的特点自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性集合表达式集合表达式I IA A R RRIRIA AR RR R-1-1RRRR-1 -1 I IA AR R R R R R关系矩阵关系矩阵主对角线主对角线元素全是元素全是1 1主对角线主对角线元素全是元素全是0 0 矩阵是对矩阵是对称矩阵称矩阵 若若r rijij1 1，且且ijij，则则r rjiji0 0 对对M M2 2中中1 1所所在位置，在位置，M M中相应的位中相应的位置都是置都是1 1 关系图关系图每个顶点每个顶点都有环都有环每个顶点每个顶点都没有环都没有环 如果两个如果两个顶点之间顶点之间有边，一有边，一定是一对定是一对方向相反方向相反的边的边( (无单无单边边) ) 如果两点之如果两点之间有边，一间有边，一定是一条有定是一条有向边向边( (无双无双向边向边) ) 如果顶点如果顶点x xi i到到x xj j有边，有边，x xj j到到x xk k有边，有边，则从则从x xi i到到x xk k也有边也有边 例例例例7.147.147.147.14例例7.147.14 判断下图中关系的性质，并说明理由。判断下图中关系的性质，并说明理由。 （1 1）对称的，不是自反的，不是反自反的，不是反对称的，）对称的，不是自反的，不是反自反的，不是反对称的，不是传递的。不是传递的。（2 2）是反自反的，不是自反的，是反对称的，不是对称的，）是反自反的，不是自反的，是反对称的，不是对称的，是传递的是传递的。（3 3）是自反的，不是反自反的，是反对称的，不是对称的，是自反的，不是反自反的，是反对称的，不是对称的，不是传递的。不是传递的。关系的性质和运算之间的关系关系的性质和运算之间的关系关系的性质和运算之间的关系关系的性质和运算之间的关系自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性R R1 1-1-1R R1 1RR2 2R R1 1RR2 2R R1 1R R2 2R R1 1 R R2 2问题问题问题问题q如果存在一条从数据中心如果存在一条从数据中心a a到到b b的电话线，的电话线， a,b就属于关系就属于关系R R。q如何确定从一个中心是否有一条电话线如何确定从一个中心是否有一条电话线( (可能不直接可能不直接) )链接到另链接到另一个中心？一个中心？q通过构造通过构造包含包含R R的的最小最小的的传递关系传递关系来找出每一对有着联系的数据来找出每一对有着联系的数据中心，这个关系叫做中心，这个关系叫做R R的的传递闭包传递闭包。波士顿波士顿芝加哥芝加哥丹佛丹佛底特律底特律圣地亚哥圣地亚哥纽约纽约7.5 7.5 7.5 7.5 关系的闭包关系的闭包关系的闭包关系的闭包q闭包（闭包（closure）的定义的定义q闭包的构造方法闭包的构造方法q闭包的性质闭包的性质q闭包的相互关系闭包的相互关系闭包的定义闭包的定义闭包的定义闭包的定义定义定义7.147.14 设设R R是非空集合是非空集合A A上的关系，上的关系，R R的的自反自反（对称对称或或传递传递）闭包闭包是是A A上的关系上的关系R R，使得使得 R R满足以下条件：满足以下条件：（1 1）R R是是自反自反的（的（对称对称的或的或传递传递的）的）（2 2）R R R R（3 3）对对A A上任何包含上任何包含R R的的自反自反（对称对称或或传递传递）关系）关系R R有有R R R R。一般将一般将R R的的自反闭包自反闭包记作记作r(R)r(R)，对称闭包对称闭包记作记作s(R)s(R)，传递闭包传递闭包记作记作t(R)t(R)。闭包的构造方法闭包的构造方法闭包的构造方法闭包的构造方法定理定理7.107.10 设设R R为为A A上的关系，则有上的关系，则有（1 1）r(R)r(R)RRR R0 0（2 2）s(R)s(R)RRR R-1-1（3 3）t(R)t(R)RRR R2 2RR3 3 证明思路证明思路(1)(1)和和(2)(2)：证明右边的集合满足闭包定义的三个条件。：证明右边的集合满足闭包定义的三个条件。(3)(3) 采用集合相等的证明方法。采用集合相等的证明方法。证明左边包含右边，即证明左边包含右边，即t(R)t(R)包含每个包含每个R Rn n。证明右边包含左边，即证明右边包含左边，即RRR R2 2具有传递的性质。具有传递的性质。 定理定理定理定理7.10 (1)7.10 (1)7.10 (1)7.10 (1)的证明的证明的证明的证明（1 1）r(R)r(R)RRRR0 0证明证明由由I IA AR R0 0 RRRR0 0，可知可知RRRR0 0是自反的，是自反的，R R RRRR0 0。设设R R是是A A上包含上包含R R的自反关系，的自反关系， 则有则有R R R R和和I IA A R R。 任取任取 x,y，必有必有 x,yRRRR0 0 RIRIA A RRRRR R 所以所以 RRRR0 0 R R。综上所述，综上所述，r(R)r(R)RRRR0 0。定理定理定理定理7.10 (2)7.10 (2)7.10 (2)7.10 (2)的证明的证明的证明的证明（2 2）s(R)s(R)RRRR-1-1证明证明 R R RRRR-1-1。证明证明RRRR-1-1是对称的，是对称的， 任取任取 x,y，有有 x,yRRRR-1-1 RRRR-1-1 RR-1-1RR y,xRRRR-1-1 所以所以 RRRR-1-1 是对称的是对称的。综上所述，综上所述，s(R)s(R)RRRR-1-1。设设R R是包含是包含R R的的对称关系，对称关系， 任取任取 x,y，有有 x,yRRRR-1-1 RRRR-1-1 RRRR RRRR RRRR Rx,yR 所以所以 RRRR-1 -1 R R。定理定理定理定理7.10 (3)7.10 (3)7.10 (3)7.10 (3)的证明的证明的证明的证明（3 3）t(R)t(R)RRRR2 2RR3 3 证明证明先证先证RR2RR2 t(R) t(R)成立，为此只需证明对任意的正成立，为此只需证明对任意的正整数整数n n有有 R Rn n t(R)t(R)即可。用归纳法。即可。用归纳法。n n1 1时，有时，有 R R1 1R R t(R) t(R)。假设假设R Rn n t(R)t(R)成立，那么对任意的成立，那么对任意的 x,y有有 x,yR Rn n+1+1R Rn n R R t t(x,(R Rn nR),yR) t t(x,(t(R)t(R),yt t(R)(R) t(R) t(R) （因为因为t(R)t(R)是传递的）是传递的）这就证明了这就证明了R Rn n+1 +1 t(R)t(R)。由归纳法命题得证。由归纳法命题得证。定理定理定理定理7.10 (3)7.10 (3)7.10 (3)7.10 (3)的证明的证明的证明的证明（3 3）t(R)t(R)RRRR2 2RR3 3 证明证明再证再证t(R)t(R) RRRR2 2成立，为此只须证明成立，为此只须证明RRRR2 2是传是传递的。递的。任取任取 ,x,y,，则则 RRx,yRR2 2 RR RR2 2 t t(R Rt t) ) s s(R Rs s) ) t t s s(R Rt t R Rs s) ) t t s s(R Rt t R Rs s) ) t t s s(R Rt t+ +s s) ) RR RR2 2从而证明了从而证明了RRRR2 2是传递的。是传递的。推论推论推论推论推论推论 设设R R为有穷集为有穷集A A上的关系，则存在正整数上的关系，则存在正整数r r使得使得t(R)=RRt(R)=RR2 2R Rr r证明证明 由定理由定理7.67.6和和7.10(3)7.10(3)得证。得证。 例题例题 求整数集合求整数集合Z Z上的关系上的关系R R | ab | ab的自反闭包和的自反闭包和对称闭包。对称闭包。解答解答 r(R)r(R)RRRR0 0|ab|a|ab|abb |ab|ab s(R)s(R)RRRR-1-1|ab|ba|ab|ba |ab|ab通过关系矩阵求闭包的方法通过关系矩阵求闭包的方法通过关系矩阵求闭包的方法通过关系矩阵求闭包的方法设关系设关系R R，r(R)r(R)，s(R)s(R)，t(R)t(R)的关系矩阵分别为的关系矩阵分别为M M，M Mr r，M Ms s和和M Mt t，则则M Mr r M ME E对角线上的值都改为对角线上的值都改为1 1M Ms s M MM M若若a aijij1 1，则令则令a ajiji1 1M Mt t M MM M2 2M M3 3沃舍尔算法沃舍尔算法其中其中E E是和是和M M同阶的单位矩阵，同阶的单位矩阵，M M是是M M的转置矩阵。的转置矩阵。注意在上述等式中矩阵的元素相加时使用逻辑加。注意在上述等式中矩阵的元素相加时使用逻辑加。通过关系图求闭包的方法通过关系图求闭包的方法通过关系图求闭包的方法通过关系图求闭包的方法设关系设关系R R，r(R)r(R)，s(R)s(R)，t(R)t(R)的关系图分别记为的关系图分别记为G G，G Gr r，G Gs s，G Gt t，则则G Gr r，G Gs s，G Gt t的顶点集与的顶点集与G G的顶点集相等。的顶点集相等。除了除了G G的边以外，以下述方法的边以外，以下述方法添加新的边添加新的边。1)1)考察考察G G的每个顶点，如果的每个顶点，如果没有环就加上一个环没有环就加上一个环。最终得到的。最终得到的是是G Gr r。2)2)考察考察G G的每一条边，的每一条边，如果有一条如果有一条x xi i到到x xj j的单向边的单向边，ijij，则在则在G G中中加一条边加一条边x xj j到到x xi i的反方向边的反方向边。最终得到。最终得到G Gs s。3)3)考察考察G G的每个顶点的每个顶点x xi i，找出从找出从x xi i出发的所有出发的所有2 2步，步，3 3步，步，n n步长的路径步长的路径（n n为为G G中的顶点数）。中的顶点数）。设路径的终点为设路径的终点为 。如果没有从如果没有从x xi i到到 ( (l=1,2,k)l=1,2,k)的边，就加上这条边。当的边，就加上这条边。当检查完所有的顶点后就得到图检查完所有的顶点后就得到图G Gt t。例例例例7.157.157.157.15例例7.157.15 设设A=a,b,c,dA=a,b,c,d，R=,R=,，则则R R和和r(R)r(R)，s(R)s(R)，t(R)t(R)的的关系图关系图如下图所示。其中如下图所示。其中r(R)r(R)，s(R)s(R)，t(R)t(R)的关系图就是使用上述方法直接从的关系图就是使用上述方法直接从R R的关系图得到的。的关系图得到的。 Warshall Warshall Warshall Warshall 算法算法算法算法输入：输入：M M（R R的关系矩阵）的关系矩阵）输出：输出：M MT T（t(R)t(R)的关系矩阵的关系矩阵）1.1.M MT TMM2.for 2.for k k 1 to n do 1 to n do3.3.for for i i 1 to n do 1 to n do4.4.for for j j 1 to n do 1 to n do5. 5. M MT T i i, ,j jMMT T i i, ,j j+M+MT T i i, ,k k *M*MT T k k, ,j j 注意：算法中矩阵加法和乘法中的元素相加都使用逻辑加。注意：算法中矩阵加法和乘法中的元素相加都使用逻辑加。Warshall Warshall Warshall Warshall 算法算法算法算法 举例举例举例举例例例 设设A=a,b,c,dA=a,b,c,d，R=,R=,， 求求t(R)t(R)。分析分析 k k1 1 时，时，M MT T i i,jM,jMT T i i,j+M,j+MT T i i, ,1 1*M*MT T 1 1,j,j M MT T 1 1,jM,jMT T 1 1,j+M,j+MT T 1 1, ,1 1*M*MT T 1 1,j,j M MT T 2 2,jM,jMT T 2 2,j+M,j+MT T 2 2, ,1 1*M*MT T 1 1,j ,j 将第将第1 1行加到第行加到第2 2行上行上 M MT T 3 3,jM,jMT T 3 3,j+M,j+MT T 3 3, ,1 1*M*MT T 1 1,j,j M MT T 4 4,jM,jMT T 4 4,j+M,j+MT T 4 4, ,1 1*M*MT T 1 1,j,j 得到得到M M1 1。Warshall Warshall Warshall Warshall 算法算法算法算法 举例举例举例举例k k1 1时，时，第第1 1列中只有列中只有MM2 2, ,1 1 1 1，将第将第1 1行加到第行加到第2 2行上。行上。k k2 2时，时，第第2 2列中列中MM1 1, ,2 2 MM2 2, ,2 2 MM4 4, ,2 2 1 1，将第将第2 2行分别加到第行分别加到第1 1, ,2 2, ,4 4行上。行上。Warshall Warshall Warshall Warshall 算法算法算法算法 举例举例举例举例k k3 3时，时，第第3 3列中列中MM1 1, ,3 3 MM2 2, ,3 3 MM4 4, ,3 3 1 1，将第将第3 3行分别加到行分别加到第第1 1, ,2 2, ,4 4行上。行上。k k4 4时，时，第第4 4列中列中MM1 1, ,4 4 MM2 2, ,4 4 MM3 3,4,4MM4 4, ,4 4 1 1，将第将第4 4行分别加到第行分别加到第1 1, ,2 2, ,3 3, ,4 4行上。行上。闭包的主要性质闭包的主要性质闭包的主要性质闭包的主要性质定理定理7.117.11 设设R R是非空集合是非空集合A A上的关系，则上的关系，则（1 1）R R是是自反自反的当且仅当的当且仅当r(R)r(R)R R。（2 2）R R是是对称对称的当且仅当的当且仅当s(R)s(R)R R。（3 3）R R是是传递传递的当且仅当的当且仅当t(R)t(R)R R。证明证明 （1 1）充分性。）充分性。 因为因为R Rr(R)r(R)，所以所以R R是自反的。是自反的。必要性。必要性。显然有显然有R R r(R)r(R)。由于由于R R是包含是包含R R的自反关系，根据的自反关系，根据自反闭包自反闭包定义有定义有r(R)r(R) R R。从而得到从而得到r(R)=Rr(R)=R。闭包的主要性质闭包的主要性质闭包的主要性质闭包的主要性质定理定理7.127.12 设设R R1 1和和R R2 2是非空集合是非空集合A A上的关系，且上的关系，且R R1 1 R R2 2，则则（1 1）r(Rr(R1 1) ) r(Rr(R2 2) )（2 2）s(Rs(R1 1) ) s(Rs(R2 2) )（3 3）t(Rt(R1 1) ) t(Rt(R2 2) )证明：证明：(1)(1)任取任取 x,y，有有 r(Rx,yr(R1 1) ) R R1 1IIA A R R1 1 I IA A R R2 2 I IA A R R2 2IIA A r(R r(R2 2) )命题命题命题命题命题命题若若R R是对称的，则是对称的，则R Rn n也是对称的，其中也是对称的，其中n n是任何正整数。是任何正整数。证明证明用归纳法。用归纳法。n=1n=1，R R1 1R R显然是对称的。显然是对称的。假设假设R Rn n是对称的，则对任意的是对称的，则对任意的 x,y，有有 x,yR Rn n+1+1 R Rn n R R t t(x,(R Rn nR),yR) t t(,xR Rn ny,R)R) RR R Rn n RR1+n1+nR Rn n+1+1所以所以R Rn n+1+1是对称的。由归纳法命题得证。是对称的。由归纳法命题得证。关系性质与闭包运算之间的联系关系性质与闭包运算之间的联系关系性质与闭包运算之间的联系关系性质与闭包运算之间的联系定理定理7.137.13 设设R R是非空集合是非空集合A A上的关系，上的关系，（1 1）若）若R R是是自反自反的，则的，则s(R)s(R)与与t(R)t(R)也是自反的。也是自反的。（2 2）若）若R R是是对称对称的，则的，则r(R)r(R)与与t(R)t(R)也是对称的。也是对称的。（3 3）若）若R R是是传递传递的，则的，则r(R)r(R)是传递的。是传递的。证明：证明：只证（只证（2 2）。）。 定理定理定理定理7.13 (2)7.13 (2)7.13 (2)7.13 (2)的证明的证明的证明的证明（2 2）若）若R R是是对称对称的，则的，则r(R)r(R)与与t(R)t(R)也是对称的。也是对称的。证明证明r(R)r(R)是对是对称的。称的。由于由于R R是是A A上的对称关系，所以上的对称关系，所以R RR R-1-1，同时同时I IA AI IA A-1-1。r(R)r(R)-1-1(RR(RR0 0) )-1-1(RI(RIA A) )-1-1R R-1-1IIA A-1-1RIRIA Ar(R)r(R)所以，所以，r(R)r(R)是对称的。是对称的。定理定理定理定理7.13 (2)7.13 (2)7.13 (2)7.13 (2)的证明的证明的证明的证明（2 2）若）若R R是是对称对称的，则的，则r(R)r(R)与与t(R)t(R)也是对称的。也是对称的。下面证明下面证明t(R)t(R)的对称性。的对称性。任取任取 x,y t(R) t(R) n n(R Rn n) ) n n(R Rn n) ) （因为因为R Rn n是对称的）是对称的） t(R)y,xt(R)所以，所以，t(R)t(R)是是对称的。对称的。定理定理定理定理7.137.137.137.13的讨论的讨论的讨论的讨论q从这里可以看出，如果计算关系从这里可以看出，如果计算关系R R的自反、对称、传递的闭的自反、对称、传递的闭包，包，为了不失去传递性，传递闭包运算应该放在对称闭包为了不失去传递性，传递闭包运算应该放在对称闭包运算的后边运算的后边，若令，若令tsrtsr(R)(R)表示表示R R的自反、对称、传递闭包，的自反、对称、传递闭包，则则tsrtsr(R)=t(s(r(R) (R)=t(s(r(R) 自反性自反性对称性对称性传递性传递性r(R)r(R)s(R)s(R)(反例反例) )t(R)t(R)反例反例 A=1A=1，2 2，33，R=R= 是传递的是传递的s(R)=,s(R)=,显然显然s(R)s(R)不是传递的。不是传递的。7.6 7.6 7.6 7.6 等价关系与划分等价关系与划分等价关系与划分等价关系与划分定义定义7.157.15 设设R R为非空集合上的关系。如果为非空集合上的关系。如果R R是是自反的自反的、对称的对称的和和传递的传递的，则称，则称R R为为A A上的上的等价关系等价关系( (equivalent relation) )。设设R R是一个等价关系，若是一个等价关系，若 RyR，称称x x等价于等价于y y，记做记做x xy y。 举例举例 (1)(1)平面上三角形集合中，三角形的相似关系。平面上三角形集合中，三角形的相似关系。(2)(2)人群中的同性关系。人群中的同性关系。例例例例7.167.167.167.16例例7.167.16 设设A A1,2,81,2,8，如下定义如下定义A A上的关系上的关系R R：R Rx|xy|x，yAxy(mod 3)yAxy(mod 3)其中其中xy(mod 3)xy(mod 3)叫做叫做x x与与y y模模3 3相等相等，即，即x x除以除以3 3的余数与的余数与y y除以除以3 3的余数相等。不难验证的余数相等。不难验证R R为为A A上的等价关系，因为上的等价关系，因为 xAxA，有有xx(mod 3)xx(mod 3) x,yAx,yA，若若xy(mod 3)xy(mod 3)，则有则有yx(mod 3)yx(mod 3) x,y,zAx,y,zA，若若xy(mod 3)xy(mod 3)，yz(mod 3)yz(mod 3)，则有则有xz(mod 3)xz(mod 3)等价类等价类等价类等价类定义定义7.167.16 设设R R为非空集合为非空集合A A上的上的等价关系等价关系， xAxA，令令xxR R=y|yA=y|yAxRyxRy 称称 xxR R为为x x关于关于R R的的等价类等价类，简称为，简称为x x的的等价类等价类，简记为，简记为 xx或或 x x 。qx x的等价类是的等价类是A A中所有与中所有与x x等价的元素构成的集合。等价的元素构成的集合。 q例例7.167.16中的等价类是：中的等价类是：1144771,4,71,4,72255882,5,82,5,833663,6 3,6 整数集合整数集合整数集合整数集合Z Z Z Z上的模上的模上的模上的模n n n n等价关系等价关系等价关系等价关系设设x x是任意整数，是任意整数，n n为给定的正整数，则存在唯一的整数为给定的正整数，则存在唯一的整数q q和和r r，使得使得x xqnqn+r+r其中其中00rn-1rn-1，称称r r为为x x除以除以n n的余数的余数。例如例如n n3 3，那么那么8 8除以除以3 3的余数为的余数为1 1，因为，因为 -8 -8-33+1-33+1对于任意的整数对于任意的整数x x和和y y，定义定义模模n n相等关系相等关系x xy y xy(mod n) xy(mod n)不难验证它是整数集合不难验证它是整数集合Z Z上的等价关系。上的等价关系。将将Z Z中的所有整数根据它们除以中的所有整数根据它们除以n n的余数分类如下：的余数分类如下：余数为余数为0 0的数，其形式为的数，其形式为nznz，zZzZ余数为余数为1 1的数，其形式为的数，其形式为nznz+ +1 1，zZzZ 余数是余数是n-1n-1的数，其形式为的数，其形式为nznz+ +n-1n-1，zZzZ以上构成了以上构成了n n个等价类，使用等价类的符号可记为个等价类，使用等价类的符号可记为 ii nznz+i|zZ+i|zZ，i=0i=0，1 1，n-1n-1等价类的性质等价类的性质等价类的性质等价类的性质定理定理7.147.14 设设R R是非空集合是非空集合A A上的上的等价关系等价关系，则，则（1 1） xAxA，xx是是A A的非空子集。的非空子集。（2 2） x,yAx,yA，如果如果xRyxRy，则则 xxyy。（3 3） x,yAx,yA，如果如果 x,y R R，则则 xx与与 yy不交。不交。（4 4）x|xAx|xAA A。证明证明（1）由等价类的定义可知，由等价类的定义可知， xAxA有有 xx A A。又由于等价关系的又由于等价关系的自反性自反性有有xxxx，即即 xx非空。非空。 定理定理定理定理7.147.147.147.14（2 2） x,yAx,yA，如果如果xRyxRy，则则 x=yx=y。任取任取z z，则有则有 z zxx x, R R R,xR( (因为因为R R是是对称对称的的) ) R R,xR R R,yR( (因为因为R R是是传递传递的的) ) RR ( (因为因为R R是对称的是对称的) ) z zyy。所以所以 xx yy。同理可证同理可证 yy xx。因此，因此， x=yx=y。定理定理定理定理7.147.147.147.14（3 3） x,yAx,yA，如果如果 x,y R R，则则 xx与与 yy不交。不交。假设假设 xyxy ，则存在则存在 z zxyxy，从而有从而有 z zxxz zyy，即即 RRRR成立。成立。根据根据R R的对称性和传递性，必有的对称性和传递性，必有 Rx,yR，与与 x,y R R矛盾，矛盾，即假设错误，原命题成立。即假设错误，原命题成立。 定理定理定理定理7.147.147.147.14（4 4）x|xAx|xAA A。 先证先证 x|xAx|xA A A任取任取y y，yx|xAyx|xA x x( (x xAyAyx x) yA yA ( (因为因为 xx A)A)从而有从而有x|xAx|xA A A。再证再证 A A x|xAx|xA任取任取y y，yA yA yyyA yyyA yx|xA yx|xA从而有从而有A A x|xAx|xA成立。成立。综上所述得综上所述得 x|xAx|xAA A。商集商集商集商集定义定义7.177.17 设设R R为非空集合为非空集合A A上的等价关系，以上的等价关系，以R R的所有等价类的所有等价类作为元素的集合称为作为元素的集合称为A A关于关于R R的的商集商集( (quotient set) )，记做记做A/RA/R，即即A/R=xA/R=xR R|xA|xA例例7.167.16中的商集为中的商集为1,4,7,2,5,8,3,61,4,7,2,5,8,3,6整数集合整数集合Z Z上模上模n n等价关系的商集是等价关系的商集是nznz+i|zZ|i=0,1,n-1+i|zZ|i=0,1,n-1划分划分划分划分定义定义7.187.18 设设A A为非空集合，若为非空集合，若A A的子集族的子集族( P(A)P(A)，是是A A的的子集构成的集合子集构成的集合) ) 满足下面的条件：满足下面的条件：（1 1）（2 2） x x y(x,yxyxyy(x,yxyxy) )（3 3）=A=A则称则称是是A A的一个的一个划分划分( (partitions)，称，称中的元素为中的元素为A A的的划分块划分块。说明说明q设集合设集合是是A A的非空子集的集合，若这些非空子集两两的非空子集的集合，若这些非空子集两两不相交，且它们的并等于不相交，且它们的并等于A A，则称则称是集合是集合A A的划分的划分。例例例例7.177.177.177.17例例7.177.17 设设A Aa,b,c,da,b,c,d，给定给定1 1,2 2,3 3,4 4,5 5,6 6, ,如下：如下：1 1=a,b,c,d=a,b,c,d2 2=a,b,c,d=a,b,c,d3 3=a,a,b,c,d=a,a,b,c,d4 4=a,b,c=a,b,c5 5=,a,b,c,d,a,b,c,d6 6=a,a,b,c,d=a,a,b,c,d判断哪一个是判断哪一个是A A的划分的划分1 1和和2 2是是A A的划分，其它都不是的划分，其它都不是A A的划分。的划分。因为因为3 3中的子集中的子集 aa和和 a,b,c,da,b,c,d有交，有交，4 4AA，5 5中含有中含有空集，而空集，而6 6根本不是根本不是A A的子集族。的子集族。商集与划分商集与划分商集与划分商集与划分q商集就是商集就是A A的一个划分，并且不同的商集将对应于不同的划的一个划分，并且不同的商集将对应于不同的划分。分。q反之，任给反之，任给A A的一个划分的一个划分，如下定义如下定义A A上的关系上的关系R R：R=|x,yAxR=|x,yAx与与y y在在的同一划分块中的同一划分块中 则不难证明则不难证明R R为为A A上的等价关系，且该等价关系所确定的商上的等价关系，且该等价关系所确定的商集就是集就是。q由此可见，由此可见，A A上的等价关系与上的等价关系与A A的划分是一一对应的的划分是一一对应的。 例例例例7.187.187.187.18例例7.187.18 给出给出A A1,2,31,2,3上所有的等价关系上所有的等价关系这些划分与这些划分与A A上的等价关系之间的一一对应是：上的等价关系之间的一一对应是：1 1对应于全域关系对应于全域关系E EA A，5 5的对应于恒等关系的对应于恒等关系I IA A，2 2，3 3和和4 4分别对应于等价关系分别对应于等价关系R R2 2，R R3 3和和R R4 4。 其中其中 R R2 2=,I=,IA AR R3 3=,I=,IA AR R4 4=,I=,IA A例题例题例题例题例题例题 问集合问集合A Aa,b,c,da,b,c,d上有多少个不同的等价关系？上有多少个不同的等价关系？解答解答 只要求出只要求出A A上的全部划分，即为等价关系。上的全部划分，即为等价关系。划分为划分为一个块一个块的情况：的情况：1 1种，即种，即 a,b,c,da,b,c,d划分为划分为两个块两个块的情况：的情况：7 7种，即种，即a,b,c,da,b,c,d，a,c,b,da,c,b,d，a,d,b,ca,d,b,ca,b,c,da,b,c,d，b,a,c,db,a,c,d，c,a,b,dc,a,b,d，d,a,b,cd,a,b,c划分为划分为三个块三个块的情况：的情况：6 6种，即种，即a,b,c,da,b,c,d，a,c,b,da,c,b,d，a,d,b,c,a,d,b,c,a,b,c,da,b,c,d，a,c,b,da,c,b,d，a,d,b,ca,d,b,c划分为划分为四个块四个块的情况：的情况：1 1种，即种，即 a,b,c,da,b,c,d因此，共有因此，共有1515种不同的等价关系。种不同的等价关系。7.7 7.7 7.7 7.7 偏序偏序偏序偏序( ( ( (partial orderpartial order) ) ) )关系关系关系关系定义定义7.197.19 设设R R为非空集合为非空集合A A上的关系。如果上的关系。如果R R是是自反自反的、的、反对称反对称的和的和传递传递的，则称的，则称R R为为A A上的上的偏序关系偏序关系，记作，记作。设设为偏序关系，如果为偏序关系，如果 x,y，则记作则记作xyxy，读作读作“x“x小小于或等于于或等于y y”。注意注意 这里的这里的“小于或等于小于或等于”不是指数的大小，而是不是指数的大小，而是在偏序关系在偏序关系中的顺序性中的顺序性。x“x“小于或等于小于或等于”y y的含义是：依照这个序，的含义是：依照这个序，x x排排在在y y的前边或者的前边或者x x就是就是y y。根据不同偏序的定义，对序有着不同根据不同偏序的定义，对序有着不同的解释。的解释。偏序关系举例偏序关系举例集合集合A A上的恒等关系上的恒等关系I IA A小于或等于关系小于或等于关系整除关系整除关系包含关系包含关系 可比可比可比可比定义定义7.207.20 设设R R为非空集合为非空集合A A上的偏序关系，定义上的偏序关系，定义(1) (1) x,yAx,yA，x xy y x xyxyyxy。(2) (2) x,yAx,yA，x x与与y y可比可比 x xyyyyx x。其中其中x xy y读作读作x“x“小于小于”y y。这里所说的这里所说的“小于小于”是指在偏序是指在偏序中中x x排在排在y y的前边。的前边。q在具有偏序关系的集合在具有偏序关系的集合A A中任取两个元素中任取两个元素x x和和y y，可能有下述几可能有下述几种情况发生：种情况发生：x xy(y(或或y yx)x)，x xy y，x x与与y y不是可比的。不是可比的。q例如例如A A11，2 2，33，是是A A上的整除关系，则有上的整除关系，则有1 12 2，1 13 3，1=11=1，2=22=2，3=33=3，2 2和和3 3不可比。不可比。全序关系全序关系全序关系全序关系定义定义7.217.21 设设R R为非空集合为非空集合A A上的偏序关系，如果上的偏序关系，如果 x,yAx,yA，x x与与y y都是可比的都是可比的，则称，则称R R为为A A上的上的全序关系全序关系( (或或线序关系线序关系) )。例如例如数集上的小于或等于关系是全序关系，因为任何两个数总是数集上的小于或等于关系是全序关系，因为任何两个数总是可比大小的。可比大小的。整除关系一般来说不是全序关系，如集合整除关系一般来说不是全序关系，如集合1,2,31,2,3上的整除上的整除关系就不是全序关系，因为关系就不是全序关系，因为2 2和和3 3不可比。不可比。 偏序集偏序集偏序集偏序集定义定义7.227.22 集合集合A A和和A A上的偏序关系上的偏序关系一起叫做一起叫做偏序集偏序集，记作，记作 。例如例如 整数集合整数集合Z Z和数的小于或等于关系和数的小于或等于关系构成偏序集构成偏序集 Z,集合集合A A的幂集的幂集P(A)P(A)和包含关系和包含关系R R 构成偏序集构成偏序集 。覆盖覆盖覆盖覆盖( ( ( (covercover) ) ) )定义定义7.237.23 设设 A,为偏序集。为偏序集。 x, ,yAA，如果如果 xy 且不存且不存在在 zAA使得使得xzy，则称则称y覆盖覆盖x。例如例如 1,2,4,61,2,4,6集合上的整除关系，集合上的整除关系，有有2 2覆盖覆盖1 1，4 4和和6 6都覆盖都覆盖2 2。但。但4 4不覆盖不覆盖1 1，因为有，因为有1 12 24 4。6 6也不覆盖也不覆盖4 4，因为，因为4 46 6不成立。不成立。哈斯图哈斯图哈斯图哈斯图( ( ( (HasseHasse diagram diagram) ) ) )q利用偏序关系的自反性、反对称性和传递性所得到的偏序利用偏序关系的自反性、反对称性和传递性所得到的偏序集合图，称为集合图，称为哈斯图哈斯图。q画偏序集画偏序集 的哈斯图的方法的哈斯图的方法(1)(1)用小圆圈代表元素。用小圆圈代表元素。(2)(2) x,yAx,yA，若若x xy y，则将则将x x画在画在y y的下方。的下方。(3)(3)对于对于A A中的两个不同元素中的两个不同元素x x和和y y，如果如果y y覆盖覆盖x x，就用一条就用一条线段连接线段连接x x和和y y。例例例例7.197.197.197.19例例7.197.19 画出偏序集画出偏序集1,2,3,4,5,6,7,8,9 和和 的哈斯图。的哈斯图。 例例例例7.207.207.207.20例例7.207.20 已知偏序集已知偏序集 A,R的哈斯图的哈斯图如右图所示，试求出集合如右图所示，试求出集合A A和关和关系系R R的表达式。的表达式。 解答解答A=a,b,c,d,e,f,g,hA=a,b,c,d,e,f,g,hR=R= ,IIA A 偏序集中的特殊元素偏序集中的特殊元素偏序集中的特殊元素偏序集中的特殊元素定义定义7.247.24 设设 为偏序集，为偏序集，B B A A，y yBB。（1 1）若若 x(xBx(xBy yx)x)成立，则称成立，则称y y为为B B的的最小元最小元。（2 2）若）若 x(xBxx(xBxy y) )成立，则称成立，则称y y为为B B的的最大元最大元。（3 3）若）若 x(xBxx(xBxy yxxy y) )成立，则称成立，则称y y为为B B的的极小元极小元。（4 4）若）若 x(xBx(xBy yxxxxy y) )成立，则称成立，则称y y为为B B的的极大元极大元。363242126B B最大元最大元最小元最小元极大元极大元极小元极小元2,3,6,122,3,6,12,24,36,24,366,126,122,3,62,3,666无无 无无24,262,312 12 6 6126 6 6 无无62,3 6 6 6 666特殊元素的性质特殊元素的性质特殊元素的性质特殊元素的性质q最小元是最小元是B B中最小的元素，它与中最小的元素，它与B B中其它元素都可比。中其它元素都可比。q极小元不一定与极小元不一定与B B中元素可比，只要没有比它小的元素，它中元素可比，只要没有比它小的元素，它就是极小元。就是极小元。q对于有穷集对于有穷集B B，极小元一定存在，但最小元不一定存在。最极小元一定存在，但最小元不一定存在。最小元如果存在，一定是唯一的。小元如果存在，一定是唯一的。q极小元可能有多个，但不同的极小元之间是不可比的（无极小元可能有多个，但不同的极小元之间是不可比的（无关系）。关系）。q如果如果B B中只有一个极小元，则它一定是中只有一个极小元，则它一定是B B的最小元。的最小元。q哈斯图中，集合哈斯图中，集合B B的极小元是的极小元是B B中各元素中的最底层。中各元素中的最底层。例例例例7.217.217.217.21例例7.217.21 设偏序集设偏序集 如右图所如右图所示，求示，求A A的极小元、最小元、极的极小元、最小元、极大元、最大元。大元、最大元。 解答解答极小元：极小元：a,b,c,ga,b,c,g极大元：极大元：a,f,ha,f,h。没有最小元与最大元没有最小元与最大元说说明明哈斯图中的孤立顶点既是极小元也是极大元。哈斯图中的孤立顶点既是极小元也是极大元。 例例例例7.227.227.227.22例例7.227.22 设设X X为集合，为集合，A AP(X)P(X) XX，且且AA。若若| |X|X|n n，问：问：（1 1）偏序集）偏序集 是否存在最大元？是否存在最大元？（2 2）偏序集）偏序集 是否存在最小元？是否存在最小元？（3 3）偏序集）偏序集 中极大元和极小元的一般形式是什么？中极大元和极小元的一般形式是什么？并说明理由。并说明理由。解答解答 A,R 不存在最小元和最大元，因为不存在最小元和最大元，因为n2n2。考察幂集考察幂集P(X)P(X)的哈斯图，最底层的顶点是空集，记作第的哈斯图，最底层的顶点是空集，记作第0 0层。层。由底向上，第由底向上，第1 1层是单元集，第层是单元集，第2 2层是二元子集，层是二元子集，由由| |X|=nX|=n，则第则第n n1 1层是层是X X的的n n1 1元子集，第元子集，第n n层，也就是最高层只有层，也就是最高层只有一个顶点一个顶点X X。偏序集偏序集 与与 相比，恰好缺少第相比，恰好缺少第0 0层与第层与第n n层层( (因为因为X X是是n n元集元集) )。因此。因此 的极小元就是的极小元就是X X的的所有单元集，即所有单元集，即 xx，xXxX；而极大元恰好少一个元素，即而极大元恰好少一个元素，即X-xX-x，xXxX。 上界、下界上界、下界上界、下界上界、下界定义定义7.257.25 设设 为偏序集，为偏序集，B B A A，y yAA。（1 1）若若 x(xBxx(xBxy y) )成立，则称成立，则称y y为为B B的的上界上界。（2 2）若）若 x(xBx(xBy yx)x)成立，则称成立，则称y y为为B B的的下界下界。（3 3）令）令C C y y| |y y为为B B的上界的上界 ，则称，则称C C的最小元为的最小元为B B的的最小上界最小上界或或上确界上确界。（4 4）令）令D D y y| |y y为为B B的下界的下界 ，则称，则称D D的最大元为的最大元为B B的的最大下界最大下界或或下确界下确界。 上界与下界举例上界与下界举例上界与下界举例上界与下界举例363242126B B上界上界下界下界上确界上确界下确界下确界2,3,6,12,3,6,12,24,362,24,366,126,122,3,62,3,666 无无 无无 无无 无无12,24,36 2,3,612,24,36 2,3,6 12 6 12 66,12,24,36 6,12,24,36 无无 6 6 无无6,12,24,366,12,24,36 2,3,6 6 6 2,3,6 6 6q考虑右考虑右图图中的偏序集。令中的偏序集。令B Bbb，c c，dd，则则B B的下界和最大下界都的下界和最大下界都不存在，上界有不存在，上界有d d和和f f，最小上界最小上界为为d d。上界与下界的性质上界与下界的性质上界与下界的性质上界与下界的性质qB B的最小元一定是的最小元一定是B B的下界，同时也是的下界，同时也是B B的最大下界。的最大下界。qB B的最大元一定是的最大元一定是B B的上界，同时也是的上界，同时也是B B的最小上界。的最小上界。qB B的下界不一定是的下界不一定是B B的最小元，因为它可能不是的最小元，因为它可能不是B B中的元素。中的元素。qB B的上界也不一定是的上界也不一定是B B的最大元。的最大元。qB B的上界、下界、最小上界、最大下界都可能不存在。如果的上界、下界、最小上界、最大下界都可能不存在。如果存在，最小上界与最大下界是唯一的。存在，最小上界与最大下界是唯一的。偏序关系的实例偏序关系的实例偏序关系的实例偏序关系的实例调调调调度问题度问题度问题度问题给定有穷的任务集给定有穷的任务集T T和和m m台相同的机器，台相同的机器，T T上存在偏序关系上存在偏序关系，如果如果t t1 1tt2 2，那么任务那么任务t t1 1完成以后完成以后t t2 2才能开始工作才能开始工作。 tTtT，l(t)l(t)表示完成任务表示完成任务t t所需要的时间，所需要的时间，d(t)d(t)表示任务表示任务t t的截止时间，的截止时间，l(t),d(t)Zl(t),d(t)Z+ +。设开始时间为设开始时间为0 0，f f:T0,1,:T0,1,D D 表示任务集表示任务集T T的一个调度方案，的一个调度方案，其中其中 f(t)f(t)表示任务表示任务t t的开始时间。的开始时间。 D D表示完成所有任务的最终时间。表示完成所有任务的最终时间。偏序关系的实例偏序关系的实例偏序关系的实例偏序关系的实例调调调调度问题度问题度问题度问题假设每项任务都可以安排在任何一台机器上进行工作，假设每项任务都可以安排在任何一台机器上进行工作，如果如果f f满足下述三个条件，则称满足下述三个条件，则称T T为为可行调度可行调度。(1)(1) tTtT，f(t)+l(t)d(t)f(t)+l(t)d(t)（表示每项任务都要在截至时间内完成表示每项任务都要在截至时间内完成）(2)(2) i i，0iD0iD，| |tT:f(t)itT:f(t)if(t)+l(t)f(t)+l(t) |m|m（表示任何时刻同时工作的机器台数不超过表示任何时刻同时工作的机器台数不超过m m）(3)(3) t,tt,tT,tT,tt tf(t)+l(t)f(tf(t)+l(t)f(t) )（表示任务安排必须满足任务集的偏序约束表示任务安排必须满足任务集的偏序约束）求使得求使得D D最小的可行调度。最小的可行调度。例例例例7.237.237.237.23q设设m m2 2，T Ttt1 1,t,t2 2,t,t6 6 ，每每项任务的截止时间都等于项任务的截止时间都等于7 7。去。去掉自反成分，掉自反成分，T T的偏序约束如右的偏序约束如右图所示。每个任务结点中的数字图所示。每个任务结点中的数字表示完成该任务所有的时间。表示完成该任务所有的时间。1t61t52t4121t3t2t1q下图中给出了两个可行的调度方下图中给出了两个可行的调度方案。案。t6t4t2t1t5t3t4t2t1t6t5t3D6D5本章主要内容本章主要内容本章主要内容本章主要内容q有序对与卡氏积有序对与卡氏积 q二元关系（包括空关系，恒等关系，全域关系等）及其表示二元关系（包括空关系，恒等关系，全域关系等）及其表示（关系矩阵，关系图）（关系矩阵，关系图）q关系的五种性质（自反性，反自反性，对称性，反对称性，传关系的五种性质（自反性，反自反性，对称性，反对称性，传递性）递性）q二元关系的幂运算二元关系的幂运算 q关系的三种闭包（自反闭包，对称闭包，传递闭包）关系的三种闭包（自反闭包，对称闭包，传递闭包） q等价关系和划分（包括等价类，商集，划分块等）等价关系和划分（包括等价类，商集，划分块等） q偏序关系（包括哈斯图，最大元，最小元，极大元，极小元，偏序关系（包括哈斯图，最大元，最小元，极大元，极小元，上界，下界，最小上界，最大下界等）上界，下界，最小上界，最大下界等） 本章学习要求本章学习要求本章学习要求本章学习要求q掌握：有序对及卡氏积的概念及卡氏积的性质掌握：有序对及卡氏积的概念及卡氏积的性质q掌握：二元关系，掌握：二元关系，A A到到B B的二元关系，的二元关系，A A上的二元关系，关系上的二元关系，关系的定义域和值域，关系的逆，关系的合成，关系在集合上的定义域和值域，关系的逆，关系的合成，关系在集合上的限制，集合在关系下的象等概念，掌握关系的定义域、的限制，集合在关系下的象等概念，掌握关系的定义域、值域、逆、合成、限制、象等的主要性质值域、逆、合成、限制、象等的主要性质 q掌握：关系矩阵与关系图的概念及求法掌握：关系矩阵与关系图的概念及求法 q掌握：集合掌握：集合A A上的二元关系的主要性质（自反性，反自反性，上的二元关系的主要性质（自反性，反自反性，对称性，反对称性，传递性）的定义及判别法，对某些关对称性，反对称性，传递性）的定义及判别法，对某些关系证明它们有或没有中的性质系证明它们有或没有中的性质 本章学习要求本章学习要求本章学习要求本章学习要求q掌握：掌握：A A上二元关系的上二元关系的n n次幂的定义及主要性质次幂的定义及主要性质 q掌握掌握A A上二元关系的自反闭包、对称闭包、传递闭包的定义上二元关系的自反闭包、对称闭包、传递闭包的定义及求法及求法 q掌握：等价关系、等价类、商集、划分、等概念，以及等价掌握：等价关系、等价类、商集、划分、等概念，以及等价关系与划分之间的对应关系与划分之间的对应 q掌握：偏序关系、偏序集、哈斯图、最大元、最小元、极大掌握：偏序关系、偏序集、哈斯图、最大元、最小元、极大元、极小元、上界、下界、上确界、下确界等概念元、极小元、上界、下界、上确界、下确界等概念 作业作业作业作业习题七习题七：1 1、3 3、4 4、1212、1313、1414、1616、2222、2626、3131、3232、3939、4242、4646、48 48 关系性质的证明关系性质的证明关系性质的证明关系性质的证明q通常的证明方法是利用定义证明。通常的证明方法是利用定义证明。qR R在在A A上自反上自反任取任取x，有有xA A RRqR R在在A A上对称上对称任取任取 ，有有 R R RRqR R在在A A上反对称上反对称任取任取 ，有有 R R R R xyqR R在在A A上传递上传递任取任取 ， ，有有 R R R R RR有关关系性质的练习题有关关系性质的练习题有关关系性质的练习题有关关系性质的练习题q在正整数集合上定义关系在正整数集合上定义关系R R：RR，如果如果x x和和y y的最大公因子是的最大公因子是1 1。判断判断R R是否满足关系的五条性质？是否满足关系的五条性质？q设设A=aA=a, ,b,cb,c，试给出试给出A A的一个二元关系的一个二元关系R R，使其同时不满足使其同时不满足五个性质。五个性质。qN N元素集合上有多少个自反的关系？元素集合上有多少个自反的关系？例题例题例题例题例题例题 在正整数集合上定义关系在正整数集合上定义关系R R：RR，如果如果x x和和y y的最大公因子是的最大公因子是1 1。判断判断R R是否满足关系的五条性质？是否满足关系的五条性质？ 分析分析按增序系统地列出所有的序对，然后观察。按增序系统地列出所有的序对，然后观察。 x,yx xy y最大公因子最大公因子是否在是否在R R中中2 21 1是是3 31 1是是3 31 1是是4 41 1是是4 42 2否否4 41 1是是例题例题例题例题解答解答 自反自反 否否 R R反自反反自反 否否 R R对称对称 是是 RRx,yRR反对称反对称 否否1RR ,2RR 但但 1 12 2传递传递 否否2RR ,1RR 但但 R R扩展扩展 (1) (1)从列出的若干序偶来考察是否属于关系。从列出的若干序偶来考察是否属于关系。(2)(2)按一定规则列出序偶。按一定规则列出序偶。(3)(3)一个范例即可证明不满足某种性质。一个范例即可证明不满足某种性质。(4)(4)证明某种性质成立，必须取出关系中的每个元素。证明某种性质成立，必须取出关系中的每个元素。例题例题例题例题例题例题 设设A=aA=a, ,b,cb,c，试给出试给出A A的一个二元关系的一个二元关系R R，使其同时不使其同时不满足五个性质。满足五个性质。 分析分析因为关系的各种性质的存在，都要求满足一定的条件，因为关系的各种性质的存在，都要求满足一定的条件，要做的就是创造或破坏这些条件。要做的就是创造或破坏这些条件。从从A AA A出发，通过删除某些序偶，使其不满足那些性质。出发，通过删除某些序偶，使其不满足那些性质。解答解答令令R R, R R不满足自反性不满足自反性RR不满足反自反性不满足反自反性R R R R不满足对称性不满足对称性RRbRRbc c不满足反对称性不满足反对称性RRRR R R不满足传递性不满足传递性 习题习题习题习题设设R R|x,yN |x,yN 且且 x+3yx+3y1212(1)(1)求求R R的集合表达式的集合表达式(2)(2)求求 domdom R R，ran Rran R(3)(3)求求R R R R(4)(4)求求R R2,3,4,62,3,4,6(5)(5)求求R3R3(6)R(6)R3 3解答：解答：,0,3,6,9,120,3,6,9,12，0,1,2,3,40,1,2,3,4,33习题习题习题习题q设设R R是复数集合是复数集合C C上的关系，且满足上的关系，且满足xRyxRyx-yx-ya+bia+bi，a a和和b b为给定的非负整数，试确定为给定的非负整数，试确定R R的性质并证明之。的性质并证明之。解答解答（1 1）当）当a ab b0 0时，满足自反性、对称性、反对称性和传递时，满足自反性、对称性、反对称性和传递性，不满足反自反性。性，不满足反自反性。（2 2）当）当a a、b b不全为不全为0 0时，只满足反自反性、反对称性。时，只满足反自反性、反对称性。习题习题习题习题例例题题 设设I I为为整整数数集集，R R|xy(mod |xy(mod k)k)，证证明明R R是是等等价价关关系。系。证明证明 设任意设任意a,b,cIa,b,cI(1)(1)因为因为a aa a0 0，所以所以 Ra,aR。(2)(2)若若ab(mod k)ab(mod k)，a ab bktkt(t(t为整数为整数) )，则，则b ba a- -ktkt，所以所以ba(mod k)ba(mod k)。(3)(3)若若ab(mod k)ab(mod k)，bc(mod k)bc(mod k)，则则a ab bktkt，b bc cksks(t(t和和s s为整数为整数) )，a ac ca ab bb bc cktktksksk(tk(ts)s)，所以所以ac(mod k)ac(mod k)因此，因此，R R是等价关系。是等价关系。