1、关系的基本概念关系的基本概念关系的表示方法关系的表示方法 关系的运算关系的运算 关系的性质关系的性质 关系的闭包关系的闭包等价关系与划分等价关系与划分偏序关系偏序关系12.1关系的基本概念为了讨论关系，首先引入有序对和笛卡儿积两个概念。为了讨论关系，首先引入有序对和笛卡儿积两个概念。由两个元素由两个元素a,ba,b组成的集合组成的集合a,ba,b中，中，a a和和b b是没有次是没有次序的。有时需要考虑有次序的两个元素，所以需要由序的。有时需要考虑有次序的两个元素，所以需要由两个元素组成新的东西，并且两个元素是有次序的。两个元素组成新的东西，并且两个元素是有次序的。定义定义2.12.1两个元素
2、两个元素a,b a,b 有次序地放在一起，称为一个有次序地放在一起，称为一个有有序对序对或或序偶序偶，记为，记为(a,b)(a,b)。在有序对。在有序对(a,b)(a,b)中，中，a a 称称为为第一元素第一元素，b b称为称为第二元素第二元素。且。且(a(a1 1,b,b1 1)=(a)=(a2 2,b,b2 2)当且仅当当且仅当a a1 1=a=a2 2 且且b b1 1=b=b2 2。例例2.1 2.1 直角坐标系中的点直角坐标系中的点(1,2)(1,2)与点与点(2,1)(2,1)是两个不同的是两个不同的点。点。2定义定义2.2 2.2 任给任给n2,n n2,n 个元素个元素a a1
3、 1,a,a2 2,a,an n 有有次序地放在一起次序地放在一起,称为一个称为一个n n 元有序元有序 组组,记为记为(a(a1 1,a,a2 2,a,an n)。为了体现。为了体现n n 元有序组的次序元有序组的次序,规定规定(a(a1 1,a,a2 2,a,an n)=(b)=(b1 1,b,b2 2,b,bn n)当且仅当当且仅当任给任给1in,1in,都有都有a ai i=b=bi i。例例2.2 2.2 三维坐标系中的点三维坐标系中的点(1,2,3)(1,2,3)与点与点(3,2,1)(3,2,1)是两个不同的点。是两个不同的点。34定义定义2.32.3 设设A,B 是两个集合，集
4、合是两个集合，集合(x,y)|xA 且且yB 称为称为A 和和B 的的笛卡儿积笛卡儿积，也称也称卡氏积卡氏积，记为，记为AB。用属于关系来表示。用属于关系来表示就是：就是：(x,y)AB 当且仅当当且仅当xA 且且yB和和(x,y)AB 当且仅当当且仅当x A或或y B。其中。其中A 称为称为第一集合第一集合，B 称为称为第二集合第二集合。5例例2.32.3 设设A=1,2,3,B=A,BA=1,2,3,B=A,B，求求ABAB。由笛卡儿积的定义可知有由笛卡儿积的定义可知有AA=A=A=。又由有序对的性质可知，一般没有又由有序对的性质可知，一般没有ABBAABBA。ABAB也是一个集合，所以可
5、以也是一个集合，所以可以和另一集合和另一集合C C作笛卡儿积作笛卡儿积(AB)C(AB)C，类似地，类似地有有A(BC)A(BC)。但是，一般没有。但是，一般没有(AB)C=A(BC)(AB)C=A(BC)，且，且ABAB中的元素既中的元素既不是不是A A 中的元素，也不是中的元素，也不是B B中的元素。中的元素。定义定义2.4 2.4 任给任给n2,An2,A1 1,A,A2 2,A,An n 是是n n 个集合个集合,集合集合(x(x1 1,x,x2 2,x,xn n)|)|任给任给1i n,1i n,都有都有x xi iAAi i 称为称为A A1 1,A,A2 2,A,An n的笛卡儿
6、积的笛卡儿积,记为记为 A A1 1AA2 2AAn n。任给。任给1in,A1in,Ai i 称为这个称为这个卡氏积的第卡氏积的第i i个集合。个集合。6例例2.4 2.4 设集合设集合A=1,2,A=1,2,集合集合B=a,b,B=a,b,集合集合C=C=,计算计算ABC,(AB)C,A(BC)ABC,(AB)C,A(BC)。解解:ABC:ABC=(1,a,=(1,a,),(1,),(1,b,b,),(2,),(2,a,a,),(2,),(2,b,b,),(1,),(1,a,a,),),(1,(1,b,b,),(2,),(2,a,a,),(2,),(2,b,b,)(AB)C AB)C=(1
7、,a),=(1,a),),(1,),(1,b),b),),(2,),(2,a),a),),(2,),(2,b),b),),(),(1,(1,a),a),),(1,),(1,b),b),),(2,),(2,a),a),),(2,),(2,b),b),)A(BC)A(BC)=(1,(a,=(1,(a,),(1,(),(1,(b,b,),(2,(),(2,(a,a,),(2,(),(2,(b,b,),(),(1,(1,(a,a,),(1,(),(1,(b,b,),(2,(),(2,(a,a,),(2,(),(2,(b,b,)78定理定理2.1 2.1 如果如果B B1 1 A A1 1，B B2 2
8、 A A2 2，则，则B B1 1B B2 2 A A1 1A A2 2。证明证明 对对(x,y)B B1 1B B2 2，有，有xB B1 1 且且yB B2 2，又因为，又因为B B1 1 A A1 1 ，B B2 2 A A2 2 ，则，则xA A1 1 且且yA A2 2，所以，所以(x,y)A A1 1A A2 2，即，即B B1 1B B2 2 A A1 1A A2 2。9定理定理2.22.2 A,B,C 是任意集合，则：是任意集合，则：(1)(1)A(BC)=(AB)(AC)，(BC)A=(BA)(CA)。(2)A(BC)=(AB)(AC)，(BC)A=(BA)(CA)。(3)A
9、(B-C)=(AB)-(AC)，(B-C)A=(BA)-(CA)。10证明证明 (1)(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)。因为因为AA，BBC 和和CBC 得得ABA(BC)和和ACA(BC)，因此，因此(AB)(AC)A(BC)。因此因此A(BC)=(AB)(AC)成立。成立。同理可证同理可证(BC)A=(BA)(CA)。11(2)对对(x,y)(
10、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)。因为因为AA，BCB和和BCC，所以有，所以有A(BC)AB和和A(BC)AC成立，因此成立，因此A(BC)(AB)(AC)。因此因此A(BC)=(AB)(AC)。同理可证同理可证(BC)A=(BA)(CA)。12(3)(3)对对(x,y)A(B-C)，有，有xA且且yB-C，所以，所以xA且且yB且且y C。由。由xA且且yB得得(x,y)AB，由，由y C得得(x,y
11、)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.52.5 如果一个集合满足以下条件之一：如果一个集合满足以下条件之一：（1 1）集合非空，且它的元素都是有
12、序对；）集合非空，且它的元素都是有序对；（2 2）集合是空集。）集合是空集。则称该集合为一个则称该集合为一个二元关系二元关系，记作，记作R R。二元关系也可。二元关系也可简称为简称为关系关系。对于二元关系。对于二元关系R R，如果，如果(x,y)R)R，可，可记作记作xR Ry；如果；如果(x,y)R R，则记作，则记作xR R y。设设A A，B B为集合，为集合，ABAB的任何子集所定义的二元关系的任何子集所定义的二元关系叫做叫做从从A A到到B B的二元关系的二元关系，特别当，特别当A=BA=B时则叫做时则叫做A A上的上的二元关系二元关系。例例2.5 2.5 判断下列集合是否是二元关系
13、。判断下列集合是否是二元关系。(1)A=(1)A=。(2)B=(1,2),(a,b)(2)B=(1,2),(a,b)。(3)C=a,(a,b)(3)C=a,(a,b)。(4)D=(1,2),(a,b),(3,4),(c,d)(4)D=(1,2),(a,b),(3,4),(c,d)。1415例例2.62.6 设集合设集合A=0,1A=0,1，B=1,2,3B=1,2,3，那么，那么R R1 1=(0,2)=(0,2)，R R2 2=AB=AB，R R3 3=，R R4 4=(0,1)=(0,1)等都是从等都是从A A到到B B的二元关系，而的二元关系，而R R3 3和和R R4 4同时也同时也是
14、是A A上的二元关系。上的二元关系。16定义定义2.62.6笛卡尔积笛卡尔积A1A2An的任意一个子集的任意一个子集R称称为为A1，A2，An上的一个上的一个n元关系。当元关系。当A1=A2=An=A时，称时，称R为为A上的上的n元关系元关系。定义定义2.7空集空集上定义一个二元关系，简称上定义一个二元关系，简称空关系空关系；若一个若一个n元关系元关系R本身是笛卡儿积本身是笛卡儿积A1A2An，则称则称R为为全关系全关系，用符号用符号UA表示，即表示，即UA=(ai，aj)|ai，ajA为为A上的全关系。上的全关系。符号符号IA=(x,x)|xA为为A上的上的恒等恒等关系关系 17例例2.8
15、2.8 设设A=1,2,3,4A=1,2,3,4，下面各式定义的，下面各式定义的R R都是都是A A上的关系，试用列元素法表示上的关系，试用列元素法表示R.R.(1)R(1)R1 1=(x,y)|x=(x,y)|x是是y y的倍数的倍数(2)R(2)R2 2=(x,y)|(x-y)=(x,y)|(x-y)2 2AA(3)R(3)R3 3=(x,y)|x/y=(x,y)|x/y是素数是素数(4)R(4)R4 4=(x,y)|xy=(x,y)|xy18解解：(1)(1)R R1 1=(4,4)(4,4),(4(4,2),2),(4,14,1),(3,3),(3,1),(2,2),(2,1),(1,
16、1),(3,3),(3,1),(2,2),(2,1),(1,1)(2)R(2)R2 2=(2,1),(3,2),(4,3),(3,1),(4,2),(2,4),(1,3),(3,4),(2,=(2,1),(3,2),(4,3),(3,1),(4,2),(2,4),(1,3),(3,4),(2,3),(1,2)3),(1,2)(3)R(3)R3 3=(2,1),(3,1),(4,2)=(2,1),(3,1),(4,2)(4)R(4)R4 4=U=UA A-I-IA A=(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,=(1,2),(1,3),
17、(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)4),(4,1),(4,2),(4,3)例例2.9 2.9 设集合设集合A=a,b,A=a,b,求出定义在求出定义在A A 上的所上的所有二元关系。有二元关系。解解:首先计算出首先计算出AA=(a,a),(a,b),(b,a),(b,b),AA=(a,a),(a,b),(b,a),(b,b),则定义在则定义在 A A上的二元关系共有上的二元关系共有1616个个,即即AAAA的所有子集。的所有子集。1920定义定义2.82.8 R R ABAB中所有的有序对的第一元素中所有的有序
18、对的第一元素构成的集合称为构成的集合称为R R的的定义域定义域，记为，记为domRdomR。形。形式化表示为：式化表示为：domR=x|x A,domR=x|x A,y B,y B,使使得得(x,y)R(x,y)R。R R ABAB中所有有序对的第中所有有序对的第二元素构成的集合称为二元素构成的集合称为R R的的值域值域，记作，记作ranRranR。形式化表示为形式化表示为ranR=y|yB,ranR=y|yB,xA,xA,使使得得(x,y)R(x,y)R。21定义定义2.92.9 设设R R为二元关系为二元关系，R R的的逆关系逆关系，简称简称R R的的逆逆，记作记作R R-1-1,其中其中
19、R R-1-1=(y,x)|(x,y)R=(y,x)|(x,y)R。例例2.102.10 整除关系整除关系设设A=2,3,4,8,B=3,4,5,6,7,A=2,3,4,8,B=3,4,5,6,7,定义从定义从A A到到B B的二元关系的二元关系R:(a,b)R:(a,b)R Ra a整除整除b b。则。则 R=(2,4),(2,6),(3,3),(3,6),(4,4)R=(2,4),(2,6),(3,3),(3,6),(4,4)，Dom R=2,3,4,Ran R=3,4,6Dom R=2,3,4,Ran R=3,4,6，R R-1-1=(4,2),(6,2),(3,3),(6,3),(4,
20、4)=(4,2),(6,2),(3,3),(6,3),(4,4)例例2.11 2.11 设集合设集合A=1,2,A=1,2,集合集合B=2,3,4,B=2,3,4,定义定义A A到到B B上的二元关系上的二元关系R=(1,2),(1,3),(2,2),(2,4)R=(1,2),(1,3),(2,2),(2,4)则则domR=1,2,ranR=2,3,4domR=1,2,ranR=2,3,4。例例2.12 2.12 设集合设集合A=a,b,c,A=a,b,c,定义定义A A上的二元关上的二元关系系R=(a,a),(a,b),(b,c),R=(a,a),(a,b),(b,c),则则 domR=a,
21、b,ranR=a,b,c,domR=a,b,ranR=a,b,c,R R-1-1=(a,a),(b,a),(c,b),=(a,a),(b,a),(c,b),domRdomR-1-1=a,b,c,=a,b,c,ranRranR-1-1=a,b=a,b。2223关系从本质上讲，仍是集合，只是这个集合中关系从本质上讲，仍是集合，只是这个集合中的元素都是以有序对的形式出现。既然关系的元素都是以有序对的形式出现。既然关系是一个集合，那么集合的表示方法就可以用是一个集合，那么集合的表示方法就可以用来表示关系，又因为关系是一个特殊的集合，来表示关系，又因为关系是一个特殊的集合，其中的元素均以序偶的形式出现，
22、除了可以其中的元素均以序偶的形式出现，除了可以用集合的表示方法外，还可以用其他的表示用集合的表示方法外，还可以用其他的表示方法。这里主要介绍如下几种表示方法。方法。这里主要介绍如下几种表示方法。241.1.用列举法表示二元关系用列举法表示二元关系如果二元关系中的序偶个数是有限的，可以用列举如果二元关系中的序偶个数是有限的，可以用列举法将其所包含的全部元素一一列举出来。法将其所包含的全部元素一一列举出来。例例2.132.13 设集合设集合A=1,2,3A=1,2,3，在集合，在集合A A上定义的小于上定义的小于等于关系，等于关系，L LA A=(a,b)|a,bA,ab=(a,b)|a,bA,a
23、b，则，则L LA A=(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)=(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)。252.2.用描述法表示二元关系用描述法表示二元关系用确定的条件表示某些序偶是否属于这个关系，并把用确定的条件表示某些序偶是否属于这个关系，并把这个条件写在大括号内表示关系的方法。这个条件写在大括号内表示关系的方法。格式是：格式是：L LR R=(x,y)|xR=(x,y)|xR且且yRyR且且xyxy。例例2.142.14设设A=1A=1，2 2，3 3，44，下面两式定义的，下面两式定义的R R1 1和和R R2 2都是都是
24、A A上的关系，分别列出上的关系，分别列出R R1 1与与R R2 2的元素如下：的元素如下：(1)R(1)R1 1=(x,y)|x=(x,y)|x是是y y的倍数的倍数 (2)R(2)R2 2=(x,y)|(x-y)=(x,y)|(x-y)2 2AA26解解：(1)(1)R1=(4,4),(4,2),(4,1),(3,3),(3,1),(2,2),(2,1),(1,1)(2)(2)R2=(2,1),(1,2),(3,1),(1,3),(2,3),(3,2),(4,2),(2,4),(3,4),(4,3)27定义定义2.102.10设设A A和和B B是两个有限集是两个有限集A=aA=a1 1
25、,a,am m，B=B=bb1 1,b,bn n，R R是从是从A A到到B B的二元关系，称的二元关系，称m m n n阶矩阵阶矩阵M MR R=(r=(rijij)为为R R的关系矩阵，其中的关系矩阵，其中 r rijij=1=1 ，当且仅当，当且仅当(a(ai i,b,bj j)R R r rijij=0 =0，当且仅当，当且仅当(a(ai i,b,bj j)R R28例例2.162.16设集合设集合A=1,2,3,A=1,2,3,在集合在集合 A A 上定义的小于或等于关上定义的小于或等于关系系,则关系则关系R R 的关系的关系 矩阵为矩阵为 ：例例2.172.17设设A=1,2,3,
26、4,A=1,2,3,4,下面两式定义的下面两式定义的R R1 1 和和R R2 2 都是都是A A 上上的关系的关系,分别列出分别列出R R1 1 与与R R2 2 的元素。的元素。(1)R(1)R1 1=(x,y)|x=(x,y)|x 是是y y 的倍数的倍数 (2)R(2)R2 2=(x,y)|(x-y)=(x,y)|(x-y)2 2A A 则关系则关系R R1 1 与与R R2 2 的关系矩阵分别为：的关系矩阵分别为：，29设设A=A=a1,an，R R是是A A上的二元关系。上的二元关系。A A中每个元中每个元素素ai用一个点表示，称该点为顶点用一个点表示，称该点为顶点ai。R R的关
27、系图的关系图是一个有向图，是一个有向图，A A中每个元素分别用一个顶中每个元素分别用一个顶点表示，当且仅当点表示，当且仅当(ai,aj)R)R时，用弧或线段时，用弧或线段联结联结ai和和aj；若若(ai,aj)R)R，则在，则在ai处画一条处画一条自封闭的弧线自封闭的弧线,其中其中11i,jnn。这样表示。这样表示R R中关系的图形，称为中关系的图形，称为R R的的关系图关系图，用，用G GR R表示。表示。30例例2.182.18设集合设集合A=1,2,3,4A=1,2,3,4，在集合，在集合A A上定义关系上定义关系R=(1,1)R=(1,1)，(1,2)(1,2)，(2,3)(2,3)，
28、(2,4)(2,4)，(4,2)(4,2)，则，则R R的关系图如图的关系图如图2.12.1所示。所示。31n关系R的集合表达式、关系矩阵MR、关系图GR三者均可唯一相互确定32定义定义2.112.11 设关系设关系R R和和S S是从是从A A到到B B的两个二元关系，对于的两个二元关系，对于a a A A，b b B B，定义：，定义：（1 1）RSRS：(a,b)RS(a,b)RS(a,b)R(a,b)R或或(a,b)S(a,b)S。（2 2）RSRS：(a,b)RS(a,b)RS(a,b)R(a,b)R且且(a,b)S(a,b)S。（3 3）R-SR-S：(a,b)R-S(a,b)R-
29、S(a,b)R(a,b)R且且(a,b)(a,b)S S。（4 4）RR：(a,b)R(a,b)R(a,b)AB-R(a,b)AB-R。（5 5）R R S=(R-S)(S-R)S=(R-S)(S-R)33例例2.202.20 设集合设集合A=a,b,cA=a,b,c，集合，集合B=1,2B=1,2，且，且R R和和S S是是从从A A到到B B的两个二元关系，的两个二元关系，R=(a,1),(b,2),(c,1)R=(a,1),(b,2),(c,1)S=(a,1),(b,1),(c,2)S=(a,1),(b,1),(c,2)则则 RS=(a,1),(b,2),(c,1),(b,1),(c,2
30、)RS=(a,1),(b,2),(c,1),(b,1),(c,2)RS=(a,1)RS=(a,1)R-S=(b,2),(c,1)R-S=(b,2),(c,1)R R=AB=ABR=(a,2),(b,1),(c,2)R=(a,2),(b,1),(c,2)R R S=(b,2),(c,1)(b,1),(c,2)S=(b,2),(c,1)(b,1),(c,2)=(b,1),(b,2),(c,1),(c,2)=(b,1),(b,2),(c,1),(c,2)34因为关系可以用矩阵的形式表示，当我们用矩阵的形因为关系可以用矩阵的形式表示，当我们用矩阵的形式求关系的并、交、补及对称差的运算时，可以用式求关系
31、的并、交、补及对称差的运算时，可以用如下形式表示：如下形式表示：M MRSRS=M=MR R M MS S （矩阵的对应分量做逻辑析取运算）（矩阵的对应分量做逻辑析取运算）M MRSRS=M=MR R M MS S （矩阵的对应分量做逻辑合取运算）（矩阵的对应分量做逻辑合取运算）M MR-SR-S=M=MRSRS=M=MR R M MS S M MR R=M=M R R （矩阵的对应分量做逻辑非运算）（矩阵的对应分量做逻辑非运算）35例例2.212.21对例对例2.202.20中的关系的运算采用矩阵的形式表示如下：中的关系的运算采用矩阵的形式表示如下：根据题意，关系根据题意，关系R R与与S
32、S的关系矩阵分别表示为的关系矩阵分别表示为则36定理定理2.32.3 设关系设关系R R、S S是集合是集合A A到集合到集合B B的二元关系，则有下列的二元关系，则有下列性质成立：性质成立：(1)(R(1)(R-1-1)-1-1=R,(R=R,(R)=R(=R(双重否定律双重否定律)(2)(R(2)(R)-1-1=(R=(R-1-1),-1-1=(可换性可换性)(3)(RS)(3)(RS)-1-1=R=R-1-1SS-1-1 (分配律分配律)(RS)(RS)-1-1=R=R-1-1SS-1-1 (R-S)(R-S)-1-1=R=R-1-1-S-S-1-1 (4)S(4)S R R S S-1
33、-1 R R-1-1 (单调性单调性)S S R R S S R R (5)domR (5)domR-1-1=ranR=ranR，ranRranR-1-1=domR=domR(6)(A(6)(A B)B)-1-1=B=B A A 37证明证明：这里只证明（这里只证明（1 1）和（）和（5 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=d
34、omR。38定义定义2.122.12设设R R是从集合是从集合A A到集合到集合B B的二元关系，的二元关系，S S是从集合是从集合B B到集合到集合C C的二元关系，则的二元关系，则R R与与S S的的复合关系复合关系（合成关系合成关系）R RS S是从是从A A到到C C的关系，的关系，并且，并且，R RS=(x,z)|xAS=(x,z)|xA且且zCzC且存在且存在yByB使得使得(x,y)R,(y,z)S(x,y)R,(y,z)S，运算，运算“”称为称为复合复合运算运算或或合成运算合成运算。39例例2.222.22 设设A A上的二元关系上的二元关系R R=(x,y)|x,y A,x是
35、是y的父亲的父亲，S S=(x,y)|x,y A,x是是y的母亲的母亲 (1)说明说明R RR R，R R-1-1 S S11，R R-1-1 S S的含义。的含义。(2)表示以下关系：表示以下关系：(x,y)|x,y A,y是是x的外祖母的外祖母(x,y)|x,y A,x是是y的祖母的祖母40解解：(1)R RR R表示关系表示关系(x,y)|x,y A,x是是 y的祖父的祖父 R R-1-1 S S11 表示关系表示关系(x,y)|x,y A,y是是x的祖母的祖母 t A(x,t)R-1-1 (t,y)S-1-1)R R-1-1 S S表示空关系表示空关系(2)(x,y)|x,y A,y是
36、是x的外祖母的外祖母表示为表示为S S-1-1 S S11(x,y)|x,y A,x是是y的祖母的祖母表示为表示为S SR R41例例2.232.23设设Z Z是整数集合，是整数集合，R R，S S是是Z Z到到Z Z的两个关的两个关系：系：R=(x,3x)|xZR=(x,3x)|xZ；S=(x,5x)|xZS=(x,5x)|xZ。计算计算 R RS S；S SR R；R RR R；S SS S；(R(RR)R)R R；(R(RS)S)R R。42解解 R RS=(x,15x)|xZS=(x,15x)|xZ；S SR=(x,15x)|xZR=(x,15x)|xZ；R RR=(x,9x)|xZR
37、=(x,9x)|xZ；S SS=(x,25x)|xZS=(x,25x)|xZ；(R(RR)R)R=(x,27x)|xZR=(x,27x)|xZ；(R(RS)S)R=(x,45x)|xZR=(x,45x)|xZ。43证明证明 任取任取(x,y)(x,y)，有，有(x,y)R(x,y)RI IA At(x,t)Rt(x,t)R且且(t,y)I(t,y)IA A)t(x,t)Rt(x,t)R且且t=y)t=y)(x,y)R(x,y)R又又(x,y)R(x,y)R(x,y)R(x,y)R且且x,yAx,yA (x,y)R(x,y)R且且(y,y)I(y,y)IA A (x,y)R(x,y)RI IA
38、A所以，所以，R RI IA A=R=R。同理可证同理可证 I IA AR=RR=R。定理定理2.4 2.4 R R为定义在集合为定义在集合A A上的关系上的关系,则则R R I IA A=I=IA A R=RR=R44定理定理2.52.5 设设R R1 1 A1 A A2 2，R R2 2 A2 A A3 3，R R3 3 A3 A A4 4，则，则(1)(R R1 1R R2 2)R R3 3=R R1 1(R R2 2R R3 3)(2)(R R1 1R R2 2)-1=R2-1R R1 1-1但复合关系不满足交换律，即但复合关系不满足交换律，即R R1 1R R2 2 R R2 2R
39、R1 1。45证明证明：(1)任取任取(x,y),(x,y)(R1R2)R3(t A3)(使得使得(x,t)R1R2且且(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)R2R3)(x,y)R1(R2R3)所以所以(R1 R2)R3=R1(R2R3)46由归纳法，任意由归纳法，任意n n个关系的合成也是可结合的个
40、关系的合成也是可结合的特别，当特别，当A1=A2=An+1=A=A且且R1=R2=Rn=R=R，合成关系，合成关系R R R R R=RR=Rn n 是是集合集合A A上的一个关系。上的一个关系。47（2 2）任取任取(z,x)(R(z,x)(R1 1R R2 2)-1-1，则（，则（x,z)Rx,z)R1 1R R2 2，由，由“”的的定义知，至少存一个定义知，至少存一个yByB，使得，使得(x,y)R(x,y)R1 1，(y,z)R(y,z)R2 2，即，即(y,x)R(y,x)R-1-11 1，(z,y)R(z,y)R-1-12 2。由。由(z,y)R(z,y)R-1-12 2和和(y,
41、x)R(y,x)R-1-11 1 ，有，有(z,x)R(z,x)R-1-12 2 R R-1-11 1 。所以，。所以，(R(R1 1R R2 2)-1-1 R R-1-12 2 R R-1-11 1 。反之，任取反之，任取(z,x)(z,x)R R-1-12 2 R R-1-11 1 ，由，由“”的定义知：的定义知：则至则至少存在一个少存在一个yByB，使得，使得(z,y)R(z,y)R-1-12 2和和(y,x)R(y,x)R-1-11 1 ，所以，所以 (x,y)R(x,y)R1 1，(y,z)R(y,z)R2 2。由由“”知知(x,z)R(x,z)R1 1R R2 2。即有。即有(z,
42、x)(R(z,x)(R1 1R R2 2)-1-1。所以，所以，R R-1-12 2 R R-1-11 1 (R(R1 1R R2 2)-1-1。由集合的性质知：由集合的性质知：(R(R1 1R R2 2)-1=R)-1=R-1-12 2 R R-1-11 1 。48例例2.252.25 设设A=a,b,c,d,e,fA=a,b,c,d,e,f，R=(a,a),(a,b),(b,c),(c,d),(d,e),(e,f)R=(a,a),(a,b),(b,c),(c,d),(d,e),(e,f)。求。求R Rn n(n=1,2,3,4,(n=1,2,3,4,)49解解：R R1 1=R=R；R R
43、2 2=R=RR=(a,a),(a,b),(a,c),(b,d),(c,e),(d,f)R=(a,a),(a,b),(a,c),(b,d),(c,e),(d,f)；R R3 3=R=RR RR=RR=R2 2R=(a,a),(a,b),(a,c),(a,d),(b,e),(c,f)R=(a,a),(a,b),(a,c),(a,d),(b,e),(c,f)；R R4 4=R=R3 3R=(a,a),(a,b),(a,c),(a,d),(a,e),(b,f)R=(a,a),(a,b),(a,c),(a,d),(a,e),(b,f)；R R5 5=R=R4 4R=(a,a),(a,b),(a,c),
44、(a,d),(a,e),(a,f)R=(a,a),(a,b),(a,c),(a,d),(a,e),(a,f)；R R6 6=R=R5 5R=(a,a),(a,b),(a,c),(a,d),(a,e),(a,f)=RR=(a,a),(a,b),(a,c),(a,d),(a,e),(a,f)=R5 5；R R7 7=R=R6 6R=RR=R5 5；R Rn n=R=R5 5（n n5 5）。）。50幂集幂集Rn的基数的基数|Rn|并非随着并非随着n的增加而增的增加而增加，而是呈递减趋势，而且，当加，而是呈递减趋势，而且，当 时，时，有有 51有了关系的定义，可以来定义关系的某些特有了关系的定义，可
45、以来定义关系的某些特殊性质，这些性质在以后的讨论中，将起到殊性质，这些性质在以后的讨论中，将起到极其重要的作用。本节主要讨论关系的五种极其重要的作用。本节主要讨论关系的五种性质，即性质，即自反性自反性、反自反性反自反性、对称性对称性、反对反对称性称性和和传递性传递性。52定义定义2.14设设R R为集合为集合A A上的二元关系：上的二元关系：（1 1）若对任意的若对任意的xAxA，都有，都有(x,x)R(x,x)R，则称关系，则称关系R R在集合在集合A A上是上是自反自反的或称关系的或称关系R R具有具有自反性自反性；否则，否则，称称R R是非自反的。是非自反的。（2 2）若对任意的若对任意
46、的xAxA，都有，都有(x,x)R(x,x)R，则称关，则称关系系R R在集合在集合A A上是上是反自反反自反的或称关系的或称关系R R具有具有反自反性反自反性。53例例2.262.26 设设A=1,2,3A=1,2,3，R R1 1=(1,1),(2,2)=(1,1),(2,2)，R R2 2=(1,1),(2,2),(3,3),(1,2)=(1,1),(2,2),(3,3),(1,2)，R R3 3=(1,3)=(1,3)，说明，说明R R1 1，R R2 2，R R3 3是否为是否为A A上自反上自反的关系。的关系。54解解：只有只有R R2 2是是A A上自反的关系，因为上自反的关系，
47、因为I IA A R R2 2；而而R R1 1和和R R3 3都不是都不是A A上的自反关系，因为上的自反关系，因为(3,3)(3,3)R R1 1 ，所以，所以R R1 1不是自反的，而不是自反的，而(1,1),(2,2),(3,3)(1,1),(2,2),(3,3)都不属于都不属于R R3 3 ，因此，因此R R3 3不不是自反的。是自反的。关系关系R R是否为自反关系是相对集合是否为自反关系是相对集合A A来说的。来说的。同一个关系在不同的集合上具有不同的性质。同一个关系在不同的集合上具有不同的性质。55例例2.272.27设设A=a,b,c,dA=a,b,c,d，在集合，在集合A A
48、上定义如下上定义如下三个二元关系三个二元关系R,S,TR,S,T分别如下：分别如下：R=(a,a),(a,d),(b,b),(b,d),(c,c),(d,d)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)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),T=(a,a),(a,b),(a,c),(b,d),(c,a),(c,c),(d,c)(d,c)说明说明R,S,TR,S,T在在A A上的自反性
49、与反自反性。上的自反性与反自反性。56解解：因为因为A A中每个元素中每个元素x x，都有，都有(x,x)R(x,x)R，所以，所以R R在在A A具备自反性。具备自反性。因为因为A A中每个元素中每个元素x x，都有，都有(x,x)(x,x)S S，所以，所以S S在在A A具备具备反自反性。反自反性。因为因为A A中有元素中有元素b b，使，使(b,b)(b,b)T T，所以，所以T T在在A A上不具备上不具备自反性；自反性；因为因为A A中有元素中有元素a a，使，使(a,a)T(a,a)T，所以，所以T T在在A A上也不具备反自反性。上也不具备反自反性。任何不是自反的关系未必一定是
50、反自反的关系，反任何不是自反的关系未必一定是反自反的关系，反之亦然。即存在既不是自反的也不是反自反的关系。之亦然。即存在既不是自反的也不是反自反的关系。57证明证明 （1 1）必要性必要性 设设R R在在A A上是自反的，则上是自反的，则I IA A R R。根据恒等关系的定义，对任意的根据恒等关系的定义，对任意的xAxA有有(x,x)I(x,x)IA A，又因为又因为R R在在A A上是自反的，即对于任意的上是自反的，即对于任意的xAxA有有(x,x)R(x,x)R，因此，因此I IA A R R。（2 2）充分性）充分性 设设I IA A R R，则，则R R在在A A上是自反的。上是自反
