离散数学关系.PPT

1、1第二章关系2在现实生活中, 集合与集合之间还存在着某种联系，如同学关系、朋友关系等。这些关系正是各门学科所要研究的主要内容。离散数学从集合出发，主要研究集合之间的关系。本章内容主要研究二元关系。3本章主要内容：n关系的基本概念n关系的表示方法 n关系的运算 n关系的性质 n关系的闭包n等价关系与划分n偏序关系42.1关系的基本概念为了讨论关系，首先引入有序对和笛卡儿积两个概念。为了讨论关系，首先引入有序对和笛卡儿积两个概念。由两个元素由两个元素a, b组成的集合组成的集合a, b中，中，a和和b是没有是没有次序的。有时需要考虑有次序的两个元素，所以需次序的。有时需要考虑有次序的两个元素，所以

2、需要由两个元素组成新的东西，并且两个元素是有次要由两个元素组成新的东西，并且两个元素是有次序的。序的。定义定义2.1两个元素a, b 有次序地放在一起，称为一个有有序对序对或序偶序偶，记为(a, b)。在有序对(a, b)中，a 称为第一元素第一元素，b称为第二元素第二元素。且(a1, b1) = (a2, b2)当且仅当a1 = a2 且b1 = b2。5定义定义2.2 设A, B 是两个集合，集合(x, y) | xA 且yB称为A 和B 的笛卡儿积笛卡儿积，也称卡氏积卡氏积，记为AB。用属于关系来表示就是：(x, y)AB 当且仅当xA 且yB和(x, y) AB 当且仅当x A或y B

3、。其中A 称为第一集合第一集合，B 称为第二集合第二集合。 6例例2.1 设A=1,2,3, B=a,b，求AB。由笛卡儿积的定义可知有A=A= 。又由有序对的性质可知，一般没有ABBA。AB也是一个集合，所以可以和另一集合C作笛卡儿积(AB)C，类似地有A(BC)。但是，一般没有(AB)C=A(BC)，且AB中的元素既不是A 中的元素，也不是B中的元素。7定理定理2.1 2.1 如果B1A1，B2A2，则B1B2 A1A2。8证明证明 对(x, y)B1B2，有xB1 且yB2，又因为B1 A1 ，B2 A2 ，则xA1 且yA2，所以(x, y)A1A2，即B1B2 A1A2。 9定理定理

4、2.2 A, B, C 是任意集合，则：(1) A(BC) = (AB)(AC)，(BC)A = (BA)(CA)。(2) A(BC) = (AB)(AC)，(BC)A = (BA)(CA)。(3) A(B -C) = (AB)- (AC)， (B -C)A = (BA) - (CA)。10证明证明 (1) 对(x, y)A(BC)，有xA 且yBC，因此xA 且(yB 或yC)，当y B 时，由xA 和yB 得(x, y)AB，当yC 时，由xA 和yC 得(x, y)AC，所以(x, y)(AB)(AC)，即A(BC) (AB)(AC)。因为A A，B BC 和C BC 得AB A(BC)

5、和AC A(BC)，因此(AB)(AC) A(BC)。因此A(BC) = (AB)(AC)成立。同理可证(BC)A = (BA)(CA)。11(2) 对(x,y)(AB)(AC)，有(x,y)AB且(x,y)AC，所以（xA且yB）且（xA且yC）。由yB且yC得yBC，由xA且yBC 得(x,y)A(BC)。因此(AB)(AC)A(BC)。因为A A，BC B和BC C，所以有A(BC) AB和A(BC) AC成立，因此A(BC) (AB)(AC)。因此A(BC)=(AB)(AC)。同理可证(BC)A=(BA)(CA)。12(3) 对(x,y)A(B-C)，有xA且yB-C，所以xA且yB且

6、yC。由xA且yB得(x,y)AB，由y C得(x,y) AC，所以(x,y)(AB)-(AC)。因此A(B-C) (AB)-(AC)。对(x,y)(AB)-(AC)，有(x,y)AB且(x,y) AC，由(x,y)AB 得xA且yB，由xA和(x,y) AC得y C，所以xA且yB且y C。由yB且y C得yB-C，所以(x,y)A(B-C)。因此(AB)-(AC) A(B-C)。因此A(B-C)=(AB)-(AC)。同理可证(B-C)A=(BA)-(CA)。13定义定义2.3 任给n2，n 个元素a1，, an 有次序地放在一起，称为一个n 元有序组元有序组，记为(a1，an)。为了体现n

7、 元有序组的次序，规定(a1，an)= (b1,，bn)当且仅当任给1in，都有ai = bi。n 元有序组可以组成集合，特别地有n 个集合的卡氏积。 14定义定义2.4 任给n2，A1，An 是n 个集合，集合(x1, , xn)| 任给1in，都有xiAi称为A1， An 的卡氏积，记为A1An。任给1in，Ai 称为这个卡氏积的第i 个集合。 15定义定义2.5 如果一个集合满足以下条件之一：（1）集合非空，且它的元素都是有序对；（2）集合是空集。则称该集合为一个二元关系二元关系，记作R。二元关系也可简称为关系关系。对于二元关系R，如果(x,y)R，可记作xRy；如果(x,y)R，则记作

