离散数学课件3

1、2022-4-30Copyright：张捷：张捷12022-4-301计算机科学与工程系计算机科学与工程系Tianjin University of Technology Department of Computer Science & Engineering离散数学离散数学(Discrete Mathematics)2022-4-30Copyright：张捷：张捷22022-4-302第三章第三章 集合与关系集合与关系（Sets and Relations)Sets and Relations) 本章首先采用朴素集合论的方法，介绍有关集合的一些基本本章首先采用朴素集合论的方法，介绍有

2、关集合的一些基本知识，内容显得较为直观，学起来易于接受。但集合及其相关的知识，内容显得较为直观，学起来易于接受。但集合及其相关的概念是本门课程后面各章内容的基础，同学们务必熟练的掌握。概念是本门课程后面各章内容的基础，同学们务必熟练的掌握。本本章重点讨论关系（主要是二元关系），它仍然是一种集合，章重点讨论关系（主要是二元关系），它仍然是一种集合，但它是一种更为复杂的集合。它的元素是有序二元组的形式，但它是一种更为复杂的集合。它的元素是有序二元组的形式，这些有序二元组中的两个元素来自于两个不同或者相同的集这些有序二元组中的两个元素来自于两个不同或者相同的集合。因此，关系是建立在其它集合基础之上的

3、集合。关系中合。因此，关系是建立在其它集合基础之上的集合。关系中的有序二元组反映了不同集合中元素与元素之间的关系，或的有序二元组反映了不同集合中元素与元素之间的关系，或者同一集合中元素之间的关系。本章讨论这些关系的表示方者同一集合中元素之间的关系。本章讨论这些关系的表示方法、关系的运算以及关系的性质，最后讨论集合法、关系的运算以及关系的性质，最后讨论集合A A上几类特上几类特殊的关系。殊的关系。 2022-4-30Copyright：张捷：张捷32022-4-303第三章第三章 集合与关系集合与关系（Sets and Relations)Sets and Relations) 3.6 3.6

4、关系的闭包运算关系的闭包运算(Closure Operations)(Closure Operations)3.7 3.7 集合的划分与覆盖集合的划分与覆盖(Partition & Cover of Sets) (Partition & Cover of Sets) 3.8 3.8 等价关系等价关系(Equivalent Relations) (Equivalent Relations) 3.9 3.9 相容关系相容关系(Compatibility(CompatibilityRelations) Relations) 3.10 3.10 序关系序关系(Ordered Relat

5、ions)(Ordered Relations)3.1 3.1 集合及其运算集合及其运算(Sets & Operations with sets)(Sets & Operations with sets) 3.2 3.2 序偶与笛卡尔积序偶与笛卡尔积(Ordered Pairs & Cartesian Product)(Ordered Pairs & Cartesian Product)3.3 3.3 关系关系 (Relations) (Relations) 3.4 3.4 关系的性质关系的性质(The Propeties of Relations) (The

6、Propeties of Relations) 3.5 3.5 复合关系与逆关系复合关系与逆关系(Compound Relations & Inverse(Compound Relations & Inverse Relations) Relations)2022-4-30Copyright：张捷：张捷42022-4-304第三章第三章 集合与关系集合与关系（Sets and Relations)Sets and Relations) 3.1 3.1 集合及其运算集合及其运算(Sets & Operations with sets)(Sets & Operati

7、ons with sets) 3.1.13.1.1 集合和元素集合和元素( (Sets & ElementsSets & Elements) ) 3.1.23.1.2 集合间的关系集合间的关系(Relations between sets) (Relations between sets) 3.1.33.1.3 集合的运算和运算定律集合的运算和运算定律( (Operations with setsOperations with sets & Operation laws & Operation laws) ) 3.1.4 3.1.4 幂集幂集(Power set

8、)(Power set)2022-4-30Copyright：张捷：张捷52022-4-305又例如又例如 所有的正整数组成一个集合，每一个正整数均是这个集所有的正整数组成一个集合，每一个正整数均是这个集 合的元素。合的元素。例如例如 全体中国人可组成一个集合，每一个中国人均是这个集合的全体中国人可组成一个集合，每一个中国人均是这个集合的 元素元素. .第三章第三章 集合与关系集合与关系 3.1 3.1 集合及其运算集合及其运算(Sets & Operations with sets )(Sets & Operations with sets ) 3.1.13.1.1 集合和元

