离散数学 代数.ppt

1、2020/7/9,1,第三章 集合与关系,本章学习目标：,（1）集合的概念及表示方法,第二篇 集合论,集合是现代数学中的最基本概念,被广泛地应用于数学的各个,学科,在计算机科学理论的研究中,也得到了卓有成效的应用。,本章主要介绍集合的基本概念和基本运算。通过本章学习,读,者应该掌握以下内容：,（2）子集、空集、全集、补集、幂集等概念,（3）集合的基本运算：交、并、补和对称差,（4）有序元组与笛卡尔积,2020/7/9,2,第3章集合与关系,3.1 集合的概念与表示,第二篇 集合论,3.2 子集,3.3 集合的运算,3.4 有序n元组与笛卡尔积,3.5 多重集,2020/7/9,3,第3章集合与

2、关系,3.6关系的概念及表达式,第二篇 集合论,3.7关系的性质,3.8 复合关系及逆运算,3.9关系闭包,3.10等价关系及划分,3.11偏序关系与偏序集,2020/7/9,4,3.1 集合的概念与表示,3.1.1 集合的基本概念,第二篇 集合论 第三章集合与关系,3.1.2 集合的表示,一组明确的、互不相同的事物组成的整体称之为一个集合,组成集合的各个事物称为该集合的元素。,1列举法,（1）全部列举法：写出集合的所有元素,并将他们放在花括号内。,（2）部分列举法：列举集合的部分元素,其他元素可从列举的元,素归纳出来,用省略号代替。,2描述法 通过刻划集合的元素所满足的条件来描述集合,3文氏

3、图法,2020/7/9,5,3.2 子集,1.子集的概念,第二篇 集合论 第三章集合与关系,定义 1 如果集合 A 中的每一个元素都是集合 B 的元,素,则称 A 是 B 的子集,也可以说 A 包含于B,或者 B,包含 A,可记为,AB 或 BA,如果 A 不是 B 的子集,即在 A 中至少有一个元素,不属于 B 时,称B不包含A,记作,BA 或 AB,2020/7/9,6,3.2 子集,2. 集合相等,定理1.1 集合 A 和集合 B 相等的充分必要条件是：,第二篇 集合论 第三章集合与关系,定义 2 如果两个集合 A 和 B 的元素完全相同,则称这,两个集合相等,记作AB。,例如： A1,

4、2,3,4,B3,1,4,2,Cx|x是英文字母且x是元音,Da,e,i,o,u,显然有： AB,CD,AB 且 BA,2020/7/9,7,3.2 子集,3. 真子集,第二篇 集合论 第三章集合与关系,定义 3 如果集合 A 是集合 B 的子集,但 A 和 B 不相,等,也就是说在 B 中至少有一个元素不属于A,则称 A是,B 的真子集,记作 AB 或 BA,例如：集合A1,2,B1,2,3,那么 A 是B 的,真子集。,4. 全集,定义 4 若集合 U 包含我们所讨论的每一个集合,则称,U 是所讨论问题的完全集,简称全集。,2020/7/9,8,3.2 子集,5. 幂集,第二篇 集合论 第

5、三章集合与关系,定义 5 设 A 是有限集,由 A 的所有子集作为元素,而构成的集合称为 A 的幂集,记作(A)。,即(A)X|XA。,在 A 的所有子集中,A 和 这两个子集又叫平凡,子集。,例如：A1,2,3,则,(A),1,2,3,1,2,1,3, 2,3,1,2,3,2020/7/9,9,3.2 子集,5. 幂集,第二篇 集合论 第三章集合与关系,定理 2 设 A 是有限集,|A|=n,则 A 的幂集(A)的基数为2n。,证明：由排列组合知：,又由二项式定理知：,所以可得：|(A)|= 2n,2020/7/9,10,3.3 集合的运算,1 集合的并运算,第二篇 集合论 第三章集合与关系

6、,定义 1 任意两个集合 A、B 的并,记作AB。它也是一,个集合,由所有属于A或者属于B的元素合并在一起而构,成的,即,ABx | xA 或 xB ,例如,Aa,b,c,Ba,b,c,d,e,则,ABa,b,c,d,e,又如,A1,2,3,4,B1,3,5,7,则,AB1,2,3,4,5,7,2020/7/9,11,3.3 集合的运算,第二篇 集合论 第三章集合与关系,1 集合的并运算,用文氏图表示集合之间的并运算：,用平面上的矩形表示全集U。用矩形内的圆表示U中的任,一集合。图中表示了集合 A 和集合 B 的并集。阴影部,分就是AB。,2020/7/9,12,3.3 集合的运算,2 集合的

7、交运算,第二篇 集合论 第三章集合与关系,定义 2 任意两个集合 A、B 的交记作 AB,它也是一个,集合,由所有既属于 A 又属于 B 的元素构成,即,AB x | xA 且 xB,例如,Aa,b,c,Bb,c,d,e,则,ABb,c,又如,A1,2,3,4,5,B1,3,5,7,则 AB1,3,5,2020/7/9,13,3.3 集合的运算,2 集合的交运算,第二篇 集合论 第三章集合与关系,集合交运算的文氏图表示如下,其中阴影部分就是,AB。,2020/7/9,14,3.3 集合的运算,3 集合的补运算,第二篇 集合论 第三章集合与关系,定义 3 设 A、B 是两个集合,A-B 也是一个

