离散数学课件：CH2－关系

1、0 1 第二章第二章 关关 系系 本章讨论的关系（主要是二元关系），它仍然是一种 集合，但它是比第一章更为复杂的集合。它的元素是 有序二元组的形式，这些有序二元组中的两个元素来 自于两个不同或者相同的集合。因此，关系是建立在 其它集合基础之上的集合。关系中的有序二元组反映 了不同集合中元素与元素之间的关系，或者同一集合 中元素之间的关系。本章讨论这些关系的表示方法、 关系的运算以及关系的性质及其判定方法，最后讨论 集合 A 上几类特殊的关系。 2 主要内容如下： 2.1 笛卡尔积与关系2.5 等价关系 2.2 关系的表示 2.6 相容关系 2.3 关系的复合运算 2.7 偏序关系 2.4 关系

2、的性质与闭包 习题课 3 一、有序一、有序 n 元组与笛卡尔积元组与笛卡尔积 1. 有序有序 n 元组元组 定义定义2-1 由由 n 个具有给定次序的个体个具有给定次序的个体 a1, a2, , an 组成的序列称组成的序列称 为为有序有序 n 元组元组，记作，记作 (a1, a2, , an)，其中第，其中第 i 个元素个元素 ai 常称为常称为 该有序该有序 n 元组的第元组的第 i 个个分量分量或或坐标坐标。 注意：注意：有序 n 元组与 n 个元素的集合，是不相同的。 例如例如 a, b, c, d = b, a, d, c = a, b, d, c 但但 (a, b, c, d) (

3、b, a, d, c) (a, b, d, c) 又如又如 4, 4, 3, 2 = 4, 3, 2，但，但 (4, 4, 3, 2) (4, 3, 2) 2.1 笛卡尔积与关系笛卡尔积与关系 4 定义定义2-2 设设 (a1, a2, , an) 和和 (b1, b2, , bn) 是两个有序是两个有序 n 元组，元组， 若若a1 = b1, a2 = b2, , an = bn，则称这，则称这两个有序两个有序 n 元组相等元组相等，并，并 记作记作 (a1, a2, , an) = (b1, b2, , bn)。 当当 n = 2 时，有序二元组时，有序二元组 (a, b) 又称为又称为序

4、偶序偶。 如平面上点的笛卡儿坐标表示就是序偶。如平面上点的笛卡儿坐标表示就是序偶。 2. 笛卡尔积笛卡尔积 1）笛卡尔积的定义笛卡尔积的定义 定义定义2-3 设设 A, B 为两个集合，称集合为两个集合，称集合 A B = (a, b) | a A, b B 为为 A 与与 B 的笛卡尔积的笛卡尔积。 5 例例1 设设 A = 0, 1，B = a, b, c，则，则 A B = (0, a), (0, b), (0, c), (1, a), (1, b), (1, c) B A = (a, 0), (b, 0), (c, 0), (a, 1), (b, 1), (c, 1) 推广推广 n 个

5、集合的笛卡儿积为个集合的笛卡儿积为 A1 A2 An = (x1, x2, , xn) | xi Ai, i = 1, 2, , n。 特别特别 A A A = An。 例例2 设设 A = 0, 1，则，则 A2 = A A = (0, 0), (0, 1), (1, 0), (1, 1)。 注：注：（1）两集合的笛卡尔积仍然是一个集合。）两集合的笛卡尔积仍然是一个集合。 （2）两集合的笛卡儿积的元素为序偶，序偶的第一个分量必在）两集合的笛卡儿积的元素为序偶，序偶的第一个分量必在 第一个集合中，第二个分量必在第二个集合中。第一个集合中，第二个分量必在第二个集合中。 6 2）笛卡尔积的性质）笛

6、卡尔积的性质 视两个集合的笛卡儿积为一种运算，它有如下的性质。视两个集合的笛卡儿积为一种运算，它有如下的性质。 不满足封闭性不满足封闭性 例如例如 U = 1, 2, 3, 4，A = 1, 2 2U，B = 3 2U， 但但 A B = (1, 3), (2, 3) 2U。 不满足交换律不满足交换律 A B B A 不满足结合律不满足结合律 (A B ) C A (B C) （反例见教材反例见教材P27例例1） A B = 当且仅当当且仅当 A = 或者或者 B = 。 7 3）笛卡尔积的基数）笛卡尔积的基数（可推广到有限）（可推广到有限） 当当 A 和和 B 均是有限集时，均是有限集时，A

7、 B 必为有限集，且必为有限集，且 #(A B) = #A #B。 当其中有一个是无限集时，笛卡尔积必为无限集。当其中有一个是无限集时，笛卡尔积必为无限集。 4）与笛卡尔积有关的一些恒等式）与笛卡尔积有关的一些恒等式 设设 A、B、C 是任意三个集合，则有是任意三个集合，则有 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) 8 例如例如 以第一个等式以第一个等式 A (B C) = (A B) (A C) 为例，给出为例，给出 其证明。其证明。 证明证明 任取任取 (

8、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)。 9 反之，任取反之，任取 (x, y) (A B) (A C)， 则则 (x, y) A B 或或 (x, y) A C， 于是于是 (x A 且且 y B) 或或 (x A 且且 y C)， 即即 x A 且且 (y B 或或 y C)， 亦即亦即 x A 且且 y