9、素集合和元素( (Sets & ElementsSets & Elements) )1. 1. 集合和元素集合和元素 v 定义定义3.1.13.1.1 把一些确定的、彼此不同的事物作为一把一些确定的、彼此不同的事物作为一个整体来看待时，这个整体便称为是一个个整体来看待时，这个整体便称为是一个集合集合。 v 组成集合的那些个体称为集合的组成集合的那些个体称为集合的元素元素。 通常用大写英文字母来标记集合，用小写英文字母标通常用大写英文字母来标记集合，用小写英文字母标记组成集合的个体记组成集合的个体. .若个体若个体a a是集合是集合A A的元素，则记作的元素，则记作“aAaA”若

10、若a a不是集合不是集合A A的元素，则记作的元素，则记作“a Aa A” 2022-4-30Copyright：张捷：张捷62022-4-3062.几个常用集合的表示符号：N：所有自然数的集合。：所有自然数的集合。 Q Q：所有有理数的集合。：所有有理数的集合。Z Z：所有整数的集合。：所有整数的集合。 P P：所有素数的集合。：所有素数的集合。 R R：所有实数的集合。：所有实数的集合。 N Nm m：从：从1 1到到m m，这，这m m个正整数的集合。个正整数的集合。C: C: 所有复数的集合。所有复数的集合。 Z Zm m：从：从0 0到到m-1m-1，这，这m m个非负整数的集合。个

11、非负整数的集合。R R+ +：所有正实数的集合。：所有正实数的集合。R R- -：所有负实数的集合。：所有负实数的集合。于是于是2N2N，2.5 N2.5 N，-3 N-3 N，但，但2.5Q2.5Q，-3I-3I。 2022-4-30Copyright：张捷：张捷72022-4-307 3. 集合的表示方法集合的表示方法(1)(1)列举法列举法：按任意顺序逐一列举集合中的元素于花括号：按任意顺序逐一列举集合中的元素于花括号内，元素之间用逗号隔开。内，元素之间用逗号隔开。例如：例如：A=2,a,b,9,B=4,5,6,7,8A=2,a,b,9,B=4,5,6,7,8(2)(2)描述法描述法：给

12、定一个条件：给定一个条件P(x)P(x)，当且仅当个体，当且仅当个体a a使使P(a)P(a)成立时，成立时，aAaA。其一般形式为。其一般形式为A=aP(a)A=aP(a) 例如例如 上述集合上述集合B=aaNB=aaN且且4a84a8 又如又如 C=2C=2i iiZiZ+ +,即即C=2C=20 0,2,21 1,2,22 2,2,23 3, , D=2xxZ D=2xxZ+ +且且x50,x50,即即D=0,2,4,6,D=0,2,4,6,98,100,98,1002022-4-30Copyright：张捷：张捷82022-4-308 4. 集合的基数集合的基数集合集合A A中不同元素

13、的个数称为集合中不同元素的个数称为集合A A的的基数基数，记作，记作 . .。例如例如 N , Z+ , I , R 等均为无限集等均为无限集。 5.5.空集空集定义定义3.1.23.1.2 不含有任何元素的集合，称为不含有任何元素的集合，称为空集空集，记作，记作。 例如例如 A=x | xR 且且 x2+8=0 = A例如例如 上页中的集合，上页中的集合， =4=4， =5=5， =51=51，集合，集合C C有无穷多个元素，因此有无穷多个元素，因此C C的基数是无穷大。的基数是无穷大。ADB若若 是有限数，则称是有限数，则称A A为有限集，否则称为有限集，否则称A A为无限集。为无限集。A

