《离散数学第七章二元关系》由会员分享，可在线阅读，更多相关《离散数学第七章二元关系（91页珍藏版）》请在金锄头文库上搜索。
1、主要内容 l 有序对与笛卡儿积 l 二元关系的定义与表示法 l 关系的运算 l 关系的性质 l 关系的闭包 l 等价关系与划分 l 偏序关系第七章 二元关系17.1 有序对与笛卡儿积定义7.1 由两个元素 x 和 y，按照一定的顺序组成的二元组 称为有序对，记作.有序对性质: (1) 有序性 （当xy时） (2) 与相等的充分必要条件是= x=uy=v. 2笛卡儿积定义7.2 设A,B为集合，A与B的笛卡儿积记作AB，且AB = | xAyB.例1 A=1,2,3, B=a,b,cAB=, BA=, A=, B=P(A)A = , P(A)B = 3笛卡儿积的性质(1) 不适合交换律 AB B
2、A (AB, A, B) (2) 不适合结合律(AB)C A(BC) (A, B, C) (3) 对于并或交运算满足分配律A(BC) = (AB)(AC) (BC)A = (BA)(CA) A(BC) = (AB)(AC) (BC)A = (BA)(CA) (4) 若 A 或 B 中有一个为空集，则 AB 就是空集.A = B = (5) 若 |A| = m, |B| = n, 则 |AB| = mn 4性质证明证明 A(BC) = (AB)(AC)证 任取 A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC) 所以有A(BC) = (AB)(AC).
3、5实例例2 (1) 证明A=B,C=D AC=BD (2) AC = BD是否推出 A=B,C=D? 为什么？解 (1) 任取AC xAyC xByD BD (2) 不一定.反例如下：A=1，B=2, C = D = , 则AC = BD但是A B.67.2 二元关系定义7.3 如果一个集合满足以下条件之一： (1) 集合非空, 且它的元素都是有序对 (2) 集合是空集 则称该集合为一个二元关系, 简称为关系，记作R. 如果R, 可记作xRy；如果R, 则记作x y实例：R=, S=,a,b. R是二元关系, 当a, b不是有序对时，S不是二元关系 根据上面的记法，可以写1R2, aRb, a
4、 c等. 7A到B的关系与A上的关系定义7.4 设A,B为集合, AB的任何子集所定义的二元关系叫做从 A 到B的二元关系, 当A=B时则叫做A上的二元关系.例 3A = 0 , 1 ,B = 1 , 2 , 3 ,那 么 R1= ,R2= A B ,R3= ,R4= R1,R2,R3,R4 是 从A到B的 二 元 关 系 ,R3和R4也 是 A 上 的 二 元 关 系 .计 数 :| A | = n ,| A A | = n2 ,A A 的 子 集 有 个 .所 以A 上 有 个 不 同 的 二 元 关 系 .例 如| A |=3 ,则A 上 有 = 5 1 2 个 不 同 的 二 元 关
5、系 .8A上重要关系的实例定义7.5 设 A 为集合, (1) 是A上的关系，称为空关系 (2) 全域关系 EA = | xAyA = AA 恒等关系 IA = | xA小于等于关系 LA = | x,yAxy, A为实数子集 整除关系 DB = | x,yBx整除y, A为非0整数子集 包含关系 R = | x,yAxy, A是集合族.9实例 例如, A=1, 2, 则 EA = , IA = , 例如 A = 1, 2, 3, B=a, b, 则LA = ,DA = ,例如 A = P(B) = ,a,b,a,b, 则 A上的包含关系是R = , ,类似的还可以定义：大于等于关系, 小于关
6、系, 大于关系, 真包含关系等.10关系的表示 1. 关系矩阵若A=x1, x2, , xm，B=y1, y2, , yn，R是从A到B的关系，R的关系矩阵是布尔矩阵MR = rij mn, 其中rij = 1 R. 2. 关系图若A= x1, x2, , xm，R是从A上的关系，R的关系图是 GR=, 其中A为结点集，R为边集. 如果属于关系R，在图中就有一条从 xi 到 xj 的有向边. 注意： l 关系矩阵适合表示从A到B的关系或A上的关系（A,B为有 穷集） l 关系图适合表示有穷集A上的关系 11实例 例4A=1,2,3,4, R=,R的关系矩阵MR和关系图GR如下：127.3 关系
7、的运算关系的基本运算 定义7.6 关系的定义域、值域与域分别定义为domR = x | y (R) ranR = y | x (R) fldR = domR ranR 例5 R=, 则 domR=1, 2, 4 ranR=2, 3, 4 fldR=1, 2, 3, 4 13关系运算(逆与合成)定义7.7 关系的逆运算R1 = | R 定义7.8 关系的合成运算RS = | y (R S) 例6 R = , , , S = , , , , R1 = , , , RS = , , SR = , , , 14合成的图示法利用图示（不是关系图）方法求合成RS =, , SR =, , , 15关系运算
8、(限制与像)定义7.9 设R为二元关系, A是集合 (1) R在A上的限制记作 RA, 其中 RA = | xRyxA (2) A在R下的像记作RA, 其中 RA=ran(RA) 说明：lR在A上的限制 RA是 R 的子关系，即 RA R lA在R下的像 RA 是 ranR 的子集，即 RA ranR 16实例例7 设R=, 则 R1 = , R = R2,3 = , R1 = 2,3 R = R3 = 2 17关系运算的性质定理7.1 设F是任意的关系, 则(1) (F1)1=F(2) domF1= ranF, ranF1= domF证 (1) 任取, 由逆的定义有(F1)1 F1 F. 所
9、以有(F1)1=F.(2) 任取x,xdomF1 y(F1) y(F) xranF 所以有 domF1=ranF. 同理可证 ranF1=domF.18定理7.2 设F, G, H是任意的关系, 则 (1) (FG)H = F(GH) (2) (FG)1 = G1F1关系运算的性质证 (1) 任取, (FG)H t (FGH) t ( s (FG)H) t s (FGH) s (Ft (GH) s (FGH) F(GH) 所以 (FG)H = F(GH)19证明(2) 任取, (FG)1 FG t (FG) t (G1F1) G1 F1所以 (F G)1 = G1 F1 20关系运算的性质定理
10、7.3 设R为A上的关系, 则 RIA= IAR=R证 任取RIA t (RIA) t (Rt=yyA) R21关系运算的性质 定理7.4 (1) F(GH) = FGFH (2) (GH)F = GFHF(3) F(GH) FGFH (4) (GH)F GFHF只证 (3) 任取, F(GH) t (FGH) t (FGH) t (FG)(FH) t (FG)t (FH) FGFH FGFH所以有 F(GH)=FGFH22推广定理7.4 的结论可以推广到有限多个关系 R(R1R2Rn) = RR1RR2RRn(R1R2Rn)R = R1RR2RRnRR(R1R2 Rn) RR1RR2 RRn
11、(R1R2 Rn)R R1RR2R RnR 23关系运算的性质定理7.5 设F 为关系, A, B为集合, 则(1) F (AB) = F AF B (2) F AB = F AF B(3) F (AB) = F AF B (4) F AB F AF B 24证明证 只证 (1) 和 (4).(1) 任取 F (AB) FxAB F(xAxB) (FxA)(FxB) F AF B F AF B所以有F (AB) = F AF B. 25证明(4) 任取y, yF AB x (FxAB) x (FxAxB) x (FxA)(FxB) x (FxA)x (FxB) yF AyF B yF AF B
12、所以有F AB=F AF B. 26关系的幂运算定义7.10 设 R 为 A 上的关系, n为自然数, 则 R 的 n 次幂定义为： (1) R0 = | xA = IA (2) Rn+1 = RnR注意： l 对于A上的任何关系 R1 和 R2 都有 R10 = R20 = IA l 对于A上的任何关系 R 都有 R1 = R27例 8 设A = a,b,c,d, R = , 求R的各次幂, 分别用矩阵和关系图表示. 解 R 与 R2的关系矩阵分别是：幂的求法28R3和R4的矩阵阵是：因此M4=M2, 即R4=R2. 因此可以得到 R2=R4=R6=， R3=R5=R7=R0的关系矩阵是 幂的求法29关系图R0, R1, R2, R3,的关系图如下图所示. R0R1R2=R4=R3=R5=30幂运算的性质 定理7.6 设 A 为 n 元集, R 是A上的关系, 则存在自然数 s 和 t, 使得 Rs = Rt.证 R 为A上的关系,
