集合的运算-南京大学计算机科学与技术系.ppt

1、关系及其运算,离散数学集合论南京大学计算机科学与技术系,回顾,集合的基本概念集合及其描述集合相等、子集关系幂集、笛卡尔乘积集合运算交并补、广义交、广义并集合恒等式集合相关命题的证明方式,提要,关系的定义关系的表示关系的运算0-1矩阵运算关系的性质,有序对（Ordered pair）,(a, b)是集合a, a, b的简写次序的体现(x,y)=(u,v) iff x=u 且 y=v若x,x,y=u,u,v，则x=u或x= u,v, 因此x=u。假设yv(1) 若x=y, 左边=x, 而vx,右边x; (2) 若xy,则必有x,y= u,v, 但y既非u,又非v, 矛盾。,笛卡尔乘积（Cartes

2、ian Product）,对任意集合A, B笛卡尔积 AB = (a, b)|aA, bB例：1,2,3a,b = (1, a), (3, a) , (3, a), (1, b), (2, b) , (3, b) 若A，B是有限集合， |AB|= |A|B|,例题,A=1,2, (A)A=?|A|=m, |B|=n, |AB|=?,（二元）关系的定义,若A, B是集合,从A到B的一个关系是AB的一个子集.集合, 可以是空集集合的元素是有序对关系意味着什么？两类对象之间建立起来的联系！,从A到B的二元关系,笛卡尔乘积的子集“从A到B的关系”R；RAB若A=B： 称为“集合A上的（二元）关系”例子

3、常用的数学关系：不大于、整除、集合包含等 网页链接、文章引用、相互认识,特殊的二元关系,集合A上的空关系: 空关系即空集全域关系 EA: EA = (x, y) | x, yA 恒等关系 IA : IA =(x, x) | xA ,函数是一种特殊的关系,函数 f : ABR= (x, f(x) | xA 是一个从A到B的一个关系,关系的表示,假设A=a,b,c,d, B=, / 假设为有限集合集合表示: R1=(a, ), (b, ), (c, ),(c, ) 0-1矩阵 有向图,二元关系和有向图,关系 RABA和B是集合有序对集合(x,y)R若A=B, R中存在序列：(x1,x2), (x2

4、,x3),(xn-1,xn),有向图 (VD , ED )顶点集 VD= AB有向边集ED从x到y有一条边图D中存在从 x1 到 xn 的长度为 n-1的通路,关系的运算（1）,关系是集合, 所有的集合运算对关系均适用例子:自然数集合上: “”等同于,关系的运算（2）,与定义域和值域有关的运算dom R = x | y (x,y)Rran R = y | x (x,y)Rfld R = dom R ran RR A = (x,y) | xA xRy RRA = y | x (xA (x,y)R)= ran(RA) ranR例：A=1,2,3,4,5, B=1,3,5,6, A上关系R： R=(

5、1,2), (1,4),(2,3),(3,5),(5,2), 求 RB、RB、R(1)和R(2),关系的运算（3）,逆运算R-1 = (x, y) | (y,x)R注意:如果R是从A到B的关系,则R-1是从B到A的。(R-1)-1 = R例子：(R1R2)-1 = R1-1R2-1 (x, y) (R1R2)-1 (y, x)(R1R2) (y, x)R1 或 (y, x)R2 (x, y)R1-1 或 (x, y)R2-1,关系的运算（4）,关系的复合（合成, Composition）设 R1AB, R2BC, R1与R2的复合（合成）, 记为 R2 R1, 定义如下：R2 R1=(a, c

6、) AC | bB (a, b) R1(b, c)R2) ,复合关系的图示,(a, c)R2 R1 当且仅当 aA, cC, 且存在bB，使得(a, b) R1, (b,c) R2,a,b,c,R1,R2,关系的复合运算：举例,设A=a, b, c, d, R1, R2为A上的关系，其中：R1 = (a, a), (a, b), (b, d)R2 = (a, d), (b, c), (b, d), (c, b)则：R2 R1 = (a, d), (a, c), (a, d)R1 R2 = (c, d)R12 = (a, a), (a, b), (a, d),关系的复合运算的性质（1）,结合律给

7、定R1AB, R2BC, R3CD, 则： (R3 R2) R1 = R3 (R2 R1) 证明左右两个集合相等.,关系的复合运算的性质（2）,复合关系的逆关系给定R1AB, R2BC, 则： (R2 R1)-1 = R1-1 R2-1 同样，证明左右两个集合相等(x, y) (R2 R1)-1 (y, x) R2 R1 tB (y, t)R1 (t, x)R2) tB (t, y) R1-1(x, t)R2-1 ) (x, y) R2-1 R1-1,关系的复合运算的性质（3）,对集合并运算满足分配律给定FAB, GBC, HBC, 则： (GH) F = (G F) (H F) 对集合交运算

