离散数学及其应用 教学课件 作者 魏雪丽第4章 函数.ppt

《离散数学及其应用 教学课件 作者 魏雪丽第4章 函数.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4.1函数的基本概念(Theconceptoffunction)4.2特殊映射(Specialmappings)4.3复合函数与逆函数(CompositionsoffunctionsandInversefunctions)4.4置换(Permutation)*4.5基数(CardinalNumber)4.1函数的基本概念(Theconceptoffunction)4.1.1函数的基本概念4.1.2特殊函数类(Specialfunctions)4.1.1函数的基本概念函数概念是最基本的数学概念之一，

2、也是最重要的数学工具。初中数学中函数定义为"对自变量每一确定值都有一确定的值与之对应"的因变量；高中数学中函数又被定义为两集合元素之间的映射。现在，我们要把后一个定义作进一步的深化，用一个特殊关系来具体规定这一映射，称这个特殊关系为函数，因为关系是一个集合，从而又将函数作为集合来研究。离散结构之间的函数关系在计算机科学研究中也已显示出极其重要的意义。我们在讨论函数的一般特征时，总把注意力集中在离散结构之间的函数关系上，但这并不意味着这些讨论不适用于其它函数关系。考虑下面几个由图示表示的集合A到集合

3、B的关系（见图4.1.1）。在这６个关系中，后４个关系ρ3，ρ4，ρ5，ρ6与ρ1，ρ2不同，它们都有下面两个特点：（1）其定义域为A；（2）A中任一元素a对应唯一一个B中的元素b。图4.1.1几个关系的示图图4.1.1几个关系的示图图4.1.1几个关系的示图定义4.1.1设X，Y为集合，如果f为X到Y的关系（fX×Y），且对每一x∈X，都有唯一的y∈Y，使〈x,y〉∈f，称f为X到Y的函数（functions），记为f：X→Y。当X=X1×X2×…×Xn时，称f为n元函数。函数也称映射（m

4、apping）。换言之，函数是特殊的关系，它满足（1）函数的定义域是X，而不能是X的某个真子集(即dom(f)=X)。（2）若〈x,y〉∈f，〈x,y′〉∈f，则y＝y′（单值性）。图4.1.2由于函数的第二个特性，人们常把〈x,y〉∈f或xfy这两种关系表示形式，在f为函数时改为y=f(x)。这时称x为自变量，y为函数在x处的值；也称y为x在f作用下的像(imageofxunderf)，x为y的原像。一个自变量只能有唯一的像，但不同的自变量允许有共同的像。注意，函数的上述表示形式不适用于一般关系

5、。（因为一般关系不具有单值性。）【例1】设A={a,b},B={1,2,3}，判断下列集合是否是A到B的函数。F1={〈a,1〉,〈b,2〉},F2={〈a,1〉,〈b,1〉}，F3={〈a,1〉,〈a,2〉},F4={〈a,3〉}解F1,F2是函数，F3,F4不是函数，但若不强调是A到B的函数，则F4是函数，其定义域为{a}。【例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}（

11、4）{〈x,y〉

12、x,y∈R,x=

13、y

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

15、x,y∈R,

16、x

17、=

18、y

19、}解:只有（3）能构成函数。对于函数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的原像集。对于AX，称f(A)为A的像（imageofA），定义为f(A)=显然,f()=,f({x})={f(x)}(x∈A)。定理4.1.1设f:X→Y，

20、对任意AX，BX，有（1）f(A∪B)=f(A)∪f(B)（2）f(A∩B)f(A)∩f(B)（3）f(A)-f(B)f(A-B)在这里请注意区别函数值和像两个不同的概念。函数值f(x)∈Y,而像f(A)Y。关于像有下列性质。证明（1）对任一y∈Yy∈f(A∪B)x(x∈A∪B∧y=f(x))x((x∈A∧y=f(x))∨(x∈B∧y=f(x)))x(x∈A∧y=f(x))∨x(x∈B∧y=f(x))y∈f(A)∨y∈f(B)y∈f(A)∪f(B)因此f(A∪B)=f(

21、A)∪f(B)。（2）、（3）的证明请读者完成。注意，（2）、（3）中的包含符号不能用等号代替。我们举例说明。【例3】设X={a,b,c,d}，Y={1,2,3,4,5}，f:X→Y,如图4.1.3所示。那么，f({a})={2},f({b})={2},f({a})∩f({b})={2}f({a})-f({b})=f({a}∩{b})=f()=f({a}-{b})=f({a})={2}f({a}∩{b})f({a})∩f({b})f({a})-f({b})f({a}-{b