第5章 关系 Relation.

Presentation on theme: "第5章 关系 Relation."— Presentation transcript:

1 第5章 关系 Relation

2 关系是在集合的基础上定义的一个重要的概念，与集合的概念一样，关系的概念在计算机科学中也是最基本的。它主要反映元素之间的联系和性质，在计算机科学中有重要的意义，如有限自动机和形式语言，编译程序设计，信息检索，数据结构以及算法分析和程序设计的描述中经常出现。 第 5 章 关系

3 第 5 章 关系 内容提要： 1.笛卡尔积及关系的概念 2.关系的性质 3.关系矩阵和关系图 4.复合关系与逆关系 5.关系的闭包
6.等价关系及证明 7.分划、覆盖、等价类、商集的概念 8.偏序与哈斯图 9.关系在计算机科学中的应用 第 5 章 关系

4 5.1.1 笛卡尔积 定义5.1 由n个具有给定次序的个体a1,a2,…,an组成的序列，叫做有序n元组，记作(a1,a2,…,an)。其中ai（i=1,2,…,n）叫做该有序n元组的第i个坐标。 有序n元组与前面所讲的n个元素的集合这两个概念是两个不同的概念，不同在于集合中这n个元素是无序的，而在有序n元组中，必须对这n个元素指定一个次序。因此对任意给定的n个个体，他们只能组成一个n元素的集合，但却可以组成n!个不同的有序n元组。 5.1 关系及其表示

5 5.1.1 笛卡尔积 另外，有序n元组的一种常见的特殊情形是n=2。有序n元组（a,b）又被称为序偶。序偶的一个熟悉的例子是平面上点的笛卡尔坐标表示。例如，序偶（1,3），（2,4），（5,3）等均表示平面上不同的点。 定义5.2 设(a1,a2,…,an)和(b1,b2,…,bn)两个有序n元组，如果ai=bi(i=1,2,…,n)，则称这两个有序n元组相等，记为(a1,a2,…,an)=(b1,b2,…,bn)。 5.1 关系及其表示

6 5.1.1 笛卡尔积 定义5.3 设A1,A2,…,An是任意集合，则称集合 {(a1,a2,…,an)|aiAi,i=1,2,…,n} 为集合A1,A2,…,An的笛卡尔积，记为A1A2…An。 5.1 关系及其表示

7 5.1.1 笛卡尔积 5.1 关系及其表示 例5.1 设A={a,b}，B={1,2,3}，求AB，BA，AA，BB。
解AB={(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)} BA={(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)} AA={(a,a),(a,b),(b,a),(b,b)} BB={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)} 5.1 关系及其表示

8 5.1.1 笛卡尔积 5.1 关系及其表示 例5.2 设A=，B={1,2,3}，求AB，BA。
解 AB=B=， BA=B= 5.1 关系及其表示

9 5.1.1 笛卡尔积 5.1 关系及其表示 定理5.1 设A,B为任意两个有限集，则 |AB|=|A|•|B|
推论5.1 设A1,A2,…,An为任意n个有限集，则 |A1A2…An|=|A1|•|A2|• … •|An| 5.1 关系及其表示

10 5.1.1 笛卡尔积 5.1 关系及其表示 定理5.2 设A,B,C,D为任意四个非空集合，则 (1)ABCD当且仅当AC,BD；
(1)A(B∪C)=(AB)∪(AC) (2)(A∪B)C=(AC)∪(BC) (3)A(B∩C)=(AB)∩(AC) (4)(A∩B)C=(AC)∩(BC) (5)A(B-C)=(AB)-(AC) (6)(A-B)C=(AC)-(BC) 5.1 关系及其表示

11 5.1.1 笛卡尔积 5.1 关系及其表示 例5.3 设A,B,C和D是任意的集合，试问下列等式是否成立？为什么？
(1)(A∩B)(C∩D)=(AC)∩(BD) 解 成立。因为对于任意的（x,y），设 (x,y)(A∩B)(C∩D) xA∩ByC∩D xAxByCyD (x,y)A×C(x,y)B×D (x,y)(AC)∩(BD) 5.1 关系及其表示

12 5.1.1 笛卡尔积 5.1 关系及其表示 (2)(A∪B)(C∪D)=(AC)∪(BD)
解 不成立。举一反例如下：设A=D=，B=C={1}，则(A∪B)(C∪D)=BC={(1,1)}，(AC)∪(BD)=∪=，显然等式不成立。 5.1 关系及其表示

13 5.1.2 关系的基本概念 5.1 关系及其表示 定义5.4 设nI+，A1,A2,…,An为任意n个集合，A1A2…An，则
(3)若=，则称为空关系； (4)若=A1A2…An，则称为普遍关系； (5)若A1=A2=…=An=A，则称为A上的n元关系； (6)若={(x,x)|xA}，则称为A上的恒等关系。 若是由A到B的一个关系，且(a,b)，则a对b有关系，记作ab。 5.1 关系及其表示

