离散数学关系课件

章

2021/5/91在现实生活中,集合与集合之间还存在着某种联系，如同学关系、朋友关系等。这些关系正是各门学科所要研究的主要内容。离散数学从集合出发，主要研究集合之间的关系。本章内容主要研究二元关系。2021/5/92本章主要内容：关系的基本概念关系的表示方法关系的运算关系的性质关系的闭包等价关系与划分偏序关系2021/5/932.1关系的基本概念为了讨论关系，首先引入有序对和笛卡儿积两个概念。由两个元素a,b组成的集合{a,b}中，a和b是没有次序的。有时需要考虑有次序的两个元素，所以需要由两个元素组成新的东西，并且两个元素是有次序的。定义2.1两个元素a,b有次序地放在一起，称为一个有序对或序偶，记为(a,b)。在有序对(a,b)中，a称为第一元素，b称为第二元素。且(a1,b1)=(a2,b2)当且仅当a1=a2

且b1=b2。2021/5/94定义2.2

设A,B

是两个集合，集合{(x,y)|x∈A

且y∈B}称为A

和B

的笛卡儿积，也称卡氏积，记为A×B。用属于关系来表示就是：(x,y)∈A×B

当且仅当x∈A

且y∈B和(x,y)∉A×B

当且仅当x∉A或y∉B。其中A

称为第一集合，B

称为第二集合。2021/5/95例2.1

设A={1,2,3},B={a,b}，求A×B。由笛卡儿积的定义可知有A×=×A=

。又由有序对的性质可知，一般没有A×B≠B×A。A×B也是一个集合，所以可以和另一集合C作笛卡儿积(A×B)×C，类似地有A×(B×C)。但是，一般没有(A×B)×C=A×(B×C)，且A×B中的元素既不是A中的元素，也不是B中的元素。2021/5/96定理2.1如果B1A1，B2A2，则B1×B2

A1×A2。2021/5/97证明对(x,y)∈B1×B2，有x∈B1

且y∈B2，又因为B1

A1

，B2

A2

，则x∈A1

且y∈A2，所以(x,y)∈A1×A2，即B1×B2

A1×A2。2021/5/98定理2.2

A,B,C

是任意集合，则：(1)A×(B∪C)=(A×B)∪(A×C)，(B∪C)×A=(B×A)∪(C×A)。(2)A×(B∩C)=(A×B)∩(A×C)，(B∩C)×A=(B×A)∩(C×A)。(3)A×(B-C)=(A×B)-(A×C)，

(B-C)×A=(B×A)-(C×A)。2021/5/99证明

(1)对(x,y)∈A×(B∪C)，有x∈A

且y∈B∪C，因此x∈A且(y∈B

或y∈C)，当y

∈B时，由x∈A

和y∈B

得(x,y)∈A×B，当y∈C

时，由x∈A

和y∈C得(x,y)∈A×C，所以(x,y)∈(A×B)∪(A×C)，即A×(B∪C)⊆(A×B)∪(A×C)。因为A⊆A，B⊆B∪C

和C⊆B∪C

得A×B⊆A×(B∪C)和A×C⊆A×(B∪C)，因此(A×B)∪(A×C)⊆A×(B∪C)。因此A×(B∪C)=(A×B)∪(A×C)成立。同理可证(B∪C)×A=(B×A)∪(C×A)。2021/5/910(2)对(x,y)∈(A×B)∩(A×C)，有(x,y)∈A×B且(x,y)∈A×C，所以（x∈A且y∈B）且（x∈A且y∈C）。由y∈B且y∈C得y∈B∩C，由x∈A且y∈B∩C得(x,y)∈A×(B∩C)。因此(A×B)∩(A×C)A×(B∩C)。因为A⊆A，B∩C⊆B和B∩C⊆C，所以有A×(B∩C)⊆A×B和A×(B∩C)⊆A×C成立，因此A×(B∩C)⊆(A×B)∩(A×C)。因此A×(B∩C)=(A×B)∩(A×C)。同理可证(B∩C)×A=(B×A)∩(C×A)。2021/5/911(3)对(x,y)∈A×(B-C)，有x∈A且y∈B-C，所以x∈A且y∈B且yC。由x∈A且y∈B得(x,y)∈A×B，由y

C得(x,y)A×C，所以(x,y)∈(A×B)-(A×C)。因此A×(B-C)⊆(A×B)-(A×C)。对(x,y)∈(A×B)-(A×C)，有(x,y)∈A×B且(x,y)A×C，由(x,y)∈A×B得x∈A且y∈B，由x∈A和(x,y)A×C得y

C，所以x∈A且y∈B且yC。由y∈B且y

C得y∈B-C，所以(x,y)∈A×(B-C)。因此(A×B)-(A×C)⊆A×(B-C)。因此A×(B-C)=(A×B)-(A×C)。同理可证(B-C)×A=(B×A)-(C×A)。2021/5/912定义2.3

任给n≥2，n个元素a1，…,an

有次序地放在一起，称为一个n元有序组，记为(a1，…，an)。为了体现n元有序组的次序，规定(a1，…，an)=

