离散数学及其应用第3章-集合与关系课件.ppt

1、 3.6复合关系与逆关系复合关系与逆关系(Compound Relations&Inverse Relations)3.7关系的闭包运算关系的闭包运算(Closure Operations)3.8 等价关系与相容关系等价关系与相容关系(Equivalent Relations&Compatibility Relations)3.9 序关系序关系(Ordered Relations)3.1集合的基本概念集合的基本概念(The Basic Concepts of Sets)3.2集合的运算集合的运算(Operations With Sets)3.3序偶与笛卡尔积序偶与笛卡尔积(Ordered Pa

2、irs&Cartesian Product)3.4关系及其表示关系及其表示(Relations&Theirs Presentations)3.5关系的性质及其判定关系的性质及其判定(The Propeties of Relations)第三章第三章 集合与关系集合与关系（Sets and Relations)2022-8-5计算机科学与技术学院 3.1 集合的基本概念集合的基本概念(The Basic Concepts of Sets)3.1.1 集合和元素集合和元素(Sets&Elements)3.1.2 集合间的关系集合间的关系(Relations between sets)3.1.3 幂

3、集幂集(Power set)第三章第三章 集合与关系集合与关系（Sets and Relations)2022-8-5计算机科学与技术学院例如例如 全体中国人可组成一个集合，每一个中国全体中国人可组成一个集合，每一个中国人均是这个集合的元素人均是这个集合的元素.3.1.1 集合和元素集合和元素(Sets&Elements)1.1.集合和元素集合和元素 v 定义定义3.1.13.1.1 把一些确定的、彼此不同的事把一些确定的、彼此不同的事物作为一个整体来看待时，这个整体便称为物作为一个整体来看待时，这个整体便称为是一个是一个集合集合。v 组成集合的那些个体称为集合的组成集合的那些个体称为集合的元

4、素元素。第三章第三章 集合与关系集合与关系（Sets and Relations)2022-8-5计算机科学与技术学院又例如又例如 所有的正整数组成一个集合，每一个所有的正整数组成一个集合，每一个正整数均是这个集合的元素。正整数均是这个集合的元素。通常用大写英文字母来标记集合，用小写英通常用大写英文字母来标记集合，用小写英文字母标记组成集合的个体文字母标记组成集合的个体.若个体若个体a是集合是集合A的元素，则记作的元素，则记作“aA”若若a不是集合不是集合A的元素，则记作的元素，则记作“a A”第三章第三章 集合与关系集合与关系（Sets and Relations)2022-8-5计算机科学

5、与技术学院2.几个常用集合的表示符号：N：所有自然数的集合。：所有自然数的集合。Q：所有有理数的集合。：所有有理数的集合。I(或或Z)：所有整数的集合。：所有整数的集合。P：所有素数的集合。：所有素数的集合。R：所有实数的集合。：所有实数的集合。Nm：从：从1到到m，这，这m个正整数的集合。个正整数的集合。C:所有复数的集合。所有复数的集合。Zm：从：从0到到m-1，这，这m个非负整数的集合。个非负整数的集合。R+：所有正实数的集合。：所有正实数的集合。R-：所有负实数的集合。：所有负实数的集合。于是于是2N，2.5 N，-3 N，但，但2.5Q，-3I。第三章第三章 集合与关系集合与关系（S

6、ets and Relations)2022-8-5计算机科学与技术学院 3.集合的表示方法集合的表示方法(1)列举法列举法：按任意顺序逐一列举集合中的元：按任意顺序逐一列举集合中的元素于花括号内，元素之间用逗号隔开。素于花括号内，元素之间用逗号隔开。例如例如：A=2,a,b,9,B=4,5,6,7,8(2)描述法描述法：给定一个条件：给定一个条件P(x)，当且仅当个体，当且仅当个体a使使P(a)成立时，成立时，aA。其一般形式为。其一般形式为A=a P(a)例如例如 上述集合上述集合B=a aN且且4a8 又如又如 C=2i iZ+,即即C=20,21,22,23,D=2x xZ+且且x50

