离散数学第4章屈

1、1,第4章 关系,4.1 关系的定义及其表示 4.2 关系运算 4.3 关系的性质 4.4 等价关系与偏序关系,2,4.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 = |

2、xA yB . 例2 A=0, 1, B=a, b, c AB=, BA =, A = , B = P(A)A = , P(A)B = ,5,笛卡儿积的性质,对于并或交运算满足分配律 A(BC)=(AB)(AC) (BC)A=(BA)(CA) A(BC)=(AB)(AC) (BC)A=(BA)(CA),若A或B中有一个为空集，则AB就是空集. A=B=,不适合交换律 ABBA (AB, A, B),不适合结合律 (AB)CA(BC) (A, B, C),若|A|=m, |B|=n, 则 |AB|=mn,6,有序 n 元组和 n 阶笛卡尔积,定义4.3 (1) 由 n 个元素 x1, x2, ,

3、 xn按照一定的顺序排列构成 有序 n 元组，记作 (2) 设A1, A2, , An为集合，称 A1A2An= | xiAi, i=1,2, ,n 为 n 阶笛卡儿积. 实例 (1,1,0)为空间直角坐标，(1,1,0)R R R,7,二元关系的定义,定义4.4 如果一个集合满足以下条件之一： （1）集合非空, 且它的元素都是有序对 （2）集合是空集 则称该集合为一个二元关系, 简称为关系，记作R. 如R, 可记作 xRy；如果R, 则记作x y 实例：R=, S=,a,b. R是二元关系, 当a, b不是有序对时，S不是二元关系 根据上面的记法，可以写1R2, aRb, a c等.,8,实

4、例,例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代表了空间直角坐标系中的一个平面.,9,5元关系的实例数据库实体模型,5元组： ，,10,从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=

5、, R4=, 从A到B的关系: R1, R2, R3, R4, A上的关系R3和R4. 计数： |A|=n, |B|=m, |AB|=nm, AB 的子集有 个. 所以从A到B有 个不同的二元关系. |A|=n, A上有 不同的二元关系. 例如 |A|=3, 则 A上有512个不同的二元关系.,11,A上重要关系的实例,设A为任意集合， 是A上的关系，称为空关系 定义 4.6 EA, IA分别称为全域关系与恒等关系，其中 EA= | xA yA=AA IA= | xA 例如, A=1,2, 则 EA=, IA=,12,A上重要关系的实例（续）,小于等于关系LA, 整除关系DA, 包含关系R定义

6、如下： 定义4.7 LA=| x,yAxy, 这里AR，R为实数集合 DB=| x,yBx整除y, BZ*, Z*为非0整数集 R=| x,yAxy, 这里A是集合族. 例如 A=1,2,3, B=a,b, 则 LA=, DA=, A=P(B)=,a,b,a,b, 则A上的包含关系是 R=, ,类似的还可以定义大于等于关系, 小于关系, 大于关系, 真包含关系等等.,13,矩阵的定义,定义 由mn个数aij(i=1,2,m, j=1,2,n)排成的一个m行n列的矩形表，称为mn矩阵。记为,14,定义,矩阵的乘法,，,其中，,(i=1,2,m, j=1,2,n),15,矩阵的乘法,16,关系的表

7、示,表示方式：关系的集合表达式、关系矩阵、关系图 定义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为结点集，R为边集.如果属于关系R，在图中就有一条从 xi 到 xj 的有向边. 注意：设A, B为有穷集 关系矩阵适合于表示从A到B 的关系或者A上的关系 关系图适合于表示A上的关系,17,实例,例5 A=a, b, c, d, R=, R的关系矩阵 MR 和关系图

8、GR 如下：,18,4.2.1 关系的基本运算 定义域、值域、域、逆、合成 基本运算的性质 4.2.2 关系的幂运算 幂运算的定义 幂运算的方法 幂运算的性质,4.2 关系运算,19,关系的基本运算,定义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,20,关系的基本运算（续）,定义4.11 R 的逆 R1 = | R 定义4.12 R与S的合成 RS = | y (RS)

9、 ,例2 R=, , , S=, , , , R1 = RS = SR =, , , , , , , ,21,合成运算的图示方法,利用图示（不是关系图）方法求合成 RS =, , SR =, , , ,22,若X=x1,x2,x3,xm Y=y1,y2,y3,yn Z=z1,z2,z3,zp R是X到Y的关系，关系矩阵MR是mn阶矩阵, S是Y到Z的关系，关系矩阵MS是np阶矩阵. 设C=R S, 关系矩阵MC为mp阶矩阵，其中,用矩阵表示两个关系的复合,23,R是X到Y的关系，S是Y到Z的关系， R=(1,2),(3,4),(2,2)， S=(4,2),(2,5),(3,1),(1,3)，则

