第七章 二元关系 主要内容 有序对与笛卡儿积 二元关系的定义与表示法 关系的运算 关系的性质 关系的闭包 等价关系与划分 偏序关系.

Presentation on theme: "第七章 二元关系 主要内容 有序对与笛卡儿积 二元关系的定义与表示法 关系的运算 关系的性质 关系的闭包 等价关系与划分 偏序关系."— Presentation transcript:

1 第七章 二元关系 主要内容 有序对与笛卡儿积 二元关系的定义与表示法 关系的运算 关系的性质 关系的闭包 等价关系与划分 偏序关系

2 7.1 有序对与笛卡儿积 定义7.1 由两个元素 x 和 y，按照一定的顺序组成的二元组 称为有序对，记作<x,y>.
有序对性质: (1) 有序性 <x,y><y,x> （当xy时） (2) <x,y>与<u,v>相等的充分必要条件是 <x,y>=<u,v>  x=uy=v.

3 笛卡儿积 定义7.2 设A,B为集合，A与B的笛卡儿积记作AB，且 AB = {<x,y>| xAyB}.
例1 A={1,2,3}, B={a,b,c} AB ={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>} BA ={<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>,<a,3>,<b,3>,<c,3>} 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| = m, |B| = n, 则 |AB| = mn

5 性质证明 证明 A(BC) = (AB)(AC) 证 任取<x,y> <x,y>∈A×(B∪C)
 x∈A∧y∈B∪C  x∈A∧(y∈B∨y∈C)   (x∈A∧y∈B)∨(x∈A∧y∈C)   <x,y>∈A×B∨<x,y>∈A×C   <x,y>∈(A×B)∪(A×C) 所以有A×(B∪C) = (A×B)∪(A×C).

6 实例 例2 (1) 证明A=B,C=D  AC=BD (2) AC = BD是否推出 A=B,C=D? 为什么？
解 (1) 任取<x,y> <x,y>AC  xAyC  xByD  <x,y>BD (2) 不一定.反例如下： A={1}，B={2}, C = D = , 则AC = BD但是A  B.

7 7.2 二元关系 定义7.3 如果一个集合满足以下条件之一： (1) 集合非空, 且它的元素都是有序对 (2) 集合是空集
定义7.3 如果一个集合满足以下条件之一： (1) 集合非空, 且它的元素都是有序对 (2) 集合是空集 则称该集合为一个二元关系, 简称为关系，记作R. 如果<x,y>∈R, 可记作xRy；如果<x,y>R, 则记作x y 实例：R={<1,2>,<a,b>}, S={<1,2>,a,b}. R是二元关系, 当a, b不是有序对时，S不是二元关系 根据上面的记法，可以写1R2, aRb, a c等.

8 A到B的关系与A上的关系 定义7.4 设A,B为集合, A×B的任何子集所定义的二元关系叫做从A
 R1={<0,2>}, R2=A×B, R3=, R4={<0,1>} R1, R2, R3, R4是从 A 到 B 的二元关系, R3 和 R4 也是A上的二元关系. 计数: |A|=n, |A×A|=n2, A×A的子集有个. 所以 A上有 个不同的二元关系. 例如 |A| = 3, 则 A上有=512个不同的二元关系.

9 A上重要关系的实例 定义7.5 设 A 为集合, (1) 是A上的关系，称为空关系
(2) 全域关系 EA = {<x,y>| x∈A∧y∈A} = A×A 恒等关系 IA = {<x,x>| x∈A} 小于等于关系 LA = {<x,y>| x,y∈A∧x≤y}, A为实数子集 整除关系 DB = {<x,y>| x,y∈B∧x整除y}, B为非0整数子集 包含关系 R = {<x,y>| x,y∈A∧xy}, A是集合族.

10 实例 例如, A={1, 2}, 则  EA = {<1,1>,<1,2>,<2,1>,<2,2>}  IA = {<1,1>,<2,2>} 例如 A = {1, 2, 3}, B={a, b}, 则 LA = {<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>} DA = {<1,1>,<1,2>,<1,3>,<2,2>,<3,3>} 例如 A = P(B) = {,{a},{b},{a,b}}, 则 A上的包含关系是 R = {<,>,<,{a}>,<,{b}>,<,{a,b}>,<{a},{a}>, <{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>} 类似的还可以定义： 大于等于关系, 小于关系, 大于关系, 真包含关系等.

11 关系的表示 1. 关系矩阵 若A={x1, x2, …, xm}，B={y1, y2, …, yn}，R是从A到B的
1. 关系矩阵 若A={x1, x2, …, xm}，B={y1, y2, …, yn}，R是从A到B的 关系，R的关系矩阵是布尔矩阵MR = [ rij ] mn, 其中 rij = 1 < xi, yj> R. 反之rij = 0 2. 关系图 若A= {x1, x2, …, xm}，R是A上的关系，R的关系图是GR=<A, R>, 其中A为结点集，R为边集. 如果<xi,xj>属于 关系R，在图中就有一条从 xi 到 xj 的有向边. 注意： 关系矩阵适合表示从A到B的关系或A上的关系（A,B为有穷集） 关系图适合表示有穷集A上的关系

12 实例 例4 A={1,2,3,4}, R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}, R的关系矩阵MR和关系图GR如下：