8、集合。它是,由属于集合 A 但不属于集合 B 的所有元素组成的。,A-B 称为集合 B 关于 A 的补集(或相对补)。即,-Bx|x且 xB,A-B 也称为集合 A 和 B 的差集。,例如, a,b,c,d ,B a,b,e,f ,则 -Bc,2020/7/9,15,3.3 集合的运算,3 集合的补运算,第二篇 集合论 第三章集合与关系,定义 4 设 U 是全集,A 是 U 的一个子集,称 U-A 为,A关于全集的补集,也叫做 A 的绝对补集,简称为补,集。记作 A。,即： U-A A x | x且 x,例如,Ux | x是山东大学计算机学院的学生,Ax | x是山东大学计算机学院的女学生,则

9、 Ax | x是山东大学计算机学院的男学生,2020/7/9,16,3.3 集合的运算,3 集合的补运算,第二篇 集合论 第三章集合与关系,集合差、补运算的文氏图表示如下,其中左图阴影,部分就是 A-B,右图阴影部分就是 A 。,2020/7/9,17,3.3 集合的运算,4 集合运算的性质,第二篇 集合论 第三章集合与关系,由前面所述集合并运算的定义可知,运算具有以下性质：,（1）幂等律：AAA AAA,（2）交换律：ABBA ABBA,（3）结合律：(AB)CA(BC),(AB)CA(BC),（4）分配律：A（BC）（AB）（AC）,A（BC）（AB）（AC）,2020/7/9,18,3.

10、3 集合的运算,4 集合运算的性质,第二篇 集合论 第三章集合与关系,（5）摩根律：（AB）= AB,（AB）= AB,（6）吸收律：A（AB）A,A（AB）A,（7）零律： AUU A,（8）单位律：AA AUA,（9）补律： AAU AA,2020/7/9,19,3.3 集合的运算,4 集合运算的性质,第二篇 集合论 第三章集合与关系,（10）反身律：（A）= A,（11）摩根律：U,（12）摩根律：U = ,（13） A-BAB,A-BA-（AB）,2020/7/9,20,3.3 集合的运算,5 集合的对称差,第二篇 集合论 第三章集合与关系,定义 5 设 A、B 是两个集合,集合 A

11、和 B 的对称差,记作AB,它是一个集合,其元素或属于 A,或属于B,但不能既属于 A 又属于 B。即：,A B (AB)-(AB),例如,Aa,b,c,d,Ba,c,e,f,g,那么 A B b,e,d,f,g,2020/7/9,21,3.3 集合的运算,5 集合的对称差,第二篇 集合论 第三章集合与关系,例如,Aa,b,c,d,Ba,c,e,f,g,那么 A B b,e,d,f,g,2020/7/9,22,3.3 集合的运算,5 集合的对称差,第二篇 集合论 第三章集合与关系,由对称差运算的定义易得下列性质：,（1）A A,（2）A A,（3）A ,（4）A BB A,（5）（A B） C

12、A （B C）,（6）A B(A-B)(B-A),2020/7/9,23,3.4 有序 n 元组与笛卡尔积,1 有序n元组,定义 1 两有序对 , 是相等的,当且仅当,第二篇 集合论 第三章集合与关系,由两个固定次序的个体 x,y 组成的序列称为序偶或,有序对,记为 ,其中 x,y 分别称为序偶的第,一、二分量（或称第一、二元素）。,a = c,b = d；记作 = 。,2020/7/9,24,3.4 有序 n 元组与笛卡尔积,2 笛卡尔积,第二篇 集合论 第三章集合与关系,定义 2 给定两个集合 A 和 B,如果序偶的第一个分量,是 A 中的一个元素,第二个分量是 B 中的一个元素,则所有这

13、种序偶的集合称为集合 A 和 B 的笛卡儿积,简称为卡氏积,记为 AB,即：,AB=xAyB。,2020/7/9,25,3.4 有序 n 元组与笛卡尔积,2 笛卡尔积,第二篇 集合论 第三章集合与关系,例（1）A=a,b,B=c,d,求AB。,（2）A=a,b,B=c,d,求BA。,解：（1）AB=a,bc,d,=, 。,（2）BA=c,da,b,=,。,2020/7/9,26,3.4 有序 n 元组与笛卡尔积,2 笛卡尔积,第二篇 集合论 第三章集合与关系,例（3）A=a,b,B=1,2,C=c,求（AB）C和A（BC）。,解：（AB）=a,b1,2,=, 。,（AB）C= , c,=,c,

14、c,c,c,BC=1,2c=,。,A（BC）=,。,2020/7/9,27,3.4 有序 n 元组与笛卡尔积,3 笛卡尔积性质,定理 2 设A,B,C为任意 3 个集合,且 C,则有,第二篇 集合论 第三章集合与关系,定理 1 设A,B,C为任意 3 个集合,则有,（1）A（BC）=（AB）（AC）,（2）A（BC）=（AB）（AC）,（3）（AB）C=（AC）（BC）,（4）（AB）C=（AC）（BC）,AB （AC BC）（CA CB）,2020/7/9,28,3.5 多重集,一般地如果有一组事物,其中可以有某些事物不加区别（或说,第二篇 集合论 第三章集合与关系,某些事物可重复出现多次,

15、且出现几次就看作是几个事物）这组,物构成的整体就称为一个多重集。即集合中的元素可以重复出现,在一个多重集 A 中,元素 a 出现的次数（可以是整数,也可以是无,出现的次数称为重复度。,穷或零）,称为 a 在 A中的重复度,记为 MA(a)。,例如：A=a,b,b,c,a,d,b,则,MA(a)=2, MA(b)= , MA(c)= 1, MA(e)=0,显然,一个多重集 A,如果其元素的重复度都为 1 和 0,则,该多重集就是通常意义下的集合。,2020/7/9,29,3.6 关系的概念和表示,1. 二元关系的概念,定义 2 设 R 是二元关系,由 R 的所有 x 组成的集合称,第二篇 集合论