14 5.1.2 关系的基本概念 例5.4 设A={1,2,4,7,8}，B={2,3,5,7}，定义由A到B的关系={(a,b)|(a+b)/5是整数}，求关系。 解 根据的定义，中的序偶(a,b)应满足如下三个条件：（1）aA；（2）bB；（3）a+b能被5整除，于是={(2,3),(7,3),(8,2),(8,7)}。 5.1 关系及其表示

15 5.1.2 关系的基本概念 例5.5 设A={2,3,4,5,9,25}，定义A上的关系，对于任意的a,bA，当且仅当(a-b)² A时，有ab，试问由哪些序偶组成？ 解 根据的定义，中的序偶(a,b)应满足以下三个条件：（1）aA；（2）bB；（3）(a-b)² A。因此 ={(2,4),(4,2),(2,5),(5,2),(3,5),(5,3),(4,9),(9,4)}。 5.1 关系及其表示

16 5.1.2 关系的基本概念 5.1 关系及其表示 例5.6 设A={0,1,2}，求A上的普遍关系UA和A上的恒等关系IA。
解 由普遍关系和恒等关系的定义知 UA=AA={(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)}， IA={(0,0),(1,1),(2,2)}。 5.1 关系及其表示

17 5.1.2 关系的基本概念 5.1 关系及其表示 定义5.5 设是从集合A到B的关系，令
dom={x|xA且有yB使(x,y)} ran={y|yB且有xA使(x,y)} 则称dom为的定义域；ran为的值域。 从定义5.5可以看出，的定义域实际上是由中所有序偶的第一坐标构成的集合，的值域是由中所有序偶的第二坐标构成的集合。 5.1 关系及其表示

18 5.1.2 关系的基本概念 例5.7 设1={(1,2),(2,4),(3,3)}，2={(1,3),(2,4),(4,2)}，试求出dom1，dom2，dom(1∪2)，ran1，ran2和ran(1∩2)。 解 根据的定义域和值域的定义有 dom1={1,2,3}， ran1={2,3,4} dom2={1,2,4}， ran2={2,3,4} 又因为 1∪2={(1,2),(2,4),(3,3),(1,3),(4,2)}， 1∩2={(2,4)} 所以 dom(1∪2)={1,2,3,4}， ran(1∩2)={4}。 5.1 关系及其表示

19 5.1.3 关系的表示方法 1. 集合表示法 因为关系是一个集合，因此可以用集合的列举法或描述法来表示它。在前面的叙述中，已经多次采用了这两种方法。 例如，例4.4中定义的由A到B的关系={(a,b)|(a+b)/5是整数}，用的就是描述法，而例4.7中定义的关系1={(1,2),(2,4),(3,3)}和2={(1,3),(2,4),(4,2)}，用的是列举法。 5.1 关系及其表示

20 5.1.3 关系的表示方法 2. 关系矩阵 定义5.6 设m,nI+，A={x1,x2,…,xm}，B={y1,y2,…,yn}，是从A到B的关系，令 1 若(xi,yi) 其中aij= (1≤i≤m,1≤j≤n) 0 否则 称M为的关系矩阵。  5.1 关系及其表示

21 5.1.3 关系的表示方法 例5.8 设A={2,3,4,5}，B={6,7,8,9}，由A到B的关系定义为={(a,b)|a与b互素}。试写出的关系矩阵M。 解 由定义={(2,7),(2,9),(3,7),(3,8),(4,7),(4,9),(5,6),(5,7),(5,8),(5,9)}，所以关系矩阵 5.1 关系及其表示

22 5.1.3 关系的表示方法 3. 关系图 定义4.7 设A和B是任意的非空有限集，是一个从A到B的关系，以A∪B中的每个元素为一个结点，对每个(x,y)，画一条从x到y的有向边，得到一个有向图G，称其为的关系图。 5.1 关系及其表示

23 5.1.3 关系的表示方法 例5.9 设A={1,2,3,4}，={(1,1),(1,2),(2,3),(2,4),(4,2)}，画出的关系图。 5.1 关系及其表示 ① ② ④ ③

24 5.2 关系 的性质 定义5.8 设为集合A上的二元关系，则 (1)若对所有的aA，有(a,a)，则称为自反关系；
(3)对任意a,bA，若有(a,b)，就必有(b,a)，则称为对称关系； (4)对任意a,bA，若有(a,b)，(b,a)，就必有a=b，则称为反对称关系； (5)对任意a,b,c A，若有(a,b)，(b,c)，就必有(a,c)，则称为传递关系。 5.2 关系 的性质

