离散数学第五章 函数.ppt

《离散数学第五章 函数.ppt》由会员分享，可在线阅读，更多相关《离散数学第五章 函数.ppt（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、、可计算性理论等领域中，函数都有着极其广泛的应用。PART PART 0101函数的基本概念和性质主要内容PART PART 0 02 2函数的合成和合成函数的性质PART PART 0 03 3特殊函数PART PART 0 04 4反函数PART PART 0 05 5特征函数PART PART 0 06 6基数PART PART 0 07 7不可解问题5.1 函数的基本概念和性质n定义5.1 设 A和 B是两个任意的集合，并且 f是从 A 到B 的一种关系。如果对于每一个 ，都存在唯一的 ，使得 ，则称关系 f为函数或映射，并记作n对于函数 来说，如果有 ，则称 x 是自变量；与 x相对

3、应的 y，称为在 f作用下 x的像点，或称 y是函数 f 在 x 处的值。通常用 表示 。4函数5.1 函数的基本概念和性质n从A 到 B的函数 f，是具有下列性质的从 A 到 B 的二元关系。（1）每一个元素 ，都必须关系到某一个 ；也就是说，关系 f 的定义域是集合 A本身，而不是 A 的真子集。（2）如果有 ，则函数 f 在 x 处的值y是唯一的，亦即 因为函数是关系，所以关系的一些术语也适用于函数。例如，如果f是从A到 B的函数，则集合A是函数 f 的定义域，亦即 ；集合 B 称为 f 的陪域；是 f 的值域，且 。有时也用 表示 f 的值域 ，亦即 有时也称 是函数 f 的像点。55

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

5、f 和 g 是相等的，记作 75.1 函数的基本概念和性质n定义5.3 给定函数 ，且有 。（1）试构建一个从 A到 Y的函数通常称 g是函数 f 的缩小，并记作 。（2）如果 g是 f 的缩小，则称 f 是 g 的扩大。从定义可以看出，函数 的定义域是集合 A，而函数 f 的定义域则是集合 X。和 f 的陪域均是集合Y。于是若 g是 f 的缩小，则应和 并且对于任何 都有85.1 函数的基本概念和性质n例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到 上的扩大

6、（或称延拓）。95.1 函数的基本概念和性质因为函数是二元关系，所以可以用关系图和关系矩阵来表达函数。此外，由函数的定义可知，在关系矩阵的每一个行上，都有且仅有一个元素的值是1，而此行上的其他元素都必定为0。因此，可以用一个单独的列来代替关系矩阵。在这个单独的列上，应标明所对应的给定函数的各个值。这样，该列上的各元素也说明了自变量与其函数值之间的对应关系。10函数 f:XY 的图解5.1 函数的基本概念和性质n例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 的简化关

7、系矩阵为：115.1 函数的基本概念和性质n定义5.4 设A和B是任意两个集合，记：为从A到B的所有函数的集合。n例5.6 设集合X=a,b,c和集合Y=0,1。试求出所有可能的函数f:XY。解：首先求出的XY所有序偶，于是应有 于是，有26 个可能的子集，但其中仅有下列23个子集可以用来定义函数：125.1 函数的基本概念和性质n设A和B都是有限集合，且|A|=m和|B|=n，因为任何函数f:AB的域都是集合A，所以每个函数中都恰有m个序偶。而且，任何元素x A，都可以在B的n个元素中任选其一作为自己的象点。因此，应有nm 个可能的不同函数，亦即|BA|=|B|A|=nmn例5.7 设A为任

8、意集合，B为任意非空集合。（1）因为存在唯一的一个从到A的函数，所以A=。（2）因为不存在从B到的函数，所以B=。13PART PART 0101函数的基本概念和性质主要内容PART PART 0 02 2函数的合成和合成函数的性质PART PART 0 03 3特殊函数PART PART 0 04 4反函数PART PART 0 05 5特征函数PART PART 0 06 6基数PART PART 0 07 7不可解问题5.2 函数的合成和合成函数的性质n定义5.5 设f:XY和g:YZ是两个函数。于是，合成关系fg为f与g的合成函数，并用gf表示。即 n注意：合成函数g f 与合成关系