16、 第三章集合与关系,定义 1 设 A,B 是两个集合,R 是笛卡儿积 AB 的任一子集,则,称 R 为从 A 到 B 的一个二元关系,简称关系。特别当 A = B 时,则称 R 为 A 上的二元关系（或 A 上的关系）。,为 R 的定义域,记作 domR,即,domR =x|y（yBR）,由 R 的所有 y 组成的集合称为 R 的值域,记作 ranR,即 ranR =y|x（xAR）,2020/7/9,30,3.6 关系的概念和表示,1. 二元关系的概念,第二篇 集合论 第三章集合与关系,例如 设 A=a,b,c,d,e,B=1,2,3,R=,求：R的定义域和值域。,解： domR =a,b,

17、c, ranR =2,3,例如 设 A=1,3,5,7,R 是 A 上的二元关系,定义为：,当 a,bA 且 aR,求：R 和它的定义域、值域。,解：R=,domR =1,3,5, ranR =3,5,7,2020/7/9,31,3.6 关系的概念和表示,1. 二元关系的概念,第二篇 集合论 第三章集合与关系,定义 3 设IA为集合 A 上的二元关系,且满足,IA=xA,则称IA为集合 A 上的恒等关系。,例如 设 A=a,b,c,d,e,则,IA= ,2020/7/9,32,3.6 关系的概念和表示,2. 二元关系的表示,第二篇 集合论 第三章集合与关系,（1）关系的矩阵表示法,设给定集合A

18、=a1,a2,an,集合B=b1,b2,bm,R 为,从 A 到 B 的一个二元关系,构造一个 nm,矩阵。用集合 A 的元素标注矩阵的行,用集合 B 的元,素标注矩阵的列,对于aA 和 bB,若R,则在行 a 和列 b 交叉处标 1,否则标 0。这样得到的,矩阵称为 R 的关系矩阵。,2020/7/9,33,3.6 关系的概念和表示,2. 二元关系的表示,第二篇 集合论 第三章集合与关系,（1）关系的矩阵表示法,例如 A=1,2,3,4,B=5,6,7,R=,写出 R 的关系矩阵。,解： R 的关系矩阵如下所示：,2020/7/9,34,3.6 关系的概念和表示,2. 二元关系的表示 （1）

19、关系的矩阵表示法 例如 设A=1,2,3,4,R=,。 写出 A 上的关系 R 的关系矩阵。 解： R 的关系矩阵如下所示：,第二篇 集合论 第三章集合与关系,2020/7/9,35,3.6 关系的概念和表示,2. 二元关系的表示,第二篇 集合论 第三章集合与关系,（2）关系的图表示法,有限集的二元关系可以用有向图来表示,设集合,A=a1,a2,an,集合B=b1,b2,bm,R 为从A 到 B,的一个二元关系。首先在平面上作出 n 个结点分别记,作a1,a2,an,然后另外作出 m 个结点分别记作,b1,b2,bm,如果aA、bB且R,则自结点 a 到,结点 b 作出一条有向弧,其箭头指向

20、b。如果R,则结点 a 和结点 b 之间没有线段联结。用这种方法得,到的图称为R的关系图。,2020/7/9,36,3.6 关系的概念和表示,2. 二元关系的表示,第二篇 集合论 第三章集合与关系,（2）关系的图表示法,例如 A=1,2,3,4,B=5,6,7,R=,作出 R 的关系图。,解： R 的关系图,如图所示：,2020/7/9,37,3.6 关系的概念和表示,2. 二元关系的表示,第二篇 集合论 第三章集合与关系,（2）关系的图表示法,例如 设A=1,2,3,4,R=,画出 A 上的关系 R 的关系图。,解： R 的关系图,如图所示：,2020/7/9,38,3.7 关系的性质,1.

21、关系的性质,定义 2 设 R 是集合 A 上的二元关系,如果对于每个,第二篇 集合论 第三章集合与关系,（1）关系的自反性和反自反性,定义 1 设 R 是集合 A 上的二元关系,如果对于每个,xA,都有R,则称二元关系 R 是自反的.,R 在 A 上是自反的 x（xAR）,xA,都有R,则称二元关系 R 是反自反的。,R 在 A 上是反自反的 x（xAR）,2020/7/9,39,3.7 关系的性质,1.关系的性质,定义 4 设 R 是集合 A 上的二元关系,如果对于每个x,yA,第二篇 集合论 第三章集合与关系,（2） 关系的对称性和反对称性,定义 3 设 R 是集合 A 上的二元关系,如果

22、对于每个x,yA,当R,就有R,则称二元关系 R 是对称的。,R是对称的xy（xAyARR）,当R 和 R 时,必有x=y,则称二元关系 R 是,反对称的。,R 是反对称的, xy(xAyARRx=y),2020/7/9,40,3.7关系的性质,1.关系的性质,第二篇 集合论 第三章集合与关系,（3）关系的传递性,定义 5 设 R 是集合 A 上的二元关系,如果对于任意,x,y,zA,当R,R,就有R,则称二元关系 R 在 A 上是传递的。,R 是传递的xyz(xAyAzA,RR,R),2020/7/9,41,3.7 关系的性质,例如 设A=a,b,c,R,S,T 是 A 上的二元关系,其中,

