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

《离散数学PPT电子教案-第06章_二元关系.ppt》由会员分享，可在线阅读，更多相关《离散数学PPT电子教案-第06章_二元关系.ppt（89页珍藏版）》请在三一文库上搜索。

1、离散数学,2020年1月29日星期三,2020/1/29,第三篇 二元关系,第6章 二元关系,2020/1/29,6.0 内容提要,2020/1/29,6.1本章学习要求,2020/1/29,第三篇 二元关系,关系理论历史悠久。它与集合论、数理逻辑、组合学、图论和布尔代数都有密切的联系。 关系是日常生活以及数学中的一个基本概念, 例如: 兄弟关系, 师生关系, 位置关系, 大小关系, 等于关系, 包含关系等。,2020/1/29,6.2 二元关系,6.2.1 序偶与笛卡尔积,特征：成对出现、具有一定的顺序。,定义6.2.1 由两个元素x,y按照一定的次序组成的二元组称为有序偶对(序偶), 记作

2、, 其中x为第一个元素，y为第二个元素。,定义6.2.2 给定序偶 和 ， 如果a=c, b=d，则 =。,2020/1/29,N重有序组,定义6.2.3 由n个元素a1,a2,a3,an按照一定次序组成的n元组称为n重有序组，记作:,定义6.2.4 给定两个n重有序组 和 。如果aibi (i1,2,，n), 则 =。,2020/1/29,笛卡尔乘积,定义6.2.5设A，B是两个集合，称集合： AB|(xA)(yB) 为集合A与B的笛卡尔积。,注意： （1）集合A与B的笛卡儿积 AB 仍然是集合； （2）笛卡尔积AB中的元素是序偶。,2020/1/29,例6.2.3,设A=a, B=b,c,

3、 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。,2020/1/29,注意,由例6.2.3我们可以看出： （1）笛卡儿积不满足交换律, 即 AB BA; （2）AB= 当且仅当 A=或者B=； （3）笛卡儿积不满足结合律, 即 A(BD) (AB)D ； （4）对有限集A,B，有 |AB|=|BA|=|A|B|。,2020/1/29,两个定理,定理6.2

4、.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。,2020/1/29,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

5、|A2|An|。,2020/1/29,定义6.2.7 设A,B为两个非空集合，称AB的任何子集R为从A到B的二元关系，简称关系。 如果 AB，则称R为A上的二元关系。,6.2.2 二元关系的定义,特别地，当R=时，称R为空关系； 当R=AB时，称R为全关系。,集合,2020/1/29,例6.2.4,假设A=a,b, B=c,d, 试写出从A到B的所有不同关系. 解 因为A=a,b,B=c,d，所以 AB=,。 于是AB的所有不同子集为： 0元子集：； 1元子集: , , , ； 2元子集: , , , , , ,;,2020/1/29,例6.2.4 解（续）,3元子集： , , , ,； 4元

6、子集： ,。,注意: 当集合A,B都是有限集时，AB共有 2|A|B| 个不同的子集，即， 从A到B的不同关系共有 2|A|B| 个。,2020/1/29,其中, A称为R的前域, B称为R的后域。DA, CB 满足: Dx|R, Cy|R。称D为R的定义域，记为DdomR；称C为R的值域, 记CranR;并称 fldRDC 为R的域。,2020/1/29,求定义在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, ranR

7、2=7,7, fldR2=7,7。,例6.2.5,2020/1/29,练习: 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元关系。,2020/1/29,6.2.3 关系的表示法,1.集合表示法（枚举法和叙述法） 例6.2.7（1）设A=a,B=b,c，用枚举法写出从A到B的不同关系； （2）用叙述法写出定义在R上的“相等”关

8、系。 解（1）A到B的不同关系有：R1=, R2=, R3=, R4=,； （2）设R上的“相等”关系为S，则 S=|(x,yR)(x=y)。,2020/1/29,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 相连。为对应图中的有向边。,2020/1/29,（2)A=B 设AB, R是A上的关系, 则R的关系图规定如下： 设a1,a2,.,an为图中

9、节点，用 “。”表示 如R, 则从ai到aj可用有向边ai。 。aj相连。为对应图中的有向边。 如R,则从ai到ai用一带箭头的小圆环表示，即： ai。,2.关系图法（续）,2020/1/29,例6.2.8,试用关系图表示下面的关系。 （1）设A=2,3,4，B=3,4,5,6，则A到B之间的一种整除关系R1=, （2）假设A=1,2,3,4，则A上的小于等于关系R2= , , , 。,2020/1/29,例6.2.8 解,（1）关系R1的关系图如图6.2.3所示； （2）关系R2的关系图如图6.2.4所示。,2020/1/29,设Aa1,a2,.,an, Bb1,b2,.,bm, R是从A到

