《离散数学教学课件 ppt 作者 陈志奎 第五章 函数》由会员分享，可在线阅读，更多相关《离散数学教学课件 ppt 作者 陈志奎 第五章 函数（61页珍藏版）》请在金锄头文库上搜索。
1、,第五章 函数,离散数学 陈志奎主编 人民邮电出版社,前言,函数是满足某些条件的二元关系。这里所要讨论的是离散函数，它能把一个有限集合变换成另一个有限集合。计算机执行任何程序都属于这样一种变换。通常，总是认为函数是输入和输出之间的一种关系，即对于每一个输入或自变量，函数都能产生一个输出或函数值。因此，可以把计算机的输出看成是输入的函数。编译程序则能把一个源程序变换成一个机器语言的指令集合目标程序。 在本章中，首先将定义一般的函数，然后讨论特种函数，由一种特殊函数双射函数引出不可数集合基数的比较方法。在以后的各章中，这些概念将起着重要作用。在开关理论、自动机理论、可计算性理论等领域中，函数都有着
2、极其广泛的应用。,函数的基本概念和性质,主要内容,函数的合成和合成函数的性质,特殊函数,反函数,特征函数,基数,不可解问题,5.1 函数的基本概念和性质,定义5.1 设 A和 B是两个任意的集合，并且 f是从 A 到B 的一种关系。如果对于每一个 ，都存在唯一的 ，使得 ，则称关系 f为函数或映射，并记作 对于函数 来说，如果有 ，则称 x 是自变量；与 x相对应的 y，称为在 f作用下 x的像点，或称 y是函数 f 在 x 处的值。通常用 表示 。,4,函数,5.1 函数的基本概念和性质,从A 到 B的函数 f，是具有下列性质的从 A 到 B 的二元关系。 （1）每一个元素 ，都必须关系到某
3、一个 ；也就是说，关系 f 的定义域是集合 A本身，而不是 A 的真子集。 （2）如果有 ，则函数 f 在 x 处的值y是唯一的，亦即 因为函数是关系，所以关系的一些术语也适用于函数。例如，如果f是从A到 B的函数，则集合A是函数 f 的定义域，亦即 ；集合 B 称为 f 的陪域； 是 f 的值域，且 。有时也用 表示 f 的值域 ，亦即 有时也称 是函数 f 的像点。,5,5.1 函数的基本概念和性质,例5.1 设 E 是全集， 是P(E) 的幂集。对任何两个集合 的并运算和相交运算，都是从 到 p(E) 的映射；对任何集合 的求补运算，则是从 到 的映射。 例5.2 试说明下面的二元关系是
4、否是函数。 （1） （2） 解：（1）是函数，满足函数的任意性和唯一性条件；（2）不是函数，不满足唯一性条件。例如 时， 。此例告诉我们，这里给出的函数的概念和高等数学中给出的函数的概念是有所区别的，在高等数学中，一直是把反正弦 当作函数的。,6,5.1 函数的基本概念和性质,定义5.2 给定函数 和 。如果 f 和 g 具有同样的定义域和陪域，亦即 和 ，并且对于所有的 或 都有 ，则称函数 f 和 g 是相等的，记作,7,5.1 函数的基本概念和性质,定义5.3 给定函数 ，且有 。 （1）试构建一个从 A到 Y的函数 通常称 g是函数 f 的缩小，并记作 。 （2）如果 g是 f 的缩小
5、，则称 f 是 g 的扩大。 从定义可以看出，函数 的定义域是集合 A，而函数 f 的定义域则是集合 X。 和 f 的陪域均是集合Y 。于是若 g是 f 的缩小，则应 和 并且对于任何 都有,8,5.1 函数的基本概念和性质,例5.4：令X1=0,1,X2=0,1,2,Y=a,b,c,d。定义从 到Y的函数f为： f=,。 g=f ,是从 到Y的函数。于是f=g/ ，因此f是g在 上的缩小（或称限制），g是f到 上的扩大（或称延拓）。,9,5.1 函数的基本概念和性质,因为函数是二元关系，所以可以用关系图和关系矩阵来表达函数。 此外，由函数的定义可知，在关系矩阵的每一个行上，都有且仅有一个元素
6、的值是1，而此行上的其他元素都必定为0。因此，可以用一个单独的列来代替关系矩阵。在这个单独的列上，应标明所对应的给定函数的各个值。这样，该列上的各元素也说明了自变量与其函数值之间的对应关系。,10,函数 f : XY 的图解,5.1 函数的基本概念和性质,例5.5 设集合X=a,b,c,d和Y=1,2,3,4,5，并且有 f=, 试求出domf，ranf 和 f 的矩阵表达式。 解： domf =a,b,c,d ranf =1,3,4 f 的简化关系矩阵为：,11,5.1 函数的基本概念和性质,定义5.4 设A和B是任意两个集合，记： 为从A到B的所有函数的集合。 例5.6 设集合X=a,b,
7、c和集合Y=0,1。试求出所有可能的函数f: XY。 解：首先求出的XY所有序偶，于是应有 于是，有26 个可能的子集，但其中仅有下列23个子集可以用来定义函数：,12,5.1 函数的基本概念和性质,设A和B都是有限集合，且|A|=m和|B|=n，因为任何函数f: AB的域都是集合A， 所以每个函数中都恰有m个序偶。而且，任何元素x A，都可以在B的n个元素中任选其一作为自己的象点。因此，应有nm 个可能的不同函数，亦即 |BA|=|B|A|=nm 例5.7 设A为任意集合，B为任意非空集合。 （1）因为存在唯一的一个从到A的函数，所以A=。 （2）因为不存在从B到的函数，所以B=。,13,函
8、数的基本概念和性质,主要内容,函数的合成和合成函数的性质,特殊函数,反函数,特征函数,基数,不可解问题,5.2 函数的合成和合成函数的性质,定义5.5 设f: XY和g: YZ是两个函数。于是，合成关系fg为f与g的合成函数，并用gf表示。即 注意：合成函数g f 与合成关系 f g 实际上表示同一个集合。这种表示方法的不同有其方便之处： 对合成函数gf，当z=(gf)(x)时，必有 z=g(f(x) gf与g(f(x) 的次序是理想的。,15,5.2 函数的合成和合成函数的性质,定理5.1 设 和 是两个函数。 （1）合成函数 是从 的函数，并且，对于每一个 ，都有 。 （2） 其中 表示
9、g 的定义域在 f 下的原像集， 表示 f 的值域在 g下的像点集。,16,5.2 函数的合成和合成函数的性质,例5.8 设集合X=x1,x2,x3,x4, Y=y1,y2,y3,y4,y5，Z=z1,z2,z3。函数f: XY和g: YZ分别是 试求出函数gf=XZ，并给出它的图解。 解：,17,5.2 函数的合成和合成函数的性质,例5.9 设集合 ，函数 和 分别为 试求出合成函数 ， ， , 。 解： 由上面的例子可以看出， ，即函数的合成运算是不可交换的，但它是可结合的。,18,5.2 函数的合成和合成函数的性质,定理5.2 函数的合成运算是可结合的，即如果 f , g , h 都是函
10、数，则应有 下面把恒等式所给出的关系，推广到更为一般的情况。设有 n个函数： ， ， ，于是无括号表达式，唯一地表达了从 到 的函数。如果 和 ，则可用 表示从 X 到 X 的合成函数 。,19,5.2 函数的合成和合成函数的性质,例5.10 设Z是整数集合，并且函数f: ZZ给定成f(i)=2i+1。试求出合成函数f3( i ) 。 解：合成函数 f3( i ) 是一个由Z到Z的函数，于是有,20,5.2 函数的合成和合成函数的性质,定义5.6 给定函数f: XX，如果有f2=f，则称f是个等幂函数。 例5.11 设Z是整数集合和Nm=0,1,2,m-1，并且函数f: ZNm是f(i)=i(mod m)。试证明，对于n1都有fn=f。 证明： （归纳证法）当n=2时 假设当n=k时，满足fk=f; 那么当n=k+1时， fk+1 = fkf = ff = f 得证。对于所有的n1，都有fn=f,21,等幂函数,函数的基本概念和性质,主要内容,函数的合成和合成函数的性质,特殊函数,反函数,特征函数,基数,不可解问题,5.3 特殊函数,某些类型的函数，具有一些十分重要的性质，而这些性质对于我们研究某些具体领域中的实际问题是十分有用的。例如
