离散数学左孝凌4.ppt

《离散数学左孝凌4.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4.1函数的基本概念(Theconceptoffunction)4.2复合函数与逆函数(CompositionsoffunctionsandInversefunctions)4.1函数的基本概念(Theconceptoffunction)4.1.1函数的基本概念4.1.2特殊函数类(Specialfunctions)4.1.1函数的基本概念函数概念是最基本的数学概念之一，也是最重要的数学工具。初中数学中函数定义为"对自变量每一确定值都有一确定的值与之对应"的因变量；高中数学中函数又被定义为两集合元素之间的映射。现在，我们要把后

2、一个定义作进一步的深化，用一个特殊关系来具体规定这一映射，称这个特殊关系为函数，因为关系是一个集合，从而又将函数作为集合来研究。离散结构之间的函数关系在计算机科学研究中也已显示出极其重要的意义。我们在讨论函数的一般特征时，总把注意力集中在离散结构之间的函数关系上，但这并不意味着这些讨论不适用于其它函数关系。考虑下面几个由图示表示的集合A到集合B的关系（见图4.1.1）。在这６个关系中，后４个关系R3，R4，R5，R6与R1，R2不同，它们都有下面两个特点：（1）其定义域为A；（2）A中任一元素a对应唯一一个B中的元素b。图4.

3、1.1几个关系的示图图4.1.1几个关系的示图图4.1.1几个关系的示图定义4-1.1设X和Y是任何两个集合，而f是X到Y的一个关系（fXY），如果对于每一个xX，都有唯一的yY，使f。则称f是X到Y的函数（functions），记为f：X→Y，当X=X1…Xn时，称f为n元函数。函数也称映射（mapping）或变换(transformation）。换言之，函数是特殊的关系，它满足（1）函数的定义域是X，而不能是X的某个真子集(即dom(f)=X)。（2）若〈x,y〉∈f，〈x,y′〉∈f，则y＝y′（

4、单值性）。图4.1.2由于函数的第二个特性，人们常把〈x,y〉∈f或xfy这两种关系表示形式，在f为函数时改为y=f(x)。这时称x为自变量，y为函数在x处的值；也称y为x在f作用下的像(imageofxunderf)，x为y的原像。一个自变量只能有唯一的像，但不同的自变量允许有共同的像。注意，函数的上述表示形式不适用于一般关系。（因为一般关系不具有单值性。）【例1】设A={a,b},B={1,2,3}，判断下列集合是否是A到B的函数。F1={〈a,1〉,〈b,2〉},F2={〈a,1〉,〈b,1〉}，F3={〈a,1〉,〈a

5、,2〉},F4={〈a,3〉}【例2】下列关系中哪些能构成函数？（1）{〈x,y〉

6、x,y∈N,x+y<10}（2）{〈x,y〉

7、x,y∈N,x+y=10}（3）{〈x,y〉

8、x,y∈R,

9、x

10、=y}（4）{〈x,y〉

11、x,y∈R,x=

12、y

13、}（5）{〈x,y〉

14、x,y∈R,

15、x

16、=

17、y

18、}对于函数f：X→Y,f的前域dom(f)=X就是函数y=f(x)的定义域,有时也记为Df,f的值域ran(f)Y,有时也记为Rf,即Rf=Y称为f的共域,ran(f)=Rf也称为f的像集合,dom(f)=X=Df也称为f的原像集。对于AX，

19、称f(A)为A的像（imageofA），定义为f(A)=显然,f()=,f({x})={f(x)}(x∈A)。定义4-1.2设函数f:A→B，g:C→D，如果A=C，B=D，且对所有xA和xC，都有f(x)=g(x)，则称函数f等于函数g,记为f=g。如果AC，B＝D，且对每一xA，f(x)＝g(x)。则称函数f包含于函数g，记为fg。设X和Y都是有限集合，X=m，Y=n，由于从X到Y任意一个函数f的定义域都是X，每一个f都有m个序偶（象存在性），那么{ff:X→Y}的基数为nm。即共有nm个X到Y的函数。

20、【例3】设A={a,b},B={1,2,3}。由A→B能生成多少个不同的函数？由B→A能生成多少个不同的函数？解:设fi:A→B(i=1,2,…，9),gi:B→A(i=1,2,…，8)f1={〈a,1〉,〈b,1〉}g1={〈1,a〉,〈2,a〉,〈3,a〉}f2={〈a,1〉,〈b,2〉}g2={〈1,a〉,〈2,a〉,〈3,b〉}f3={〈a,1〉,〈b,3〉}g3={〈1,a〉,〈2,b〉,〈3,a〉}f4={〈a,2〉,〈b,1〉}g4={〈1,a〉,〈2,b〉,〈3,b〉}f5={〈a,2〉,〈b,2〉}g5={〈

21、1,b〉,〈2,a〉,〈3,a〉}f6={〈a,2〉,〈b,3〉}g6={〈1,a〉,〈2,a〉,〈3,b〉}f7={〈a,3〉,〈b,1〉}g7={〈1,b〉,〈2,a〉,〈3,b〉}f8={〈a,3〉,〈b,2〉}g8={〈1,b〉,〈2,b〉,〈3,b〉}f9={〈a,