离散数学课件：第4章 二元关系与函数1

1、1第第4章章 二元关系与函数二元关系与函数n4.1 集合的笛卡儿积与二元关系集合的笛卡儿积与二元关系n4.2 关系的运算关系的运算n4.3 关系的性质关系的性质n4.4 关系的闭包关系的闭包n4.5 等价关系和偏序关系等价关系和偏序关系n4.6 函数的定义和性质函数的定义和性质n4.7 函数的复合和反函数函数的复合和反函数24.1 集合的笛卡儿积和二元关系集合的笛卡儿积和二元关系n 有序对有序对n 笛卡儿积笛卡儿积 及性质及性质n 二元关系的定义二元关系的定义n 二元关系的表示二元关系的表示3有序对有序对定义 由两个元素 x 和 y，按照一定的顺序组成的 二元组称为有序对，记作 实例：点的直角

2、坐标 (3, 4) 有序对性质有序性 （当x y时） 与 相等的充分必要条件： = x=u y=v例1 = ，求 x, y. 解: 依有序对性质有：3y 4 = 2, x+5 = y y = 2, x = 34有序有序 n 元组元组定义定义 一个有序 n (n3) 元组 是一个有序对，其中第一个元素是一个有序 n-1元组，即 = , xn （当当 n=1时时, 形式上可以看成有序形式上可以看成有序 1 元组元组. ）实例：实例： n 维向量是有序维向量是有序 n元组元组. 5笛卡儿积笛卡儿积定义 设A,B为集合，由A与B产生的有序对集： | xA yB ，称为A与B的笛卡儿积，记作 AB例2

3、设 A=1,2,3, B=a,b,c AB =, , BA =, , , 若A=, P(A)A=, u显然：若| A|=m，| B |=n，则 |AB|= mn6笛卡儿积的性质笛卡儿积的性质u 若A或B中有一个为空集，则AB就是空集. A = B = u 一般不满足交换律 AB BA (AB, A, B)u 一般不满足结合律 (AB)C A(BC) (A,B,C非空 )u 满足对并、交、差、对称差运算的分配律（可用谓词逻辑证明）A(BC)=(AB)(AC) (BC)A=(BA)(CA) A(BC)=(AB)(AC) (BC)A=(BA)(CA) A(B-C)=(AB)-(AC) (B-C)A=

4、(BA)-(CA) A(BC)=(AB)(AC) (BC)A=(BA)(CA) 7证明证明 A (B- -C)=(A B)- -(A C)证证 任取 A(B-C) xA yB-C xA yB y C (xA yB y C) (xA yB x A ) (xA yB ) ( y C x A ) (xA yB ) (xA yC ) (AB) (AC) (AB) - (AC)所以，A(B-C) = (AB) - (AC)8例题例题 解 (1) 任取 AC xA yC xB yD BD 例3 (1) 证明 A=B C=D AC=BD (2) AC=BD是否推出 A=B C=D ? 为什么？ (2) 不一

5、定. 反例如下： A=1，B=2, C=D=, 则 AC=BD = 但是 AB.9二元关系的定义二元关系的定义二元关系：空集，或者元素均为有序对的集合集合，称为二元关系二元关系，简称为关系关系，记作R.如R, 可记作 xRy；如果R, 则记作x y例如：R=, S=,a,b. 此时R是二元关系；对于S， 当a, b不代表有序对时，S不是二元关系；根据上面的记法，可以写 1R2, aRb, a c 等. 10从从A到到B的关系与的关系与A上上的关系的关系从从A到到B的二元关系： 设A,B为集合, 由AB的任何子集所定义的二元关系称做从A到B的二元关系； 当A=B时，简称 A上的二元关系上的二元关

6、系.例4 A=0,1, B=1,2,3, R1=, R2=AB, R3=, R4=. 那么 R1, R2, R3, R4都是从 A 到 B 的二元关系, R3和R4同时也可看成是 A上的二元关系. A上的二元关系上的二元关系计数计数|A|=n, |AA|=n2, AA的子集有 个. 所以 A上有 个不同的二元关系. 例如 |A|=3, 则 A上有=512个不同的二元关系. 22n22n11A上的重要关系上的重要关系设 A 为任意集合， 空关系： 是 A 上的空关系 全域关系： EA=|xAyA=AA 恒等关系： IA=|xA例, A=1,2, 则 EA=, IA=,12A上重要关系上重要关系

7、实例实例 设AR，R为实数集合 小于等于小于等于关系 LA, LA=| x,yAxy, 设AZ*, （Z*为非0整数集 ） 整除整除关系DA, DA=| x,yA x整除y, A是集合族， 包含包含关系R： R=| x,yAxy类似的还可以定义大于等于关系, 小于关系, 大于关系, 真包含关系等等. 13实例实例例，设 A = 1, 2, 3, B =a, b, 则 LA=, DA=, 设A=P(B)=,a,b,a,b, 则 A上的包含关系是 R= , , ,a,b, , , , 14关系的表示方式关系的表示方式关系的表示方式除了用集合表示，还有 关系矩阵和关系图 关系矩阵关系矩阵：设A=a1

