离散数学第二章

1、11 1第二章第二章 关关 系系 本本章讨论的关系（主要是二元关系），它仍然是一种章讨论的关系（主要是二元关系），它仍然是一种集合，但它是比第一章更为复杂的集合。它的元素是有序集合，但它是比第一章更为复杂的集合。它的元素是有序二元组的形式，这些有序二元组中的两个元素来自于两个二元组的形式，这些有序二元组中的两个元素来自于两个不同或者相同的集合。因此，关系是建立在其它集合基础不同或者相同的集合。因此，关系是建立在其它集合基础之上的集合。关系中的有序二元组反映了不同集合中元素之上的集合。关系中的有序二元组反映了不同集合中元素与元素之间的关系，或者同一集合中元素之间的关系。本与元素之间的关系，或者同

2、一集合中元素之间的关系。本章讨论这些关系的表示方法、关系的运算以及关系的性质，章讨论这些关系的表示方法、关系的运算以及关系的性质，最后讨论集合最后讨论集合A A上几类特殊的关系。上几类特殊的关系。 主要内容如下：主要内容如下：2.1 2.1 笛卡尔积与关系笛卡尔积与关系 2.5 2.5 等价关系等价关系2.2 2.2 关系的表示关系的表示 2.6 2.6 相容关系相容关系2.3 2.3 关系的复合运算关系的复合运算 2.7 2.7 偏序关系偏序关系2.4 2.4 关系的性质与闭包关系的性质与闭包22 2有序有序n n元组与元组与n n个元素的集合，是不相同的。个元素的集合，是不相同的。例如例如

3、 但但 ,cdbacdabdcba),(),(),(cdbacdabdcba2.1 2.1 笛卡尔积与关系笛卡尔积与关系 一、有序一、有序n n元组与笛卡尔积元组与笛卡尔积1. 1. 有序有序n n元组元组定义定义2-1 由由n n个具有给定次序的个体个具有给定次序的个体 组成的组成的序列称为有序序列称为有序n n元组，记作（元组，记作（ ）。）。naaa,21naaa,2133 3例如例如 4,4,3,2=4,3,24,4,3,2=4,3,2 但但 (4,4,3,2)(4,3,2)(4,4,3,2)(4,3,2) 定义定义2-22-2 设设 和和 是两是两个有序个有序n元组，若元组，若 ,则

4、称这两则称这两个有序个有序n元组相等，并记作元组相等，并记作 ),(21naaa),(21nbbbnnbababa,2211),(),(2121nnbbbaaa当当n=2n=2时，有序二元组时，有序二元组(a,b)(a,b)又称为序偶。又称为序偶。44 42. 2. 笛卡尔积笛卡尔积(1)(1)笛卡尔积的定义笛卡尔积的定义定义定义2-3 设设A,BA,B为任意集合，为任意集合， A A 和和 B B 的笛卡尔积用的笛卡尔积用 表表示，定义为示，定义为BA,| ),(BbAabaBA例例1 1 设设 则则 但但,1 , 0cbaBA), 1 (), 1 (), 1 (), 0(), 0(), 0

