离散数学教案(3).ppt

《离散数学教案(3).ppt》由会员分享，可在线阅读，更多相关《离散数学教案(3).ppt（138页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、q第七章第七章q二元关系二元关系本章说明本章说明本章说明本章说明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

2、 等价关系与划分等价关系与划分7.7 7.7 偏序关系偏序关系 本章小节本章小节 习题习题 作业作业 7.1 7.1 有序对与笛卡儿积有序对与笛卡儿积有序对与笛卡儿积有序对与笛卡儿积 定义定义7.17.1 元素元素x x和和y y按一定顺序排成的二元组叫做一按一定顺序排成的二元组叫做一个有序对或序偶，记作个有序对或序偶，记作，其中，其中x x、y y分别为第分别为第一、第二元素。一、第二元素。有序对有序对具有的性质：具有的性质：（1 1）当）当xyxy时，时，.（2 2）的充要条件是的充要条件是x xu u且且y yv v.例例例例 7.1 7.1 7.1 7.1例例7.17.1 已知已知 x

3、+2,4，求，求x x和和y.y.解解:由有序对相等的充要条件有由有序对相等的充要条件有 x+2=5x+2=5 且且 2x+y2x+y4,4,解得解得 x x3,y3,y-2.-2.定义定义7.27.2 设设A A，B B为集合为集合,令令A A中元素为第一中元素为第一元素，元素，B B中元素为中元素为第二元素的有序对，构成的集合叫第二元素的有序对，构成的集合叫A A和和B B的的笛卡儿积。笛卡儿积。笛卡儿积表示为笛卡儿积表示为A AB B|xAyB|xAyB.笛卡儿积的定义笛卡儿积的定义笛卡儿积的定义笛卡儿积的定义笛卡尔积举例笛卡尔积举例设设A=A=a,ba,b,B=0,1,2,B=0,1,