25 5.2 关系 的性质 注意区别自反关系和恒等关系，一个集合A上的恒等关系是自反关系，但自反关系不一定是恒等关系。
另外，反对称关系的定义也可等价地叙述为，对任意a,bA，若有a≠b且(a,b)，就必有(b,a)，则称为反对称关系。 5.2 关系 的性质

26 5.2 关系 的性质 例5.10 设A={a,b,c,d} (1)判断下列关系是否为自反关系或反自反关系； 1={(a,b),(b,c)}
2={(a,a),(b,b),(c,c),(d,a)} 3={(a,a),(a,b),(d,d),(c,c),(b,b)} 4={(a,a),(b,b),(c,c),(d,d)} 解 1不是自反关系，因为对于所有的xA，(x,x)均不在1中；上述原因正好说明1是反自反关系。 2不是自反关系，因为(d,d)2；2也不是反自反关系，因为(a,a),(b,b),(c,c) 2。 3是自反关系，不是反自反关系。 4是自反关系，不是反自反关系。 5.2 关系 的性质

27 5.2 关系 的性质 (2)判断下列关系是否为对称关系或反对称关系； 5={(a,a),(a,b),(b,a),(b,c),(c,b)}
6={(a,a),(a,b),(b,c),(d,c)} 7={(a,a),(c,b),(c,d),(d,c)} 8={(b,b),(d,d)} 解 5是对称关系，但不是反对称关系，因为a≠b，但(a,b)和(b,a)均出现在5中，同样b≠c，但(b,c)和(c,b)均出现在5中。 6不是对称关系，因为(a,b)6，但(b,a)6，同样(b,c)6，但(c,b)6，(d,c)6但(c,d)6；而上述原因正好说明6是反对称关系。 7不是对称关系，因为(c,b)7但(b,c)7；7也不是反对称关系，因为c≠d，但(c,d)和(d,c)均在7中。 8既是对称关系，也是反对称关系。 5.2 关系 的性质

28 5.2 关系 的性质 (3)判断下列关系是否为传递关系。 9={(b,c),(c,c),(c,d),(b,d)}
10={(b,c),(c,b),(b,b),(a,d)} 11={(b,c),(d,a),(d,c)} 解 9是传递关系。 10不是传递关系，因为(c,b)10，(b,c)10，但(c,c)10。 11是传递关系，在11中没有出现(x,y)11同时(y,z)11的情形，因此也就无所谓(x,z)11的要求。 5.2 关系 的性质

29 5.2 关系 的性质 关系的这些性质，在关系矩阵和关系图上大多可以得到明确的反映：
若关系是自反的，则关系矩阵的主对角线上的元素全为1；若是对称的，则关系矩阵关于主对角线对称；若是反对称的，则对ij，若aij =1，则aji =0。 5.2 关系 的性质

30 若关系是自反的，则的关系图中的每一个结点引出一个单边环；若是对称的，则在其关系图中，对每一由结点ai指向结点aj的边，必有一相反方向的边；若是反对称的，则在其图中，任何两个不同的节点间最多只有一条边，而不会同时有两条相反方向的边；若是传递的，则若有由结点ai指向ak的边，且又有由结点ak指向aj的边，就必有一条由结点ai指向aj的边。 5.2 关系 的性质

31 5.3.1 复合关系 定义5.9 设1为从集合A到集合B的关系，2为从集合B到集合C的关系，则称A到C的关系 {(x,z)|xA, zC,有yB使(x,y)1且(y,z)2} 为1与2的复合关系，记为1  2。这种从1和2得到1  2的运算，叫做关系的复合运算。 复合关系1  2与关系1和2之间的联系，我们可用下图表示。 B A C 5.3 关系的运算 2 x y z 1

32 5.3.1 复合关系 例5.11 设集合A={1,2,3,4}，B={2,3,4,5}，C={0,1,2}，1是从A到B的关系，2是从B到C的关系，分别定义为： 1={(a,b)|a+b=6}，2={(b,c)|b-c=2}， 试求复合关系1  2和2  1。 解 由题意知 1={(1,5),(2,4),(3,3),(4,2)} 2={(2,0),(3,1),(4,2)} 根据复合关系的定义 1  2={(2,2),(3,1),(4,0)} 2  1={(3,5),(4,4)} 5.3 关系的运算

33 5.3.1 复合关系 定理5.4 设A,B,C,D为任意四个集合，1是从A到B的关系，2 和3是从B到C的关系，4是从C到D的关系，于是有： (1)若2  3 ，则1  2  1  3 ，2  4  3  4； (2) 1  (2∪3) = (1  2)∪(1  3) (3) (2∪3)  4 = (2  4)∪(3  4) (4) 1  (2∩3)  (1  2)∩(1  3) (5) (2∩3)  4  (2  4)∩(3  4) (6) (1  2)  4 = 1  (2  4) 5.3 关系的运算