14、2022-4-30Copyright：张捷：张捷92022-4-309练习练习3.1.13.1.1 1. 用列举法表示下列集合用列举法表示下列集合（1）A=a|aPP且且a20a20（2）B=a|a|=)()()(,yxRyRxyx例例3 Q=,2Rxxx4, 52 , 31,4 ,5 , 2,3 , 1例例42022-4-30Copyright：张捷：张捷55第三章第三章 集合与关系集合与关系(Sets & Relations)BR例例5 5 设设 。 由由 到到 的关系的关系 定义为：当且仅当定义为：当且仅当a a整除整除b b时，时，有有 。AB 定义定义3.3.2 设设 是由是

15、由A A到到B B的一个关系，的一个关系， 的定义的定义域或前域记作域或前域记作dom dom ， 的值域记作的值域记作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-4-30Copyright：张捷：张捷56A3.3.2 3.3.2 几种特殊的关系几种特

16、殊的关系(Several special (Several special Relations)Relations)AABABA, 空关系空关系 对任意集合对任意集合 . . 所以所以 是由是由A A到到B B的关系，的关系， 也是也是A A上的关系，称为空关上的关系，称为空关系。系。 BA 全域关系全域关系 因为因为 , , ,所以所以是一个由是一个由 到到 的关系的关系, ,称为由称为由 到到 的的全域关系全域关系。 是是 上的一个关系上的一个关系, ,称为称为 上的上的全域关系全域关系。 常将常将 记作记作 BABAAAAAAAABAAA,|,AaaaaUjijiABAA2022-4-3

17、0Copyright：张捷：张捷57),(),(),(ccbcac|,AaaaIA 是是 上的恒等关系。上的恒等关系。 恒等关系恒等关系定义集合定义集合 上的恒等关系上的恒等关系例例6 6 设设 则则 是是 上的全域关系。上的全域关系。A,cbaA ,cbbbabcabaaaAAUA,ccbcacA,ccbbaaIAA2022-4-30Copyright：张捷：张捷583.3.3 3.3.3 关系的表示关系的表示(The expression of (The expression of Relations)Relations)第三章第三章 集合与关系集合与关系(Sets & Relat

18、ions),751B,8432A),(),(74541.1.集合表示法集合表示法用用表示集合的列举法或描述法来表示关系表示集合的列举法或描述法来表示关系。,baba 例例7 7 设设 A=2,3,4,8,B=1,5,7,A=2,3,4,8,B=1,5,7,用描用描述法定义由述法定义由A A到到B B的关系的关系 ，试用列举法将试用列举法将 表示出来。表示出来。 解解 7 , 4,5 , 4,7 , 3,5 , 3,7 , 2,5 , 22022-4-30Copyright：张捷：张捷59 例例8 8 有王、张、李、何是某校的老师，该校有三有王、张、李、何是某校的老师，该校有三门课程：语文、数学

19、和英语，已知王可以教语文和门课程：语文、数学和英语，已知王可以教语文和数学，张可以教语文和英语，李可以教数学，何可数学，张可以教语文和英语，李可以教数学，何可以教英语，若记以教英语，若记A=A=王，张，李，何王，张，李，何 ，B=B=语文，数语文，数学，英语学，英语 。那么这些老师与课程之间的对应关系就。那么这些老师与课程之间的对应关系就可以用由可以用由A A到到B B的一个关系的一个关系 中的序偶来表示。中的序偶来表示。 =王王,语文语文,王王,数学数学,张张,语文语文,张张,英语英语 , 李李,数学数学,何何,英语英语2022-4-30Copyright：张捷：张捷602.2.矩阵表示法矩

20、阵表示法 ijrM例例7 7中由中由A A到到B B的关系的关系 可以可以用一个用一个 的矩阵来表示。的矩阵来表示。 1 5 7 1 5 7jijiijbabar若若01M34 定义定义3.3.3 设设 A A 、B B 都是有限集，都是有限集， , , ，由，由A A到到B B的关系的关系 可以用一个可以用一个 的矩阵的矩阵 来表示，来表示， 的第的第i i行第行第j j列的元素列的元素 取值如取值如下：下：矩阵矩阵 称为称为 的关系矩阵。的关系矩阵。 ,21naaaA,21mbbbBmnMMijr0001101101108432M2022-4-30Copyright：张捷：张捷61|,的整

21、数倍是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-4-30Copyright：张捷：张捷623.3.关系图表示法关系图表示法关系图由结点和边组成关系图由结点和边组成 例如例如 例例7 7中的中的 ， , ,则则的关系图如下的关系图如下AB8 , 4 , 3 , 2A7 , 5 , 1B7 , 4,5 , 4,7 , 3,5 , 3,7 ,

22、2,5 , 22022-4-30Copyright：张捷：张捷63例如例如 例例9 9中的中的 ， 的关系图如下：的关系图如下： 4 , 3 , 2 , 1A4 , 4,3 , 3,4 , 2,2 , 2,4 , 1,3 , 1,2 , 1,1 , 12022-4-30Copyright：张捷：张捷64第三章第三章 集合与关系集合与关系(Sets & Relations)小结小结: 本节介绍了本节介绍了关系的定义、几种特殊的关系的定义、几种特殊的关系及关系的表示。重点掌握关系的表示方关系及关系的表示。重点掌握关系的表示方法。法。作业作业：P109 （2），（6） ，（7）2022-4-

23、30Copyright：张捷：张捷6565张捷2022-4-30Copyright：张捷：张捷66第三章第三章 集合与关系集合与关系（Sets and Relations)Sets and Relations) 3.6 3.6 关系的闭包运算关系的闭包运算(Closure Operations)(Closure Operations)3.7 3.7 集合的划分与覆盖集合的划分与覆盖(Partition & Cover of Sets) (Partition & Cover of Sets) 3.8 3.8 等价关系等价关系(Equivalent Relations) (Equi

24、valent Relations) 3.9 3.9 相容关系相容关系(Compatibility(CompatibilityRelations) Relations) 3.10 3.10 序关系序关系(Ordered Relations)(Ordered Relations)3.1 3.1 集合及其运算集合及其运算(Sets & Operations with sets)(Sets & Operations with sets) 3.2 3.2 序偶与笛卡尔积序偶与笛卡尔积(Ordered Pairs & Cartesian Product)(Ordered Pairs

25、 & Cartesian Product)3.3 3.3 关系关系 (Relations) (Relations) 3.4 3.4 关系的性质关系的性质(The Propeties of Relations) (The Propeties of Relations) 3.5 3.5 复合关系与逆关系复合关系与逆关系(Compound Relations & Inverse(Compound Relations & Inverse Relations) Relations)2022-4-30Copyright：张捷：张捷67BABA 3.4 3.4 关系的性质关系的性质(

26、The properties of Relations)(The properties of Relations)3.4.13.4.1 集合集合A A上上关系的关系的性质性质( (The properties ofThe properties of Relations on set A Relations on set A) )3.4.2 3.4.2 由由关系图、关系矩阵判别关系的性质关系图、关系矩阵判别关系的性质第三章第三章 集合与关系集合与关系(Sets & Relations)2022-4-30Copyright：张捷：张捷68第三章第三章 集合与关系集合与关系(Sets &am

27、p; Relations) 3.4.1 3.4.1 集合集合A A上关系的性质上关系的性质 aa 定义定义3.4.1 设设 是集合是集合A A上的关系上的关系 （1 1）若对于所有的）若对于所有的 ，均有，均有 ，则称，则称 在在A A上是自反的上是自反的(reflexive)(reflexive)。 Aaaa （2 2）若对于所有的）若对于所有的 ，均有，均有 ，则称，则称 在在A A上是反自反的上是反自反的(antireflexive) (antireflexive) 。 AaaaAba, （3 3）对于所有的）对于所有的 ，若每当有，若每当有 就必有就必有 ，则称则称 在在 A A 上是

