二元关系学习

1、1第7章 二元关系离离 散散 数数 学学中国地质大学本科生课程中国地质大学本科生课程2021/3/232021/3/232本章说明本章说明q 本章的主要内容本章的主要内容有序对与笛卡儿集有序对与笛卡儿集二元关系的定义和表示法二元关系的定义和表示法关系的运算关系的运算关系的性质关系的性质等价关系与划分等价关系与划分偏序关系偏序关系q 本章与后续各章的关系本章与后续各章的关系本章是函数的基础本章是函数的基础本章是图论的基础本章是图论的基础 2021/3/232021/3/233本章内容本章内容7.1 7.1 有序对与笛卡儿积有序对与笛卡儿积7.2 7.2 二元关系二元关系7.3 7.3 关系的运算

2、关系的运算7.4 7.4 关系的性质关系的性质7.6 7.6 等价关系与划分等价关系与划分7.7 7.7 偏序关系偏序关系 本章小结本章小结 习题习题 作业作业2021/3/232021/3/2347.1 有序对与笛卡儿积有序对与笛卡儿积 定义定义7.17.1 由两个元素由两个元素x x和和y y（允许允许x=yx=y）按一定顺序排列成的二元按一定顺序排列成的二元组叫做一个组叫做一个有序对有序对( (ordered pair) )或或序偶序偶, ,记作记作 ,x,y,其中其中x x是是它的第一元素它的第一元素, ,y y是它的第二元素。是它的第二元素。有序对有序对 x,y具有以下性质具有以下性

3、质: : （1 1）当）当xyxy时时,x,y。 （2 2） x,y的充分必要条件是的充分必要条件是x xu u且且y yv v。 说明说明q 有序对中的元素是有序的有序对中的元素是有序的q 集合中的元素是无序的集合中的元素是无序的2021/3/232021/3/235例例7.17.1例例7.17.1 已知已知 x+2,4,求求x x和和y y。 由有序对相等的充要条件有由有序对相等的充要条件有 x+2x+25 5 2 2x+yx+y4 4 解得解得 x x3,y3,y-2-2。 解答解答2021/3/232021/3/236定义定义7.27.2 设设A,BA,B为集合为集合, ,用用A A中