9、B C， 因此因此 (x, y) A (B C)， 故故 (A B) (A C) A (B C) 。 综上所述综上所述 A (B C) = (A B) (A C)。 10 1. 关系的定义关系的定义 定义定义2-4 笛卡尔积笛卡尔积 A B 的任意一个子集的任意一个子集 称为称为由由 A 到到 B 的一的一 个二元关系个二元关系，当，当 A = B 时，称时，称 是是 A 上的二元关系上的二元关系。 可以推广到可以推广到 n 个集合或同一个集合上的个集合或同一个集合上的 n 元关系元关系。 例例3 设设 A = a, b，B = 2, 5, 8， 则则 A B = (a, 2), (a, 5)

10、, (a, 8), (b, 2), (b, 5), (b, 8). 令令 1 = (a, 2), (a, 8), (b, 2)， 2 = (a, 5), (b, 2), (b, 5)， 3 = (a, 2)， 因为因为 1 A B， 2 A B， 3 A B， 所以所以 1， 2 和和 3 均是由均是由 A 到到 B 的关系。的关系。 二、关二、关 系系 11 A = a, b，B = 2, 5, 8 又又 B A = (2, a), (5, a), (8, a), (2, b), (5, b), (8, b)， 令令 4 = (2, a), (2, b)， 5 = (5, a), (8, a

11、), (8, b)， 因为因为 4 B A， 5 B A， 所以所以 4 和和 5 均是由均是由 B 到到 A 的关系。的关系。 又如又如 对于对于 B = 2, 5, 8, B B = (2, 2), (2, 5), (2, 8), (5, 2), (5, 5), (5, 8), (8, 2), (8, 5), (8, 8), 令令 6 = (2, 2), (5, 2), (8, 2), 7 = (8, 5), (5, 2), (2, 8), (2, 5), 因为因为 6 B B， 7 B B， 所以所以 6 和和 7 均是集合均是集合 B 上的关系。上的关系。 12 由有限集由有限集 A

12、到有限集到有限集 B 的二元关系的个数为的二元关系的个数为 #(2A B) = 2#(A B) = 2#A #B。 若若 (a, b) ，则称，则称 a 与与 b 有关系有关系 ，又记作，又记作 a b。 若若 (a, b) ，则称，则称 a 与与 b 没有关系没有关系 ，又记作，又记作 a b。 例如例如 在例在例3中中 a 1 2，a 1 8，但，但 a 1 5。 注意注意 数学上抽象定义的关系，有的在直观上已无法再用自然数学上抽象定义的关系，有的在直观上已无法再用自然 语言来描述了。语言来描述了。 13 2. 几种特殊的关系几种特殊的关系 空关系空关系 对任意集合对任意集合 A 与与 B

13、，因为因为 A B， A A， 所以所以 是由是由 A 到到 B 的关系，的关系， 也是也是 A 上的关系，称为上的关系，称为空关系空关系。 全域关系（或普遍关系）全域关系（或普遍关系） 因为因为 A B A B, A A A A, 所以所以 A B 是一个由是一个由 A 到到 B 的关系，称为的关系，称为由由 A 到到 B 的全关系的全关系； A A 是是 A 上的一个关系，称为上的一个关系，称为 A 上的全关系上的全关系。 常将常将 A A 记作记作 UA = (ai, aj) | ai, aj A。 14 恒等关系恒等关系 定义集合定义集合 A 上的上的恒等关系恒等关系为为 IA = (

14、a, a) | a A。 例例4 设设 A = a, b, c，则，则 UA = A A = (a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c) 是是 A 上的普遍关系。上的普遍关系。 IA = (a, a), (b, b), (c, c) 是是 A 上的恒等关系。上的恒等关系。 15 3. 关系的定义域和值域关系的定义域和值域 定义定义2-5 设设 是由是由 A 到到 B 的一个关系，的一个关系， 的的定义域定义域记作记作 D ， 的的值域值域记作记作 R ，分别定义为：，分别定义为： D = a |

15、a A 且存在且存在 b B，使得，使得 a b， R = b | b B 且存在且存在 a A，使得使得 a b。 显然有显然有 D A， R B。 此时，此时，A 称为关系称为关系 的的前域前域，B 称为关系称为关系 的的后域后域。 16 例例5 设设 A = 2, 3, 5，B = 2, 6, 7, 8, 9， 由由 A 到到 B 的关系的关系 定义为：定义为： 当且仅当当且仅当 a 整除整除 b 时，有时，有 a b。 于是于是 = (2, 2), (2, 6), (2, 8), (3, 6), (3, 9)， 的定义域的定义域 D = 2, 3，值域，值域 R = 2, 6, 8,