8、： (G H) F (G F) (H F) 注意：等号不成立。A=a, B=s,t, C=b; F=(a,s), (a,t), G=(s,b), H=(t,b); GH=, (G F) (H F)=(a,b),0-1 矩阵运算,令0-1矩阵M1=aij,M2=bij:C=M1 M2: cij=1 iff. aij=bij=1C=M1 M2: cij=1 iff. aij=1或bij=1令rs矩阵M1=aij；st矩阵M2=bij:C=M1 M2: cij=1 iff.,关系运算的矩阵法（1）,命题,证明：,关系的性质：自反性 reflexivity,集合A上的关系 R 是:自反的 reflex

9、ive：定义为：对所有的 aA, (a,a)R反自反的 irreflexive：定义为：对所有的aA, (a,a)R注意区分”非”与”反”设 A=1,2,3, RAA(1,1), (1,3), (2,2), (2,1), (3,3) 是自反的(1,2), (2,3), (3,1) 是反自反的(1,2), (2,2), (2,3),( 3,1) 既不是自反的，也不是反自反的,自反性与恒等关系,R 是 A 上的自反关系 IAR, 这里IA是集合A上的恒等关系,即: IA=(a,a)| aA 直接根据定义证明： 只需证明：对任意(a,b) ，若(a,b)IA, 则(a,b)R 只需证明：对任意的a,

10、 若aA, 则(a,a)R,自反关系的有向图和0-1矩阵,关系的性质：对称性 Symmetry,集合A上的关系R是: 对称的 symmetric：定义为：若 (a,b)R, 则 (b,a)R反对称的 anti-：定义为：若(a,b)R 且(b,a)R ，则a=b设 A=1,2,3, RAA(1,1),(1,2),(1,3),(2,1),(3,1),(3,3) 是对称的(1,2),(2,3),(2,2),(3,1) 是反对称的,理解对称性,关系R满足对称性：对任意(a,b)，若 (a,b)R, 则 (b,a)R注意：是对称关系。反对称并不是对称的否定: ( 令：A=1,2,3, RAA)(1,1

11、),(2,2) 既是对称的，也是反对称的是对称关系，也是反对称关系。,对称性与逆关系,R 是集合A上的对称关系 R-1=R 证明一个集合等式R-1=R 若(a,b)R-1, 则(b,a)R, 由R的对称性可知(a,b)R, 因此：R-1R; 同理可得：RR-1; 只需证明：对任意的(a,b) 若(a,b)R, 则(b,a)R,对称关系的有向图和0-1矩阵,关系的性质：传递性 transitivity,集合A上的关系R是传递的 transitive: 若 (a,b)R, (b,c)R, 则 (a,c) R设 A=1,2,3, RAA(1,1),(1,2),(1,3),(2,1),(2,2),(2

12、,3),(3,3) 传递的(1,2),(2,3),(3,1) 是非传递的(1,3)? ?,传递性与关系的乘幂,关系的复合(乘)运算满足结合律，可以用 Rn 表示R R R (n是正整数) 命题：(a,b)Rn 当且仅当：存在t1,t2,tn-1A, 满足：(a,t1),(t1,t2),(tn-2,tn-1),(tn-1,b)R。对n=1用数学归纳法：n=1, trivial. 奠基n=2,直接由关系复合的定义可得；归纳基于：Rn=Rn-1 R集合A上的关系R是传递关系 R2R必要性：任取(a,b) R2 ,根据上述命题以及R的传递性可得(a,b)R充分性： 若(a,b)R, (b,c)R, 则

13、(a,c)R2, 由R2R可得： (a,c)R，则 R是传递关系,传递关系的有向图和0-1矩阵,一些常用关系的性质,关系运算与性质的保持,小结,关系：笛卡尔积的子集关系的运算集合运算；复合运算；逆0-1矩阵运算关系的性质reflexivity, ir-; symmetry, anti-; transitivity 图特征；矩阵特征,作业,教材内容：Rosen 2.1.3、8.1 节 8.3节课后习题：见课程主页,函数及其运算,离散数学集合论南京大学计算机科学与技术系,回顾,关系：笛卡尔积的子集关系的运算集合运算；复合运算；逆0-1矩阵运算关系的性质reflexivity, ir-; symme

14、try, anti-; transitivity 图特征；矩阵特征,提要,函数的定义子集的像单射与满射反函数函数的复合函数加法与乘法,函数(function)的定义,设 A 和 B 为非空集合，从集合A到B的函数 f 是对元素的一种指派，对A的每个元素恰好指派B的一个元素。记作 f :AB。Well defined(良定义)f :AB：函数的型构f 的定义域（domain）是A，f 的伴域（codomain）是B如果 f 为A中元素a指派的B中元素为b，就写成 f(a)=b。此时，称 b是a的像，而a是b的一个原像。A中元素的像构成的集合称为f的值域 range （ f的像 image）。函数

