离散数学PPT电子教案第06章二元关系.ppt

离散数学,2023年3月6日星期一,2023/3/6,第三篇 二元关系,第6章 二元关系,2023/3/6,6.0 内容提要,2023/3/6,6.1本章学习要求,2023/3/6,第三篇 二元关系,关系理论历史悠久。它与集合论、数理逻辑、组合学、图论和布尔代数都有密切的联系。关系是日常生活以及数学中的一个基本概念,例如:兄弟关系,师生关系,位置关系,大小关系,等于关系,包含关系等。,2023/3/6,6.2 二元关系,6.2.1 序偶与笛卡尔积,特征：成对出现、具有一定的顺序。,定义6.2.1由两个元素x,y按照一定的次序组成的二元组称为有序偶对(序偶),记作,其中x为第一个元素，y为第二个元素。,定义6.2.2 给定序偶 和，如果a=c,b=d，则=。,2023/3/6,N重有序组,定义6.2.3 由n个元素a1,a2,a3,an按照一定次序组成的n元组称为n重有序组，记作:,定义6.2.4 给定两个n重有序组 和。如果aibi(i1,2,，n),则=。,2023/3/6,笛卡尔乘积,定义6.2.5设A，B是两个集合，称集合：AB|(xA)(yB)为集合A与B的笛卡尔积。,注意：（1）集合A与B的笛卡儿积 AB 仍然是集合；（2）笛卡尔积AB中的元素是序偶。,2023/3/6,例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)=,;(AB)D=,1,2,1,2。,2023/3/6,注意,由例6.2.3我们可以看出：（1）笛卡儿积不满足交换律,即 AB BA;（2）AB=当且仅当 A=或者B=；（3）笛卡儿积不满足结合律,即A(BD)(AB)D；（4）对有限集A,B，有|AB|=|BA|=|A|B|。,2023/3/6,两个定理,定理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)AC,BD。,2023/3/6,n个集合的笛卡尔集,定义6.2.6 设A1,A2,An是n个集合，称集合 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|。,2023/3/6,定义6.2.7 设A,B为两个非空集合，称AB的任何子集R为从A到B的二元关系，简称关系。如果 AB，则称R为A上的二元关系。,6.2.2 二元关系的定义,特别地，当R=时，称R为空关系；当R=AB时，称R为全关系。,集合,2023/3/6,例6.2.4,假设A=a,b,B=c,d,试写出从A到B的所有不同关系.解 因为A=a,b,B=c,d，所以AB=,。于是AB的所有不同子集为：0元子集：；1元子集:,；2元子集:,;,2023/3/6,例6.2.4 解（续）,3元子集：,；4元子集：,。,注意:当集合A,B都是有限集时，AB共有 2|A|B|个不同的子集，即，从A到B的不同关系共有 2|A|B|个。,2023/3/6,其中,A称为R的前域,B称为R的后域。DA,CB 满足:Dx|R,Cy|R。称D为R的定义域，记为DdomR；称C为R的值域,记CranR;并称 fldRDC 为R的域。,2023/3/6,求定义在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）domR2=7,7,ranR2=7,7,fldR2=7,7。,例6.2.5,2023/3/6,练习:P190 1(1)(3),1.给定集合:A=1,7,B=0,3,5,C=1,2.(1)写出A对B的关系,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元关系。,2023/3/6,6.2.3 关系的表示法,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)。,2023/3/6,6.2.3 关系的表示法,2.关系图法(1)AB 设Aa1,a2,.,an,Bb1,b2,.,bm，R是从A到B的一个二元关系，则规定R的关系图如下：设a1,a2,.,an和b1,b2,.,bm分别为图中的结点,用“。”表示；,如 R,则从ai到bj可用有向边 ai。bj 相连。为对应图中的有向边。,2023/3/6,（2)A=B设AB,R是A上的关系,则R的关系图规定如下：设a1,a2,.,an为图中节点，用“。”表示 如R,则从ai到aj可用有向边ai。aj相连。为对应图中的有向边。如R,则从ai到ai用一带箭头的小圆环表示，即：ai。,2.关系图法（续）,2023/3/6,例6.2.8,试用关系图表示下面的关系。（1）设A=2,3,4，B=3,4,5,6，则A到B之间的一种整除关系R1=,（2）假设A=1,2,3,4，则A上的小于等于关系R2=,。,2023/3/6,例6.2.8 解,（1）关系R1的关系图如图6.2.3所示；（2）关系R2的关系图如图6.2.4所示。,2023/3/6,设Aa1,a2,.,an,Bb1,b2,.,bm,R是从A到B的一个二元关系，称矩阵 MR(rij)nm为关系R的关系矩阵，其中又称MR为R的邻接矩阵。,3.关系矩阵,注意：A中元素序号对应矩阵元素的行下标，B中元素序号对应矩阵元素的列下标；关系矩阵是0-1矩阵，称为布尔矩阵。,2023/3/6,例6.2.9,设A=1,2,3,4，考虑A上的 整除关系R 和 等于关系S。（1）试写出R和S中的所有元素；（2）试写出R和S的关系矩阵。,2023/3/6,例6.2.9解,（1）根据整除关系和等于关系的定义，有R=,S=,。（2）设R和S的关系矩阵分别为MR和MS，则有,2023/3/6,布尔矩阵的运算(并,交,布尔积),定义6.2.9 如果A=(aij)和B=(bij)是两个mn矩阵,则A和B的并是矩阵AB=C=(cij),其中：(6.2.2),定义6.2.10 如果A=(aij)和B=(bij)是两个mn矩阵,则A和B的交是矩阵AB=C=(cij),其中：(6.2.3),2023/3/6,布尔矩阵的运算(续),定义6.2.11 如果A=(aij)是mp矩阵，B=(bij)是pn矩阵，则A和B的布尔积是矩阵AB=C=(cij),其中：,2023/3/6,例6.2.10,令、和。计算（1）AB；（2）AB；（3）AC。,2023/3/6,6.3 关系的运算,设R，S都是从集合A到B的两个关系，则：RS|(xRy)(xSy)RS|(xRy)(xSy),2023/3/6,6.3.1 关系的复合运算,定义6.3.1 设A,B,C是三个集合，R是从A到B的关系(R:AB)，S是从B到C的关系(S:BC)，则R与S的复合关系RS是从A到C的关系，并且：RS|(xA)(zC)(y)(yB)(xRy)(ySz)运算“”称为复合运算。,1.RoS 对任意的 xA 和 zC,不存在 yB,使得 xRy 和 ySz 同时成立。2.oRRo。,2023/3/6,例6.3.3,设A=a,b,c,d,B=b,c,d,C=a,b,d,R=,是A到B的关系，S=,是B到C的关系。试用关系的三种表示方法求RS。,解（1）集合表示法:RS=,；,2023/3/6,例6.3.3的解,(2)RS的关系图如图6.3.2所示，图6.3.1是以y为“桥梁”的情形。根据图6.3.2得RS=,；(3),2023/3/6,两个定理,定理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.3.2 设A,B,C和D是任意四个集合,R是从A到B的关系,S1,S2是从B到C的关系,T是从C到D的关系,则 1)R(S1S2)(RS1)(RS2)2)R(S1S2)(RS1)(RS2)3)(S1S2)T(S1T)(S2T)4)(S1S2)T(S1T)(S2T),2023/3/6,试说明下面的包含关系不一定成立。（1）(RoS1)(RoS2)Ro(S1S2)（2）(S1oT)(S2oT)(S1S2)oT,例6.3.5,分析：如要说明某一事实不一定成立，则可举一反例加以说明。,2023/3/6,设Aa,Bb1,b2,Cc,关系R,S1,S2定义如下:R,S1,S2。则由于S1S2,所以 R(S1S2)R,但(RS1),(RS2)，所以(RS1)(RS2)=，即(RoS1)(RoS2)Ro(S1S2),这说明(RoS1)(RoS2)Ro(S1S2)不一定成立。,例6.3.5 解（1）,2023/3/6,定义6.3.2 设A，B是两个集合，R是A到B的关系，则从B到A的关系 R-1|R称为R的逆关系,运算“-1”称为逆运算。,6.3.2 关系的逆运算,注意：关系是一种集合，逆关系也是一种集合，因此，如果R是一个关系，则R-1和都是关系，但R-1和是完全不同的两种关系，千万不要混淆。(R-1)-1=R；-1=。,2023/3/6,注意,（1）将R的关系图中有向边的方向改变成相反方向即得R-1的关系图，反之亦然；（2）将R的关系矩阵转置即得R-1的关系矩阵，即R和R-1的关系矩阵互为转置矩阵。（3）R-1的前域与后域正好是R的后域和前域，即 domR=ranR-1，domR-1=ranR；（4）|R|=|R-1|；（5）(RoS)-1=S-1oR-1(定理6.3.3),2023/3/6,例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。,2023/3/6,例6.3.6 解,(1)R-1=,-1=,，R和R-1的关系图见图6.3.3和图6.3.4。,2023/3/6,例6.3.6 解（续）,(3)RoS=,，故(RoS)-1=,。R-1=,S-1=,，故 S-1oR-1=,。,（2）R和R-1的关系矩阵为：,2023/3/6,设R，S是从集合A到集合B的关系，则有(RS)-1R-1S-1；(分配性)(RS)-1R-1S-1；(R-S)-1R-1-S-1；()-1；(可换性)(AB)-1(BA)；SR S-1R-1；(单调性),定理6.3.4,2023/3/6,定义6.3.3设R是集合A上的关系，则R的n次幂，记为Rn,定义如下：(1)R0IA|aA；(2)R1；(3)Rn+1RnRRRn。,6.3.3 关系的幂运算,显然，RmRnRm+n,(Rm)nRmn。,则Rn也是A上的二元关系，,2023/3/6,设A是有限集合，且|A|n，R是A上的二元关系，则：,定理6.3.5,2023/3/6,作业,第190-191页 4,7 思考:10,12预习:6.4 关系的性质 6.5 关系的闭包,2023/3/6,6.4 关系的性质,本节涉及到的关系，如无特别声明，都假定其前域和后域相同。即都为定义在非空集合A上的关系。,2023/3/6,6.4.1 关系性质的定义,1、自反性和反自反性定义6.4.1设R是集合A上的关系，（1）如果对 xA,都有 R，那么 称R在A上是自反的，或称R具有自反性。例如：相等关系。（2）如果对任意的xA，都有 R，那么 称R在A上是反自反的，或称R具有反自反性。例如：父子关系。,2023/3/6,符号化：,（1）R在A上是自反的(x)(xA)(R)=1，（2）R在A上是反自反的(x)(xA)(R)=1。根据上面两式分别可得：（1）R在A上不是自反的(x)(xAR)=1，（2）R在A上不是反自反的(x)(xAR)=1。,2023/3/6,例6.4.1,设A=1,2,3，定义A上的关系R,S和T如下：（1）R=,；（2）S=,；（3）T=,。解:(1)R是自反的；(2)S是反自反的；(3)T既不是自反的,也不是反自反的。,2023/3/6,例6.4.1 解法,（一）(1)因为A中x，都有R，所以R是自反的；(2)因为A中x，都有S，所以S是反自反的；(3)因为存在2A，使T，所以T不是自反的；又因为存在1A，使T，所以T不是反自反的，即T既不是自反的，也不是反自反的。,2023/3/6,例6.4.1 解（续）,（二）设R,S和T的关系矩阵分别为MR,MS和MT，则：（三）R,S和T的关系图分别是下图的(a),(b)和(c)。,2023/3/6,结论：,（1）关系R是自反的R一定不是反自反的;（2）存在既不是自反的也不是反自反的关系;（3）关系R是自反的关系图中每个结点都有自环,关系R是反自反的关系图中每个结点都无自环;（4）关系R是自反的关系矩阵的主对角线上全为1,关系R是反自反的关系矩阵的主对角线上全为0。,2023/3/6,例6.4.2,设A=a,b,B=a,b,c,试计算A,B上所有具有自反性的关系R的个数。解 A上具有自反性的关系R的个数为：24-2=4 B上具有自反性的关系R的个数为：29-3=64问:具有反自反性的关系的个数呢?,2023/3/6,2、对称性和反对称性,定义6.4.2 设R是集合A上的关系。（1）对任意的x,yA,如果R,那么R,则称关系R是对称的,或称R具有对称性;（2）对任意的x,yA,如果R且R,那么x=y,则称关系R是反对称的,或称R具有反对称性。,2023/3/6,符号化：,（1）R在A上是对称的(x)(y)(xAyARR)=1,（2）R在A上是反对称的(x)(y)(xAyAR Rx=y)=1,2023/3/6,结论：,(1)R在A上是对称的 对x,yA,有：R并且R,或 R并且R(2)R在A上不是对称的 x,yA，有 R但R,或者R但R(3)R在A上是反对称的 对x,yA,如果xy，则R 或 R(4)R在A上不是反对称的 x,yA,有xy,R且R,2023/3/6,例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的关系矩阵和画出相应的关系图。,2023/3/6,例6.4.2 解,(1)a)关系R是对称的,但不是反对称的；b)关系S是反对称的,但不是对称的；c)关系T既不是对称的,也不是反对称的；d)关系V既是对称的，也是反对称的。(2)关系矩阵分别为,(3)关系图分别是,2023/3/6,注意,(1)存在既不是对称也不是反对称的关系,也存在既是对称也是反对称的关系；(2)关系R是对称的 关系图中任何一对结点之间,要么有方向相反的两条边,要么无任何边；关系R是反对称的 关系图中任何一对结点之间,至多有一条边；(3)关系R是对称的 R的关系矩阵为对称矩阵 关系R是反对称的 R的关系系矩阵为反对称矩阵,2023/3/6,3、传递性,定义6.4.3 设R是集合A上的关系。对任意的x,y,zA,如果R且R，那么R，则 称关系R是传递的,或称R具有传递性。定义6.4.3可符号化为：R在A上是传递的(x)(y)(z)(xAyA zARRR)=1,2023/3/6,例6.4.3,设A=1,2,3，定义A上的关系R,S,T 和 V 如下：（1）R=,；（2）S=；（3）T=,；（4）V=,。试判定它们是否具有传递性。解:R,S具有传递性;T,V不具有传递性。,2023/3/6,总结,2023/3/6,例6.4.6,判定下列关系所具有的特殊性质。（1）集合A上的全关系；（2）集合A上的空关系；（3）集合A上的恒等关系。解(1)全关系具有自反性，对称性和传递性；(2)空关系具有反自反性、对称性、反对称性和传递性；(3)恒等关系具有自反性、对称性、反对称性和传递性。,2023/3/6,例6.4.8,假设A=a,b,c,d，R=,是定义在A上的关系。试判定R所具有的特殊性质。解 R既不是自反的，也不是反自反的；既不是对称的，也不是反对称的；而且也不是传递的。即R不具备关系的任何性质。,2023/3/6,例6.4.9,设R=,，试判断R在集合A和B上具备的特殊性质，其中A=1,2,B=1,2,3。解(1)当R是定义在集合A上的关系时，R是自反、对称、反对称和传递的；(2)当R是定义在集合B上的关系时，R是对称、反对称和传递的。,2023/3/6,练习:P191 13,13.设A=a.b,c,A上的关系Ri定义如下:(1)R1=,;(2)R2=,;(3)R3=,;(4)R4=;(5)R5=AA判断A上的上述关系具备哪些性质。,2023/3/6,定理6.4.1 设R是集合A上的二元关系，则：（1）R是自反的 IAR；（2）R是反自反的RIA；（3）R是对称的 RR-1；（4）R是反对称的RR-1IA；（5）R是传递的 RR R。,6.4.2 关系性质的判断定理,2023/3/6,练习:P191 15,15.设A=1,2,3,在图6.7.1中给出了16种A上的关系。对于每一种关系图,写出相应的关系表达式和关系矩阵,并说明它们具备什么性质。,2023/3/6,定理6.4.2 设R,S是定义在A上的二元关系，则：(1)若R,S是自反的,则 R-1,RS,RS,RS也是自反的；(2)若R,S是反自反的,则 R-1,RS,RS 也是反自反的。(3)若R,S是对称的,则 R-1,RS,RS 也是对称的。(4)若R,S是反对称的,则 R-1,RS 也是反对称的。(5)若R,S是传递的,则 R-1,RS 也是传递的。,6.4.3 关系性质的保守性,注意：（1）逆运算与交运算具有较好的保守性；（2）并运算、差运算和复合运算的保守性较差。,2023/3/6,6.5 关系的闭包运算,对于一个给定的关系，可能不具有某一个特殊性质。但是，如果我们希望它具有该特定的性质，那么应该怎么做呢？例如，对给定集合A=1,2,3上的关系 R=,，它不具有自反性。根据自反性的定义,添加,这两个元素后,所得到的新关系就具有自反性。另外，还可以添加,得到的新关系仍然具有自反性。,2023/3/6,6.5.1关系的闭包,定义6.5.1 设R是定义在A上的关系，若存在A上的另一个关系R,R R,满足：（1）R是自反的(对称的、或传递的)；（2）对任何自反的(对称的、或传递的)关系R,如果 R R,就有 R R,则称R为R的自反闭包(对称闭包、或传递闭包),记为 r(R)(s(R)、或t(R)。显然,关系的闭包是增加最少元素,使其具备所需性质的扩充。,2023/3/6,例6.5.1,设A=1,2,3，R=,是A上的关系。试求R的自反闭包、对称闭包和传递闭包。解 由关系的自反性定义知，R是自反的当且仅当对aA，都有R，因此，在R中添和后得到的新关系就具有自反性，且满足自反闭包的定义，即 r(R)=,;,2023/3/6,例6.5.1(续),由关系的对称性定义知，在R中添上后得到的新关系就具有对称性，且满足对称闭包的定义，即 s(R)=,；由关系的传递性定义知，在R中添上和后得到的新关系就具有传递性，且满足传递闭包的定义。即 t(R)=,。,2023/3/6,例6.5.2,求下列关系的r(R),s(R)和t(R)。（1）定义在整数集Z上的“”关系；（2）定义在整数集Z上的“=”关系。,2023/3/6,例6.5.2 解,（1）定义在Z上的“”关系的 r(R)为“”，s(R)为“”，t(R)为“”；（2）定义在Z上的“=”关系的 r(R)为“=”，s(R)为“=”，t(R)为“=”。,2023/3/6,例6.5.3,设集合A=1,2,3,4，R=,是定义在A上的二元关系。（1）画出R的关系图；（2）求出r(R),s(R),t(R),并画出其相应的关系图。解（1）R的关系图见下图；,2023/3/6,例6.5.3（续）（2）,r(R)=,；s(R)=,；t(R)=,。r(R)，s(R)，t(R)的关系图分别如下：,2023/3/6,总结,利用关系图求关系R闭包的方法：（1）检查R的关系图，在没有自环的结点处加上自环，可得r(R)的关系图；（2）检查R的关系图，将每条单向边全部改成双向边，可得s(R)的关系图；（3）检查R的关系图，从每个结点出发，找到其终点，如果该结点到其终点没有边相连，就加上此边，可得t(R)的关系图。,2023/3/6,设R是集合A上的二元关系，则：（1）r(R)RIA。（2）s(R)RR-1。（3）t(R)，若|A|n，则t(R)。,定理6.5.1,2023/3/6,作业,第192页 16,17 思考:18,19预习:7.2 等价关系,2023/3/6,6.6 本章总结,1、序偶和笛卡儿积的概念2、二元关系的概念和表示3、关系的交、并、补、差运算、复合运算和逆运算4、关系性质的定义、关系性质的判定、关系性质的证明和关系性质的保守性；5、关系的自反、对称、和传递闭包的概念及计算。,2023/3/6,习题类型,（1）基本概念题：涉及关系性质的判定，关系性质的保守性；（2）判断题：涉及关系性质的保守性；（3）计算题：涉及关系的运算和闭包的计算；（4）证明题：涉及关系性质的证明，关系运算律的证明。,2023/3/6,P190 4.设A=0,1,2,3,R和S是A上的二元关系,R=|(j=i+1)或(j=i/2);S=|(i=j+2).(1)用关系矩阵法求RS;(2)用关系图法求SR;(3)用任意方法求 RSR,R3,S3.解 R和S的关系矩阵分别为 故 RS的关系矩阵为,2023/3/6,题4的答案（续）,(2)SR的关系图为(3)RSR,R3,S3的关系矩阵分别为,2023/3/6,P191 7.,7.设A=,B=,.求 AB,AB,domA,domB,ranA,ranB,dom(AB),ran(AB),AB.解:AB=,;AB=;domA=1,2,3;domB=1,2,4;ranA=2,3,4=ranB;dom(AB)=1,2,3,4;ran(AB)=4 AB=,.,2023/3/6,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)对称.,2023/3/6,P191 17.求闭包(图(a),(b),2023/3/6,P191 17.求闭包(图(c),(d),2023/3/6,P191 17.求闭包(图(e),(f),