《西安交大离散课件第3章-1》由会员分享，可在线阅读，更多相关《西安交大离散课件第3章-1（32页珍藏版）》请在金锄头文库上搜索。
1、1,第三章 函数1.函数的基本概念2.函数的复合3.集合的基数 势理论,2,第三章 函数（function） 1.函数基本概念定义1.函数(映射(map)、变换(transformation)函数是后者唯一的关系。即 f是由X到Y的函数，记为f :XY f XY(xX)(yY)(zY)(x, y)f (x, z)f y=z) 。注：函数概念主要是限制了关系概念中的一对多；但允许多对一；,f,f,3,与函数概念关联的一些概念(1)若(x, y)f ，则函数惯用的记法是y= f(x)；称x为自变量，称y为因变量。(2)此定义可容纳多值函数 f :XY ， f(x) = y1, y2 ,yk其修改为
2、 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) 。,函数的定义域和值域,4,(5)象(image)：子集A X的象定义为f(A)=y : yY(xA)(x, y)f )=y : yY(xA)(y= f(x) 。(6)逆象(inverse image)：子集BY的逆象定义为f -1(B) =x : x
3、X(yB)(x, y)f )=x : xX(yB)(y= f(x) ；,f,5,特别地，单元素yY的逆象是f -1(y) =x : xX(x, y)f =x : xXf(x)=y 。(7)全函数（full function）：处处有定义的函数。即 D(f)=X （或者f -1(Y) = X）(8)偏函数(partial function)：部分有定义的函数。即 D(f)X （或者f -1(Y)X） 。,6,例1投影函数（projection function）uni :X1 X2 Xn Xi uni(x1 , x2 , , xn) = xi ( i=1,2, ,n )例2截痕函数(cross
4、function)：f :X2XY ，f(x) = xY 。例3.计算机是一个函数。即计算机:输入空间输出空间；编译是一个函数。即 编译:源程序目标程序。例4. 一种定义离散函数的方式是采用下面的分段定义形式。即 f :N N 。,7,例5.绝对值函数(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
5、 , R(f1)=R+0；f2 =(x,-x) : xR x0， D(f2)=R- , R(f2)=R+ ；(这里R-=x: xRx 0是负实数集)，于是；D(f)= D(f1) D(f2)= R , R(f)= R(f1) R(f2)=R+0 ；绝对值函数也可采用下面分段定义的形式。即。,8,例6.后继函数(successor function)后继函数也称为Peano函数。设(X,)是一全序集，并且每个元素的后继存在，即 (xX)(yX)(x+=y) ， 则关系 P=(x, y) : xXyXx+=y 是一函数，即所谓的后继函数。记作s:XX ，对任何xXs(x) = x+ = x +1。
6、 这里加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 。,9,例7.第一章2定义2定义的集合的并运算是一函数。即f (2X 2X) 2X ，f =(x,y), z) : x, y , z 2X z= x y 这里(x,y)是前者， z是后者；或者 f :2X
7、2X 2X ， f(x ,y) = z= x y ，这里(x,y)是自变量， z是因变量；因此 f = 。例8. 函数可以逐点来定义。g :1,2,3 A,B,C g(1)=A， g(2)=C ，g(3)=C定义2.函数的相等函数的相等是逐点相等。即 设f ,g是由X到Y的两个函数，f ,g :XY，则f = g (xX)(f(x) = g(x) ) 。,10,定义3.运算(operation)对于任何自然数n1，n元运算f是一个从n维叉积Xn到X的函数。 即 f :Xn X 。关于运算， 主要考虑其封闭性。n元运算f的封闭性：对于任何n个元素x1 , x2 , , xn ，x1 , x2 ,
8、 , xnX f(x1 , x2 , , xn)X ， 或者 (x1 , x2 , , xn)Xn f(x1 , x2 , , xn)X 。例9.集合的余运算 :2X 2X 是一元运算；集合的交，并运算 , :2X 2X 2X 是二元运算。例10.集合的特征函数：对于任何集合AX， 定义A的特征函数A :X0,1 如下A(x)=,11,于是 有 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) 。
9、例11.谓词的特征函数：设P是X上的谓词， 定义P的特征函数P :X0,1 如下P(x)=于是 有 P(x)=1- P(x)PQ(x)= P(x) .Q(x) PQ(x)= P(x) +Q(x) - PQ(x) (PQ)(xX)(P(x)Q(x) (PQ)(xX)(P(x)=Q(x) F(xX)(F(x) =0)T(xX)(T(x) =1) 。,12,例13.单位函数或幺函数(identity function)：幺函数即是幺关系。用函数的记法，即是IX :XX对任何xX ， IX (x)= x 。显然 D(IX)= R(IX)=X 。定义4.单射、满射、双射(injection,surjec
10、tion,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既是单射函数又是满射函数。,13,注：单射函数概念主要是限制了函数概念中的多对一；允许的是一对一； 满射函数概念主要是不允许函数的后集中存在元素无前集中元素与其对应；在有限集的情况，双射函数的存在，保证前集和后集一样大小。即 |X| = |Y
11、| 在有限集的情况，若 |X| = |Y| ，则可证： f是单射函数 f是满射函数 f是双射函数,14,例14. 设 X=a,b,c,d , Y=1,2,3,4f : XY, f(a)=1, f(b)=2, f(c)=3, f(d)=4f的性质如何？例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 性质如何？,15,
12、定理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是单射),16,(2) 是全函数：D( )=y : yY(xX)(y, x) )=y : yY(xX)(x, y)f )= R(f)=
13、Y (f是双射，故f是满射)(3) 是单射：对于任何y1,y2Y(y1) = (y2) (xX)( (y1) = x (y2) = x) ( 是全函数) (xX)(f(x) = y1 f(x) = y2 ) (xX)(x , y1) f (x , y2) f) y1= y2 (f 是函数,后者唯一；注意：不是利用等号=的对称性、传递性),17,(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 ； 证.函数是关系，关系的反身性前面已证。,18,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) 。 注： 函数的复合其实就是关系的合成；只不过记法上有所不同；函数的复合是(向)左复合，右(边)优先；而关系的合成是(向)右复合，左(边)优先；,