4、元素为第一元素中元素为第一元素, ,B B中元素为第二中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做元素构成有序对。所有这样的有序对组成的集合叫做A A和和B B的的笛卡儿积笛卡儿积( (Cartesian product), ,记作记作A AB B。笛卡儿积的符号化表示为笛卡儿积的符号化表示为A AB B|xAyB |xAyB 笛卡儿积的定义笛卡儿积的定义q A A表示某大学所有学生的集合表示某大学所有学生的集合,B,B表示大学开设的所有表示大学开设的所有课程的集合课程的集合, ,则则A AB B可以用来表示该校学生选课的所有可能情况。可以用来表示该校学生选课的所有可能情况。q

5、令令A A是直角坐标系中是直角坐标系中x x轴上的点集轴上的点集, ,B B是直角坐标系中是直角坐标系中y y轴上的点集轴上的点集, ,于是于是A AB B就和平面点集一一对应。就和平面点集一一对应。 举例举例2021/3/232021/3/237笛卡尔积举例笛卡尔积举例设设A=a,b, B=0,1,2,A=a,b, B=0,1,2,则则A AB=,B=,B BA=, A=, 举例举例说明说明q 如果如果| |A|=m,|B|=n,A|=m,|B|=n,则则| |A AB|=mnB|=mn。2021/3/232021/3/238笛卡儿积的运算性质笛卡儿积的运算性质 (1)(1)对任意集合对任意

6、集合A,A,根据定义有根据定义有A A, , A A(2)(2)一般的说一般的说, ,笛卡儿积运算不满足交换律笛卡儿积运算不满足交换律, ,即即A ABBBBA A ( (当当 AA B B AB AB 时时) )(3)(3)笛卡儿积运算不满足结合律笛卡儿积运算不满足结合律, ,即即( (A AB)B)CACA(B(BC)C)( (当当 AA B B C C 时时) )(4)(4)笛卡儿积运算对并和交运算满足分配律笛卡儿积运算对并和交运算满足分配律, ,即即A A(B(BC)=(AC)=(AB)B)(A(AC)C)( (B BC)C)A=(BA=(BA)A)(C(CA)A)A A(B(BC)=

7、(AC)=(AB)B)(A(AC)C)( (B BC)C)A=(BA=(BA)A)(C(CA)A)(5)(5)A A C BC B D D A AB B C CD D2021/3/232021/3/239A A(BC)=(A(BC)=(AB)(AB)(AC)C)的证明的证明任取任取 x,y Ax,yA(BC)(BC) xA yBC xA yBC xA (yByC) xA (yByC) (xAyB) (xAyC) (xAyB) (xAyC) A AB AB AC C (A (AB)(AB)(AC) C) 所以所以 A A(BC)=(A(BC)=(AB)(AB)(AC)C)2021/3/23202

8、1/3/2310关于关于A A CBCB D D A AB B C CD D的讨论的讨论该性质的逆命题不成立该性质的逆命题不成立, ,可分以下情况讨论。可分以下情况讨论。（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成立成立, ,证明如下证明如下: :任取任取xA,xA,由于由于BB, ,必存在必存在yB,yB,因此有因此有 xAyB xAyB A AB B C CD D xCyD xCyD xC xC从而证明了从而证明了 A A C C。同理可证同理可证 B

9、 B D D。2021/3/232021/3/2311关于关于A A CBCB D D A AB B C CD D的讨论的讨论该性质的逆命题不成立该性质的逆命题不成立, ,可分以下情况讨论。可分以下情况讨论。（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成立。成立。 反例略。反例略。 2021/3/232021/3/2312例例7.27.2例例7.2 7.

10、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, , , 解答解答2021/3/232021/3/2313例例7.37.3例例7.3 7.3 设设A,B,C,DA,B,C,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 ABCBCD D A AC CB BD D(4) (4) 存在集合存在集合A,A,使得

11、使得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 A= =A AA A 成立。成立。 解答解答2021/3/232021/3/23147.2 7.2 二元关系二元关系( (binary

12、relation)binary relation)定义定义7.37.3 如果一个集合满足以下条件之一如果一个集合满足以下条件之一: :（1 1）集合非空）集合非空, ,且它的元素都是有序对且它的元素都是有序对（2 2）集合是空集）集合是空集 则称该集合为一个则称该集合为一个二元关系二元关系, ,记作记作R R。二元关系也可简称为二元关系也可简称为关关系系。对于二元关系。对于二元关系R,R,如果如果 R,x,yR,可记作可记作xRy;xRy;如果如果 x,y R,R,则记作则记作xRyxRy。设设R R1 1,R,R2 2,a,b,a,b。则则R R1 1是二元关系是二元关系, ,R R2 2不

13、是二元关系不是二元关系, ,只是一个集合只是一个集合, ,除除非将非将a a和和b b定义为有序对。定义为有序对。根据上面的记法可以写根据上面的记法可以写1 1R R1 12,aR2,aR1 1b,aRb,aR1 1c c等。等。 举例举例2021/3/232021/3/2315集合集合A A上的二元关系的数目依赖于上的二元关系的数目依赖于A A中的元素数。中的元素数。如果如果| |A|=n,A|=n,那么那么| |A AA|=nA|=n2 2, A, AA A的子集就有的子集就有 个。个。每一个子集代表一个每一个子集代表一个A A上的二元关系上的二元关系, ,所以所以A A上有上有 个不同个

14、不同的二元关系。的二元关系。例如例如| |A|=3,A|=3,则则A A上有上有 个不同的二元关系。个不同的二元关系。7.2 7.2 二元关系二元关系定义定义7.4 7.4 设设A,BA,B为集合为集合, ,A AB B的任何子集所定义的二元关系叫做的任何子集所定义的二元关系叫做从从A A到到B B的二元关系的二元关系; ;特别当特别当A=BA=B时时, ,则叫做则叫做A A上的二元关系上的二元关系。 A=0,1,B=1,2,3,A=0,1,B=1,2,3,那么那么 R R1 1=,R=,R2 2=A=AB,RB,R3 3= = ,R,R4 4=等都是从等都是从A A到到B B的二元关系的二元

15、关系, ,而而R R3 3和和R R4 4同时也是同时也是A A上的二上的二元关系。元关系。 举例举例22n22n232说明说明2021/3/232021/3/2316常用的关系常用的关系定义定义7.57.5 对任意集合对任意集合A,A,定义定义全域关系全域关系 E EA A=|xAyA=A=|xAyA=AA A 恒等关系恒等关系 I IA A=|xA=|xA空关系空关系 设设 A=1,2,A=1,2,那么那么E EA A=,=,I IA A=,=, 举例举例2021/3/232021/3/2317其它常用的关系其它常用的关系q 小于或等于关系小于或等于关系:L:LA A=|x,yAxy,=|

16、x,yAxy,其中其中 A A R R。q 整除关系整除关系: :D DB B=|x,yBx=|x,yBx整除整除y,y,其中其中 A A Z Z* * Z Z* *是非零整数集是非零整数集q 包含关系包含关系: :R R |x,yAx|x,yAx y,y,其中其中 A A是集合族。是集合族。 (1)(1)设设 A=1,2,3,BA=1,2,3,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, , , , , 举例举例2021/3/23202

17、1/3/2318例例7.47.4例例7.47.4 设设A=1,2,3,4,A=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=,=, , , 2021/

18、3/232021/3/2319关系的表示方法关系的表示方法q关系的三种表示方法关系的三种表示方法: :集合表达式集合表达式关系矩阵关系矩阵关系图关系图q关系矩阵和关系图可以表示有穷集上的关系。关系矩阵和关系图可以表示有穷集上的关系。2021/3/232021/3/2320关系矩阵和关系图的定义关系矩阵和关系图的定义设设A=xA=x1 1,x,x2 2, ,x,xn n,R,R是是A A上的关系。令上的关系。令 n)n), ,1,2,1,2,j j(i,(i,RxRx若x若x0 0RxRx若x若x1 1 r rj ji ij ji iij ijnnnnn2n2n1n12n2n222221211n

19、1n12121111ij ijr rr rr rr rr rr rr rr rr r) )(r (r则则 是是R R的的关系矩阵关系矩阵, ,记作记作M MR R。 设设A=xA=x1 1,x,x2 2, ,x,xn n,R,R是是A A上的关系。令图上的关系。令图G=,G=,其中顶点其中顶点集合集合V=A,V=A,边集为边集为E E。对于对于 x xi i,x,xj jV,V,满足满足 E E x xi iRxRxj j称图称图G G为为R R的的关系图关系图, ,记作记作 G GR R。2021/3/232021/3/2321关系矩阵和关系图的实例关系矩阵和关系图的实例设设 A=1,2,3

20、,4,R=,A=1,2,3,4,R=,则则R R的关系矩阵和关系图分别是的关系矩阵和关系图分别是 0 00 01 10 00 00 00 00 01 11 10 00 00 00 01 11 1MMR R2021/3/232021/3/23227.3 7.3 关系的运算关系的运算定义定义7.67.6 设设R R是二元关系。是二元关系。(1)(1)R R中所有有序对的第一元素构成的集合称为中所有有序对的第一元素构成的集合称为R R的的定义域定义域( (domain)domain), ,记为记为dom Rdom R。形式化表示为形式化表示为: :dom R dom R x | x | y(Ry(R

21、 )(2)(2)R R中所有有序对的第二元素构成的集合称为中所有有序对的第二元素构成的集合称为R R的的值域值域( (range)range) , ,记作记作ran Rran R。形式化表示为形式化表示为ran Rran Ry | y | x(R) x(R)(3)(3)R R的定义域和值域的并集称为的定义域和值域的并集称为R R的的域域( (field)field), ,记作记作fld Rfld R。形形式化表示为式化表示为fld Rfld Rdom R ran R dom R ran R 例例7.57.5 求求R=,R=,的定义域、值域和域。的定义域、值域和域。 解答解答dom Rdom R

22、1,2,4 ran R1,2,4 ran R2,3,4 fld R2,3,4 fld R1,2,3,4 1,2,3,4 2021/3/232021/3/2323关系的逆和右复合运算关系的逆和右复合运算定义定义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),

23、yG)例例7.67.6 设设F F,G=,G=,则则F F-1 -1 ,F F G GG G F F说明说明q 可以把二元关系看作一种作用可以把二元关系看作一种作用, , Rx,yR可以解释为可以解释为x x通过通过R R的作用变到的作用变到y y。q F F G G表示两个作用的连续发生。表示两个作用的连续发生。2021/3/232021/3/2324关系的限制和像关系的限制和像定义定义7.97.9 设设R R为二元关系为二元关系,A,A是集合是集合(1) (1) R R在在A A上的上的限制限制( (restriction) )记作记作R RA,A,其中其中R RA=|xRyxA A=|x

24、RyxA (2) A(2) A在在R R下的下的像像( (image) )记作记作RA,RA,其中其中RA=ran(RRA=ran(RA) A) 说明说明q R R在在A A上的限制上的限制RARA是是R R的子关系。的子关系。q A A在在R R下的像下的像RARA是是ran Rran R的子集。的子集。2021/3/232021/3/2325例例7.77.7设设R R,R R11,R R R R2,32,3 ,RR112,32,3RR RR33222021/3/232021/3/2326关系与集合的说明关系与集合的说明q 关系是集合关系是集合, ,集合运算对于关系也是适用的。集合运算对于关

25、系也是适用的。 q 规定规定: :关系运算中逆运算优先于其它运算关系运算中逆运算优先于其它运算所有的关系运算都优先于集合运算所有的关系运算都优先于集合运算, ,优先权的运算以括号决定运算顺序。优先权的运算以括号决定运算顺序。 q 例如例如: :ran Fran F-1-1F F GFGF H Hran (Fran (FA)A)2021/3/232021/3/2327例题例题q 设设A A表示是学校的所有学生的集合表示是学校的所有学生的集合,B,B表示学校的所有课程的集合表示学校的所有课程的集合, ,并设并设R R1 1由所有有序对由所有有序对 a,b组成组成, ,其中其中a a是选修课程是选修

26、课程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的含义为的含义为q R R1 1RR2 2:a:a是一个学生是一个学生, ,他或者选修了课程他或者选修了课程b,b,或者课程或者课程b b是他的必是他的必修课。修课。q R R1 1RR2 2:a:a是一个学生是一个学生, ,他选修了课程他选修了课程b b并且课程并且课程b b也是也是a a的必修课的必修课。 q R R1

27、1RR2 2: :学生学生a a已经选修了课程已经选修了课程b,b,但课程但课程b b不是不是a a的必修课的必修课, ,或者课或者课程程b b是是a a的必修课的必修课, ,但是但是a a没有选修它。没有选修它。q R R1 1R R2 2: :学生学生a a已经选修了课程已经选修了课程b,b,但课程但课程b b不是不是a a的必修课。的必修课。 q R R2 2R R1 1: :课程课程b b是学生是学生a a的必修课的必修课, ,但是但是a a没有选修它。没有选修它。 2021/3/232021/3/2328定理定理7.17.1定理定理7.17.1 设设F F是任意的关系是任意的关系,

28、,则则 (1)(1)(F F-1-1) )-1-1F F (2)(2)dom Fdom F-1-1ran F,ran Fran F,ran F-1-1dom F dom F (1)(1)任取任取 ,x,y,由逆的定义有由逆的定义有 x,y(F(F-1-1) )-1-1 F F-1-1 F F (2)(2)任取任取x x x xdom dom F F-1-1 y y(x,(FF-1-1) ) y y(F) ,xF) xran F xran F 所以有所以有 dom Fdom F-1-1ran Fran F证明证明2021/3/232021/3/2329定理定理7.27.2定理定理7.27.2 设