13 7.3 关系的运算 关系的基本运算 定义7.6 关系的定义域、值域与域分别定义为
定义7.6 关系的定义域、值域与域分别定义为 domR = { x | y (<x,y>R) } ranR = { y | x (<x,y>R) } fldR = domR  ranR 例5 R={<1,2>,<1,3>,<2,4>,<4,3>}, 则 domR={1, 2, 4} ranR={2, 3, 4} fldR={1, 2, 3, 4}

14 关系运算(逆与合成) 定义7.7 关系的逆运算 R1 = { <y, x> | <x, y>R }
定义7.7 关系的逆运算 R1 = { <y, x> | <x, y>R } 定义7.8 关系的合成运算 RS = { <x, z> |  y (<x, y>R  <y, z>S) } 例6 R = {<1,2>, <2,3>, <1,4>, <2,2>} S = {<1,1>, <1,3>, <2,3>, <3,2>, <3,3>} R1 = {<2,1>, <3,2>, <4,1>, <2,2>} RS = {<1,3>, <2,2>, <2,3>} SR = {<1,2>, <1,4>, <3,2>, <3,3>}

15 合成的图示法 利用图示（不是关系图）方法求合成 RS ={<1,3>, <2,2>, <2,3>}
SR ={<1,2>, <1,4>, <3,2>, <3,3>}

16 关系运算(限制与像) R在A上的限制 R↾A是 R 的子关系，即 R↾A  R
(1) R在A上的限制记作 R↾A, 其中  R↾A = { <x,y> | xRy∧x∈A } (2) A在R下的像记作R[A], 其中  R[A]=ran(R↾A) 说明： R在A上的限制 R↾A是 R 的子关系，即 R↾A  R A在R下的像 R[A] 是 ranR 的子集，即 R[A] ranR

17 实例 例7 设R={<1,2>,<1,3>,<2,2>,<2,4>,<3,2>}, 则R↾{1} ， R↾， R↾{2,3} R[{1}]，  R[] ， R[{3}]  R↾{1} = {<1,2>,<1,3>}  R↾ =   R↾{2,3} = {<2,2>,<2,4>,<3,2>}  R[{1}] = {2,3}  R[] =   R[{3}] = {2}

18 关系运算的性质 定理7.1 设F是任意的关系, 则 (1) (F1)1=F (2) domF1= ranF, ranF1= domF
证 (1) 任取<x,y>, 由逆的定义有 <x,y>∈(F1)1  <y,x>∈F1  <x,y>∈F. 所以有(F1)1=F. (2) 任取x, x∈domF1  y(<x,y>∈F1)  y(<y,x>∈F) x∈ranF 所以有 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) 任取<x,y>, <x,y>(FG)H  t (<x,t>∈FG∧<t,y>∈H)  t ( s (<x,s>∈F∧<s,t>∈G)∧<t,y>∈H)  t s (<x,s>∈F∧<s,t>∈G∧<t,y>∈H)  s (<x,s>∈F∧t (<s,t>∈G∧<t,y>∈H))  s (<x,s>∈F∧<s,y>∈GH)  <x,y>∈F(GH) 所以 (FG)H = F(GH)

20 证明 (2) 任取<x,y>,  <x,y>∈(FG)1   <y,x>∈FG   t (<y,t>∈F∧<t,x>∈G)  t (<x,t>∈G1∧<t,y>∈F1)  <x,y>∈G1 F1 所以 (F  G)1 = G1 F1

21 关系运算的性质 定理7.3 设R为A上的关系, 则   RIA= IAR=R
证任取<x,y> <x,y>∈RIA   t (<x,t>∈R∧<t,y>∈IA)  t (<x,t>∈R∧t=y∧y∈A)  <x,y>∈R

