离散数学第3章函数.ppt

1,离散数学,西安交通大学电子与信息工程学院计算机系,2,离散数学,第三章 函数 1.函数的基本概念 2.函数的复合,3,离散数学,第三章 函数（function）1.函数基本概念 定义1.函数(映射(map)、变换(transformation)函数是后者唯一的关系。即 f是由X到Y的函数，记为f:XY f XY(xX)(yY)(zY)(x,y)f(x,z)f y=z)。注：函数概念主要是限制了关系概念中的一对多；但允许多对一；,f,4,离散数学,5,离散数学,6,离散数学,与函数概念关联着的一些概念(1)若(x,y)f，则函数惯用的记法是y=f(x)；称x为自变量，称y为因变量。(2)此定义可容纳多值函数 f:XY，f(x)=y1,y2,yk 其修改为 f:X2Y，f(x)=y1,y2,yk2Y。(3)定义域(domain)：称f的前域为f的定义域。即 D(f)=x:xX(yY)(x,y)f)=x:xX(yY)(y=f(x)(4)值域(range)：称f的后域为f的值域。即 R(f)=y:yY(xX)(x,y)f)=y:yY(xX)(y=f(x)。,7,离散数学,(5)象(image)：子集A X的象定义为 f(A)=y:yY(xA)(x,y)f)=y:yY(xA)(y=f(x)。,f,8,离散数学,(6)逆象(inverse image)：子集BY的逆象定义为 f-1(B)=x:xX(yB)(x,y)f)=x:xX(yB)(y=f(x)；特别地，单元素yY的逆象是 f-1(y)=x:xX(x,y)f=x:xXf(x)=y。,9,离散数学,(7)全函数（full function）：处处有定义的函数。即 D(f)=X（或者f-1(Y)=X）今后，在本课程中，除非有特别声明，我们一概研究全函数。(8)偏函数(partial function)：部分有定义的函数。即 D(f)X（或者f-1(Y)X）。,10,离散数学,例1.截痕函数(cross function)：f:X2XY，f(x)=xY。例2.计算机是一个函数。即 计算机:输入空间输出空间；编译是一个函数。即 编译:源程序目标程序。,11,离散数学,例3.绝对值函数(absolute value function)f=(x,|x|):xR(这里R是实数集)或者 f:RR+0，f(x)=|x|(这里R+=x:xRx0是正实数集)，于是 D(f)=R,R(f)=R+0；绝对值函数可以拆成两个函数的并。即 f=f1 f 2，这里 f1=(x,x):xR x0，D(f1)=R+0,R(f1)=R+0；f2=(x,-x):xR x0，D(f2)=R-,R(f2)=R+；(这里R-=x:xRx 0是负实数集)，于是；,12,离散数学,D(f)=D(f1)D(f2)=R,R(f)=R(f1)R(f2)=R+0；绝对值函数也可采用下面分段定义的形式。即。例4.后继函数(successor function)后继函数也称为Peano函数。设(X,)是一全序集，并且每个元素的后继存在，即(xX)(yX)(x+=y)，则关系 P=(x,y):xXyXx+=y是一函数，即所谓的后继函数。记作,13,离散数学,s:XX，对任何xX s(x)=x+=x+1这里加1表示后继，并非都是普通的算术加1。例如,若就是普通的小于等于全序，则当X=I(整数集)时，s(-6)=-6+1=-5,s(1)=1+1=2，相当于普通算术的加1；当X=E(偶整数集)时，s(-6)=-6+1=-4,s(2)=2+1=4，相当于普通算术的加2；当X=n:n I3n(3倍数整数集)时，s(-3)=-3+1=0,s(9)=9+1=12，相当于普通算术的加3。例5.第一章2定义2定义的集合的并运算是一函数。即 f(2X 2X)2X，f=(x,y),z):x,y,z 2X z=x y,14,离散数学,这里(x,y)是前者，z是后者；或者 f:2X 2X 2X，f(x,y)=z=x y，这里(x,y)是自变量，z是因变量；因此 f=。例6.函数未必都有统一的表达式。不象连续函数那样大多都有统一的表达式，离散函数大多都没有统一的表达式。一种定义离散函数的方式是采用下面的分段定义形式。即 f:N N。,15,离散数学,例7.函数未必都很复杂。一些简单的函数可以逐点来定义。g:1,2,3 A,B,C g(1)=A，g(2)=C，g(3)=C其函数映射可用图形表示如下：例8.投影函数（projection function）uni:X1 X2 Xn Xi uni(x1,x2,xn)=xi(i=1,2,n),16,离散数学,定义2.函数的相等 函数的相等是逐点相等。即 设f,g是由X到Y的两个函数，f,g:XY，则 f=g(xX)(f(x)=g(x)。定义3.运算(operation)对于任何自然数n1，n元运算f是一个从n维叉积Xn到X的函数。即 f:Xn X。一般说来，运算具有以下两个特点：(1)定义较一般函数特殊；(2)易可操作性；特别地，一元运算f:XX；二元运算f:X XX。,17,离散数学,例9.集合的补运算:2X 2X是一元运算；集合的交，并运算,:2X 2X 2X是二元运算。关于运算，我们主要考虑其封闭性。n元运算f的封闭性：对于任何n个元素x1,x2,xn，x1,x2,xnX f(x1,x2,xn)X，或者(x1,x2,xn)Xn f(x1,x2,xn)X。,18,离散数学,例10.集合的特征函数：对于任何集合AX，我们定义A的特征函数 A:X0,1 如下 A(x)=于是我们有 A(x)=1-A(x)AB(x)=A(x).B(x)AB(x)=A(x)+B(x)-AB(x)AB(xX)(A(x)B(x)A=B(xX)(A(x)=B(x)A=(xX)(A(x)=0)A=X(xX)(A(x)=1)。,19,离散数学,例11.单位函数或幺函数(identity function)：幺函数即是幺关系。用函数的记法，即是IX:XX 对任何xX，IX(x)=x。显然D(IX)=R(IX)=X。,20,离散数学,定义4.单射满射双射(injection,surjection,bijection)设 f 是从X到Y的函数，即 f:XY。则我们称(1)f是单射(内射)函数(x1X)(x2X)(x1 x2 f(x1)f(x2)(x1X)(x2X)(f(x1)=f(x2)x1=x2)；(2)f是满射函数(yY)(xX)(f(x)=y)R(f)=Y f(X)=Y；(3)f是双射函数 f既是单射函数又是满射函数。,21,离散数学,注：单射函数概念主要是限制了函数概念中的多对一；允许的是一对一；满射函数概念主要是不允许函数的后集中有元素无前集中元素和其对应；在有限集的情况，双射函数的存在，保证前集和后集一样大小。即|X|=|Y|在有限集的情况，若|X|=|Y|，则可证：f是单射函数 f是满射函数 f是双射函数这可由鸽巢原理证明。留给学者。,22,离散数学,23,离散数学,例14.设 X=a,b,c,d,Y=1,2,3,4 f:XY,f(a)=1,f(b)=2,f(c)=3,f(d)=4 则f是从X到Y的双射函数。例15.设X,Y都是实数的集合，f:XY,f=(x,y):xX yY y=sin(x)若X=Y=R正弦函数f 既不是满射函数也不是单射函数；若将Y限制在-1,1 之间，X=R，则f是满射函数，但非单射函数；若将X限制在-/2,/2 之间，Y=R，则f是单射函数，但非满射函数；若将X限制在-/2,/2 之间，Y限制在-1,1 之间，则f是双射函数。,24,离散数学,定理1.逆(反)函数(inverse function)双射函数f:XY的逆关系 Y X是一个从Y到X的双射函数；我们称其为f的逆函数，记为 f1:Y X。证.(采用：逻辑法)(1)后者唯一(即 是函数)：对于任何yY，对于任何x1,x2X(y,x1)(y,x2)(x1,y)f(x2,y)f f(x1)=y f(x2)=y f(x1)=f(x2)(等号=的对称性，传递性)x1=x2(f是双射，故f是单射),25,离散数学,(2)是全函数：D()=y:yY(xX)(y,x)=y:yY(xX)(x,y)f)=R(f)=Y(f是双射，故f是满射)(3)是单射：对于任何y1,y2Y(y1)=(y2)(xX)(y1)=x(y2)=x)(是全函数)(xX)(f(x)=y1 f(x)=y2),26,离散数学,(xX)(x,y1)f(x,y2)f)y1=y2(f 是函数,后者唯一；(4)是满射：R()=x:xX(yY)(y,x)=x:xX(yY)(x,y)f)=D(f)=X(f 是全函数)。定理2.设f:XY是一双射函数。则 f 的逆函数(作为逆运算)f1:Y X满足 反身性：(f1)-1=f；证.函数是关系，关系的反身性前面已证。,27,离散数学,2.函数的复合定义1.函数的复合运算 设 f:XY,g:YZ 是两个函数。则合成关系fg=(x,z):xXzZ(yY)(x,y)f(y,z)g)=(x,z):xX zZ(yY)(f(x)=y g(y)=z)称为函数f和g的复合(运算)，fg称为函数f和g的复合函数。记为gf:X对任何xX，有(g f)(x)=g(f(x)。注：函数的复合其实就是关系的合成；只不过记法上有所不同；函数的复合是(向)左复合，右(边)优先；而关系的合成是(向)右复合，左(边)优先；,28,离散数学,定义1的合理性证明.要证如下两点：(1)gf 后者唯一(即gf是函数)对于任何xX，若存在着z1,z2Z，使(g f)(x)=z1(g f)(x)=z2(x,z1)g f(x,z2)g f(y1Y)(x,y1)f(y1,z1)g)(y2Y)(x,y2)f(y2,z2)g)(yY)(x,y)f(y,z1)g(y,z2)g)(由于f 是函数，故后者唯一，所以,y1=y2=y)(yY)(y,z1)g)(y,z2)g)z1=z2(由于g是函数，故后者唯一),29,离散数学,(2)g f是全函数 根据复合函数的定义，显然有D(g f)X；另一方面：对于任何x，xX(yY)(x,y)f)(条件：f是全的，故D(f)=X)对于任何y，yY(zZ)(y,z)g)(条件：g是全的，故D(g)=Y)xX(yY)(x,y)f(y,z)g)(x,z)g f xD(g f)所以 XD(g f)；所以 D(g f)=X。,30,离散数学,例1.设 X=1,2,3,f:XX,f=(1,2),(2,3),(3,1)，g:XX,g=(1,2),(2,1),(3,3)，则 g f=(1,1),(2,3),(3,2)，f g=(1,3),(2,2),(3,1)。注：从上例可知：函数复合没有交换律，即g f f g；但是函数复合仍是关系的合成，因此有关关系合成的几乎所有性质都适用于函数的复合，尤其是结合律。f:XY,g:YZ,h:ZW,则有函数复合的结合律：h(g f)=(h g)f。,31,离散数学,定义2.函数的复合幂 设 f:X X 是一函数。那么我们定义：(1)f 1=f,f n+1=f f n；（注意与关系合成幂的不同之处）(2)若f 2=f，则称 f 是幂等函数。例2.设 f:II,f(x)=3 x+2。于是 f(x)=f(f(x)=3 f(x)+2=3(3x+2)+2=3x+3 2+2=3x+8 f(x)=f(f(x)=3 f(x)+2=3(3x+8)+2=3x+38+2=33 x+26 一般地，我们猜测 f n(x)=3n x+3n-1，则有 f n+1(x)=f(f n(x)=3 f n(x)+2=3(3nx+3n-1)+2=3n+1x+3n+1-3+2=3n+1x+3n+1-1。,32,离散数学,定理1.设 f:XY,g:YZ 是两个函数。则(1)f和g都是单射函数 g f也是单射函数；(2)f和g都是满射函数 g f也是满射函数；(3)f和g都是双射函数 g f也是双射函数。证.(采用逻辑法)只证(1)和(2)；(3)由(1)和(2)是显然的。(1)对于任何x1,x2X(g f)(x1)=(g f)(x2)g(f(x1)=g(f(x2)f(x1)=f(x2)(g是单射)x1=x2(f是单射)所以g f是单射；,33,离散数学,(2)对于任何zzZ(yY)(y,z)g)(g是满射)(yY)(xX)(x,y)f)(y,z)g)(f是满射)(xX)(yY)(x,y)f(y,z)g)(xX)(x,z)g f)所以(zZ)(xX)(x,z)g f)所以g f是满射。,34,离散数学,定理2.设 f:XY 是双射函数。则(1)f1 f=IX；(2)f f1=IY。证.只证(1)对于任何xX(f1 f)(x)=f1(f(x)=f1(y)(由于D(f)=X，因而有某个 yY，使 f(x)=y)=x(f(x)=y，故 f1(y)=x)=IX(x)所以f1 f=IX。,35,离散数学,定义3.置换(permutation)设X，|X|=n，X=x1,x2,xn。则我们称 P为X上的一个(n次)置换P是从X到X的一个双射函数，即 P:XX。并且称n为置换P的阶。注：所有n次置换构成的集合记为Sn；在n个元素的集合中，不同的n阶置换的个数为n!，即|Sn|=n!；,36,离散数学,通常用下面的方法表示X上的一个(n次)置换；若xiX 有 P(xi)=xi，则称P是恒等置换,记为I,可表示为；P的逆函数P-1称为P的逆置换，可表示为 置换的合成运算是作为关系的合成运算，而不是作为函数的复合运算=。置换的合成运算满足结合律，但不满足交换律。,37,离散数学,重点要求 要求掌握函数的基本概念,弄清单射、满射、双射之间的区别。给定一个函数,要能够确定它是否是单射、满射、双射等。掌握反函数和复合函数的定义和性质,并弄清楚它们存在的条件。理解元素及集合的象及原象的定义及相关的性质。给定一个函数,能够确定一个点的象,一个集合的象,能够确定一个点的原象,一个集合的原象,能够确定两个函数的复合函数等。掌握集合的势、可数集、不可数集等概念。,38,离散数学,第三章函数到此已经结束！谢谢读者收看！,