10、B的一个二元关系，称矩阵 MR(rij)nm为关系R的关系矩阵，其中 又称MR为R的邻接矩阵。,3.关系矩阵,注意：A中元素序号对应矩阵元素的行下标， B中元素序号对应矩阵元素的列下标； 关系矩阵是0-1矩阵，称为布尔矩阵。,2020/1/29,例6.2.9,设A = 1, 2, 3, 4， 考虑A上的 整除关系R 和 等于关系S。 （1）试写出R和S中的所有元素； （2）试写出R和S的关系矩阵。,2020/1/29,例6.2.9 解,（1）根据整除关系和等于关系的定义，有 R=, S=,。 （2）设R和S的关系矩阵分别为MR和MS，则有,2020/1/29,布尔矩阵的运算 (并, 交, 布尔

11、积),定义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),2020/1/29,布尔矩阵的运算(续),定义6.2.11 如果A=(aij)是mp矩阵，B=(bij)是pn矩阵，则A和B的布尔积是矩阵AB=C=(cij),其中：,2020/1/29,例6.2.10,令 、 和 。 计算（1）AB； （2）AB； （3）AC。,2020/1/29,6.3 关系的运算,设R，S都是从集合A到B的

12、两个关系，则： RS|(xRy)(xSy) RS|(xRy)(xSy),2020/1/29,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。,2020/1/29,例6.3.3,设A=a,b,c,d,B=b,c,d,C=a,b,d, R=,是A到B的关系，S=,是B到C的

13、关系。 试用关系的三种表示方法求RS。,解（1）集合表示法: RS=,；,2020/1/29,例6.3.3的解,(2) RS的关系图 如图6.3.2所示， 图6.3.1是以y为 “桥梁”的情形。 根据图6.3.2得 RS=,； (3),2020/1/29,两个定理,定理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(S

14、1S2) (RS1)(RS2) 2) R(S1S2) (RS1)(RS2) 3) (S1S2)T (S1T)(S2T) 4) (S1S2)T (S1T)(S2T),2020/1/29,试说明下面的包含关系不一定成立。 （1）(RoS1)(RoS2) Ro(S1S2) （2）(S1oT)(S2oT) (S1S2)oT,例6.3.5,分析：如要说明某一事实不一定成立，则可举一反例加以说明。,2020/1/29,设Aa, Bb1,b2, Cc, 关系R,S1,S2定义如下: R, S1, S2。 则由于S1S2, 所以 R(S1S2) R , 但 (RS1), (RS2)， 所以 (RS1)(RS2

15、) = ， 即 (RoS1)(RoS2) Ro(S1S2), 这说明 (RoS1)(RoS2)Ro(S1S2) 不一定成立。,例6.3.5 解（1）,2020/1/29,定义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=。,2020/1/29,注意,（1）将R的关系图中有向边的方向改变成相反方向即得R-1的关系图，反之亦然； （

16、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),2020/1/29,例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。,2020/1/29,例6.3.6

17、解,(1)R-1=,-1 =,， R和R-1的关系图见图6.3.3和图6.3.4。,2020/1/29,例6.3.6 解（续）,(3) RoS=,， 故 (RoS)-1=,。 R-1=, S-1=,， 故 S-1oR-1=,。,（2）R和R-1的关系矩阵为：,2020/1/29,设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,2020/1/29,定义6.3.3 设R是集合A上的关系，则R的n次幂，记为R

18、n,定义如下： (1) R0IA|aA； (2) R1； (3) Rn+1RnRRRn。,6.3.3 关系的幂运算,显然，RmRnRm+n, (Rm)nRmn。,则Rn也是A上的二元关系，,2020/1/29,设A是有限集合，且|A|n，R是A上的二元关系，则：,定理6.3.5,2020/1/29,作业,第190-191页 4, 7 思考: 10, 12 预习: 6.4 关系的性质 6.5 关系的闭包,2020/1/29,6.4 关系的性质,本节涉及到的关系，如无特别声明，都假定其前域和后域相同。即都为定义在非空集合A上的关系。,2020/1/29,6.4.1 关系性质的定义,1、自反性和反自

19、反性 定义6.4.1设R是集合A上的关系， （1）如果对 xA, 都有 R，那么 称R在A上是自反的，或称R具有自反性。 例如：相等关系。 （2）如果对任意的xA，都有 R，那么 称R在A上是反自反的，或称R具有反自反性。 例如：父子关系。,2020/1/29,符号化：,（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。,2020/1/29,例6.4.1,设A=1,2,3，定义A上的关系R,S和T如下： （1）R=,

