1、离散数学离散数学2022年11月18日星期五第三篇第三篇 二元关系二元关系第第6 6章章 二元关系二元关系6.0 内容提要内容提要关系的性质关系的性质3关系的闭包运算关系的闭包运算4二元关系二元关系1关系的运算关系的运算26.1本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 二元关系的二元关系的概念和表示概念和表示2 关系的复合关系的复合与逆运算与逆运算3 关系的性质关系的性质31 n重有序组重有序组2 n个集合的个集合的笛卡儿积笛卡儿积3 n重有序组重有序组相等的判定相等的判定21 关系的闭包关系的闭包运算运算第三篇第三篇 二元关系二元关系 关系理论历史悠久。它关系理论
2、历史悠久。它与集合论、数理逻辑、与集合论、数理逻辑、组合学、图论和布尔代数组合学、图论和布尔代数都有密切的联系。都有密切的联系。关系是关系是日常生活以及数学日常生活以及数学中的一个基本概念中的一个基本概念,例如例如:兄弟关系兄弟关系,师生关系师生关系,位置关系位置关系,大小关系大小关系,等等于关系于关系,包含关系等。包含关系等。6.2 二元关系二元关系6.2.1 序偶与笛卡尔积序偶与笛卡尔积 特征：特征：成对出现、具有一定的顺序。成对出现、具有一定的顺序。由两个元素由两个元素x,y按照按照一定的次序一定的次序组组成的成的二元组二元组称为称为有序偶对有序偶对(序偶序偶),记作记作,其其中中x为第
3、一个元素，为第一个元素，y为第二个元素。为第二个元素。定义定义6.2.2 给定序偶给定序偶 和和，如果如果a=c,b=d，则，则=。N重有序组重有序组定义定义6.2.3 由由n个元素个元素a1,a2,a3,an按照一定次序组成按照一定次序组成的的n元组称为元组称为n重有序组重有序组，记作记作:定义定义6.2.4 给定两个给定两个n重有序组重有序组 和和 。如果。如果aibi(i1,2,，n),则则 =。笛卡尔乘积笛卡尔乘积定义定义6.2.5设设A，B是两个集合，称集合：是两个集合，称集合：AB|(xA)(yB)为为集合集合A与与B的的笛卡尔积笛卡尔积。注意注意：（1）集合）集合A与与B的笛卡儿
4、积的笛卡儿积 AB 仍然是集合；仍然是集合；（2）笛卡尔积）笛卡尔积AB中的元素是序偶。中的元素是序偶。例例6.2.3设设A=a,B=b,c,C=,D=1,2,请分别写出下列笛请分别写出下列笛卡儿积中的元素。卡儿积中的元素。(1)AB,BA;(2)AC,CA;(3)A(BD),(AB)D。解解 根据根据笛卡儿积的定义笛卡儿积的定义，有，有(1)AB=,BA=,;(2)AC=,CA=;(3)A(BD)=a,a,a,a,;(AB)D =,1,2,1,2。注意注意由例由例6.2.3我们可以看出：我们可以看出：（1）笛卡儿积不满足交换律）笛卡儿积不满足交换律,即即 AB BA;（2）AB=当且仅当当且
5、仅当 A=或者或者B=；（3）笛卡儿积不满足结合律）笛卡儿积不满足结合律,即即A(BD)(AB)D；（4）对有限集）对有限集A,B，有，有|AB|=|BA|=|A|B|。两个定理两个定理定理定理6.2.1 设设A,B,C是任意三个集合，则是任意三个集合，则（1）A(BC)=(AB)(AC)；（2）(BC)A=(BA)(CA)；（3）A(BC)=(AB)(AC)；（4）(BC)A=(BA)(CA)。定理定理6.2.2 设设A,B,C,D是任意四个集合，则是任意四个集合，则 (AB)(CD)A C,B D。n个集合的笛卡尔集个集合的笛卡尔集定义定义6.2.6 设设A1,A2,An是是n个集合，称集
6、合个集合，称集合 A1A2An =|aiAi,i1,2,3,n为集合为集合A1,A2,An的的笛卡儿积笛卡儿积当当A1=A2=An=A时，有时，有A1A2An=An。定理定理6.2.3 当集合当集合A1,A2,An都是都是有限集有限集时，时，|A1A2An|=|A1|A2|An|。定义定义6.2.7 设设A,B为两个非空集合，称为两个非空集合，称AB的任何的任何子集子集R为为从从A到到B的二元关系的二元关系，简称关系。，简称关系。如果如果 AB，则称则称R为为A上的二元关系上的二元关系。6.2.2 二元关系的定义二元关系的定义设一有序对设一有序对：若若R，则则记为记为xRy，读作读作“x对对y
7、有关系有关系R”;若若 R，则记为则记为xRy，读作读作“x对对y没有关系没有关系R”。特别地，特别地，当当R=时，称时，称R为为空关系空关系；当当R=AB时，称时，称R为为全关系全关系。集合集合例例6.2.4假设假设A=a,b,B=c,d,试写出从试写出从A到到B的的所有不同关系所有不同关系.解解 因为因为A=a,b,B=c,d，所以，所以AB=,。于是于是AB的所有不同子集为：的所有不同子集为：0元子集：元子集：；1元子集元子集:,；2元子集元子集:,;例例6.2.4 解（续）解（续）3元子集：元子集：,；4元子集：元子集：,。注意注意:当集合当集合A,B都是有限集时，都是有限集时，AB共
8、有共有 2|A|B|个个不同的子集，即，不同的子集，即，从从A到到B的不同关系共有的不同关系共有 2|A|B|个。个。其中其中,A称为称为R的的前域前域,B称为称为R的的后后域。域。D A,C B 满满足足:Dx|R,Cy|R。称称D为为R的的定定义域义域，记为记为DdomR；称称C为为R的的值域值域,记记CranR;并并称称 fldRDC 为为R的的域域。求定义在求定义在Z上关系的定义域、值域和域。上关系的定义域、值域和域。（1）R1=|(x,yZ)y=x2；（2）R2=|(x,yZ)|x|=|y|=7。解解（1）domR1=Z,ranR1=0,1,4,9,n2,fldR1=Z；（2）dom
9、R2=7,7,ranR2=7,7,fldR2=7,7。例例6.2.5练习练习:P190 1(1)(3)1.给定集合给定集合:A=1,7,B=0,3,5,C=1,2.(1)写出写出A对对B的关系的关系,=,并确定并确定dom,ran,fld;(3)写出写出A对对C的关系的关系,=,并确定并确定dom,ran,fld。解解 (1)R=,R=,R =R;dom R=1,ranR=3,5,fldR=1,3,5;定义定义6.2.8(n元关系元关系)设设A1,A2,An为为n个非空集合个非空集合,称称 A1A2An的任意的任意子集子集R为以为以A1A2An为为基的基的n元关系元关系。6.2.3 关系的表示
10、法关系的表示法1.集合表示法集合表示法（枚举法和叙述法枚举法和叙述法）例例6.2.7（1）设）设A=a,B=b,c，用枚举法写出从，用枚举法写出从A到到B的不同关系；的不同关系；（2）用叙述法写出定义在）用叙述法写出定义在R上的上的“相等相等”关系。关系。解解（1）A到到B的不同关系有：的不同关系有：R1=,R2=,R3=,R4=,；（2）设）设R上的上的“相等相等”关系为关系为S，则，则 S=|(x,yR)(x=y)。6.2.3 关系的表示法关系的表示法2.关系图法关系图法 (1)AB 设设Aa1,a2,.,an,Bb1,b2,.,bm，R是从是从A到到B的的一个二元关系，则规定一个二元关系
11、，则规定R的关系图如下：的关系图如下：设设a1,a2,.,an和和b1,b2,.,bm分别为图中的结点分别为图中的结点,用用“。”表示表示；如如 R,则从则从ai到到bj可用有向边可用有向边 ai。bj 相连。相连。为对应图中的为对应图中的有向边有向边。（2)A=B设设AB,R是是A上的关系上的关系,则则R的关系的关系图规定如下：图规定如下：设设a1,a2,.,an为图中节点，用为图中节点，用“。”表表示示 如如 R,则从则从ai到到aj可用有向边可用有向边ai。aj相相连。连。为对应图中的为对应图中的有向边有向边。如如 R,则从则从ai到到ai用一带箭头的小圆环表用一带箭头的小圆环表示，即：
12、示，即：ai。2.关系图法关系图法（续）续）例例6.2.8试用关系图表示下面的关系。试用关系图表示下面的关系。（1）设）设A=2,3,4，B=3,4,5,6，则，则A到到B之间的一之间的一种种整除关系整除关系R1=,（2）假设）假设A=1,2,3,4，则，则A上的上的小于等于关系小于等于关系R2=,。例例6.2.8 解解（1）关系）关系R1的关系图如图的关系图如图6.2.3所示；所示；（2）关系）关系R2的关系图如图的关系图如图6.2.4所示。所示。2图图6.2.3244336134图图6.2.45设设Aa1,a2,.,an,Bb1,b2,.,bm,R是从是从A到到B的的一个二元关系，称矩阵一
13、个二元关系，称矩阵 MR(rij)nm为关系为关系R的的关关系矩阵系矩阵，其中，其中又称又称MR为为R的的邻接矩阵邻接矩阵。1,Rr(1,2,.,1,2,.,)0,Rijijija bin jma b 3.关系矩阵关系矩阵注意：注意：A中元素序号中元素序号对应矩阵元素的对应矩阵元素的行下标行下标，B中元素序号中元素序号对应矩阵元素的对应矩阵元素的列下标列下标；关系矩阵是关系矩阵是0-1矩阵，称为矩阵，称为布尔矩阵布尔矩阵。例例6.2.9 设设A=1,2,3,4，考虑考虑A上的上的 整除关系整除关系R 和和 等于关系等于关系S。（1）试写出）试写出R和和S中的所有元素；中的所有元素；（2）试写出
14、）试写出R和和S的关系矩阵。的关系矩阵。例例6.2.9 解解（1）根据整除关系和等于关系的定义，有）根据整除关系和等于关系的定义，有R=,S=,。（2）设）设R和和S的关系矩阵分别为的关系矩阵分别为MR和和MS，则有，则有 R1 1 1 1010 1M001 0000 1 S1 0000100M001 0000 1 布尔矩阵的运算布尔矩阵的运算(并并,交交,布尔积布尔积)定义定义6.2.9 如果如果A=(aij)和和B=(bij)是两个是两个mn矩阵矩阵,则则A和和B的并的并是矩阵是矩阵AB=C=(cij),其中：其中：(6.2.2)ijijijijij1a1b1,c1im,1jn0,a0b0
15、 ，如果或如果且定义定义6.2.10 如果如果A=(aij)和和B=(bij)是两个是两个mn矩阵矩阵,则则A和和B的交的交是矩阵是矩阵AB=C=(cij),其中：其中：(6.2.3)ijijijijij1a1b1,c1im,1jn0,a0b0 ，如果且如果或布尔矩阵的运算布尔矩阵的运算(续续)定义定义6.2.11 如果如果A=(aij)是是mp矩阵，矩阵，B=(bij)是是pn矩阵，则矩阵，则A和和B的布尔积的布尔积是矩阵是矩阵A B=C=(cij),其中：其中：ikkjij1,ka1b1,c0,存 在使 得且否 则例例6.2.10令令 、和和 。计算（计算（1）AB；（2）AB；（3）A
16、C。1 0 11 1 11 0 00 0 1 A0 0 01 0 11 1 00 1 1B 0 0 0 11 0 1 11 1 0 0C 1 0 11 1 11 1 00 1 1AB0 0 01 0 11 0 00 0 1AB1 1 0 11 1 1 10 0 0 11 1 0 0AC 6.3 关系的运算关系的运算设设R，S都是从集合都是从集合A到到B的两个关系，则：的两个关系，则：RS|(xRy)(xSy)RS|(xRy)(xSy)R RS|(xRy)(xSy)|(xRy)=ABR6.3.1 关系的关系的复合运算复合运算定义定义6.3.1 设设A,B,C是三个集合，是三个集合，R是从是从A到
17、到B的关系的关系(R:AB)，S是从是从B到到C的关系的关系(S:BC)，则，则R与与S的的复合关系复合关系R S是从是从A到到C的关系，并且：的关系，并且：R S|(xA)(zC)(y)(yB)(xRy)(ySz)运算运算“”称为称为复合运算复合运算。1.RoS 对对任意的任意的 xA 和和 zC,不存在不存在 yB,使得使得 xRy 和和 ySz 同时成立同时成立。2.oRRo。例例6.3.3设设A=a,b,c,d,B=b,c,d,C=a,b,d,R=,是是A到到B的关系，的关系，S=,是是B到到C的关系。的关系。试用关系的试用关系的三种表示方法三种表示方法求求R S。解（解（1）集合表示
18、法）集合表示法:R S=,；bSRoSRabcdabcddcabdabd图图6.3.1 图图6.3.2例例6.3.3的解的解R S0 0 0 10 0 0 1M0 1 0 00 0 0 0 (2)R S的关系图的关系图如图如图6.3.2所示，所示，图图6.3.1是以是以y为为“桥梁桥梁”的情形。的情形。根据图根据图6.3.2得得R S=,；(3)两个定理两个定理定理定理6.3.1 设设A,B,C和和D是任意四个集合是任意四个集合,R,S和和T分别是分别是从从A到到B,B到到C和和C到到D的二元关系的二元关系,则则 （1）(RoS)oT=Ro(SoT)；（2）IAoR=RoIB=R。定理定理6.
19、3.2 设设A,B,C和和D是任意四个集合是任意四个集合,R是从是从A到到B的的关系关系,S1,S2是从是从B到到C的关系的关系,T是从是从C到到D的关系的关系,则则 1)R(S1S2)(R S1)(R S2)2)R(S1S2)(R S1)(R S2)3)(S1S2)T (S1 T)(S2 T)4)(S1S2)T (S1 T)(S2 T)试说明下面的包含关系不一定成立。试说明下面的包含关系不一定成立。（1）(RoS1)(RoS2)Ro(S1S2)（2）(S1oT)(S2oT)(S1S2)oT例例6.3.5分析：分析：如要说明某一事实如要说明某一事实不一定不一定成立，则可成立，则可举一反例加以说
20、明。举一反例加以说明。设设Aa,Bb1,b2,Cc,关系关系R,S1,S2定义如下定义如下:R,S1,S2。则由于则由于S1S2,所以所以 R(S1S2)R ,但但 (R S1),(R S2)，所以所以 (R S1)(R S2)=，即即 (RoS1)(RoS2)Ro(S1S2),这这说明说明(RoS1)(RoS2)Ro(S1S2)不一定成立。不一定成立。例例6.3.5 解（解（1）定义定义6.3.2 设设A，B是两个集合，是两个集合，R是是A到到B的关的关系，则从系，则从B到到A的关系的关系 R-1|R称为称为R的的逆关系逆关系,运算运算“-1”称为称为逆运算逆运算。6.3.2 关系的关系的逆
21、逆运算运算注意：注意：关系是一种集合，逆关系也是一种集合，关系是一种集合，逆关系也是一种集合，因此，如果因此，如果R是一个关系，则是一个关系，则R-1和都是关系，和都是关系，但但R-1和是完全不同的两种关系，千万不要混和是完全不同的两种关系，千万不要混淆。淆。(R-1)-1=R；-1=。RR注意注意（1）将）将R的的关系图关系图中中有向边的方向改变成相反方有向边的方向改变成相反方向向即得即得R-1的关系图，反之亦然；的关系图，反之亦然；（2）将）将R的的关系矩阵关系矩阵转置即得转置即得R-1的关系矩阵，即的关系矩阵，即R和和R-1的关系矩阵互为转置矩阵。的关系矩阵互为转置矩阵。（3）R-1的前
22、域与后域正好是的前域与后域正好是R的后域和前域，即的后域和前域，即 domR=ranR-1，domR-1=ranR；（4）|R|=|R-1|；（5）(RoS)-1=S-1oR-1 (定理定理6.3.3)例例6.3.6设设A=1,2,3,4,B=a,b,c,d,C=2,3,4,5,R是从是从A到到B的一个关系且的一个关系且 R=,S是从是从B到到C的一个关系且的一个关系且S=,。（1）计算）计算R-1，并画出，并画出R和和R-1的关系图；的关系图；（2）写出）写出R和和R-1的关系矩阵；的关系矩阵；（3）计算）计算(RoS)-1和和S-1oR-1。例例6.3.6 解解(1)R-1=,-1 =,，
23、R和和R-1的关系图见图的关系图见图6.3.3和图和图6.3.4。R-1abcd124 图图6.3.3 图图6.3.43R1234abdcABBA例例6.3.6 解（续）解（续）1RR1 0 0 01 0 0 00 0 1 00 0 1 1M,M0 1 0 00 1 0 00 1 0 10 0 0 1(3)RoS=,，故故(RoS)-1=,。R-1=,S-1=,，故故 S-1oR-1=,。（2）R和和R-1的关系矩阵为：的关系矩阵为：设设R，S是从集合是从集合A到集合到集合B的关系，则有的关系，则有 (RS)-1R-1S-1；(分配分配性性)(RS)-1R-1S-1；(R-S)-1R-1-S-
24、1；()-1 ；(可换性可换性)(AB)-1(BA)；S R S-1 R-1；(单调单调性性)定理定理6.3.4RR1 定义定义6.3.3设设R是集合是集合A上的关系，则上的关系，则R的的n次幂，次幂，记为记为Rn,定义如下：定义如下：(1)R0IA|aA；(2)R1；(3)Rn+1Rn RR Rn。6.3.3 关系的关系的幂幂运算运算显然，显然，Rm RnRm+n,(Rm)nRmn。则则Rn也是也是A上的二元关系，上的二元关系，设设A是有限集合，且是有限集合，且|A|n，R是是A上的二元关系，上的二元关系，则：则：niii 1i 1RR 定理定理6.3.5作业作业第第190-191页页 4,
25、7 思考思考:10,12预习预习:6.4 关系的性质关系的性质 6.5 关系的闭包关系的闭包6.4 关系的性质关系的性质 本节涉及到的关系，如无特别声明，本节涉及到的关系，如无特别声明，都都假定其前域和后域相同假定其前域和后域相同。即都为。即都为定义在非空集合定义在非空集合A上的关系。上的关系。6.4.1 关系性质的定义关系性质的定义1、自反性和反自反性、自反性和反自反性定义定义6.4.1设设R是集合是集合A上的关系，上的关系，（1）如果对）如果对 xA,都都有有 R，那么那么 称称R在在A上是上是自反的自反的，或称，或称R具有具有自反性自反性。例如：相等关系。例如：相等关系。（2）如果对任意
26、的）如果对任意的xA，都有，都有 R，那么，那么 称称R在在A上是上是反自反的反自反的，或称，或称R具有具有反自反反自反性性。例如：例如：父子关系。父子关系。符号化：符号化：（1）R在在A上是自反的上是自反的 (x)(xA)(R)=1，（2）R在在A上是反自反的上是反自反的 (x)(xA)(R)=1。根据上面两式分别可得：根据上面两式分别可得：（1）R在在A上上不是不是自反的自反的 (x)(xA R)=1，（2）R在在A上上不是不是反自反的反自反的 (x)(xAR)=1。例例6.4.1设设A=1,2,3，定义，定义A上的关系上的关系R,S和和T如下：如下：（1）R=,；（2）S=,；（3）T=
27、,。解解:(1)R是自反的；是自反的；(2)S是反自反的；是反自反的；(3)T既不是自反的既不是自反的,也不是反自反的。也不是反自反的。例例6.4.1 解法解法（一）（一）(1)因为因为A中中 x，都有，都有R，所以所以R是自反的；是自反的；(2)因为因为A中中 x，都有，都有 S，所以所以S是反自反的；是反自反的；(3)因为存在因为存在2A，使，使 T，所以所以T不是自反的；不是自反的；又因为存在又因为存在1A，使，使T，所以所以T不是反自反的，不是反自反的，即即T既不是自反的，也不是反自反的。既不是自反的，也不是反自反的。例例6.4.1 解（续）解（续）R1 1 0M0 1 00 0 1S
28、0 1 0M0 0 11 0 0T1 1 1M0 0 01 0 1（二）设（二）设R,S和和T的关系矩阵分别为的关系矩阵分别为MR,MS和和MT，则：则：（三）（三）R,S和和T的关系图分别是下图的的关系图分别是下图的(a),(b)和和(c)。133123212 (1)(2)(3)结论：结论：（1）关系）关系R是自反的是自反的R一定一定不是不是反自反的反自反的;（2）存在存在既不是自反的也不是反自反的关系既不是自反的也不是反自反的关系;（3）关系）关系R是自反的是自反的关系图中每个结点都有关系图中每个结点都有自环自环,关系关系R是反自反的是反自反的关系图中每个结点都关系图中每个结点都无自环无自
29、环;（4）关系）关系R是自反的是自反的关系矩阵的关系矩阵的主对角线上全为主对角线上全为1,关系关系R是反自反的是反自反的关系矩阵的关系矩阵的主对角线上全为主对角线上全为0。例例6.4.2设设A=a,b,B=a,b,c,试计算试计算A,B上所有具有上所有具有自反自反性性的关系的关系R的个数。的个数。解解 A上具有自反性的关系上具有自反性的关系R的个数为：的个数为：24-2=4 B上具有自反性的关系上具有自反性的关系R的个数为：的个数为：29-3=64问问:具有具有反自反性反自反性的关系的个数呢的关系的个数呢?2、对称性和反对称性、对称性和反对称性定义定义6.4.2 设设R是集合是集合A上的关系。
30、上的关系。（1）对）对任意任意的的x,yA,如果如果R,那么那么R,则称关系则称关系R是是对称的对称的,或称或称R具有具有对称性对称性;（2）对）对任意任意的的x,yA,如果如果R且且R,那那么么x=y,则称关系则称关系R是是反对称的反对称的,或称或称R具有具有反对称性反对称性。符号化：符号化：（1）R在在A上是对称的上是对称的 (x)(y)(xAyARR)=1,（2）R在在A上是反对称的上是反对称的 (x)(y)(xAyAR Rx=y)=1结论：结论：(1)R在在A上上是对称的是对称的 对对 x,yA,有：有：R并且并且R,或或 R并且并且 R(2)R在在A上上不是对称不是对称的的 x,yA
31、，有，有 R但但 R,或者或者 R但但R(3)R在在A上上是是反对称的反对称的 对对 x,yA,如果如果xy，则则 R 或或 R(4)R在在A上上不是反对称不是反对称的的 x,yA,有有xy,R且且R例例6.4.3设设A=1,2,3,4，定义定义A上的关系上的关系R,S,T和和V如下：如下：a)R=,；b)S=,；c)T=,；d)V=,。试判定它们是否具有试判定它们是否具有对称性和反对称性对称性和反对称性，并写出，并写出R,S,T和和V的的关系矩阵关系矩阵和画出相应的和画出相应的关系图关系图。例例6.4.2 解解(1)a)关系关系R是对称的是对称的,但不是反对称的但不是反对称的；b)关系关系S
32、是反对称的是反对称的,但不是对称的但不是对称的；c)关系关系T既不是对称的既不是对称的,也不是反对称的；也不是反对称的；d)关系关系V既是对称的，也是反对称的。既是对称的，也是反对称的。(2)关系矩阵分别为关系矩阵分别为R1 0 1 00 0 0 0M1 0 0 00 0 0 1 S1 0 1 10 0 0 1M0 0 0 00 0 0 0 T1 1 1 10 0 0 0M1 0 0 00 0 0 0 V1 0 0 00 1 0 0M0 0 1 00 0 0 1(3)关系图分别是关系图分别是1234 (a)(b)(c)(d)123412341234注意注意(1)存在存在既不是对称也不是反对称的
33、关系既不是对称也不是反对称的关系,也存在也存在既是对称也是反对称的关系既是对称也是反对称的关系；(2)关系关系R是对称的是对称的 关系图中任何一对结点之间关系图中任何一对结点之间,要么有方向相反的两条边要么有方向相反的两条边,要么无任何边要么无任何边；关系关系R是反对称的是反对称的 关系图中关系图中任何一对结点之间任何一对结点之间,至多有一条边；至多有一条边；(3)关系关系R是对称的是对称的 R的关系矩阵为的关系矩阵为对称矩阵对称矩阵 关系关系R是反对称的是反对称的 R的关系系矩阵为的关系系矩阵为反对称矩阵反对称矩阵3、传递性、传递性定义定义6.4.3 设设R是集合是集合A上的关系。对任意的上
34、的关系。对任意的x,y,zA,如果如果R且且R，那么，那么R，则，则 称关系称关系R是是传递的传递的,或称或称R具有具有传递性传递性。定义定义6.4.3可符号化为：可符号化为：R在在A上是传递的上是传递的 (x)(y)(z)(xAyA zARRR)=1 例例6.4.3设设A=1,2,3，定义，定义A上的关系上的关系R,S,T 和和 V 如下：如下：（1）R=,；（2）S=；（3）T=,；（4）V=,。试判定它们是否具有传递性。试判定它们是否具有传递性。解解:R,S具有传递性具有传递性;T,V不具有传递性。不具有传递性。总结总结例例6.4.6判定下列关系所具有的特殊性质。判定下列关系所具有的特殊
35、性质。（1）集合）集合A上的上的全关系；全关系；（2）集合）集合A上的上的空关系；空关系；（3）集合）集合A上的上的恒等关系。恒等关系。解解(1)全关系具有全关系具有自反性，对称性和传递性；自反性，对称性和传递性；(2)空关系具有空关系具有反自反性、对称性、反对称性和传反自反性、对称性、反对称性和传递性递性；(3)恒等关系具有恒等关系具有自反性、对称性、反对称性和传自反性、对称性、反对称性和传递性。递性。例例6.4.8假设假设A=a,b,c,d，R=,是是定义在定义在A上的关系。试判定上的关系。试判定R所具有的特殊性质。所具有的特殊性质。解解 R既不是自反的，也不是反自反的；既不是自反的，也不
36、是反自反的；既不是对称的，也不是反对称的；既不是对称的，也不是反对称的；而且也不是传递的而且也不是传递的。即即R不具备关系的任何性质。不具备关系的任何性质。例例6.4.9设设R=,，试判断，试判断R在集合在集合A和和B上具备上具备的特殊性质，其中的特殊性质，其中A=1,2,B=1,2,3。解解 (1)当当R是定义在集合是定义在集合A上的关系时，上的关系时，R是自反、对称、反对称和传递的；是自反、对称、反对称和传递的；(2)当当R是定义在集合是定义在集合B上的关系时上的关系时，R是对称、反对称和传递的。是对称、反对称和传递的。练习练习:P191 1313.设设A=a.b,c,A上的关系上的关系R
37、i定义如下定义如下:(1)R1=,;(2)R2=,;(3)R3=,;(4)R4=;(5)R5=AA判断判断A上的上述关系具备哪些性质。上的上述关系具备哪些性质。定理定理6.4.1 设设R是集合是集合A上的二元关系，则：上的二元关系，则：（1）R是自反的是自反的 IA R；（2）R是反自反的是反自反的RIA；（3）R是对称的是对称的 RR-1；（4）R是反对称的是反对称的RR-1 IA；（5）R是传递的是传递的 R R R。6.4.2 关系性质的判断定理关系性质的判断定理练习练习:P191 1515.设设A=1,2,3,在图在图6.7.1中给出了中给出了16种种A上的关系。上的关系。对于每一种关
38、系图对于每一种关系图,写出相应的关系表达式和关系写出相应的关系表达式和关系矩阵矩阵,并说明它们具备什么性质。并说明它们具备什么性质。定理定理6.4.2 设设R,S是定义在是定义在A上的二元关系，则：上的二元关系，则：(1)若若R,S是是自反自反的的,则则 R-1,RS,RS,R S也是也是自反的自反的；(2)若若R,S是是反自反的反自反的,则则 R-1,RS,RS 也是也是反自反的。反自反的。(3)若若R,S是是对称对称的的,则则 R-1,RS,RS 也是也是对称的对称的。(4)若若R,S是是反对称的反对称的,则则 R-1,RS 也是也是反对称的反对称的。(5)若若R,S是是传递的传递的,则则
39、 R-1,RS 也是也是传递的。传递的。6.4.3 关系性质的保守性关系性质的保守性注意：注意：（1）逆运算与交运算具有较好的保守性；）逆运算与交运算具有较好的保守性；（2）并运算、差运算和复合运算的保守性较差。）并运算、差运算和复合运算的保守性较差。6.5 关系的闭包运算关系的闭包运算对于一个给定的关系，可能不具有某一个特殊性质。对于一个给定的关系，可能不具有某一个特殊性质。但是，如果但是，如果我们希望它具有该特定的性质，那么应我们希望它具有该特定的性质，那么应该怎么做呢？该怎么做呢？例如，对给定集合例如，对给定集合A=1,2,3上的关系上的关系 R=,，它不具有自反性。，它不具有自反性。根
40、据自反性的定义根据自反性的定义,添加添加,这两个元素后这两个元素后,所得到的新关系就具有自反性。所得到的新关系就具有自反性。另外，还可以另外，还可以添加添加,得到的新得到的新关系仍然具有自反性。关系仍然具有自反性。6.5.1关系的闭包关系的闭包定义定义6.5.1 设设R是定义在是定义在A上的关系，若上的关系，若,R R,满足：满足：（1）R是是自反的自反的(对称的对称的、或、或)；（2）对任何）对任何自反的自反的(对称的对称的、或、或)关系关系R,如果如果 R R,就有就有 R R,则称则称为为R的的自反闭包自反闭包(对称闭包对称闭包、或、或),记为记为 r(R)(s(R)、或、或。显然显然,
41、例例6.5.1设设A=1,2,3，R=,是是A上的上的关系。关系。试求试求R的自反闭包、对称闭包和传递闭包。的自反闭包、对称闭包和传递闭包。解解 由关系的自反性定义知，由关系的自反性定义知，R是自反的当且仅当对是自反的当且仅当对aA，都有，都有R，因此，在因此，在R中添中添和和后得到的新关系就后得到的新关系就具有自反性，且满足自反闭包的定义，即具有自反性，且满足自反闭包的定义，即 r(R)=,;例例6.5.1(续续)由关系的对称性定义知，在由关系的对称性定义知，在R中添上中添上后得到的后得到的新关系就具有对称性，且满足对称闭包的定义，即新关系就具有对称性，且满足对称闭包的定义，即 s(R)=,
42、；由关系的传递性定义知，在由关系的传递性定义知，在R中添上中添上和和后得到的新关系就具有传递性，且满足传递闭包的后得到的新关系就具有传递性，且满足传递闭包的定义。即定义。即 t(R)=,。例例6.5.2求下列关系的求下列关系的r(R),s(R)和和t(R)。（1）定义在整数集）定义在整数集Z上的上的“”关系；关系；（2）定义在整数集）定义在整数集Z上的上的“=”关系。关系。例例6.5.2 解解（1）定义在）定义在Z上的上的“”关系的关系的 r(R)为为“”，s(R)为为“”，t(R)为为“”；（2）定义在）定义在Z上的上的“=”关系的关系的 r(R)为为“=”，s(R)为为“=”，t(R)为为
43、“=”。例例6.5.3设集合设集合A=1,2,3,4，R=,是定义在是定义在A上的二元关系。上的二元关系。（1）画出）画出R的关系图；的关系图；（2）求出）求出r(R),s(R),t(R),并画出其相应的关系图。并画出其相应的关系图。解解（1）R的关系图见下图；的关系图见下图；2413例例6.5.3（续）（续）（2）r(R)=,；s(R)=,；t(R)=,。r(R)，s(R)，t(R)的关系图分别如下：的关系图分别如下：r(R)s(R)t(R)123412341234总结总结利用关系图求关系利用关系图求关系R闭包的方法：闭包的方法：（1）检查）检查R的关系图，的关系图，在没有自环的结点处加上在
44、没有自环的结点处加上自环自环，可得，可得r(R)的关系图；的关系图；（2）检查）检查R的关系图，的关系图，将每条单向边全部改成双将每条单向边全部改成双向边，向边，可得可得s(R)的关系图；的关系图；（3）检查）检查R的关系图，的关系图，从每个结点出发，找到其从每个结点出发，找到其终点，如果该结点到其终点没有边相连，就加上此终点，如果该结点到其终点没有边相连，就加上此边，边，可得可得t(R)的关系图。的关系图。设设R是集合是集合A上的二元关系，则：上的二元关系，则：（1）r(R)RIA。（2）s(R)RR-1。（3）t(R)，若若|A|n，则，则t(R)。Ri1i Rin1i 定理定理6.5.1
45、作业作业第第192页页 16,17 思考思考:18,19预习预习:7.2 等价关系等价关系6.6 本章总结本章总结1、序偶和笛卡儿积的概念、序偶和笛卡儿积的概念2、二元关系的概念和表示、二元关系的概念和表示3、关系的交、并、补、差运算、复合运算和逆运算、关系的交、并、补、差运算、复合运算和逆运算4、关系性质的定义、关系性质的判定、关系性质的、关系性质的定义、关系性质的判定、关系性质的证明和关系性质的保守性；证明和关系性质的保守性；5、关系的自反、对称、和传递闭包的概念及计算。、关系的自反、对称、和传递闭包的概念及计算。习题类型习题类型（1）基本概念题：基本概念题：涉及关系性质的判定，关系性涉及
46、关系性质的判定，关系性质的保守性；质的保守性；（2）判断题：）判断题：涉及关系性质的保守性涉及关系性质的保守性；（3）计算题：计算题：涉及关系的运算和闭包的计算；涉及关系的运算和闭包的计算；（4）证明题：证明题：涉及关系性质的证明，关系运算律涉及关系性质的证明，关系运算律的证明的证明。P190 4.设设A=0,1,2,3,R和和S是是A上的二元关系上的二元关系 R=|(j=i+1)或或(j=i/2);S=|(i=j+2).(1)用关系矩阵法求用关系矩阵法求R S;(2)用关系图法求用关系图法求S R;(3)用任意方法求用任意方法求 R S R,R3,S3.解解 R和和S的关系矩阵分别为的关系矩
47、阵分别为 故故 R S的关系矩阵为的关系矩阵为R11000010M01010000 S00000000M10000100 R SRS00001000MMM01000000 题题4的答案（续）的答案（续）(2)S R的关系图为的关系图为(3)R S R,R3,S3的关系矩阵分别为的关系矩阵分别为0132R S R00001100M00100000 3R11110010M01010000 3S00000000M00000000 P191 7.7.设设A=,B=,.求求 A B,A B,domA,domB,ranA,ranB,dom(A B),ran(A B),A B.解解:A B=,;A B=;d
48、omA=1,2,3;domB=1,2,4;ranA=2,3,4=ranB;dom(A B)=1,2,3,4;ran(A B)=4 A B=,.P191 16.下述关系具有哪些性质下述关系具有哪些性质(1)Z上的关系上的关系R=|(x,yZ)(xy);(2)Z上的关系上的关系R=|(xZ)(x0);(3)任意集合任意集合A上的恒等关系上的恒等关系 IA=|xA;(4)B=1,2,3,10上的关系上的关系 R=|(x,yB)(x+y=10).答答:(1),;(2)反对称反对称;(3),;(4)对称对称.xP191 17.求闭包求闭包(图图(a),(b)1243s(Ra)1243t(Ra)1243r(Ra)1243 Ra 1243 Rb 1243r(Rb)1243s(Rb)1243t(Rb)P191 17.求闭包求闭包(图图(c),(d)1243 Rc 1243r(Rc)1243s(Rc)1243t(Rc)1243 Rd 1243r(Rd)1243s(Rd)1243t(Rd)P191 17.求闭包求闭包(图图(e),(f)1243 Re 1243r(Re)1243s(Re)1243t(Re)1243 Rf 1243r(Rf)1243s(Rf)1243t(Rf)
