离散数学第四章二元关系和函数知识点总结

1、本文格式为Word版，下载可任意编辑 离散数学第四章二元关系和函数知识点总结 集合论部分 第四章、二元关系和函数 集合的笛卡儿积与二元关系有序对 定义由两个客体x 和y，依照一定的顺序组成的 二元组称为有序对，记作 实例：点的直角坐标(3,4) 有序对性质 有序性 （当x y时） 与 相等的充分必要条件是= x=u y=v 例1 = ，求x, y. 解 3y 4 = 2, x+5 = y y = 2, x = 3 定义一个有序n (n3) 元组 是一个 有序对，其中第一个元素是一个有序n-1元组，即 = , x n 当n=1时, 形式上可以看成有序 1 元组. 实例 n 维向量是有序 n元组.

2、 笛卡儿积及其性质 定义设A,B为集合，A与B 的笛卡儿积记作A B，即A B = | x A y B 例2 A=1,2,3, B=a,b,c A B =, , B A =, , , A=, P(A)A=, 性质： 不适合交换律A B B A (A B, A, B) 不适合结合律 (A B)C A(B C) (A, B)对于并或交运算满足分派律 A(B C)=(A B)(A C) (B C)A=(B A)(C A) A(B C)=(A B)(A C) (B C)A=(B A)(C A) 若A或B中有一个为空集，则A B就是空集. A=B= 若|A|=m, |B|=n, 则 |A B|=mn 证

3、明A(B C)=(A B)(A C) 证任取 A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC) 所以有A(BC) = (AB)(AC). 例3 (1) 证明A=B C=D A C=B D (2) A C=B D是否推出A=B C=D 为什么 解 (1) 任取 A C x A y C x B y D B D (2) 不一定. 反例如下： A=1，B=2, C=D=, 则A C=B D 但是A B. 二元关系的定义 定义设A,B为集合, AB的任何子集所定义的二元 关系叫做从A到B的二元关系, 当A=B时则叫做A上 的二元关系. 例4 A=0,1, B

4、=1,2,3, R1=, R2=AB, R3=, R4=. 那么R1, R2, R3, R4是从A 到B 的二元关系, R3和R4同时也是A上的二元关系. 计数 |A|=n, |AA|=n2, AA的子集有个. 所以A上有 个不同的二元关系. 例如 |A|=3, 则A上有=512个不同的二元关系. 设A 为任意集合， 是A 上的关系，称为空关系 E , I A 分别称为全域关系与恒等关系，定义如下： A E =|xAyA=AA A I =|xA A 例如, A=1,2, 则 E =, A I =, A 小于等于关系L A, 整除关系D A, 包含关系R定义： L =| x,yAxy, A R，

5、R为实数集合 A D =| x,yBx整除y, B B Z*, Z*为非0整数集 R=| x,yAx y, A是集合族. 类似的还可以定义大于等于关系, 小于关系, 大于关系, 真包含关系等等. 例如A = 1, 2, 3, B =a, b, 则 L =, A D =, A A=P(B)=,a,b,a,b, 则A上的包含关系是 R=, , 二元关系的表示 表示方式：关系的集合表达式、关系矩阵、关系图 关系矩阵：若A=a1, a2, , a m，B=b1, b2, , b n，R是从A到B的关系，R 的关系矩阵是布尔矩阵M R = r ij m n, 其中r ij= 1 R. 关系图：若A= x

6、1, x2, , x m，R是从A上的关系，R的关系图是G R=, 其中A为结点集，R为边集.假如属于关系R，在图中就有一条从x i到x j 的有向边. 注意：A, B为有穷集，关系矩阵适于表示从A到B的关系或者A上的关系，关系图适于表示A上的关系 A=1,2,3,4, R=, R的关系矩阵M 和关系图G R如下： R 关系的运算 基本运算定义：定义域、值域和域 dom R = x | y (R) ran R = y | x (R) fld R = dom R ran R 例1 R=, 则 dom R=1, 2, 4 ran R=2, 3, 4 fld R=1, 2, 3, 4 逆与合成 R1

7、 = | R RS = | | y (RS) 例2 R=, , , S=, , , , R1=, , , RS =, , SR =, , , 定义 F 在A上的限制 F?A = | xFy x A A 在F下的像 FA = ran(F?A) 实例R=, , , R?1=, R1=2,4 R?= R1,2=2,3,4 注意：F?A F, FA ran F 基本运算的性质 定理1 设F是任意的关系, 则 (1) (F1)1=F (2) dom F1=ran F, ran F1=dom F 证 (1) 任取, 由逆的定义有 (F 1) 1 F 1 F 所以有 (F1)1=F (2) 任取x, xdo

8、m F 1 y(F1) y(F) xran F 所以有dom F1= ran F. 同理可证 ran F1 = dom F. 定理2 设F, G, H是任意的关系, 则 (1) (FG)H=F(GH) (2) (FG)1= G1F 1 证 (1) 任取, (FG)H t(FGH) t (s(FG)H) t s (FGH) s (Ft (GH) s (FGH) F(GH) 所以 (FG)H = F(GH) (2) 任取, (FG)1 FG t (F(t,x)G) t (G1(t,y)F1) G1F1 所以 (FG)1 = G1F1 幂运算 设R为A上的关系, n为自然数, 则R 的n次幂定义为：

9、 (1) R0= | xA =I A (2) R n+1 = R nR 注意： 对于A上的任何关系R1和R2都有 R 10 = R 2 0 = I A 对于A上的任何关系R 都有 R1 = R 性质：定理3 设A为n元集, R是A上的关系, 则存在自然数s 和t, 使得R s = R t. 证R为A上的关系, 由于|A|=n, A上的不同关系只有个. 当列出R 的各次幂 R0, R1, R2, , , , 必存在自然数s 和t 使得R s=R t. 定理4 设R 是A 上的关系, m, nN, 则 (1) R mR n=R m+n (2) (R m)n=R mn 证用归纳法 (1) 对于任意给

10、定的mN, 施归纳于n. 若n=0, 则有 R mR0=R mI =R m=R m+0 A 假设R mR n=R m+n, 则有 R mR n+1=R m(R nR)=(R mR n)R=R m+n+1 , 所以对一切m, nN有R mR n=R m+n. (2) 对于任意给定的mN, 施归纳于n. 若n=0, 则有 (R m)0=I A=R0=R m0 假设 (R m)n=R mn, 则有 (R m)n+1=(R m)nR m=(R mn)R m=R mn+m=R m(n+1) 所以对一切m,nN有 (R m)n=R mn. 关系的性质 自反性 反自反性 定义设R为A上的关系, (1) 若x

11、(xAR), 则称R在A上是自反的. (2) 若x(xAR), 则称R在A上是反自反的.实例： 反关系：A上的全域关系E A, 恒等关系I A 小于等于关系L A, 整除关系D A 反自反关系：实数集上的小于关系 幂集上的真包含关系 例1 A=1,2,3, R1, R2, R3是A上的关系, 其中R , 1 R , 2 R 3 R 自反, 2 R 反自反, 3 R 既不是自反也不是反自反的 1 对称性 反对称性 定义设R为A上的关系, (1) 若x y(x,yARR), 则称R为A上对称的关系. (2) 若x y(x,yARRx=y), 则称R为A上的反对称关系. 实例： 对称关系：A上的全域关系E A, 恒等关系I A和空关系 反对称关系：恒等关系I A，空关系是A上的反对称关系. 例2 设A1,2,3, R1, R2, R3和R4都是A上的关系, 其中 R ,，R2, 1 R ,，R4, 3 R 对称、反对称. 1