《离散数学屈婉玲第七章.ppt》由会员分享，可在线阅读，更多相关《离散数学屈婉玲第七章.ppt（90页珍藏版）》请在三一文库上搜索。
1、1,主要内容 有序对与笛卡儿积 二元关系的定义与表示法 关系的运算 关系的性质 关系的闭包 等价关系与划分 偏序关系,第七章 二元关系,2,7.1 有序对与笛卡儿积,定义7.1 由两个元素 x 和 y，按照一定的顺序组成的二元组 称为有序对，记作. 有序对性质: (1) 有序性 （当xy时） (2) 与相等的充分必要条件是 = x=uy=v.,3,笛卡儿积,定义7.2 设A,B为集合，A与B的笛卡儿积记作AB，且 AB = | xAyB.,例1 A=1,2,3, B=a,b,c AB =, BA =, A=, B= P(A)A = , P(A)B = ,4,笛卡儿积的性质,(1) 不适合交换律
2、 AB BA (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) ACBDABCD. (6) 若 |A| = m, |B| = n, 则 |AB| = mn,5,性质证明,证明 A(BC) = (AB)(AC),证 任取 A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)
3、(AC) 所以有A(BC) = (AB)(AC).,6,实例,例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.,7,7.2 二元关系,定义7.3 如果一个集合满足以下条件之一： (1) 集合非空, 且它的元素都是有序对 (2) 集合是空集 则称该集合为一个二元关系, 简称为关系，记作R. 如果R, 可记作xRy；如果R, 则记作x y 实例：R=, S=,a,b. R是二元关系, 当a, b不是
4、有序对时，S不是二元关系 根据上面的记法，可以写1R2, aRb, a c等.,8,A到B的关系与A上的关系,定义7.4 设A,B为集合, AB的任何子集所定义的二元关系叫做从A 到B的二元关系, 当A=B时则叫做A上的二元关系.,例3 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的子集有个. 所以 A上有 个不同的二元关系. 例如 |A| = 3, 则 A上有=512个不同的二元关系.,9,A上重要关系的实例,定义7
5、.5 设 A 为集合, (1) 是A上的关系，称为空关系 (2) 全域关系 EA = | xAyA = AA 恒等关系 IA = | xA 小于等于关系 LA = | x,yAxy, A为实数子集 整除关系 DB = | x,yBx整除y, A为非0整数子集 包含关系 R = | x,yAxy, A是集合族.,10,实例,例如, A=1, 2, 则 EA = , IA = , 例如 A = 1, 2, 3, B=a, b, 则 LA = , DA = , 例如 A = P(B) = ,a,b,a,b, 则 A上的包含关系是 R = , , 类似的还可以定义： 大于等于关系, 小于关系, 大于关
6、系, 真包含关系等.,11,关系的表示,1. 关系矩阵 若A=x1, x2, , xn，R是A上的关系，R的关系矩阵是布尔矩阵MR = (rij )nn, 其中 rij = 1 R 2. 关系图 若A= x1, x2, , xm，R是从A上的关系，R的关系图是GR=, 其中A为结点集，R为边集. 如果属于 关系R，在图中就有一条从 xi 到 xj 的有向边. 注意： 关系矩阵适合表示有穷集A上的关系（可推广为从A到B的关系） 关系图适合表示有穷集A上的关系,12,实例,例4 A=1,2,3,4, R=, R的关系矩阵MR和关系图GR如下：,13,7.3 关系的运算,关系的基本运算 定义7.6
7、关系的定义域、值域与域分别定义为 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,14,关系运算(逆与合成),定义7.7 关系的逆运算 R1 = | R 定义7.8 关系的合成运算 FG = | t (F G) ,例6 R = , , , S = , , , , R1 = , , , RS = , , SR = , , , ,15,合成的图示法,利用图示（不是关系图）方法求合成 RS =, , SR =, , , ,16,关系运算(限制与像
8、),定义7.9 设R为二元关系, A是集合 (1) R在A上的限制记作 RA, 其中 RA = | xRyxA (2) A在R下的像记作RA, 其中 RA=ran(RA) 说明： R在A上的限制 RA是 R 的子关系，即 RA R A在R下的像 RA 是 ranR 的子集，即 RA ranR,17,实例,例7 设R=, 则 R1 = , R = R2,3 = , R1 = 2,3 R = R3 = 2,18,关系运算的性质,定理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.,19,定理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),20,证明,(2) 任取, (FG)1 FG t (FG) t (G1F1) G1 F1所以 (F G)1 = G1 F1
10、,21,关系运算的性质,定理7.3 设R为A上的关系, 则 RIA= IAR=R,证任取 RIA t (RIA) t (Rt=yyA) R,22,关系运算的性质,定理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)=FGFH,23,推广,定理7.4 的结论可以推广到有限多个关系 R(R1R2Rn) = RR1RR2RRn (R1R2Rn)R = R1RR2R
11、RnR R(R1R2 Rn) RR1RR2 RRn (R1R2 Rn)R R1RR2R RnR,24,关系运算的性质,定理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,25,证明,证 只证 (1) 和 (4). (1) 任取 F (AB) FxAB F(xAxB) (FxA)(FxB) F AF B F AF B 所以有F (AB) = F AF B.,26,证明,(4) 任取y, yF AB x (FxAB) x (FxAxB) x (FxA)(
12、FxB) x (FxA)x (FxB) yF AyF B yF AF B 所以有F AB=F AF B.,27,关系的幂运算,定义7.10 设 R 为 A 上的关系, n为自然数, 则 R 的 n 次幂定义为： (1) R0 = | xA = IA (2) Rn+1 = RnR 注意： 对于A上的任何关系 R1 和 R2 都有 R10 = R20 = IA 对于A上的任何关系 R 都有 R1 = R,28,例 8 设A = a,b,c,d, R = , 求R的各次幂, 分别用矩阵和关系图表示.,解 R 与 R2的关系矩阵分别是：,幂的求法,29,R3和R4的矩阵是： 因此M4=M2, 即R4=
13、R2. 因此可以得到 R2=R4=R6=， R3=R5=R7= R0的关系矩阵是 ,幂的求法,30,关系图,R0, R1, R2, R3,的关系图如下图所示.,R0,R1,R2=R4=,R3=R5=,31,幂运算的性质,定理7.6 设 A 为 n 元集, R 是A上的关系, 则存在自然数 s 和 t, 使得 Rs = Rt.,证 R 为A上的关系, 由于|A|=n, A上的不同关系只有 个. 列出 R 的各次幂 R0, R1, R2, , , , 必存在自然数 s 和 t 使得 Rs = Rt,32,定理7.7 设 R 是 A上的关系, m, nN, 则 (1) RmRn = Rm+n (2)
14、 (Rm)n = Rmn,幂运算的性质,证 用归纳法 (1) 对于任意给定的mN, 施归纳于n. 若n=0, 则有 RmR0 = RmIA = Rm = Rm+0 假设 RmRn = Rm+n, 则有 RmRn+1 = Rm (Rn R) = (Rm Rn)R = Rm+n+1 , 所以对一切m,nN 有 RmRn = Rm+n.,33,证明,(2) 对于任意给定的mN, 施归纳于n. 若n=0, 则有 (Rm)0 = IA = R0 = Rm0 假设 (Rm)n = Rmn, 则有 (Rm)n+1 = (Rm)nRm = (Rmn)Rn = Rmn+m = Rm(n+1) 所以对一切m,nN
15、 有 (Rm)n = Rmn.,34,定理7.8 设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 = Rt Rk = 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
16、+iRp = Rs+iRp = Rs+p+i = Rs+ts+i = Rt+i = Rs+i 由归纳法命题得证.,35,证明,(3) 任取 qN, 若 q t, 显然有 RqS, 若q t, 则存在自然数 k 和 i 使得 q = s+kp+i, 其中0ip1. 于是 Rq = Rs+kp+i = Rs+i 而 s+i s+p1 = s+ts1 = t1 从而证明了 RqS.,36,7.4 关系的性质,定义7.11 设 R 为A上的关系, (1) 若 x(xAR), 则称 R 在 A 上是自反的. (2) 若 x(xAR), 则称 R 在 A 上是反自反的.,实例： 自反：全域关系EA, 恒等
17、关系IA, 小于等于关系LA, 整除关系DA 反自反：实数集上的小于关系、幂集上的真包含关系. A=1,2,3, R1, R2, R3是A上的关系, 其中 R1, R2, R3 R2 自反 ，R3 反自反，R1既不是自反的也不是反自反的.,37,对称性与反对称性,定义7.12 设 R 为 A上的关系, (1) 若xy( x,yARR), 则称 R 为 A上对 称的关系. (2) 若xy( x,yARRx=y), 则称 R 为 A上的反对称关系.,实例：对称关系：A上的全域关系EA, 恒等关系IA和空关系 反对称关系：恒等关系IA和空关系也是A上的反对称关系. 设A1,2,3, R1, R2,
18、R3和R4都是A上的关系, 其中 R1,，R2, R3,，R4, R1：对称和反对称； R2：只有对称；R3：只有反对称； R4：不对称、不反对称,38,传递性,定义7.13 设R为A上的关系, 若 xyz(x,y,zARRR), 则称 R 是A上的传递关系.,实例： A上的全域关系 EA,恒等关系 IA和空关系 ，小于等 于和小于关系，整除关系，包含与真包含关系 设 A1,2,3, R1, R2, R3是A上的关系, 其中 R1, R2, R3 R1和R3是A上的传递关系, R2不是A上的传递关系.,39,关系性质成立的充要条件,定理7.9 设R为A上的关系, 则 (1) R 在A上自反当且
19、仅当 IA R (2) R 在A上反自反当且仅当 RIA = (3) R 在A上对称当且仅当 R=R1 (4) R 在A上反对称当且仅当 RR1 IA (5) R 在A上传递当且仅当 RR R,40,证明,证明 只证(1)、(3)、(4)、(5) (1) 必要性 任取, 由于R 在A上自反必有 IA x,yAx=y R 从而证明了IAR 充分性. 任取x, 有 xA IA R 因此 R 在A上是自反的.,41,证明,(3) 必要性. 任取, R R R1 所以 R = R1 充分性. 任取, 由R = R1得R R1 R 所以R在A上是对称的,42,证明,(4) 必要性. 任取, 有 RR1
20、RR1 RR x=y x,yA IA 这就证明了RR1IA 充分性. 任取, RR RR1 RR1 IA x=y 从而证明了R在A上是反对称的.,43,证明,(5) 必要性. 任取有 RR t (RR) R 所以 RR R 充分性. 任取,R, 则 RR RR R 所以 R 在 A上是传递的,44,关系性质的三种等价条件,45,关系性质的判别,例9 判断下列各图的性质 (a) (b) (c),解： (a) 对称 (b) 反自反、反对称、传递 (c) 自反、反对称,46,关系的性质和运算之间的联系,47,7.5 关系的闭包,主要内容 闭包定义 闭包的构造方法 集合表示 矩阵表示 图表示 闭包的性
21、质,48,闭包定义,定义7.14 设R是非空集合A上的关系, R的自反(对称或传递)闭 包是A上的关系R, 使得R满足以下条件： (1) R是自反的(对称的或传递的) (2) RR (3) 对A上任何包含R的自反(对称或传递)关系R 有RR R的自反闭包记作r(R), 对称闭包记作s(R), 传递闭包记作t(R).,定理7.10 设R为A上的关系, 则有 (1) r(R)=RR0 (2) s(R)=RR1 (3) t(R)=RR2R3 说明：对有穷集A(|A|=n)上的关系, (3)中的并最多不超过Rn,49,证明,证 只证(1)和(3). (1) 由IA=R0RR0 知 RR0是自反的, 且
22、满足RRR0 设R 是A上包含R的自反关系, 则有RR 和IA R . 从而有 RR0R. RR0满足闭包定义, 所以r(R)=RR0.,(1) 先证 RR2 t(R)成立. 用归纳法证明对任意正整数n 有Rn t(R). n=1时有R1=R t(R). 假设Rnt(R)成立, 那么对任意的 Rn+1=RnR t ( RnR) t (t(R)t(R) t(R) 这就证明了Rn+1t(R). 由归纳法命题得证. ,50,证明,再证 t(R) RR2成立, 为此只须证明RR2传递. 任取, 则 RR2RR2 t (Rt)s(Rs) t s (RtRs ) t s (Rt+s ) RR2 从而证明了
23、RR2是传递的.,51,闭包的矩阵表示和图表示,设关系R, r(R), s(R), t(R)的关系矩阵分别为M, Mr , Ms 和 Mt 则 Mr=M+E Ms=M+M Mt=M+M2+M3+ E 是单位矩阵, M 是 转置矩阵，相加时使用逻辑加.,设关系R, r(R), s(R), t(R)的关系图分别记为G, Gr, Gs, Gt, 则Gr , Gs , Gt 的顶点集与G 的顶点集相等. 除了G 的边以外, 以下述 方法添加新的边： (1) 考察G 的每个顶点, 若没环就加一个环，得到Gr (2) 考察G 的每条边, 若有一条 xi 到 xj 的单向边, ij, 则在G 中加一条 xj
24、 到 xi 的反向边, 得到Gs (3) 考察G 的每个顶点 xi, 找 xi 可达的所有顶点 xj (允许i=j )， 如果没有从 xi 到 xj 的边, 就加上这条边, 得到图Gt,52,实例,例9 设A=a,b,c,d, R=, R和r(R), s(R), t(R)的关系图如下图所示.,53,求传递闭包的算法,算法 Warshall 输人：M（R的关系矩阵） 输出：MT（t(R)的关系矩阵） 1MTM 2for k1 to n do 3 for i1 to n do 4 for j1 to n do 5 MTi,jMTi,j+MTi,k MTk,j,54,实例,设A=a,b,c,d, R
25、=, R的传递闭包的矩阵如下：,55,闭包的性质,定理7.11 设R是非空集合A上的关系, 则 (1) R是自反的当且仅当 r(R)=R. (2) R是对称的当且仅当 s(R)=R. (3) R是传递的当且仅当 t(R)=R.,定理7.12 设R1和R2是非空集合A上的关系, 且 R1R2, 则 (1) r(R1) r(R2) (2) s(R1) s(R2) (3) t(R1) t(R2),证明 略,56,定理7.13 设R是非空集合A上的关系, (1) 若R是自反的, 则 s(R) 与 t(R) 也是自反的 (2) 若R是对称的, 则 r(R) 与 t(R) 也是对称的 (3) 若R是传递的
26、, 则 r(R) 是传递的. 说明：如果需要进行多个闭包运算，比如求R的自反、对 称、传递的闭包 tsr(R)，运算顺序如下： tsr(R) = rts(R) = trs(R),闭包的性质,证明 略,57,7.6 等价关系与划分,主要内容 等价关系的定义与实例 等价类及其性质 商集与集合的划分 等价关系与划分的一一对应,58,7.6 等价关系与划分,定义7.15 设R为非空集合上的关系. 如果R是自反的、对称的和 传递的, 则称R为A上的等价关系. 设 R 是一个等价关系, 若 R, 称 x等价于y, 记做xy.,实例 设 A=1,2,8, 如下定义A上的关系R： R=| x,yAx y(mo
27、d 3) 其中x y(mod 3)叫做 x与 y 模3相等, 即x除以3的余数与y除以 3的余数相等. 不难验证 R 为A上的等价关系, 因为 (1) xA, 有 x x (mod 3) (2) x,yA, 若x y(mod 3), 则有y x(mod 3) (3) x,y,zA, 若x y(mod 3), y z(mod 3), 则有x z(mod 3),59,模 3 等价关系的关系图,等价关系的实例,60,等价类定义,定义7.16 设R为非空集合A上的等价关系, xA，令 xR = y | yAxRy 称xR 为x关于R的等价类, 简称为x的等价类, 简记为x或 实例 A=1, 2, ,
28、8上模3等价关系的等价类： 1 = 4 = 7 = 1, 4, 7 2 = 5 = 8 = 2, 5, 8 3 = 6 = 3, 6,61,等价类的性质,定理7.14 设R是非空集合A上的等价关系, 则 (1) xA, x是A的非空子集 (2) x,yA, 如果 xRy, 则 x = y (3) x,yA, 如果 x y, 则 x与y不交 (4) x | xA=A,证 (1) 由定义, xA有xA. 又xx, 即x非空. (2) 任取 z, 则有 zx R R RR R R 从而证明了zy. 综上所述必有 xy. 同理可证 yx. 这就得到了x = y.,62,证明,(3) 假设 xy, 则存
29、在 zxy, 从而有zxzy, 即RR成立. 根据R的对称性和传递性必有 R, 与 x y矛盾,(4) 先证x | xA A. 任取y, yx | xA x(xAyx) yxx A yA 从而有x | xA A 再证A x | xA. 任取y, yA yyyA yx | xA 从而有x | xA A成立. 综上所述得x | xA = A.,63,商集与划分,定义7.17 设 R 为非空集合A上的等价关系, 以 R 的所有等价 类作为元素的集合称为A关于R的商集, 记做A/R, A/R = xR | xA 实例 设 A=1,2,8，A关于模3等价关系R的商集为 A/R = 1,4,7, 2,5,
30、8, 3,6 A关于恒等关系和全域关系的商集为： A/IA = 1, 2, , 8， A/EA = 1,2,8,定义7.18 设A为非空集合, 若A的子集族( P(A)满足: (1) (2) xy(x,yxyxy=) (3) = A 则称是A的一个划分, 称中的元素为A的划分块.,64,划分实例,例10 设 A a, b, c, d , 给定 1, 2, 3, 4, 5, 6如下： 1= a, b, 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的划分, 其
31、他都不是A的划分.,65,例11 给出 A1,2,3上所有的等价关系,实例,1对应 EA, 5 对应 IA, 2, 3 和 4分别对应 R2, R3和 R4. R2=,IA R3=,IA R4=,IA,解 先做出A的划分, 从左到右分别记作 1, 2, 3, 4, 5.,66,7.7 偏序关系,主要内容 偏序关系 偏序关系的定义 偏序关系的实例 偏序集与哈斯图 偏序集中的特殊元素及其性质 极大元、极小元、最大元、最小元 上界、下界、最小上界、最大下界,67,定义与实例,定义7.19 偏序关系：非空集合A上的自反、反对称和传递的关系， 记作. 设为偏序关系, 如果 , 则记作 x y, 读作 x
32、“小于或等于”y. 实例 集合A上的恒等关系 IA是 A上的偏序关系. 小于或等于关系, 整除关系和包含关系也是相应集合上的偏 序关系.,68,相关概念,定义7.20 设 R 为非空集合A上的偏序关系, (1) x, yA, x与y可比 x yy x (2) 任取元素 x 和 y, 可能有下述几种情况发生： x y (或 y x), xy, x与y不是可比的,定义7.21 R 为非空集合A上的偏序关系, (1) x,yA, x与y都是可比的，则称R为全序（或线序） 实例：数集上的小于或等于关系是全序关系,整除关系不是正 整数集合上的全序关系,定义7.22 x,yA, 如果 xy 且不存在 zA
33、 使得 xzy, 则称 y 覆盖x. 例如1,2,4,6集合上整除关系, 2覆盖1, 4和6覆盖2, 4不覆盖1.,69,偏序集与哈斯图,定义7.23 集合A和A上的偏序关系一起叫做偏序集, 记作 . 实例: , ,哈斯图: 利用偏序关系的自反、反对称、传递性进行简化的 关系图 特点： (1) 每个结点没有环 (2) 两个连通的结点之间的序关系通过结点位置的高低表 示，位置低的元素的顺序在前 (3) 具有覆盖关系的两个结点之间连边,70,实例,例12 偏序集和的 哈斯图.,71,例13 已知偏序集的哈斯图如下图所示, 试求出集合A 和关系R的表达式.,解 A= a, b, c, d, e, f
34、, g, h R=,IA,实例,72,偏序集中的特殊元素,定义7.24 设为偏序集, BA, yB (1) 若x(xByx)成立, 则称 y 为B的最小元 (2) 若x(xBxy)成立, 则称 y 为B的最大元 (3) 若x(xBxyx=y)成立, 则称 y 为B的极小元 (4) 若x(xByxx=y)成立, 则称 y 为B的极大元,性质： (1) 对于有穷集，极小元和极大元一定存在，可能存在多个. (2) 最小元和最大元不一定存在，如果存在一定惟一. (3) 最小元一定是极小元；最大元一定是极大元. (4) 孤立结点既是极小元，也是极大元.,73,定义7.25 设为偏序集, BA, yA (
35、1) 若x(xBxy)成立, 则称y为B的上界 (2) 若x(xByx)成立, 则称y为B的下界 (3) 令Cy| y为B的上界, C的最小元为B的最小上界或上确界 (4) 令Dy| y为B的下界, D的最大元为B的最大下界或下确界,偏序集中的特殊元素,性质： (1) 下界、上界、下确界、上确界不一定存在 (2) 下界、上界存在不一定惟一 (3) 下确界、上确界如果存在，则惟一 (4) 集合的最小元是其下确界，最大元是其上确界；反之不对.,74,实例,例14 设偏序集，求A的极小元、最小元、极大元、最 大元，设B b,c,d , 求B的下界、上界、下确界、上确界.,解 极小元：a, b, c,
36、 g； 极大元：a, f, h； 没有最小元与最大元. B的下界和最大下界都不存在； 上界有 d 和 f, 最小上界为 d.,75,实例,例15 设X为集合, AP(X)X, 且A. 若|X|=n, n2. 问： (1) 偏序集 是否存在最大元？ (2) 偏序集 是否存在最小元？ (3) 偏序集 中极大元和极小元的一般形式是什么？ 并说明理由.,解 (1) 不存在最小元和最大元, 因为n2. (2) 的极小元就是 X 的所有单元集, 即x, xX. (3) 的极大元恰好比 X 少一个元素, 即Xx, xX.,76,调度问题,有穷任务集T，m台相同的机器， T上存在偏序，若 t1t2, 任务t1
37、完成后 t2 才能开始 tT, l(t)是 t 需要的时间，d(t)是 t 的截止时间，l(t),d(t)Z+ 开始时间为0，:T0,1, 表示对任务集 T 的一个调度， 完成所有任务的时间：D=max(t)+l(t) | tT 可行调度 满足： (1) tT, (t)+l(t) d(t) 每个任务都在截止时间之前完成 (2) i, 0 i D, | t T | (t) i (t)+l(t) | m 至多m个任务并行 (3) t,tT, t t (t)+l(t) (t) 任务安排满足偏序,77,寻找最优调度,例16 m=2, T= t1, t2, , t6 l( ti ) 如图所示，d( ti
38、 )=7 拓扑排序: m=1，ti 都相等,78,第七章 习题课,主要内容 有序对与笛卡儿积的定义与性质 二元关系、从A到B的关系、A上的关系 关系的表示法：关系表达式、关系矩阵、关系图 关系的运算：定义域、值域、域、逆、合成、限制、像、幂 关系运算的性质: A上关系的自反、反自反、对称、反对称、传递的性质 A上关系的自反、对称、传递闭包 A上的等价关系、等价类、商集与A的划分 A上的偏序关系与偏序集,79,基本要求,熟练掌握关系的三种表示法 能够判定关系的性质（等价关系或偏序关系） 掌握含有关系运算的集合等式 掌握等价关系、等价类、商集、划分、哈斯图、偏序集等概念 计算AB, dom R,
39、ranR, fldR, R1, RS , Rn , r(R), s(R), t(R) 求等价类和商集A/R 给定A的划分，求出 所对应的等价关系 求偏序集中的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界 掌握基本的证明方法 证明涉及关系运算的集合等式 证明关系的性质、证明关系是等价关系或偏序关系,80,练习1,1设A = 1, 2, 3, R = | x, yA且x+2y 6 ， S = , , 求: (1) R的集合表达式 (2) R1 (3) dom R, ran R, fld R (4) RS, R3 (5) r(R), s(R), t(R),81,解答,(1) R = ,
40、 , , , (2) R1 = , , , , (3) domR = 1, 2, 3, ranR = 1,2, fldR = 1, 2, 3 (4) RS = , , , , , R3 = , , , , , (5) r(R) = , , , , , s(R) = , , , t(R) = , , , , , ,82,练习2,2设A=1,2,3,4，在AA上定义二元关系R： ,R x+y = u+v， 求R导出的划分.,AA=, , , , , , , , , , , , , , ,根据 中的 x+y = 2, 3, 4, 5, 6, 7, 8 将A划分成等价类： A/R=, , , , ,
41、, , , , , , , , , ,83,3设R是Z上的模 n 等价关系, 即 xy x y(modn), 试给出由R确定的Z的划分.,练习3,解 设除以 n 余数为 r 的整数构成等价类 r，则 r = kn+r | kZ , r = 0, 1, , n1 = r | r = 0, 1, , n1,84,图11,练习4,4设偏序集 的哈斯图如图所示. (1) 写出A和R的集合表达式 (2) 求该偏序集中的极大元、极小元、最大元、最小元,解 (1) A = a, b, c, d, e R = , , , , , , IA (2) 极大元和最大元是a, 极小元是d, e； 没有最小元.,85,
42、练习5,5设R是A上的二元关系， 设 S = | c(RR). 证明如果R是等价关系，则S也是等价关系。,证 R是A上的等价关系. (1) 证自反 任取x, xA R x (RR) S (2) 证对称 任取, S c(RR) c (RR) S (3) 证传递 任取, , S S c (RR) d (RR) R R S,86,6设偏序集和，定义AB上二元关系T: T xRu ySv 证明T为偏序关系.,练习6,证 (1) 自反性 任取, AB xAyB xRxySy T (2) 反对称性 任取, TT xRu ySv uRx vSy (xRu uRx) (ySv vSy) x=u y=v = (
43、3) 传递性 任取, TT xRu ySv uRw vSt (xRu uRw) (ySv vSt) xRw ySt T,87,关系性质的证明方法,1. 证明R在A上自反 任取x, xA . R 前提 推理过程 结论 2. 证明R在A上对称 任取， R . R 前提 推理过程 结论,88,3. 证明R在A上反对称 任取， RR . x = y 前提 推理过程 结论 4. 证明R在A上传递 任取,， RR . R 前提 推理过程 结论,关系性质的证明方法,89,7R,S为A上的关系，证明 RS t(R) t(S),练习7,证 只需证明对于任意正整数n, Rn Sn. 对n归纳. n=1, 显然为真. 假设对于n，命题为真，任取 Rn+1 RnR t (Rn R) t (Sn S) SnS Sn+1,90,数学归纳法（主要用于幂运算） 证明中用到关系运算的定义和公式, 如： xdomR y(R) yranR x(R) R R1 RS t (RS) RA xA R yRA x (xA R) r(R) = RIA s(R) = RR1 t(R) = RR2,关系等式或包含式的证明方法,