7、,即即 D=0,2,4,6,98,1002022-8-5计算机科学与技术学院 4.集合的基数集合的基数集合集合A中不同元素的个数称为集合中不同元素的个数称为集合A的的基数基数，记作记作 。例如例如 N,Z+,I ,R 等均为无限集等均为无限集。A例如例如 上页中的集合，上页中的集合，=4=4，=5=5，=51=51，集合集合C有无穷多个元素，因此有无穷多个元素，因此C的基数是无的基数是无穷大。穷大。ADB若若 是有限数，则称是有限数，则称A为有限集，否则称为有限集，否则称A为为无限集。无限集。A2022-8-5计算机科学与技术学院 5.5.空集空集定义定义3.1.2 不含有任何元素的集合，称为

8、不含有任何元素的集合，称为空集空集，记作记作。例如例如 A=x|xR 且且 x2+8=0=第三章第三章 集合与关系集合与关系（Sets and Relations)2022-8-5计算机科学与技术学院练习练习3.1.1 1.用列举法表示下列集合用列举法表示下列集合（1）A=a|aP且且a2020（2）B=a|a|=)()()(,yxRyRxyx例例3 Q=,2Rxxx4,52,31,4,5,2,3,1例例42022-8-5计算机科学与技术学院第三章第三章 集合与关系集合与关系(Sets&Relations)BR例例5 5 设设 。由由 到到 的关系的关系 定义为：当且仅当定义为：当且仅当a a

9、整除整除b b时，时，有有 。定义定义3.4.2 设设 是由是由A到到B的一个关系，的一个关系，的定义域的定义域或前域记作或前域记作domdom ，的值域记作的值域记作ran ran ，分别，分别定义为：定义为：,|baBbAaadom使得且存在,|baAaBbbran使得且存在 显然有显然有 BRAD,BranAdom,9,8,7,6,2,5,3,2BAABba于是于是 9,3,6,3,8,2,6,2,2,2 的定义域的定义域 ，值域，值域 .3,2dom9,8,6,2ran2022-8-5计算机科学与技术学院A3.4.2 几种特殊的关系几种特殊的关系(Several special Rel

10、ations)AABABA,空关系空关系 对任意集合对任意集合 .所以所以 是由是由 到到 的关系，的关系，也是也是 上的关系，称上的关系，称为空关系。为空关系。BA 全域关系全域关系 因为因为 ,所以所以是一个由是一个由 到到 的关系的关系,称为由称为由 到到 的的全域关系全域关系。是是 上的一个关系上的一个关系,称为称为 上的上的全域关系全域关系。常将常将 记作记作 BABAAAAAAAABAAA,|,AaaaaUjijiABAAAAB2022-8-5计算机科学与技术学院),(),(),(ccbcac|,AaaaIA 是是 上的恒等关系。上的恒等关系。恒等关系恒等关系定义集合定义集合 上的

11、恒等关系上的恒等关系例例6 6 设设 则则 是是 上的全域关系。上的全域关系。A,cbaA,cbbbabcabaaaAAUA,ccbcacA,ccbbaaIAA2022-8-5计算机科学与技术学院3.4.3 关系的表示关系的表示(The expression of Relations)第三章第三章 集合与关系集合与关系(Sets&Relations)1.1.集合表示法集合表示法用用表示集合的列举法或描述法来表示关系表示集合的列举法或描述法来表示关系。,751B,8432A),(),(7454,baba 例例7 7 设设 A=2,3,4,8,B=1,5,7,用描述法用描述法定义由定义由A到到B的

12、关系的关系 ，试用，试用列举法将列举法将 表示出来。表示出来。解解 7,4,5,4,7,3,5,3,7,2,5,22022-8-5计算机科学与技术学院 例例8 有王、张、李、何是某校的老师，该校有三门有王、张、李、何是某校的老师，该校有三门课程：语文、数学和英语，已知王可以教语文和数课程：语文、数学和英语，已知王可以教语文和数学，张可以教语文和英语，李可以教数学，何可以学，张可以教语文和英语，李可以教数学，何可以教英语，若记教英语，若记A=王，张，李，何王，张，李，何，B=语文，数学，语文，数学，英语英语。那么这些老师与课程之间的对应关系就可以。那么这些老师与课程之间的对应关系就可以用由用由A

13、到到B的一个关系的一个关系 中的序偶来表示。中的序偶来表示。=王王,语文语文,王王,数学数学,张张,语文语文,张张,英语英语,李李,数数 学学,何何,英语英语2022-8-5计算机科学与技术学院2.矩阵表示法矩阵表示法 ijrM例例7 7中由中由A到到B的关系的关系 可以可以用一个用一个 的矩阵来表示。的矩阵来表示。1 5 71 5 7jijiijbabar若若01M34 定义定义3.4.3 设设 A、B 都是有限集，都是有限集，,，由，由A到到B的关系的关系 可以用一个可以用一个 的矩阵的矩阵 来表示，来表示，的第的第i i行第行第j j列的元素列的元素 取值如取值如下：下：矩阵矩阵 称为称

14、为 的关系矩阵。的关系矩阵。,21naaaA,21mbbbBmnMMijr0001101101108432M2022-8-5计算机科学与技术学院|,的整数倍是xyyx 1 2 3 4例例9 9 设设 ，A上的关系上的关系解解4,3,2,1A则则 可以用一个可以用一个 的矩阵来表示。的矩阵来表示。4410000100101011114321M4,4,3,3,4,2,2,2,4,1,3,1,2,1,1,12022-8-5计算机科学与技术学院3.关系图表示法关系图表示法关系图由结点和边组成关系图由结点和边组成 例如，例如，例例7 7中的中的 ，,AB8,4,3,2A7,5,1B7,4,5,4,7,3

15、,5,3,7,2,5,2则则 的关系图如下的关系图如下2022-8-5计算机科学与技术学院例如例如 例例9 9中的中的 ，的关系图如下：的关系图如下：4,3,2,1A4,4,3,3,4,2,2,2,4,1,3,1,2,1,1,12022-8-5计算机科学与技术学院第三章第三章 集合与关系集合与关系(Sets&Relations)小结小结:本节介绍了本节介绍了关系的定义、几种特殊的关系的定义、几种特殊的关系及关系的表示。重点掌握关系的表示方关系及关系的表示。重点掌握关系的表示方法。法。作业：作业：P80:1,2，42022-8-5计算机科学与技术学院BABA 3.5 关系的性质关系的性质(The

16、 properties of Relations)3.5.1 集合集合A上上关系的关系的性质性质(The properties of Relations on set A)3.5.2 由由关系图、关系矩阵判别关系的性质关系图、关系矩阵判别关系的性质第三章第三章 集合与关系集合与关系(Sets&Relations)2022-8-5计算机科学与技术学院第三章第三章 集合与关系集合与关系(Sets&Relations)3.5.1 集合集合A上关系的性质上关系的性质 aa 定义定义3.5.1 设设 是集合是集合A上的关系上的关系 （1 1）若对于所有的）若对于所有的 ，均有，均有 ，则称，则称 在在A

17、上是自反的上是自反的(reflexive)(reflexive)。Aaaa （2 2）若对于所有的）若对于所有的 ，均有，均有 ，则称，则称 在在A上是反自反的上是反自反的(antireflexive(antireflexive)。AaaaAba,（3 3）对于所有的）对于所有的 ，若每当有，若每当有 就必有就必有 ，则称则称 在在 A上是对称的上是对称的(symmetric)(symmetric)。baab （4 4）对于所有的）对于所有的 ，若每当有，若每当有 和和 就就必有必有 ，则称，则称 在在 A上是反对称的上是反对称的(antisymmetric(antisymmetric).).

18、Aba,baabba （5 5）对于所有的）对于所有的 ，若每当有，若每当有 和和 就必有就必有 ，则称，则称 在在 A上是可传递的上是可传递的(transitive)(transitive)。Acba,bacbca2022-8-5计算机科学与技术学院 例例1 1 设设 ，（1 1）自反与反自反）自反与反自反 自反自反自反自反非自反非自反反自反反自反3,2,1,0A3,3,2,2,1,1,0,013,3,3,2,2,2,1,1,2,1,0,023,3,0,0,1,232,1,3,2,1,042022-8-5计算机科学与技术学院),(),(),(),(233222217 （2 2）对称与反对称）

19、对称与反对称对称，非反对称对称，非反对称非对称，反对称非对称，反对称非对称，非反对称非对称，非反对称对称，反对称对称，反对称2,3,3,2,1,2,2,1,1,152,0,1,3,2,1,1,162,2,2,3,2,1,3,270,0,2,2,1,18第三章第三章 集合与关系集合与关系(Sets&Relations)2022-8-5计算机科学与技术学院),(),(),(),(3212211110（3 3）可传递与不可传递）可传递与不可传递可传递可传递不可传递不可传递可传递可传递3,0,3,2,2,0,0,091,2,3,2,2,1,1,1102,3,2,1,0,311U 自反自反反自反反自反U

20、对称不对称不反对称反对称反对称反对称不对称不对称既对称又反对称既对称又反对称2022-8-5计算机科学与技术学院则则),(),(),(531333),(),(4424),(),(),(553515 例例2 2 设设 ，A A上的关系上的关系自反自反对称对称不是反对称不是反对称5,4,3,2,1A|,是偶数baba,5,3,1,3,3,3,4,2,2,2,5,1,3,1,1,15,5,3,5,1,5,4,4,2,4对于任意的对于任意的 ,，则则 也是偶数。也是偶数。因此因此 是可传递的。是可传递的。Acba,ncbmba2,2)(2)()(nmcbbaca2022-8-5计算机科学与技术学院),

21、(),(),(531333),(),(),(553515则则 是是自反的、反对称的、自反的、反对称的、可传递的。可传递的。例例3 3 设设则则 自反的、对称的、反对称的、自反的、对称的、反对称的、可传递的。可传递的。则则 自反的、反对称的、自反的、反对称的、可传递的。可传递的。,|,1baRbaba且123,|,2baRbaba且,|,3baNbaba且2022-8-5计算机科学与技术学院),(),(),(531333),(),(),(553515则则 是是自反的、对称的、自反的、对称的、可传递的。可传递的。例例3 3（续）（续）则则 反自反的、反对称的、反自反的、反对称的、可传递的。可传递的

22、。则则 反自反的、反对称的反自反的、反对称的。546,|,4的朋友是且是人bababa,|,5的祖先是且是人bababa,|,6的父亲是且是人bababa例例4 4 是不是不自反、反自反的、对称的、反对称、自反、反自反的、对称的、反对称、可传递的。可传递的。例例5 5 全关系是全关系是自反的、对称的、自反的、对称的、可传递的。可传递的。2022-8-5计算机科学与技术学院3.5.2 由由关系图、关系矩阵判别关系的性质关系图、关系矩阵判别关系的性质1.1.关系矩阵关系矩阵 1 2 3 410000100101011114321M若若 是自反的，则关系矩阵的主对角线上的所有元素是自反的，则关系矩阵

23、的主对角线上的所有元素均为均为1 1。若若 是反自反的，则关系矩阵的主对角线上所有元素是反自反的，则关系矩阵的主对角线上所有元素均为均为0 0。若若 是对称的，则关系矩阵关于主对角线对称。是对称的，则关系矩阵关于主对角线对称。若若 是反对称的，则关系矩阵中，关于主对角线对称是反对称的，则关系矩阵中，关于主对角线对称的元素不同时为的元素不同时为1 1。例如，例如，2022-8-5计算机科学与技术学院2.2.关系图关系图 若若 是对称的，则在关系图中，若两结点之间有边，则是对称的，则在关系图中，若两结点之间有边，则必存在两条方向相反的边。必存在两条方向相反的边。若若 是反对称的，则在关系图中，任意

24、两个不同的结点是反对称的，则在关系图中，任意两个不同的结点间至多只有一条边。间至多只有一条边。kaiaja 若若 是自反的，则关系图中每一结点引出一个指向自身是自反的，则关系图中每一结点引出一个指向自身的单边环的单边环(自环）。自环）。若若 是反自反的，则关系图中每一结点均没有自环。是反自反的，则关系图中每一结点均没有自环。若若 是可传递的，则在关系图中，若每当有边由是可传递的，则在关系图中，若每当有边由 指指向向 ，且又有边由，且又有边由 指向指向 ，则必有一条边由，则必有一条边由 指向指向 。iakajaiajaka2022-8-5计算机科学与技术学院123 例例6 6 设设 ，下面分别给

25、出集合，下面分别给出集合A上三个关系上三个关系的关系图，试判断它们的性质。的关系图，试判断它们的性质。3,2,1A（2 2）非自反，也不是反自反，非对称，反对称，非自反，也不是反自反，非对称，反对称，可传递。可传递。（3 3）是自反的，对称的，可传递的，不是反自反，是自反的，对称的，可传递的，不是反自反，也不是反对称。也不是反对称。解解 （1 1）是自反的，非对称，不是反对称，不可传递是自反的，非对称，不是反对称，不可传递 但但 ,113,2,2,1.3,112022-8-5计算机科学与技术学院第三章第三章 集合与关系集合与关系(Sets&Relations)小结小结:本节介绍了本节介绍了关系

26、的基本性质及其判别关系的基本性质及其判别方法。方法。作业：作业：P83:2，4,5,62022-8-5计算机科学与技术学院BABA 3.6 复合关系与逆关系复合关系与逆关系(Compound Relations&Inverse Relations)3.6.1 关系的并、交、补及对称差运算关系的并、交、补及对称差运算3.6.2 复合关系复合关系(Compound Relations)3.6.3 逆关系逆关系(Inverse Relations)第三章第三章 集合与关系集合与关系(Sets&Relations)2022-8-5计算机科学与技术学院第三章第三章 集合与关系集合与关系(Sets&Rel

27、ations)3.6.1 关系的并、交、补及对称差运算关系的并、交、补及对称差运算),(4221)3,3(),2,1(21,RSR例例1 1 设设 ，则则3,3,4,2,2,112,4,4,2,3,12.2,4,3,1,3,3,4,2,2,121.4,221.3,3,2,121定理定理3.6.1 若若R与与S都是集合都是集合A到集合到集合B的关的关系，则系，则 RS,RS,R-S,均为均为A到到B的关系。的关系。.2,4,3,1,3,3,2,1212022-8-5计算机科学与技术学院3.6.2 复合关系复合关系(Compound Relations)1.复合关系的定义复合关系的定义 定义定义3

28、.6.1 设设 是由是由A到到B的关系，的关系，是由是由B到到C 的关的关系，则系，则 和和 的复合关系是一个由的复合关系是一个由A到到C 的关系，用的关系，用 表示，定义为：当且仅当存在元素表示，定义为：当且仅当存在元素 ，使，使得得 ，时，有时，有 。这种由这种由 和和 求复合关系求复合关系 的运算称为关系的运算称为关系的复合运算。的复合运算。由定义可知由定义可知:121212Bbba1cb2ca)(211221)()()(,21BbbCcAaca)()(21cbba2022-8-5计算机科学与技术学院于是复合关系于是复合关系 例例2 2 设设 是由是由 到到 的关的关 系。系。是由是由

29、B B 到到 的关系。的关系。分别定义为：分别定义为：12,4,3,2,1A4,3,2B6,5,3C2,4,3,3,4,26|,1baba6,3,3,3,6,2|,2cbcb整除6,4,6,3,3,3212022-8-5计算机科学与技术学院 例例3 3 设设 是所有人的集合是所有人的集合 于是复合关系于是复合关系 CBA,|,1的兄弟是baAbaba,|,2的父亲是cbAcbcb21,|,的叔伯是caAcaca第三章第三章 集合与关系集合与关系(Sets&Relations)2022-8-5计算机科学与技术学院2.2.关系复合运算的性质关系复合运算的性质 定理定理3.6.2 设设 是由集合是由

30、集合A到到B的关系，则的关系，则 例例4 4 以例以例2 2中的关系中的关系 为例，为例，从关系图，可得从关系图，可得 ,BAII2,4,3,3,4,21111AI11BI2022-8-5计算机科学与技术学院 定理定理3.6.3 设设 是由是由A到到B的关系，的关系，是由是由B到到C的关的关系，则有系，则有 证证:(3):(3)反设反设则必存在则必存在 使使 ，从而从而 使使 故故 且且 所以所以 ，这就与，这就与12121)(domdom(1)(2)(3)221)(ranran1212,random若则,21,CzAxzx21,By,21zyyx,1rany,2domy21domrany)2

31、1domran矛盾。矛盾。2022-8-5计算机科学与技术学院 ,2 定理定理3.6.4 (1)(1)设设 是由是由A到到B的关系，的关系，是由是由B到到C的关系，的关系，是由是由C到到D的关系，则有的关系，则有 (2)(2)设设 是由是由A到到B的关系，的关系，是由是由B到到C的关系，的关系，则有则有 (3)(3)设设 是由是由A到到B的关系，的关系，是由是由B B到到C的关系，的关系，则有则有 123)()(32132113)()()(3121321,123)()()(32313212022-8-5计算机科学与技术学院 例例5 5 设设 ，,.,.A到到B的关系的关系 B到到C的关系的关系

32、 C到到D的关系的关系 则则A到到C的关系的关系 因此因此因此因此所以所以3,2,1C4,3,2B6,5,4D2,4,3,2,4,216,3,6,2,5,1,4,233,4,2,3,1,221,4,2,2,3,2214,3,2,1A6,4,6,3,4,3,5,2325,4,4,2,6,2)(3215,4,4,2,6,2)(321)()(321321第三章第三章 集合与关系集合与关系(Sets&Relations)2022-8-5计算机科学与技术学院11A2A22A3AnnA1nAn211A一般地，若一般地，若 是一由是一由 到到 的关系，的关系，是由是由 到到的关系，的关系，是一由是一由 到到

33、 的关系，则不加括号的表的关系，则不加括号的表达式达式 ，唯一地表示一由唯一地表示一由 到到 的关的关系，在计算这一关系时，可以运用结合律将其中任意两系，在计算这一关系时，可以运用结合律将其中任意两个相邻的关系先结合。个相邻的关系先结合。特别特别,当当 ,时，时，复合关系复合关系 简记作简记作 ，它也是集，它也是集 A 上的一上的一 个关系。个关系。1nAAAAAn121n21n2022-8-5计算机科学与技术学院2 3.求复合关系的几种方法求复合关系的几种方法（1 1）根据复合关系的定义求复合关系）根据复合关系的定义求复合关系 例例5 5中求复合关系采用的就是这种方法。中求复合关系采用的就是

34、这种方法。又例如又例如,下面的关系图给出了从集合下面的关系图给出了从集合A到到B的关系的关系 和从和从B到到C的关系的关系121,3,3,2,2,2212022-8-5计算机科学与技术学院（2）运用关系矩阵的运算求复合关系）运用关系矩阵的运算求复合关系布尔运算布尔运算其加法和乘法运算定义如下其加法和乘法运算定义如下000111 0+0=0,0+1=1+0=1+1=1 ,例如例如 00001101111)11()000()111()10()001(2022-8-5计算机科学与技术学院 关系矩阵的乘积关系矩阵的乘积 对两个关系矩阵求其乘积时，其运算法则与一般对两个关系矩阵求其乘积时，其运算法则与一

35、般矩阵的乘法是相同的，但其中的加法运算和乘法运矩阵的乘法是相同的，但其中的加法运算和乘法运算应改为布尔加和布尔乘。算应改为布尔加和布尔乘。则则例例6 6 设设 和和 是两个关系矩阵是两个关系矩阵1M2M0010101000011M1010100012M00101010100121MM2022-8-5计算机科学与技术学院 复合关系的关系矩阵复合关系的关系矩阵 定理定理3.6.5 设设A、B、C均是有限集，均是有限集，是一由是一由A到到B的关系的关系,是一由是一由B到到C的关系，它们的关系的关系，它们的关系矩阵分别为矩阵分别为 和和 ，则复合关系，则复合关系 的关的关系矩阵系矩阵 121M2M21

36、2121MMM2022-8-5计算机科学与技术学院2 3 4 1 2 3 1 2 34,3,2,1A4,3,2B 设有集合设有集合 ，A A到到B B的关系的关系 B B到到C C的关系的关系 则则与例与例6 6比较得比较得 3,2,1C2,4,3,3,4,2,2,113,4,1,4,2,3,1,221,4,2,3,3,2,1,2,1,12100101010000143211M1010100014322M001010101001432121M2121MMM例例72022-8-5计算机科学与技术学院 例例8 8 设设 ，A上的关系上的关系 试求试求 和和 。,dcbaA,cbdcccabba32

37、因此因此0000110011100101000011000101001000001100010100102MMM 解解 作出的关系矩阵作出的关系矩阵 a b c d根据定理根据定理3.5.53.5.50000110001010010dcbaM,2dcccdbcbbbcaaa2022-8-5计算机科学与技术学院又又 ，所以，所以因此因此2300001100110111100000110011100101000011000101001023MMM,3dcccdbcbabdacaba2022-8-5计算机科学与技术学院 设设 是有限集是有限集A上的关系，则复合关系上的关系，则复合关系 也是也是A上的

38、关上的关系，由复合关系的定义，对于任意的系，由复合关系的定义，对于任意的 ，当且仅，当且仅当当 存在，使得存在，使得 ，时，有时，有 。反映在关系图上，这意味着，当且仅当在反映在关系图上，这意味着，当且仅当在 的关系图的关系图中有某一结点中有某一结点 存在，使得有边由存在，使得有边由 指向指向 ，且有边，且有边由由 指向指向 时，在时，在 的关系图中有边从的关系图中有边从 指向指向 。kaja（3）利用关系图求复合关系）利用关系图求复合关系n2Aaaji,Aakkiaajkaajiaa2kaiakakaja2iajaiakajajaia22022-8-5计算机科学与技术学院根据根据 的关系图构

39、造出的关系图构造出 的关系图：的关系图：对于对于 的关系图中的每一结点的关系图中的每一结点 ，找出从，找出从 经经过长为过长为n n的路能够到达的结点，这些结点在的路能够到达的结点，这些结点在 的的关系图中，边必须由关系图中，边必须由 指向它们。指向它们。类似地，对于任意正整数类似地，对于任意正整数n n，当且仅当在，当且仅当在 的的关系图中存在关系图中存在n-1n-1个结点个结点 ,使得有边使得有边由由 指向指向 ,由由 指向指向 ，由由 指向指向 时，在时，在 的关系图中，有边由结点的关系图中，有边由结点 指向指向 。121,nkkkaaaia1ka1ka2ka1nkajaniajania

40、iania第三章第三章 集合与关系集合与关系(Sets&Relations)2022-8-5计算机科学与技术学院 例例9 9 试利用构造试利用构造 和和 的关系图的方法求例的关系图的方法求例8 8 中的中的 和和 。例中。例中2323,cbdcccabba第三章第三章 集合与关系集合与关系(Sets&Relations)2022-8-5计算机科学与技术学院解解2（4 4）根据）根据 和和 的的关系图直接写出关系图直接写出 和和 中的序偶中的序偶.（1 1）先）先作出作出 的关系的关系图图（2 2）构造）构造 的关系图。的关系图。在在 的关的关系图中寻系图中寻找长为找长为2 2的的路。路。（3

41、3）构造）构造 的关系图。的关系图。在在 的关的关系图中寻系图中寻找长为找长为3 3的的路路.33322,cbdcccabba2022-8-5计算机科学与技术学院第三章第三章 集合与集合与关系关系(Sets&Relations)例例1010.下图给出了集合下图给出了集合 上的关上的关系系 的关系图，试画出关系的关系图，试画出关系 和和 的关系图。的关系图。6,5,4,3,2,1A582022-8-5计算机科学与技术学院 3.6.3 逆关系逆关系(Inverse Relations)定义定义3.6.2 设设 A、B 是任意集合，是任意集合，是由是由 A到到 B 的关系，定义由的关系，定义由 B

42、到到 A 的关系的关系称称 为关系为关系 的逆关系。的逆关系。,|,1baab1第三章第三章 集合与关系集合与关系(Sets&Relations)2022-8-5计算机科学与技术学院于是于是 解解 由由 的定义知的定义知 例例1111 设设 ，定义由，定义由A到到B的关的关系系 ：当且仅当：当且仅当 a 整除整除 b 时，有时，有 ，试求，试求 的逆关的逆关系系 。5,3,2A10,6,4Bba1 2,4,2,6,2,10,3,6,5,10 1 4,2,6,2,10,2,6,3,10,5 第三章第三章 集合与关系集合与关系(Sets&Relations)2022-8-5计算机科学与技术学院 关

43、于关于逆关系我们有如下定理：逆关系我们有如下定理：定理定理3.6.6 设设 A 、B 是任意集合，是任意集合，、和和 都是都是由由 A 到到 B 的关系，则有的关系，则有11)(1211121)(121211121)(ABBA1)(,)()(11BA1211121)(（1）（2）（3）（4）（5）（6）2022-8-5计算机科学与技术学院AI1 关于关于逆关系我们有如下定理：逆关系我们有如下定理：定理定理3.6.7 设设 A、B、C 是任意集合，是任意集合，、分别是分别是 由由 A 到到 B 的关系和由的关系和由 B 到到 C 的关系，则有的关系，则有1112121)(12定理定理3.6.8

44、设设 是集合是集合A上的二元关系上的二元关系 ，则则 （1 1）对称当且仅当对称当且仅当 （2 2）反对称当且仅当反对称当且仅当证：证：1)(2022-8-5计算机科学与技术学院第三章第三章 集合与关系集合与关系(Sets&Relations)小结小结:本节主要介绍了本节主要介绍了关系的关系的复合运算与逆复合运算与逆运算。运算。重点掌握关系的重点掌握关系的复合运算及其性质、复合运算及其性质、关系的关系的逆运算的性质逆运算的性质。作业：作业：P90:1，2,52022-8-5计算机科学与技术学院BABA 3.7 关系的闭包运算关系的闭包运算(Closure Operations)3.7.1关系的

45、闭包的概念关系的闭包的概念(The definitions of closures of relations)3.7.2关系的闭包的求法关系的闭包的求法(How to find the closures of relations)第三章第三章 集合与关系集合与关系(Sets&Relations)2022-8-5计算机科学与技术学院第三章第三章 集合与关系集合与关系(Sets&Relations)3.7 关系的闭包运算关系的闭包运算(Closure Operations)3.7.1 关系的闭包的概念关系的闭包的概念(The definitions of closures of relations

46、)例例1.1.设设 是由是由 A上的关系，上的关系，A=1,2,3,=1,2,3,(1)(1)求求A上的关系上的关系 使得使得 且且 是自反的。是自反的。(2)(2)这样的关系共有多少个这样的关系共有多少个?解解:1,3,3,2,2,12022-8-5计算机科学与技术学院3.7 关系的闭包运算关系的闭包运算(Closure Operations)定义定义3.7.1 设设 、是集合是集合A上的关系，如果上的关系，如果 满足满足:(1)(1)是自反的是自反的(对称的对称的/可传递的可传递的)(2)(2)(3)(3)对任何自反的对任何自反的(对称的对称的/可传递的可传递的)的关系的关系 ,若若 则则

47、 ,称称 为为 的自反的自反(对称对称/传递传递)闭包闭包,记作记作 。)(/)()(tsr2022-8-5计算机科学与技术学院)(s 说明说明:(1)求求集合集合A上的关系上的关系 的自反、对称、传递闭的自反、对称、传递闭 包的运算，称为关系包的运算，称为关系 的闭包运算。的闭包运算。(2)(2)的自反的自反(对称、传递对称、传递)闭包是包含闭包是包含 的最小的最小 自反自反(对称对称/可传递可传递)关系。关系。定理定理3.7.1 设设 是是集合集合A上的二元关系上的二元关系,则则 (1)(1)是自反的是自反的(2)(2)是对称的是对称的(3)(3)是可传递的是可传递的)(r)(t3.7 关

48、系的闭包运算关系的闭包运算(Closure Operations)2022-8-5计算机科学与技术学院 1()s3.7.2关系的闭包的求法关系的闭包的求法(How to find the closures of relations)1.1.由定义求由定义求 的闭包的闭包 定理定理3.7.2 设设 是是集合集合A上的二元关系上的二元关系,则则 (1)(1)(2)(2)(3)(3)证明证明:(3):(3)()ArI1()iit2022-8-5计算机科学与技术学院1ii 证明证明 （1 1）显然显然 。1ii故故 是可传递的是可传递的.（2）对任意的）对任意的 ，则必存在正则必存在正整数整数h和和k

49、，使得，使得 ，于是，于是khcbba,11,iiiicbbakhkhca,1ii2022-8-5计算机科学与技术学院（3 3）设）设 是是A A上的任意一个包含上的任意一个包含 的可传递关系。的可传递关系。对任意对任意 ，则存在正整数，则存在正整数k k，使，使得得 ，因此必存在元素，因此必存在元素 ，使得，使得 。bbbbbak1211,因为因为 ，所以，所以 。而而 是可传递的，因此是可传递的，因此 即即 ，故，故有有 。11,iibabak121,kbbbbbbbbak1211,1bbbbbak1121111,1ba11,ba11ii2022-8-5计算机科学与技术学院 例例2 2.下

50、图给出了集合下图给出了集合 上的关上的关系系 的关系图，试画的关系图，试画 、和和 。6,5,4,3,2,1A)(r)(s)(t解解:由关系图知由关系图知:6,6,3,6,4,5,5,4,5,2,3,1,5,12022-8-5计算机科学与技术学院则则)(r 1,1,2,2,3,3,4,4,5,5 6,3,2,5,1,3,1,5)(s26,6,3,6,5,5,4,4,4,2,4,16,6,3,6,4,5,5,4,5,2,5,13426,6,3,6,5,5,4,4,4,2,4,1 6,6,3,6,5,5,4,5,5,4,4,4,5,2,4,2,5,1,4,1,3,13526)(t6,6,3,6,4