15、也称为映射(mapping)或变换(transformation),函数的集合定义,函数的集合定义（续）,函数举例,下取整函数 x: R Z,函数 f 的图像: (a, b) | aA f(a)=b,Java Programint floor(float real) ,floor: float int,函数举例,某课程成绩,ProgramCourseGrade grade(StudentName sname，CourseName cname) ,Function：Grade: StudentName CourseName CourseGrade,函数原型,函数型构(signature),函数举

16、例,设A为非空集合，A上的 恒等函数A:AA定义为A(x)=x，xA设U为非空集合，对任意的AU, 特征函数A:U0,1 定义为：A(x)=1，xAA(x)=0，xU-A,函数的集合,函数(function)的相等,函数相等 f=g ifdom(f)=dom(g)codom(f)=codom(g)x(xdom(f) f(x)=g(x),函数的相等,子集在函数下的像,设 f 是从集合A到B的函数，S 是A的一个子集。S 在 f 下的像，记为f(S)，定义如下：f (S)= t | sS (t= f (s) 备注：f (A) 即为 f 的值域。,B,f(S):T,A,S,f,S的像和逆像,S的像:

17、T,T的逆像是什么？,并集的像,设函数 f: AB，且X，Y是A的子集，则f (XY) = f(X)f (Y) 证明:f (XY) f(X)f (Y) 对任意的t，若tf (XY) , 则存在sXY, 满足f(s)=t; 假设sX, 则tf(X), 假设sY, 则tf(Y), tf (X)f(Y) f(X)f (Y) f (XY) 对任意的t，若tf (X)f(Y) 情况1：tf (X), 则存在sX XY, 满足f(s)=t, t f (XY) 情况2： tf (Y), 同样可得t f (XY) t f (XY),交集的像,设函数 f : AB，且X，Y是A的子集，则f (XY) f(X)f

18、 (Y),A,B,X,Y,a1,a2,c,f,在f(X)f (Y)中，但不在f (XY)中,函数性质,:AB是单射（一对一的）injection, injective function, one-to-one functionx1, x2A, 若x1x2，则(x1) (x2)/等价的说法：x1, x2A, 若(x1) =(x2)，则x1=x2/另一种等价的说法？:AB是满射（映上的）surjection, surjective function, onto functionyB, xA, 使得(x)=y/等价的说法：f (A)=B:AB是双射（一一对应）bijection, bijective

19、 function, one-to-one correspondence满射+单射,函数性质的证明,判断:RRRR, () = 的性质单射？令() = ()x1+y1=x2+y2且x1-y1=x2-y2,易见： x1=x2且y1=y2=满射？任取 RR，总存在,使得()=,函数性质的证明,设A有限集合，f 是从A到A的函数。f 是单射当且仅当 f 是满射。,反函数,设f 是从A到B的一一对应，f 的反函数是从B到A的函数，它指派给B中元素b的是A中满足f(a)=b的（唯一的）a。 f 的反函数记作f -1。f(a)=b 当且仅当 f -1(b)=a任何函数都有反函数吗？例子:RRRR, ()

20、= f -1:RRRR, -1 () = ,函数的复合,设g是从A到B的函数，f是从B到C的函数，f和g的复合用f g表示，定义为：(f g) (x)= f(g(x)， xA,a,A,g(a),B,C,f(g(a),g,f,f g,复合运算的性质,函数的复合满足结合律(f g) h = f (g h)满射的复合是满射单射的复合是单射 双射的复合是双射 设f 是从A到B的双射 f -1 f = Af f -1 = B,复合运算,复合运算,但是,若f g是满射，能推出f 和g是满射吗？f一定是满射， g不一定是满射。 若f g是单射，能推出f 和g是单射吗？g一定是单射，f 不一定是单射。,g,f

21、,A,B,C,函数的加法、乘法,设f和g是从A到R的函数，那么 f+g 和 f g也是从A到R的函数，其定义为(f+g)(x) = f(x) + g(x) ， xAf g(x) = f(x) g(x) ， xA,递增（递减）函数,设f的定义域和伴域都是实数(或其子集)，f是递增的x y (xy f (x)f(y)f是严格递增的x y (xy f (x) f(y),一个有趣的例子,自然数1,2,3,n2+1的任何一种排列中，必然含一个长度不小于n+1的严格递增链或严格递减链。7,4,3,5,2,1,9,8,6,10/10,3,2,6,4,7,5,9,1,8在所给的序列中，以k开始的严格递增序列长度为I(k), 以k开始的严格递减序列长度为D(k)。f: k (I(k), D(k), k1,2, n2+1f(7)=(3,5),f(4)=(4,4),f(3)=(4,3),f(5)=(3,3),f(2)=(3,2),f(1)=(3,1)f(9)=(2,3),f(8)=(2,2),f(6)=(2,1),f(10)=(1,1)f是单射：对于k1k2，如果k1排在k2前面，则I(k1)I(k2)，如果k2排在k1前面，则D(k2)D(k1)。反证法：给定任一种排列，假设严格递增与递减序列最大长度均不大于n： f的值域最多有n2个元素f不可能是单射,作业,教材2.3见课程主页,