28、对称的上是对称的(symmetric)(symmetric)。 baab （4 4）对于所有的）对于所有的 ，若每当有，若每当有 和和 就就必有必有 ，则称，则称 在在 A A 上是反对称的上是反对称的(antisymmetric). (antisymmetric). Aba,baabba （5 5）对于所有的）对于所有的 ，若每当有，若每当有 和和 就必有就必有 ，则称，则称 在在 A A 上是可传递的上是可传递的(transitive)(transitive)。 Acba,bacbca2022-4-30Copyright：张捷：张捷69例例1 1 设设 ， （1 1）自反与反自反）自反与反

29、自反 自反自反自反自反非自反非自反反自反反自反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-4-30Copyright：张捷：张捷70),(),(),(),(233222217 （2 2）对称与反对称）对称与反对称对称，非反对称对称，非反对称非对称，反对称非对称，反对称非对称，非反对称非对称，非反对称对称，反对称对称，反对称2 , 3,3 , 2,1 , 2,2 , 1,1 , 152 , 0,1 , 3,2 ,

30、 1,1 , 162 , 2,2 , 3,2 , 1,3 , 270 , 0,2 , 2,1 , 182022-4-30Copyright：张捷：张捷71),(),(),(),(3212211110（3 3）可传递与不可传递）可传递与不可传递可传递可传递不可传递不可传递可传递可传递3 , 0,3 , 2,2 , 0,0 , 091 , 2,3 , 2,2 , 1,1 , 1102 , 3,2 , 1,0 , 311U 自反自反反自反反自反U对称不对称不反对称反对称反对称反对称不对称不对称既对称又反对称既对称又反对称2022-4-30Copyright：张捷：张捷72则则),(),(),(531

31、333),(),(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-4-30Copyright：张捷：张捷73),(),(),(531333),(),(),(5

32、53515则则 是是自反的、反对称的、自反的、反对称的、可传递的。可传递的。 例例3 3 设设则则 自反的、对称的、反对称的、自反的、对称的、反对称的、可传递的。可传递的。则则 自反的、反对称的、自反的、反对称的、可传递的。可传递的。,|,1baRbaba且123,|,2baRbaba且,|,3baNbaba且2022-4-30Copyright：张捷：张捷74),(),(),(531333),(),(),(553515则则 是是自反的、对称的、自反的、对称的、可传递的。可传递的。 例例3 3（续）（续）则则 反自反的、反对称的、反自反的、反对称的、可传递的。可传递的。则则 反自反的、反对称的

33、反自反的、反对称的。546,|,4的朋友是且是人bababa,|,5的祖先是且是人bababa,|,6的父亲是且是人bababa例例4 4 是不是不自反、反自反的、对称的、反对称、自反、反自反的、对称的、反对称、可传递的。可传递的。例例5 5 全关系是全关系是自反的、对称的、自反的、对称的、可传递的。可传递的。2022-4-30Copyright：张捷：张捷753.4.2 3.4.2 由由关系图、关系矩阵判别关系的性质关系图、关系矩阵判别关系的性质1. 1. 关系矩阵关系矩阵 1 2 3 410000100101011114321M若若 是自反的，则关系矩阵的主对角线上的所有元素是自反的，则关

34、系矩阵的主对角线上的所有元素均为均为1 1。若若 是反自反的，则关系矩阵的主对角线上所有元素是反自反的，则关系矩阵的主对角线上所有元素均为均为0 0。 若若 是对称的，则关系矩阵关于主对角线对称。是对称的，则关系矩阵关于主对角线对称。若若 是反对称的，则关系矩阵中，关于主对角线对称是反对称的，则关系矩阵中，关于主对角线对称的元素不同时为的元素不同时为1 1。 例如，例如，2022-4-30Copyright：张捷：张捷762. 2. 关系图关系图 若若 是对称的，则在关系图中，若两结点之间有边，则是对称的，则在关系图中，若两结点之间有边，则必存在两条方向相反的边。必存在两条方向相反的边。 若若

35、 是反对称的，则在关系图中，任意两个不同的结点是反对称的，则在关系图中，任意两个不同的结点间至多只有一条边。间至多只有一条边。 kaiaja 若若 是自反的，则关系图中每一结点引出一个指向自身是自反的，则关系图中每一结点引出一个指向自身的单边环的单边环( (自环）。自环）。 若若 是反自反的，则关系图中每一结点均没有自环。是反自反的，则关系图中每一结点均没有自环。 若若 是可传递的，则在关系图中，若每当有边由是可传递的，则在关系图中，若每当有边由 指指向向 ，且又有边由，且又有边由 指向指向 ，则必有一条边由，则必有一条边由 指向指向 。 iakajaiajaka2022-4-30Copyri

36、ght：张捷：张捷77123例例6 6 设设 ，下面分别给出集合，下面分别给出集合A A上三个关系的上三个关系的关系图，试判断它们的性质。关系图，试判断它们的性质。 3 , 2 , 1A（2 2） 非自反，也不是反自反，非对称，反对称，非自反，也不是反自反，非对称，反对称， 可传递。可传递。 （3 3） 是自反的，对称的，可传递的，不是反自反，是自反的，对称的，可传递的，不是反自反，也不是反对称。也不是反对称。 解解 （1 1） 是自反的，非对称，不是反对称，不可传递是自反的，非对称，不是反对称，不可传递 但但 , 113 , 2,2 , 1.3 , 112022-4-30Copyright：

37、张捷：张捷78第三章第三章 集合与关系集合与关系(Sets & Relations)小结小结: 本节介绍了本节介绍了关系的基本性质及其判别关系的基本性质及其判别方法。方法。作业作业：P113 （1），（4）2022-4-30Copyright：张捷：张捷7979张捷2022-4-30Copyright：张捷：张捷80第三章第三章 集合与关系集合与关系（Sets and Relations)Sets and Relations) 3.6 3.6 关系的闭包运算关系的闭包运算(Closure Operations)(Closure Operations)3.7 3.7 集合的划分与覆盖集合

38、的划分与覆盖(Partition & Cover of Sets) (Partition & Cover of Sets) 3.8 3.8 等价关系等价关系(Equivalent Relations) (Equivalent Relations) 3.9 3.9 相容关系相容关系(Compatibility(CompatibilityRelations) Relations) 3.10 3.10 序关系序关系(Ordered Relations)(Ordered Relations)3.1 3.1 集合及其运算集合及其运算(Sets & Operations with

39、sets)(Sets & Operations with sets) 3.2 3.2 序偶与笛卡尔积序偶与笛卡尔积(Ordered Pairs & Cartesian Product)(Ordered Pairs & Cartesian Product)3.3 3.3 关系关系 (Relations) (Relations) 3.4 3.4 关系的性质关系的性质(The Propeties of Relations) (The Propeties of Relations) 3.5 3.5 复合关系与逆关系复合关系与逆关系(Compound Relations &

40、; Inverse(Compound Relations & Inverse Relations) Relations)2022-4-30Copyright：张捷：张捷81BABA 3.5 3.5 复合关系与逆关系复合关系与逆关系(C(Compoundompound Relations &Relations & Inverse Relations) Inverse Relations)3.5.1 3.5.1 关系的并、交、补及对称差运算关系的并、交、补及对称差运算3.5.2 3.5.2 逆关系逆关系(Inverse Relations)(Inverse Relation

41、s)3.5.33.5.3 复合关系复合关系 ( (C Compoundompound Relations)Relations)第三章第三章 集合与关系集合与关系(Sets & Relations)2022-4-30Copyright：张捷：张捷82第三章第三章 集合与关系集合与关系(Sets & Relations) 3.5.1 3.5.1 关系的并、交、补及对称差运算关系的并、交、补及对称差运算),( 4221)3 , 3(),2 , 1(21例例1 1 设设 ， 则则3 , 3,4 , 2,2 , 112 , 4,4 , 2,3 , 12.2 , 4,3 , 1,3 , 3

42、,4 , 2,2 , 121.4 , 221,RSR.3 , 3,2 , 121定理定理3.5.1 若若R R与与S S都是集合都是集合A A到集合到集合B B的关的关系，则系，则 RS,RS,R-S, RS,RS,R-S, 均为均为A A到到B B的关系。的关系。.2 , 4,3 , 1,3 , 3,2 , 1212022-4-30Copyright：张捷：张捷833.5.23.5.2 复合关系复合关系 ( (C Compoundompound Relations)Relations)1.1. 复合关系的定义复合关系的定义 定义定义3.5.1 设设 是由是由A A到到B B的关系，的关系，

43、是由是由B B到到C C的的关系，则关系，则 和和 的复合关系是一个由的复合关系是一个由A A到到C C的关系，的关系，用用 表示，定义为：当且仅当存在元素表示，定义为：当且仅当存在元素 ，使得使得 ， 时，有时，有 。 这种由这种由 和和 求复合关系求复合关系 的运算称为关系的运算称为关系的复合运算。的复合运算。 由定义可知由定义可知: : 121212Bbba1cb2ca)(211221)()()(,21BbbCcAaca)()(21cbba2022-4-30Copyright：张捷：张捷84于是复合关系于是复合关系 例例2 2 设设 是由是由 到到 的关的关系。系。 是由是由 B B 到

44、到 的关系。的关系。 分别定义为：分别定义为：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-4-30Copyright：张捷：张捷85 例例3 3 设设 是所有人的集合是所有人的集合 于是复合关系于是复合关系 CBA,|,1的兄弟是baAbaba,|,2的父亲是cbAcbcb21,|,的叔伯是caAcaca2022-4-30Copyright：张捷：张捷862. 2. 关系复合运算的性质关系复合运算的性质定理定理3

45、.5.23.5.2 设设 是由集合是由集合A A到到B B的关系，则的关系，则 例例4 4 以例以例2 2中的关系中的关系 为例，为例， 从关系图，可得从关系图，可得 ,BAII2 , 4,3 , 3,4 , 21111AI11BI2022-4-30Copyright：张捷：张捷87 定理定理3.5.33.5.3 设设 是由是由A A到到B B的关系，的关系， 是由是由B B到到C C的关系，的关系，则有则有证证: (3): (3)反设反设则必存在则必存在 使使 ， 从而从而 使使 故故 且且 所以所以 ，这就与，这就与12121)(domdom(1)(2)(3)221)(ranran2121

46、,则若domran,21,CzAxzx21,By,21zyyx,1rany,2domy21domrany21domran矛盾。矛盾。2022-4-30Copyright：张捷：张捷88 ,2 定理定理3.5.43.5.4 (1) (1) 设设 是由是由A A到到B B的关系，的关系， 是由是由B B到到C C的关系，的关系， 是由是由C C到到D D的关系，则有的关系，则有 (2) (2)设设 是由是由A A到到B B的关系，的关系， 是由是由B B到到C C的关系，的关系，则有则有 (3)(3)设设 是由是由A A到到B B的关系，的关系， 是由是由B B到到C C的关系，的关系，则有则有

47、123)()(32132113)()()(3121321,123)()()(32313212022-4-30Copyright：张捷：张捷89 例例5 5 设设 ， ， , ., . A A到到B B的关系的关系 B B到到C C的关系的关系 C C到到D D的关系的关系 则则A A到到C 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

48、,4 , 3,5 , 2325 , 4,4 , 2,6 , 2)(3215 , 4,4 , 2,6 , 2)(321)()(3213212022-4-30Copyright：张捷：张捷90一般地，若一般地，若 是一由是一由 到到 的关系，的关系， 是由是由 到到 的关系，的关系， 是一由是一由 到到 的关系，则不的关系，则不加括号的表达加括号的表达式式 ， 唯一地表示一由唯一地表示一由 到到 的关系，在计算这一关系时，可以运用结合的关系，在计算这一关系时，可以运用结合律将其中任意两个相邻的关系先结合。律将其中任意两个相邻的关系先结合。特别特别, ,当当 ， 时，时，复合关系复合关系 简记作简记

49、作 ，它也是集，它也是集 A A 上的上的一个关系。一个关系。11A2A22A3AnnA1nAn211A1nAAAAAn121n21n2022-4-30Copyright：张捷：张捷912 3. 3. 求复合关系的几种方法求复合关系的几种方法（1 1）根据复合关系的定义求复合关系）根据复合关系的定义求复合关系 例例5 5中求复合关系采用的就是这种方法。中求复合关系采用的就是这种方法。 又例如又例如 下面的关系图给出了从集合下面的关系图给出了从集合A A到到B B的关系的关系 和从和从B B到到C C的关系的关系121 , 3,3 , 2,2 , 2212022-4-30Copyright：张捷

50、：张捷92（2 2）运用关系矩阵的运算求复合关系）运用关系矩阵的运算求复合关系布尔运算布尔运算其加法和乘法运算定义如下其加法和乘法运算定义如下000111 0+0=0 , 0+1=1+0=1+1=1 ,例如例如 00001101111) 11 ()000() 111 () 10()001 (2022-4-30Copyright：张捷：张捷93 关系矩阵的乘积关系矩阵的乘积 对两个关系矩阵求其乘积时，其运算法则与一般对两个关系矩阵求其乘积时，其运算法则与一般矩阵的乘法是相同的，但其中的加法运算和乘法运矩阵的乘法是相同的，但其中的加法运算和乘法运算应改为算应改为布尔加布尔加和和布尔乘布尔乘。 则则

51、例例6 6 设设 和和 是两个关系矩阵是两个关系矩阵1M2M0010101000011M1010100012M00101010100121MM2022-4-30Copyright：张捷：张捷94 复合关系的关系矩阵复合关系的关系矩阵 定理定理3.5.53.5.5 设设A A、B B、C C均是有限集，均是有限集， 是一由是一由A A到到B B的关系的关系, , 是一由是一由B B到到C C的关系，它们的关系的关系，它们的关系矩阵分别为矩阵分别为 和和 ，则复合关系，则复合关系 的的关系矩阵关系矩阵 121M2M212121MMM2022-4-30Copyright：张捷：张捷952 3 4 1

52、 2 3 1 2 34 , 3 , 2 , 1A4 , 3 , 2B例例7 7 设有集合设有集合 ， ， 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 , 12100101010000143211M1010100014322M001010101001432121M2121MMM2022-4-30Copyright：张捷：张捷96 例例8 8 设设 ，A A上的关系上的关系 试求试求

53、和和 。,dcbaA ,cbdcccabba32因此因此0000110011100101000011000101001000001100010100102MMM 解解 作出的关系矩阵作出的关系矩阵 a b c da b c d根据定理根据定理3.5.53.5.50000110001010010dcbaM,2dcccdbcbbbcaaa2022-4-30Copyright：张捷：张捷97又又 ，所以，所以因此因此2300001100110111100000110011100101000011000101001023MMM,3dcccdbcbabdacaba2022-4-30Copyright：张

54、捷：张捷98 设设 是有限集是有限集A A上的关系，则复合关系上的关系，则复合关系 也是也是A A上的关上的关系，由复合关系的定义，对于任意的系，由复合关系的定义，对于任意的 ，当且仅，当且仅当当 存在，使得存在，使得 ， 时，有时，有 。 反映在关系图上，这意味着，当且仅当在反映在关系图上，这意味着，当且仅当在 的关系图的关系图中有某一结点中有某一结点 存在，使得有边由存在，使得有边由 指向指向 ，且有边，且有边由由 指向指向 时，在时，在 的关系图中有边从的关系图中有边从 指向指向 。 kaja（3 3）利用关系图求复合关系）利用关系图求复合关系n2Aaaji,Aakkiaajkaajia

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

56、在时，在 的关系图中，有边由结点的关系图中，有边由结点 指向指向 。121,nkkkaaaia1ka1ka2ka1nkajaniajaniaiania2022-4-30Copyright：张捷：张捷100解解2例例1010 试利用构造试利用构造 和和 的关系图的方法求例的关系图的方法求例9 9中的中的 和和 。例中例中（4 4）根据）根据 和和 的的关系图直接写出关系图直接写出 和和 中的序偶中的序偶. .（1 1）先）先作出作出 的关系的关系图图（2 2）构造）构造 的关系图。的关系图。在在 的关的关系图中寻系图中寻找长为找长为2 2的的路。路。 （3 3）构造）构造 的关系图。的关系图。在

57、在 的关的关系图中寻系图中寻找长为找长为3 3的的路路. .2323,cbdcccabba2333222022-4-30Copyright：张捷：张捷101例例1111. . 下图给出了集合下图给出了集合 上的关上的关系系 的关系图，试画出关系的关系图，试画出关系 和和 的关系图。的关系图。 6 , 5 , 4 , 3 , 2 , 1A582022-4-30Copyright：张捷：张捷102 3.5.3 3.5.3 逆关系逆关系(Inverse Relations)(Inverse Relations) 定义定义3.5.2 设设 A A 、 B B 是任意集合，是任意集合， 是由是由 A A

58、 到到 B B 的的 关系，定义由关系，定义由 B B 到到 A A 的关系的关系称称 为关系为关系 的逆关系。的逆关系。 ,|,1baab1于是于是 解解 由由 的定义知的定义知 例例1212 设设 ， ， 定义由定义由A A到到B B的关的关系系 ：当且仅当：当且仅当 a a 整除整除 b b 时，有时，有 ，试求，试求 的逆关的逆关系系 。 5 , 3 , 2A10, 6 , 4Bba110, 5,6 , 3,10, 2,6 , 2,4 , 25 ,10,3 , 6,2 ,10,2 , 6,2 , 412022-4-30Copyright：张捷：张捷103 关于关于逆关系我们有如下定理：

59、逆关系我们有如下定理： 定理定理3.5.6 设设 A A 、 B B 是任意集合，是任意集合， 、 和和 都是都是由由 A A 到到 B B 的关系，则有的关系，则有11)(1211121)(121211121)(ABBA1)(, )()(11BA1211121)(（1）（2）（3）（4）（5）（6）2022-4-30Copyright：张捷：张捷104AI1 关于关于逆关系我们有如下定理：逆关系我们有如下定理： 定理定理3.5.7 设设 A A 、 B B、C C 是任意集合，是任意集合， 、 分别是分别是 由由 A A 到到 B B 的关系和由的关系和由 B B 到到 C C 的关系，则有

60、的关系，则有1112121)(12定理定理3.5.8 设设 是集合是集合A A上的二元关系上的二元关系 ， 则则 （1 1） 对称当且仅当对称当且仅当 （2 2） 反对称当且仅当反对称当且仅当证：证：1)(2022-4-30Copyright：张捷：张捷105第三章第三章 集合与关系集合与关系(Sets & Relations)小结小结: 本节主要介绍了本节主要介绍了关系的关系的复合运算与逆复合运算与逆运算。运算。重点掌握关系的重点掌握关系的复合运算及其性质、复合运算及其性质、关系的关系的逆运算的性质逆运算的性质。作业作业：P118119 （1）， （5） ， （6）2022-4-30Copyright：张捷：张捷106106张捷2022-4-30Copyright：张捷：张捷107第三章第三章 集合与关系集合与关系（Sets and Relations)Sets and Relations) 3.6 3.6 关系的闭包运算关系的闭包运算(Closure Operations)(Closure Operations)3.7 3.7 集合的划分与覆盖集合的划分与覆盖(Partitio