34 5.3.1 复合关系 定义5.10 设1,2,…,n分别是A1到A2,A2到 A3,…,An到An+1的关系，则称关系 {(x1,xn+1)|x1A,xn+1An+1,存在x2A2,…,xnAn,使(x1,x2)1,…,(xn,xn+1)n} 为1,2,…,n的复合，记为1  2  …n 。 当A1=A2=…=An+1=A，1=2=…=n=时，则复合关系12 …n= …称为的n次幂，记为ⁿ。 5.3 关系的运算

35 5.3.1 复合关系 5.3 关系的运算 例5.12 设A={1,2,3,4}，A上的关系={(2,1),(3,2),(4,3)}，则有
2={(3,1),(4,2)} 3={(4,1)} 4= 5.3 关系的运算

36 5.3.1 复合关系 5.3 关系的运算 练习 设1和2是集合A上的两个关系，判断下列命题是否正确。
(1)若1和2是自反的，则1  2也是自反的； (2)若1和2是对称的，则1  2也是对称的； (3)若1和2是反对称的，则1  2也是反对称的； (4)若1和2是传递的，则1  2也是传递的。 5.3 关系的运算

37 5.3.1 复合关系 5.3 关系的运算 定义5.11 设A为任意集合，为A上的任意二元关系，则有：
（1）0是A上的恒等关系，即0 = IA； （2）n+1 =   n，nN。 定理5.5 设m,nN，为集合A上的二元关系，则 （1）m  n = m+n （2）(n)m = m·n 5.3 关系的运算

38 5.3.1 复合关系 为了研究复合关系的关系矩阵，我们首先介绍布尔运算，布尔运算只涉及数字0和1，有两个运算符“”和“”，运算规则如下： 00=0， 01=1， 10=0， 11=1； 00=0， 01=0， 10=0， 11=1。 然后用布尔运算来定义两个关系矩阵的乘积运算“*”如下： 其中 ≤i≤m，1≤j≤p 5.3 关系的运算 * =

39 5.3.1 复合关系 5.3 关系的运算 定理5.6 设A,B,C是非空有限集，1是从A到B的关系，2是从B到C的关系，则
M1  2 = M1 * M2 推论5.2 设A1,A2,…,An+1是有限集合，1,2,…,n分别是A1到A2,A2到A3,…,An到An+1的关系，它们的关系矩阵分别为M1,M2,…,Mn ,则有： M1  2  …  n = M1 * M2 * … * Mn 推论5.3 是集合A上的关系，M为其关系矩阵，则有 Mn = (M)n 5.3 关系的运算

40 5.3.1 复合关系 对于集合A上的二元关系，其复合关系n，仍是A上的二元关系。我们可以用如下的方法由的关系图作出n的关系图。 由的关系图构成n的关系图的步骤如下： （1）对的关系图（假设有m个结点）中每个结点ai(i=1,2,…,m)，找出从ai经由长为n的路能够到达的结点aj； （2）连接aiaj得n的一条边； （3）前两步得到的所有边组成n的关系图。 5.3 关系的运算

41 5.3.1 复合关系 练习 设A={a,b,c,d},A上的关系={(a,a),(a,b),(b,d),(c,a),(d,c)}，试求复合关系² 。 5.3 关系的运算

42 5.3.2 逆关系 5.3 关系的运算 定义5.12 设是从集合A到B的关系，则如下从B到A的关系：
{(y,x)|yB,xA且(x,y)} 称为关系的逆关系，记为-1，这种从得到-1的运算，叫做关系的逆运算。 显然，从集合A到B的关系的逆关系是将中每一个序偶的坐标顺序互换所得到的集合。 5.3 关系的运算

43 5.3.2 逆关系 5.3 关系的运算 定理5.7 设A,B为非空有限集，是从A到B的关系，则有：
（1）M-1 = MT(MT为M的转置矩阵，即将M中的行和列互换) （2）把G的每条有向边反向，就得到-1的关系图G-1。 5.3 关系的运算

44 5.3.2 逆关系 例5.13 设A={a,b,c},A上的关系={(a,a),(a,c),(b,a),(b,b),(c,a),(c,b)}，试求逆关系-1及其关系矩阵、关系图。 解 由逆关系的定义知 -1={(a,a),(c,a),(a,b),(b,b), (a,c),(b,c)} 5.3 关系的运算

45 5.3.2 逆关系 5.3 关系的运算 定理5.8 设和i(i=1,2,…)都是从集合A到集合B的二元关系，则有：
（1）(-1)-1=； （2）若12，则1-12-1； （3）若1=2，则1-1=2-1 定理5.9 设是集合A上的二元关系，则有： （1）是自反的，当且仅当-1是自反的； （2）是反自反的，当且仅当-1是反自反的； （3）是对称的，当且仅当-1是对称的； （4）是反对称的，当且仅当-1是反对称的； （5）是传递的，当且仅当-1是传递的。 5.3 关系的运算