8、xRy。设A，B为集合，AB的任何子集所定义的二元关系叫做从从A到到B的二元关系的二元关系，特别当A=B时则叫做A上的二元关系上的二元关系。16例例2.2 设集合A=0,1，B=1,2,3，那么R1=(0,2)，R2=AB，R3= ，R4=(0,1)等都是从A到B的二元关系，而R3和R4同时也是A上的二元关系。17定义定义2.6笛卡尔积A1A2 An的任意一个子集R称为A1，A2，An上的一个n元关系。当A1=A2= =An=A时，称R为A上的n元关系元关系。定义定义2.7 空集上定义一个二元关系，简称空关空关系系；若一个n元关系R本身是笛卡儿积A1A2 An ，则称R为全关系全关系，用符号U

9、A表示，即UA=(ai，aj)| ai，aj A为A上的全关系。 符号IA=(x,x)|x A为A上的恒等恒等关系关系 18例2.3 设A=1,2,3,4，下面各式定义的R都是A上的关系，试用列元素法表示R。(1) R=(x,y)|x是y的倍数(2) R=(x,y)|(x-y)2A(3) R=(x,y)|x/y是素数(4) R=(x,y)|xy19解解： (1) R=(4,4), (4,2), 4,1),(3,3),(3,1),(2,2),(2,1),(1,1)(2) R=(2,1),(3,2),(4,3),(3,1),(4,2),(2,4),(1,3),(3,4),(2,3),(1,2)(3

10、) R=(2,1),(3,1),(4,2)(4) R=UA-IA =(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)20定义定义2.8 RAB中所有的有序对的第一元素构成的集合称为R的定义域定义域，记为domR。形式化表示为：domR=x|x A,y B,使得(x,y)R。 RAB中所有有序对的第二元素构成的集合称为R的值域值域，记作ranR。形式化表示为ranR=y| yB ,xA,使得(x,y)R。21定义定义2.9 设R为二元关系，R的的逆关系逆关系，简称R的的逆逆，记作R-1,其中R-1=(y

11、, x)|(x, y)R。例例2.4 整除关系设A=2, 3, 4,8, B=3, 4, 5, 6, 7, 定义从A到B的二元关系R: (a, b)Ra整除b。则 R=(2, 4), (2, 6), (3, 3), (3, 6), (4, 4)，Dom R=2, 3, 4, Ran R=3, 4, 6，R-1=(4, 2), (6, 2), (3, 3), (6, 3), (4, 4) 22关系从本质上讲，仍是集合，只是这个集合中的元素都是以有序对的形式出现。既然关系是一个集合，那么集合的表示方法就可以用来表示关系，又因为关系是一个特殊的集合，其中的元素均以序偶的形式出现，除了可以用集合的表示

12、方法外，还可以用其他的表示方法。这里主要介绍如下几种表示方法。 2.2 关系的表示方法 231. 用列举法表示二元关系如果二元关系中的序偶个数是有限的，可以用列举法将其所包含的全部元素一一列举出来。例例2.5 设集合A=1,2,3，在集合A上定义的小于等于关系，LA=(a,b)|a,bA,ab，则LA=(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)。242. 用描述法表示二元关系用确定的条件表示某些序偶是否属于这个关系，并把这个条件写在大括号内表示关系的方法。 格式是： LR=(x,y)|xR且yR且xy。例例2.6设A=1，2，3，4，下面两式定义的R1和R2都是A上

13、的关系，分别列出R1与R2的元素如下： (1) R1 =(x,y)|x是y的倍数 (2) R2 =(x,y)|(x-y)2A25解解： (1) R1=(4,4),(4,2),(4,1),(3,3),(3,1),(2,2),(2,1),(1,1)(2) R2=(2,1),(1,2),(3,1),(1,3),(2,3),(3,2),(4,2),(2,4),(3,4),(4,3)263.用关系矩阵表示关系定义定义2.10设A和B是两个有限集A=a1, , am，B=b1, , bn，R是从A到B的二元关系，称mn阶矩阵MR=(rij)为R的关系矩阵，其中 rij = 1 ，当且仅当(ai, bj)R

14、 rij = 0 ，当且仅当(ai, bj) R27例例2.7 例2.5中的关系R的关系矩阵为：例例2.8 例2.6中的关系R1与R2的关系矩阵分别为：RM1001101111RM10110101001100012RM0110101111010110， 28 4.用关系图表示二元关系 设A=a1, , an，R是A上的二元关系。A中每个元素ai用一个点表示，称该点为顶点ai 。R的关系图是一个有向图，A中每个元素分别用一个顶点表示，当且仅当(ai,aj)R时，用弧或线段联结ai和aj； 若(ai,aj) R，则在ai处画一条自封闭的弧线,其中1i,jn。这样表示R中关系的图形，称为R的关系图关

15、系图，用GR表示。29例例2.9设集合A=1,2,3,4，在集合A上定义关系R=(1,1)，(1,2)，(2,3)，(2,4)，(4,2)，则R的关系图如图2.1所示。30n关系R的集合表达式、关系矩阵MR、关系图GR三者均可唯一相互确定31定义定义2.11 设关系R和S是从A到B的两个二元关系，对于aA，bB，定义：（1） RS： (a,b)RS (a,b)R或(a,b)S。（2） RS： (a,b)RS (a,b)R且(a,b)S。（3） R-S： (a,b)R-S (a,b)R且(a,b)S。（4） R： (a,b)R (a,b)AB-R。2.3 关系的运算 32例例2.10 设集合A=