22 关系运算的性质 定理7.4 (1) F(GH) = FG∪FH (2) (G∪H)F = GF∪HF
只证 (3) 任取<x,y>,  <x,y>∈F(G∩H)  t (<x,t>∈F∧<t,y>∈G∩H)   t (<x,t>∈F∧<t,y>∈G∧<t,y>∈H)   t ((<x,t>∈F∧<t,y>∈G)∧(<x,t>∈F∧<t,y>∈H))   t (<x,t>∈F∧<t,y>∈G)∧t (<x,t>∈F∧<t,y>∈H)   <x,y>∈FG∧<x,y>∈FH   <x,y>∈FG∩FH 所以有 F(G∩H)=FG∩FH

23 推广 定理7.4 的结论可以推广到有限多个关系  R(R1∪R2∪…∪Rn) = RR1∪RR2∪…∪RRn (R1∪R2∪…∪Rn)R = R1R∪R2R∪…∪RnR R(R1∩R2∩ … ∩Rn)  RR1∩RR2∩ … ∩RRn (R1∩R2∩ … ∩Rn)R  R1R∩R2R∩ … ∩RnR

24 关系运算的性质 定理7.5 设F 为关系, A, B为集合, 则 (1) F ↾(A∪B) = F ↾A∪F ↾B

25 证明 证 只证 (1) 和 (4). (1) 任取<x,y>  <x,y>∈F ↾(A∪B)
 <x,y>∈F∧x∈A∪B  <x,y>∈F∧(x∈A∨x∈B)  (<x,y>∈F∧x∈A)∨(<x,y>∈F∧x∈B)  <x,y>∈F ↾A∨<x,y>∈F ↾B  <x,y>∈F ↾A∪F ↾B 所以有F ↾(A∪B) = F ↾A∪F ↾B.

26 证明 (4) 任取y,   y∈F [A∩B]  x (<x,y>∈F∧x∈A∩B)  x (<x,y>∈F∧x∈A∧x∈B)  x ((<x,y>∈F∧x∈A)∧(<x,y>∈F∧x∈B))  x (<x,y>∈F∧x∈A)∧x (<x,y>∈F∧x∈B)  y∈F [A]∧y∈F [B]  y∈F [A]∩F [B] 所以有F [A∩B]=F [A]∩F [B].

27 关系的幂运算 对于A上的任何关系 R1 和 R2 都有 R10 = R20 = IA 对于A上的任何关系 R 都有 R1 = R
定义7.10 设 R 为 A 上的关系, n为自然数, 则 R 的 n 次幂定义为： (1) R0 = { <x,x> | x∈A } = IA (2) Rn+1 = RnR 注意： 对于A上的任何关系 R1 和 R2 都有 R10 = R20 = IA 对于A上的任何关系 R 都有 R1 = R

28 幂的求法 例 8 设A = {a,b,c,d}, R = {<a,b>,<b,a>,<b,c>,<c,d>}, 求R的各次幂, 分别用矩阵和关系图表示. 解 R 与 R2的关系矩阵分别是：

29 幂的求法 R3和R4的矩阵是： 因此M4=M2, 即R4=R2. 因此可以得到  R2=R4=R6=…， R3=R5=R7=…
 

30 关系图 R0, R1, R2, R3,…的关系图如下图所示. R0 R1 R2=R4=… R3=R5=…

31 幂运算的性质 定理7.6 设 A 为 n 元集, R 是A上的关系, 则存在自然数 s 和 t, 使得 Rs = Rt.
由于|A|=n, A上的不同关系只有 个. 列出 R 的各次幂 R0, R1, R2, … , , …, 必存在自然数 s 和 t 使得 Rs = Rt

32 幂运算的性质 定理7.7 设 R 是 A上的关系, m, n∈N, 则 (1) RmRn = Rm+n (2) (Rm)n = Rmn
证 用归纳法 (1) 对于任意给定的m∈N, 施归纳于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,n∈N 有 RmRn = Rm+n.

33 证明 (2) 对于任意给定的m∈N, 施归纳于n. 若n=0, 则有 (Rm)0 = IA = R0 = Rm×0
假设 (Rm)n = Rmn, 则有 (Rm)n+1 = (Rm)nRm = (Rmn)Rn = Rmn+m = Rm(n+1) 所以对一切m,n∈N 有 (Rm)n = Rmn.