29、设F,G,HF,G,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)2021/3/232021/3/2330定理定理7.

30、27.2定理定理7.27.2 设设F,G,HF,G,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-12021/3/232021/3/2331定理定理7.37.3定理定理7.3 7.3 设设R R为为A A上的关系上的关系, ,则则R R I IA AI IA A R RR R证

31、明证明(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 R2021/3/232021/3/2332定理定理7.47.4定理定理7.47.4 设设F,G,HF,G,H是任意的关系是任意的关系, ,则则(1) (1) F F ( (G GH)H)F F GFGF H H(2) (GH)(2) (GH) F FG G F FH

32、H 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 FG F H H x,yF F GFGF

33、H H2021/3/232021/3/2333定理定理7.47.4的推论的推论q 由数学归纳法不难证明定理由数学归纳法不难证明定理7.47.4的结论对于有限多个关系的结论对于有限多个关系的并和交也是成立的的并和交也是成立的, ,即有即有R R (R(R1 1RR2 2RRn n) )R R R R1 1RR R R2 2RR R Rn n( R( R1 1 RR2 2RRn n) ) R RR R1 1 RRRR2 2 RRRRn n R RR R (R(R1 1RR2 2RRn n) ) R R R R1 1RR R R2 2RR R Rn n ( R ( R1 1RR2 2RRn n) )

34、 R R R R1 1 RRRR2 2 RRRRn n R R 2021/3/232021/3/2334定理定理7.57.5定理定理7.57.5 设设F F为关系为关系,A,B,A,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 2021/3/232021/3/2335定理定理7.5 (1)7.5 (1)的证明的证明(1) (1) F(AB)F(AB)FAFB FAFB 证明证明任取任取 ,x,y, F(AB) F

35、(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。 2021/3/232021/3/2336定理定理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,y

36、Fx xB) B) yFA yFB yFA yFB yFAFByFAFB所以有所以有 FABFAB FAFB FAFB 2021/3/232021/3/2337关系的幂运算关系的幂运算定义定义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+1n+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次