(b1,，…，bn)当且仅当任给1≤i≤n，都有ai=bi。n元有序组可以组成集合，特别地有n个集合的卡氏积。2021/5/913定义2.4

任给n≥2，A1，…，An

是n个集合，集合{(x1,⋯,xn)|任给1≤i≤n，都有xi∈Ai}称为A1，…，An

的卡氏积，记为A1×…×An。任给1≤i≤n，Ai

称为这个卡氏积的第i

个集合。2021/5/914定义2.5

如果一个集合满足以下条件之一：（1）集合非空，且它的元素都是有序对；（2）集合是空集。则称该集合为一个二元关系，记作R。二元关系也可简称为关系。对于二元关系R，如果(x,y)∈R，可记作xRy；如果(x,y)R，则记作xRy。设A，B为集合，A×B的任何子集所定义的二元关系叫做从A到B的二元关系，特别当A=B时则叫做A上的二元关系。2021/5/915例2.2

设集合A={0,1}，B={1,2,3}，那么R1={(0,2)}，R2=A×B，R3=，R4={(0,1)}等都是从A到B的二元关系，而R3和R4同时也是A上的二元关系。2021/5/916定义2.6笛卡尔积A1×A2×…×An的任意一个子集R称为A1，A2，…，An上的一个n元关系。当A1=A2=…=An=A时，称R为A上的n元关系。定义2.7

空集上定义一个二元关系，简称空关系；若一个n元关系R本身是笛卡儿积A1×A2×…×An

，则称R为全关系，用符号UA表示，即UA={(ai，aj)|ai，aj∈A}为A上的全关系。符号IA={(x,x)|x∈A}为A上的恒等关系

2021/5/917例2.3设A={1,2,3,4}，下面各式定义的R都是A上的关系，试用列元素法表示R。(1)R={(x,y)|x是y的倍数}(2)R={(x,y)|(x-y)2∈A}(3)R={(x,y)|x/y是素数}(4)R={(x,y)|x≠y}2021/5/918解：(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)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)}2021/5/919定义2.8RA×B中所有的有序对的第一元素构成的集合称为R的定义域，记为domR。形式化表示为：domR={x|x∈A,y∈B,使得(x,y)∈R}。RA×B中所有有序对的第二元素构成的集合称为R的值域，记作ranR。形式化表示为ranR={y|y∈B,x∈A,使得(x,y)∈R}。2021/5/920定义2.9

设R为二元关系，R的逆关系，简称R的逆，记作R-1,其中R-1={(y,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)}，DomR={2,3,4},RanR={3,4,6}，R-1={(4,2),(6,2),(3,3),(6,3),(4,4)}2021/5/921关系从本质上讲，仍是集合，只是这个集合中的元素都是以有序对的形式出现。既然关系是一个集合，那么集合的表示方法就可以用来表示关系，又因为关系是一个特殊的集合，其中的元素均以序偶的形式出现，除了可以用集合的表示方法外，还可以用其他的表示方法。这里主要介绍如下几种表示方法。2.2关系的表示方法2021/5/9221.用列举法表示二元关系如果二元关系中的序偶个数是有限的，可以用列举法将其所包含的全部元素一一列举出来。例2.5

设集合A={1,2,3}，在集合A上定义的小于等于关系，LA={(a,b)|a,b∈A,a≤b}，则LA={(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)}。2021/5/9232.用描述法表示二元关系用确定的条件表示某些序偶是否属于这个关系，并把这个条件写在大括号内表示关系的方法。格式是：LR={(x,y)|x∈R且y∈R且x≥y}。例2.6设A={1，2，3，4}，下面两式定义的R1和R2都是A上的关系，分别列出R1与R2的元素如下：

(1)R1={(x,y)|x是y的倍数}(2)R2={(x,y)|(x-y)2∈A}2021/5/924解：(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)}2021/5/9253.用关系矩阵表示关系定义2.10设A和B是两个有限集A={a1,…,am}，B={b1,…,bn}，R是从A到B的二元关系，称mn阶矩阵MR=(rij)为R的关系矩阵，其中

rij=1

，当且仅当(ai,bj)R

rij=0，当且仅当(ai,bj)R2021/5/926例2.7

例2.5中的关系R的关系矩阵为：例2.8

例2.6中的关系R1与R2的关系矩阵分别为：，2021/5/9274.用关系图表示二元关系设A={a1,……,an}，R是A上的二元关系。A中每个元素ai用一个点表示，称该点为顶点ai

。R的关系图是一个有向图，A中每个元素分别用一个顶点表示，当且仅当(ai,aj)∈R时，用弧或线段联结ai和aj；若(ai,aj)∈R，则在ai处画一条自封闭的弧线,其中1≤i,j≤n。这样表示R中关系的图形，称为R的关系图，用GR表示。2021/5/928例2.9设集合A={1,2,3,4}，在集合A上定义关系R={(1,1)，(1,2)，(2,3)，(2,4)，(4,2)}，则R的关系图如图2.1所示。2021/5/929关系R的集合表达式、关系矩阵MR、关系图GR三者均可唯一相互确定2021/5/930定义2.11