20、； （2）S=,； （3）T=,。 解: (1) R是自反的； (2) S是反自反的； (3) T既不是自反的, 也不是反自反的。,2020/1/29,例6.4.1 解法,（一）(1) 因为A中x，都有R， 所以R是自反的； (2) 因为A中x，都有S， 所以S是反自反的； (3) 因为存在2A，使T， 所以T不是自反的； 又因为存在1A，使T， 所以T不是反自反的， 即T既不是自反的，也不是反自反的。,2020/1/29,例6.4.1 解（续）,（二）设R,S和T的关系矩阵分别为MR,MS和MT，则： （三）R,S和T的关系图分别是下图的(a),(b)和(c)。,2020/1/29,结论：,

21、（1）关系R是自反的R一定不是反自反的; （2）存在既不是自反的也不是反自反的关系; （3）关系R是自反的关系图中每个结点都有自环, 关系R是反自反的关系图中每个结点都无自环; （4）关系R是自反的关系矩阵的主对角线上全为1, 关系R是反自反的关系矩阵的主对角线上全为0。,2020/1/29,例6.4.2,设A=a,b, B=a,b,c, 试计算A, B上所有具有自反性的关系R的个数。 解 A上具有自反性的关系R的个数为：24-2=4 B上具有自反性的关系R的个数为：29-3=64 问: 具有反自反性的关系的个数呢?,2020/1/29,2、对称性和反对称性,定义6.4.2 设R是集合A上的关

22、系。 （1）对任意的x,yA, 如果R, 那么R, 则称关系R是对称的, 或称R具有对称性; （2）对任意的x,yA, 如果R且R, 那么x=y, 则称关系R是反对称的, 或称R具有反对称性。,2020/1/29,符号化：,（1）R在A上是对称的 (x)(y)(xAyARR)=1, （2）R在A上是反对称的 (x)(y)(xAyAR Rx=y)=1,2020/1/29,结论：,(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上

23、不是反对称的 x,yA, 有xy, R且R,2020/1/29,例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的关系矩阵和画出相应的关系图。,2020/1/29,例6.4.2 解,(1) a) 关系R是对称的, 但不是反对称的； b) 关系S是反对称的, 但不是对称的； c) 关系T既不是对称的, 也不是反对称的； d) 关系V既是对称的，也是反对称的。 (2) 关系矩阵分别为,(3) 关系图分别是,2020/1/29,注意,(1) 存在既不是对称

24、也不是反对称的关系, 也存在既是对称也是反对称的关系； (2) 关系R是对称的 关系图中任何一对结点之间, 要么有方向相反的两条边, 要么无任何边； 关系R是反对称的 关系图中任何一对结点之间, 至多有一条边； (3) 关系R是对称的 R的关系矩阵为对称矩阵 关系R是反对称的 R的关系系矩阵为反对称矩阵,2020/1/29,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,2020/1/29,例6.4.3,设A=1

25、,2,3，定义A上的关系R, S, T 和 V 如下： （1）R=,； （2）S=； （3）T=,； （4）V=,。 试判定它们是否具有传递性。 解: R, S具有传递性; T, V不具有传递性。,2020/1/29,总结,2020/1/29,例6.4.6,判定下列关系所具有的特殊性质。 （1）集合A上的全关系； （2）集合A上的空关系； （3）集合A上的恒等关系。 解 (1) 全关系具有自反性，对称性和传递性； (2) 空关系具有反自反性、对称性、反对称性和传递性； (3) 恒等关系具有自反性、对称性、反对称性和传递性。,2020/1/29,例6.4.8,假设A=a,b,c,d，R=, 是定

26、义在A上的关系。试判定R所具有的特殊性质。 解 R既不是自反的，也不是反自反的； 既不是对称的，也不是反对称的； 而且也不是传递的。 即R不具备关系的任何性质。,2020/1/29,例6.4.9,设R=,，试判断R在集合A和B上具备的特殊性质，其中A=1,2, B=1,2,3。 解 (1) 当R是定义在集合A上的关系时， R是自反、对称、反对称和传递的； (2) 当R是定义在集合B上的关系时， R是对称、反对称和传递的。,2020/1/29,练习: P191 13,13. 设A=a.b,c, A上的关系Ri定义如下: (1) R1=,; (2) R2=,; (3) R3=,; (4) R4=;

