離散數(shù)學(xué) 第3章 函數(shù)

1、離散數(shù)學(xué)西安交通大學(xué)電子與信息工程學(xué)院計(jì)算機(jī)系1離散數(shù)學(xué) 第三章 函數(shù) 1.函數(shù)的基本概念 2.函數(shù)的復(fù)合2離散數(shù)學(xué) 第三章 函數(shù)（function） 1.函數(shù)基本概念 定義1.函數(shù)(映射(map)、變換(transformation) 函數(shù)是后者唯一的關(guān)系。即 f是由X到Y(jié)的函數(shù)，記為f :XY f XY(xX)(yY)(zY)(x, y)f (x, z)f y=z)。注：函數(shù)概念主要是限制了關(guān)系概念中的一對(duì)多；但允許多對(duì)一；fYf(a)aX函數(shù)的圖象3離散數(shù)學(xué)ba1a2XY函數(shù)允許的情況：多對(duì)一fab1b2f函數(shù)不允許的情況：一對(duì)多XY4離散數(shù)學(xué)D(f)R(f)XYf函數(shù)的定義域和值域5離

2、散數(shù)學(xué)與函數(shù)概念關(guān)聯(lián)著的一些概念 (1)若(x, y)f ，則函數(shù)慣用的記法是y= f(x)；稱x為自變量，稱y為因變量。 (2)此定義可容納多值函數(shù) f :XY ， f(x) = y1, y2 ,yk 其修改為 f :X2Y ， f(x) = y1, y2 ,yk2Y 。 (3)定義域(domain)：稱f的前域?yàn)閒的定義域。即 D(f)=x : xX (yY)(x, y)f ) =x : xX (yY)(y= f(x) (4)值域(range)：稱f的后域?yàn)閒的值域。即 R(f)= y : yY(xX)(x, y)f ) =y : yY(xX)(y= f(x) 。 6離散數(shù)學(xué) (5)象(i

3、mage)：子集A X的象定義為 f(A)=y : yY(xA)(x, y)f ) =y : yY(xA)(y= f(x) 。 fXY集合的象AD(f)f(A) R(f)7離散數(shù)學(xué) (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 。XYf -1(B)集合的逆象BD(f)R(f)f8離散數(shù)學(xué) (7)全函數(shù)（full function）：處處有定義的函數(shù)。即 D(f)=X （或者f

4、 -1(Y) = X） 今后，在本課程中，除非有特別聲明，我們一概研究全函數(shù)。 (8)偏函數(shù)(partial function)：部分有定義的函數(shù)。即 D(f)X （或者f -1(Y)X） 。 XD(f)D(f)X9離散數(shù)學(xué) 例1.截痕函數(shù)(cross function)：f :X2XY ， f(x) = xY 。 例2.計(jì)算機(jī)是一個(gè)函數(shù)。即 計(jì)算機(jī):輸入空間輸出空間； 編譯是一個(gè)函數(shù)。即 編譯:源程序目標(biāo)程序。 XYxYYXx10離散數(shù)學(xué)例3.絕對(duì)值函數(shù)(absolute value function) f =(x,|x|) : xR (這里R是實(shí)數(shù)集)或者 f :RR+0 ， f(x) =

5、 |x| (這里R+=x: xRx0是正實(shí)數(shù)集)，于是 D(f)=R , R(f)=R+0； 絕對(duì)值函數(shù)可以拆成兩個(gè)函數(shù)的并。即 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是負(fù)實(shí)數(shù)集)，于是； 11離散數(shù)學(xué) D(f)= D(f1) D(f2)= R , R(f)= R(f1) R(f2)=R+0 ； 絕對(duì)值函數(shù)也可采用下面分段定義的形式。即 。例4.后繼函數(shù)(successor function) 后繼函數(shù)也稱為

6、Peano函數(shù)。 設(shè)(X,)是一全序集，并且每個(gè)元素的后繼存在，即 (xX)(yX)(x+=y) ，則關(guān)系 P=(x, y) : xXyXx+=y是一函數(shù)，即所謂的后繼函數(shù)。記作12離散數(shù)學(xué) s:XX ，對(duì)任何xX s(x) = x+ = x +1這里加1表示后繼，并非都是普通的算術(shù)加1。例如,若就是普通的小于等于全序，則當(dāng)X=I (整數(shù)集)時(shí)，s(-6)=-6+1=-5, s(1)=1+1=2，相當(dāng)于普通算術(shù)的加1；當(dāng)X=E(偶整數(shù)集)時(shí)，s(-6)=-6+1=-4, s(2)=2+1=4，相當(dāng)于普通算術(shù)的加2；當(dāng)X=n : n I3n (3倍數(shù)整數(shù)集)時(shí)，s(-3)=-3+1=0, s(9

7、)=9+1=12，相當(dāng)于普通算術(shù)的加3 。例5.第一章2定義2定義的集合的并運(yùn)算是一函數(shù)。即 f (2X 2X) 2X， f =(x,y), z) : x, y , z 2X z= x y 13離散數(shù)學(xué)這里(x,y)是前者， z是后者；或者 f :2X 2X 2X ， f(x ,y) = z= x y ，這里(x,y)是自變量， z是因變量；因此 f = 。 例6.函數(shù)未必都有統(tǒng)一的表達(dá)式。不象連續(xù)函數(shù)那樣大多都有統(tǒng)一的表達(dá)式，離散函數(shù)大多都沒有統(tǒng)一的表達(dá)式。一種定義離散函數(shù)的方式是采用下面的分段定義形式。即 f :N N 。 14離散數(shù)學(xué)例7.函數(shù)未必都很復(fù)雜。一些簡(jiǎn)單的函數(shù)可以逐點(diǎn)來定義。