46 5.3.2 逆关系 5.3 关系的运算 定理5.10 设A,B,C是三个集合，1是从A到B的关系，2是从B到C的关系，则有：
(1  2)-1 = 2-1  1-1 推论5.4 设nN，是集合A上的二元关系，则(n)-1 =(-1)n 。 5.3 关系的运算

47 5.3.2 逆关系 5.3 关系的运算 例5.14 设是A上的二元关系，则是对称的当且仅当=-1 。
证明 任取(x,y)，则(y,x)，从而(x,y)-1，所以-1。反之，任取(x,y)-1，则(y,x)，从而(x,y)，所以-1。因此=-1。 若设=-1，任取(x,y)，则(y,x)-1，但=-1，所以(y,x)，因此对称。 由以上两方面知该命题成立。 5.3 关系的运算

48 5.3.3 关系的闭包 5.3 关系的运算 定义5.13 设为集合A上的二元关系，如果A上的二元关系满足：
(1)是自反(对称，传递)的； (2)； (3)若A上的二元关系也满足(1)(2)，则； 则称为的自反(对称，传递)闭包，记为r()(s(),t())。 从定义可以看出，的自反(对称，传递)闭包就是包含并且具有自反(对称，传递)性质的最小关系。显然，若已经是自反(对称，传递)的，那么的自反(对称，传递)闭包就是它自身。 5.3 关系的运算

49 5.3.3 关系的闭包 5.3 关系的运算 定理5.11 设是A上的二元关系，则： (1) 是自反的，当且仅当r()=；
(2) 是对称的，当且仅当s()=； (3) 是传递的，当且仅当t()=。 5.3 关系的运算

50 5.3.3 关系的闭包 5.3 关系的运算 定理5.12 设是集合A上的二元关系，则： (1) r()=∪IA；
(2) s()=∪-1； (3) 定理5.13 设A为n个元素的有限集，为A上的二元关系，则 5.3 关系的运算

51 5.3.3 关系的闭包 例5.15 设A={a,b,c},A上的二元关系={(a,b),(b,c),(c,a)}，求r(),s(),t()。 解 r()=∪IA={(a,b),(b,c),(c,a)}∪{(a,a),(b,b),(c,c)} ={(a,a),(a,b),(b,b),(b,c),(c,a),(c,c)} s()=∪-1={(a,b),(b,c),(c,a)}∪{(b,a),(c,b),(a,c)} ={(a,b),(a,c),(b,a),(b,c),(c,a),(c,b)} t()=∪2∪3 ={(a,b),(b,c),(c,a)}∪{(a,c),(b,a),(c,b)}∪{(a,a), (b,b),(c,c)} ={(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a),(c,b),(c,c)} 5.3 关系的运算

52 5.3.3 关系的闭包 练习 设1和2是集合A上的两个关系， (1)试证明 (2) 成立吗？为什么？ 5.3 关系的运算

53 5.4.1 等价关系及判定 5.4 等价 关系 定义4.14 设是集合A上的二元关系，若是自反，对称和传递的，则称为等价关系。
在我们日常生活和学习中，就有一些等价关系的例子，如： （1）在一群人的集合上年龄相等的关系是等价关系，而朋友关系不一定是等价关系，因为它可能不是传递的。 （2）命题公式间的逻辑等值关系是等价关系。 （3）集合上的恒等关系和普遍关系都是等价关系。 （4）在同一平面上直线之间的平行关系，三角形之间的相似关系都是等价关系。 5.4 等价 关系

54 5.4.1 等价关系及判定 5.4 等价 关系 例5.16 设A={a,b,c,d,e}，A上的关系
1={(a,a),(a,b),(b,a),(b,b),(c,c),(d,d),(d,e),(e,d),(e,e)}， 2={(a,b),(b,a),(b,b),(c,c),(d,d),(d,e)}， 试判断1和2是否为等价关系。 解 1是等价关系，因为它满足自反性，对称性和传递性。 2不是等价关系，因为：①(a,a),(e,e)2，即2不满足自反性；②(d,e)2，但(e,d)2，即2不满足对称性；③(a,b)2，(b,a)2，但(a,a)2，即2不满足传递性。 当然，以上三条原因中只要具备任何一条就可判断2不是等价关系。 5.4 等价 关系

55 5.4.1 等价关系及判定 例5.17 设1是集合A上的一个二元关系，2={(a,b)∣存在c，使(a,c)∈1且(c,b)∈1}，证明若1是一个等价关系，则2也是一个等价关系。 证明 设1是A上的等价关系， （1）对任意一个xA，因为1在A上自反，所以(x,x)1。由2的定义，(x,x)2，所以2是自反的。 5.4 等价 关系