23、第二篇 集合论 第三章集合与关系,R=,S=, ,T=,给出 A 上 R,S,T 的关系性质。,解 根据关系性质的定义可知,R 具有自反性、反对称性和传递性；,S 具有反自反性和对称性；,T 具有反自反性、反对称性和传递性。,2020/7/9,42,3.7 关系的性质,2.关系性质的判定,第二篇 集合论 第三章集合与关系,（1）自反性的判定方法,设 R 是 A 上的二元关系,则 R 在 A 上是自反的,当且仅当IA R。,证明：先证必要性。,任取,由于 R 在 A 上是自反的,则有 IAx,yAx=yR,从而证明了IA R。,再证充分性。任取xA,有,xA IAR,因此,R 在 A 上是自反的

24、。,2020/7/9,43,3.7 关系的性质,2.关系性质的判定,第二篇 集合论 第三章集合与关系,（1）自反性的判定方法,若 R 是 A 上的二元关系,并且是自反的,当且仅,当 R 的关系矩阵中对角元全为 1。,例如 设A=1,2,3,4,R=,由 R 关系矩阵可知 R 是自反的。,2020/7/9,44,3.7 关系的性质,2.关系性质的判定,第二篇 集合论 第三章集合与关系,（1）自反性的判定方法,若 R 是 A 上的二元关系,并且是自反的,当且仅,当 R 的关系图上每一点都有自环。,例如 设A=a,b,c,d,R=,由 R 关系图可知 R 是自反的。,2020/7/9,45,3.7

25、关系的性质,2.关系性质的判定,由于 ,R,即IAR=,所以 R 是反自反的。,第二篇 集合论 第三章集合与关系,（2）反自反性的判定方法,若 R 是 A 上的二元关系,并且是反自反的,当且,仅当IAR=。,例如 设集合 A=a,b,c,d,A 上的二元关系,R=,讨论 R 的反自反性质。,2020/7/9,46,3.7 关系的性质,2.关系性质的判定,第二篇 集合论 第三章集合与关系,（2）反自反性的判定方法,若 R 是 A 上的二元关系,并且是反自反的,当且仅,当 R 的关系矩阵中对角元全为0。,例如 设集合 A=a,b,c,d,A 上的二元关系,R=,由关系矩阵可知,关系 R 是反自反的

26、。,2020/7/9,47,3.7 关系的性质,2.关系性质的判定,第二篇 集合论 第三章集合与关系,（2）反自反性的判定方法,若 R 是 A 上的二元关系,并且是反自反的,当且仅,当 R 的关系图中不存在自环。,例如 设集合 A=a,b,c,d,A 上的二元关系,R=,由关系图可知,关系 R 是反自反的。,2020/7/9,48,3.7 关系的性质,2.关系性质的判定,第二篇 集合论 第三章集合与关系,（3）对称性的判定方法,设 R是 A 上的二元关系,则 R 在 A 上是对称的当,且仅当 R=R1。,例如 设集合 A=a,b,c,d,A 上的二元关系,R=,讨论 R 的对称性。,由于 R1

27、=,R=R1,所以,关系 R 是对称的。,2020/7/9,49,3.7 关系的性质,2.关系性质的判定,第二篇 集合论 第三章集合与关系,（3）对称性的判定方法,设 R是 A 上的二元关系,并且是对称的当且仅当,R 的关系矩阵是对称的。,例如 设集合 A=a,b,c,d,A 上的二元关系,R=,由 R 的关系矩阵可知 R 是对称的。,2020/7/9,50,3.7 关系的性质,2.关系性质的判定,第二篇 集合论 第三章集合与关系,（3）对称性的判定方法,设 R 是 A 上的二元关系,并且是对称的,当且仅,当 R 的关系图中不同顶点间的弧线成对出现。,例如 设集合 A=a,b,c,d,A 上的

28、二元关系,R=,由 R 的关系图可知 R 是对称的。,2020/7/9,51,3.7 关系的性质,2.关系性质的判定,第二篇 集合论 第三章集合与关系,（3）反对称性的判定方法,设 R 是 A 上的二元关系,则 R 在 A 上是反对称,的当且仅当 RR1IA。,例如 设集合 A=a,b,c,d,A上的二元关系 R 定义为：,R=,讨论 R 的反对称性。,由于 R1=,而 RR1=IA,所以 R是反对称的。,2020/7/9,52,3.7 关系的性质,2.关系性质的判定,第二篇 集合论 第三章集合与关系,（3）反对称性的判定方法,设 R 是 A 上的二元关系,并且是反对称的,当且,仅当 R 的关

29、系矩阵中关于对角线的对称元不同时为1。,例如 设集合 A=a,b,c,d,A上的二元关系 R 定义为：,R=,2020/7/9,53,3.7 关系的性质,2.关系性质的判定,第二篇 集合论 第三章集合与关系,（3）反对称性的判定方法,设 R 是 A 上的二元关系,并且是反对称的,当且,仅当 R 的关系图中任意两点之间至多有一条弧。,例如 设集合 A=a,b,c,d,A上的二元关系 R 定义为：,R=,2020/7/9,54,3.8 复合关系与逆关系,1.关系的交、并、差、补运算,例如 设 X=1,2,3,4,5,A,B 是定义在 X 上的关系,并,第二篇 集合论 第三章集合与关系,因为关系是有