27、 (5) R5=AA 判断A上的上述关系具备哪些性质。,2020/1/29,定理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 关系性质的判断定理,2020/1/29,练习: P191 15,15. 设A=1,2,3, 在图6.7.1中给出了16种A上的关系。对于每一种关系图, 写出相应的关系表达式和关系矩阵, 并说明它们具备什么性质。,2020/1/29,定理6.4.2 设R,S是定义在A上的二元关系，则： (1)若R,S是自反的, 则

28、 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）并运算、差运算和复合运算的保守性较差。,2020/1/29,6.5 关系的闭包运算,对于一个给定的关系，可能不具有某一个特殊性质。但是，如果我们希望它具有该特定的性质，那么应该怎么做呢？ 例如，对给定集合A=1,2,3上的关

29、系 R=,，它不具有自反性。 根据自反性的定义, 添加 ,这两个元素后, 所得到的新关系就具有自反性。 另外，还可以添加, , , 得到的新关系仍然具有自反性。,2020/1/29,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) )。 显然, 关系的闭包是增加最少元素, 使其具备所需性质的扩充。,2020/1/29,例6

30、.5.1,设A=1,2,3，R=,是A上的关系。试求R的自反闭包、对称闭包和传递闭包。 解 由关系的自反性定义知， R是自反的当且仅当对aA，都有R， 因此，在R中添和后得到的新关系就具有自反性，且满足自反闭包的定义，即 r(R)=,;,2020/1/29,例6.5.1(续),由关系的对称性定义知，在R中添上后得到的新关系就具有对称性，且满足对称闭包的定义，即 s(R)=,； 由关系的传递性定义知，在R中添上和后得到的新关系就具有传递性，且满足传递闭包的定义。即 t(R)=,。,2020/1/29,例6.5.2,求下列关系的r(R),s(R)和t(R)。 （1）定义在整数集Z上的“”关系； （

31、2）定义在整数集Z上的“=”关系。,2020/1/29,例6.5.2 解,（1）定义在Z上的“”关系的 r(R)为“”， s(R)为“”， t(R)为“”； （2）定义在Z上的“=”关系的 r(R)为“=”， s(R)为“=”， t(R)为“=”。,2020/1/29,例6.5.3,设集合A=1,2,3,4，R=, 是定义在A上的二元关系。 （1）画出R的关系图； （2）求出r(R),s(R),t(R),并画出其相应的关系图。 解（1）R的关系图见下图；,2020/1/29,例6.5.3（续）（2）,r(R)=,； s(R)=,；t(R)=,。 r(R)，s(R)，t(R)的关系图分别如下：,

32、2020/1/29,总结,利用关系图求关系R闭包的方法： （1）检查R的关系图，在没有自环的结点处加上自环，可得r(R)的关系图； （2）检查R的关系图，将每条单向边全部改成双向边，可得s(R)的关系图； （3）检查R的关系图，从每个结点出发，找到其终点，如果该结点到其终点没有边相连，就加上此边，可得t(R)的关系图。,2020/1/29,设R是集合A上的二元关系，则： （1）r(R)RIA。 （2）s(R)RR-1。 （3）t(R) ，若|A|n，则t(R) 。,定理6.5.1,2020/1/29,作业,第192页 16, 17 思考: 18, 19 预习: 7.2 等价关系,2020/1/

33、29,6.6 本章总结,1、序偶和笛卡儿积的概念 2、二元关系的概念和表示 3、关系的交、并、补、差运算、复合运算和逆运算 4、关系性质的定义、关系性质的判定、关系性质的证明和关系性质的保守性； 5、关系的自反、对称、和传递闭包的概念及计算。,2020/1/29,习题类型,（1）基本概念题：涉及关系性质的判定，关系性质的保守性； （2）判断题：涉及关系性质的保守性 ； （3）计算题：涉及关系的运算和闭包的计算； （4）证明题：涉及关系性质的证明，关系运算律的证明 。,2020/1/29,P190 4. 设A=0,1,2,3, R和S是A上的二元关系,R=|(j=i+1)或(j=i/2); S

34、=|(i=j+2). (1) 用关系矩阵法求RS; (2) 用关系图法求SR; (3) 用任意方法求 RSR, R3, S3. 解 R和S的关系矩阵分别为 故 RS的关系矩阵为,2020/1/29,题4的答案（续）,(2) SR的关系图为 (3) RSR, R3, S3的关系矩阵分别为,2020/1/29,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,

35、3,4; ran(AB)=4 AB =,.,2020/1/29,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) 对称.,2020/1/29,P191 17. 求闭包(图 (a),(b),2020/1/29,P191 17. 求闭包(图 (c),(d),2020/1/29,P191 17. 求闭包(图 (e),(f),