5、(cbacbaBA)1 ,(),1 ,(),1 ,(),0 ,(),0 ,(),0 ,(cbacbaAB当当 或者或者 时，时， ，即，即 。AB BAABABBA笛卡尔积笛卡尔积 我们常记作我们常记作AA2A,| ),(AaAaaaAjiji2 例例2 2 设设 则则 1 ,0A),(),(),(),(110110002AAA55 5（2 2）笛卡尔积的基数）笛卡尔积的基数当当 A 和和 B 均 是 有 限 集 时 ，均 是 有 限 集 时 ， 必 为 有 限 集 ， 而 且必 为 有 限 集 ， 而 且当其中有一个是无限集时，必为无限集。当其中有一个是无限集时，必为无限集。（3 3）与笛卡

6、尔积有关的一些恒等式）与笛卡尔积有关的一些恒等式设设A、B、C是任意的集合，则有是任意的集合，则有 1） 2） 3） 4） )()()(CABACBA)()()(ACABACB)()()(CABACBA)()()(ACABACBBABABA#)(#66 6以第一个等式以第一个等式 为例，给出其证明。为例，给出其证明。)()()(CABACBA证明证明 设设 ， )(),(CBAyx则则 ，且，且 , ,AxCBy因此因此 或或 。 ),(ByAx),(CyAx于是于是 或或 ， BAyx),(CAyx),(即即 ， )()(),(CABAyx故故 。 )()()(CABACBA即即 ，且（，且

7、（ 或或 ) )，AxCy By 77 7反之，设反之，设 ， )()(),(CABAyx则则 或或 ， BAyx),(CAyx),(于是于是( ( 且且 ）或）或( ( 且且 ），）， AxByAxCy即即 且（且（ 或或 ）, , AxByCy即即 且且 ，因此，因此 , ,AxCBy)(),(CBAyx故故 。 )()()(CBACABA由上证得由上证得)()()(CABACBA88 8BABA 二、关系二、关系1. 1. 关系的定义关系的定义定义定义2-4 笛笛卡尔积卡尔积 的任意一个子集的任意一个子集 称为称为是由是由A到到B的一个二元关系，当的一个二元关系，当 时，称时，称 是是A

8、上的二元关系上的二元关系。 99 9例例3 设设A=a,b，B=2,5,8 则则 )8 ,(),5 ,(),2 ,(),8 ,(),5 ,(),2 ,(bbbaaaBA令令 )2 ,(),8 ,(),2 ,(1baa)5 ,(),2 ,(),5 ,(2bba)2 ,(3a因为因为 ， ， 。BA1BA2BA3所以，所以， , 和和 均是由均是由A到到B的关系。的关系。123又又 ), 8(), 5(), 2(), 8(), 5(), 2(bbbaaaAB令令 ), 2(), 2(4ba), 8(), 8(), 5(5baa因为因为 , 。AB4AB5所以所以 和和 均是由均是由 B 到到 A

9、的关系。的关系。45101010对于对于 ,)8 , 8 (),5 , 8 (),2 , 8 (),8 , 5 (),5 , 5 (),2 , 5 (),8 , 2 (),5 , 2 (),2 , 2(BB,852B令令 ),(),(),(2825226)5 , 2(),8 , 2(),2 , 5(),5 , 8(7因为因为 ， . . BB6BB751a所以所以 和和 均是集合均是集合B上的关系。上的关系。若若 ，则称，则称a与与b有关系有关系 ，又记作，又记作 。 若若 ，则称，则称a与与b没有关系没有关系 ，又记作，又记作 。例如例如 在例在例3中中 ， ，但，但 67),(baba),

10、(baba81a21a111111 全域关系（或普遍关系）全域关系（或普遍关系） 因为因为 , , 。 所以所以 是一个由是一个由 到到 的关系。的关系。 是是 上的一个关系。上的一个关系。 常将常将 记作记作 BABAAAAAAA,| ),(AaaaaUjijiAAAABAAB2. 2. 几种特殊的关系几种特殊的关系 空关系空关系 对任意集合对任意集合 . .所以所以 是由是由 到到 的关系，的关系， 也是也是 上的关系，称为空关系。上的关系，称为空关系。 AABABA,ABA121212 恒等关系恒等关系定义集合定义集合 上的恒等关系上的恒等关系| ),(AaaaIAA例例4 4 设设 ,

11、cbaA 则下面集合则下面集合 AAUA),(),(),(cabaaa),(),(),(cbbbab 是是 上的恒等关系。上的恒等关系。 ),(),(),(ccbbaaIAA),(),(),(ccbcac是是 上的普遍关系。上的普遍关系。A131313 3. 3. 关系的定义域和值域关系的定义域和值域 定义定义2-5 设设 是由是由 到到 的一个关系，的一个关系， 的的定义域定义域记作记作 ， 的的值域值域记作记作 ，分别定义为：，分别定义为：ABRD,|baBbAaaD使得且存在 ,|baAaBbbR使得且存在 显然有显然有 BRAD,例例5 5 设设 。 9 , 8 , 7 , 6 , 2

12、,5 , 3 , 2BA 由由 到到 的关系的关系 定义为：当且仅当定义为：当且仅当a a整除整除b b时，时，有有 。ABba于是于是 )9 , 3(),6 , 3(),8 , 2(),6 , 2(),2 , 2( 的定义域的定义域 ，值域，值域3 , 2D9 , 8 , 6 , 2RAB14141420,),4 , 0(),2 , 0(),0 , 0(210,420,)2 , 4(),1 , 1 (4 , 13 , 2 , 1B5 , 4 , 3 , 2 , 1A2.2.设设 ， ，由，由 到到 的关系的关系则用列举法表示则用列举法表示 AB| ),(2babaDR2 , 1练习练习2-1

13、2-11.1.设设 ，由，由 到到 的关系的关系则用列举法表示则用列举法表示 4 , 2 , 0,2 , 1 , 0BA| ),(BAabbaBADRAB),2 , 1 (),0 , 1 ()0 , 2(151515)2 , 1 (),1 , 1 (),2 , 0(),1 , 0(3. 3. 设设 , , 。则则 ,2110BA BA BB)2 , 2(),1 , 2(),2 , 1 (),1 , 1 (624. ,4. ,则则 _ _ _ _ 由由 到到 不同的关系的个数是不同的关系的个数是 _ _ 2#A3#B)(#BA)2(#BAAB626161616165. 5. 设设 则则 _ _

14、_ A上不同关系的个数是上不同关系的个数是 _ 4A#)(#AA)(#AA21621622n6. 6. 设设则则 _ _ _ A上不同关系的个数是上不同关系的个数是 _ _ nA #)(#AA)(#AA2)(22n)(22n1717172.2 2.2 关系的表示关系的表示 一、集合表示法一、集合表示法用用表示集合的列举法或描述法来表示关系表示集合的列举法或描述法来表示关系。,751B 例例1 1 设设 , , , , 用描述用描述法定义由法定义由A A到到B B的关系的关系 ，试，试用列举法将用列举法将 表示出来。表示出来。 ,8432A| ),(baba解解 ),(),(7252),(),(

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

16、王王,数学数学),(张张,语文语文),(张张,英语英语),(李李,数数 学学),(何何,英语英语)191919二、矩阵表示法二、矩阵表示法 ijrM 定义定义2-6 设设 A A 、B B 都是有限集，都是有限集， , , ，由，由A A到到B B的关系的关系 可以用一个可以用一个 的矩阵的矩阵 来表示，来表示， 的第的第i i行第行第j j列的元素列的元素 取值如下：取值如下：矩阵矩阵 称为称为 的关系矩阵。的关系矩阵。 ,naaaA21,21mbbbBmnMjijiijbabar若若01M例例1 1中由中由A A到到B B的关系的关系 可以用可以用一个一个 的矩阵来表示。的矩阵来表示。34

17、0001101101108432M 1 5 7 1 5 7202020例例3 3 设设 ，A上的关系上的关系解解 ,4321A| ),(的整数倍是xyyx),(),(),(),(),(),(),(),(4433422241312111则则 可以用一个可以用一个 的矩阵来表示。的矩阵来表示。 4410000100101011114321M 1 2 3 4212121三、关系图表示法三、关系图表示法关系图由结点和边组成关系图由结点和边组成 例如例如 例例1 1中的中的 ， , ,8 , 4 , 3 , 2A,751B),(),(),(),(),(),(745473537252则则的关系图如下的关系

18、图如下AB222222例如例如 例例3 3中的中的 ，,4321A),(),(),(),(),(),(),(),(4433422241312111 的关系图如下：的关系图如下： 232323,210A,420B),(),(),(),(),(),(022101402000练习练习2.22.21.1. 设设 ， ，A A到到B B的关系的关系 试构造出试构造出 的关系矩阵的关系矩阵 0 2 4 210M001011111242424122. 2. 设设 ，A A上的关系上的关系 试画出试画出 和和 的关系图。的关系图。 ,654321A| ),(jiji整除1| ),(是素数jiji2252525

19、 2.3 2.3 关系的复合运算关系的复合运算 一、关系的并、交、补运算一、关系的并、交、补运算例例1 1 设设 ， ),(),(),(3342211),(),(),(2442312则则),(),(),(),(),(243133422121),( 4221),(),(332121若若 和和 都是由集合都是由集合 A A 到到 B B 的关系，的关系，则则 ， 。于是于是 ， ，因此因此 ， 和和 也都是由也都是由 A A 到到 B B 的关系。的关系。12BA1BA2BA21BA21BA21212121262626若将若将 看作是全集看作是全集U U，则，则也都是由也都是由A A到到B B的关

20、系。的关系。BA),( | ),(11baba),( | ),(22baba例例2 2 设设 ，, 32A,984B这里这里 . . ),(),(),(),(),(),(938343928242 BA设由设由A A到到B B的关系的关系 , , ),(),(82421),( 932则则 ； ； ),(),(),(9382422121),(),(824221),(),(),(),(938343921均是由均是由A A到到B B的关系。的关系。 272727 二、求逆关系的运算二、求逆关系的运算 定义定义2-7 设设 A A 、 B B 是任意集合，是任意集合， 是由是由 A A 到到 B B 的

21、关系，的关系，定义由定义由 B B 到到 A A 的关系的关系称称 为关系为关系 的逆关系。的逆关系。 ),( | ),(baab解解 由由 的定义知的定义知),(),(),(1026242于是于是 ),(),(),(),(),(510362102624),( 63),( 105 例例3 3 设设 ， ， 定义由定义由A A到到B B的关的关系系 ：当且仅当：当且仅当 a a 整除整除 b b 时，有时，有 ，试求，试求 的逆关系的逆关系 。 ,532A,1064Bba282828三、关系的复合运算三、关系的复合运算1. 1. 复合关系的定义复合关系的定义21 定义定义2-8 设设 是由是由A

22、 A到到B B的关系，的关系， 是由是由B B到到C C的的关系，则关系，则 和和 的复合关系是一个由的复合关系是一个由A A到到C C的关系，的关系，用用 表示，定义为：当且仅当存在元素表示，定义为：当且仅当存在元素 ，使得使得 ， 时，有时，有 。 这种由这种由 和和 求复合关系求复合关系 的运算称为的运算称为关系的复合运算。关系的复合运算。 12Bbba1cb2ca)(21122112292929 例例4 4 设设 是由是由 到到 的关系。的关系。 是由是由 B B 到到 的关系。的关系。分别定义为：分别定义为：1 ,4321A,432B2,653C),(),(),(| ),(24334

23、261baba),(),(),(| ),(6333622cbcb整除于是复合关系于是复合关系 ),(),(),(646333213030302. 2. 关系复合运算的性质关系复合运算的性质定理定理2-12-1 设设 是由集合是由集合A A到到B B的关系，则的关系，则 BAII1例例5 5 以例以例4 4中的关系中的关系 为例，为例， ),(),(),(243342111AI11BI),(),(),(),(44332211AI),(),(),(443322BI ,从关系图，可得从关系图，可得 ,313131 定理定理2-22-2 设设 是由是由A A到到B B的关系，的关系， 是由是由B B到

24、到C C的关的关系，系， 是由是由C C到到D D的关系，则有的关系，则有 123)()(321321 例例6 6 设设 ， ， , ., . A A到到B B的关系的关系 B B到到C C的关系的关系 C C到到D D的关系的关系 ,4321A,432B,321C,654D),(),(),(2432421),(),(),(3423122),(),(),(),(636251423则则A A到到C C的关系的关系 ),(),(),(14223221因此因此),(),(),()(544262321),(),(),(),(6463435232因此因此),(),(),()(544262321所以所以)

25、()(321321323232一般地，若一般地，若 是一由是一由 到到 的关系，的关系， 是由是由 到到 的关系，的关系， 是一由是一由 到到 的关系，则不的关系，则不加括号的表达加括号的表达式式 ， 唯一地表示一由唯一地表示一由 到到 的关系，在计算这一关系时，可以运用结合律的关系，在计算这一关系时，可以运用结合律将其中任意两个相邻的关系先结合。将其中任意两个相邻的关系先结合。特别特别, ,当当 ， 时，复合关系时，复合关系 简记作简记作 ，它也是集，它也是集 A A 上的一个关系。上的一个关系。11A2A23A2AnnA1nAn211A1nAAAAAn121n21n333333 3. 3.

26、 求复合关系的几种方法求复合关系的几种方法（1 1）根据复合关系的定义求复合关系）根据复合关系的定义求复合关系 例例6 6中求复合关系采用的就是这种方法。中求复合关系采用的就是这种方法。 12又例如又例如 下面的关系图给出了从集合下面的关系图给出了从集合A A到到B B的关系的关系 和从和从B B到到C C的关系的关系),(),(),(13322221343434（2 2）运用关系矩阵的运算求复合关系）运用关系矩阵的运算求复合关系布尔运算布尔运算其加法和乘法运算定义如下其加法和乘法运算定义如下00011101101110000110 , ,例如例如 11100011110001)()()()(

27、)(353535 关系矩阵的乘积关系矩阵的乘积 对两个关系矩阵求其乘积时，其运算法则与一般对两个关系矩阵求其乘积时，其运算法则与一般矩阵的乘法是相同的，但其中的加法运算和乘法运矩阵的乘法是相同的，但其中的加法运算和乘法运算应改为布尔加和布尔乘。算应改为布尔加和布尔乘。 00101010100121MM则则例例7 7 设设 和和 是两个关系矩阵是两个关系矩阵0010101000011M1010100012M1M2M363636 复合关系的关系矩阵复合关系的关系矩阵 定理定理2-32-3 设设A A、B B、C C均是有限集，均是有限集， 是一由是一由A A到到B B的关系的关系, , 是一由是一

28、由B B到到C C的关系，它们的关系的关系，它们的关系矩阵分别为矩阵分别为 和和 ，则复合关系，则复合关系 的的关系矩阵关系矩阵 121M2M212121MMM373737例例8 8 设有集合设有集合 ， ， A A到到B B的关系的关系 B B到到C C的关系的关系 则则,4321A,432B3 , 2 , 1C),(),(),(),(341423122),(),(),(),(243342211),(),(),(),(),(1423321211212 3 4 1 2 3 1 2 300101010000143211M1010100014322M001010101001432121M与例与例7

29、 7比较得比较得 2121MMM383838 例例9 9 设设 ，A A上的关系上的关系 试求试求 和和 。,dcbaA ),(),(),(),(),(cbdcccabba23 解解 作出的关系矩阵作出的关系矩阵 a b c da b c d0000110001010010dcbaM0000110011100101000011000101001000001100010100102MMM因此因此),(),(),(),(),(),(),(2dcccdbcbbbcaaa根据定理根据定理2-32-3393939又又 ，所以，所以2300001100110111100000110011100101000

30、011000101001023MMM因此因此),(),(),(),(),(),(),(),(3dcccdbcbabdacaba404040（3 3）利用关系图求复合关系）利用关系图求复合关系n 设设 是有限集是有限集A A上的关系，则复合关系上的关系，则复合关系 也是也是A A上的关上的关系，由复合关系的定义，对于任意的系，由复合关系的定义，对于任意的 ，当且仅，当且仅当当 存在，使得存在，使得 ， 时，有时，有 。2Aaaji,Aakkiaajkaajiaa2 反映在关系图上，这意味着，当且仅当在反映在关系图上，这意味着，当且仅当在 的关系图中有的关系图中有某一结点某一结点 存在，使得有边由

31、存在，使得有边由 指向指向 ，且有边由，且有边由 指指向向 时，在时，在 的关系图中有边从的关系图中有边从 指向指向 。 kaiakaka2iajajajakaiajaia2414141 类似地，对于任意正整数类似地，对于任意正整数n n，当且仅当在，当且仅当在 的的关系图中存在关系图中存在n-1n-1个结点个结点 , ,使得有使得有边由边由 指向指向 , ,由由 指向指向 ，由由 指向指向 时，在时，在 的关系图中，有边由结点的关系图中，有边由结点 指向指向 。121nkkkaaa,ia1ka1ka2ka1nkajaniaja根据根据 的关系图构造出的关系图构造出 的关系图：的关系图： n

32、对于对于 的关系图中的每一结点的关系图中的每一结点 ，找出从，找出从 经过长为经过长为n n的路能够到达的结点，这些结点在的路能够到达的结点，这些结点在 的关系图中，边必须由的关系图中，边必须由 指向它们。指向它们。iaiania424242例例1010 试利用构造试利用构造 和和 的关系图的方法求例的关系图的方法求例9 9中的中的 和和 。例中例中2323),(),(),(),(),(cbdcccabba（4 4）根据）根据 和和 的关的关系图直接写出系图直接写出 和和 中的序偶中的序偶. .2323解解（1 1）先）先作出作出 的关系图的关系图（2 2）构造）构造 的关系图。的关系图。在在

33、 的关的关系图中寻系图中寻找长为找长为2 2的的路。路。 2（3 3）构造）构造 的关系图。的关系图。在在 的关的关系图中寻系图中寻找长为找长为3 3的的路路. .3434343)3 , 3(),3 , 2(),2 , 2(),3 , 1 (),2 , 1 (),1 , 1 (练习练习2-32-31.1. 设设 ，A A上的关系上的关系则则用列举法表示用列举法表示 3 , 2 , 1A| ),(yxyx1| ),(yxyx212111AA21)2 , 3(),1 , 3(),3 , 2(),1 , 2)(3 , 1 (),2 , 1 ()3 , 2(),3 , 1 (),2 , 3(),2 ,

34、 1 (),1 , 3(),1 , 2()2 , 3(),1 , 3(),1 , 2() 3 , 3(),2 , 2(),1 , 1 (444444则复合关系则复合关系 2. 2. 设设 ，A A上的关系上的关系,3210A),(),(),(),(),(00123221101),(),(13022211221121) 1 , 2(),0 , 1 ()2 , 3(),0 , 2(),1 , 2()0 , 0(),1 , 0(),2 , 2(),1 , 1 (),3 , 1 (),2 , 0()2 , 2(),0 , 1 (),1 , 1 (454545 3. 3. 下图给出了集合下图给出了集合

35、上的关上的关系系 的关系图，试画出关系的关系图，试画出关系 和和 的关系图。的关系图。 ,654321A584646462.4 2.4 关系的性质与闭包关系的性质与闭包 一、集合一、集合A A上关系的性质上关系的性质 定义定义2-9 设设 是集合是集合A A上的关系上的关系 （1 1）若对于所有的）若对于所有的 ，均有，均有 ，则称，则称 在在A A上是自反的。上是自反的。 Aaaa （2 2）若对于所有的）若对于所有的 ，均有，均有 ，则称，则称 在在A A上是反自反的。上是反自反的。 Aaaa （3 3）对于所有的）对于所有的 ，若每当有，若每当有 就必有就必有 , , ，则称则称 在在

36、A A 上是对称的。上是对称的。 Aba,abba （4 4）对于所有的）对于所有的 ，若每当有，若每当有 和和 就就必有必有 ，则称，则称 在在 A A 上是反对称的。上是反对称的。 Aba,abba ba （5 5）对于所有的）对于所有的 ，若每当有，若每当有 和和 就必有就必有 ，则称，则称 在在 A A 上是可传递的。上是可传递的。 Acba,bacbca474747例例1 1 设设 ， （1 1）自反与反自反）自反与反自反 ,3210A),(),(),(),(332211001),(),(),(),(),(),(3211223321002),(),(),(3300123),(),()

37、,(2132104自反自反自反自反非自反非自反反自反反自反484848 （2 2）对称与反对称）对称与反对称),(),(),(),(),(23321221115),(),(),(),(132011216),(),(),(),(233222217),(),(),(1122008对称，非反对称对称，非反对称非对称，反对称非对称，反对称非对称，非反对称非对称，非反对称对称，反对称对称，反对称494949（3 3）可传递与不可传递）可传递与不可传递),(),(),(),(303220009),(),(),(),(3212211110),(),(),(23032111可传递可传递不可传递不可传递可传递可

38、传递505050例例2 2 设设 ，A A上的关系上的关系,54321A| ),(是偶数baba),(),(),(513111则则),(),(),(531333),(),(4424),(),(),(553515),(),(4222自反自反对称对称不是反对称不是反对称对于任意的对于任意的 ，若，若 ， Acba,ncbmba22,则则 也是偶数。也是偶数。 )()()(nmcbbaca2因此因此 是可传递的。是可传递的。 515151二、如何利用关系矩阵和关系图来判断关系二、如何利用关系矩阵和关系图来判断关系的性质的性质1. 1. 关系矩阵关系矩阵 10000100101011114321M 1

39、 2 3 4若若 是对称的，则关系矩阵关于主对角线对称。是对称的，则关系矩阵关于主对角线对称。若若 是反对称的，则关系矩阵中，关于主对角线对称的元是反对称的，则关系矩阵中，关于主对角线对称的元素不同时为素不同时为1 1。 若若 是自反的，则关系矩阵的主对角线上的所有元素均为是自反的，则关系矩阵的主对角线上的所有元素均为1 1。若若 是反自反的，则关系矩阵的主对角线上所有元素均为是反自反的，则关系矩阵的主对角线上所有元素均为0 0。 5252522. 2. 关系图关系图 若若 是自反的，则关系图中每一结点引出一个指向自身是自反的，则关系图中每一结点引出一个指向自身的单边环。的单边环。 若若 是反

40、自反的，则关系图中每一结点均没有单边环。是反自反的，则关系图中每一结点均没有单边环。 若若 是对称的，则在关系图中，若两结点之间存在有边，是对称的，则在关系图中，若两结点之间存在有边，则必存在两条方向相反的边。则必存在两条方向相反的边。 若若 是反对称的，则在关系图中，任意两个不同的结点间是反对称的，则在关系图中，任意两个不同的结点间至多只有一条边。至多只有一条边。 ka 若若 是可传递的，则在关系图中，若每当有边由是可传递的，则在关系图中，若每当有边由 指指向向 ，且又有边由，且又有边由 指向指向 ，则必有一条边由，则必有一条边由 指向指向 。 iajaiajaka535353例例3 3 设

41、设 ，下面分别给出集合，下面分别给出集合A A上三个关系的上三个关系的关系图，试判断它们的性质。关系图，试判断它们的性质。 ,321A解解 （1 1） 是自反的，非对称，不是反对称，不可传递。是自反的，非对称，不是反对称，不可传递。 1（2 2） 非自反，也不是反自反，非对称，反对称，非自反，也不是反自反，非对称，反对称， 可传递。可传递。 2（3 3） 是自反的，对称的，可传递的，不是反自反，是自反的，对称的，可传递的，不是反自反，也不是反对称。也不是反对称。 3545454三、集合三、集合A A上关系的闭包上关系的闭包1. 1. 闭包的定义闭包的定义 例例4 4 设设 ，A A上的关系上的

42、关系 , ,则则 ,3210A),(),(),(321000),(),(),(),(),(),(),(),(),(),(),(),(),()(32103322110033221100321000AIr显然，显然， 是自反的。是自反的。 )(r 定义定义2-10 设设 是集合是集合A A上的关系，由下式定义的上的关系，由下式定义的A A上上的关系的关系 称为称为 的自反闭包。的自反闭包。 AIr)(555555 定义定义2-11 设设 是集合是集合A A上的关系，由下式定上的关系，由下式定义的义的A A上的关系上的关系 称为称为 的对称闭包。的对称闭包。 )(s例例5 5 例例4 4中的中的 。

43、 ),(),(),(321000它不是对称的它不是对称的, , ),(),(),(230100则则),(),(),(),(),(),(),(),(),(),(),()(2332011000230100321000s显然，显然， 是对称的。是对称的。 )(s565656 定义定义2-12 设设 是集合是集合A A上的关系，由下式定义的上的关系，由下式定义的A A上上的关系的关系称为称为 的传递闭包。的传递闭包。 321iit)( 当当A A是有限集时，是有限集时，A A上只有有限个不同的关系，因此，上只有有限个不同的关系，因此，存在某个正整数存在某个正整数m m，使得，使得imit1)( 事实上

44、，可以证明，若事实上，可以证明，若 ，则，则nA #init1)(575757例例6 6 设设 ，A A上的关系上的关系 ,dcbaA ),(),(),(),(dccbabba则则),(),(),(),(2dbbbcaaa),(),(),(),(3cbabdaba),(),(),(),(4dbbbcaaa注意到注意到 , 则则 ，24,357246354131iiiidcdbcbbbabdacaaabat),(),(),(),(),(),(),(),(),()(585858)(rr)(r 2. 2. 闭包的性质闭包的性质 集合集合A A上关系的三个不同的闭包具有如下类似的性质。上关系的三个不同

45、的闭包具有如下类似的性质。 定理定理2-4 设设 是集合是集合A A上的关系，则上的关系，则 的自反闭包的自反闭包 具有以下性质：具有以下性质： （1 1） 。 （2 2） 是自反的。是自反的。 （3 3）对于）对于A A上任何关系上任何关系 ，若，若 自反且自反且 ，则则)(rrrrr)( 证明证明 ，所以性质（，所以性质（1 1）, ,（2 2）显然成立。）显然成立。 IAr)(设设 是是A A上的关系，上的关系， 自反且自反且 ，rrr则由则由 自反，可知自反，可知rrAI由由 和和 知知 ，即，即 。rAIrrAIrr)(595959s 定理定理2-5 设设 是集合是集合A A上的关系

46、，则上的关系，则 的对称闭包的对称闭包 具有如下性质：具有如下性质： （1 1） （2 2） 是对称的是对称的 （3 3）对于）对于A A上任何关系上任何关系 ，若，若 对称且对称且 ， 则则)(s)(s)(ssSss)(证明证明 所以性质（所以性质（1 1）、（）、（2 2）显然成立，）显然成立， )(s设设 是是A A上的关系，上的关系， 对称且对称且 ，则对任意，则对任意sss),(ab必有必有 ，由，由 ，必有，必有 ， ),(bassba),(又由又由 的对称性，有的对称性，有 ，因此，因此 。 ssab),(s由由 和和 知知 ，即，即 。 sssss)(606060 定理定理2-

47、6 设设 是集合是集合A A上的关系，则上的关系，则 的传递闭包的传递闭包 具有如下性质具有如下性质: : （1 1） （2 2） 是可传递的是可传递的 （3 3）对于）对于A A上任何关系上任何关系 ，若，若 可传递且可传递且 ， 则则 。 )(t)(t)(tttttt)( 证明证明 根据根据 ，性质（，性质（1 1）显然成立。）显然成立。 1iit)(设设 ，)(),(),(),(tcbtba 则必存在正整数则必存在正整数h和和k，使得使得 ，即，即 ，khcbba),( ,),(cbbakh, 于是于是 ， 即即 ，cakhkhca),( 因此因此 ，故，故 是可传递的是可传递的.)()

48、,(tca)(t616161设设 是是A A上的任意一个包含上的任意一个包含 的可传递关系。的可传递关系。 t又设又设)(),(tba121kbbb, 因此必存在元素因此必存在元素 ，使得使得bbbbbak1211,因为因为 ，所以，所以 。tbbbbbatktt1211,而而 是可传递的，因此是可传递的，因此 即即 ，故，故有有 。 tbattba),(tt)(bakkba),( ，则存在正整数，则存在正整数k k，使得，使得 ，626262四、如何利用关系矩阵和关系图求关系四、如何利用关系矩阵和关系图求关系的闭包的闭包例例7 7 设设 ，A A上的关系上的关系求求 。 ,dcbaA ),(

49、),(),(),(dccbabba)(),(),(tsr1. 1. 利用关系矩阵求利用关系矩阵求 的闭包的闭包(1)(1)0000100001010010dcbaMdcba1000010000100001dcbaMdcbaAI636363因为因为 所以所以AIr)(100011000111001110000100001000010000100001010010dcbaMdcbar)(于是于是 ),(),(),(),(),(),(),(),()(dddccccbbbabbaaar646464 (2) (2) 若若 ，则，则 ； ， 则则 ， ),(jiaa),(ijaa),(jiaa),(ija

50、a即为若即为若 中中 , ,则则 中中M1ijr1jirM若若 中中 ，则，则 中中 。这说明。这说明 是是 的转置矩阵。的转置矩阵。 M0ijrM0jirMM根据根据 的关系矩阵。的关系矩阵。)(,)(ss)(MMMs010010100101001001000010000100100000100001010010dcbaMdcbas)(于是于是),(),(),(),(),(),()(cddcbccbabbas656565（3 3）因为）因为 ，所以，所以4#A41432iit)(对任意对任意 ，只要，只要 属于属于 、 、 、中任何一个关系，则中任何一个关系，则 ， AAba),(),(ba

51、234)(),(tba于是于是432MMMMMt)(00000000010110100000000010100101000010000101001023MMM0000000010100101000010000101001000001000010100102MMM66666600000000101001010000000001011010000010000101001034MMM32MMMMt)(0000000001011010000000001010010100001000010100100000100011111111dcba于是于是 ),(),(),(),(),(),(),(),(),()

52、(dcdbcbbbabdacabaaat6767672. 2. 利用关系图求利用关系图求 的闭包的闭包例例8 8 对例对例7 7中的关系中的关系 ，利用关系图求其闭包。，利用关系图求其闭包。的关系图的关系图r r() 的关系图的关系图t t()()的关系图的关系图S()S()的关系图的关系图686868练习练习2-42-41. 1. 从下列各题给出的备选答案中选出正确的答案，并将其代从下列各题给出的备选答案中选出正确的答案，并将其代号填入题后面的括号内。号填入题后面的括号内。(1) (1) 设设A=0,1,2,3A=0,1,2,3，A A上的关系上的关系=(0,0),(0,2),(1,1),(

53、1,3),(2,2),(2,0),(3,1)=(0,0),(0,2),(1,1),(1,3),(2,2),(2,0),(3,1)，则，则是是A.A. 自反的自反的 B. B. 对称的对称的 C. C. 反对称的反对称的 D. D. 可传递的可传递的 ( ) B （2) 2) 设设是整数集是整数集I I上的关系，定义为当且仅当上的关系，定义为当且仅当 时时 ， ，则，则是是A. 自反的自反的 B. B. 对称的对称的 C. C. 反对称的反对称的 D. D. 可传递的可传递的 ( )( )1021ii21ii A、B6969692.2. 下图给出了下图给出了1,2,31,2,3上三个关系的关系图

54、，试对每一个图上三个关系的关系图，试对每一个图所表示的关系的性质作出判别，并将选中的性质的代号填入所表示的关系的性质作出判别，并将选中的性质的代号填入相应的括号内。相应的括号内。 若若 A. A. 自反的自反的 B. B. 对称的对称的 C. C. 反对称的反对称的 D. D. 可传递可传递 E. E. 反自反反自反则则 是（是（ ）则则 是（是（ ）则则 是（是（ ） 123A AB B A A E E707070 3. 3. 设设 ，A A上的关系上的关系对下列求出的闭包判断正确与否，分别将对下列求出的闭包判断正确与否，分别将“Y”Y”或或“N”N”填入后面的括号。填入后面的括号。 （ ）

55、 （ ） （ ） ,dcbaA ),(),(),(bcdbba),(),(),(),(),(),()(ddccbbaadbbar),(),(),(),(),(),()(cadcdabcdbbat),(),(),(),(),(),()(cbbdabbcdbbasN NY YN N7171712.5 2.5 等价关系等价关系 一、等价关系的定义一、等价关系的定义1. 1. 等价关系等价关系 定义定义2-13 集合集合A A上的关系上的关系，如果它是自反的，对，如果它是自反的，对称的，且可传递的，则称称的，且可传递的，则称是是A A上的等价关系。上的等价关系。 例如例如 数的相等关系是任何数集上的等

56、价关系。数的相等关系是任何数集上的等价关系。 又例如又例如 一群人的集合中姓氏相同的关系也是一群人的集合中姓氏相同的关系也是等价关系。等价关系。但朋友关系不是等价关系，因为它不可传递。但朋友关系不是等价关系，因为它不可传递。 727272 例例1 1 设设A A是任意集合，则是任意集合，则A A上的恒等关系和普上的恒等关系和普遍关系遍关系U UA A均是均是A A上的等价关系。上的等价关系。 例例2 2 设设 ，A A上的关系上的关系,dcbaA ),(),(),(),(),(),(),(),(ddcddcccbbabbaaa是是A A上的等价关系。上的等价关系。 2. 2. 元素元素a a与

57、与b b等价等价 设设是集合是集合A A上的等价关系，若元素上的等价关系，若元素ab ab ，则，则称称a a与与b b等价，或称等价，或称b b与与a a等价。等价。 7373733. 3. 等价类等价类 定义定义2-14 设设是集合是集合A A上的等价关系，则上的等价关系，则 A A 中中等价于元素等价于元素 a a 的所有元素组成的集合称为的所有元素组成的集合称为 a a 生成生成的等价类，用的等价类，用 表示，即表示，即 a|baAbba且例如例如 对于例对于例2 2中的中的来说来说,babbaa,dcddcc7474741. 1. 对任意对任意 , 二、等价类的性质二、等价类的性质

58、Aaa因为对于任意的因为对于任意的aA,aA,有有aaaa，所以，所以 。aa 2. 2. 对任意的对任意的a,bA a,bA 若若 ab ab ，则，则 。ba由由的对称性有的对称性有xa xa ， 证明证明 若若 ，则，则ax ax ， ax又由又由的传递性有的传递性有xb xb ，因此，因此 bx故故 。 ba类似地可以证明类似地可以证明由上得由上得abba7575753. 3. 对任意对任意a,bAa,bA，若，若 ，则，则baba 证明证明（用反证法）（用反证法）假设假设 , , ba则则A A中至少有一元素中至少有一元素 bax因此因此 且且 ，axbx即即xaxa，且，且xb,x

59、b, 于是由于是由ax,xbax,xb，得，得abab，故故 baba与与 相矛盾。相矛盾。767676例例3 3 设设A=a,b,c,dA=a,b,c,d，A A上的关系上的关系),(),(),(),(),(),(),(),(),(),(ddacbcabbbcccacbbaaa是是A上的等价关系上的等价关系 ,cbacbadd 同一个等价类中元素均相互等价。不同等价类同一个等价类中元素均相互等价。不同等价类中的元素互不等价。中的元素互不等价。 777777三、等价关系与分划三、等价关系与分划 集合集合A A上的等价关系与集合上的等价关系与集合A A上的分划具有一一对应关系。上的分划具有一一对

60、应关系。 定理定理2-7 设设是集合是集合A A上的一个等价关系，则集合上的一个等价关系，则集合A A中所中所有元素产生的等价类的集合有元素产生的等价类的集合 是是A A的一个分划。的一个分划。 （1 1）对每一元素）对每一元素aAaA， 是是A A的非空子集。的非空子集。 Aa （2 2）对任意）对任意a,bAa,bA，或者，或者 与与 是是A A的同一子集或的同一子集或者者 abba另一方面，对任一另一方面，对任一 ，而，而 ,xxAx有Aaax|Aaa （3 3）对所有的元素的等价类求并集，显然有）对所有的元素的等价类求并集，显然有 . .aAaA所以所以 ，因此，因此 ，故，故 。Aa