30、序对的集合,所以可以进行集合间的,运算。,且 A= x与y的差能被2整除,B=x与y的差,为正且能被3整除。,求：AB,AB,A-B,B-A, A。,2020/7/9,55,3.8 复合关系与逆关系,1.关系的交、并、差、补运算,解：A=,第二篇 集合论 第三章集合与关系,B=,AB=,AB=,A-B=,B-A=,2020/7/9,56,3.8 复合关系与逆关系,1.关系的交、并、差、补运算,解：A=,第二篇 集合论 第三章集合与关系,B=,A=XX-A,=1,2,3,4,51,2,3,4,5,-,=,2020/7/9,57,3.8 复合关系与逆关系,2.复合关系,（1）基本概念,第二篇 集合

31、论 第三章集合与关系,定义 1 设 R 是从集合 A 到集合 B 上的二元关系,S是,从集合 B 到集合 C 上的二元关系,则 RS 称为 R 和,S 的复合关系,表示为:,RS=|xAzC,y(yBRS),求解复合关系的运算称为复合运算。,2020/7/9,58,3.8 复合关系与逆关系,2.复合关系（1）基本概念,例如 A=1，2，3，4，B=3，5，7，C=1，2，3，,第二篇 集合论 第三章集合与关系,R=,S=,则 RS=,。,如图所示：,2020/7/9,59,3.8 复合关系与逆关系,2.复合关系（1）基本概念,例如 设 R，S 都是 A 上的关系，A=1，2，3，4。,第二篇

32、集合论 第三章集合与关系,R=,S=,，即 S 为 A 上的,恒等关系。,则 RS=SR=R。,如图所示：,2020/7/9,60,3.8 复合关系与逆关系,2.复合关系（1）基本概念,复合关系可以通过矩阵乘运算求得。,第二篇 集合论 第三章集合与关系,设 R 是从 A 到 B 的关系，S 是从 B 到 C 的关系，,其中A=a1,a2,am,B=b1,b2,bn,C=c1,c2,ct。,而 MR，MS 和 MR S分别为关系 R，S 和 RS 的关系矩,阵，则有 MRS= MRMS。,2020/7/9,61,3.8 复合关系与逆关系,2.复合关系,（2）复合关系的性质,第二篇 集合论 第三章

33、集合与关系,设 R 是从集合 A 到集合 B 上的二元关系，S 是从集合,B 到集合 C 上的二元关系，T 是从集合 C 到集合 D 上,的二元关系，则有：,1）R（ST）=RSRT,2）R（ST）RSRT,3）（RS）T= RTST,4）（RS）TRTST,2020/7/9,62,3.8 复合关系与逆关系,2.复合关系,（2）复合关系的性质,第二篇 集合论 第三章集合与关系,设 R 是从 A 到 B 的关系，S 是从 B 到 C 的关系，,T 是从 C 到 D 的关系。,则复合运算满足结合性，即,R（ST）=（RS）T。,2020/7/9,63,3.8 复合关系与逆关系,2.复合关系,（3）

34、关系的幂运算,第二篇 集合论 第三章集合与关系,定义 2 设 R 是从 A 上的关系，n 为整数，关系 R 的,n 次幂定义如下：,1）R0=xA=IA；,2）Rn+1=RnR。,从关系 R 的 n 次幂定义，可得出下面的结论：,1）Rn+m=RnRm；,2）（Rn）m=Rnm。,2020/7/9,64,3.8 复合关系与逆关系,3.逆关系,（1）基本概念,第二篇 集合论 第三章集合与关系,定义 4 设 R 是从集合 A 到集合 B 的二元关系，如果,将 R 中每一序偶的第一元素和第二元素的顺序互换，所,得到的集合称为 R 的逆关系，记为R-1。,即 R-1=R,求解逆关系的运算称为关系的逆运

35、算,2020/7/9,65,3.8 复合关系与逆关系,3.逆关系,（2）逆关系的性质,第二篇 集合论 第三章集合与关系,设 R，S 和 T 都是从 A 到 B 的二元关系，则下列各式,成立：,1）(R)-1)-1 = R,2）(RS)-1 = R-1S-1,3）(RS)-1= R-1S-1,4）(AB)-1 =BA,5）(R)-1= （R-1）（这里R=AB-R）,6）(R-S)-1= R-1-S-1,2020/7/9,66,3.8 复合关系与逆关系,3.逆关系,（3）逆关系和复合关系,第二篇 集合论 第三章集合与关系,设 R 是从 A 到 B 的二元关系，S 是从 B 到 C 的二元关系，,