4、2，则，则A AB=,.B=,.B BA=,.A=,.举例举例说明说明q如果如果|A|=A|=m,|Bm,|B|=n,|=n,则则|A AB|=B|=mnmn.笛卡儿积的运算性质笛卡儿积的运算性质 (1)(1)对任意集合对任意集合A A，根据定义有，根据定义有A A,A A.(2)(2)一般，笛卡儿积运算不满足交换律，即一般，笛卡儿积运算不满足交换律，即A ABBBBA(A(当当 A A B B AB AB 时时)。(3)(3)笛卡儿积运算不满足结合律，即笛卡儿积运算不满足结合律，即(A(AB)B)CACA(B(BC)(C)(当当 A ABBCC 时时)。(4)(4)笛卡儿积运算对并和交运算满

5、足分配律，即笛卡儿积运算对并和交运算满足分配律，即A A(BC)=(A(BC)=(AB)(AB)(AC)C).(BC)(BC)A=(BA=(BA)(CA)(CA).A).A A(BC)=(A(BC)=(AB)(AB)(AC).C).(BC)(BC)A=(BA=(BA)(CA)(CA).A).(5)A(5)A C BC B D D A AB B C CD D.A(BC)=(AB)(AC)A(BC)=(AB)(AC)的证明的证明任取任取 ,A(BC)A(BC)xA yBC xA yBC xA (yByC)xA (yByC)(xAyB)(xAyC)(xAyB)(xAyC)AB AC AB AC (A

6、B)(AC)(AB)(AC)所以所以 A(BA(BC)=(AB)C)=(AB)(AC)(AC).关于关于A A CBCB D D AB AB CDCD的讨论的讨论该性质的逆命题不成立，可如下讨论该性质的逆命题不成立，可如下讨论:（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成立，证明如下：成立，证明如下：任取任取xAxA，由于，由于BB,必存在必存在yB,yB,因此有因此有 xAyB xAyB AB AB CD CD xCyD xCyD xC xC.从而证明了从而

7、证明了 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.2 7.2 7.2 7.2例

8、例7.27.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.37.3 A A，B B，C C，D D为任意集合，以下命题是否为真为任意集合，以下命题是否为真?理由理由?(1)A(1)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，使得，使得A A A AA.A.(1)(1)不一定。当不一定。当A

9、A，B B1,C1,C22时，有时，有 A AB BA AC C，但，但BC.BC.(2)(2)不一定。当不一定。当A=B=1,CA=B=1,C22时，有时，有 A-(B A-(BC)C)111,1,(A-B)A-B)(A-C)(A-C)11.(3)(3)为真。由等量代入的原理可证。为真。由等量代入的原理可证。(4)(4)为真。当为真。当A A时，有时，有 A A A AA A 成立。成立。解答解答7.2 7.2 二元关系二元关系(binary relation)(binary relation)定义定义7.37.3 如果一个集合满足以下条件之一：如果一个集合满足以下条件之一：（1 1）集合非

10、空，且它的元素都是有序对）集合非空，且它的元素都是有序对（2 2）集合是空集）集合是空集 则称该集合为一个二元关系，记作则称该集合为一个二元关系，记作R R，简称为关系。如果，简称为关系。如果 RR，记作，记作xRyxRy；如果；如果 R R，则记作，则记作x y.x y.设设R R1 1,，R R2 2,a,ba,b.R R1 1是二元关系，是二元关系，R R2 2不是二元关系，只是集合，除非将不是二元关系，只是集合，除非将a a和和b b定义为有序对。定义为有序对。由上面的记法可写由上面的记法可写1 1R R1 12 2，aRaR1 1b b，aRaR1 1c c等。等。举例举例 7.2

11、7.2 7.2 7.2 二元关系二元关系二元关系二元关系定义定义7.47.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 对任意集

12、合对任意集合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=,.=,.举例举例其它常用的关系其它常用的关系小于或等于关系：小于或等于关系：L LA A=|x,yAxy=|x,yAxy,其中其中A A R.R.整除关系：整除关系：D DB B=|x,yBx=|x,yBx整除整除yy，其中，其中B B Z Z*,Z Z*是非零整数集。是非零整数集。包含关系：包含关系：R R|x,yAx|x,yAx yy,A A是集合族。是

13、集合族。(1)(1)设设 A=1,2,3A=1,2,3，B B a,ba,b 则则 L LA A=,=,D DA A=,.=,.(2)(2)令令A=P(B)=A=P(B)=,a,b,a,ba,b,a,b，A A上包含关系是上包含关系是 R R,.举例举例例例 7.4 7.4例例7.47.4 设设A=1,2,3,4A=1,2,3,4,下面各式定义的下面各式定义的R R都是都是A A上上的关系，试用列元素法表示的关系，试用列元素法表示R R.(1)R=|x(1)R=|x是是y y的倍数的倍数,(2)R=(2)R=|(x-y)|(x-y)2 2A,A,(3)R=(3)R=|x/yx/y是素数是素数,

14、(4)R=(4)R=|xyxy.解解(1)(1)R=,R=,(2)(2)R=,R=,(3)(3)R=,R=,(4)R=E(4)R=EA A-I-IA A=,.,.关系的表示方法关系的表示方法关系的三种表示方法：关系的三种表示方法：集合表达式集合表达式关系矩阵关系矩阵关系图关系图关系矩阵和关系图可以表示有穷集上的关系。关系矩阵和关系图可以表示有穷集上的关系。关系矩阵和关系图的定义关系矩阵和关系图的定义设设A=xA=x1 1,x,x2 2,x xn n,R,R是是A A上的关系。令上的关系。令 则则 是是R R的关系矩阵，记作的关系矩阵，记作M MR R.关系矩阵和关系图的定义关系矩阵和关系图的定

15、义设A=x1,x2,xn,R是A上的关系。令图G=，其中顶点集合V=A，边集为E.对于xi,xjV，满足 E xiRxj称图G为R的关系图，记作 GR.关系矩阵和关系图的实例关系矩阵和关系图的实例设设 A=1,2,3,4A=1,2,3,4，R=,R=,，则则R R的关系矩阵和关系图分别是的关系矩阵和关系图分别是 7.3 7.3 关系的运算关系的运算定义定义7.67.6 设设R R是二元关系。是二元关系。(1)R(1)R中所有有序对的第一元素构成的集合称为中所有有序对的第一元素构成的集合称为R R的定义域，的定义域，记为记为dom Rdom R.形式化表示为：形式化表示为：dom Rdom Rx

16、|x|y(R)y(R).(2)R(2)R中有序对的第二元素构成的集合称中有序对的第二元素构成的集合称R R的值域的值域,表示为表示为ran Rran Ry|y|x(R)x(R).(3)R(3)R的定义域和值域的并集称为的定义域和值域的并集称为R的域，记作的域，记作fld Rfld R.表示为表示为fld Rfld Rdom R ran Rdom R ran R.例题例题例7.5 求R=,的定义域、值域和域。解:domR1,2,4,ranR2,3,4,fld R1,2,3,4.关系的逆和右复合运算关系的逆和右复合运算定义定义7.77.7 设设R R为二元关系为二元关系,R,R的逆关系的逆关系,简

17、称简称R R的逆的逆,记作记作R R-1-1,其中其中 R R-1-1|R|R.定义定义7.87.8 设设F,GF,G为二元关系，为二元关系，G G对对F F的右复合记作的右复合记作F F G G，其中，其中 F F G G|t(FG)t(FG).例例7.67.6 设设F F,G=,G=，则，则F F-1-1,F F G GG G F F关系的限制和像关系的限制和像定义定义7.97.9 设设R R为二元关系，为二元关系，A A是集合是集合(1)R(1)R在在A A上的限制上的限制(restrictionrestriction)记作记作RARA，其中，其中RA=|xRyxARA=|xRyxA.(

18、2)A(2)A在在R R下的像下的像(imageimage)记作记作RARA，其中，其中RA=ran(RA)RA=ran(RA).例例 7.7 7.7设设R R，.RR11，,RR ,RR2,32,3，,RR112,3,2,3,RR ,RR332,2,ran Rran R2,3,4,2,3,4,RR22 2,4.2,4.关系与集合的说明关系与集合的说明关系是集合，集合运算对于关系也是适用的。关系是集合，集合运算对于关系也是适用的。规定规定：关系运算中逆运算优先于其它运算关系运算中逆运算优先于其它运算所有的关系运算都优先于集合运算，所有的关系运算都优先于集合运算，优先权的运算以括号决定运算顺序。

19、优先权的运算以括号决定运算顺序。例例题题设设A A是学校的所有学生的集合，是学校的所有学生的集合，B B是学校的所有课是学校的所有课程集合，并设程集合，并设R R1 1由所有有序对由所有有序对组成，其中组成，其中a a是选修课程是选修课程b b的学生。的学生。R R2 2由所有的有序对由所有的有序对构构成，其中课程成，其中课程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分别为分别为例例题题R R1 1RR2 2:a:a是一个学生是一个学生,他或选修了课程他或选修了课程b

20、 b,或或b b是他的必修课。是他的必修课。R R1 1RR2 2:a:a是一学生是一学生,他选修了课程他选修了课程b b且课程且课程b b也是也是a a的必修课。的必修课。R R1 1RR2 2:学生学生a a已选修了课程已选修了课程b b，但课程，但课程b b不是不是a a的选修课，或的选修课，或课程课程b b是是a a的必修课，但的必修课，但a a没有选修它。没有选修它。R R1 1R R2 2：学生：学生a a已经选修了课程已经选修了课程b b，但课程，但课程b b不是不是a a的选修课。的选修课。R R2 2R R1 1：课程：课程b b是学生是学生a a的必修课，但是的必修课，但是

21、a a没有选修它。没有选修它。定理定理7.17.1定理定理7.17.1 设设F F是任意的关系，则是任意的关系，则 (1)(F(1)(F-1-1)-1-1F F(2)dom F(2)dom F-1-1ran Fran F，ran Fran F-1-1dom F dom F.(1)(1)任取任取,由逆的定义有由逆的定义有 (F(F-1-1)-1-1 F F-1-1 FF (2)(2)任取任取x x x xdomdom F F-1-1 y(y(FF-1-1)y(y(F)F)xranxran F F 所以有所以有 domdom F F-1-1ran F.ran F.证明证明定理定理7.27.2定理定

22、理7.27.2 设设F F，G G，H H是任意的关系，则是任意的关系，则(1)(F(1)(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定理定理7.27.2的证明的证明(1)(1)任取任取 ，(F F G)G)H H t(t(F F G(t,y)HG(t,y)H)t(t(s s(FFG)G)H)H)t t s s(FFGGH)H)s(s(FF t t(GGH)H)s(s(FFGG H)H)F F(G G H)H)证明证明定理定理定理定理7.27.27.27.2定理定理7.27.2 设设F F，G G，H H是任意的关系，则是任意

23、的关系，则(1)(F(1)(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)任取任取 ，(F(F G)G)-1-1 FF G G t(t(FFG)G)t(t(FF-1-1GG-1-1)GG-1-1 F F-1-1定理定理定理定理7.37.37.37.3定理定理7.37.3 设设R R为为A A上的关系，则上的关系，则 R R I IA AI IA A R RR R.证明证明(1)(1)任取任取 ，R R I IA A t(t(R(t,y)IR(t,y)IA A)t(t(RtRty)y)RR(2)(2)R R R

24、yARyA RRIIA 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)F(1)F(G GH)H)F F GFGF H (2)(GH)H (2)(GH)F FG G F FHH F F(3)(3)F F(GH)GH)F F GFGF H (4)H (4)(GH)(GH)F F G G FFH H F F证明证明(3)(3)F F(GH)GH)t(t(F(t,y)GHF(t,y)GH)t(t(F(

25、t,y)G(t,y)HF(t,y)G(t,y)H)t(t(F(t,y)GF(t,y)G)()(F(t,y)HF(t,y)H)t(t(F(t,y)GF(t,y)G)t(t(F(t,y)HF(t,y)H)FF G G FF H H F F GFGF H H定理定理7.47.4的推论的推论由数学归纳法易证定理由数学归纳法易证定理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

26、 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)R R R R1 1 RRRR2 2 RRRRn n R R 定理定理定理定理7.57.57.57.5定理定理7.57.5 设设F F为关系，为关系，A,BA,B为集合，则为集合，则(1)F(AB)(1)F(AB)FAFB FAFB(2)FAB(2)FABFAFB FAFB(3)F(AB)(3)F(AB)FAFB FAFB(4)FAB(4)FAB FAFB FAFB 定理定理定理定理7.5(1)7.5(1)7.5(1)7.5(1)的证明的

27、证明的证明的证明(1)F(AB)(1)F(AB)FAFB FAFB 证明证明任取任取 ，F(AB)F(AB)F F x(ABx(AB)F (F (xAxBxAxB)(FxAFxA)()(FxBFxB)FFA A FFB B FFAFAFB B 所以有所以有 F(AB)F(AB)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+1n+1R Rn n R R说明说明q对于对于A A上的任何关系上的任何关系

28、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.R.R Rn n的计算的计算给定给定A A上的关系上的关系R R和自然数和自然数n n，怎样计算，怎样计算R Rn n呢？呢？若若n n是是0 0或或1 1，易求。下面考虑，易求。下面考虑n2n2的情况。的情况。如如R R是用集合给出，可以通过是用集合给出，可以通过

29、n-1n-1次右复合计次右复合计算得到算得到R Rn n .如如R R是用关系矩阵是用关系矩阵M M给出的，则给出的，则R Rn n的关系矩阵的关系矩阵是是M Mn n .与普通矩阵乘法不同，其中相加是逻辑与普通矩阵乘法不同，其中相加是逻辑加，即加，即1+11+11 1，1+01+00+10+11 1，0+00+00 0.R Rn n的计算的计算如如R R是用关系图是用关系图G G给出的，可由图给出的，可由图G G得到得到R Rn n的关系的关系图图G G.G G的顶点集与的顶点集与G G相同。考察相同。考察G G的每个顶点的每个顶点x xi i，如在，如在G G中从中从x xi i出发经出发

30、经n n步长的路径到达顶点步长的路径到达顶点x xj j，则在，则在G G中加一条从中加一条从x xi i到到x xj j的边。所有这样的的边。所有这样的边都找到后，就得到图边都找到后，就得到图GG.例例 7.8 7.8例例7.87.8 设设A Aa,b,c,da,b,c,d，R R,，求求R R的各次幂，用矩阵表示。的各次幂，用矩阵表示。解答解答例例 7.8 7.8例例 7.8 7.8因此因此M M4 4M M2 2，即，即R R4 4R R2 2.因此可以得到因此可以得到R R2 2R R4 4R R6 6R R3 3R R5 5R R7 7 幂运算的性质幂运算的性质定理定理7.67.6

31、设设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.定理定理7.77.7定理定理7.77.7 设设R R

32、是是A A上的关系，上的关系，m,nNm,nN，则，则(1)R(1)Rm m R Rn nR Rm+nm+n(2)(R(2)(Rm m)n nR Rmnmn证明证明(1)(1)对于任意给定的对于任意给定的mNmN,施归纳于施归纳于n.n.若若n=0n=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+0.m+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)R)(R Rm m

33、R Rn n)R R R Rm+n+1m+n+1，定理定理定理定理7.77.77.77.7定理定理7.77.7 设设R R是是A A上的关系，上的关系，m,nNm,nN，则，则(1)R(1)Rm m R Rn nR Rm+nm+n(2)(R(2)(Rm m)n nR Rmnmn证明证明(2)(2)对于任意给定的对于任意给定的mNmN,施归纳于施归纳于n.n.若若n=0n=0，则有，则有所以对一切所以对一切m,nNm,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，则有，则有(

34、R Rm m)n+1n+1(R Rm m)n n R Rm mR Rmn+mmn+m R Rm(n+1).m(n+1).定理定理定理定理7.87.87.87.8定理定理7.87.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=Rs+is+i，其中，其中p=t-sp=t-s (3)(3)令令S=RS=R0 0，R R1 1，R Rt-1t-1，则对

35、于任意的，则对于任意的qNqN有有 R Rq qSS.定理定理定理定理7.87.87.87.8定理定理7.87.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=Rs+is+i，其中，其中p=t-sp=t-s(3)(3)令令 =R =R0 0，R R1 1，R Rt-1t-1，则对于任意的，则对于任意的qNqN有有 R Rq q定理定理7.87.8的说明的说

36、明有穷集有穷集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的右复合运算下有下述变化规律：的右复合运算下有下述

37、变化规律：ababababdefdefdefdef对于对于a a或或b,b,每个元素的变化周期是每个元素的变化周期是2 2.对于对于d,e,fd,e,f,变变化周期是化周期是3 3.故有故有RmRm=Rm+6=Rm+6，6 6是是2 2和和3 3的最小公倍数。的最小公倍数。取取m=0,n=6m=0,n=6即可即可解解7.4 7.4 关系的性质关系的性质自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性自反性和反自反性自反性和反自反性定义定义7.117.11 设设R R为为A A上的关系，上的关系，(1)(1)若若 x(xAR)x(xAR)，则称，则称R R在在A A上是自反上

38、是自反的。的。(2)(2)若若 x(xAx(xA R)R)，则称，则称R R在在A A上是反上是反自反的。自反的。例例 7.10 7.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是反自反的。是反自反的。对称性和反对称性对称性

39、和反对称性对称性和反对称性对称性和反对称性定义定义7.127.12 设设R R为为A A上的关系，上的关系，（1 1）若）若 x x y(x,yARR)y(x,yARR)，则称，则称R R为为A A上对称的关系。上对称的关系。（2 2）若）若 x x y(x,yARRx=y)y(x,yARRx=y)，则称则称R R为为A A上的反对称关系。上的反对称关系。例子例子例如例如 A A上的全域关系上的全域关系E EA A,恒等关系恒等关系I IA A和空关系是和空关系是A A上对称关系。上对称关系。恒等关系恒等关系I IA A和空关系也是和空关系也是A A上的反对称关系。上的反对称关系。但全域关系但

40、全域关系E EA A一般不是一般不是A A上的反对称关系，上的反对称关系，除非除非A A为单元集或空集。为单元集或空集。例例 7.11 7.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是对称的但不是反对称的。是对称的但不是反对称的。

41、R R3 3是反对称的但不是对称的。是反对称的但不是对称的。R R4 4既不是对称的也不是反对称的。既不是对称的也不是反对称的。传递性传递性定义定义7.137.13 设设R R为为A A上的关系，若上的关系，若 x x y y z(x,y,zARRRz(x,y,zARRR)则称则称R R是是A A上的传递上的传递(transitivitytransitivity)关系。关系。例如例如 A A上全域关系上全域关系E EA A,恒等关系恒等关系I IA A和空关系都是和空关系都是A A上传递关系。上传递关系。小于等于关系，整除关系和包含关系也是传递关系。小于等于关系，整除关系和包含关系也是传递关系

42、。小于关系和真包含关系仍旧是相应集合上的传递关系。小于关系和真包含关系仍旧是相应集合上的传递关系。例例 7.12 7.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

43、上的关系，则上的关系，则（1 1）R R在在A A上自反当且仅当上自反当且仅当 I IA A R R（2 2）R R在在A A上反自反当且仅当上反自反当且仅当 RI RIA A（3 3）R R在在A A上对称当且仅当上对称当且仅当 R RR R-1-1（4 4）R R在在A A上反对称当且仅当上反对称当且仅当 RR RR-1-1 I IA A（5 5）R R在在A A上传递当且仅当上传递当且仅当 R R R R R R 定理定理7.9(1)7.9(1)的证明的证明（1 1）R R在在A A上自反当且仅当上自反当且仅当 I IA A R R.必要性必要性。任取任取，有，有 I IA A x,yA

44、 xx,yA xy y RR 所以所以 I IA A R R充分性充分性。任取任取x x，有，有 xAxA 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上反自反当且仅当上反自反当且仅当 RI RIA A .充分性充分性。任取任取x x，有，有 xAxA IIA A R(RIR(RIA A=)所以所以 R R在在A A上是反自反的上是反自反的.必要性必要性。用反证法。用反证法。假设假设RIRIA A，必存在必存在 RIRIA A.由于由于I IA A是是A A

45、上恒等关系，上恒等关系，可知可知 xAxA且且 R.R.这与这与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.必要性必要性。任取任取，有，有 R R R R(因为因为R R在在A A上对称上对称)R R-1-1 所以所以 R RR R-1-1 .充分性充分性。任取任取 ，由，由 R RR R-1-1 得得 RR RR-1-1 RR 所以所以 R R在在A A上是对称的。上是对称的。定理定理定理定理7.9(4)7.9(4)

46、7.9(4)7.9(4)的证明的证明的证明的证明（4 4）R R在在A A上反对称当且仅上反对称当且仅RRRR-1-1 I IA A.必要性必要性。任取任取，有，有 RR RR-1-1 R R R R-1-1 R RR R x xy y(R(R是反对称的是反对称的)I IA A所以所以 RR RR-1-1 I IA A .充分性充分性。任取任取,则有则有 R R RR R R RR-1-1 RRRR-1-1 IIA 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)的证明的证

47、明的证明的证明（5 5）R R在在A A上传递当且仅当上传递当且仅当 R R R R R R.必要性必要性。任取。任取，有，有 R R R R t(RR)t(RR)R R(因为因为R R在在A A上是传递的上是传递的)所以所以 R R R R R R.充分性充分性。任取。任取,R,R，则，则 RR RR RR R R R R(因为因为R R R R R)R)所以所以 R R在在A A上是传递的。上是传递的。例例 7.13 7.13例例7.137.13 设设A A是集合，是集合，R R1 1和和R R2 2是是A A上的关系，证明：上的关系，证明：(1)(1)若若R R1 1，R R2 2是自反

48、的和对称的，则是自反的和对称的，则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,从而

49、得到从而得到 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,有有(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是传递的

50、，则是传递的，则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上