16、9。 17 练习练习2-1 1. 设设 A = 0, 1, 2，B = 0, 2, 4，由，由 A 到到 B 的关系的关系 = (a, b) | 数数 a 与与 b 的乘积的乘积 a b A B 则用列举法表示则用列举法表示 A B = = D = R = (0, 0), (0, 2), (0, 4) 0, 2 0, 1, 2 (1, 0), (1, 2) 0, 2, 4 (2, 0) 18 2. 设设 A = 1, 2, 3, 4, 5，B = 1, 2, 3，由，由 A 到到 B 的关系的关系 = (a, b) | a = b2 则用列举法表示则用列举法表示 = D = R = (1, 1

17、), (4, 2) 1, 4 1, 2 19 3. 设设 A = 0, 1, B = 1, 2， 则则 A B = ， B B = 。 4. #A = 2，#B = 3， 则则 #(A B) = _ #(2A B) = _ 由由 A 到到 B 不同的关系的个数是不同的关系的个数是 _ 。 (0, 1), (0, 2), (1, 1), (1, 2) (1, 1), (1, 2), (2, 1), (2, 2) 6 26 26 20 5. 设设 #A = 4， 则则 #(A A) = _ #(2A A) = _ A 上不同关系的个数是上不同关系的个数是 _ 6. 设设 #A = n， 则则 #(

18、A A) = _ #(2A A) = _ A 上不同关系的个数是上不同关系的个数是 _ 2 2n 2 2n 16 216 216 n2 21 2.2 关系的表示法关系的表示法 一、集合表示法一、集合表示法 用表示集合的列举法或描述法来表示关系。用表示集合的列举法或描述法来表示关系。 例例1 设设 A = 2, 3, 4, 8，B = 1, 5, 7，用描述法定义由，用描述法定义由 A 到到 B 的的 关系关系 = (a, b) | a b，试用列举法将，试用列举法将 表示出来。表示出来。 解解 = (2, 5), (2, 7),(3, 5), (3, 7), (4, 5), (4, 7) 例例

19、2 有王、张、李、何是某校的老师，该校有三门课程：语文、有王、张、李、何是某校的老师，该校有三门课程：语文、 数学和英语，已知王可以教语文和数学，张可以教语文和英语，数学和英语，已知王可以教语文和数学，张可以教语文和英语， 李可以教数学，何可以教英语。试将这些老师与课程之间的对李可以教数学，何可以教英语。试将这些老师与课程之间的对 应关系表示出来。应关系表示出来。 22 若记若记 A = 王，张，李，何王，张，李，何，B = 语文，数学，英语语文，数学，英语。那么。那么 这些老师与课程之间的对应关系就可以用由这些老师与课程之间的对应关系就可以用由 A 到到 B 的一个关的一个关 系系 中的序偶

20、来表示。中的序偶来表示。 = (王，语文王，语文)，(王，数学王，数学)，(张，语文张，语文)，(张，英语张，英语)，(李，李， 数学数学)，(何，英语何，英语) 注：注：用序偶的集合来表示关系有两个不足：用序偶的集合来表示关系有两个不足： 不能直观地看出其特点和性质不能直观地看出其特点和性质 给计算机的处理带来困难给计算机的处理带来困难 为此提出了关系矩阵和关系图的表示方法。为此提出了关系矩阵和关系图的表示方法。 23 二、矩阵表示法二、矩阵表示法 设设 A、B 都是有限集，都是有限集，A = a1, a2, , an，B = b1, b2, , bm， 由由 A 到到 B 的关系的关系 可

21、以用一个可以用一个 n m 的矩阵的矩阵 M 来表示，来表示，M 的的 第第 i 行第行第 j 列的元素列的元素 rij 取值如下：取值如下： 矩阵矩阵 M 称为称为 的的关系矩阵关系矩阵。 关系矩阵是一个关系矩阵是一个 0-1 矩阵，称为矩阵，称为布尔矩阵布尔矩阵。 例例1中由中由 A 到到 B 的关系的关系 可以可以 用一个用一个 4 3 的矩阵来表示。的矩阵来表示。 ji ji ij ba, ba, r 若若 若若 0 1 000 110 110 110 8 4 3 2 M 1 5 7 A = 2, 3, 4, 8，B = 1, 5, 7， = (2, 5), (2, 7),(3, 5)

22、, (3, 7), (4, 5), (4, 7) 24 例例3 设设 A = 1, 2, 3, 4，A 上的关系上的关系 = (x, y) | y 是是 x 的整数倍的整数倍， 则则 = (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4) 于是于是 可以用一个可以用一个 4 4 的矩阵表示如下。的矩阵表示如下。 1000 0100 1010 1111 4 3 2 1 M 1 2 3 4 25 三、关系图表示法三、关系图表示法 由于关系的元素是序偶，所以可用有向图来刻划关系，这种图由于关系的元素是序偶，所以可用有向图来刻划