16、a,b,c，集合B=1,2，且R和S是从A到B的两个二元关系， R=(a,1),(b,2),(c,1) S=(a,1),(b,1),(c,2) 则 RS=(a,1),(b,2),(c,1),(b,1),(c,2) RS=(a,1) R-S=(b,2),(c,1) R=ABR=(a,2),(b,1),(c,2)33因为关系可以用矩阵的形式表示，当我们用矩阵的形式求关系的并、交、补及对称差的运算时，可以用如下形式表示：MRS=MRMS （矩阵的对应分量做逻辑析取运算）MRS=MRMS （矩阵的对应分量做逻辑合取运算）MR-S=MRS=MRMS MR=MR （矩阵的对应分量做逻辑非运算）34例例2.

17、11对例2.10中的关系的运算采用矩阵的形式表示如下： 根据题意，关系R与S的关系矩阵分别表示为011001RM100101SM则SRSRMMM111101SRSRMMM000001SRSRMMM011000RRBARMMM10011035定理定理2.3 设关系R、S是集合A到集合B的二元关系，则有下列性质成立：(1) (R-1)-1=R, (R)=R (双重否定律)(2) (R)-1= (R-1), -1 = (可换性) (3) (RS)-1=R-1S-1 (分配律) (RS)-1=R-1S-1 (R-S)-1=R-1-S-1 (4) SR S-1 R-1 (单调性) SR S R (5)d

18、omR-1=ranR，ranR-1=domR(6) (AB)-1= BA 36证明证明：这里只证明（1）和（5）。(1)任取(x,y)，由逆的定义有(x,y)(R-1)-1 (y,x)R-1 (x,y)R。所以有(R-1)-1=R。(5)任取x, xdomR-1 y(x,y)R-1) y(y,x)R) xranR 所以有domR-1=ranR。同理可证 ranR-1=domR。37合成关系定义定义2.12设R是从集合A到集合B的二元关系，S是从集合B到集合C的二元关系，则R与S的复合关系复合关系（合成关系合成关系）RS是从A到C的关系，并且，RS=(x,z)|xA且zC且存在yB使得(x,y)

19、R,(y,z)S，运算“”称为复合复合运算运算或合成运算合成运算。38例例2.12 设A上的二元关系R=(x,y)|x,yA, x是y的父亲，S=(x,y)| x,yA, x是y的母亲 (1)说明RR，R-1 S1 ，R-1 S的含义。(2)表示以下关系：(x,y)|x,yA, y是x的外祖母(x,y)|x,yA, x是y的祖母39解解：(1) RR表示关系(x,y)|x,yA, x是 y的祖父 R-1 S1 表示关系(x,y)|x,yA, y是x的祖母 tA(x,t)R-1 (t,y)S-1)R-1 S表示空关系(2)(x,y)|x,yA, y是x的外祖母表示为S-1 S1 (x,y)|x,

20、yA, x是y的祖母表示为SR40例例2.13设Z是整数集合，R，S是Z到Z的两个关系：R=(x,3x)|xZ； S=(x,5x)|xZ。计算RS； SR；RR； SS； (RR)R； (RS)R。41解解RS=(x,15x)|xZ； SR=(x,15x)|xZ； RR=(x,9x)|xZ； SS=(x,25x)|xZ； (RR)R=(x,27x)|xZ； (RS)R=(x,45x)|xZ。42定理定理2.4 R为定义在集合A上的关系,则RIA=IAR=R43证明证明 任取(x,y)，有(x,y)RIAt(x,t)R且(t,y)IA) t(x,t)R且t=y) (x,y)R又有(x,y)R (

21、x,y)R且x,yA (x,y)R且(y,y)IA (x,y)RIA所以，RIA=R。同理可证 IAR=R。44定理定理2.5 设R1 A1A2 ，R2 A2A3 ， R3 A3A4，则(1)(R1R2)R3 = R1(R2R3) (2)(R1R2)-1=R2-1R1-1不满足交换律，即R1R2 R2R145证明： (1)任取(x,y), (x,y)(R1R2)R3(tA3) (使得(x,t) R1R2且(t,y)R3)(tA3)(sA2),使得(x,s)R1且(s,t)R2)且(t,y)R3)(tA3) (sA2)(使得(x,s)R1且(s,t)R2且(t,y)R3) (sA2)(使得(x,

22、s)R1且(tA3) (使得(s,t)R2且(t,y)R3) (sA2)(使得(x,s)R1且(s,y)R2R3) (x,y)R1(R2R3)所以(R1 R2) R3 =R1(R2R3)46由归纳法，任意n个关系的合成也是可结合的特别，当A1= A2 = =An+1 =A且R1= R2 = =Rn =R，合成关系R R R=Rn 是集合A上的一个关系。47（2） 任取(z,x)(R1R2)-1，则（x,z)R1R2，由“”的定义知，至少存一个yB，使得(x,y)R1，(y,z)R2，即(y,x)R-11，(z,y)R-12。由(z,y) R-12和(y,x) R-11 ，有(z,x) R-12

