《离散数学4.1-2》由会员分享，可在线阅读，更多相关《离散数学4.1-2（28页珍藏版）》请在金锄头文库上搜索。
1、第4章 二元关系与函数n4.1 集合的笛卡儿积与二元关系n4.2 关系的运算n4.3 关系的性质n4.4 关系的闭包n4.5 等价关系和偏序关系n4.6 函数的定义和性质n4.7 函数的复合和反函数14.1 集合的笛卡儿积和二元关系n 有序对n 笛卡儿积及其性质n 二元关系的定义n 二元关系的表示2有序对定义 由两个客体 x 和 y，按照一定的顺序组成的二元组称为有序对，记作 实例：点的直角坐标(3,4) 有序对性质有序性 （当x y时） 与 相等的充分必要条件是= x=u y=v例1 = ，求 x, y. 解 3y 4 = 2, x+5 = y y = 2, x = 3 3有序 n 元组定义
2、 一个有序 n (n3) 元组 是一个有序对，其中第一个元素是一个有序 n-1元组，即= , xn 当 n=1时, 形式上可以看成有序 1 元组. 实例 n 维向量是有序 n元组. 4笛卡儿积定义 设A,B为集合，A与B 的笛卡儿积记作AB， 即 AB = | xA yB 例2 A=1,2,3, B=a,b,cAB =, , BA =, , A=, P(A)A=, 5笛卡儿积的性质不适合交换律 ABBA (AB, A, B)不适合结合律 (AB)CA(BC) (A, B)对于并或交运算满足分配律A(BC)=(AB)(AC) (BC)A=(BA)(CA) A(BC)=(AB)(AC) (BC)A
3、=(BA)(CA) 若A或B中有一个为空集，则AB就是空集.A=B= 若|A|=m, |B|=n, 则 |AB| =mn6例题 解 (1) 任取例3 (1) 证明 A=B C=D AC=BD (2) AC=BD是否推出 A=B C=D ? 为什么？(2) 不一定. 反例如下：A=1，B=2, C=D=, 则 AC=BD 但是 AB.AC xA yC xB yD BD7二元关系的定义定义 如果一个集合满足以下条件之一： （1）集合非空, 且它的元素都是有序对 （2）集合是空集 则称该集合为一个二元关系, 简称为关系，记作R. 如R, 可记作 xRy；如果R, 则记作x y 实例：R=, S=,a
4、,b. R是二元关系, 当a, b不是有序对时，S不是二元关系 根据上面的记法，可以写 1R2, aRb, a c 等. 8从A到B的关系与A上的关系定义 设A,B为集合, AB的任何子集所定义的二元关系 叫做从A到B的二元关系, 当A=B时则叫做 A上的二元关 系. 例4 A=0,1, B=1,2,3, R1=, R2=AB, R3=, R4=.那么 R1, R2, R3, R4是从 A 到 B 的二元关系, R3和R4同时也是 A上的二元关系.计数 |A|=n, |AA|= n2, AA的子集有 个.2n2所以 A上有 个不同的二元关系.2n29A上重要关系的实例设 A 为任意集合， 是
5、A 上的关系，称为空关系 EA, IA 分别称为全域关系与恒等关系，定义如下： EA=|xAyA=AA IA=|xA 例如, A=1,2, 则 EA=, IA=,10A上重要关系的实例（续）小于等于关系 LA, 整除关系DA, 包含关系R定义：LA=| x,yAxy, AR，R为实数集合 DB=| x,yBx整除y, BZ*, Z*为非0整数集 R=| x,yAxy, A是集合族.类似的还可以定义大于等于关系, 小于关系, 大于关系, 真包含关系等等. 11实例例如 A = 1, 2, 3, B =a, b, 则 LA=, DA=,A=P(B)=,a,b,a,b, 则 A上的包含关系是R=,
6、,12关系的表示表示方式：关系的集合表达式、关系矩阵、关系图 关系矩阵：若A=a1, 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到B的 关系或者A上的关系，关系图适于表示A上的关系 13实例A=1,2,3,4, R=, R的关系矩阵MR和关系图GR如下：14n基本运算定义定义域
7、、值域、域逆、合成、限制、像n基本运算的性质n幂运算定义求法性质4.2 关系的运算15关系的基本运算定义定义域、值域 和 域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 16关系的基本运算定义（续）逆与合成 R1 = | RRS = | | y (SR) 例2 R=, , , S=, , , , R1=, , , SR =, , RS =, , , 17限制与像定义 F 在A上的限制 FA = | xFy xAA 在F下的像FA = ra
8、n(FA) 实实例 R=, , , R1=,R1=2,4R=R1,2=2,3,4 注意：FAF, FA ranF 18关系基本运算的性质 定理1 设F是任意的关系, 则 (1) (F1)1=F (2) domF1=ranF, ranF1=domF证 (1) 任取, 由逆的定义有 (F 1)1 F1 F 所以有 (F1)1=F(2) 任取x,xdomF1 y(F1) y(F) xranF 所以有domF1= ranF. 同理可证 ranF1 = domF.19定理2 设F, G, H是任意的关系, 则 (1) (FG)H=F(GH)(2) (FG)1= G1F1 证 (1) 任取, (FG)H
9、t(FGH) t (s(FG)H) t s (FGH) s (Ft (GH) s (FGH) F(GH) 所以 (FG)H = F(GH)关系基本运算的性质（续） 20(2) 任取, (FG)1 FG t (F(t,x)G) t (G1(t,y)F1) G1F1 所以 (FG)1 = G1F1 关系基本运算的性质（续） 21A上关系的幂运算设R为A上的关系, n为自然数, 则 R 的 n次幂定义为：(1) R0= | xA =IA(2) Rn+1 = RnR注意：对于A上的任何关系R1和R2都有 R10 = R20 = IA 对于A上的任何关系 R 都有 R1 = R 22幂的求法对于集合表示
10、的关系R，计算 Rn 就是n个R右复合 . 矩阵表示就是n个矩阵相乘, 其中相加采用逻辑加. 例3 设A=a,b,c,d, R=, 求R的各次幂, 分别用矩阵和关系图表示. 解 R与R2的关系矩阵分别为23同理，R0=IA, R3和R4的矩阵分别是：幂的求法（续）因此M4=M2, 即R4=R2. 因此可以得到 R2=R4=R6=, R3=R5=R7=24R0, R1, R2, R3,的关系图如下图所示幂的求法（续）25幂运算的性质定理3 设A为n元集, R是A上的关系, 则存在自然数 s 和 t, 使得 Rs = Rt.26定理4 设 R 是 A 上的关系, m, nN, 则 (1) RmRn
11、=Rm+n(2) (Rm)n=Rmn 证 用归纳法 (1) 对于任意给定的mN, 施归纳于n. 若n=0, 则有 RmR0=RmIA=Rm=Rm+0 假设RmRn=Rm+n, 则有 RmRn+1=Rm(RnR)=(RmRn)R=Rm+n+1 , 所以对一切m, nN有RmRn=Rm+n. 幂运算的性质（续）27(接上页证明) (2) 对于任意给定的 mN, 施归纳于n. 若n=0, 则有 (Rm)0=IA=R0=Rm0 假设 (Rm)n=Rmn, 则有 (Rm)n+1=(Rm)nRm=(Rmn)Rm=Rmn+m=Rm(n+1) 所以对一切 m,nN 有 (Rm)n=Rmn. 幂运算的性质（续）28