23、关系，这种图 称为关系的称为关系的关系图关系图。 关系图由结点和边组成：关系图由结点和边组成： 用小圆圈代表元素，在图中称为结点，用小圆圈代表元素，在图中称为结点， 用从用从 a 到到 b 的有向单边表示的有向单边表示 (a, b)。 例例4 例例1中的中的 A = 2, 3, 4, 8, B = 1, 5, 7， = (2, 5), (2, 7),(3, 5), (3, 7), (4, 5), (4, 7)， 的关系图如右。的关系图如右。 26 例例5 例例3中的中的 A = 1, 2, 3, 4 ， = (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2,

24、 4), (3, 3), (4, 4) 的关系图如下。的关系图如下。 27 注：注： 用矩阵来表示关系，为计算机处理关系带来了极大的方便。用矩阵来表示关系，为计算机处理关系带来了极大的方便。 用关系图的方式表示关系，最富有直观性。用关系图的方式表示关系，最富有直观性。 对人来说，关系图是表示关系的很好的方法；对计算机来说，对人来说，关系图是表示关系的很好的方法；对计算机来说， 关系矩阵的表示方式是最好的。关系矩阵的表示方式是最好的。 表示表示(a, a)的单边，如例的单边，如例5的关系图中的关系图中(1, 1)等，被称为等，被称为自环自环。 在画关系图时，在画关系图时， n如果如果 A B，则

25、需要将，则需要将 A 和和 B 中的元素都画出来，如例中的元素都画出来，如例4的的 关系图；关系图； n如果如果 A = B，则只需画出，则只需画出 A 中的所有元素即可，如例中的所有元素即可，如例5的关的关 系图。系图。 28 练习练习2-2 0 2 4 2 1 0 M 001 011 111 1. 设设 A = 0, 1, 2，B = 0, 2, 4，A 到到 B 的关系的关系 = (0, 0), (0, 2), (0, 4), (1, 0), (1, 2), (2, 0) 试构造出试构造出 的关系矩阵。的关系矩阵。 29 2. 设设 A = 1, 2, 3, 4, 5, 6，A 上的关系

26、上的关系 1 = (i, j) | i 整除整除 j， 2 = (i, j) | i / j 是素数是素数 试画出试画出 1 和和 2 的关系图。的关系图。 1 的关系图的关系图 2 的关系图的关系图 30 2.3 关系的复合运算关系的复合运算 一、关系的并、交、补运算一、关系的并、交、补运算 关系是一种特殊的集合，因此可对它进行集合的所有基本运算关系是一种特殊的集合，因此可对它进行集合的所有基本运算 （并、交、差、补等）而产生新的集合。（并、交、差、补等）而产生新的集合。 例例1 设设 1 = (1, 2), (2, 4), (3, 3), 2 = (1, 3), (2, 4), (4, 2

27、), 则则 1 2 = (1, 2), (2, 4), (3, 3), (1, 3), (4, 2)， 1 2 = (2, 4)， 1 2 = (1, 2), (3, 3)。 若若 1 和和 2 都是由集合都是由集合 A 到到 B 的关系，则的关系，则 1 A B， 2 A B， 于是于是 1 2 A B， 1 2 A B， 1 2 A B。 因此因此 1 2， 1 2 和和 1 2 也都是由也都是由 A 到到 B 的关系。的关系。 31 若将若将 A B 看作是全集看作是全集 U，则，则 1 = (a, b) | (a, b) 1， 2 = (a, b) | (a, b) 2 也都是由也都是

28、由 A 到到 B 的关系。的关系。 例例2 设设 A = 2, 3，B = 4, 8, 9，这里，这里 A B = (2, 4), (2, 8), (2, 9), (3, 4), (3, 8), (3, 9). 设由设由 A 到到 B 的关系的关系 1 = (2, 4), (2, 8), 2 = (3, 9)，则，则 1 2 = (2, 4), (2, 8), (3, 9)， 1 2 = ， 1 2 = (2, 4), (2, 8)， 1 = (2, 9), (3, 4), (3, 8), (3, 9) 均是由均是由 A 到到 B 的关系。的关系。 32 定义定义2-6 设设 A、B 是两个集

29、合，是两个集合， 是由是由 A 到到 B 的关系，则由的关系，则由 B 到到 A 的关系的关系 (b, a) | (a, b) 称为称为关系关系 的逆关系的逆关系，也记为，也记为 - -1。 例例3 设设 A = 2, 3, 5，B = 4, 6, 10，定义由，定义由 A 到到 B 的关系的关系 ： 当且仅当当且仅当 a 整除整除 b 时，有时，有 a b，试求，试求 的逆关系。的逆关系。 解解 由由 的定义知的定义知 = (2, 4), (2, 6), (2, 10), (3, 6), (5, 10) 于是于是 1 = (4, 2), (6, 2), (10, 2), (6, 3), (1

30、0, 5). 二、求逆关系的运算二、求逆关系的运算 33 三、关系的复合运算三、关系的复合运算 1. 复合关系的定义复合关系的定义 定义定义2-7 设设A, B, C 是三个集合，是三个集合， 1 是由是由 A 到到 B 的关系，的关系， 2 是是 由由 B 到到 C 的关系，则的关系，则 1 和和 2 的复合关系的复合关系 1 2 (简记为简记为 1 2) 是一个由是一个由 A 到到 C 的关系，并且的关系，并且 1 2 = (a, c) | a A, c C, 且存在且存在 b B, 使得使得 a 1 b, b 2 c. 这种由这种由 1 和和 2 求复合关系求复合关系 1 2 的运算称为