34 幂运算的性质 定理7.8 设R 是A上的关系, 若存在自然数 s, t (s<t) 使得 Rs=Rt, 则
(1) 对任何 k∈N有 Rs+k = Rt+k (2) 对任何 k, i∈N有 Rs+kp+i = Rs+i, 其中 p = ts (3) 令S = {R0,R1,…,Rt1}, 则对于任意的 q∈N 有Rq∈S 证 (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) 任取 q∈N, 若 q < t, 显然有 Rq∈S, 若q ≥ t, 则存在自然数 k 和 i 使得
q = s+kp+i, 其中0≤i≤p1. 于是  Rq = Rs+kp+i = Rs+i 而 s+i ≤ s+p1 = s+ts1 = t1 从而证明了 Rq∈S.

36 7.4 关系的性质 定义7.11 设 R 为A上的关系, (1) 若 x(x∈A→<x,x>R), 则称 R 在 A 上是自反的. (2) 若 x(x∈A→<x,x>R), 则称 R 在 A 上是反自反的. 实例： 自反：全域关系EA, 恒等关系IA, 小于等于关系LA, 整除关系DA 反自反：实数集上的小于关系、幂集上的真包含关系. A={1,2,3}, R1, R2, R3是A上的关系, 其中 R1＝{<1,1>,<2,2>} R2＝{<1,1>,<2,2>,<3,3>,<1,2>} R3＝{<1,3>} R2 自反 ，R3 反自反，R1既不是自反的也不是反自反的.

37 对称性与反对称性 定义7.12 设 R 为 A上的关系,  (1) 若xy( x,y∈A∧<x,y>∈R→<y,x>∈R), 则称 R 为 A上对 称的关系. (2) 若xy( x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y), 则称 R 为 A上的反对称关系. 实例：对称关系：A上的全域关系EA, 恒等关系IA和空关系 反对称关系：恒等关系IA和空关系也是A上的反对称关系. 设A＝{1,2,3}, R1, R2, R3和R4都是A上的关系, 其中 R1＝{<1,1>,<2,2>}，R2＝{<1,1>,<1,2>,<2,1>} R3＝{<1,2>,<1,3>}，R4＝{<1,2>,<2,1>,<1,3>} R1：对称和反对称； R2：只有对称；R3：只有反对称； R4：不对称、不反对称

38 传递性 定义7.13 设R为A上的关系, 若 xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R), 则称 R 是A上的传递关系. 实例： A上的全域关系 EA,恒等关系 IA和空关系 ，小于等 于和小于关系，整除关系，包含与真包含关系 设 A＝{1,2,3}, R1, R2, R3是A上的关系, 其中 R1＝{<1,1>,<2,2>} R2＝{<1,2>,<2,3>} R3＝{<1,3>} R1和R3是A上的传递关系, R2不是A上的传递关系.

39 关系性质成立的充要条件 定理7.9 设R为A上的关系, 则 (1) R 在A上自反当且仅当 IA  R
(2) R 在A上反自反当且仅当 R∩IA =  (3) R 在A上对称当且仅当 R=R1 (4) R 在A上反对称当且仅当 R∩R1  IA (5) R 在A上传递当且仅当 RR  R

40 证明 证明 只证(1)、(3)、(4)、(5) (1) 必要性
证明 只证(1)、(3)、(4)、(5) (1) 必要性 任取<x,y>, 由于R 在A上自反必有  <x,y>∈IA  x,y∈A∧x=y  <x,y>∈R 从而证明了IAR 充分性. 任取x, 有   x∈A  <x,x>∈IA  <x,x>∈R 因此 R 在A上是自反的.

41 证明 (3) 必要性. 任取<x,y>, <x,y>∈R  <y,x>∈R  <x,y>∈R1 所以 R = R1 充分性. 任取<x,y>, 由R = R1得 <x,y>∈R  <y,x>∈R1  <y,x>∈R 所以R在A上是对称的

42 证明 (4) 必要性. 任取<x,y>, 有  <x,y>∈R∩R1  <x,y>∈R∧<x,y>∈R  <x,y>∈R∧<y,x>∈R  x=y  x,yA   <x,y>∈IA 这就证明了R∩R1IA 充分性. 任取<x,y>,   <x,y>∈R∧<y,x>∈R  <x,y>∈R∧<x,y>∈R1  <x,y>∈R∩R1  <x,y>∈IA   x=y 从而证明了R在A上是反对称的.

43 证明 (5) 必要性. 任取<x,y>有  <x,y>∈RR
  t (<x,t>∈R∧<t,y>∈R)    <x,y>∈R 所以 RR  R 充分性. 任取<x,y>,<y,z>∈R, 则  <x,y>∈R∧<y,z>∈R  <x,z>∈RR  <x,z>∈R 所以 R 在 A上是传递的