56 5.4.1 等价关系及判定 （2）对任意x,yA，若(x,y)2，则存在某个cA，使得(x,c)1且(c,y)1，因为1是对称，故有(y,c)1且(c,x)1，由2的定义，可知(y,x)2，所以2是对称的。 （3）对任意x,y,zA，若(x,y)2，(y,z)2，则必存在某个c1A，使(x,c1)1，(c1,y)1。由1的传递性，可知(x,y)1，同理存在c2A，使(y,c2)1且(c2,z)1，由1传递，可知(y,z)1。再由2的定义，得(x,z)2。所以2是传递的。 由以上（1）（2）（3）可知2是一个等价关系。 5.4 等价 关系

57 5.4.1 等价关系及判定 5.4 等价 关系 例5.18 设1和2都是集合A上的等价关系，
证明 由交集的定义1∩2={(a,b)|(a,b)1且(a,b)2}。 对任意一个aA，因为1和2都是自反的，所以有(a,a)1且(a,a)2，因而有(a,a)1∩2，故1∩2是自反的。 5.4 等价 关系

58 5.4.1 等价关系及判定 对任意a,bA，若(a,b)1∩2，则有(a,b)1且(a,b)2，由1和2的对称性有(b,a)1且(b,a)2，因而有(b,a)1∩2，故1∩2是对称的。 对任意a,b,cA，若(a,b)1∩2，(b,c)1∩2，则有(a,b)1，(b,c)1；(a,b)2，(b,c)2。由1和2的传递性有(a,c)1，(a,c)2，因而有(a,c)1∩2，故1∩2是传递的。 由以上三方面知1∩2是A上的等价关系。 5.4 等价 关系

59 5.4.1 等价关系及判定 5.4 等价 关系 （2）1∪2是A上的等价关系吗？为什么？
解 为了判断1∪2是否为A上的等价关系，我们试图来证明它的自反性，对称性和传递性。由并集的定义1∪2={(a,b)|(a,b)1或(a,b)2} 对任意一个aA，因为1是自反的，所以有(a,a)1，因而有(a,a)1∪2，故1∪2是自反的。 对任意a,bA，若(a,b)1∪2，则有(a,b)1或(a,b)2，由1和2的对称性有(b,a)1或(b,a)2，因而有(b,a)1∪2，故1∪2是对称的。 5.4 等价 关系

60 5.4.1 等价关系及判定 5.4 等价 关系 对任意a,b,cA，若(a,b)1∪2，(b,c)1∪2，则有
(a,b)1 或 (a,b)2； (b,c)1 或 (b,c)2。 因为(a,b)和(b,c)不一定同时属于1，也不一定同时属于2，所以我们无法推出(a,c)1或(a,c)2，因而也就无法推出(a,c)1∪2，这说明1∪2的传递性不一定成立，因此推不出1∪2是A上的等价关系。 5.4 等价 关系

61 5.4.1 等价关系及判定 5.4 等价 关系 举反例如下：设A={1,2,3}，A上的关系
1={(1,1),(2,2),(3,3),(1,3),(3,1)}； 2={(1,1),(2,2),(3,3),(2,3),(3,2)}。 显然1和2均是等价关系。 1∪2={(1,1),(2,2),(3,3),(1,3),(3,1),(2,3),(3,2)}。 这里1∪2是自反，对称的，但因为(2,3)1∪2且(3,1)1∪2，而(2,1)1∪2，所以1∪2不是传递的。 5.4 等价 关系

62 5.4.2 覆盖与分划 5.4 等价 关系 定义5.15 设A是一个非空集合，是满足下列条件的集合： (1)中元素是A的非空子集；
(3)中元素互不相交。 则称为A的一个分划，中每个元素叫做A的一个分划块。 5.4 等价 关系

63 5.4.2 覆盖与分划 例5.19 设A={0,1,2,3,4}，1={{0,1},{1,2},{2,3,4}}，2={{0,1},{2,3},{4}}，则1是A的一个覆盖但不是分划，2既是A的一个覆盖，也是A的一个分划。 5.4 等价 关系

64 5.4.2 覆盖与分划 定义5.16 设1={A1,A2,…,An}，2={B1,B2,…,Bn}都是集合A的分划，如果对每个Ai均有一个Bj使AiBj，则称分划1是分划2的细分或加细。 例5.20 设A={a,b,c}，1={{1},{2},{3}}，2={{1},{2,3}}，3={{1,2,3}}，则1，2和3都是集合A的分划，且1是2和3的细分，2是3的细分。 5.4 等价 关系

65 5.4.3 等价类与商集 定义5.17 设为集合A上的等价关系，任取aA，集合[a]={x|xA,(a,x)}称为a形成的的等价类，有时也简记为[a]。 由定义知，[a]是非空的，因为至少有a[a]。 5.4 等价 关系