8、g :1,2,3 A,B,C g(1)=A， g(2)=C ，g(3)=C其函數(shù)映射可用圖形表示如下：例8.投影函數(shù)（projection function）uni :X1 X2 Xn Xi uni(x1 , x2 , , xn) = xi ( i=1,2, ,n )g123ABC15離散數(shù)學(xué)定義2.函數(shù)的相等 函數(shù)的相等是逐點(diǎn)相等。即 設(shè)f ,g是由X到Y(jié)的兩個(gè)函數(shù)，f ,g :XY，則 f = g (xX)(f(x) = g(x) ) 。定義3.運(yùn)算(operation) 對(duì)于任何自然數(shù)n1，n元運(yùn)算f是一個(gè)從n維叉積Xn到X的函數(shù)。 即 f :Xn X 。 一般說來，運(yùn)算具有以下兩個(gè)特點(diǎn)

9、： (1)定義較一般函數(shù)特殊； (2)易可操作性； 特別地，一元運(yùn)算f :XX； 二元運(yùn)算f :X XX。16離散數(shù)學(xué)例9.集合的補(bǔ)運(yùn)算 :2X 2X是一元運(yùn)算； 集合的交，并運(yùn)算 , :2X 2X 2X是二元運(yùn)算。關(guān)于運(yùn)算，我們主要考慮其封閉性。 n元運(yùn)算f的封閉性：對(duì)于任何n個(gè)元素x1 , x2 , , xn， x1 , x2 , , xnX f(x1 , x2 , , xn)X ，或者(x1 , x2 , , xn)Xn f(x1 , x2 , , xn)X 。 17離散數(shù)學(xué)例10.集合的特征函數(shù)：對(duì)于任何集合AX，我們定義A的特征函數(shù) A :X0,1 如下 A(x)= 于是我們有 A(

10、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) 。 18離散數(shù)學(xué)例11.單位函數(shù)或幺函數(shù)(identity function)：幺函數(shù)即是幺關(guān)系。用函數(shù)的記法，即是IX :XX 對(duì)任何xX ， IX (x)= x 。顯然D(IX)= R(IX)=X 。19離散數(shù)學(xué)定義4.單射滿射雙射(injection,surjection,bijection)設(shè) f 是從X到Y(jié)的函數(shù)，即 f :XY 。則我們稱

11、 (1) f是單射(內(nèi)射)函數(shù) (x1X)(x2X)(x1 x2 f(x1) f(x2 ) ) (x1X)(x2X)(f(x1) =f(x2 ) x1 =x2 )； (2) f是滿射函數(shù)(yY)(xX)( f(x)= y ) R(f)= Y f(X)= Y ； (3) f是雙射函數(shù) f既是單射函數(shù)又是滿射函數(shù)。 20離散數(shù)學(xué)注：?jiǎn)紊浜瘮?shù)概念主要是限制了函數(shù)概念中的多對(duì)一；允許的是一對(duì)一； 滿射函數(shù)概念主要是不允許函數(shù)的后集中有元素?zé)o前集中元素和其對(duì)應(yīng)； 在有限集的情況，雙射函數(shù)的存在，保證前集和后集一樣大小。即 |X| = |Y| 在有限集的情況，若 |X| = |Y| ，則可證： f是單射函

12、數(shù) f是滿射函數(shù) f是雙射函數(shù)這可由鴿巢原理證明。留給學(xué)者。21離散數(shù)學(xué)滿射函數(shù)不允許的情況bYR(f)D(f)fa1a2bXYf單射函數(shù)不允許的情況D(f)R(f)22離散數(shù)學(xué)例14. 設(shè) 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(jié)的雙射函數(shù)。例15. 設(shè)X,Y都是實(shí)數(shù)的集合， f : XY, f = (x, y) : xX yY y= sin(x) 若X=Y=R正弦函數(shù)f 既不是滿射函數(shù)也不是單射函數(shù)； 若將Y限制在 -1,1 之間，X=R ，則f是滿射函數(shù)， 但非單射函數(shù)； 若將X限制在 - /