44 关系性质的三种等价条件  自反性 反自反性 对称性 反对称性 传递性 集合 IAR R∩IA= R=R1 R∩R1IA
关系矩阵 主对角线元素全是1 主对角线元素全是0 矩阵是 对称矩阵 若rij＝1, 且i≠j, 则rji＝0 M2中1位置, M中相应位置都是1 关系图 每个顶点都有环 每个顶点都没有环 两点之间有边, 是一对方向相反的边 两点之间有边,是一条有向边 点xi到xj有边, xj 到xk有边, 则xi到xk也有边

45 关系的性质和运算之间的联系 自反性 反自反性 对称性 反对称性 传递性 R11 √ R1∩R2 R1∪R2 × R1R2 R1  R2

46 7.5 关系的闭包 主要内容 闭包定义 闭包的构造方法 集合表示 矩阵表示 图表示 闭包的性质

47 闭包定义 定义7.14 设R是非空集合A上的关系, R的自反(对称或传递)闭 包是A上的关系R, 使得R满足以下条件：
(3) 对A上任何包含R的自反(对称或传递)关系R 有RR R的自反闭包记作r(R), 对称闭包记作s(R), 传递闭包记作t(R). 定理 设R为A上的关系, 则有 (1) r(R)=R∪R0 (2) s(R)=R∪R1 (3) t(R)=R∪R2∪R3∪… 说明：对有穷集A(|A|=n)上的关系, (3)中的并最多不超过Rn

48 证明 证 只证(1)和(3). (1) 由IA=R0R∪R0 知 R∪R0是自反的, 且满足RR∪R0
证 只证(1)和(3). (1) 由IA=R0R∪R0 知 R∪R0是自反的, 且满足RR∪R0 设R 是A上包含R的自反关系, 则有RR 和IA R . 从而有 R∪R0R. R∪R0满足闭包定义, 所以r(R)=R∪R0. (1) 先证 R∪R2∪… t(R)成立. 用归纳法证明对任意正整数n 有Rn  t(R). n=1时有R1=R  t(R). 假设Rnt(R)成立, 那么对任意的<x,y> <x,y>∈Rn+1=RnR  t ( <x,t>∈Rn∧<t,y>∈R)  t (<x,t>∈t(R)∧<t,y>∈t(R))  <x,y>∈t(R) 这就证明了Rn+1t(R). 由归纳法命题得证. 

49 证明 再证 t(R)  R∪R2∪…成立, 为此只须证明R∪R2∪…传递.
任取<x,y>,<y,z>, 则  <x,y>∈R∪R2∪…∧<y,z>∈R∪R2∪…  t (<x,y>∈Rt)∧s(<y,z>∈Rs)  t s (<x,z>∈RtRs )  t s (<x,z>∈Rt+s )  <x,z>∈R∪R2∪… 从而证明了R∪R2∪…是传递的.

50 闭包的矩阵表示和图表示 设关系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 的单向边, i≠j, 则在G 中加一条 xj 到 xi 的反向边, 得到Gs (3) 考察G 的每个顶点 xi, 找 xi 可达的所有顶点 xj (允许i=j )， 如果没有从 xi 到 xj 的边, 就加上这条边, 得到图Gt

51 实例 例9 设A={a,b,c,d}, R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}, R和r(R), s(R), t(R)的关系图如下图所示. R r(R) s(R) t(R)

52 闭包的性质 定理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) 证明 略

53 闭包的性质 定理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) 传递放在对称之后运算 证明 略

54 7.6 等价关系与划分 主要内容 等价关系的定义与实例 等价类及其性质 商集与集合的划分 等价关系与划分的一一对应

55 等价关系的定义与实例 定义7.15 设R为非空集合上的关系. 如果R是自反的、对称的和
传递的, 则称R为A上的等价关系. 设 R 是一个等价关系, 若 <x,y>∈R, 称 x等价于y, 记做x～y. 实例 设 A={1,2,…,8}, 如下定义A上的关系R： R={<x,y>| x,y∈A∧x ≡ y(mod 3)} 其中x ≡ y(mod 3)叫做 x与 y 模3相等, 即x除以3的余数与y除以 3的余数相等. 不难验证 R 为A上的等价关系, 因为 (1) x∈A, 有 x ≡ x (mod 3) (2) x,y∈A, 若x ≡ y(mod 3), 则有y ≡ x(mod 3) (3) x,y,z∈A, 若x ≡ y(mod 3), y ≡ z(mod 3), 则有x ≡ z(mod 3)

56 等价关系的实例 模 3 等价关系的关系图

57 等价类定义 定义7.16 设R为非空集合A上的等价关系, x∈A，令  [x]R = {y | y∈A∧xRy}
称[x]R 为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}