37、幂都相等次幂都相等, ,都等于都等于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 R2021/3/232021/3/2338Rn的计算的计算q 给定给定A A上的关系上的关系R R和自然数和自然数n,n,怎样计算怎样计算R Rn n呢呢? ?q 若若n n是是0 0或或1,1,结果是很简单的。下面考虑结果是很简单的。下面考虑n2n2的情况。的情况。如果如果R R是用是用集合表达式集合表达式给出的给出的, ,可以通过可以通过n-1n-1次右复合次右复合计算计算

38、得到得到R Rn n。如果如果R R是用是用关系矩阵关系矩阵M M给出的给出的, ,则则R Rn n的关系矩阵是的关系矩阵是M Mn n, ,即即n n个个矩阵矩阵M M之积之积。与普通矩阵乘法不同的是。与普通矩阵乘法不同的是, ,其中的相加是逻辑其中的相加是逻辑加加, ,即即1+11+11,1+01,1+00+10+11,0+01,0+00 0如果如果R R是用是用关系图关系图G G给出的给出的, ,可以直接由图可以直接由图G G得到得到R Rn n的关系图的关系图GG。GG的顶点集与的顶点集与G G相同。考察相同。考察G G的每个顶点的每个顶点x xi i, ,如果如果在在G G中中从从x

