离散数学(第13讲)函数1

《离散数学(第13讲)函数1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章函数(1)栾新成四川大学软件学院luanxch@sina.com8599782213808024081主要内容1、函数的基本概念2、单射、满射、双射和逆函数3、函数的递归定义2021年7月10日2概述函数是一种特殊的二元关系,我们可以把函数看作输入输出关系;它把一个集合(输入集合)的元素变成另一个集合(输出集合)的元素。在高等数学中，函数的概念是从变量的角度提出来，而且是在实数集合上讨论，这种函数一般是连续或间断连续的函数。这里，将连续函数的概念推广到对离散量的讨论。前面所讨论的有关集合或关系的运算和性质，对于函数完全适用。任何程序在计算机中的实现,都包含种种这样或

2、那样的变换。如编译程序把一个源程序变换成机器语言的指令集合—目标程序。或者说,计算机中的程序可以把一定范围内的任一组数据变换成另一组数据。函数是许多数学工具的基础,计算机科学中大量用到函数,如数据结构,程序语言的设计与实现,开关理论,自动机理论,代数结构,可计算性理论,计算复杂性,程序正确性证明等。2021年7月10日3一般集合的函数概念定义6-1.1设f是集合A到B的关系，如果对每个x∈A，都存在惟一的y∈B，使得∈f，则称关系f为A到B的函数（或映射、变换），记为f：A→B。当∈f时，通常记为y=f(x)，这时称x为函数的自变量，称y为x在f下的函

3、数值（或映象）。由函数的定义显然有：(1)domf=A，称为函数f的定义域；(2)ranf=B，称为函数f的值域，ranf也可记为f(A)，并称f(A)为A在f下的象；(3)∈f∧∈fy=z；(4)

4、f

5、=

6、A

7、。注意，f(x)仅表示一个变值，但f则代表一个集合，因此f≠f(x)。2021年7月10日4一般集合的函数概念例6.1判断下图所示的几个关系是否是函数：解f3、f4、f5、f6都是函数，但f1、f2则不是函数。因f1中A的元素5没出现在序偶的第一元素中，f2中A的元素4出现在两个不同序偶的第一元素中。2021年7月10日5函数与关系的差别20

8、21年7月10日6如果记由此可以知道，函数确是一种特殊的关系，它与一般关系比较具备如下差别：(1)A×B的任何一个子集，都是A到B的二元关系，因此，从A到B的不同的关系有2

9、A

10、

11、B

12、个；但从A到B的不同的函数却仅有

13、B

14、

15、A

16、个。(2)每一个函数的基数都为

17、A

18、个，但关系的基数却可以从零一直到

19、A

20、×

21、B

22、。(3)每一个函数中序偶的第一个元素一定是互不相同的。函数与关系的差别例6.2设A＝{a,b}，B＝{1,2}，A×B＝{,,,}，此时从A到B的不同的关系有24＝16个。分别如下：R0＝Φ；R1＝{}；R2＝{

23、}；R3＝{}；R4＝{}；R5＝{,}；R6＝{,}；R7＝{,}；R8＝{,}；R9＝{,}；R10＝{,}；R11＝{,,}；R12＝{,,}；R13＝{,,}；2021年7月10日7函数与关系的差别R14＝{,,}；R15＝{,,,}。从A到B的不同的函数

24、仅有22＝4个。分别如下：f1＝{,}；f2＝{,}；f3＝{,}；f4＝{,}。常将从A到B的一切函数构成的集合记为BA：BA＝｛f

25、f：A→B}2021年7月10日8函数的复合运算定义6-1.2设f和g：X→Y是两个函数，如果对xX,都有f(x)=g(x),则称f与g相等，记为f=g。定义6-1.3设f：X→Y，g：Y→Z是两个函数，称gf={︱（yY）[y=f(x)∧z=g(y)]}称为函数f与g的复合函数，记为gf：X→Z。(gf)（x）=g（f（x））函

26、数复合的性质1)函数复合是可结合的(∵关系的复合是可结合的)2)函数复合一般是不可交换的,2021年7月10日9由于历史的原因，函数f和g的复合记成了g◦f的形式，与关系的复合记法相反单射、满射和双射定义6-2.1设f是从X到Y的函数，若f满足：对任意x1,x2∈X，若x1≠x2，则f(x1)≠f(x2)，则称f为从X到Y的单射或1-1映射；若ranf＝Y，则称f为从X到Y的满射或从X到Y上的映射；若f既是从X到Y的满射，又是从X到Y的单射，则称f为从X到Y的双射或一一对应的映射。若X＝Y，则称f为X上的函数；当X上的函数f是