58 等价类的性质 定理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, 则有  z∈[x]  <x,z>∈R  <z,x>∈R <z,x>R∧<x,y>R  <z,y>R  <y,z>R 从而证明了z∈[y]. 综上所述必有 [x][y]. 同理可证 [y][x]. 这就得到了[x] = [y].

59 证明 (3) 假设 [x]∩[y]≠, 则存在 z[x]∩[y], 从而有z[x]∧z[y],
即<x,z>R∧<y,z>R成立. 根据R的对称性和传递性必有 <x,y>R, 与 x y矛盾 (4) 先证∪{[x] | xA}  A. 任取y, y∪{[x] | xA}  x(xA∧y[x])  y[x]∧[x]  A  yA 从而有∪{[x] | x∈A}  A 再证A  ∪{[x] | x∈A}. 任取y, yA  y[y]∧yA  y∈∪{[x] | xA} 从而有∪{[x] | x∈A}  A成立. 综上所述得∪{[x] | xA} = A.

60 商集与划分 定义7.17 设 R 为非空集合A上的等价关系, 以 R 的所有等价
类作为元素的集合称为A关于R的商集, 记做A/R, A/R = {[x]R | x∈A} 实例 设 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}} 定义7.18 设A为非空集合, 若A的子集族π(π  P(A))满足: (1)  π (2) xy(x,yπ∧x≠y→x∩y=) (3) ∪π = A 则称π是A的一个划分, 称π中的元素为A的划分块.

61 划分实例 例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的划分.

62 实例 1 5 2 4 3 1对应 EA, 5 对应 IA, 2, 3 和 4分别对应 R2, R3和 R4.
R2={<2,3>,<3,2>}∪IA R3={<1,3>,<3,1>}∪IA R4={<1,2>,<2,1>}∪IA

63 7.7 偏序关系 主要内容 偏序关系 偏序关系的定义 偏序关系的实例 偏序集与哈斯图 偏序集中的特殊元素及其性质
极大元、极小元、最大元、最小元 上界、下界、最小上界、最大下界

64 定义与实例 定义7.19 偏序关系：非空集合A上的自反、反对称和传递的关系，
记作≼. 设≼为偏序关系, 如果 <x, y> ∈≼, 则记作 x ≼ y, 读作 x“小于或等于”y. 实例 集合A上的恒等关系 IA是 A上的偏序关系. 小于或等于关系, 整除关系和包含关系也是相应集合上的偏 序关系.

65 相关概念 定义7.20 设 R 为非空集合A上的偏序关系, (1) x, y∈A, x与y可比  x ≼ y∨y ≼ x
(2) 任取元素 x 和 y, 可能有下述几种情况发生： x ≺ y (或 y ≺ x), x＝y, x与y不是可比的 定义7.21 R 为非空集合A上的偏序关系, (1) x,y∈A, x与y都是可比的，则称R为全序（或线序） 实例：数集上的小于或等于关系是全序关系,整除关系不是正 整数集合上的全序关系 定义7.22 x,y∈A, 如果 x≺y 且不存在 z∈A 使得 x≺z≺y, 则称 y 覆盖x. 例如{1,2,4,6}集合上整除关系, 2覆盖1, 4和6覆盖2, 4不覆盖1.

66 偏序集与哈斯图 定义7.23 集合A和A上的偏序关系≼一起叫做偏序集, 记作 <A,≼>.
实例: <Z,≤>, <P(A),R> 哈斯图: 利用偏序关系的自反、反对称、传递性进行简化的 关系图 特点： (1) 每个结点没有环 (2) 两个连通的结点之间的序关系通过结点位置的高低表 示，位置低的元素的顺序在前 (3) 具有覆盖关系的两个结点之间连边

67 实例 例12 偏序集<{1,2,3,4,5,6,7,8,9}, R整除>和<P({a,b,c}),R>的 哈斯图.

68 实例 例13 已知偏序集<A,R>的哈斯图如下图所示, 试求出集合A 和关系R的表达式.
解 A={ a, b, c, d, e, f, g, h } R={<b,d>,<b,e>,<b,f>,<c,d>,<c,e>,<c,f>,<d,f>,<e,f>,<g,h>}∪IA