23、 R-11 。所以，(R1R2)-1 R-12 R-11 。反之，任取(z,x) R-12 R-11 ，由“”的定义知： 则至少存在一个yB，使得(z,y) R-12和(y,x) R-11 ，所以 (x,y)R1，(y,z)R2。由“”知(x,z)R1R2。即有(z,x)(R1R2)-1。所以， R-12 R-11 (R1R2)-1。由集合的性质知： (R1R2)-1= R-12 R-11 。48例例2.14 设A=a,b,c,d,e,f，R=(a,a),(a,b),(b,c),(c,d),(d,e),(e,f)。求Rn(n=1,2,3,4,)49解解： R1=R； R2=RR=(a,a),(

24、a,b),(a,c),(b,d),(c,e),(d,f)； R3=RRR=R2R=(a,a),(a,b),(a,c),(a,d),(b,e),(c,f)； R4=R3R=(a,a),(a,b),(a,c),(a,d),(a,e),(b,f)； R5=R4R=(a,a),(a,b),(a,c),(a,d),(a,e),(a,f)； R6=R5R=(a,a),(a,b),(a,c),(a,d),(a,e),(a,f)=R5； R7=R6R=R5； Rn=R5（n5）。50n幂集Rn的基数|Rn|并非随着n的增加而增加，而是呈递减趋势，而且，当 时，有An AiinRR1512.4关系的性质有了关系

25、的定义，可以来定义关系的某些特殊性质，这些性质在以后的讨论中，将起到极其重要的作用。本节主要讨论关系的五种性质，即自反性自反性、反自反性反自反性、对称性对称性、反对称性反对称性和传递性传递性。52自反、反自反定义定义2.14设R为集合A上的二元关系： （1） 若对任意的xA，都有(x,x)R，则称关系R在集合A上是自反自反的或称关系R具有自反性自反性； 否则，称R是非自反的。（2） 若对任意的xA，都有(x,x)R，则称关系R在集合A上是反自反反自反的或称关系R具有反自反自反性反性。自反关系：全关系、恒等关系、小于等于关系、整除关系、包含关系反自反关系：小于关系、真包含关系53例例2.15 设

26、A=1,2,3，R1=(1,1),(2,2)，R2=(1,1),(2,2),(3,3),(1,2)，R3=(1,3)，说明R1，R2，R3是否为A上自反的关系。54解解： 只有R2是A上自反的关系，因为IA R2； 而R1和R3都不是A上的自反关系，因为(3,3)R1 ，所以R1不是自反的，而(1,1),(2,2),(3,3)都不属于R3 ，因此R3不是自反的。关系R是否为自反关系是相对集合A来说的。同一个关系在不同的集合上具有不同的性质。55例例2.16设A=a,b,c,d，在集合A上定义如下三个二元关系R,S,T分别如下： R=(a,a),(a,d),(b,b),(b,d),(c,c),(

27、d,d)S=(a,b),(a,d),(b,c),(b,d),(c,a),(d,c)T=(a,a),(a,b),(a,c),(b,d),(c,a),(c,c),(d,c)说明R,S,T在A上的自反性与反自反性。56解解： 因为A中每个元素x，都有(x,x)R，所以R在A具备自反性。因为A中每个元素x，都有(x,x)S，所以S在A具备反自反性。因为A中有元素b，使(b,b)T，所以T在A上不具备自反性； 因为A中有元素a，使(a,a)T，所以T在A上也不具备反自反性。任何不是自反的关系未必一定是反自反的关系，反之亦然。即存在既不是自反的也不是反自反的关系。57定理定理2.6 设R是定义在集合A上的

28、二元关系，R是自反的当且仅当IA R。58证明证明 （1）必要性必要性 设R在A上是自反的，则IA R。根据恒等关系的定义，对任意的xA有(x,x)IA，又因为R在A上是自反的，即对于任意的xA有(x,x)R，因此IA R 。 （2）充分性）充分性 设IA R，则R在A上是自反的。对任意的xA有(x,x)IA，而IA R ，因此对任意的xA有(x,x)R，即R在A上是自反的。59定理定理2.7 设R是定义在集合A上的二元关系，R是反自反的当且仅当RIA=。60证明证明 （1）必要性必要性 设R在A上是反自反的，则RIA=。 假设RIA，比如存在（x，y）RIA，即（x，y）R且（x，y） IA

29、 ，也即（x，y）R且x=y，即（x，x）R，与R在A上是反自反的相矛盾。因此RIA=。充分性充分性 设RIA=，则R在A上是反自反的。对任意的xA，有 ( x, x) IA ，由于RIA=，因此( x, x)R，即R在A上是反自反的。61对称、反对称定义定义2.15 设R为A上的关系。 (1) 若对任意的x与y，都有x,yA且(x,y)R，则有(y,x)R，则称R为A上对称对称关系； 否则，称R是非对称的。(2) 若对任意的x与y，都有x,yA且当(x,y)R，(y,x)R时，有x=y，则称R为A上的反对称反对称关系。对称：全关系、恒等关系、空关系反对称：恒等关系、空关系62例例2.17 设

30、A=a,b,c，定义A上的二元关系如下： R=(a,a),(b,b)S=(a,a),(a,b),(b,a)T=(a,c),(a,b),(b,a)试说明R，S，T是否是A上的对称关系和反对称关系。63解解： 根据定义R上A上的对称关系与反对称关系。S是A上的对称关系。S不是A上的反对称关系，因为(a,b)与(b,a)都是S中的元素，但是ab，所以S不是A上的反对称关系。T既不是A上的对称关系，也不是A上的反对称关系。因为(a,c)是T中的元素，但是(c,a)不是T中的元素，因此不满足对称性，又因为(a,b)与(b,a)都是T中的元素，但是ab，因此也不满足反对称性。64定理定理2.8 设R是A上