66 5.4.3 等价类与商集 例5.21 设A={a,b,c,d,e}，A上的关系={(a,a),(a,b),(b,a),(b,b),(c,c),(d,d),(d,e),(e,d),(e,e)}， 确定由集合A中的元素产生的等价类。 解 对于元素a，因为(a,a)，(b,a)，所以a产生的等价类[a] ={a,b}。 对于元素b，因为(b,b)，(a,b)，所以b产生的等价类[b] ={a,b}。 类似地，[c] ={c}，[d] ={e,d}，[e] ={e,d}。 5.4 等价 关系

67 5.4.3 等价类与商集 定理5.14 设是集合A上的等价关系，对于a,bA，有(a,b)当且仅当[a] =[b]。 定义5.18 设是集合A上的等价关系，则称集合{[a]|aA}为A关于的商集，记为A/，商集的基数称为等价关系的秩。 如例5.21中的商集为A/={[a],[b],[c],[d],[e]} ={{a,b},{c},{d,e}}。 5.4 等价 关系

68 5.4.3 等价类与商集 定理5.15 设是集合A上的等价关系，则A关于的商集A/是A的一个分划，称为A关于的等价分划。 定理5.16 集合A的一个分划确定A上的一个等价关系。 5.4 等价 关系

69 5.4.3 等价类与商集 例5.22 设A={a,b,c,d,e}有一个分划={{a,b},{c},{d,e}}，求所确定的等价关系。 解 设 1={a,b}{a,b}={(a,a),(a,b),(b,a),(b,b)}， 2={c}{c}={(c,c)}, 3={d,e}{d,e}={(d,d),(d,e),(e,d),(e,e)}。 所以=1∪2∪3={(a,a),(a,b),(b,a),(b,b),(c,c), (d,d),(d,e),(e,d),(e,e)}。 5.4 等价 关系

70 5.4.3 等价类与商集 5.4 等价 关系 例5.23 设A是由4个元素组成的集合，试问在A上可以定义多少个不同的等价关系？
解 如果直接考虑A上可以定义多少个等价关系，则计算过程比较繁琐，也容易出错。根据定理5.16可知集合A上的等价关系与分划存在一一对应的关系，因此此题可转化为考虑A上有多少个不同的分划。 5.4 等价 关系

71 5.4.3 等价类与商集 5.4 等价 关系 将集合A分划为一块：有1种分法； 将集合A分划为两块：有C(4,2)/2+C(4,1)种分法；
1+C(4,2)/2+C(4,1)+C(4,2)+1=15。 5.4 等价 关系

72 定义5.19 设是非空集合A上的关系，若是自反的，反对称和传递的，则称为A上的偏序关系。A与合在一起称为偏序集，记作<A,>。
若是偏序关系，<A,>常记为<A,≤>，读作“小于或等于”，因为“小于或等于”也是一种偏序，故不会产生混乱。所以，是偏序关系，ab就表示成a≤b，如果ab，则可以表示成a＜b。 5.5 偏序 关系

73 5.5 偏序 关系 例5.24 偏序的一些例子。 （1）实数集R上的“≤关系”是偏序关系，<R,≤>表示一个偏序集。
例5.24 偏序的一些例子。 （1）实数集R上的“≤关系”是偏序关系，<R,≤>表示一个偏序集。 （2）集合A的幂集P(A)上的“关系”是偏序关系，<P(A),>表示一个偏序集。 （3）正整数集合上的整除关系是偏序关系，<I+,|>表示一个偏序集。 5.5 偏序 关系

74 练习 设是集合A上的偏序关系，BA，试证明∩(BB)是B上的偏序关系。
5.5 偏序 关系

75 5.5 偏序 关系 定义5.20 设<A,≤>为偏序集，对于任意的x,yA，如果x≤y或者y≤x成立，则称x与y是可比的。
定义5.21 设<A,≤>为偏序集。对于任意的x,yA，若x＜y且不存在zA，使得x＜z＜y，则称y为x的覆盖。 例5.25 在偏序集<R,≤>中任何实数均无覆盖，因为任意两个实数之间均有另外的实数。偏序集<N,≤>中每个自然数均有惟一的覆盖。 5.5 偏序 关系

76 5.5 偏序 关系 设≤是集合A上的偏序关系，则≤的哈斯图作图规则如下： (1)图中每个顶点代表A的一个元素；
(2)若x＜y，则顶点y在顶点x的上方； (3)若x＜y，且y是x的覆盖，则x与y间连一条无向边。 5.5 偏序 关系

77 5.5 偏序 关系 例5.26 设A={2,3,6,12,24,36}，A上的整除关系“|”是如下的一个偏序关系：
{(2,2),(2,6),(2,12),(2,24),(2,36),(3,3),(3,6),(3,12),(3,24),(3,36),(6,6),(6,12),(6,24),(6,36),(12,12),(12,24),(12,36),(24,24),(36,36)} 作上述偏序关系的哈斯图时，首先求出各元素的覆盖，然后再作图。 2的覆盖是6；3的覆盖是6；6的覆盖是12；12的覆盖是24,36；24和36没有覆盖。 5.5 偏序 关系