31、的运算称为关系的复合运算关系的复合运算。 显然，（，（1）如果）如果 1 的值域和的值域和 2 的定义域的交集为空，则复合的定义域的交集为空，则复合 关系关系 1 2 是空关系。是空关系。 （2） 1 = 1 = 。 34 例例4 设设 1 是由是由 A = 1, 2, 3, 4 到到 B = 2, 3, 4 的关系，的关系， 2 是由是由 B 到到 C = 3, 5, 6 的关系，分别定义为：的关系，分别定义为： 1 = (a, b) | a + b = 6 = (2, 4), (3, 3), (4, 2) 2 = (b, c) | b 整除整除 c = (2, 6), (3, 3), (3

32、, 6) 于是复合关系于是复合关系 1 2 = (3, 3), (3, 6), (4, 6). 35 2. 关系复合运算的性质关系复合运算的性质 定理定理2-1 设设 是由集合是由集合 A 到到 B 的关系，则的关系，则 IA = IB = . 例例5 以例以例4中的关系中的关系 1 为例，为例， 1 = (2, 4), (3, 3), (4, 2) IA = (1, 1), (2, 2), (3, 3), (4, 4)，IB = (2, 2), (3, 3), (4, 4). 从关系图，可得从关系图，可得 IA 1 = 1, 1 IB = 1. A = 1, 2, 3, 4, B = 2,

33、3, 4 36 定理定理2-2 设设 1 是由是由 A 到到 B 的关系，的关系， 2 是由是由 B 到到 C 的关系，的关系， 3 是由是由 C 到到 D 的关系，则有的关系，则有 ( 1 2) 3 = 1 ( 2 3)。 例例6 设设 A = 1, 2, 3, 4, B = 2, 3, 4, C = 1, 2, 3, D = 4, 5, 6. A 到到 B 的关系的关系 1 = (2, 4), (2, 3), (4, 2) B 到到 C 的关系的关系 2 = (2, 1), (3, 2), (4, 3) C 到到 D 的关系的关系 3 = (2, 4), (1, 5), (2, 6), (

34、3, 6) 则则 A 到到 C 的关系的关系 1 2 = (2, 3), (2, 2), (4, 1) 因此因此 ( 1 2) 3 = (2, 6), (2, 4), (4, 5) 又又 B 到到 D 的关系的关系 2 3 = (2, 5), (3, 4), (3, 6), (4, 6) 因此因此 1 ( 2 3) = (2, 6), (2, 4), (4, 5) 所以所以 ( 1 2) 3 = 1 ( 2 3)。 37 一般地，若一般地，若 1 是一由是一由 A1 到到 A2 的关系，的关系， 2 是一由是一由 A2 到到 A3 的的 关系，关系， n 是一由是一由 An 到到 An+1 的

35、关系，则不加括号的表达式的关系，则不加括号的表达式 1 2 n 唯一地表示一由唯一地表示一由 A1 到到 An+1 的关系。在计算这一的关系。在计算这一 关系时，可以运用结合律将其中任意两个相邻的关系先结合。关系时，可以运用结合律将其中任意两个相邻的关系先结合。 特别，当特别，当 A1 = A2 = = An+1 = A， 1 = 2 = = n = 时，复时，复 合关系合关系 简记作简记作 n，它也是集合，它也是集合 A 上的一个关系，上的一个关系， 称为称为 的的 n 次幂次幂。 规定：规定： 0 = (a, a) | a A，即，即 0 = IA。 38 定理定理 设设 A, B, C,

36、 D 是四个集合，是四个集合， 1 是由是由 A 到到 B 的关系，的关系， 2 和和 3 都是由都是由 B 到到 C 的关系，的关系， 4 是由是由 C 到到 D 的关系，则的关系，则 (1) 1 ( 2 3) = ( 1 2) ( 1 3)。 (2) ( 2 3) 4 = ( 2 4) ( 3 4)。 (3) 1 ( 2 3) ( 1 2) ( 1 3)。 (4) ( 2 3) 4 ( 2 4) ( 3 4)。 注：注：(3) 和和 (4) 的反包含关系不一定成立。例如的反包含关系不一定成立。例如 设设 A = 1, 2, 3，B = 1, 2，C = 2, 3，D = 4，关系如下：，关

37、系如下： 1 = (2, 1), (2, 2)， 2 = (1, 2), (2, 3)， 3 = (1, 3), (2, 2)， 4 = (2, 4), (3, 4)。 39 3. 求复合关系的几种方法求复合关系的几种方法 （1）根据复合关系的定义求复合关系）根据复合关系的定义求复合关系 例例6中求复合关系采用的就是这种方法。中求复合关系采用的就是这种方法。 又如又如 下面的关系图给出了由集合下面的关系图给出了由集合 A 到到 B 的关系的关系 1 和由和由 B 到到 C 的关系的关系 2，则，则 1 2 = (2, 2), (2, 3), (3, 1) 40 （2）运用关系矩阵的运算求复合关

38、系）运用关系矩阵的运算求复合关系 布尔运算布尔运算 其加法和乘法运算定义如下其加法和乘法运算定义如下 0 + 0 = 0, 0 + 1 = 1 + 0 = 1 + 1 = 1 1 1 = 1, 0 1 = 1 0 = 0 0 = 0 例如例如 (1 0 0) + (0 1) + (1 1 1) + (0 0 0) + (1 1) = 1 注：注：在一个式子中当且仅当至少有一个乘积是形式在一个式子中当且仅当至少有一个乘积是形式1 1 1 时，乘积的和等于时，乘积的和等于1，否则为，否则为0。 41 关系矩阵的乘积关系矩阵的乘积 定义定义2-8 设设M1是一个是一个(i, j)通路（即第通路（即第