31、的二元关系，R是对称的当且仅当R=R-1。65证明证明 (1)必要性必要性 设R是对称的，则R=R-1。(x，y)R(y，x)R(x，y) R-1 R=R-1。(2)充分性充分性 设R=R-1，则R是对称的。(x，y)R(y，x) R-1(y，x)R，因此R是对称的。 66定理定理2.9 设R是A上的二元关系，R是反对称的当且仅当RR-1IA。67证明证明 (1)必要性必要性 设R是反对称的，则RR-1IA。(x，y)RR-1(x，y)R且(x，y)R-1（x，y）R且(y，x)R，因为R是反对称的，根据反对称的定义，则x=y，因此(x，y)=(y，x)=(x，x) IA，所以RR-1IA。(

32、2)充分性充分性 设RR-1IA，则R是反对称的。(x，y)R且(y，x)R (x，y)R 且 (x，y)R-1 (x，y)RR-1因为RR-1IA，所以(x，y) IA，顾x=y，因此R是反对称的。68传递定义定义2.16 设R为A上的关系，若对任意的x，y，z有x,y,zA且当(x,y)R，(y,z)R时，有(x,z)R,则称R是A上的传递关系，否则称R是非传递关系。传递关系：全关系、空关系、小于、包含69例例2.18 设A=1,2,3，R1=(1,1)，R2=(1,3),(2,3)，R3=(1,1),(1,2),(2,3)，说明R1，R2，R3是否为集合A上传递的关系。70解解： 根据定

33、义2.16，R1，R2是A上传递的关系； 但R3不是传递的，因为(1,2)R3，(2,3)R3，而(1,3)R3，由传递关系的定义知R3不是传递的关系。71定理定理2.10 设R是集合A上的二元关系，则R是传递的当且仅当R.RR 72证明证明(1） 必要性必要性 设R是传递的，则R.RR。设(x，y)R.R，zA，使得(x，z) R且(z，y) R。因为R是传递的，所以(x，y) R，即有R.RR。(2)充分性充分性 设R.RR，则R是传递的。(x，y) R且(y，z) R。由复合关系的定义可得(x，z) R.R，因为R.RR，所以(x，z) R，即R是传递的。 732.4.2关系性质的证明在

34、二元关系中，除了对一个具体的关系判断它具有哪些性质外，更多的是针对一个抽象的关系，利用它的特点来证明它具有某个性质。由于关系性质的定义全部都是按“如果那么”来描述的，在证明这类问题时，一般采用按照定义证明的方法。这种证明问题的方法在于： 证明时不能仅仅利用题目所给的已知条件，还要同时结合定义中的“已知”，并且推出的并非整个定义，而是定义中的结论。另外，由于关系是特殊的集合，当用集合的手段来描述关系的性质时，其证明的方法也是按集合中的按定义证明方法来证。74例例2.19设R1，R2是定义在集合A上的两个关系，并且R1，R2具有传递性，则R1R2也具有传递性。75证明证明： 对任意x,yA，则若(

35、x,y) R1R2且(y,z) R1R2(x,y)R1且(x,y)R2且(y,z)R1且(y,z)R2(x,y)R1且(y,z)R1)且(x,y)R2 且(y,z)R2)又因为R1，R2具有传递性，因此(x,y)R1且(y,z)R1)且(x,y)R2且(y,z)R2)(x,z)R1且(x,z)R2 (x,z)R1R2根据定义2.16， R1R2具有传递性。76关系性质与集合运算运算性质自反性反自反性对称性反对称性传递性RSRSR-SR-1RS772.5关系的闭包对于在非空集合上定义的关系R不一定具备某种性质或某几种性质，而这些性质对研究某些具体的问题时又非常重要，这时就需要构造一个基于此关系的

36、新关系，使其具备所需要的性质，即往该关系中添加一些适量的元素以改变原有关系的性质，得到新的关系，使得新关系具有所需要的性质，但又不希望新关系与R相差太多，也就是说，要尽可能少地来添加有序对，满足这些要求的新关系就称为R的闭包。本节介绍关系的自自反反、对称对称和传递闭包传递闭包。78定义定义2.17设R是非空集合A上的关系，R的自反自反（对称对称或传递传递）闭包是A上的关系Rc，使得Rc满足以下条件： (1) Rc是自反自反的（对称对称的或传递传递的）； (2) R Rc； (3) 对A上任何包含R的自反（对称或传递）关系Rp有Rc Rp。一般将R的自反闭包记作r(R)，对称闭包记作s(R)，传

37、递闭包记作t(R)。79定理定理2.11 设R为定义在非空集合A上的二元关系，则有（1）r（R）= RIA（2）s（R）= RR-1（3）t（R）= RR2R380证明证明（1） 令R=RIA，则有 IA R IA ，而R IA =R，因此R是自反的。 R R IA ，而R IA =R，因此R R。 假设R是A上的任意自反关系并且R R，因为R是自反的，所以IAR，因此有R=RIA R。由自反闭包的定义，R=R IA是R的自反闭包，即r(R)=R=R IA 。 81（2）令R= RR-1(R) -1=(RR-1)-1= R-1(R-1) -1= R-1R= RR-1= R,因此R是对称的。R

