1、1離 散 數 學主講 魚亮 西安電子科技大學計算機學院2函數的概念特殊函數復合函數逆函數函數3 4.1 函數的概念設X和Y是任意兩個集合，f 是X到Y的一個二元關系，如果對于每一個xX，有唯一的yY，使得f，則稱關系f 為函數（a function from X to Y）或映射（mapping），記為 f 也可記為y=f(x)，f 的前域就是函數y=f(x)的定義域，記作dom f = X ，f的值域ran f Y，集合Y稱為f 的陪域(共域)。 4函數的概念例1：判斷下列關系中哪些是函數：f=|x1,x2N,且x1+x210f=|x1,x2R,且(x2)2=x1f=|x1,x2N,且x2為

2、小于x1的素數的個數如果f，則y稱為在f 作用下x的像（image）， x稱為原像（preimage），且記5函數的概念由函數定義可知，XY的子集并不都能成為X到Y的函數。思考：設X和Y都為有限集合，分別有m個和n個不同元素，則從X到Y有多少個不同的函數？ 由于從X到Y的任意一個函數，其定義域都為X，在這些函數中每一個恰好有m個序偶。而對于X中任意元素x，Y中都有n個元素可以成為它的象，故共有nm個不同的函數。用符號YX表示從X到Y的所有函數的集合，即使X和Y是無限集合時。6函數的概念函數相等7函數的概念當函數f的前域X是n個集合的笛卡兒積時，稱f為n元函數，在函數下的像記為f (x1,x2,

3、xn)。例2 設函數f : NNN，f (x,y)=x+2y+1。（a）求在函數f 下的像；（b）求domf 和ranf 。解 （a）f (2,0)=2+20+1=3； （b）domf =NN， 不存在NN使得 f (x,y)=0，ranf =I+。8函數的歸納定義當函數的前域是歸納定義的集合時，歸納法也是定義函數的有效方法。（a）自然數集合N上的階乘函數f(n)=n!的歸納定義如下： 設 f ：NN (1)(基礎) f(0)=1; (2)(歸納)nN, f(n+1)=(n+1)f(n).（b）Fibonacci函數0,1,1,2,3,5,8,13,的歸納定義如下： 設F：NN是斐波那契函數

4、(1)(基礎) F(0)=0， F(1)=1; (2)(歸納) F(n+2)=F(n+1)+F(n). 歸納步驟中的函數值都是用較“早”變元的函數值指定的。9函數的歸納定義對于kn，f(n)用f(k)表達的式子稱為遞歸公式，用遞歸公式定義稱為遞歸定義(recursive definition)。遞歸定義時k不一定都小于n。如麥卡錫“91函數”（c）f ：NN (1) f (x)=x-10, x100; (2) f (x)=f ( f (x+11), x100. 即 (1) f (x)=x-10, x100; (2) f (x)=91, 0 x100.“91函數”是遞歸的，但不是歸納的。10函數

5、的歸納定義在歸納定義的集合上用遞歸（包括歸納）方法定義的函數，所得未必是函數，尤其當前域的歸納定義允許某些元素可以用多種方法構造的時候。如果定義所得滿足函數定義，稱該函數是良定的。遞歸定義函數時，通常需要證明它是良定的。 上述定義允許多種方法構造某些元素，如abc，可讓x=a，y=bc，形成abc；或者讓x=ab，y=c，形成abc。11函數的歸納定義12 4.2 特殊函數設映射f:XY,如果ranf=Y，即Y的每一個元素都是X中一個或多個元素的像，則稱這個映射為滿射(surjective function)。設映射f:XY,如果X中沒有兩個元素有相同的像，則稱這個映射為單射(injectiv

6、e function)。13特殊函數從X到Y的一個映射，若既是滿射又是單射，則稱這個映射是雙射的(bijective function)。是單射，不是滿射是滿射，不是單射是雙射14特殊函數定理1：設X和Y是有限集合，f 是從集合X 到Y的函數。 （a）若f 是單射，則必有|X|Y|； （b）若f 是滿射，則必有|X|Y|； （c）若f 為雙射，則必有|X|=|Y|；證明:（a）因為f是單射函數，所以|f(X)|=|X|。 又因為f(X)Y，所以有|f (X)| |Y|， 故有|X| |Y|。 （b）假設|X|Y|，因為|f(X)| |X|，所以有|f(X)|Y|， 即f(X)Y，這與是滿射矛盾

7、。 （c）可由（a）（b）直接得出。15特殊函數定理2：16特殊函數常函數和恒等函數17特殊函數X上的雙射函數稱為X上的置換(permutation)或排列(array)。例：一個集合X上的恒等函數是一個置換，稱為幺置換，或恒等置換。函數f: II，f(x)=x+5，是整數集合上的一個置換。 當集合X是無限集時，X上的置換稱為無限次的，當X是有限集時，若|X|=n，則X上的置換稱為n次的。n次置換常寫成18特殊函數在n個元素的集合中，不同的n次置換有n!個。置換的合成是置換，且滿足封閉性。置換的合成是可結合的。19 4.4 復合函數和逆函數設 函數復合運算與關系復合運算書寫次序相反。20復合函數21復合函數22復合函數例：設R為實數集合，對xR有f(x)=x+2, g(x)=x-2, h(x)=3x, 求gf與h(gf)。 gf = |xR h(gf) = |xR 實際上，由關系合成運算的結合性可知，函數的復合是可結合的，即h(gf) = (hg)f 23復合函數24復合函數25復合函數26復合函數27逆函數函數呢？