8、, a2, , am，B=b1, b2, , bn，R是从A到B的关系，R的关系矩阵是布尔矩阵MR = rij mn, 其中 rij = 1 R. 关系图关系图：设A= x1, x2, , xm，R是A上的关系，R的关系图是GR=, 其中A为结点集，R为边集.如果属于关系R，在图中就有一条从 xi 到 xj 的有向边. 关系矩阵可以表示从A到B的关系 或者 A上的关系；关系图适合表示A上的关系；此处此处A, B为有穷集。为有穷集。 15实例实例A=1,2,3,4, R=,R的关系矩阵的关系矩阵MR和关系图和关系图GR如下：如下： 0010000011000011RM16n基本运算定义基本运算定

9、义定义域、值域、域定义域、值域、域逆、合成、限制、像逆、合成、限制、像n基本运算的性质基本运算的性质n幂运算幂运算定义定义求法求法性质性质4.2 关系的运算关系的运算17关系的基本运算定义关系的基本运算定义定义域定义域、值域值域 和和 域域 domR = x | y ( R) ranR = y | x ( R) fldR = domR ranR 例例1 R=, 则则 domR=1, 2, 4 ranR=2, 3, 4 fldR=1, 2, 3, 4 18关系的基本运算定义（续）关系的基本运算定义（续）逆逆与与合成合成 R 1 = | R R S = | y ( S R) (注意本书采用左复合注

10、意本书采用左复合)例例2 R=, , , S=, , , , R 1=, , , R S = , , , S R =, , 19合成运算的图示方法合成运算的图示方法 利用图示法（并非关系图）求合成利用图示法（并非关系图）求合成 R S=, , , S R =, , R SS R20限制与像限制与像定义定义 关系关系F 在在A上的上的限制限制 F A = | xFy xA A 在关系在关系F下的下的像像 FA = ran(F A) 实例 R=, , , R 1=, R1=2,4 R = R1,2=2,3,4显然：F A F, FA ranF 21关系基本运算的性质关系基本运算的性质 定理定理4.

11、1 设设F, G, H是任意的关系是任意的关系, 则则(1) (F 1) 1=F(2) domF 1=ranF, ranF 1=domF (3) (F G) H=F (G H) (4) (F G) 1= G 1 F 1 证证: (1) 任取任取, 由由逆的定义逆的定义有有 (F 1) 1 F 1 F所以有所以有 (F 1) 1=F22 (2) 任取任取x, xdomF 1 y(F 1) y(F) xranF 所以有所以有domF 1= ranF. 同理可证同理可证 ranF 1 = domF. (3) 任取任取, (F G) H tH (F G ) t H sGF t s H GF s t H

12、 G F s (G H) F F (G H) 所以所以 (F G) H = F (G H)关系基本运算的性质（续）关系基本运算的性质（续） 23 (4) 任取任取, (F G) 1 F G t GF t G 1F 1 G 1 F 1 所以所以 (F G) 1 = G 1 F 1 关系基本运算的性质（续）关系基本运算的性质（续） 24关系基本运算的性质关系基本运算的性质 定理定理4.2 设设F, G, H是任意的关系是任意的关系, 则则 (1) F (G H) = F G F H (2) (G H) F = G F H F (3) F (G H) F G F H (4) (G H) F G F

13、H F25A上关系的幂运算上关系的幂运算设设R为为A上的关系上的关系, n为自然数为自然数, 则则 R 的的 n次幂次幂定义为：定义为： (1) R0= | xA =IA (2) Rn+1 = Rn R 注意：注意： 对对A上的任何关系上的任何关系R1和和R2都有都有 R10 = R20 = IA 对对A上的任何关系上的任何关系 R 都有都有 R1 = R 26幂的求法幂的求法关系关系R在集合下，在集合下，Rn 就是就是n个个R依次左复合；而在依次左复合；而在 矩阵表示下就是矩阵表示下就是n个个R的关系矩阵相乘的关系矩阵相乘, 其中涉及其中涉及到的到的相加按逻辑加相加按逻辑加. 例例3 设设A

14、=a,b,c,d, R=, 求求R的各次幂的各次幂, 分别用矩阵和关系图表示分别用矩阵和关系图表示.解：解： R与与R2的关系矩阵分别为的关系矩阵分别为 0000100001010010M 0000000010100101000010000101001000001000010100102M27R0=IA，R3和和R4的矩阵的矩阵 分别是：分别是： 0000000010100101,000000000101101043MM 10000100001000010M幂的求法（幂的求法（关系矩阵法）留意到，留意到，M4=M2, 即即R4=R2. 因而有因而有R2=R4=R6=, R3=R5=R7=28（

15、R=, , , ）R0, R1, R2, R3,的关系图如下图所示的关系图如下图所示幂的求法（幂的求法（关系图法）R0R1R2=R4=R3=R5=29幂运算的性质幂运算的性质定理定理3 设设A为为n元集元集, R是是A上的关系上的关系, 则存在自然则存在自然数数 s 和和 t, 使得使得 Rs = Rt.证：证： R为为A上的关系上的关系, 由于由于|A|=n, A上的不同关系上的不同关系只有只有 个个. 当列出当列出 R 的各次幂的各次幂 R0, R1, R2, , , , 必存在自然数必存在自然数 s 和和 t 使得使得 Rs=Rt.22n30定理定理4 设设 R 是是 A 上的关系上的关系, m, nN, 则则 (1) Rm Rn=Rm+n (2) (Rm)n=Rmn 证：证： 用归纳法用归纳法 (1) 对于对于任意给定的任意给定的mN, 对对n归纳归纳. i) 当当n=0, 有有 Rm R0=Rm IA=Rm=Rm+0 ；ii) 假设假设Rm Rn=Rm+n, 则则Rm Rn+1=Rm (Rn R