69 偏序集中的特殊元素 定义7.24 设<A,≼>为偏序集, BA, y∈B
偏序集中的特殊元素  定义7.24 设<A,≼>为偏序集, BA, y∈B (1) 若x(x∈B→y≼x)成立, 则称 y 为B的最小元 (2) 若x(x∈B→x≼y)成立, 则称 y 为B的最大元 (3) 若x(x∈B∧x≼y→x=y)成立, 则称 y 为B的极小元 (4) 若x(x∈B∧y≼x→x=y)成立, 则称 y 为B的极大元 性质： (1) 对于有穷集，极小元和极大元一定存在，可能存在多个. (2) 最小元和最大元不一定存在，如果存在一定惟一. (3) 最小元一定是极小元；最大元一定是极大元. (4) 孤立结点既是极小元，也是极大元.

70 偏序集中的特殊元素 定义7.25 设<A, ≼>为偏序集, BA, y∈A
偏序集中的特殊元素  定义7.25 设<A, ≼>为偏序集, BA, y∈A (1) 若x(x∈B→x≼y)成立, 则称y为B的上界 (2) 若x(x∈B→y≼x)成立, 则称y为B的下界 (3) 令C＝{y| y为B的上界}, C的最小元为B的最小上界或上确界 (4) 令D＝{y| y为B的下界}, D的最大元为B的最大下界或下确界 性质： (1) 下界、上界、下确界、上确界不一定存在 (2) 下界、上界存在不一定惟一 (3) 下确界、上确界如果存在，则惟一 (4) 集合的最小元是其下确界，最大元是其上确界；反之不对.

71 实例 例14 设偏序集<A,≼>，求A的极小元、最小元、极大元、最
大元，设B＝{ b,c,d }, 求B的下界、上界、下确界、上确界. 解 极小元：a, b, c, g； 极大元：a, f, h； 没有最小元与最大元. B的下界和最大下界都不存在； 上界有 d 和 f, 最小上界为 d.

72 实例 例15 设X为集合, A＝P(X)－{}－{X}, 且A≠. 若|X|=n, n≥2. 问：
(1) 偏序集 <A, R> 是否存在最大元？ (2) 偏序集 <A, R> 是否存在最小元？ (3) 偏序集 <A, R> 中极大元和极小元的一般形式是什么？ 并说明理由. 解 (1) <A, R> 不存在最小元和最大元, 因为n≥2. (2) <A, R> 的极小元就是 X 的所有单元集, 即{x}, x∈X. (3) <A, R> 的极大元恰好比 X 少一个元素, 即X{x}, x∈X.

73 第七章 习题课 主要内容 有序对与笛卡儿积的定义与性质 二元关系、从A到B的关系、A上的关系 关系的表示法：关系表达式、关系矩阵、关系图
第七章 习题课 主要内容 有序对与笛卡儿积的定义与性质 二元关系、从A到B的关系、A上的关系 关系的表示法：关系表达式、关系矩阵、关系图 关系的运算：定义域、值域、域、逆、合成、限制、像、幂 关系运算的性质: A上关系的自反、反自反、对称、反对称、传递的性质 A上关系的自反、对称、传递闭包 A上的等价关系、等价类、商集与A的划分 A上的偏序关系与偏序集

74 基本要求 熟练掌握关系的三种表示法 能够判定关系的性质（等价关系或偏序关系） 掌握含有关系运算的集合等式
掌握等价关系、等价类、商集、划分、哈斯图、偏序集等概念 计算AB, dom R, ranR, fldR, R1, RS , Rn , r(R), s(R), t(R) 求等价类和商集A/R 给定A的划分，求出 所对应的等价关系 求偏序集中的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界 掌握基本的证明方法 证明涉及关系运算的集合等式 证明关系的性质、证明关系是等价关系或偏序关系

75 练习1 1．设A = {1, 2, 3}, R = {<x,y> | x, yA且x+2y  6 }，
S = {<1,2>, <1,3>,<2,2>}, 求: (1) R的集合表达式 (2) R1 (3) dom R, ran R, fld R (4) RS, R3 (5) r(R), s(R), t(R)

76 解答 (1) R = {<1,1>, <1,2>, <2,1>, <2,2>, <3,1>} (2) R1 = {<1,1>, <2,1>, <1,2>, <2,2>, <1,3 >} (3) domR = {1, 2, 3}, ranR = {1,2}, fldR = {1, 2, 3} (4) RS = {<1,2>, <1,3>, <2,2>, <2,3>, <3,2>, <3,3>} R3 = {<1,1>, <1,2>, <2,1>, <2,2>, <3,1>, <3,2>} (5) r(R) = {<1,1>, <1,2>, <2,1>, <2,2>, <3,1>, <3,3>} s(R) = {<1,1>,<1,2>,<2,1>, <2,2>, <3,1>, <1,3>} t(R) = {<1,1>, <1,2>, <2,1>, <2,2>, <3,1>, <3,2>}

