大二離散r04函數(shù)

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

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

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

4、(1)(基礎(chǔ)) F(0)=0， F(1)=1; (2)(歸納) F(n+2)=F(n+1)+F(n). 歸納步驟中的函數(shù)值都是用較“早”變元的函數(shù)值指定的。9函數(shù)的歸納定義對于kn，f(n)用f(k)表達的式子稱為遞歸公式，用遞歸公式定義稱為遞歸定義(recursive definition)。遞歸定義時k不一定都小于n。如麥卡錫“91函數(shù)”（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函數(shù)”是遞歸的，但不是歸納的。10函數(shù)

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

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

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