13、2,/2 之間，Y=R ，則f是單射函數(shù)， 但非滿射函數(shù)； 若將X限制在 - /2,/2 之間， Y限制在 -1,1 之間，則f是雙射函數(shù)。23離散數(shù)學(xué)定理1. 逆(反)函數(shù)(inverse function)雙射函數(shù)f : XY的逆關(guān)系 Y X是一個(gè)從Y到X的雙射函數(shù)；我們稱其為f的逆函數(shù)，記為 f1 : Y X。證.(采用：邏輯法)(1) 后者唯一(即 是函數(shù))： 對(duì)于任何yY ，對(duì)于任何x1,x2X (y , x1) (y , x2) (x1 ,y) f (x2 ,y) f f(x1) = y f(x2) = y f(x1) = f(x2) (等號(hào)=的對(duì)稱性，傳遞性) x1 = x2 (

14、f是雙射，故f是單射) 24離散數(shù)學(xué) (2) 是全函數(shù)：D( )=y : yY(xX)(y, x) ) =y : yY(xX)(x, y)f ) = R(f) =Y (f是雙射，故f是滿射) (3) 是單射： 對(duì)于任何y1,y2Y (y1) = (y2) (xX)( (y1) = x (y2) = x) ( 是全函數(shù)) (xX)(f(x) = y1 f(x) = y2 ) 25離散數(shù)學(xué) (xX)(x , y1) f (x , y2) f) y1= y2 (f 是函數(shù),后者唯一； (4) 是滿射： R() =x : xX(yY)(y, x) ) =x : xX(yY)(x, y)f ) =D(f

15、) =X (f 是全函數(shù))。定理2. 設(shè)f : XY是一雙射函數(shù)。則 f 的逆函數(shù)( 作為逆運(yùn)算 )f1 : Y X滿足 反身性： ( f1 )-1= f ；證.函數(shù)是關(guān)系，關(guān)系的反身性前面已證。26離散數(shù)學(xué) 2.函數(shù)的復(fù)合定義1.函數(shù)的復(fù)合運(yùn)算 設(shè) f : XY, g: YZ 是兩個(gè)函數(shù)。則合成關(guān)系fg=(x, z) : xXzZ(yY)(x, y)f (y, z)g ) =(x, z) : xX zZ (yY)(f(x)= y g(y)= z)稱為函數(shù)f和g的復(fù)合(運(yùn)算)， fg稱為函數(shù)f和g的復(fù)合函數(shù)。記為gf : X對(duì)任何xX，有 (g f)(x)= g(f(x) 。 注： 函數(shù)的復(fù)合

16、其實(shí)就是關(guān)系的合成；只不過記法上有所不同； 函數(shù)的復(fù)合是(向)左復(fù)合，右(邊)優(yōu)先；而關(guān)系的合成是(向)右復(fù)合，左(邊)優(yōu)先；27離散數(shù)學(xué)定義1的合理性證明.要證如下兩點(diǎn)： (1) gf 后者唯一 (即gf是函數(shù)) 對(duì)于任何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 是函數(shù)，故后者唯一， 所以, y1 = y2 = y)(yY)(y

17、 ,z1)g)(y , z2)g) z1=z2 (由于g是函數(shù)，故后者唯一)28離散數(shù)學(xué) (2) g f是全函數(shù) 根據(jù)復(fù)合函數(shù)的定義，顯然有D(g f) X； 另一方面：對(duì)于任何x ，xX (yY)(x , y)f ) (條件： f是全的，故D(f)=X ) 對(duì)于任何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 。29離散數(shù)學(xué)例1.設(shè) X=1,2,3, f : XX , f =(1,2),(2,3),(3,1)， g : X

18、X, g =(1,2),(2,1),(3,3)，則 g f =(1,1),(2,3),(3,2) ， f g =(1,3),(2,2),(3,1)。注： 從上例可知：函數(shù)復(fù)合沒有交換律，即g f f g ； 但是函數(shù)復(fù)合仍是關(guān)系的合成，因此有關(guān)關(guān)系合成的幾乎所有性質(zhì)都適用于函數(shù)的復(fù)合，尤其是結(jié)合律。f : XY, g : YZ, h: ZW, 則有函數(shù)復(fù)合的結(jié)合律： h ( g f )= ( h g ) f 。30離散數(shù)學(xué)定義2.函數(shù)的復(fù)合冪 設(shè) f : X X 是一函數(shù)。那么我們定義：(1) f 1 = f , f n+1 = f f n ； （注意與關(guān)系合成冪的不同之處） (2)若f 2

19、= f ，則稱 f 是冪等函數(shù)。例2.設(shè) 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 一般地，我們猜測(cè) 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 。31離散數(shù)學(xué)定理1.

20、設(shè) f : XY, g: YZ 是兩個(gè)函數(shù)。則 (1) f和g都是單射函數(shù) g f也是單射函數(shù)； (2) f和g都是滿射函數(shù) g f也是滿射函數(shù)； (3) f和g都是雙射函數(shù) g f也是雙射函數(shù)。證. (采用邏輯法) 只證(1)和(2) ； (3)由(1)和(2)是顯然的。 (1) 對(duì)于任何x1,x2X (g f )(x1) = (g f )(x2) g(f(x1)= g(f(x2) f(x1)= f(x2) (g是單射) x1= x2 (f是單射) 所以g f是單射；32離散數(shù)學(xué)(2)對(duì)于任何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是滿射。33離散數(shù)學(xué)定理2.設(shè) f : XY 是雙射函數(shù)。則 (1)