77 练习2 2．设A={1,2,3,4}，在AA上定义二元关系R：
<<x,y>,<u,v>>R  x+y = u+v， 求R导出的划分. AA={<1,1>, <1,2>, <1,3>, <1,4>, <2,1>, <2,2>, <2,3>, <2,4>,<3,1>, <3,2>, <3,3>, <3,4>, <4,1>, <4,2>, <4,3>, <4,4>} 根据 <x,y> 中的 x+y = 2, 3, 4, 5, 6, 7, 8 将A划分成等价类： A/R={{<1,1>}, {<1,2>,<2,1>}, {<1,3>, <2,2>, <3,1>}, {<1,4>, <2,3>, <3,2>, <4,1>}, {<2,4>, <3,3>, <4,2>}, {<3,4>, <4,3>}, {<4,4>}}

78 练习3 3．设R是Z上的模 n 等价关系, 即 xy  x  y(modn), 试给出由R确定的Z的划分.
解 设除以 n 余数为 r 的整数构成等价类 [r]，则 [r] ={ kn+r | kZ }, r = 0, 1, …, n1  = { [r] | r = 0, 1, …, n1}

79 练习4 a b c d e 4．设偏序集 <A, R> 的哈斯图如图所示. (1) 写出A和R的集合表达式
(2) 求该偏序集中的极大元、极小元、最大元、最小元 解 (1) A = {a, b, c, d, e} R = {<d,b>, <d,a>, <d,c>, <e,c>, <e,a>, <b,a>, <c,a>}IA (2) 极大元和最大元是a, 极小元是d, e； 没有最小元. a b c d e 图11

80 练习5 5．设R是A上的二元关系， 设 S = {<a,b> | c(<a,c>R<c,b>R)}. 证明如果R是等价关系，则S也是等价关系。 证 R是A上的等价关系. (1) 证自反 任取x, xA  <x,x>R  x (<x,x>R<x,x>R)  <x,x>S (2) 证对称 任取<x,y>, <x,y>S  c(<x,c>R<c,y>R)  c (<c,x>R<y,c>R) <y,x>S (3) 证传递 任取<x,y>, <y,z>, <x,y>S  <y,z>S  c (<x,c>R<c,y>R)  d (<y,d>R<d,z>R)  <x,y>R<y,z> R  <x,z>S

81 练习6 6．设偏序集<A,R>和<B,S>，定义AB上二元关系T:
<x,y>T<u,v>  xRu  ySv 证明T为偏序关系. 证 (1) 自反性 任取<x,y>, <x,y>AB  xAyB  xRxySy  <x,y>T<x,y> (2) 反对称性 任取<x,y>,<u,v> <x,y>T<u,v><u,v>T<x,y>  xRu  ySv  uRx  vSy  (xRu  uRx)  (ySv  vSy)  x=u  y=v  <x,y>=<u,v> (3) 传递性 任取<x,y>,<u,v>, <w,t> <x,y>T<u,v><u,v>T<w,t>  xRu  ySv  uRw  vSt  (xRu  uRw)  (ySv  vSt)  xRw  ySt  <x,y>T<w,t>

82 关系性质的证明方法 1. 证明R在A上自反 任取x, xA  ……………………..….…….  <x,x>R
前提 推理过程 结论 2. 证明R在A上对称 任取<x,y>， <x,y> R  ……………………………….  <y,x>R 前提 推理过程 结论

83 关系性质的证明方法 3. 证明R在A上反对称 任取<x,y>，
<x,y>R<y,x>R  ……………………..  x = y 前提 推理过程 结论 4. 证明R在A上传递 任取<x,y>,<y,z>， <x,y>R<y,z>R  ……………………..  <x,z>R 前提 推理过程 结论

84 练习7 7．R,S为A上的关系，证明 RS  t(R)  t(S) 证 只需证明对于任意正整数n, Rn  Sn. 对n归纳.
假设对于n，命题为真，任取<x,y> <x,y>Rn+1  <x,y>Rn∘R  t (<x, t>Rn  <t, y>R)  t (<x, t>Sn  <t, y>S)  <x,y>Sn∘S  <x,y>Sn+1

85 关系等式或包含式的证明方法 数学归纳法（主要用于幂运算） 证明中用到关系运算的定义和公式, 如：
xdomR  y(<x,y>R) yranR  x(<x,y>R) <x,y>R  <y,x>R1 <x,y>R∘S  t (<x,t>R<t,y>S) <x,y>R↾A  xA  <x,y>R yRA]  x (xA  <x,y>R) r(R) = RIA s(R) = RR1 t(R) = RR2…