39、 xi i出发经过出发经过n n步长的路径到达顶点步长的路径到达顶点x xj j, ,则在则在GG中加一条从中加一条从x xi i到到x xj j的边的边。当把所有这样的便都找到以后。当把所有这样的便都找到以后, ,就得到图就得到图GG。 2021/3/232021/3/2339例例7.87.8例例7.87.8 设设A Aa,b,c,d,Ra,b,c,d,R,求求R R的各次幂的各次幂, ,分别用矩阵和关系图表示。分别用矩阵和关系图表示。 解答解答0 00 00 00 01 10 00 00 00 01 10 01 10 00 01 10 0MM0 00 00 00 01 10 00 00 0

40、0 01 10 01 10 00 01 10 00 00 00 00 01 10 00 00 00 01 10 01 10 00 01 10 0MM2 20 00 00 00 01 10 00 00 00 01 10 01 10 00 01 10 00 00 00 00 00 00 00 00 01 10 01 10 00 01 10 01 1MMMMMM2 23 31 10 00 00 00 01 10 00 00 00 01 10 00 00 00 01 1MM0 00 00 00 00 00 00 00 00 01 10 01 10 00 01 10 01 10 00 00 00 00

41、00 00 00 00 01 10 01 11 10 01 10 02021/3/232021/3/2340例例7.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, ,的关系图如下图所示。的关系图如下图所示。0 00 00 00 01 10 00 00 00 01 10 01 10 00 01 10 00 00 00 00 00 00 00 00 00 01 10 0

42、1 11 10 01 10 0MMMMMM3 34 40 00 00 00 00 00 00 00 01 10 01 10 00 01 10 01 12021/3/232021/3/2341幂运算的性质幂运算的性质定理定理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,Rk,Rk k都是都是A AA A的子集。的子集。证明证明又知又知| |A AA|=nA|=n2 2，|P(A|P(AA)|= A)|= ，2 2n n

