离散数学屈婉玲第七章ppt课件.ppt

1主要内容主要内容l 有序对与笛卡儿积有序对与笛卡儿积l 二元关系的定义与表示法二元关系的定义与表示法l 关系的运算关系的运算l 关系的性质关系的性质l 关系的闭包关系的闭包l 等价关系与划分等价关系与划分l 偏序关系偏序关系第七章第七章 二元关系二元关系27.1 有序对与笛卡儿积有序对与笛卡儿积定义定义7.1 由两个元素由两个元素 x 和和 y，按照一定的顺序组成的二元组，按照一定的顺序组成的二元组称为称为有序对有序对，记作，记作.有序对性质有序对性质: (1) 有序性有序性 （当（当x y时）时） (2) 与与相等的充分必要条件是相等的充分必要条件是 = x=u y=v. 3笛卡儿积笛卡儿积定义定义7.2 设设A,B为集合，为集合，A与与B的的笛卡儿积笛卡儿积记作记作A B，且，且 A B = | x A y B.例例1 A=1,2,3, B=a,b,c A B =, B A =, A=, B= P(A) A = , P(A) B = 4笛卡儿积的性质笛卡儿积的性质(1) 不适合交换律不适合交换律 A B B A (A B, A, B)(2) 不适合结合律不适合结合律 (A B) C A (B C) (A, B, C)(3) 对于并或交运算满足分配律对于并或交运算满足分配律 A (B C) = (A B) (A C) (B C) A = (B A) (C A) A (B C) = (A B) (A C) (B C) A = (B A) (C A) (4) 若若 A 或或 B 中有一个为空集，则中有一个为空集，则 A B 就是空集就是空集. A = B = (5) A C B DA B C D.(6) 若若 |A| = m, |B| = n, 则则 |A B| = mn 5性质证明性质证明证明证明 A (B C) = (A B) (A C)证证 任取任取 A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC)所以有所以有A(BC) = (AB)(AC).6实例实例例例2 (1) 证明证明A=B,C=D A C=B D (2) A C = B D是否推出是否推出 A=B,C=D? 为什么？为什么？解解 (1) 任取任取 A C x A y C x B y D B D(2) 不一定不一定.反例如下：反例如下： A=1，B=2, C = D = , 则则A C = B D但是但是A B.77.2 二元关系二元关系定义定义7.3 如果一个集合满足以下条件之一：如果一个集合满足以下条件之一：(1) 集合非空集合非空, 且它的元素都是有序对且它的元素都是有序对(2) 集合是空集集合是空集则称该集合为一个则称该集合为一个二元关系二元关系, 简称为关系，记作简称为关系，记作R.如果如果R, 可记作可记作xRy；如果；如果 R, 则记作则记作x y实例：实例：R=, S=,a,b. R是二元关系是二元关系, 当当a, b不是有序对时，不是有序对时，S不是二元关系不是二元关系根据上面的记法，可以写根据上面的记法，可以写1R2, aRb, a c等等. 8A到到B的关系与的关系与A上的关系上的关系定义定义7.4设设A,B为集合为集合, AB的任何子集所定义的二元关系叫做的任何子集所定义的二元关系叫做从从A到到B的二元关系的二元关系, 当当A=B时则叫做时则叫做A上的二元关系上的二元关系.22n例例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个不同的二元关系个不同的二元关系. 9A上重要关系的实例上重要关系的实例定义定义7.5 设设 A 为集合为集合, (1) 是是A上的关系，称为上的关系，称为空关系空关系(2) 全域关系全域关系 EA = | xAyA = AA 恒等关系恒等关系 IA = | xA 小于等于关系小于等于关系 LA = | x,yAxy, A为实数子集为实数子集 整除关系整除关系 DB = | x,yBx整除整除y, A为非为非0整数子集整数子集 包含关系包含关系 R = | x,yAx y, 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 = , ,类似的还可以定义：类似的还可以定义： 大于等于关系大于等于关系, 小于关系小于关系, 大于关系大于关系, 真包含关系等真包含关系等.11关系的表示关系的表示1. 关系矩阵关系矩阵 若若A=x1, x2, , xn，R是是A上的关系，上的关系，R的关系矩阵是布尔的关系矩阵是布尔矩阵矩阵MR = (rij )n n, 其中其中 rij = 1 R 2. 关系图关系图 若若A= x1, x2, , xm，R是从是从A上的关系，上的关系，R的关系图是的关系图是GR=, 其中其中A为结点集，为结点集，R为边集为边集. 如果如果属于属于 关系关系R，在图中就有一条从，在图中就有一条从 xi 到到 xj 的有向边的有向边. 注意：注意：l 关系矩阵适合表示有穷集关系矩阵适合表示有穷集A上的关系（可推广为从上的关系（可推广为从A到到B的的关系）关系）l 关系图适合表示有穷集关系图适合表示有穷集A上的关系上的关系 12实例实例例例4 A=1,2,3,4, R=, R的关系矩阵的关系矩阵MR和关系图和关系图GR如下：如下： 0010000011000011RM137.3 关系的运算关系的运算关系的基本运算关系的基本运算定义定义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 14关系运算关系运算(逆与合成逆与合成)定义定义7.7 关系的关系的逆运逆运算算 R 1 = | R 定义定义7.8 关系的关系的合成合成运算运算 F G = | t ( F G) 例例6 R = , , , S = , , , , R 1 = , , , R S = , , S R = , , , 15合成的图示法合成的图示法利用图示（不是关系图）方法求合成利用图示（不是关系图）方法求合成 R S =, , S R =, , , 16关系运算关系运算(限制与像限制与像)定义定义7.9 设设R为二元关系为二元关系, A是集合是集合 (1) R在在A上的上的限制限制记作记作 R A, 其中其中 R A = | xRyxA (2) A在在R下的下的像像记作记作RA, 其中其中 RA=ran(R A) 说明：说明：l R在在A上的限制上的限制 R A是是 R 的子关系，即的子关系，即 R A Rl A在在R下的像下的像 RA 是是 ranR 的子集，即的子集，即 RA ranR 17实例实例例例7 设设R=, 则则 R 1 = , R = R 2,3 = , R1 = 2,3 R = R3 = 2 18关系运算的性质关系运算的性质定理定理7.1 设设F是任意的关系是任意的关系, 则则 (1) (F 1) 1=F (2) domF 1= ranF, ranF 1= domF证证 (1) 任取任取, 由逆的定义有由逆的定义有 (F 1) 1 F 1 F.所以有所以有(F 1) 1=F.(2) 任取任取x, xdomF 1 y(F 1) y(F) xranF 所以有所以有 domF 1=ranF. 同理可证同理可证 ranF 1=domF.19定理定理7.2 设设F, G, H是任意的关系是任意的关系, 则则(1) (F G) H = F (G H)(2) (F G) 1 = G 1 F 1关系运算的性质关系运算的性质证证 (1) 任取任取, (F G) H t (F GH) t ( s (FG)H) t s (FGH) s (F t (GH) s (FG H) F (G H) 所以所以 (F G) H = F (G H)20证明证明(2) 任取任取, (F G) 1 F G t (FG) t (G 1F 1) G 1 F 1所以所以 (F G) 1 = G 1 F 1 21关系运算的性质关系运算的性质定理定理7.3 设设R为为A上的关系上的关系, 则则 R IA= IA R=R证证任取任取 R IA t (RIA) t (Rt=yyA) R22关系运算的性质关系运算的性质定理定理7.4 (1) F (G H) = F GF H (2) (GH) F = G FH F (3) F (GH) F GF H (4) (GH) F G FH F只证只证 (3) 任取任取, F (GH) t (FGH) t (FGH) t (FG)(FH) t (FG) t (FH) F GF H F GF H所以有所以有 F (GH)=F GF H23推广推广定理定理7.4 的结论可以推广到有限多个关系的结论可以推广到有限多个关系 R (R1R2Rn) = R R1R R2R Rn (R1R2Rn) R = R1 RR2 RRn R R (R1R2 Rn) R R1R R2 R Rn (R1R2 Rn) R R1 RR2 R Rn R 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)(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 = Rn R注意：注意：l对于对于A上的任何关系上的任何关系 R1 和和 R2 都有都有 R10 = R20 = IA l对于对于A上的任何关系上的任何关系 R 都有都有 R1 = R28例例 8 设设A = a,b,c,d, R = , 求求R的各次幂的各次幂, 分别用矩阵和关系图表示分别用矩阵和关系图表示. 0000100001010010M解解 R 与与 R2的关系矩阵分别是：的关系矩阵分别是： 0000000010100101000010000101001000001000010100102M幂的求法幂的求法29R3和和R4的矩阵是：的矩阵是：因此因此M4=M2, 即即R4=R2. 因此可以得到因此可以得到 R2=R4=R6=， R3=R5=R7=R0的关系矩阵是的关系矩阵是 0000000010100101,000000000101101043MM 10000100001000010M幂的求法幂的求法30关系图关系图R0, R1, R2, R3,的关系图如下图所示的关系图如下图所示. R0R1R2=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 22nR22n32定理定理7.7 设设 R 是是 A上的关系上的关系, m, nN, 则则 (1) Rm Rn = Rm+n(2) (Rm)n = Rmn 幂运算的性质幂运算的性质证证 用归纳法用归纳法(1) 对于任意给定的对于任意给定的mN, 施归纳于施归纳于n.若若n=0, 则有则有 Rm R0 = Rm IA = Rm = Rm+0 假设假设 Rm Rn = Rm+n, 则有则有 Rm Rn+1 = Rm (Rn R) = (Rm Rn) R = Rm+n+1 , 所以对一切所以对一切m,nN 有有 Rm Rn = Rm+n. 33证明证明(2) 对于任意给定的对于任意给定的mN, 施归纳于施归纳于n.若若n=0, 则有则有 (Rm)0 = IA = R0 = Rm0 假设假设 (Rm)n = Rmn, 则有则有 (Rm)n+1 = (Rm)n Rm = (Rmn) Rn = Rmn+m = Rm(n+1)所以对一切所以对一切m,nN 有有 (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 = t s (3) 令令S = R0,R1,Rt 1, 则对于任意的则对于任意的 qN 有有RqS幂运算的性质幂运算的性质证证 (1) Rs+k = Rs Rk = Rt Rk = Rt+k (2) 对对k归纳归纳. 若若k=0, 则有则有Rs+0p+i = Rs+i假设假设 Rs+kp+i = Rs+i, 其中其中p = t s, 则则 Rs+(k+1)p+i = Rs+kp+i+p = Rs+kp+i Rp = Rs+i Rp = Rs+p+i = Rs+t s+i = Rt+i = Rs+i 由归纳法命题得证由归纳法命题得证.35证明证明(3) 任取任取 qN, 若若 q t, 显然有显然有 RqS, 若若q t, 则存在自然数则存在自然数 k 和和 i 使得使得 q = s+kp+i, 其中其中0ip 1.于是于是 Rq = Rs+kp+i = Rs+i 而而 s+i s+p 1 = s+t s 1 = t 1从而从而证明了证明了 RqS.367.4 关系的性质关系的性质定义定义7.11 设设 R 为为A上的关系上的关系, (1) 若若 x(xA R), 则称则称 R 在在 A 上是上是自反自反的的.(2) 若若 x(xA R), 则称则称 R 在在 A 上是上是反自反反自反的的. 实例：实例：自反：全域关系自反：全域关系EA, 恒等关系恒等关系IA, 小于等于关系小于等于关系LA, 整除关系整除关系DA反自反：实数集上的小于关系、幂集上的真包含关系反自反：实数集上的小于关系、幂集上的真包含关系. A=1,2,3, R1, R2, R3是是A上的关系上的关系, 其中其中 R1, R2, R3R2 自反自反 ，R3 反自反，反自反，R1既不是自反的也不是反自反的既不是自反的也不是反自反的.37对称性与反对称性对称性与反对称性定义定义7.12 设设 R 为为 A上的关系上的关系, (1) 若若 x y( x,yARR), 则称则称 R 为为 A上上对对称称的关系的关系.(2) 若若 x y( x,yARRx=y), 则称则称 R 为为A上的上的反对称反对称关系关系.实例：对称关系：实例：对称关系：A上的全域关系上的全域关系EA, 恒等关系恒等关系IA和空关系和空关系反对称关系：恒等关系反对称关系：恒等关系IA和空关系也是和空关系也是A上的反对称关系上的反对称关系. 设设A1,2,3, R1, R2, R3和和R4都是都是A上的关系上的关系, 其中其中 R1,，R2, R3,，R4, R1：对称和反对称；：对称和反对称； R2：只有对称；：只有对称；R3：只有反对称；：只有反对称； R4：不对称、不反对称：不对称、不反对称38传递性传递性定义定义7.13 设设R为为A上的关系上的关系, 若若 x y z(x,y,zARRR),则称则称 R 是是A上的上的传递传递关系关系.实例：实例： A上的全域关系上的全域关系 EA,恒等关系恒等关系 IA和空关系和空关系 ，小于等小于等于和小于关系，整除关系，包含与真包含关系于和小于关系，整除关系，包含与真包含关系设设 A1,2,3, R1, R2, R3是是A上的关系上的关系, 其中其中 R1, R2, R3R1和和R3是是A上的传递关系上的传递关系, R2不是不是A上的传递关系上的传递关系. 39关系性质成立的充要条件关系性质成立的充要条件定理定理7.9 设设R为为A上的关系上的关系, 则则(1) R 在在A上自反当且仅当上自反当且仅当 IA R(2) R 在在A上反自反当且仅当上反自反当且仅当 RIA = (3) R 在在A上对称当且仅当上对称当且仅当 R=R 1(4) R 在在A上反对称当且仅当上反对称当且仅当 RR 1 IA(5) R 在在A上传递当且仅当上传递当且仅当 R R R 40证明证明证明证明 只证只证(1)、(3)、(4)、(5)(1) 必要性必要性任取任取, 由于由于R 在在A上自反必有上自反必有 IA x,yAx=y R从而证明了从而证明了IA R充分性充分性.任取任取x, 有有 xA IA R因此因此 R 在在A上是自反的上是自反的. 41证明证明(3) 必要性必要性. 任取任取, R R R 1所以所以 R = R 1充分性充分性.任取任取, 由由R = R 1得得R R 1 R所以所以R在在A上是对称的上是对称的42证明证明(4) 必要性必要性. 任取任取, 有有 RR 1 RR 1 RR x=y x,y A IA这就证明了这就证明了RR 1 IA充分性充分性. 任取任取, RR RR 1 RR 1 IA x=y从而证明了从而证明了R在在A上是反对称的上是反对称的.43证明证明(5) 必要性必要性. 任取任取有有 R R t (RR) R所以所以 R R R充分性充分性. 任取任取,R, 则则 RR R R R 所以所以 R 在在 A上是传递的上是传递的44自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性集合集合IA RRIA=R=R 1RR 1 IAR R R关系关系矩阵矩阵主对角主对角线元素线元素全是全是1主对角线主对角线元素全是元素全是0矩阵是矩阵是对称矩阵对称矩阵若若rij1, 且且ij, 则则rji0M2中中1位置位置, M中相应位中相应位置都是置都是1关系关系图图每个顶每个顶点都有点都有环环每个顶点每个顶点都没有环都没有环两点之间两点之间有边有边, 是是一对方向一对方向相反的边相反的边两点之间有两点之间有边边,是一条有是一条有向边向边点点xi到到xj有有边边, xj 到到xk有边有边, 则则xi到到xk也有边也有边 关系性质的三种等价条件关系性质的三种等价条件45关系性质的判别关系性质的判别例例9 判断下列各图的性质判断下列各图的性质 (a) (b) (c) 解：解：(a) 对称对称(b) 反自反、反对称、传递反自反、反对称、传递(c) 自反、反对称自反、反对称46自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性R1 1 R1R2 R1R2 R1 R2 R1 R2 关系的性质和运算之间的联系关系的性质和运算之间的联系477.5 关系的闭包关系的闭包 主要内容主要内容l 闭包定义闭包定义l 闭包的构造方法闭包的构造方法 集合表示集合表示 矩阵表示矩阵表示 图表示图表示l 闭包的性质闭包的性质 48闭包定义闭包定义定义定义7.14 设设R是非空集合是非空集合A上的关系上的关系, R的的自反自反(对称对称或或传递传递)闭闭包包是是A上的关系上的关系R , 使得使得R 满足以下条件：满足以下条件：(1) R 是自反的是自反的(对称的或传递的对称的或传递的) (2) R R (3) 对对A上任何包含上任何包含R的自反的自反(对称或传递对称或传递)关系关系R 有有RR R的自反闭包记作的自反闭包记作r(R), 对称闭包记作对称闭包记作s(R), 传递闭包记作传递闭包记作t(R). 定理定理7.10 设设R为为A上的关系上的关系, 则有则有(1) r(R)=RR0(2) s(R)=RR 1(3) t(R)=RR2R3说明：对有穷集说明：对有穷集A(|A|=n)上的关系上的关系, (3)中的并最多不超过中的并最多不超过Rn49证明证明证证 只证只证(1)和和(3). (1) 由由IA=R0 RR0 知知 RR0是自反的是自反的, 且满足且满足R RR0设设R 是是A上包含上包含R的自反关系的自反关系, 则有则有R R 和和IA R . 从而有从而有RR0 R . RR0满足闭包定义满足闭包定义, 所以所以r(R)=RR0.(1) 先证先证 RR2 t(R)成立成立. 用归纳法证明对任意正整数用归纳法证明对任意正整数n 有有Rn t(R). n=1时有时有R1=R t(R). 假设假设Rn t(R)成立成立, 那么对任意的那么对任意的 Rn+1=Rn R t ( RnR) t (t(R)t(R) t(R) 这就证明了这就证明了Rn+1 t(R). 由归纳法命题得证由归纳法命题得证. 50证明证明再证再证 t(R) RR2成立成立, 为此只须证明为此只须证明RR2传递传递. 任取任取, 则则 RR2RR2 t (Rt) s(Rs) t s (Rt Rs ) t s (Rt+s ) RR2从而证明了从而证明了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 到到 xi 的反向边的反向边, 得到得到Gs(3) 考察考察G 的每个顶点的每个顶点 xi, 找找 xi 可达的所有顶点可达的所有顶点 xj (允许允许i=j )， 如果没有从如果没有从 xi 到到 xj 的边的边, 就加上这条边就加上这条边, 得到图得到图Gt52实例实例例例9 设设A=a,b,c,d, R=, R和和r(R), s(R), t(R)的关系图如下图所示的关系图如下图所示. Rr(R)s(R)t(R)求传递闭包的算法求传递闭包的算法算法算法 Warshall输人：输人：M（R的关系矩阵）的关系矩阵）输出：输出：MT（t(R)的关系矩阵）的关系矩阵）1MTM2for k1 to n do3 for i1 to n do 4 for j1 to n do5 MTi,jMTi,j+MTi,k MTk,j 53实例实例54 1111111111111111,11111000111111110111100001110111,0010100001110010,001010000101001043210MMMMM设设A=a,b,c,d, R=, 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上的关系上的关系, 且且 R1 R2, 则则(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是传递的是传递的, 则则 r(R) 是传递的是传递的. 说明：如果需要进行多个闭包运算，比如求说明：如果需要进行多个闭包运算，比如求R的自反、对的自反、对称、传递的闭包称、传递的闭包 tsr(R)，运算顺序如下：，运算顺序如下： tsr(R) = rts(R) = trs(R)闭包的性质闭包的性质证明证明 略略577.6 等价关系与划分等价关系与划分 主要内容主要内容l 等价关系的定义与实例等价关系的定义与实例l 等价类及其性质等价类及其性质l 商集与集合的划分商集与集合的划分l 等价关系与划分的一一对应等价关系与划分的一一对应 587.6 等价关系与划分等价关系与划分定义定义7.15 设设R为非空集合上的关系为非空集合上的关系. 如果如果R是自反的、对称的和是自反的、对称的和传递的传递的, 则称则称R为为A上的上的等价关系等价关系. 设设 R 是一个等价关系是一个等价关系, 若若R, 称称 x等价于等价于y, 记做记做xy. 实例实例 设设 A=1,2,8, 如下定义如下定义A上的关系上的关系R： R=| x,yAx y(mod 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, , 8上模上模3等价关系的等价类：等价关系的等价类： 1 = 4 = 7 = 1, 4, 7 2 = 5 = 8 = 2, 5, 8 3 = 6 = 3, 6x61等价类的性质等价类的性质定理定理7.14 设设R是非空集合是非空集合A上的等价关系上的等价关系, 则则(1) x A, x是是A的非空子集的非空子集(2) x,y A, 如果如果 xRy, 则则 x = y(3) x,y A, 如果如果 x y, 则则 x与与y不交不交(4) x | x A=A证证 (1) 由定义由定义, x A有有x A. 又又x x, 即即x非空非空. (2) 任取任取 z, 则有则有 zx R R R R R R从而证明了从而证明了zy. 综上所述必有综上所述必有 x y. 同理可证同理可证 y x. 这就得到了这就得到了x = y.62证明证明(3) 假设假设 xy, 则存在则存在 z xy, 从而有从而有z xz y, 即即 R R成立成立. 根据根据R的对称性和传递性必有的对称性和传递性必有 R, 与与 x y矛盾矛盾(4) 先证先证x | x A A. 任取任取y, y x | x A x(x Ay x) y xx A y A 从而有从而有x | xA A 再证再证A x | xA. 任取任取y, y A y yy A yx | x A 从而有从而有x | xA A成立成立.综上所述得综上所述得x | x A = 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,8, 3,6A关于恒等关系和全域关系的商集为：关于恒等关系和全域关系的商集为： A/IA = 1, 2, , 8， A/EA = 1,2,8定义定义7.18 设设A为非空集合为非空集合, 若若A的子集族的子集族( P(A)满足满足:(1) (2) x y(x,y xyxy=)(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的划分的划分, 其他都不是其他都不是A的划分的划分. 65例例11 给出给出 A1,2,3上所有的等价关系上所有的等价关系实例实例1 123 31 1 123 351 123 321 123 341 123 331对应对应 EA, 5 对应对应 IA, 2, 3 和和 4分别对应分别对应 R2, R3和和 R4. R2=,IA R3=,IA R4=,IA解解 先做出先做出A的划分的划分, 从左到右分别记作从左到右分别记作 1, 2, 3, 4, 5.667.7 偏序关系偏序关系 主要内容主要内容l 偏序关系偏序关系 偏序关系的定义偏序关系的定义 偏序关系的实例偏序关系的实例l 偏序集与哈斯图偏序集与哈斯图l 偏序集中的特殊元素及其性质偏序集中的特殊元素及其性质 极大元、极小元、最大元、最小元极大元、极小元、最大元、最小元 上界、下界、最小上界、最大下界上界、下界、最小上界、最大下界67定义与实例定义与实例定义定义7.19 偏序关系偏序关系：非空集合：非空集合A上的自反、反对称和传递的关系，上的自反、反对称和传递的关系，记作记作 . 设设 为偏序关系为偏序关系, 如果如果 , 则记作则记作 x y, 读读作作x“小于或等于小于或等于”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, 如果如果 x y 且不存在且不存在 zA 使得使得 x z y, 则称则称 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, g, h R=,IA实例实例72偏序集中的特殊元素偏序集中的特殊元素 定义定义7.24 设设为偏序集为偏序集, B A, yB(1) 若若 x(xBy x)成立成立, 则称则称 y 为为B的的最小元最小元(2) 若若 x(xBx y)成立成立, 则称则称 y 为为B的的最大元最大元(3) 若若 x(xBx yx=y)成立成立, 则称则称 y 为为B的的极小元极小元(4) 若若 x(xBy xx=y)成立成立, 则称则称 y 为为B的的极大元极大元性质：性质：(1) 对于有穷集，极小元和极大元一定存在，可能存在多个对于有穷集，极小元和极大元一定存在，可能存在多个. (2) 最小元和最大元不一定存在，如果存在一定惟一最小元和最大元不一定存在，如果存在一定惟一.(3) 最小元一定是极小元；最大元一定是极大元最小元一定是极小元；最大元一定是极大元. (4) 孤立结点既是极小元，也是极大元孤立结点既是极小元，也是极大元.73定义定义7.25 设设为偏序集为偏序集, B A, yA(1) 若若 x(xBx y)成立成立, 则称则称y为为B的的上界上界 (2) 若若 x(xBy x)成立成立, 则称则称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, g； 极大元：极大元：a, f, h；没有最小元与最大元没有最小元与最大元.B的下界和最大下界都不存在；的下界和最大下界都不存在；上界有上界有 d 和和 f, 最小上界为最小