9、f g 实际上表示同一个集合。这种表示方法的不同有其方便之处：对合成函数gf，当z=(gf)(x)时，必有z=g(f(x)gf与g(f(x)的次序是理想的。155.2 函数的合成和合成函数的性质n定理5.1 设 和 是两个函数。（1）合成函数 是从 的函数，并且，对于每一个 ，都有 。（2）其中 表示 g 的定义域在 f 下的原像集，表示 f 的值域在 g下的像点集。165.2 函数的合成和合成函数的性质n例5.8 设集合X=x1,x2,x3,x4,Y=y1,y2,y3,y4,y5，Z=z1,z2,z3。函数f:XY和g:YZ分别是试求出函数gf=XZ，并给出它的图解。解：175.2 函数的合

10、成和合成函数的性质n例5.9 设集合 ，函数 和 分别为 试求出合成函数 ，,。解：由上面的例子可以看出，即函数的合成运算是不可交换的，但它是可结合的。185.2 函数的合成和合成函数的性质n定理5.2 函数的合成运算是可结合的，即如果 f,g,h 都是函数，则应有下面把恒等式所给出的关系，推广到更为一般的情况。设有 n个函数：，于是无括号表达式，唯一地表达了从 到 的函数。如果 和 ，则可用 表示从 X 到 X 的合成函数 。195.2 函数的合成和合成函数的性质n例5.10 设Z是整数集合，并且函数f:ZZ给定成f(i)=2i+1。试求出合成函数f3(i)。解：合成函数 f3(i)是一个由

11、Z到Z的函数，于是有 205.2 函数的合成和合成函数的性质n定义5.6 给定函数f:XX，如果有f2=f，则称f是个等幂函数。n例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等幂函数PART PART 0101函数的基本概念和性质主要内容PART PART 0 02 2函数的合成和合成函数的性质PART PART 0 03 3特殊函数PART PART 0 04 4

12、反函数PART PART 0 05 5特征函数PART PART 0 06 6基数PART PART 0 07 7不可解问题5.3 特殊函数某些类型的函数，具有一些十分重要的性质，而这些性质对于我们研究某些具体领域中的实际问题是十分有用的。例如，可以通过双射函数来研究无限集的基数的比较，通过特征函数来研究集合间的关系等等。下面我们将专门定义这些函数，并且给出相应的术语。235.3 特殊函数n定义5.7 给定函数 f:XY。（a）如果函数f的值域 Rf=Y，则称f为映上的映射，或称满射函数满射函数。（b）如果函数f的值域 Rf Y，则称f为映入的映射或内射内射。n定义5.8 给定函数 f:XY,

13、对于x1,x2 X来说，如果有 或者是则称f为一对一的映射，或称f为单射函数单射函数。245.3 特殊函数n定义5.9 给定函数f:XY。如果f既是满射的又是单射的，则称f为一对一映满的映射，或称f为双射函数双射函数。n定义中的条件说明构成双射函数的必要条件是 。后面我们将会看到，如果两个无限集之间存在一个双射函数，那么这两个无限集是等势的。255.3 特殊函数n例5.12 判断下列函数是否为单射、满射、双射的，并给出原因。（1）（2）为正整数集。（3）（4）为正实数集。解：（1）函数f(x)为开口向下的抛物线，不是单调函数，并且在x=1处取得极大值0，因此它既不是单射也不是满射的。（2）函数

14、 f(x)是单调上升的，因此是单射的。但不是满射的，因为（3）函数 f(x)是满射，单射和双射的。因为它是单调函数并且（4）函数 f(x)既不是单射的，也不是满射的。因为当x=1 和 x=4时 f(x)=4，所以 f(x)不是单射的。当 时，f(x)取得最小值 ，所以f(x)不是满射的。265.3 特殊函数n定理5.3 给定函数f和g，并且有合成函数gf。于是（a）如果f和g都是满射函数，则合成函数gf也是个满射函数。（b）如果f和g都是单射函数，则合成函数gf也是个单射函数。（c）如果f和g都是双射函数，则合成函数gf也是个双射函数。275.3 特殊函数 285.3 特殊函数n定理5.4：给

15、定函数f和g，并且有合成函数gf,于是（1）如果gf是满射函数，则g必定是满射的。（2）如果gf是个单射函数，则f必定是个单射函数。（3）如果gf是个双射函数，则g必定是满射的，f是单射的。295.3 特殊函数 305.3 特殊函数n定义5.10：给定集合X，并且有函数IX:XX。对于所有的xX，有IX(x)=x，亦即IX=|x X则称IX为恒等函数。315.3 特殊函数n定理5.5 给定集合X 和Y。对于任何函数 f:XY，都有f=fIX=IYf证明：设xX和yY，根据定义IX(x)=x,IY(y)=y，得证！32PART PART 0101函数的基本概念和性质主要内容PART PART 0

16、 02 2函数的合成和合成函数的性质PART PART 0 03 3特殊函数PART PART 0 04 4反函数PART PART 0 05 5特征函数PART PART 0 06 6基数PART PART 0 07 7不可解问题5.4 反函数n定义5.11 设 是一个双射函数。于是f的逆关系是f的反函数（或称逆函数），并记作 。对于f来说，如果存在 ，则函数f是可逆的。应该注意，仅当 是双射函数时，才有对应于 的反函数 。若存在函数 ，使得 ，则称 g 为 f 的左逆；若存在函数 ，使得 ，则称 g 为 f 的右逆。345.4 反函数n定理5.6 设 是一个双射函数。于是，反函数 也是一个

17、双射函数，并且是从 Y 到 X 的函数 。355.4 反函数n定理5.6 设 是一个双射函数。于是，反函数 也是一个双射函数，并且是从 Y 到 X 的函数 。365.4 反函数n定理5.7 如果函数 是可逆的，则有 37函数 f 和 的合成，总会生成一个恒等函数，由于合成的次序不同，合成函数的值域或者是集合 X，或者是集合 Y。5.4 反函数n例5.15 给定集合 和 并且函数 给定成 ，反函数 给定成 。试求出 和 。解：n定理5.8 如果 f 是个双射函数，则应有 385.4 反函数n定理5.9 给定函数 和 ，并且 f 和 g 都是可逆的。于是应有n例5.16 给定集合 ，和 设函数 和

18、 分别为：，。试说明解：39PART PART 0101函数的基本概念和性质主要内容PART PART 0 02 2函数的合成和合成函数的性质PART PART 0 03 3特殊函数PART PART 0 04 4反函数PART PART 0 05 5特征函数PART PART 0 06 6基数PART PART 0 07 7不可解问题5.5 特征函数n定义5.12 设 X 为任意集合，f 和 g 是从 X 到 Y 的函数。（1）表示，对每个 ，皆有（2），对每个 皆有，称 f+g 为 f 和 g 的和 （3），对每个 皆有，称 f-g 为 f 和 g 的差。（4），对每个 皆有，称 f*g

19、为 f 和 g 的积。415.5 特征函数n定义5.13 设 E 为全集，为如下定义的从 E 到 0,1 的函数。称 为集合 A 的特征函数。425.5 特征函数n下面列举特征函数的一些重要性质，其中 0 表示从 E 到 0,1 的函数 1表示从 E 到 0,1 的函数（1）0 1,对于任意的 成立。（2），当且仅当 。（3），当且仅当（4），当且仅当（5），当且仅当（6）=1-（7）（8）（9）（10）当且仅当（11）435.5 特征函数n例5.18 用特征函数证明证明：通过直接计算可得及所以 从而得到 44PART PART 0101函数的基本概念和性质主要内容PART PART 0 02

20、 2函数的合成和合成函数的性质PART PART 0 03 3特殊函数PART PART 0 04 4反函数PART PART 0 05 5特征函数PART PART 0 06 6基数PART PART 0 07 7不可解问题5.6 基数n定义5.14 设 A 和 B 是两个集合。从 A 到 B 如果存在一个双射函数 ，则称 A 和 B 是等位的或等势的，记作 ，读作A等势于B。n例5.19 设集合 ,试证明 。解：设 ，且对于 ，令 。显然，f 是从N到 的双射函数，因而有 。46等势（等位）这里 。对于有限集绝不会有这种情况。这既是有限集和无限集之间本质上的差别，也是对无限集的一种定义方法

21、。5.6 基数n定义5.15 设 A 和 B 为两个集合。（1）如果 ，就称 A 和 B 的基数相等，记为（2）如果存在从 A到 B的单射，就称 A的基数小于等于B 的基数，记为|A|B|。（3）如果 且 ，就称 A的基数小于 B 的基数，记为|A|B|。任何两个基数都可以比较大小。对于无限集的基数，我们规定特殊的记号，令 ，读作阿列夫零；令实数集合 R 的基数为 ，读作阿列夫一。475.6 基数n例5.21 设 A为任意集合，则证明：构建函数 ，其中 是集合 的特征函数。很明显 f 为双射函数，因此有n定理5.10 设 A，B，C为任意集合。（1）（2）若 ，则（3）若 ，则 485.6 基

22、数n定理5.11 （康托定理）（1）（2）对于任意集合A 都有 49康托定理5.6 基数n定义5.17 如果集合 A 同自然数集合或自然数集合的真子集等势，则称 是可计数的或可数集；否则称 A是不可计数的或不可数集。从定义可以看出，不是所有无限集合都是可数的。例如，实数集合就是不可数的。至此，我们可以得出如下的结论。（1）和自然数等势的无限集的基数为（2）和实数集合等势的无限集的基数为（3）505.6 基数在计算机科学中，广泛地应用了本节的概念，特别是可计算性理论。在非数值系统中的元素与自然数之间，可以制定出一种双射函数关系。这样就能够把非数值系统中的命题，变换成相对应的自然数的命题。因此，可

23、以用证明自然数系统中相应的命题，来间接地证明非数值系统中给定的命题。51PART PART 0101函数的基本概念和性质主要内容PART PART 0 02 2函数的合成和合成函数的性质PART PART 0 03 3特殊函数PART PART 0 04 4反函数PART PART 0 05 5特征函数PART PART 0 06 6基数PART PART 0 07 7不可解问题5.7*不可解问题 现代数字计算机已经应用于社会生活的各个方面，似乎计算机无所不能，若不考虑运算时间的限制，对于任何问题，只要能把它抽象成计算机可接受的输入形式，就能用计算机进行求解。然后，实际情况并非如此，可计算性理

24、论告诉我们：确实存在计算机无法解决的问题，尽管他们可以表示成计算机可接受的输入形式。以下将粗浅的讨论一下可计算性的问题，首先利用可数集的概念证明不可计算的问题确实存在，然后给出著名的不可判定的停机问题。535.7*不可解问题 所谓不可解问题是指使用数字计算机无法解决的问题，在这里更具体地说，就是指使用某种程序设计语言无法解决的问题，即不存在可为它们求解的程序。下面将说明不可解问题确实存在。基本方法是：首先说明程序的集合是无限可数的，然后说明问题的集合是无限不可数的，所以问题比程序多得多，确实无法为每个问题都编写出解决它的程序。假定所考察的程序设计语言是C语言（其他程序设计语言也可以）。C语言的

25、字符集是有限集，设为 。C语言（源程序）是 中的字符所构成的有限字符串。设所有的合法的C程序组成集合 C 则 ，其中 是 上有限字符串的集合。由于 是有限集，而字符串长度 ，因此 是可数集，所以 C 也是可数集。54不可解问题存在性5.7*不可解问题 任何问题都可以抽象为从输入到输出的函数，通过适当的编码，输入和输出可以分别编码为两个自然数，所以可以用自然数集 N上的函数来为问题建模。反过来，N上的函数也都是问题。于是，可以用 N上的函数的集合来为问题的集合建立数学模型。设自然数集 N 上的函数的集合是 F，则 由康托定理可知F是不可数集。因此 C 为可数，F 为不可数，所以一定存在某个函数（

26、问题），计算它的程序是不存在的。55不可解问题存在性5.7*不可解问题 具有实际应用价值的不可解问题是否存在？答案是肯定的，著名的停机问题就是其中之一。停机问题是不可解问题的经典例子，它的不可解性是计算机科学中最著名的定理之一，图灵在1936年证明了停机问题的不可解性。停机问题的定义如下。输入：一个程序和这个程序要处理的一个输入。输出：若改程序在该输入下能终止，则输出“是”，否则，输出“否”。停机问题是一个很有意义的现实问题，它的成功解决将对程序员的工作提供很大的帮助，比如，自动判断程序中是否有死循环等等。但是，遗憾的是这样的检测工具是构造不出来的56停机问题5.7*不可解问题 在证明停机问题

27、的不可解性之前，首先注意，不能通过简单的运行一个程序并观察它的行为来确定在给定的输入下它是否能终止。若程序运行一段时间后停止了，则可以简单的得出答案。但是若在运行一段时间之后未停止，则无法确定它是永不停机，还是我们等待的时间不够。假定停机问题是可借的，有一个名为halt的解决停机问题的C函数：int halt(char*prog,char*input)它有两个输入：“*prog”是一个C函数的源代码字符串，“*input”是表示输入的字符串。如果函数“*prog”在给定的输入“*input”下能终止，halt返回1，否则返回0。57停机问题5.7*不可解问题 再给出一个简单的函数contrar

28、y如下。void contrary(char*prog)if(halt(prog,prog)while(1);现将函数contrary本身作为输入调用contrary，考察其执行过程。（1）若其中对halt的调用返回1，则表明contrary在对自身运行时将会停机。但是分析contrary的源代码可以发现，在这种情况下，contrary将进入一个无限循环，从而不会停机。这是矛盾的。（2）若其中对halt的调用返回0，则表明contrary在对自身运行时将不会停机。但是contrary的源代码表明，在这种情况下，contrary不会进入无限循环，从而将停机。这也是矛盾的。两种情况都有矛盾，所以，

29、函数halt实际上是构造不出来的，即停机问题不可解。通过把某个已知的不可解问题归约到新问题的方法，可以证明新问题也是不可解的。58停机问题5.7*不可解问题n例5.23 考虑如下的停机问题的变体零输入停机问题。输入：一个没有输入的程序。输出：若该程序能终止，则输出“是”，否则输出“否”。解：假定零输入停机问题是可解的，有一个函数int ehalt(char*prog)其输入是一个没有输入的程序。若被输入的程序能终止，则ehalt返回1，否则ehalt返回0。可以利用ehalt构造halt，即把停机问题归约到零输入停机问题，这样就得到解决停机问题的一个算法，这与已证明的结论（停机问题是不可解的）矛盾，从而证明零输入停机问题也是不可解的。59停机问题5.7*不可解问题n具体归纳方法如下。（1）把halt的输入程序 P和输入字符串 I 改造成一个没有输入的程序 ，并使得 能终止当且仅当程序 P 在输入 I 下能终止。这种改造可以通过修改程序 P，把 I 作为它的一个静态变量 S 存储，并进一步修改 P 中对输入的引用，使它们从 S中得到输入，经过如此改造的程序即为 。（2）对 调用ehalt。（3）直接输出ehalt()的返回值。上述证明使用了可计算性证明中的一个常规技术，即用一个程序修改另一个程序。60停机问题61