43、2 2即即A AA A的不同子集仅的不同子集仅 个。个。2 2n n2 2当列出当列出R R的各次幂的各次幂R R0 0，R R1 1，R R2 2， ，时，时，2 2n n2 2R R必存在自然数必存在自然数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。 2021/3/232021/3/2342定理定理7.77.7定理定理7.77

44、.7 设设R R是是A A上的关系上的关系,m,nN,m,nN,则则(1)(1)R Rm m R Rn nR Rm+nm+n(2)(R(2)(Rm m) )n nR Rmnmn证明证明(1)(1)对于任意给定的对于任意给定的mN,mN,施归纳于施归纳于n n。若若n=0,n=0,则有则有所以对一切所以对一切m,nNm,nN有有 R Rm m R Rn nR Rm+nm+n。R Rm m R R0 0 R Rm m I IA A R Rm m R Rm+0m+0假设假设R Rm m R Rn n=R=Rm+nm+n, ,则有则有R Rm m R Rn+1n+1 R Rm m (R(Rn n R)

45、R)(R(Rm m R Rn n) ) R R R Rm+n+1m+n+1, ,2021/3/232021/3/2343定理定理7.77.7定理定理7.77.7 设设R R是是A A上的关系上的关系,m,nN,m,nN,则则(1)(1)R Rm m R Rn nR Rm+nm+n(2)(R(2)(Rm m) )n nR Rmnmn证明证明(2)(2)对于任意给定的对于任意给定的mN,mN,施归纳于施归纳于n n。若若n=0,n=0,则有则有所以对一切所以对一切m,nN m,nN 有有( (R Rm m) )n n=R=Rmnmn。( (R Rm m) )0 0 I IA A R R0 0 R

46、Rm m0 0假设假设( (R Rm m) )n nR Rmnmn, ,则有则有( (R Rm m) )n+1n+1 (R(Rm m) )n n R Rm m R Rmn+mmn+m R Rm(n+1)m(n+1)2021/3/232021/3/2344定理定理7.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+ks+k=R=Rt+kt+k(2) (2) 对任何对任何k,iNk,iN有有 R Rs+kp+is+kp+i=R

47、=Rs+is+i, ,其中其中p=t-sp=t-s(3) (3) 令令S=RS=R0 0,R,R1 1, ,R,Rt-1t-1,则对于任意的则对于任意的qNqN有有 R Rq qSS证明证明(1) (1) R Rs+ks+kR Rs s R Rk kR Rt t R Rk kR Rt+kt+k(2)(2)对对k k归纳。归纳。若若k=0,k=0,则有则有 R Rs+0 p+is+0 p+iR Rs+is+i假设假设 R Rs+kp+is+kp+iR Rs+is+i, ,其中其中p pt-s,t-s,则则R Rs+(k+1)p+is+(k+1)p+i R Rs+kp+i+ps+kp+i+pR R

48、s+i s+i R Rp p=R=Rs+p+is+p+iR Rs+t-s+is+t-s+i R Rt+it+i R Rs+is+i由归纳法命题得证。由归纳法命题得证。R Rs+kp+i s+kp+i R Rp p2021/3/232021/3/2345定理定理7.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+ks+k=R=Rt+kt+k(2) (2) 对任何对任何k,iNk,iN有有 R Rs+kp+is+kp+i=R=

49、Rs+is+i, ,其中其中p=t-sp=t-s(3) (3) 令令S=RS=R0 0,R,R1 1, ,R,Rt-1t-1,则对于任意的则对于任意的qNqN有有 R Rq qSS证明证明(3)(3)任取任取qN,qN,若若qt,qt,显然有显然有R Rq qS,S,若若qt,qt,则存在自然数则存在自然数k k和和i i使得使得q qs+kp+is+kp+i其中其中00ip-1,pip-1,pt-st-s。于是于是R Rq qR Rs+kp+is+kp+iR Rs+is+i而而s+is+p-1s+is+p-1 s+t-s-1s+t-s-1 t-1t-1这就证明了这就证明了 R Rq qSS。

50、2021/3/232021/3/2346定理定理7.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,f,R=,A=a,b,d,e,f,R=,。求出最小的自然数求出最小的自然数m m和和n,n,使得使得mnmn且且R Rm m=R=Rn n。 解答解答由由R R的定义可以看出的定义可以看出A A中的元素可分成