36、则下面的式子成立：,(RS)-1=S-1R-1,证明: (RS)-1 RS, y(yBRS）, y(yBS-1R-1）, S-1R-1,所以，(RS)-1=S-1R-1。,2020/7/9,67,3.9 关系的闭包,1.基本概念,定义 1 设 R 是集合 A 上的二元关系，如果有另一个关,第二篇 集合论 第三章集合与关系,系 R 满足：,（1） R是自反的（对称的、传递的）；,（2） R R；,（3）对于任何自反的（对称的、传递的）关系 R”，如果,有 R”R，就有 R”R。,则称关系 R 为 R 的自反（对称、传递）闭包。记为：,r(R)（s(R),t(R)）。,2020/7/9,68,3.

37、9 关系的闭包,2.闭包的求法,（1）自反闭包的求法,（2）对称闭包的求法,第二篇 集合论 第三章集合与关系,设 R 是集合 A 上的二元关系，则:,r（R）=RIA,设 R 是集合 A 上的二元关系，则:,s（R）=RR1,2020/7/9,69,3.9 关系的闭包,2.闭包的求法,（3）传递闭包的求法,第二篇 集合论 第三章集合与关系,设 R 是集合 A 上的二元关系，则：,t（R）=RR2R3,设A=a1，a2，an，R 是集合 A 上的二元关系，,则存在一个正整数 kn，使得：,t（R）= RR2R3Rk,2020/7/9,70,3.9 关系的闭包,3.闭包的性质,（1）设 R 是非空

38、集合 A 上的关系，则：,第二篇 集合论 第三章集合与关系,1）R 是自反的，当且仅当 r（R）=R；,2）R 是对称的，当且仅当 s（R）=R；,3）R 是传递的，当且仅当 t（R）=R。,（2）设 R，S 是非空集合 A 上的关系，且 RS，则：,1）r（R） r（S）； 2）s（R） s（S）； 3）t（R） t（S）。,2020/7/9,71,3.9 关系的闭包,3.闭包的性质,（3）设 R 是非空集合 A 上的关系，则：,第二篇 集合论 第三章集合与关系,1）rs（R）= sr（R）；,2）rt（R）= tr（R）；,3）ts（R） st（R）。,2020/7/9,72,3.10等价

39、关系与集合的划分,1.等价关系,定义 1 设 R 是非空集合 A 上的二元关系，如果有 R 是,例如 设集合 A=a,b,c,d,，,第二篇 集合论 第三章集合与关系,自反、对称和传递的，则称 R 是集合 A 上的等价关系,R=,。,验证 R 是 A 上的等价关系。,2020/7/9,73,3.10等价关系与集合的划分,1.等价关系,首先写出关系 R 关系矩阵如下：,第二篇 集合论 第三章集合与关系,R=, ,2020/7/9,74,3.10 等价关系与集合的划分,1.等价关系,然后根据关系矩阵讨论关系的性质。,（1）关系矩阵主对角线元素都是1，可知 R 是自,综合(1)(2)(3) 故 R

40、是 A 上的等价关系。,第二篇 集合论 第三章集合与关系,（2）关系矩阵是对称的，故 R 是对称的。,（3）从 R 的表达式中，逐个检查序偶，,如，R，有R。,，R，有R，,，R，有R，。,故 R 是传递的。,2020/7/9,75,3.10 等价关系与集合的划分,2.等价类,定义 2 设 R 是非空集合 A 上的等价关系，对于任何,第二篇 集合论 第三章集合与关系,aA，集合 aR=xxA且R称为元素 a 形成,的 R 等价类。,等价类的性质：,若 R 是非空集合 A 上的等价关系，对于 a，bR，,有R 当且仅当 aR=bR。,2020/7/9,76,3.10等价关系与集合的划分,3.商集

41、,定义 3 设 R 是集合 A 上的等价关系，等价类集合,第二篇 集合论 第三章集合与关系,aRaA称作 A 关于 R 的商集，记作 A/R。,例如 设集合A=a,b,c,d，R 是集合 A上的等价关系，定义为：,R=,。则：,aR=a,d=dR,bR=b,c=cR,A/R=aR , bR=a,d, b,c,2020/7/9,77,3.10 等价关系与集合的划分,4.划分,定义 4 设 S 是一个集合，A=A1，A2，Am，如果,第二篇 集合论 第三章集合与关系,A 满足下列条件：,（1）任意Ai （i=1,2,m）,（2）对所有i,j（i=1,2,m,j=1,2,m），如果ij，,则AiAj

42、=。,（3）A1A2Am=A,则称 A=A1，A2，Am为集合 A 的一个划分，而A1，,A2，Am称为这个划分的块。,2020/7/9,78,3.10等价关系与集合的划分,5.划分与等价关系,（1）设 R 是非空集合 A 上的等价关系，确定了 A 的一个划分，,第二篇 集合论 第三章集合与关系,该划分就是商集 A/R。,（2）集合 A 的一个划分确定 A 上的一个等价关系。,（3）设 R1 和 R2 是非空集合 A 上的等价关系，,则 R1 = R2 当且仅当 A/R1 =A/R2 。,2020/7/9,79,3.10 等价关系与集合的划分,5.划分与等价关系,例如 设集合A=1,2,3,4

43、,5上的等价关系 R 定义为：,第二篇 集合论 第三章集合与关系,R=,则它所确定的等价类为：1R=2R=3R，4R=5R,所以，它所产生的A上的划分为：,A/R=1R ，4R=1,2,3,4,5,2020/7/9,80,3.11偏序关系与偏序集,1.偏序关系的定义,定义 1 设 R 是集合 A 上的一个二元关系，如果 R 是自,例如 设 R 是集合A=2,3,6,8上的关系，R=x整除y，,第二篇 集合论 第三章集合与关系,反的、反对称的和传递的，则称 R 是 A 上的一个偏序,关系，并将它记为“”。序偶称作偏序集。,验证 R 是偏序关系。,由定义可知R=,容易验证 R 是自反的、反对称的和

44、传递的。,故它是偏序关系。,2020/7/9,81,3.11偏序关系与偏序集,2.拟序关系的定义,定义 2 设 R 是集合 A 上的一个关系，如果 R 是反自反,第二篇 集合论 第三章集合与关系,的和传递的，则称 R 是 A 上的一个拟序关系。一般用,符号“”表示拟序关系。,设 R 是集合 A 上的拟序关系，则 R 是反对称的。,逆序关系与偏序关系之间存在下述关联：,设 R 是集合 A 上的关系，则有：,（1）如果 R 是一个拟序关系，则 R 的自反闭包,r（R）=RIA 是一个偏序关系。,（2）如果 R 是一个偏序关系，则 R-IA 是一个拟序关系,2020/7/9,82,3.11 偏序关系

45、与偏序集,3.哈斯图,（1）定义 3 设 R 是集合 A 上的偏序关系，如果x,yA,第二篇 集合论 第三章集合与关系,R，xy 且在 A 中不存在 z，使得R、,R，则称元素 y 盖住元素 x。,（2）哈斯图的画法,假设是一偏序集,1）用圆点表示集合中的元素。,2）如果 c 盖住 a，则 c 放在 a 的上方，且 a,c,之间连一条线。,这样得到的图，称为的Hasse图。,2020/7/9,83,3.11 偏序关系与偏序集,3.哈斯图,例如 设 A=a，b，c，R 是 A 的幂集上的包含关系，则 R 是偏序关系，,第二篇 集合论 第三章集合与关系,画出 R 的哈斯图。因为,R=,，,由上述偏

46、序关系可以确定集合中,元素的盖住关系，并画出哈斯图：,2020/7/9,84,3.11 偏序关系与偏序集,4.全序关系,定义 4 设是偏序集合，如果 A 中任意元素a,b，,第二篇 集合论 第三章集合与关系,总有ab 或者ba，则称 是全序关系，称为全,序集。,定义 5 设是偏序集合，B 是 A 的子集且,是全序集，则称子集 B 为链。,定义 6 设是偏序集合，B 是 A 的子集，如果 B,中任意两个元素都是没有关系的，则称子集 B 为反链。,2020/7/9,85,3.11 偏序关系与偏序集,4.特殊元素,（1）极大元、极小元,第二篇 集合论 第三章集合与关系,定义 7 设是偏序集合，且 B

47、 是 A 的子集，对于,B中的一个元素b，如果 B 中不存在任何元素 x，满足,bx 且 bx，则称 b 为 B 的极大元。,同理，对于 bB，如果 B 中不存在任何元素 x，满,足 bx 且 xb，则称 b 为 B 的极小元。,2020/7/9,86,3.11 偏序关系与偏序集,5.特殊元素,（2）最大元、最小元,第二篇 集合论 第三章集合与关系,定义 8 设是偏序集合，且 B 是 A 的子集，如,果有某一个元素 bB，使得 B 中任何元素 x，都满足,xb，则称 b 为 的最大元。同理，对于 bB，,如果任意元素 xB，都有 bx 成立，则称 b 为,的最小元。,设是偏序集合，且 B 是

48、A 的子集，若 B 有最,大（最小）元，则必是唯一的。,2020/7/9,87,3.11 偏序关系与偏序集,5.特殊元素,（3）上界、下界,第二篇 集合论 第三章集合与关系,定义 9 设是偏序集合，且 B 是 A 的子集，如,果有某一个元素 aA，使得 B 中任何元素 x，都满足,xa，则称 a 为子集 B 的上界。同理，对于aA，如,果任意元素 xB，都有 ax 成立，则称 a 为子集 B,的下界。,2020/7/9,88,3.11 偏序关系与偏序集,5.特殊元素,（4）上确界、下确界,第二篇 集合论 第三章集合与关系,定义 10 设是偏序集合，且B是A的子集，元素a,是集合 B 的任意上界

49、，如果对于 B 的所有上界 x 都有,ax，则称 a 为 B 的最小上界（上确界），记作:,supB。同理，b 为集合 B 的任意下界，若对 B 的所有,下界 y 都有 yb，则称 b 为子集 B 的最大下界（下确,界），记作inf B。,2020/7/9,89,3.11 偏序关系与偏序集,5.特殊元素,B 的极大元是 a,b,a,c,例如 设A=a，b，c，R 是 A 幂集上的包含关系，且 R 是偏序关,第二篇 集合论 第三章集合与关系,系，其哈斯图如下，请给出子集B=a,a,ba,c的特殊元素。,极小元是 a,上界是 a,b,c,下界是 a,上确界是 a,b,c,下确界是 a,2020/7

50、/9,90,4.1 函数,1.函数的基本概念,定义 1 设 X，Y 是两个集合，f 是一个从 X 到 Y 的,第二篇 集合论 第四章函数,关系。如果对于每一个 xX，都有唯一的 yY，使得,f，则称关系 f 为 X 到 Y 的函数，记作f:XY。,X 称作f的定义域，Y 称作 f 的值域。x 为函数的自变,X 称作f的定义域，Y 称作 f 的值域。x 为函数的自变,f（x），由所有函数值组成的集合称为函数的值域。,2020/7/9,91,4.1 函数,1.函数的基本概念,例如 判别下列关系中哪个能构成函数。,第二篇 集合论 第四章函数,（1）X=1，2，3，4，Y=4，5，6，当xX，yY，且

51、xy时,有f,因为对于元素 2X，有f,f,f，,这说明 X 中元素 2 与 Y 中的 3 个元素对应,所以 f 不是 X 到 Y 的函数。,2020/7/9,92,4.1 函数,1.函数的基本概念,例如 判别下列关系中哪个能构成函数。,第二篇 集合论 第四章函数,（2）设 N 是自然数的集合，f 是 N 上的二元关系，对,于x,yN，x+y100。,解: f 不是 X 到 Y 的函数。,因为 x 不能取定义域中的所有值，且 x 对应多个,y，故关系 f 不能构成函数。,2020/7/9,93,4.1 函数,1.函数的基本概念,例如 判别下列关系中哪个能构成函数。,第二篇 集合论 第四章函数,

52、（3）假设X=1，2，3，4，5，6，7，8，9，Y=0，1，,f为 X 到 Y 的关系，对于 X 中的任意元素 x，当 x,解: f能构成函数。,因为对于每一个 xX，都有唯一 yY 与它对应。,2020/7/9,94,4.1 函数,1.函数的基本概念,定义 2 设函数f：XY，g：TW，如果X=T，Y=W，且对,第二篇 集合论 第四章函数,于所有xX 和 xT 有 f（x）=g（x），则称函数 f 和,于所有xX 和 xT 有 f（x）=g（x），则称函数 f 和,g 相等，记作 f=g。,任意两有限集合|X|=n，|Y|=m，可以确定2nm个关系，,但这些关系中并不都是函数。只有|Y|X

53、|关系可以构成函数。,2020/7/9,95,4.1 函数,1.函数的基本概念,例如 设X=a,b,c，Y=0,1，XY=,第二篇 集合论 第四章函数,，XY有26个子集形成关系，但只有23个子集定义的,关系为从 X 到 Y 的函数。这 8 个函数如下所示：,f0=, f1=,f2=, f3=,f4=, f5=,f6=, f7=,2020/7/9,96,4.1 函数,1.函数的基本概念,例如 设 X 和 Y 都为有限集，且|X|=m，|Y|=n，问 X,第二篇 集合论 第四章函数,到 Y 可以定义多少种不同的函数？,解：因为从 X 到 Y 的每一个函数的定义域都是 X，,在这些函数中，每一个恰

54、有 m 个序偶。,另外，对于任何 xX，可以有 Y 中的 n 个元素中,的任何一个作为它的像，,所以共有 nm 个不同的函数。,2020/7/9,97,4.1 函数,1.特殊函数,（1）满射函数,第二篇 集合论 第四章函数,定义 3 设函数f：XY，如果函数的值域为 Y，即 Y 中,的每一个元素是 X 中一个或多个元素的映像，则称f为,X 到 Y 的满射函数。,设f：XY是满射函数，即对于任意的 yY，必存在,xX 使得 f（x）=y成立。,例如：A=1，2，3，4，B=a，b，c，,如果 f：AB 为 f(1)=a,f(2)=c,f(3)=b,f(4)=c，,则 f 是满射。,2020/7/

55、9,98,4.1 函数,1.特殊函数,（2）单射函数,第二篇 集合论 第四章函数,定义 4 设函数 f：XY，如果对于 X 中的任意两个元,素x1和x2，当x1x2时，都有f（x1）f（x2），则称f为 X,到 Y 的单（入）射函数。,例如：A=1，2，3，B=a，b，c，d，,如果f：AB 为 f(1)=a，f(2)=c，f(3)=b，,则 f 是单射。,2020/7/9,99,1.1 函数,1.特殊函数,（3）双射函数,第二篇 集合论 第四章函数,定义 5 设函数f：XY，如果 f 既是满射又是单射函数，,则称这个函数为双射函数。,例如：A=1，2，3，B=a，b，c ，,如果 f：AB

56、为 f(1)=a，f(2)=c，f(3)=b，,则 f 既是单射又是满射，,所以是双射函数。,2020/7/9,100,4.1函数,1.特殊函数,例如 判定下列函数是单射、满射函数，还是双射函数。,第二篇 集合论 第四章函数,（1）集合A=1，2，3，4，B=a，f 是 A 到 B 的函,数，且 f(1)=a，f(2)=a，f(3)=a，f(4)=a。,解: f 是 A 到 B 的满射函数。,（2）集合A=1，2，3，B=a，b，c，d，f 是 A 到B,的函数，且 f（1）=a，f（2）=d，f（3）=c。,解: f 是 A 到 B 的单射函数。,2020/7/9,101,4.1 函数,1.

57、特殊函数,例如 判定下列函数是单射、满射函数，还是双射函数。,第二篇 集合论 第四章函数,（3）设 A 是正整数集合，B 是正偶数集合，f是 A 到,B 的函数，且对于任意的正整数 n 有 f(n)=2n。,解: f 是 A 到 B 的双射函数。,（4）设 I 是整数集合，N 是自然数集合，f 是 I 到,N 的函数，对于任意的整数 x，f（x）=x2。,解：f 不是 A 到 B 的双射函数。,f 不是 A 到 B 的单射函数，也不是满射函数。,2020/7/9,102,4.2复合函数和逆函数,1.复合函数,定义 1 设函数f：XY，g：YZ，f 和 g 的左复合函,例如 设集合A=x，y，z

58、，B=1，2，3，4，C=a，b，c。,第二篇 集合论 第四章函数,数 gf 是从 X 到 Z 的函数，gf（x）=g（f（x）。,由f，g得到 gf 的运算“”称为函数的复合运算。,f 是 A 到 B 的函数，g 是 B 到 C 的函数，其中,f(x)=2,f(y)=3,f(z)=3,g(1)=a,g(2)=c,g(3)=a,g(4)=b,求 复合函数gf。,gf（x）=g（f（x）=g（2）=c,gf（z）=g（f（z）=g（3）=a,gf（z）=g（f（z）=g（3）=a,2020/7/9,103,4.2 复合函数和逆函数,1.复合函数,复合函数具有如下特性：,第二篇 集合论 第四章函数,设 f，g 为函数，gf 为 f 和 g 的左复合函数，,则： （1）若 f 和 g 是满射的函数，则gf是满射的函数。,（2）若 f 和 g 是单射的函数，则gf是单射的函数。,（3）若 f 和 g 是双射的函数，则gf是双射的函数。,2020/7/9,104,4.4复合函数和逆函数,2.逆函数,定义 2 设 f：XY 是一个双射函数，则如果 g：YX，,第二篇 集合论 第四章函数,对每一个yY 有g（y）=x 且 y=f（x），称 g 为 f 的,逆函数，记作 g=f1。若 f存在