大二离散r04函数

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逆函数函数呢？