设关系R和S是从A到B的两个二元关系，对于aA，bB，定义：（1）R∪S：(a,b)∈R∪S(a,b)∈R或(a,b)∈S。（2）R∩S：(a,b)∈R∩S(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)∈A×B-R。2.3关系的运算2021/5/931例2.10

设集合A={a,b,c}，集合B={1,2}，且R和S是从A到B的两个二元关系，

R={(a,1),(b,2),(c,1)}

S={(a,1),(b,1),(c,2)}

则

R∪S={(a,1),(b,2),(c,1),(b,1),(c,2)}

R∩S={(a,1)}

R-S={(b,2),(c,1)}

R=A×B－R={(a,2),(b,1),(c,2)}2021/5/932因为关系可以用矩阵的形式表示，当我们用矩阵的形式求关系的并、交、补及对称差的运算时，可以用如下形式表示：MR∪S=MRMS

（矩阵的对应分量做逻辑析取运算）MR∩S=MRMS

（矩阵的对应分量做逻辑合取运算）MR-S=MR∩S=MRMS

MR=MR

（矩阵的对应分量做逻辑非运算）2021/5/933例2.11对例2.10中的关系的运算采用矩阵的形式表示如下：根据题意，关系R与S的关系矩阵分别表示为则2021/5/934定理2.3

设关系R、S是集合A到集合B的二元关系，则有下列性质成立：

(1)(R-1)-1=R,(R)=R(双重否定律)

(2)(R)-1=(R-1),-1=(可换性)(3)(R∪S)-1=R-1∪S-1(分配律)(R∩S)-1=R-1∩S-1(R-S)-1=R-1-S-1 (4)SRS-1

R-1(单调性) SRS

R (5)domR-1=ranR，ranR-1=domR (6)(AB)-1=BA2021/5/935证明：这里只证明（1）和（5）。(1)任取(x,y)，由逆的定义有(x,y)∈(R-1)-1

(y,x)∈R-1

(x,y)∈R。

所以有(R-1)-1=R。(5)任取x,x∈domR-1

y((x,y)∈R-1)

y((y,x)∈R))

x∈ranR

所以有domR-1=ranR。

同理可证ranR-1=domR。2021/5/936合成关系定义2.12设R是从集合A到集合B的二元关系，S是从集合B到集合C的二元关系，则R与S的复合关系（合成关系）R·S是从A到C的关系，并且，R·S={(x,z)|x∈A且z∈C且存在y∈B使得(x,y)∈R,(y,z)∈S}，运算“·”称为复合运算或合成运算。2021/5/937例2.12

设A上的二元关系R={(x,y)|x,yA,x是y的父亲}，S={(x,y)|x,yA,x是y的母亲}

(1)说明R•R，R-1

•S–1

，R-1•S的含义。(2)表示以下关系：

{(x,y)|x,yA,y是x的外祖母}

{(x,y)|x,yA,x是y的祖母}2021/5/938解：

(1)R•R表示关系{(x,y)|x,yA,x是y的祖父}

R-1

•S–1