38、RR-1，而RR-1= R，因此R R。设R是A上的任意对称关系并且R R，又(x，y) R-1(y，x) R(y，x) R，从而有R= RR-1 R。因此R是R的对称闭包，即s(R)= RR-1。（3）分两部分来证所要的结论。先证RR2R3 t（R）用数学归纳法来证，对任意自然数i，有Ri t（R）当i=1时，由传递闭包的定义，R1=R t（R）。假设当i=n时，Rn t（R）,下证Rn+1 t（R）。对任意的(x,y)Rn+1，存在cA，使得(x,c)Rn且(c,y)R，即存在cA，使得(x,c)t(R)且(c,y)t(R)，则(x,y)t(R)。即Rn+1 t(R)，因此，RR2R3 t

39、(R)。再证明t(R) RR2R3 。显然，有R RR2R3成立，下证 RR2R3是传递的。(x,y) RR2R3 t(R)且(y,z) RR2R3 tA，使得(x,y)Rt且sA，使得(y,z)Rs(x,z)RtRs=Rt+s RR2R3 (x,z) RR2R3由传递关系的定义， RR2R3是传递的。综上所述， RR2R3是包含R的传递关系。而R的传递闭包是包含R的最小传递关系，因此t(R) RR2R3 。即t(R)= RR2R3成立。83推论推论 设R是有限集合A上的关系，|A|=n，此时t（R）=RR2R3Rn有。 84例2.20设集合A=a, b, c，R是A上的二元关系，且R=(a,

40、 b), (b, c), (c, a)，求出关系R的自反、对称和传递闭包。85解： r(R)=RIA=(a,a),(b,b),(c,c),(a,b),(b,c),(c,a)s(R)=RR-1=(a,b),(b,c),(c,a),(b,a),(c,b),(a,c)R2=(a,c),(b,a),(c,b)R3=(a,a),(b,b),(c,c)R4=(a,b),(b,c),(c,a)因此，有R=R4R2=R5R3=R6t(R)=RR2R3 =RR2R3 =(a,a),(b,b),(c,c),(a,b),(b,c),(c,a),(a,c),(b,a),(c,b)86例2.21设集合A=a,b,c，R

