离散数学 陈志奎 第五章 函数

《离散数学 陈志奎 第五章 函数》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章函数离散数学陈志奎主编人民邮电出版社前言函数是满足某些条件的二元关系。这里所要讨论的是离散函数，它能把一个有限集合变换成另一个有限集合。计算机执行任何程序都属于这样一种变换。通常，总是认为函数是输入和输出之间的一种关系，即对于每一个输入或自变量，函数都能产生一个输出或函数值。因此，可以把计算机的输出看成是输入的函数。编译程序则能把一个源程序变换成一个机器语言的指令集合目标程序。在本章中，首先将定义一般的函数，然后讨论特种函数，由一种特殊函数——双射函数引出不可数集合基数的比较方法。在以后的各章中，这些概念将起着重要

2、作用。在开关理论、自动机理论、可计算性理论等领域中，函数都有着极其广泛的应用。PART01函数的基本概念和性质主要内容PART02函数的合成和合成函数的性质PART03特殊函数PART04反函数PART05特征函数PART06基数PART07不可解问题5.1函数的基本概念和性质定义5.1设A和B是两个任意的集合，并且f是从A到B的一种关系。如果对于每一个，都存在唯一的，使得，则称关系f为函数或映射，并记作对于函数来说，如果有，则称x是自变量；与x相对应的y，称为在f作用下x的像点，或称y是函数f在x处的值。通常用表示。4

3、函数5.1函数的基本概念和性质从A到B的函数f，是具有下列性质的从A到B的二元关系。（1）每一个元素，都必须关系到某一个；也就是说，关系f的定义域是集合A本身，而不是A的真子集。（2）如果有，则函数f在x处的值y是唯一的，亦即因为函数是关系，所以关系的一些术语也适用于函数。例如，如果f是从A到B的函数，则集合A是函数f的定义域，亦即；集合B称为f的陪域；是f的值域，且。有时也用表示f的值域，亦即有时也称是函数f的像点。55.1函数的基本概念和性质例5.1设E是全集，是P(E)的幂集。对任何两个集合的并运算和相交运算，都是

4、从到p(E)的映射；对任何集合的求补运算，则是从到的映射。例5.2试说明下面的二元关系是否是函数。（1）（2）解：（1）是函数，满足函数的任意性和唯一性条件；（2）不是函数，不满足唯一性条件。例如时，。此例告诉我们，这里给出的函数的概念和高等数学中给出的函数的概念是有所区别的，在高等数学中，一直是把反正弦当作函数的。65.1函数的基本概念和性质定义5.2给定函数和。如果f和g具有同样的定义域和陪域，亦即和，并且对于所有的或都有，则称函数f和g是相等的，记作75.1函数的基本概念和性质定义5.3给定函数，且有。（1）试构建

5、一个从A到Y的函数通常称g是函数f的缩小，并记作。（2）如果g是f的缩小，则称f是g的扩大。从定义可以看出，函数的定义域是集合A，而函数f的定义域则是集合X。和f的陪域均是集合Y。于是若g是f的缩小，则应和并且对于任何都有85.1函数的基本概念和性质例5.4：令X1={0,1},X2={0,1,2},Y={a,b,c,d}。定义从到Y的函数f为：f={<0,0,a>,<0,1,b>,<1,0,c>,<1,1,b>}。g=f{<0,2,a>,<1,2,c>,<2,0,b>,<2,1,a>,<2,2,d>}是从到Y的函数。

6、于是f=g/，因此f是g在上的缩小（或称限制），g是f到上的扩大（或称延拓）。95.1函数的基本概念和性质因为函数是二元关系，所以可以用关系图和关系矩阵来表达函数。此外，由函数的定义可知，在关系矩阵的每一个行上，都有且仅有一个元素的值是1，而此行上的其他元素都必定为0。因此，可以用一个单独的列来代替关系矩阵。在这个单独的列上，应标明所对应的给定函数的各个值。这样，该列上的各元素也说明了自变量与其函数值之间的对应关系。10函数f:X→Y的图解5.1函数的基本概念和性质例5.5设集合X={a,b,c,d}和Y={1,2,3,

7、4,5}，并且有f={,,,}试求出domf，ranf和f的矩阵表达式。解：domf={a,b,c,d}ranf={1,3,4}f的简化关系矩阵为：115.1函数的基本概念和性质定义5.4设A和B是任意两个集合，记：为从A到B的所有函数的集合。例5.6设集合X={a,b,c}和集合Y={0,1}。试求出所有可能的函数f:X→Y。解：首先求出的X×Y所有序偶，于是应有于是，有26个可能的子集，但其中仅有下列23个子集可以用来定义函数：125.1函数的基本概念和性质设A和B都是有限集合

8、，且

9、A

10、=m和

11、B

12、=n，因为任何函数f:A→B的域都是集合A，所以每个函数中都恰有m个序偶。而且，任何元素x∈A，都可以在B的n个元素中任选其一作为自己的象点。因此，应有nm个可能的不同函数，亦即

13、BA

14、=

15、B

16、

17、A

18、=nm例5.7设A为任意集合，B为任意非空集合。（1）因为存在唯一的一个从Ф到A的函数，所以AФ