表示关系{(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

•S–1

{(x,y)|x,yA,x是y的祖母}表示为S•R2021/5/939例2.13设Z是整数集合，R，S是Z到Z的两个关系：R={(x,3x)|x∈Z}；S={(x,5x)|x∈Z}。计算R·S；S·R；R·R；S·S；(R·R)·R；(R·S)·R。2021/5/940解R·S={(x,15x)|x∈Z}；S·R={(x,15x)|x∈Z}；R·R={(x,9x)|x∈Z}；S·S={(x,25x)|x∈Z}；(R·R)·R={(x,27x)|x∈Z}；(R·S)·R={(x,45x)|x∈Z}。2021/5/941定理2.4R为定义在集合A上的关系,则R·IA=IA·R=R2021/5/942证明任取(x,y)，有(x,y)∈R·IAt((x,t)∈R且(t,y)∈IA)t((x,t)∈R且t=y)(x,y)∈R又有(x,y)∈R(x,y)∈R且x,y∈A(x,y)∈R且(y,y)∈IA(x,y)∈R·IA所以，R·IA=R。同理可证IA·R=R。2021/5/943定理2.5

设R1A1A2

，R2

A2A3

，R3A3A4，则

(1)(R1•R2)•R3=R1•(R2•R3)

(2)(R1•R2)-1=R2-1•R1-1不满足交换律，即R1•R2

R2•R12021/5/944证明：(1)任取(x,y),(x,y)∈(R1•R2)•R3(t∈A3)(使得(x,t)∈R1•R2且(t,y)∈R3)(t∈A3)(((s∈A2),使得(x,s)∈R1且(s,t)∈R2)且(t,y)∈R3)(t∈A3)(s∈A2)(使得(x,s)∈R1且(s,t)∈R2且(t,y)∈R3)

(s∈A2)(使得(x,s)∈R1且(t∈A3)(使得(s,t)∈R2且(t,y)∈R3))(s∈A2)(使得(x,s)∈R1且(s,y)∈R2•R3)(x,y)∈R1•(R2•R3)

所以(R1•R2)•R3=R1•(R2•R3)2021/5/945由归纳法，任意n个关系的合成也是可结合的特别，当A1=A2=…=An+1=A且R1=R2=…=Rn=R，合成关系R•R•…•R=Rn

是集合A上的一个关系。2021/5/946（2）任取(z,x)∈(R1·R2)-1，则（x,z)∈R1·R2，由“·”的定义知，至少存一个y∈B，使得(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·R-11

。所以，(R1·R2)-1R-12·R-11

。反之，任取(z,x)R-12·R-11

，由“·”的定义知：则至少存在一个y∈B，使得(z,y)∈R-12和(y,x)∈R-11

，所以(x,y)∈R1，(y,z)∈R2。由“·”知(x,z)∈R1·R2。即有(z,x)∈(R1·R2)-1。所以，R-12·R-11(R1·R2)-1。由集合的性质知：(R1·R2)-1=R-12·R-11

。2021/5/947例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,……)2021/5/948解：

R1=R；R2=R·R={(a,a),(a,b),(a,c),(b,d),(c,e),(d,f)}；R3=R·R·R=R2·R={(a,a),(a,b),(a,c),(a,d),(b,e),(c,f)}；R4=R3·R={(a,a),(a,b),(a,c),(a,d),(a,e),(b,f)}；R5=R4·R={(a,a),(a,b),(a,c),(a,d),(a,e),(a,f)}；R6=R5·R={(a,a),(a,b),(a,c),(a,d),(a,e),(a,f)}=R5；R7=R6·R=R5；…Rn=R5（n＞5）。2021/5/949幂集Rn的基数|Rn|并非随着n的增加而增加，而是呈递减趋势，而且，当时，有

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

设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上自反的关系。2021/5/953解：只有R2是A上自反的关系，因为IA

R2；而R1和R3都不是A上的自反关系，因为(3,3)R1

，所以R1不是自反的，而(1,1),(2,2),(3,3)都不属于R3

，因此R3不是自反的。关系R是否为自反关系是相对集合A来说的。同一个关系在不同的集合上具有不同的性质。2021/5/954例2.16设A={a,b,c,d}，在集合A上定义如下三个二元关系R,S,T分别如下：R={(a,a),(a,d),(b,b),(b,d),(c,c),(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上的自反性与反自反性。2021/5/955解：因为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上也不具备反自反性。任何不是自反的关系未必一定是反自反的关系，反之亦然。即存在既不是自反的也不是反自反的关系。2021/5/956定理2.6

设R是定义在集合A上的二元关系，R是自反的当且仅当IA

R。2021/5/957证明（1）必要性设R在A上是自反的，则IA

R。根据恒等关系的定义，对任意的x∈A有(x,x)∈IA，又因为R在A上是自反的，即对于任意的x∈A有(x,x)∈R，因此IA

R。

（2）充分性设IA

R，则R在A上是自反的。对任意的x∈A有(x,x)∈IA，而IA

R，因此对任意的x∈A有(x,x)∈R，即R在A上是自反的。2021/5/958定理2.7设R是定义在集合A上的二元关系，R是反自反的当且仅当R∩IA=。2021/5/959证明（1）必要性设R在A上是反自反的，则R∩IA=。假设R∩IA，比如存在（x，y）R∩IA，即（x，y）R且（x，y）

IA

，也即（x，y）R且x=y，即（x，x）R，与R在A上是反自反的相矛盾。因此R∩IA=。充分性设R∩IA=，则R在A上是反自反的。对任意的xA，有(x,x)IA

，由于R∩IA=，因此(x,x)R，即R在A上是反自反的。2021/5/960对称、反对称定义2.15设R为A上的关系。(1)若对任意的x与y，都有x,y∈A且(x,y)∈R，则有(y,x)∈R，则称R为A上对称关系；否则，称R是非对称的。(2)若对任意的x与y，都有x,y∈A且当(x,y)∈R，(y,x)∈R时，有x=y，则称R为A上的反对称关系。对称：全关系、恒等关系、空关系反对称：恒等关系、空关系2021/5/961例2.17

设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上的对称关系和反对称关系。2021/5/962解：根据定义R上A上的对称关系与反对称关系。S是A上的对称关系。S不是A上的反对称关系，因为(a,b)与(b,a)都是S中的元素，但是a≠b，所以S不是A上的反对称关系。T既不是A上的对称关系，也不是A上的反对称关系。因为(a,c)是T中的元素，但是(c,a)不是T中的元素，因此不满足对称性，又因为(a,b)与(b,a)都是T中的元素，但是a≠b，因此也不满足反对称性。2021/5/963定理2.8

设R是A上的二元关系，R是对称的当且仅当R=R-1。2021/5/964证明

(1)必要性设R是对称的，则R=R-1。(x，y)R(y，x)R(x，y)R-1R=R-1。(2)充分性设R=R-1，则R是对称的。(x，y)R(y，x)R-1(y，x)R，因此R是对称的。2021/5/965定理2.9

设R是A上的二元关系，R是反对称的当且仅当R∩R-1IA。2021/5/966证明

(1)必要性设R是反对称的，则R∩R-1IA。(x，y)R∩R-1(x，y)R且(x，y)R-1（x，y）R且(y，x)R，因为R是反对称的，根据反对称的定义，则x=y，因此(x，y)=(y，x)=(x，x)IA，所以R∩R-1IA。(2)充分性设R∩R-1IA，则R是反对称的。(x，y)R且(y，x)R(x，y)R且(x，y)R-1(x，y)R∩R-1因为R∩R-1IA，所以(x，y)IA，顾x=y，因此R是反对称的。2021/5/967传递定义2.16

设R为A上的关系，若对任意的x，y，z有x,y,z∈A且当(x,y)∈R，(y,z)∈R时，有(x,z)∈R,则称R是A上的传递关系，否则称R是非传递关系。传递关系：全关系、空关系、小于、包含2021/5/968例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上传递的关系。2021/5/969解：根据定义2.16，R1，R2是A上传递的关系；但R3不是传递的，因为(1,2)∈R3，(2,3)∈R3，而(1,3)R3，由传递关系的定义知R3不是传递的关系。2021/5/970定理2.10

设R是集合A上的二元关系，则R是传递的当且仅当R.RR2021/5/971证明(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是传递的。2021/5/9722.4.2关系性质的证明在二元关系中，除了对一个具体的关系判断它具有哪些性质外，更多的是针对一个抽象的关系，利用它的特点来证明它具有某个性质。由于关系性质的定义全部都是按“如果……那么……”来描述的，在证明这类问题时，一般采用按照定义证明的方法。这种证明问题的方法在于：证明时不能仅仅利用题目所给的已知条件，还要同时结合定义中的“已知”，并且推出的并非整个定义，而是定义中的结论。另外，由于关系是特殊的集合，当用集合的手段来描述关系的性质时，其证明的方法也是按集合中的按定义证明方法来证。2021/5/973例2.19设R1，R2是定义在集合A上的两个关系，并且R1，R2具有传递性，则R1∩R2也具有传递性。2021/5/974证明：对任意x,y∈A，则若(x,y)∈R1∩R2且(y,z)∈R1∩R2(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)∈R1∩R2根据定义2.16，R1∩R2具有传递性。2021/5/975关系性质与集合运算运算性质自反性反自反性对称性反对称性传递性R∪S√√√××R∩S√√√√√R-S×√√√×R-1√√√√√R•S√××××2021/5/9762.5关系的闭包对于在非空集合上定义的关系R不一定具备某种性质或某几种性质，而这些性质对研究某些具体的问题时又非常重要，这时就需要构造一个基于此关系的新关系，使其具备所需要的性质，即往该关系中添加一些适量的元素以改变原有关系的性质，得到新的关系，使得新关系具有所需要的性质，但又不希望新关系与R相差太多，也就是说，要尽可能少地来添加有序对，满足这些要求的新关系就称为R的闭包。本节介绍关系的自反、对称和传递闭包。2021/5/977定义2.17设R是非空集合A上的关系，R的自反（对称或传递）闭包是A上的关系Rc，使得Rc满足以下条件：(1)Rc是自反的（对称的或传递的）；(2)RRc；(3)对A上任何包含R的自反（对称或传递）关系Rp有Rc

Rp。一般将R的自反闭包记作r(R)，对称闭包记作s(R)，传递闭包记作t(R)。2021/5/978定理2.11

设R为定义在非空集合A上的二元关系，则有（1）r（R）=R∪IA（2）s（R）=R∪R-1（3）t（R）=R∪R2∪R3∪…2021/5/979证明（1）令R′=R∪IA，则有①IA

R∪IA

，而R∪IA=R′，因此R′是自反的。②RR∪IA

，而R∪IA=R′，因此RR′。③假设R″是A上的任意自反关系并且RR″，因为R″是自反的，所以IAR″，因此有R′=R∪IA

R″。由自反闭包的定义，R′=R∪IA是R的自反闭包，即r(R)=R′=R∪IA

。2021/5/980（2）令R=R∪R-1①(R)-1=(R∪R-1)-1=R-1∪(R-1)-1=R-1∪R=R∪R-1=R,因此R是对称的。②RR∪R-1，而R∪R-1=R，因此RR。③设R是A上的任意对称关系并且RR，又(x，y)R-1(y，x)R(y，x)R，从而有R=R∪R-1R。因此R是R的对称闭包，即s(R)=R∪R-1。2021/5/981（3）分两部分来证所要的结论。先证R∪R2∪R3∪…t（R）用数学归纳法来证，对任意自然数i，有Rit（R）①当i=1时，由传递闭包的定义，R1=Rt（R）。②假设当i=n时，Rnt（R）,下证Rn+1t（R）。对任意的(x,y)∈Rn+1，存在c∈A，使得(x,c)∈Rn且(c,y)∈R，即存在c∈A，使得(x,c)∈t(R)且(c,y)∈t(R)，则(x,y)∈t(R)。即Rn+1

t(R)，因此，R∪R2∪R3∪…t(R)。再证明t(R)R∪R2∪R3∪…。显然，有RR∪R2∪R3∪…成立，下证R∪R2∪R3∪…是传递的。(x,y)∈R∪R2∪R3∪…t(R)且(y,z)∈R∪R2∪R3∪…t∈A，使得(x,y)∈Rt且s∈A，使得(y,z)∈Rs(x,z)∈Rt·Rs=Rt+sR∪R2∪R3∪…(x,z)∈R∪R2∪R3∪…由传递关系的定义，R∪R2∪R3∪…是传递的。综上所述，R∪R2∪R3∪…是包含R的传递关系。而R的传递闭包是包含R的最小传递关系，因此t(R)R∪R2∪R3∪…。即t(R)=R∪R2∪R3∪…成立。2021/5/982推论

设R是有限集合A上的关系，|A|=n，此时t（R）=R∪R2∪R3∪…Rn有。2021/5/983例2.20设集合A={a,b,c}，R是A上的二元关系，且R={(a,b),(b,c),(c,a)}，求出关系R的自反、对称和传递闭包。2021/5/984解：r(R)=R∪IA={(a,a),(b,b),(c,c),(a,b),(b,c),(c,a)}s(R)=R∪R-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=R6…t(R)=R∪R2∪R3∪…=R∪R2∪R3={(a,a),(b,b),(c,c),(a,b),(b,c),(c,a),(a,c),(b,a),(c,b)}2021/5/985例2.21设集合A={a,b,c}，R是A上的二元关系，且R={(a,b),(b,c),(c,a)}，用关系矩阵求关系R的自反、对称和传递闭包。2021/5/986解关系的关系矩阵为：2021/5/987定理2.12

设R是非空集合A上的关系，（1）若R是自反的，则s(R)与t(R)也是自反的。（2）若R是对称的，则r(R)与t(R)也是对称的。（3）若R是传递的，则r(R)是传递的，而s(R)不一定传递。2021/5/988证明(1)若R是自反的，则有IA

R。又因为Rs(R)，且Rt(R)，所以IAs(R)且IA

t(R)，因此s(R)与t(R)是自反的。(2)因为R对称，有R=R-1。由于r(R)=R∪IA

，而(r(R))-1=(R∪IA)-1=R-1∪IA-1=R∪IA=r(R),因此r(R)对称。因为R对称，因此(Ri)-1=(R-1)i=Ri。由于t(R)=R∪R2∪R3∪…,于是(t(R))-1=(R∪R2∪R3∪…)-1=R-1∪(R2)-1∪(R3)-1∪…=R∪R2∪R3∪…=t(R)所以t(R)也对称。2021/5/989(3)因为R传递，所以R.RR，而r(R)=R∪IA

，则有r(R).r(R)=(R∪IA)(R∪IA)=R.(R∪IA)∪IA.(R∪IA)=R.R∪RIA∪IA.(R∪IA)=R.R∪R∪(R∪IA)

R∪R∪(R∪IA)=R∪IA=r(R)即r(R)具有传递性。2021/5/990下面举一个反例来说明s(R)不具备传递性。假设集合A={1,2,3}，R={(1,2)}是定义在集合A上的且具有传递性，而s(R)={(1,2),(2,1)}却不具备传递性。2021/5/991定理2.13

设R1,R2A×A，且R1R2，则

r(R1)r(R2) s(R1)s(R2) t(R1)t(R2)2021/5/992证明：(1)因为R1R2，因此R1∪IAR2∪IA，所以r(R1)r(R2)。反证法： 假设(x,y)r(R1),但(x,y)r(R2)，则r(R1)–{(x,y)}也是自反的，即xy;如果(x,y)R1，则(x,y)R2，那么(x,y)r(R2)，导致矛盾，因此(x,y)R1，所以R1r(R1)–{(x,y)}，那么r(R1)不是R1的自反闭包，矛盾。因此(x,y)r(R2)。所以r(R1)r(R2)。2021/5/993(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)。2021/5/994定理2.14

设R1和R2是集合A上的关系，则以下各式成立。（1）r（R1∪R2

）=r（R1

）∪r（R2

）（2）s（R1∪R2

）=s（R1

）∪s（R2

）（3）t（R1

）∪t（R2

）t（R1∪R2

）2021/5/995证明：（1）r(R1∪R2)=IA∪(R1∪R2)=(IA∪R1)∪(IA∪R2)=r(R1)∪r(R2)（2）s(R1∪R2)=(R1∪R2)∪(R1∪R2)-1=(R1∪R2)∪(R-11∪R-12)=(R1∪R-11)∪(R2∪R-12)=s(R1)∪s(R2)（3）因为R1R1∪R2

，R2R1∪R2

，所以t(R1)t(R1∪R2)，t(R2)t(R1∪R2)，得出t(R1)∪t(R2)t(R1∪R2)。一般地，t(R1)∪t(R2)≠t(R1∪R2)。2021/5/996例2.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(R1∪R2)={(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(R1∪R2)。2021/5/997定理2.15

设R是集合A上的关系，则（1）rs(R)=sr(R)；（2）rt(R)=tr(R)；（3）st(R)ts(R)。2021/5/998证明（1）2021/5/999(2)

2021/5/9100(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)。2021/5/9101例2.23设A={1,2}，R={(1,2)}，求st(R)与ts(R)。2021/5/9102例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)=t(s(R))=t{(1,2),(2,1)}={(1,2),(2,1),(1,1),(2,2)}2021/5/91032.6等价关系与划分在日常生活中或者在数学等学科中，常常需要对某个集合上的元素按照某种方式进行分类，即集合的划分，这是一个非常重要的而且应用十分广泛的概念，集合的划分与一种重要的关系——等价关系密切相关。利用等价关系，可以将集合中的元素分类，将一个大的集合分成若干个等价类，其主要意义在于它证实了应用抽象的一般原理的正确性，即在某方面等价的个体产生等价类，对全体的等价类进行分析常常比对全体本身进行分析更简单。2021/5/91042.6.1等价关系定义2.18设R为非空集合A上的关系。如果R是自反的、对称的和传递的，则称R为A上的等价关系。设R是一个等价关系，若(x，y)∈R，称x等价于y，记做x～y。2021/5/9105例2.24以下关系是等价关系：(1)集合A上的恒等关系、全域关系是等价关系。(2)三角形的全等关系、三角形的相似关系是等价关系。(3)在一个班级里“年龄相等”的关系是等价关系。2021/5/9106例2.25设关系R是定义在有理数集Q上的关系，并且(x,y)∈R，当且仅当x-y是整数，试证R是等价关系。2021/5/9107例2.25设关系R是定义在有理数集Q上的关系，并且(x,y)∈R，当且仅当x-y是整数，试证R是等价关系。证明：(1)自反性：对任意一个有理数x∈Q，有x-x=0是整数，即对所有的有理数有(x,x)∈R，因此R满足自反性。(2)对称性：假设x,y∈Q，并且(x,y)∈R，即x-y是整数，则y-x=-(x-y)也是整数，即(y,x)∈R，因此R满足对称性。(3)传递性：假设x,y,z∈Q，并且(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是等价关系。2021/5/9108例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上的等价关系。2021/5/9109证明：写出关系R关系矩阵如下：由关系矩阵可以看出，该矩阵的主对角线的元素都是1，即关系R满足自反性。该关系矩阵是对称的，即R满足对称性。求出R2的关系矩阵为：即R2的关系矩阵与R的关系矩阵相同，并且有R3，…，Rn都与R的关系矩阵相同，因此，t(R)=R∪R2∪R3∪…∪Rn的关系矩阵也与R的关系矩阵相同，所以R是传递的。综上所述，R是A上的等价关系。2021/5/9110例2.27设A={1,2,…,8},定义A上的关系R={(x，y)|x，y∈A且x≡y(mod3)}，其中x≡y(mod3)叫做x与y模3相等，即x除以3的余数与y除以3的余数相等。试证R为A上的等价关系。2021/5/9111证明：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,y∈A，若(x,y)∈R，即x≡ymod3，则有y≡xmod3，即(y,x)∈R，因此R满足对称性。对x,y,z∈A，若(x,y)∈R，(y,z)∈R，即x≡ymod3，y≡zmod3，则有x≡zmod3，即(x,z)∈R，因此R满足传递性。综上所述，R是等价关系。2021/5/9112定理2.16设R是定义在集合A上的关系，则R为等价关系R*R-1=R。2021/5/9113定理2.16设R是定义在集合A上的关系，则R为等价关系R*R-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)∈R·R-1

于是,RR·R-1.另一方面，(x,y)∈R·R-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-1R.综上可知,必要性得证.(2)充分性:由假设R·R-1=R可知,(x,y)∈R(x,y)∈R·R-1

z使得(x,z)∈R且(z,y)∈R-1

z使得(x,z)∈R且(z,y)∈R由此可推知R为对称和传递时方使上式成立,从而R也必为自反,充分性得证。2021/5/9114定义2.19设R为集合A上的等价关系，对集合A中的任意元素a,称A中与a等价的全体元素所组成的集合为由a生成的等价类，记作[a]R。即[a]R={b|b∈A且(a,b)∈R},a称为这一等价类的代表元或生成元。2021/5/9115例2.28设A={1,2,…,8},如下定义A上的二元关系R={(x，y)|x，y∈A且x≡y(mod3)}，其中x≡y(mod3)叫做x与y模3相等，求R的等价类。2021/5/9116解[1]R={1，4，7} [2]R={2，5，8} [3]R={3，6} [4]R={1，4，7} [5]R={2，5，8} [6]R={3，6} [7]R={1，4，7} [8]R={2，5，8}即[1]=[4]=[7]={1,4,7}[2]=[5]=[8]={2,5,8}[3]=[6]={3,6}

所以不同的等价类只有3个[1]R、[2]R

、[3]R。2021/5/9117定义2.20设R为非空集合A上的等价关系，以R的所有等价类作为元素的集合称为A关于R的商集，记做A/R，即A/R={[a]R|a∈A}A/R的基数（即不同类的个数）称为R的秩。2021/5/9118例2.29在例2.28中的商集为A/R={{1,4,7},{2,5,8},{3,6}},关系R的秩为3。2021/5/9119例2.30整数集Z上模m的等价关系R={(x,y)|x,yZ且xy(mod)m}其等价类是：[0]R={km|kZ}[1]R={km+1|kZ}…[m-1]R={km+(m-1)|kZ}因此商集为Z/R={[0]R，[1]R，…，[m-1]R}2021/5/9120定理2.17

设R为非空集合A上的等价关系,则：（1）a∈A，[a]R是A的非空子集。（2）a,b∈A，如果(a,b)∈R，则[a]R=[b]R。（3）a,b∈A，如果(a,b)R，则[a]R∩[b]R=。（4）∪{[a]R|a∈A}=A2021/5/9121证明（1）a∈A，由R的自反性，有(a,a)∈R，所以a∈[a]R，因此[a]R非空；再由等价类定义，[a]RA。（2）对于x∈[a]R，则(a,x)∈R，又因为(a,b)∈R，由R的对称性与传递性，可得(b,x)∈R，于是x∈[b]R，因此[a]R[b]R。 同样可证[b]R[a]R

所以[a]R=[b]R（3）反证法：如果有元素x∈[a]R∩[b]R，则(a,x)∈R且(b,x)∈R，由R的对称性和传递性，可得(a,b)∈R，与(a,b)R矛盾，所以[a]R与[b]R不交。2021/5/9122(4)先证∪{[a]R|a∈A}A

任取b，b∈∪{[a]R|a∈A}

a使得a∈A且b∈[a]R)

b∈A(因为[a]R

A)

∴∪{[a]R|a∈A}A

再证A∪{[a]R|a∈A}

任取b，b∈Ab∈[b]R

b∈∪{[a]R|a∈A}

∴A∪{[a]R|a∈A}成立。

综上所述得∪{[a]R|a∈A}=A。2021/5/91232.6.2集合的划分定义2.21

：设A是任意非空集合，A1，A2，…，Am是集合A的子集,满足：（1）Ai≠(i=1,2,…,m)；（2）Ai∩Aj=(i≠j)；（3）A1∪A2∪…∪Am=A。则集合族={A1，A2，…，Am}为A的一个划分，而A1，A2，…，Am为这个划分的划分块。2021/5/9124例2.31设集合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的划分。2021/5/9125细分、真细分定义2.22设1={A1,A2,…,An}和2={B1,B2,…,Bm}是集合S的两种划分,如果1中的每个Ai都是2中某个Bj的子集,则称划分1是划分2的一个细分。如果1是2的细分，且1中至少有一个Ai是某个Bj的真子集，则称1是2的真细分。2021/5/9126例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}}的细分。2021/5/9127最大划分、最小划分、交叉划分定义2.23设A是非空集合，G={{a}|a∈A}称为A的最大划分，S={A}称为A的最小划分。例2.34

在例2.31中的划分1={{1},{2},{3},{4}}是对集合A的最大划分，划分4={{1,2,3,4}}是对集合A的最小划分。2021/5/9128最大划分、最小划分、交叉划分定义2.24设1={A1,A2,…,An}和2={B1,B2,…,Bm}是集合S的两种划分，称{Ai∩Bj|Ai∩Bj≠,1≤i≤n,1≤j≤m}为1和2的交叉划分。例2.35设集合A={1,2,3,4},则在例2.31中的划分2={{1},{2,3,4}}与划分3={{1,2},{3,4}}的交叉划分为2∩3={{1},{2},{3,4}}。2021/5/9129定理2.18

：设1={A1,A2,…,An}和2={B1,B2,…,Bm}是集合S的两种划分，则其交叉划分=1∩2也是S的一个划分。2021/5/9130证明交叉划分={Ai∩Bj|Ai∩Bj≠,1≤i≤n,1≤j≤m}。在中任取两个元素Ai∩Bh，Aj∩Bk，考察(Ai∩Bh)∩(Aj∩Bk)是否满足集合划分定义中的三个条件：（1）若ij且h=k，由于Ai∩Aj=，则Ai∩Bh∩Aj∩Bk=；（2）若ij且hk，由于Ai∩Aj=，Bh∩Bk=，则Ai∩Bh∩Aj∩Bk=；（3）若i=j且hk，由于Bh∩Bk=，则Ai∩Bh∩Aj∩Bk=；由此可见，在交叉划分中，任意两个元素的交集均为，且有交叉划分中所有元素的并集为：2021/5/9131(A1∩B1)∪(A1∩B2)∪…∪(A1∩Bm)∪(A2∩B1)∪(A2∩B2)∪…∪(A2∩Bm)∪…∪(An∩B1)