41、是A上的二元关系，且R=(a,b),(b,c),(c,a)，用关系矩阵求关系R的自反、对称和传递闭包。87解 关系的关系矩阵为： 001100010RM0100011000011000100011000102RRRMMM111111111)(32RRRMMMRt10001000100110001001000110023RRRMMM88定理定理2.12 设R是非空集合A上的关系，（1）若R是自反的，则s(R)与t(R)也是自反的。（2）若R是对称的，则r(R)与t(R)也是对称的。（3）若R是传递的，则r(R)是传递的，而s(R)不一定传递。证明(1)若R是自反的，则有IA R。又因为Rs(R)

42、，且Rt(R)，所以IAs(R)且IA t(R)，因此s(R)与t(R)是自反的。(2)因为R对称，有R=R-1。由于r(R)=RIA ，而(r(R) -1=(R IA)-1= R-1 IA-1= RIA= r(R),因此r(R)对称。因为R对称，因此(Ri)-1=(R-1)i= Ri。由于t(R)= RR2R3,于是(t(R)-1=(RR2R3)-1= R-1(R2)-1(R3)-1= RR2R3=t(R)所以t(R)也对称。90(3)因为R传递，所以R.RR，而r(R)=RIA ，则有r(R).r(R)=( R IA)( R IA) =R.( R IA)IA. ( R IA) = R .R

43、R IA IA. ( R IA) = R .RR( R IA) RR( R IA) = R IA = r(R)即r(R)具有传递性。91下面举一个反例来说明s(R)不具备传递性。假设集合A=1,2,3，R=(1,2)是定义在集合A上的且具有传递性，而s(R)=(1,2),(2,1)却不具备传递性。92定理定理2.13 设R1,R2AA，且R1R2，则r(R1)r(R2) s(R1)s(R2)t(R1)t(R2) 93证明：(1)因为R1R2，因此R1IA R2IA ，所以r(R1)r(R2)。反证法：假设(x, y)r(R1), 但(x, y)r(R2)，则r(R1) (x, y)也是自反的，

44、即xy; 如果(x, y)R1，则(x, y)R2，那么(x, y)r(R2)，导致矛盾，因此(x, y) R1，所以R1 r(R1) (x, y)，那么r(R1)不是R1的自反闭包，矛盾。因此 (x, y) r(R2)。所以r(R1) r(R2)。94(2)因为R1R2，R2s(R2)，因此R1s(R2)。由s(R1)是包含R1的最小对称关系，所以s(R1)s(R2)。(3)因为R1R2，R2t(R2)，因此R1t(R2)。由t(R1)是包含R1的最小传递关系，所以t(R1)t(R2)。95定理定理2.14 设R1和R2是集合A上的关系，则以下各式成立。（1）r（ R1 R2 ）=r（ R1

45、 ）r（ R2 ）（2）s（ R1 R2 ）=s（ R1 ）s（ R2 ）（3）t（ R1 ）t（ R2 ）t（ R1 R2 ）96证明证明： （1） r(R1R2)=IA(R1 R2)=(IAR1)(IA R2)=r(R1)r(R2)（2） s(R1R2)=(R1 R2)(R1 R2)-1=(R1 R2)(R-11R-12)=(R1 R-11)(R2 R-12)=s(R1)s(R2)（3） 因为R1R1 R2 ， R2 R1 R2 ，所以t(R1) t(R1 R2)，t(R2) t(R1R2)，得出t(R1)t(R2) t(R1 R2)。一般地，t(R1)t(R2)t(R1 R2)。97例2

46、.22 设集合A=1,2,3，R1=(1,2),(2,3)，R2=(3,2)，有t(R1)=(1,2),(1,3),(2,3) t(R2)=(3,2)而t(R1R2)=(1,2),(1,3),(2,2),(2,3),(3,2),(3,3)t(R1)t(R2)=(1,2),(1,3),(2,3),(3,2)由此可见t(R1)t(R2)t(R1R2)。98定理定理2.15 设R是集合A上的关系，则（1）rs(R)=sr(R)；（2）rt(R)=tr(R)；（3）st(R)ts(R)。99证明证明 （1）)()(AIRsRsr1)()(AAIRIR)()(1AAIRIRAIRR1AIRs)()( R

47、rs100(2)()(AIRtRtriAiIR)(1 11iijAjIR111iAiijjIR1iAiIRAIRt)()(Rrt 101(3)若RS，则显然有s(R)s(S)，t(R)t(S)。根据对称闭包的定义，Rs(R)，于是t(R)ts(R)st(R) sts(R)若s(R)对称，则ts(R)也对称。 所以，由(1)可得sts(R)=ts(R)，即st(R) ts(R)。102例2.23设A=1,2，R=(1,2)，求st(R)与ts(R)。103例2.23设A=1,2，R=(1,2)，求st(R)与ts(R)。解： st(R)=s(t(R)=s(1,2)=(1,2),(2,1)ts(R

48、)=t(s(R)=t(1,2),(2,1)=(1,2),(2,1),(1,1),(2,2)1042.6等价关系与划分在日常生活中或者在数学等学科中，常常需要对某个集合上的元素按照某种方式进行分类，即集合的划分，这是一个非常重要的而且应用十分广泛的概念，集合的划分与一种重要的关系等价关系密切相关。利用等价关系，可以将集合中的元素分类，将一个大的集合分成若干个等价类，其主要意义在于它证实了应用抽象的一般原理的正确性，即在某方面等价的个体产生等价类，对全体的等价类进行分析常常比对全体本身进行分析更简单。1052.6.1等价关系定义定义2.18设R为非空集合A上的关系。如果R是自反的、对称的和传递的，

49、则称R为A上的等价等价关系关系。设R是一个等价关系，若(x，y)R，称x等价于等价于y，记做xy。 106例2.24以下关系是等价关系： (1) 集合A上的恒等关系、全域关系是等价关系。(2) 三角形的全等关系、三角形的相似关系是等价关系。(3) 在一个班级里“年龄相等”的关系是等价关系。107例2.25设关系R是定义在有理数集Q上的关系，并且(x,y)R，当且仅当x-y是整数，试证R是等价关系。108例2.25设关系R是定义在有理数集Q上的关系，并且(x,y)R，当且仅当x-y是整数，试证R是等价关系。证明证明： (1) 自反性自反性： 对任意一个有理数xQ，有x-x=0是整数，即对所有的有

50、理数有(x,x)R，因此R满足自反性。 (2) 对称性对称性： 假设x,yQ， 并且(x,y)R，即x-y是整数，则y-x=-(x-y)也是整数，即(y,x)R，因此R满足对称性。 (3) 传递性传递性： 假设x,y,zQ，并且(x,y)R，(y,z)R，即x-y与y-z都是整数，则x-z=x-y+y-z=(x-y)+(y-z)也是整数，即(x,z)R，因此R满足传递性。所以，R是等价关系。109例2.26 设集合 A=a,b,c,d,，R=(a,a)，(a,d)，(b,b)，(b,c)，(c,b)，(c,c) ，(d,a)，(d,d)。试证R是A上的等价关系。110证明： 写出关系R关系矩阵

51、如下：1001011001101001RM由关系矩阵可以看出，该矩阵的主对角线的元素都是1，即关系R满足自反性。该关系矩阵是对称的，即R满足对称性。求出R2的关系矩阵为：10010110011010012RM即R2的关系矩阵与R的关系矩阵相同，并且有R3，Rn都与R的关系矩阵相同，因此，t(R)=RR2R3Rn的关系矩阵也与R的关系矩阵相同，所以R是传递的。综上所述，R是A 上的等价关系。111例2.27设A=1,2,8, 定义A上的关系R=(x，y)|x，yA且xy(mod 3)，其中xy(mod 3)叫做x与y模3相等，即x除以3的余数与y除以3的余数相等。试证R为A上的等价关系。 112

52、证明证明： R=(1,4),(4,1),(1,7),(7,1),(2,5),(5,2),(2,8),(8,2),(3,6),(6,3)IA因为IAR，因此R满足自反性。对x,yA，若(x,y)R，即xy mod 3，则有yx mod 3，即(y,x)R，因此R满足对称性。对x,y,zA，若(x,y)R，(y,z)R，即xy mod 3，yz mod 3，则有xz mod 3，即(x,z)R，因此R满足传递性。综上所述，R是等价关系。113定理定理2.16 设R是定义在集合A上的关系，则R为等价关系R * R-1=R。 114定理定理2.16 设R是定义在集合A上的关系，则R为等价关系R * R

53、-1=R。 证明证明 (1)必要性必要性: R为等价关系 R * R-1=R令x, y是集合A中的任意元素，且(x,y)R, 则 (x,y)R (x,y)R 且(y,x)R (x,y)R且(y,x)R-1 (z)使得(x,y)R 且(z,y)R-1 (x,y)RR-1 于是, RR R-1. 另一方面， (x,y)RR-1 z使得(x,z) R且(z,y)R-1 (x,z) R且(y,z)R (x,z) R且(z,y)R (x,y) R因此, R R-1 R. 综上可知, 必要性得证.(2)充分性充分性: 由假设R R-1=R可知, (x,y) R (x,y) R R-1 z使得(x,z) R

54、且(z,y)R-1 z使得(x,z) R且(z,y)R由此可推知R为对称和传递时方使上式成立, 从而R也必为自反, 充分性得证。115定义定义2.19设设R为集合A上的等价关系，对集合A中的任意元素a,称A中与a等价的全体元素所组成的集合为由a生成的等价类，记作aR。即aR=b|bA且(a,b)R,a称为这一等价类的代表元代表元或生成元生成元。116例2.28设A=1,2,8,如下定义A上的二元关系R=(x，y)|x，yA且xy(mod 3)，其中xy(mod 3)叫做x与y模3相等，求R的等价类。117解 1R=1，4，7 2R=2，5，8 3R=3，6 4R=1，4，7 5R=2，5，8

55、6R=3，6 7R=1，4，7 8R=2，5，8即1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,6所以不同的等价类只有3个1R、2R 、3R。 118定义定义2.20设R为非空集合A上的等价关系，以R的所有等价类作为元素的集合称为A关于R的商集商集，记做A/R，即A/R=aR|aAA/R的基数（即不同类的个数）称为R的秩秩。 119例2.29 在例2.28中的商集为A/R=1,4,7,2,5,8,3,6,关系R的秩为3。120例2.30 整数集Z上模m的等价关系R=(x,y)|x,yZ且xy(mod) m其等价类是： 0R=km|kZ1R=km+1|kZm-1R=km+(m-1)

56、|kZ因此商集为Z/R=0R，1R，m-1R121定理定理2.17 设R为非空集合A上的等价关系,则：（1） aA，aR是A的非空子集。（2） a,bA，如果(a,b)R，则aR=bR。（3） a,bA，如果(a,b)R，则aRbR=。（4）aR|aA=A 122证明证明 （1）aA，由R的自反性，有(a,a)R，所以aaR，因此aR非空；再由等价类定义，aRA。（2）对于xaR，则(a,x)R ，又因为(a,b)R ，由R的对称性与传递性，可得(b,x)R ，于是xbR，因此aRbR。同样可证bRaR 所以aR=bR（3）反证法：如果有元素xaRbR，则(a,x)R且(b,x)R ，由R的对

57、称性和传递性，可得(a,b)R ，与(a,b)R矛盾，所以aR与bR不交。123 (4)先证aR|aAA 任取b，baR|aA a使得aA且baR) bA (因为aR A)aR|aAA 再证 AaR|aA 任取b， bA bbR baR |aA AaR|aA成立。综上所述得aR|aA=A。1242.6.2 集合的划分定义定义2.21 ：设A是任意非空集合， A1，A2，Am是集合A的子集,满足：（1）Ai (i=1,2,m)；（2） AiAj= (ij)； （3）A1A2 Am=A。则集合族=A1，A2，Am为A的一个划分划分，而A1，A2，Am为这个划分的划分块划分块。125例例2.31设集

58、合A=1,2,3,4,则1=1,2,3,4, 2=1,2,3,4, 3=1,2,3,4, 4=1,2,3,4均为对集合A的划分。例例2.32设集合A=a,b,c,d，判断下列子集是否是A的划分。(1) a,b,c,d,b,d(2) a,b,c,d(3) a,b,c,(4) a,b,c,d(5) a,b,c,d解： 根据划分的定义有（1），（3）不是A的划分，（2），（4），（5）是A的划分。126细分、真细分定义定义2.22设1=A1,A2,An和2=B1,B2,Bm是集合S的两种划分,如果1中的每个Ai都是2中某个 Bj的子集,则称划分1是划分2的一个细分细分。如果1是2的细分，且1中至少有

59、一个Ai是某个Bj的真子集，则称1是2的真细分真细分。127例例2.33 设集合A=1,2,3,4，则在例2.31中： (1) 划分1=1,2,3,4是2=1，2,3,4的细分，也是真细分。（2） 划分3=1,2,3,4是4=1,2,3,4的细分，也是真细分。对集合A=1,2,3,4，有1=1,2,3,4是对集合A的任意一个划分的细分，而对集合A的任意一个划分都是划分4=1,2,3,4的细分。128最大划分、最小划分、交叉划分定义定义2.23设A是非空集合，G=a|aA称为A的最大划分最大划分，S=A称为A的最小最小划分划分。例例2.34 在例2.31中的划分1=1,2,3,4是对集合A的最大

60、划分，划分4=1,2,3,4是对集合A的最小划分。129最大划分、最小划分、交叉划分定义定义2.24设1=A1,A2,An和2=B1,B2,Bm是集合S的两种划分，称AiBj|AiBj ,1i n,1j m为1和2的交叉划分交叉划分。例例2.35设集合A=1,2,3,4,则在例2.31中的划分2=1,2,3,4与划分3=1,2,3,4的交叉划分为23=1,2,3,4。130定理定理2.18 ：设1=A1,A2,An和2=B1,B2,Bm是集合S的两种划分，则其交叉划分= 12也是S的一个划分。131证明证明 交叉划分= AiBj|AiBj ,1in,1jm 。在中任取两个元素AiBh，AjBk