78 例5.27 设A={a,b,c}，集合A的幂集P(A)上的“关系”是偏序关系，画出其哈斯图。
5.5 偏序 关系

79 5.5 偏序 关系 定义5.22 设<A,≤>为偏序集，BA，bB，
（1）若x(xB→b≤x)为真，则称b为B的最小元。 （2）若x(xB→x≤b)为真，则称b为B的最大元。 （3）若x(xB  bx  x≤b)为真，则称b为B的极小元。 （4）若x(xB  bx  b≤x)为真，则称b为B的极大元。 5.5 偏序 关系

80 5.5 偏序 关系 例5.28 偏序集<{a,b,c,d,e,f,g,h},≤>，由下图的哈斯图给出。
（1）B1={b,d,e,g} （2）B2={b,c,d,e,f,g} （3）B3={a,c,d} （4）B4={d,e} 解 （1）B1的最大元为g； B1的极大元为g； B1的最小元为b； B1的极小元也为b。 5.5 偏序 关系 h f g d e b c a

81 5.5 偏序 关系 （2）B2无最大元和最小元； B2的极大元是f,g；极小元是b,c。 （3）B3无最大元，其最小元为a；
B3的极大元为c,d；极小元为a。 （4）B4无最大元，也无最小元； B4的极大元是d,e；极小元也是d,e。 5.5 偏序 关系

82 5.5 偏序 关系 定理5.17 设<A,≤>为偏序集，BA。 （1）若b为B的最大（最小）元，则b为B的极大（极小）元。

83 5.5 偏序 关系 定义5.23 设<A, ≤>为偏序集，BA，bA，
（1）若x(xB→b≤x)为真，则称b为B的下界。 （2）若x(xB→x≤b)为真，则称b为B的上界。 （3）若b是一下界且对每一个B的下界b有b≤b，则称b为B的最大下界或下确界，记为glb。 （4）若b是一上界且对每一个B的上界b有b≤b，则称b为B的最小上界或上确界，记为lub。 5.5 偏序 关系

84 5.5 偏序 关系 例5.29 同例5.28 （1）当B1={b,c,d,e,g}时，B1有上界g,h，下界a；最小上界g，最大下界a 。
例5.29 同例5.28 （1）当B1={b,c,d,e,g}时，B1有上界g,h，下界a；最小上界g，最大下界a 。 （2）当B2={b,e,d,f}时，B2有上界h，下界b,a；最小上界h，最大下界b。 5.5 偏序 关系

85 例5.30 右图中的哈斯图表示一偏序集。考虑集合B1={h, i}，它有上界j，k，但无最小上界；它有下界f，g, b, c, d, e, a，但没有最大下界。当B2={b,c,d,e}时，它有上界h，i, j, k，无最小上界；它没有下界和最大下界。 5.5 偏序 关系 j k h i f g b c d e a

86 5.5 偏序 关系 定理5.18 设<A, ≤>为偏序集，BA。
（1）若b为B之最大元（最小元），则b必为B最小上界（最大下界）。 （2）若b为B之上（下）界，且bB，则b必为B的最大（最小）元。 （3）如果B有最大下界（最小上界），则最大下界（最小上界）惟一。 5.5 偏序 关系

87 5.5 偏序 关系 定义5.24 设<A, ≤>为偏序集，BA。 （1）若B中任何两个元素都是可比的，即
xy(x,yB→x≤y  y≤x) 则称B为A上的链，|B|称为链的长度。 （2）若B中任何两个不同元素都是不可比的，即 xy(x,yBxy→(x≤y)(y≤x)) 则称B为A上的反链，|B|称为反链的长度。 5.5 偏序 关系

88 例5.31 例5.30的哈斯图中有链{a, c, f, h, j}，{a, d, g, h, j}，{e, g, h, k}等,长度分别为5，5，4。有反链{b, c, d, e}，{f, g}等，长度分别为4，2。 5.5 偏序 关系

89 关系在关系数据库中的应用 关系代数与数据子语言 等价关系在计算机中的应用 序关系在项目管理中的应用 （见教材，自学） 5.6
关系在计算机科学中的应用

90 知识回顾 小结 1. 基本概念 有序n元组、笛卡尔积、关系的定义、空关系、普遍关系、恒等关系、集合A上的关系、逆关系、复合关系、关系的闭包
2. 关系的表示方法 （1）集合的表示法 （2）关系矩阵 （3）关系图 小结

91 知识回顾 3. 集合A上关系的性质 自反、反自反、对称、反对称、传递 4. 集合A上特殊关系 等价关系、偏序关系 小结

92 课外作业 教材P 1,5,8(1)(3)(5),12,19,25,27,33 小结