10、,例题,设 X=1,2,3, Y=1,2,3,4, Z=1,2,3,4,5,24,基本运算的性质,定理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.,25,定理4.2 设F, G, H是任意的关系, 则 (1) (FG)H=F(GH) (2) (FG)1= G1F1 证 (1) 任取, (FG)H t (FGH)

11、t (s (FG)H) t s (FGH) s (Ft (GH) s (FGH) F(GH) 所以 (FG)H = F(GH),基本运算的性质（续）,26,(2) 任取, (FG)1 FG t (F(t, x)G) t (G1(t, y)F1) G1F1 所以 (FG)1 = G1F1,基本运算的性质（续）,27,定理4.3 设 R 为 A上的关系, 则 RIA= IAR = R 证明任取 RIA t (RIA) t (Rt=yyA) R 从而有RIA=R. 同理可证 IAR=R.,基本运算的性质（续）,28,A上关系的幂运算定义,定义4.13 设R为A上的关系, n为自然数, 则 R 的 n

12、次幂是 (1) R0 = | xA = IA (2) Rn+1 = RnR 注意： 对于A上的任何关系R1和R2都有 R10 = R20 = IA 对于A上的任何关系 R 都有 R1 = R,29,幂运算的方法,对于集合表示的关系R，计算Rn 就是 n 个 R 合成 . 矩阵表示的关系就是矩阵相乘, 其中相加采用逻辑加. 例3 设A = a, b, c, d, R = , 求R的各次幂, 分别用矩阵和关系图表示.解 R与R2的关系矩阵分别为,30,同理R3和R4的矩阵是： 因此M4 = M2, 即R4 = R2. 因此可以得到R2 = R4 = R6 = , R3 = R5 = R7 = 而R

13、0 = IA的关系矩阵,幂运算的方法（续）,31,用关系图的方法得到R0, R1, R2, R3,的关系图如下图所示,幂运算的方法（续）,32,幂运算的性质,定理4.4 设 A 为 n 元集, R是A上的关系, 则存在自然数 s 和 t, 使得 Rs = Rt. 证 R 为A上的关系, 由于|A| = n, A上的不同关系只有 个. 当列出 R 的各次幂 R0, R1, R2, , , , 必存在自然数 s 和 t 使得 Rs = Rt.,33,定理4.5 设 R 是 A 上的关系, m, nN, 则 (1) RmRn = Rm+n (2) (Rm)n = Rmn 证 用归纳法 (1) 对于任

14、意给定的 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.,幂运算的性质（续）,34,(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.,幂运算的性质

15、（续）,35,定理4.6 设R 是A上的关系, 若存在自然数 s, t (st) 使得 Rs = Rt, 则 (1) 对任何 kN 有 Rs+k = Rt+k (2) 对任何 k, iN 有Rs+kp+i = Rs+i, 其中p = ts (3) 令S=R0,R1, , Rt1, 则对于任意的 qN有 RqS 证明 (1) Rs+k = RsRk = RtRk = Rt+k （2）对 k 归纳. 若k=0, 则有 Rs+0p+i = Rs+i 假设 Rs+kp+i = Rs+i, 其中p = ts, 则 Rs+(k+1)p+i = Rs+kp+i+p = Rs+kp+iRp = Rs+iRp

16、= Rs+p+i = Rs+ts+i = Rt+i = Rs+i 由归纳法命题得证.,幂运算的性质（续）,36,(3) 任取 qN, 若qt, 显然有 RqS. 若 qt, 则存在自然数 k 和 i 使得 q = s+kp+i，其中0ip1. 于是 Rq = Rs+kp+i = Rs+i 而 s+i s+p1 = s+ts1 = t1 这就证明了 RqS.,幂运算的性质（续）,37,4.3 关系的性质,4.3.1关系性质的定义和判别 自反性与反自反性 对称性与反对称性 传递性 4.3.2 关系的闭包 闭包定义 闭包计算 Warshall算法,38,自反性与反自反性,定义4.14 设R为A上的关

17、系, (1) 若x(xAR), 则称R在A上是自反的. (2) 若x(xAR), 则称R在A上是反自反的. 自反：A上的全域关系EA, 恒等关系IA, 小于等于关系LA, 整除关系DA 反自反：实数集上的小于关系、幂集上的真包含关系.,R2自反, R3 反自反, R1既不自反也不反自反.,例1 A = a, b, c, R1, R2, R3 是 A上的关系, 其中 R1 = , R2 = , R3 = ,39,对称性与反对称性,例2 设Aa,b,c, R1, R2, R3和R4都是A上的关系, 其中 R1,， R2, R3,， R4,定义4.15 设R为A上的关系,(1) 若xy(x,yARR

18、), 则称R为A上 对称的关系.(2) 若xy(x,yARRx=y), 则称R 为A上的反对称关系.实例 对称：A上的全域关系EA, 恒等关系IA和空关系 反对称：恒等关系IA，空关系是A上的反对称关系,R1 对称、反对称. R2 对称. R3 反对称. R4 不对称、也不反对称,40,传递性,例3 设Aa, b, c, R1, R2, R3是A上的关系, 其中 R1, R2, R3,定义4.16 设R为A上的关系, 若 xyz(x,y,zARRR),则称R是A上的传递关系.实例：A上的全域关系 EA, 恒等关系 IA 和空关系 , 小 于等于关系, 小于关系, 整除关系, 包含关系, 真包含

19、关系,R1 和 R3 是A上的传递关系, R2不是A上的传递关系.,41,关系性质的充要条件,设 R 为 A 上的关系, 则 (1) R 在 A 上自反当且仅当 IA R (2) R 在 A 上反自反当且仅当 RIA= (3) R 在 A 上对称当且仅当 R=R1 (4) R 在 A 上反对称当且仅当 RR1IA (5) R 在 A 上传递当且仅当 RRR,42,自反性证明,证明模式 证明 R 在 A 上自反 任取 x, xA . . R 前提 推理过程 结论,例4 证明若 IA R ，则 R 在 A 上自反. 证 任取x, xA IA R 因此 R 在 A 上是自反的.,43,对称性证明,证

20、明模式 证明 R 在 A 上对称 任取 R . . R 前提 推理过程 结论,例5 证明若 R=R1 , 则 R 在A上对称. 证 任取 R R 1 R 因此 R 在 A 上是对称的.,44,反对称性证明,证明模式 证明 R 在 A 上反对称 任取 RR . x=y 前提 推理过程 结论,例6 证明若 RR1IA , 则 R 在 A 上反对称. 证 任取 R R R R 1 RR 1 IA x=y 因此 R 在 A 上是反对称的.,45,传递性证明,证明模式 证明 R 在 A上传递 任取， RR . R 前提 推理过程 结论,例7 证明若 RRR , 则 R 在 A 上传递. 证 任取， R

21、R RR R 因此 R 在 A 上是传递的.,46,关系性质判别,47,实例,例8 判断下图中关系的性质, 并说明理由,(3) 自反，不是反自反；反对称，不是对称；不传递.,(1) 不是自反也不是反自反；对称, 不是反对称；不传递.,(2) 反自反, 不是自反；反对称, 不是对称；传递.,48,运算与性质的关系,49,闭包定义,定义4.17 设R是非空集合A上的关系, R 的自反 (对称或传递) 闭包 是A上的关系R, 使得 R 满足以下条件： (1) R 是自反的（对称的或传递的） (2) R R (3) 对A上任何包含R 的自反（对称或传递）关系R 有 R R . 一般将 R 的自反闭包记

22、作 r(R), 对称闭包记作 s(R), 传递 闭包记作 t(R).,50,闭包的构造方法,集合表示 定理4.7 设R为A上的关系, 则有 (1) r(R)=RR0 (2) s(R)=RR1 (3) t(R)=RR2R3 说明： 对于有穷集合A (|A|=n) 上的关系, (3)中的并最多不超过Rn. 若R 是自反的，则 r(R)=R; 若 R 是对称的，则 s(R)=R;若 R 是传递的，则 t(R)=R.,51,定理4.7的证明,只证 (1) 和 (3) 证 r(R)=RR0 只需证明RR0 满足闭包定义. RR0包含了R 由IARR0可知 RR0 在 A上是自反的. 下面证明RR0是包含

23、R 的最小的自反关系. 假设R 是包含R 的自反关系，那么IAR , RR ， 因此有 RR0=IAR R ,52,任取和 RR2R3. RR2R3. RR2R3. 于是，由RR2R3.的传递性得 t(R) RR2R3 对n 进行归纳证明 Rn t(R). n=1时显然为真. 假设n=k时为真，那么对于任意 Rk+1 RkR t (Rk R) t (t(R)t(R) t(R) （t(R)传递） 于是， RR2R3 t(R),定理4.7的证明（续）,53,矩阵表示 设关系R, r(R), s(R), t(R)的关系矩阵分别为M, Mr, Ms 和 Mt , 则 Mr =M + E Ms =M +

24、 M Mt =M + M2 + M3 + 其中E 是和 M 同阶的单位矩阵, M 是 M 的转置矩阵. 注意：在上述等式中矩阵的元素相加时使用逻辑加. ,闭包的构造方法（续）,54,图表示 设关系R, r(R), s(R), t(R)的关系图分别记为G, Gr, Gs, Gt , 则Gr, Gs, Gt 的顶点集与G 的顶点集相等. 除了G 的边以外, 以下述方法添加新的边： 考察G 的每个顶点, 如果没有环就加上一个环. 最终得到的是Gr. 考察G 的每一条边, 如果有一条 xi 到 xj 的单向边, ij, 则在G中加一条 xj 到 xi 的反方向边. 最终得到Gs. 考察G 的每个顶点

25、xi, 找从 xi 出发的每一条路径，如果从 xi 到路径中的任何结点 xj 没有边，就加上这条边. 当检查完所有的顶点后就得到图Gt .,闭包的构造方法（续）,55,实例,例1 设A=a,b,c,d, R=, R和 r(R), s(R), t(R)的关系图如下图所示.,R,r(R),s(R),t(R),56,传递闭包的计算Warshall算法,算法思路： 考虑 n+1个矩阵的序列M0, M1, , Mn , 将矩阵 Mk 的 i 行 j 列的元素记作Mki,j. 对于k=0,1,n, Mki,j=1当且仅当在 R 的关系图中存在一条从 xi 到 xj 的路径，并且这条路径 除端点外中间只经过

26、x1, x2, , xk中的顶点. 不难证明M0 就是R 的关系矩阵，而 Mn 就对应了R 的传递闭包. Warshall算法： 从M0开始，顺序计算 M1, M2, , 直到 Mn 为止.,57,Warshall算法的依据,从 Mk i, j 计算 Mk+1i, j: i, jV. 顶点集 V1=1,2, , k, V2=k+2, ,n, V=V1k+1V2， Mk+1i,j=1 存在从i 到 j 中间只经过V1k+1中点的路径 这些路径分为两类： 第1类：只经过 V1中点 第2类：经过 k+1点 存在第1类路径：Mki,j=1 存在第2类路径： Mki,k+1=1Mkk+1,j=1,58,

27、Warshall算法及其效率,算法4.1 Warshall算法 输入：M （R 的关系矩阵） 输出：Mt （t(R)的关系矩阵） 1. MtM 2. for k1 to n do 3. for i1 to n do 4. for j1 to n do 5. Mti, j Mti, j + Mti, kMtk, j,时间复杂度 T(n)=O(n3),59,4.4 等价关系与偏序关系,4.4.1 等价关系 4.4.2 等价类和商集 4.4.3 集合的划分 4.4.4 偏序关系 4.4.5 偏序集与哈斯图,60,等价关系的定义与实例,定义4.18 设R为非空集合上的关系. 如果R是自反的、对称的和传

28、递的, 则称R为A上的等价关系. 设 R 是一个等价关系, 若R, 称 x等价于y, 记做xy. 例1 设 A=1, 2, , 8, 如下定义 A上的关系R： R=| x,yA xy (mod 3)其中 xy (mod 3) 叫做 x与y 模3相等, 即 x 除以3的余数与 y 除以3的余数相等. 不难验证R为A上的等价关系, 因为 xA, 有xx(mod 3) x,yA, 若xy(mod 3), 则有yx(mod 3) x,y,zA, 若xy(mod 3), yz(mod 3), 则有 xz(mod 3),61,模3等价关系的关系图,设 A=1, 2, , 8, R= | x,yA xy (

29、mod 3) R 的关系图如下：,62,等价类,定义4.19 设R为非空集合A上的等价关系, xA，令 xR = y | yA xRy 称 xR 为x关于R 的等价类, 简称为 x 的等价类, 简记为x. 实例 A= 1, 2, , 8 上模 3 等价关系的等价类： 1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,6,63,等价类的性质,定理4.8 设R是非空集合A上的等价关系, 则 (1) xA, x 是A的非空子集. (2) x, yA, 如果 xRy, 则 x=y. (3) x, yA, 如果 x y, 则 x与y不交. (4) ，即所有等价类的并集就是A. ,64,性质的证

30、明,(1)由等价类定义可知, xA有xA. 由自反性有xRx，因此xx, 即x非空. (2)任取z, 则有zx R R R R R R 从而证明了zy. 综上所述必有xy. 同理可证y x. 这就得到了x=y. (3) 假设xy, 则存在zxy, 从而有 zx zy, 即R R 成立. 根据R 的对称性和传递性必有R, 与x y矛盾,65,性质的证明（续）,(4) 先证 . 任取y, y x (xA yx) yx xA yA 从而有 . 再证A . 任取y, yA yy yA y 从而有A 成立. 综上所述得,66,商集,定义4.20 设R 为非空集合A 上的等价关系, 以R 的所有等 价类作

31、为元素的集合称为A关于R 的商集, 记做 A/R, A/R = xR | xA 例2 令A=1, 2, , 8，A关于模 3 等价关系R 的商集为 A/R = 1, 4,7, 2, 5, 8, 3, 6 A关于恒等关系和全域关系的商集为： A/IA = 1,2, ,8 A/EA = 1, 2, ,8 ,67,集合的划分,定义4.21 设A为非空集合, 若A的子集族 ( P(A) 满足下面条件： (1) (2) xy (x,yxyxy=) (3) =A 则称是A的一个划分, 称 中的元素为A的划分块. 例3 设Aa, b, c, d, 给定 1, 2, 3, 4, 5, 6如下： 1=a, b,

32、 c,d， 2=a, b,c,d 3=a,a, b, c, d， 4=a, b,c 5=,a, b,c, d， 6=a,a,b, c, d 则 1和 2是A的划分, 其他都不是A的划分.,68,等价关系与划分的一一对应,商集 A/R 就是A 的一个划分 不同的商集对应于不同的划分 任给A 的一个划分 , 如下定义A 上的关系 R：R = | x, yA x 与 y 在的同一划分块中 则R 为A上的等价关系, 且该等价关系确定的商集就是.,例4 给出A1,2,3上所有的等价关系 求解思路：先做出A的所有划分, 然后根据划分写出 对应的等价关系.,69,例 4, 1, 2和 3分别对应于等价关系

33、R1, R2和R3.其中 R1=,IA R2=,IA R3=,IA,A上的等价关系与划 分之间的对应： 4对应于全域关系EA 5对应于恒等关系IA,70,实例,根据有序对的 x+y=2,3,4,5,6,7,8 将AA划分. (AA)/R=, , , , , , , , , , , , , , ,例5 设A=1,2,3,4，在AA上定义二元关系 R： ,R x+y = u+v， 求R 导出的划分.,解 AA=, , , , , , , , , , , , , , ,71,偏序关系,定义4.22 非空集合A上的自反、反对称和传递的关系，称为A上的偏序关系，记作. 设为偏序关系, 如果 , 则记作

34、xy, 读作 x“小于或等于”y. 实例 集合A上的恒等关系 IA 是A上的偏序关系. 小于或等于关系, 整除关系和包含关系也是相应集合上的偏序关系.,72,相关概念,定义4.23 x与y可比 设R为非空集合A上的偏序关系, x, yA, x与y 可比 xy yx.结论：x, yA，下述几种情况发生其一且仅发生其一. xy, yx, xy, x与y不可比定义4.24 拟序 R为非空集合A上的关系,如果R是反自反和传递的，则称R是A上的拟序关系，简称为拟序，记作. 定义4.25 全序 R为非空集合A上的偏序, x, yA, x与y 都可比，则称R为全序. 定义4.26 覆盖 x,yA, 如果xy

35、且不存在 zA使得 xzy, 则称 y覆盖x. 实例：数集上的小于或等于关系是全序关系 整除关系不是正整数集合上的全序关系 1, 2, 4, 6集合上的整除关系, 2覆盖1, 4 和 6 覆盖2. 但4不覆盖1.,73,偏序集与哈斯图,定义4.27 集合A和A上的偏序关系一起叫做偏序集, 记作.实例：整数集和数的小于等于关系构成偏序集 幂集P(A)和包含关系构成偏序集. 哈斯图：利用偏序自反、反对称、传递性简化的关系图 特点： 每个结点没有环 两个连通的结点之间的序关系通过结点位置的高低 表示，位置低的元素的顺序在前 具有覆盖关系的两个结点之间连边,74,哈斯图实例,例6 ,75,例7 已知偏序集 的哈斯图如下图所示, 试求出集合A和关系 R的表达式.,哈斯图实例（续）,A=a, b, c, d, e, f, g, h R=, IA,76,偏序集的特定元素,定义4.28 设为偏序集, BA, yB. (1) 若x(xByx)成立, 则称 y 为 B 的最小元. (2) 若x(xBxy)成立, 则称 y 为 B 的最大元. (3) 若x(xBxyx=y)成立, 则称 y