《离散数学 第4章 关系》由会员分享，可在线阅读，更多相关《离散数学 第4章 关系（43页珍藏版）》请在金锄头文库上搜索。
1、第4章 关系1第4章 关系 4.1 关系的定义及其表示 4.2 关系运算 4.3 关系的性质 4.4 等价关系与偏序关系24.1 关系的定义及其表示 4.1.1 有序对与笛卡儿积 4.1.2 二元关系的定义 4.1.3 二元关系的表示3定义4.1 由两个元素，如x和y，按照一定的顺序 组成的二元组称为有序对，记作 实例：点的直角坐标 (3,4) 有序对的性质有序性 （当x y时） 与相等的充分必要条件是= x=u y=v例1 =，求 x, y. 解 3y4=2, x+5=y y=2, x= 3 有序对4笛卡儿积定义4.2 设A, B为集合，A与B 的笛卡儿积记作AB，AB = | xA yB
2、.例2 A=0, 1, B=a, b, cAB=, BA =, A = , B = P(A)A = , P(A)B = 5【例】设 A=a,b，B=1,2,3，试求AB和BA验证|AB|=|A|B|和|BA|=|B|A|解： AB=a,1,a,2,a,3,b,1,b,2,b,3 BA=1,a,1,b,2,a, 2,b,3,a, 3,b |AB|=6=23=|A|B|BA|=6=32=|B|A|6笛卡儿积的性质对于并或交运算满足分配律A(BC)=(AB)(AC) (BC)A=(BA)(CA) A(BC)=(AB)(AC) (BC)A=(BA)(CA) 幻灯片 9若A或B中有一个为空集，则AB就是
3、空集.A=B= 不适合交换律 ABBA (AB, A, B) 幻灯片 6 不适合结合律(AB)CA(BC) (A, B, C) 幻灯片 8若|A|=m, |B|=n, 则 |AB|=mn 幻灯片 67解： ABC=(AB)C=1,a,1,b,2,a,2,bx,y=1,a, x,1,b, x,2,a,x, 2,b,x, 1,a, y,1,b, y,2,a,y, 2,b,y A(BC)=1,2a,x,a, y,b,x,b, y =1,a,x,1,a, y,1,b,x,1,b, y2,a,x,2,a, y,2,b,x,2,b, y显然ABCA(BC)。【例】设A=1,2，B=a,b，A=x,y，求：
4、ABC，A(BC)。8证明：仅证明 任取a,b a,bA(BC)aAbBC aA( bBbC)(aAbB)(aAbC)a,bABa,bACa,b(AB)(AC)故 A(BC)=(AB)(AC) 可类似地证明、。 A(BC) =(AB)(AC)9有序 n 元组和 n 阶笛卡尔积 定义4.3 (1) 由 n 个元素 x1, x2, , xn按照一定的顺序排列构成有序 n 元组，记作 (2) 设A1, A2, , An为集合，称A1A2An= | xiAi, i=1,2, ,n 为 n 阶笛卡儿积. 实例(1,1,0)为空间直角坐标，(1,1,0)R R R10二元关系的定义定义4.4如果一个集合满
5、足以下条件之一： （1）集合非空, 且它的元素都是有序对 （2）集合是空集 则称该集合为一个二元关系, 简称为关系，记作R. 如R, 可记作 xRy；如果R, 则记作x y实例：R=, S=,a,b. R是二元关系, 当a, b不是有序对时，S不是二元关系 根据上面的记法，可以写1R2, aRb, a c等. 11实例例3 (1) R= | x,yN, x+y, , , , , (2) C= | x,yR, x2+y2=1，其中R代表实数集 合，C是直角坐标平面上点的横、纵坐标之间的关系 ，C中的所有的点恰好构成坐标平面上的单位圆. (3) R= | x,y,zR, x+2y+z=3，R代表了
6、空间直角坐标系中的一个平面. 125元关系的实例数据库实体模型员员工号姓名年龄龄性别别工资资301 302 303 304 张张 林 王晓晓云 李鹏鹏宇 赵赵 辉辉 50 43 47 21 男 女 男 男 1600 1250 1500 900 5元组： ，13从A到B的关系与A上的关系定义4.5 设A,B为集合, AB的任何子集所定义的二元关 系叫做从 A 到 B 的二元关系, 当 A=B 时则叫做 A上的二 元关系.例4 A=0,1, B=1,2,3, R1=, R2=AB, R3=, R4=, 从A到B的关系: R1, R2, R3, R4, A上的关系R3和R4. 计数： |A|=n,
7、|B|=m, |AB|=nm, AB 的子集有 个. 所以从A到 B有 个不同的二元关系. |A|=n, A上有 不同的二 元关系. 例如 |A|=3, 则 A上有512个不同的二元关系. 14A上重要关系的实例设A为任意集合， 是A上的关系，称为空关系 定义 4.6 EA, IA分别称为全域关系与恒等关系，其中 EA= | xA yA=AA IA= | xA例如, A=1,2, 则 EA=, IA=,15A上重要关系的实例（续）小于等于关系LA, 整除关系DA, 包含关系R定义如下： 定义4.7 LA=| x,yAxy, 这里AR，R为实数集合 DB=| x,yBx整除y, BZ*, Z*为
8、非0整数集 R=| x,yAxy, 这里A是集合族. 例如 A=1,2,3, B=a,b, 则 LA=, DA=,A=P(B)=,a,b,a,b, 则A上的包含关系是 R=, , 类似的还可以定义大于等于关系, 小于关系, 大于关系, 真包含关系等等. 16关系的表示表示方式：关系的集合表达式、关系矩阵、关系图 定义4.8 关系矩阵 若A=x1, x2, , xm，B=y1, y2, , yn ，R是从A到B的关系，R的关系矩阵是布尔矩阵MR = rij mn, 其中 rij = 1 R. 定义4.9 关系图 若A= x1, x2, , xm，R是从A上的关系， R的关系图是GR=, 其中A为
9、结点集，R为边集.如果 属于关系R，在图中就有一条从 xi 到 xj 的有向边. 注意：设A, B为有穷集 关系矩阵适合于表示从A到B 的关系或者A上的关系 关系图适合于表示A上的关系 172.用关系矩阵表示二元关系如果A，B是有限集，A=a1,a2,am，B=b1,b2,bn， R是A到B的二元关系，R的关系矩阵MR定义为 ：MR= mni=1,m j=1,n称为二元关系R的关系矩阵。18【例】设A=a1,a2,a3,a4 ，B=b1,b2,b3，R是A 到B的二元关系，定义为： R=a1,b1,a1,b3,a2,b2,a2,b3,a3,b1,a4,b1 ,a4,b2 写出R的关系矩阵。解：
10、R的关系矩阵为：MR= 19【例】设A=1,2,3,4，R是A的二元关系，定义为： R=1,1,1,2,2,1,3,2,3,1,4,3,4,2,4,1写出A上二元关系R的关系矩阵。解：R的关系矩阵为：MR=203.用关系图表示二元关系如果A和B是有限集，R是A到B二元关系 ，还可以用图表示二元关系R。表示二元关 系R的图叫做R的关系图。A到B二元关系的关系图和A上的二元关系的关系图的定义是不一样的。分别描述如 下：21A到B二元关系R的关系图设A=a1,a2,am，B=b1,b2,bn，R是 A到B二元关系，R的关系图的绘制方法如下：画出m个小点表示A的元素，再画出n个 小点表示B的元素。这些
11、小点叫做关系图的顶点(下同)。如果ai,bj R，则从ai到bj画一根有方向(带箭头)的线。这些有方向(带箭头)的线叫 做关系图的边(下同)。 22【例】设A=a1,a2,a3,a4 ，B=b1,b2,b3，R是 A到B的二元关系，定义为： R=a1,b1,a1,b3,a2,b2,a2,b3,a3,b1,a4, b1,a4,b2 R的关系图如下：23A上的二元关系R的关系图设A=a1,a2,am，R是A上的二元关系，其关系图如下绘制：画出m个小点表示A的元素。如果ai,ajR，则从ai到aj画一根有 方向(带箭头)的线。24例5 A=a, b, c, d, R=, R的关系矩阵 MR 和关系图
12、 GR 如下：25【例】设A=1,2,3,4，R是A的二元关系， R=1,1,1,2,2,1,3,2,3,1,4,3,4,2 4,1 A上二元关系R的关系图如下：26 4.2.1 关系的基本运算 定义域、值域、域、逆、合成 基本运算的性质 4.2.2 关系的幂运算 幂运算的定义 幂运算的方法 幂运算的性质4.2 关系运算27关系的基本运算定义4.10 定义域、值域 和 域domR = x | y (R) ranR = y | x (R) fldR = domR ranR 例1 R=, 则domR =ranR =fldR = a, c, a, d, b, d a, c, a, d b, d, d
13、28关系的基本运算（续）定义4.11 R 的逆 R1 = | R定义4.12 R与S的合成 RS = | | y (RS) 例2 R=, , , S=, , , , R1 = RS = SR =, , , , , , , 29合成运算的图示方法利用图示（不是关系图）方法求合成RS =, , SR =, , , 30基本运算的性质 定理4.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. 31定理4.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 (