39、 i 行、第行、第 j 列交叉处的元列交叉处的元 素）为素）为rij(1)的的l m关系矩阵，关系矩阵，M2是一个是一个(i, j)通路为通路为rij(2)的的m n 关系矩阵，则关系矩阵，则M1和和M2的乘积，记为的乘积，记为M1 M2，是一个，是一个l n矩阵，矩阵， 其其(i, j)通路为通路为 在这里求其乘积时，其在这里求其乘积时，其运算法则与一般矩阵的乘法是相同的， 但但其中的加法运算和乘法运算应改为布尔加和布尔乘其中的加法运算和乘法运算应改为布尔加和布尔乘。 注：注：M1的列数必须等于的列数必须等于M2的行数，这样的行数，这样M1 M2才有意义。才有意义。 ).,;.,()( )(

40、)( njlirrr m k kjikij 2121 1 21 42 001 010 101 001 21 MM 则则 例例7 设设 M1 和和 M2 是两个关系矩阵是两个关系矩阵 001 010 100 001 1 M 101 010 001 2 M 43 例例8 设有集合设有集合 A = 1, 2, 3, 4, B = 2, 3,4, C = 1, 2, 3， A 到到 B 的关系的关系 1 = (1, 2), (2, 4), (3, 3), (4, 2) B 到到 C 的关系的关系 2 = (2, 1), (3, 2), (4, 1), (4, 3) 则则 1 2 = (1, 1), (

41、2, 1), (2, 3), (3, 2), (4, 1) 1 2 3 001 010 101 001 4 3 2 1 21 M 与例与例7比较得比较得 2121 MMM 101 010 001 4 3 2 2 M 1 2 3 001 010 100 001 4 3 2 1 1 M 2 3 4 44 复合关系的关系矩阵复合关系的关系矩阵 定理定理2-3 设设 A、B、C 均是有限集，均是有限集， 1 是一由是一由 A 到到 B 的关系，的关系， 2 是一由是一由 B 到到 C 的关系，它们的关系矩阵分别为的关系，它们的关系矩阵分别为 和和 ， 则复合关系则复合关系 1 2 的关系矩阵的关系矩阵

42、 可以推广到有限个关系的情形。（可以推广到有限个关系的情形。（P36：定理：定理2-4，定理，定理2-5） 1 M 2 M 21 21 MMM 问题：问题： 设设 A、B均是有限集，均是有限集， 1、 2 都是由都是由 A 到到 B 的关系，它们的关的关系，它们的关 系矩阵分别为系矩阵分别为 和和 ，则下列关系的关系矩阵如何？，则下列关系的关系矩阵如何？ 1 2， 1 2， 1 ， 1 - - 2 ， 1- -1。 1 M 2 M 45 例例9 设设 A = a, b, c, d，A 上的关系上的关系 = (a, b), (b, a), (c, c), (c, d), (b, c) 试求试求

43、2 和和 3。 解解 作出的关系矩阵作出的关系矩阵 M 如右。如右。 根据定理根据定理2-3， a b c d 0000 1100 0101 0010 d c b a M 0000 1100 1110 0101 0000 1100 0101 0010 0000 1100 0101 0010 2 MMM 因此因此 2 =(a, a), (a, c), (b, b), (b, c), (b, d), (c, c), (c, d). 46 又又 3 = 2，所以，所以 0000 1100 1101 1110 0000 1100 1110 0101 0000 1100 0101 0010 23 MMM

44、 0000 1100 1110 0101 , 0000 1100 0101 0010 2 MM 因此因此 3 =(a, b), (a, c), (a, d), (b, a), (b, c), (b, d), (c, c), (c, d). 47 （3）利用关系图求复合关系）利用关系图求复合关系 n 设设 是有限集是有限集 A 上的关系，则复合关系上的关系，则复合关系 2 也是也是 A 上的关系。上的关系。 由复合关系的定义，对任意的由复合关系的定义，对任意的 ai, aj A，当且仅当存在，当且仅当存在 ak A， 使得使得 ai ak，ak aj 时，有时，有 ai 2 aj。 反映在关系图

45、上，这意味着，当且仅当在反映在关系图上，这意味着，当且仅当在 的关系图中存在有的关系图中存在有 某一结点某一结点 ak，使得有边由，使得有边由 ai 指向指向 ak，且有边由，且有边由 ak 指向指向 aj 时，时， 在在 2 的关系图中有边从的关系图中有边从 ai 指向指向 aj。 48 根据根据 的关系图构造出的关系图构造出 n 的关系图：的关系图： 对于对于 的关系图中的每一结点的关系图中的每一结点 ai，找出从，找出从 ai 经过经过长为长为 n 的路的路 能够到达的所有结点，这些结点在能够到达的所有结点，这些结点在 n 的关系图中，边必须由的关系图中，边必须由 ai 指向它们。指向它

46、们。 类似地，对于任意正整数类似地，对于任意正整数 n，当且仅当在，当且仅当在 的关系图中存在的关系图中存在 n 1 个结点个结点 ，使得有边由，使得有边由 指向指向 ，由，由 指向指向 ，由，由 指向指向 aj 时，在时，在 n 的关系图中，有的关系图中，有 边由结点边由结点 ai 指向指向 aj。 121- -n kkk aaa, i a 1 k a 1 k a 2 k a 1- -n k a 对于图中结点对于图中结点 ai 和和 aj，若存在，若存在 n 1 个结点个结点 ， 使得使得 ai ， ， aj 时，则说从结点时，则说从结点 ai 到到 aj 有一条有一条长为长为 n 的路的路

47、（n 0）。）。 121- -n kkk aaa, 1 k a 1 k a 2 k a 1- -n k a 例例10 试利用构造试利用构造 2 和和 3 的关系图的方法求例的关系图的方法求例9中的中的 2 和和 3。 例中例中 = (a, b), (b, a), (c, c), (c, d), (b, c) (4) 根据根据 2 和和 3 的关系图的关系图 直接写出直接写出 2 和和 3 中的序中的序 偶。偶。 解解 (1) 先先 作出作出 的关系的关系 图。图。 (2) 构造构造 2 的关系图。的关系图。 在在 的关的关 系图中寻系图中寻 找长为找长为 2 的路。的路。 (3) 构造构造 3

48、 的关系图。的关系图。 在在 的关的关 系图中寻系图中寻 找长为找长为 3 的路。的路。 能否利用 2 的关系图 来构造 3 的关系图？ 50 1. 设设 A = 1, 2, 3，A上的关系上的关系 1 = (x, y) | x y， 2 = (x, y) | x y， 用列举法表示下列关系。用列举法表示下列关系。 1 = 2 = 11 = 1 = A A 1 = 1 2 = 练习练习2-3 (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2) (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3 (2, 1), (

49、3, 1), (1, 2), (3, 2), (1, 3), (2, 3 (1, 1), (2, 2), (3, 3) (2, 1), (3, 1), (3, 2) 51 2. 设设 A = 0, 1, 2, 3，A 上的关系上的关系 1 = (0, 1), (1, 2), (2, 3), (2, 1), (0, 0)， 2 = (2, 0), (3, 1)， 则复合关系则复合关系 1 2 = 2 1 = 12 = 1 2 1 = (1, 0), (2, 1) (2, 1), (2, 0), (3, 2) (0, 2), (1, 3), (1, 1), (2, 2), (0, 1), (0,

50、0) (1, 1), (1, 0), (2, 2) 52 3. 设设 1, 2 是集合是集合 A 上的任意的关系，则上的任意的关系，则 ( 1 1 2 2)-1 -1 = 2-1-1 1 1-1-1。 。 证明：证明：任取任取 (x, y) ( 1 2)-1 -1，则 ，则 (y, x) 1 2。 由复合关系的定义知存在由复合关系的定义知存在 z A，使得，使得 (y, z) 1 且且 (z, x) 2。 故有故有 (z, y) 1-1 -1 且 且 (x, z) 2-1 -1。 。 于是于是 (x, y) 2-1 -1 1-1-1。 。 此即证得此即证得 ( 1 2)-1 -1 2-1-1

51、1-1-1。 。 同理可证同理可证 2-1 -1 1-1-1 ( 1 2)-1-1。 。 所以所以 ( 1 2)-1 -1 = 2-1-1 1-1-1。 。 53 4. 下图给出了集合下图给出了集合 A = 1, 2, 3, 4, 5, 6 上的关系上的关系 的关系图，的关系图， 试画出关系试画出关系 5 和和 8 的关系图。的关系图。 54 一、集合一、集合 A 上关系的性质上关系的性质 定义定义2-9 设设 是集合是集合 A 上的关系，上的关系， 若对于所有的若对于所有的 a A，均有，均有 a a，则称，则称 在在 A 上是上是自反自反的。的。 否则否则 是是非自反非自反的。的。 若对于

52、所有的若对于所有的 a A，均有，均有 a a，则称，则称 在在 A 上是上是反自反反自反的。的。 对于所有的对于所有的 a, b A，若每当有，若每当有 a b 就必有就必有 b a，则称，则称 在在 A 上是上是对称对称的。否则的。否则 是是非对称非对称的。的。 对于所有的对于所有的 a, b A，若每当有，若每当有 a b 和和 b a 就必有就必有 a = b，则，则 称称 在在 A 上是上是反对称反对称的。的。 对于所有的对于所有的 a, b, c A，若每当有，若每当有 a b 和和 b c 就必有就必有 a c， 则称则称 在在 A 上是上是可传递可传递的。否则的。否则 是是不可

53、传递不可传递的。的。 2.4 关系的性质与闭包关系的性质与闭包 55 例例1 设设 A = 0, 1, 2, 3，判断下列关系的，判断下列关系的 （1）自反与反自反）自反与反自反 1 = (0, 0), (1, 1), (2, 2), (3, 3) 2 = (0, 0), (1, 2), (3, 3), (2, 2), (1, 1), (2, 3) 3 = (2, 1), (0, 0), (3, 3) 4 = (0, 1), (2, 3), (1, 2) 自反自反 自反自反 非自反非自反 反自反反自反 注：注：（1）A 上的恒等关系是自反关系，但自反关系却不一定上的恒等关系是自反关系，但自反关

54、系却不一定 是恒等关系（是恒等关系（如如 2）。）。 （2）反自反的关系一定是非自反的关系。）反自反的关系一定是非自反的关系。 56 （2）对称与反对称）对称与反对称 5 = (1, 1), (1, 2), (2, 1), (2, 3), (3, 2) 6 = (1, 2), (1, 1), (0, 2), (3, 1) 7 = (1, 2), (2, 2), (2, 3), (3, 2) 8 = (0, 0), (2, 2), (1, 1) 对称，非反对称对称，非反对称 非对称，反对称非对称，反对称 非对称，非反对称非对称，非反对称 对称，反对称对称，反对称 注：注：（1）若）若 是是 A

55、上的反对称关系上的反对称关系，则由定义知，则由定义知，在在 中，中， (a, b) 与与 (b, a) 至多有一个出现，其中至多有一个出现，其中 a b。 （2）A 上的恒等关系既是对称的也是反对称的。上的恒等关系既是对称的也是反对称的。 57 （3）可传递与不可传递）可传递与不可传递 9 = (0, 0), (0, 2), (2, 3), (0, 3) 10 = (1, 1), (1, 2), (2, 1), (2, 3) 11 = (1, 2), (3, 0), (3, 2) 可传递可传递 不可传递不可传递 可传递可传递 注：注：A 上的恒等关系是可传递关系。上的恒等关系是可传递关系。 5

56、8 例例2 设设 A = 1, 2, 3, 4, 5，A 上的关系上的关系 = (a, b) | a b 是偶数是偶数， 则则 = (1, 1), (1, 3), (1, 5), (2, 2), (2, 4), (3, 3), (3, 1), (3, 5), (4, 2), (4, 4), (5, 1), (5, 3), (5, 5) 于是于是 对于任意的对于任意的 a, b, c A，若，若 a b = 2m，b c = 2n， 则则 a c = (a b) + (b c) = 2(m + n)也是偶数，也是偶数， 因此因此 是可传递的是可传递的。 自反自反； 对称对称； 不是反对称不是反对

57、称。 二、集合二、集合 A 上关系性质的判断方法上关系性质的判断方法 1. 集合运算的方法集合运算的方法 定理定理 设设 为为 A 上的关系，则上的关系，则 （1） 在在 A 上上自反自反 当且仅当当且仅当 IA （2） 在在 A 上上反自反反自反 当且仅当当且仅当 IA = （3） 在在 A 上上对称对称 当且仅当当且仅当 = - -1 （4） 在在 A 上上反对称反对称 当且仅当当且仅当 -1 -1 IA （5） 在在 A 上上传递传递 当且仅当当且仅当 （1） 在在 A 上上自反自反当且仅当当且仅当 IA 证证 （1） 必要性必要性 任取任取 (x, y) IA，则，则 x, y A 且

58、且 x = y。 由于由于 在在 A 上自反，所以上自反，所以 (x, y) 。 从而证明了从而证明了 IA 。 充分性充分性 任取任取 x A，由于，由于 (x, x) IA 且且 IA ，故，故 (x, x) 。 因此因此 在在 A 上是自反的。上是自反的。 61 （2） 在在 A 上上反自反反自反当且仅当当且仅当 IA = 证证 （2） 必要性必要性（用反证法）（用反证法） 假设假设 IA ，则必存在，则必存在 (x, y) IA， 故故 (x, y) 且且 (x, y) IA。 由于由于 IA 是是 A 上的恒等关系，故上的恒等关系，故 x, y A 且且 x = y， 从而从而 (x

59、, x) = (x, y) 。 这与这与 在在 A 上是反自反的相矛盾。上是反自反的相矛盾。 充分性充分性 任取任取 x A，由于，由于 (x, x) IA，且，且 IA = ，故，故 (x, x) 。 因此因此 在在 A 上是反自反的。上是反自反的。 62 （3） 在在 A 上上对称对称当且仅当当且仅当 = - -1 证证 （3） 必要性必要性 任取任取 (x, y) ，由于，由于 在在 A 上对称，所以上对称，所以 (y, x) 。 于是于是 (x, y) - -1 1 。 此即证得此即证得 - -1。 同理可证同理可证 - -1 。 从而证明了从而证明了 = - -1。 充分性充分性 任

60、取任取 x, y A，若，若 (x, y) ，则，则 (y, x) - -1。 由于由于 = - -1，所以，所以 (y, x) 。 因此因此 在在 A 上是对称的。上是对称的。 63 （4） 在在 A 上上反对称反对称当且仅当当且仅当 -1 -1 IA 证证 （4） 必要性必要性 任取任取 (x, y) - -1，则，则 (x, y) 且且 (x, y) -1 -1， ， 即即 (x, y) 且且 (y, x) 。 由于由于 在在 A 上反对称，故上反对称，故 x = y。 于是于是 (x, y) IA。 从而证明了从而证明了 -1 -1 IA。 。 充分性充分性 任取任取 x, y A，若