51、两组中的元素可分成两组, ,即即 a,ba,b和和 d,e,fd,e,f。它们在它们在R R的右复合运算下有下述变化规律的右复合运算下有下述变化规律: :ababababdefdefdefdef对于对于a a或或b,b,每个元素的变化周期是每个元素的变化周期是2 2。对于。对于d,e,f,d,e,f,每个元素每个元素的变化周期是的变化周期是3 3。因此必有。因此必有R Rm m=R=Rm+6m+6, ,其中其中6 6是是2 2和和3 3的最小公倍的最小公倍数。取数。取m=0,n=6m=0,n=6即满足题目要求。即满足题目要求。2021/3/232021/3/23477.4 7.4 关系的性质关

52、系的性质q 自反性自反性q 反自反性反自反性q 对称性对称性q 反对称性反对称性q 传递性传递性2021/3/232021/3/2348自反性和反自反性自反性和反自反性定义定义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, ,小于等于关系小于等

53、于关系L LA A, ,整除关系整除关系D DA A都都是为是为A A上的上的自反关系自反关系。包含关系包含关系R R是给定集合族是给定集合族A A上的上的自反关系自反关系。小于关系小于关系和和真包含关系真包含关系都是给定集合或集合族上的都是给定集合或集合族上的反自反反自反关系关系。2021/3/232021/3/2349例例7.107.10例例7.107.10 设设A=1,2,3,RA=1,2,3,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上的自反关系

54、和反自反关系。上的自反关系和反自反关系。解答解答 R R1 1既不是自反的也不是反自反的既不是自反的也不是反自反的, ,R R2 2是自反的是自反的, ,R R3 3是反自反的。是反自反的。2021/3/232021/3/2350对称性和反对称性对称性和反对称性定义定义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上的上的反对称反对称(

55、 (antisymmetry) )关系。关系。 例如例如 A A上的上的全域关系全域关系E EA A, ,恒等关系恒等关系I IA A和和空关系空关系都是都是A A上的上的对称关对称关系系。恒等关系恒等关系I IA A和和空关系空关系也是也是A A上的上的反对称反对称关系。关系。但全域关系但全域关系E EA A一般不是一般不是A A上的反对称关系上的反对称关系, ,除非除非A A为单元集为单元集或空集。或空集。2021/3/232021/3/2351例例7.117.11例例7.117.11 设设A A1,2,3,R1,2,3,R1 1,R,R2 2,R,R3 3和和R R4 4都是都是A A上

56、的关系上的关系, ,其中其中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既不是对称的也不是反对称的。既不是对称的也不是反对称的。2021/3/232021/3/2352传递性传递性定义定义7.137.13 设设R R为为A A上的关系上的关系, ,若若 x x y

57、 y z(x,y,zARRR)z(x,y,zARRR)则称则称R R是是A A上的上的传递传递( (transitivity) )关系。关系。例如例如 A A上的上的全域关系全域关系E EA A, ,恒等关系恒等关系I IA A和和空关系空关系都是都是A A上的上的传递关系传递关系。小于等于关系小于等于关系, ,整除关系整除关系和和包含关系包含关系也是相应集合上的也是相应集合上的传递传递关系关系。小于关系小于关系和和真包含关系真包含关系仍旧是相应集合上的传递关系。仍旧是相应集合上的传递关系。 2021/3/232021/3/2353例例7.127.12例例7.127.12 设设A A1,2,3

58、,R1,2,3,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上的传递关系。上的传递关系。 2021/3/232021/3/2354关系性质的等价描述关系性质的等价描述 定理定理7.97.9 设设R R为为A A上的关系上的关系, ,则则（1 1）R R在在A A上自反当且仅当上自反当且仅当 I IA A R R（2 2）R R

59、在在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 利用该定理可以从关系的集合表达式来判断或证明关利用该定理可以从关系的集合表达式来判断或证明关系的性质。系的性质。分析分析关系性质的证明方法关系性质的证明方法2021/3/232021/3/2355定理定理7.9 (1)7.9 (1)的证明的证明（1 1） R R在在A A上自反当且

60、仅当上自反当且仅当 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上是自反的。上是自反的。2021/3/232021/3/2356定理定理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上是反自反的。