第四章 函数 4.1函数的概念 数值函数可以表示为二元组的集合 数值函数是特殊的二元关系： 所涉及的元素的集合是数值的集合 同一个元素有且仅有一个后继 定义12 底函数和顶函数：R→Z 底函数x=小于或等于x的最大整数 {(x,y)x∈R，y∈Z,y≤x,且u∈Z,u≤x,有u≤y} 顶函数x=大于或等于x的最小整数 {(x,y)x∈R，y∈Z,y≥x，且u∈Z,u≥x,有u≥y} [x]=x或[x]=四舍五入

函数是数值函数的推广，取消“元素的集合是数值的集合”的限制 定义 A到B的函数（映射）f：A→B是A到B的二元关系，fA×B ，满足： （1）a∈A，b∈B，使(a, b)∈f （即dom(f)=A） （2）a∈A，b1，b2∈B，若(a, b1)，(a, b2)∈f ，则b1=b2 即在f下，A的每个元素都（唯一地）对应B中的一个且仅一个元素 这个唯一的元素表示为f(a)，称为a的像；a称为f(a)的原像（定义2） 函数图形上的特点： 对A中的每个元素，都有一个以它为尾的箭头 对A中的每个元素，只有一个以它为尾的箭头 对A中的每个元素有且只有一个以它为尾的箭头

关系的Dom和Ran(R) RAB，dom(R)={xx∈A，且y∈B，使(x, y)∈R} ran(R)={y y∈B，且x∈A，使(x, y)∈R} 定义4 f：A→B，SA S的像f(S)={f(s)s∈S}B f(A)=ran(f) 例 1 令A={a,b,c,d,e}而B={1,2,3,4}，且f(a)=2, f(b)=1, f(c)=4, f(d)=1及f(e)=1。子集S={b,c,d}的像是集合f(s)={1,4}.

4.2一对一函数和映上函数 定义5 一对一函数(单射) f：A→B，x，y∈A， f(x)=f(y)x=y 或x≠y f(x)≠f(y) 例 2 判断从{a,b,c,d}到{1,2,3,4,5}的函数f是否为一对一的，f的定义是f(a)=4, f(b)=5, f(c)=1及f(d)=3。 解： f是一对一的，因为f在它定义域的四个元素上取不同的值。 例 3 判断从整数集合到整数集合的函数f(x)= x2 是否为一对一的。 解： 函数f(x)= x2不是一对一的。因为，例如 f(1)=f(-1)=1，但1-1。

例 4 判断函数f(x)=x+1是否为一对一的。 解： 函数f(x)=x+1是一对一的。要证明这一点，只需注意在xy时，x+1y+1。 实数集上的严格单调函数必定是一对一的 定义7 映（到）上函数（满射） f：A→B，ran(f)=B 例 5 令f为从{a,b,c,d}到{1，2，3}的函数，其定义为f(a)=3，f(b)=2,f(c)=1，f(d)=3。F是映上函数吗？ 解： 由于伴域中所有三个元素均为定义域中元素的像，f是映上的。 例 6 从整数集合到整数集合的函数f(x)= x2是映上的吗？ 解： f不是映上的。因为，比如说没有x使f(x)=-1.

例 7 从整数集到整数集的函数f(x)=x+1是映上的吗？ 解： 这个函数是映上的，因为对每个整数y，都有一个整数x，使得f(x)=y。为看出这一点，只要注意f(x)=y的充分必要条件是x+1=y，而这只要令x=y-1就成立。 定义8 一一对应（双射）既是一对一的，又是映（到）上的 例 令A为集合，A上的恒等函数是函数f:AA，其中，f(x)=x，对所有xA。换言之，恒等函数f是这样的函数，它赋给每个元素的是这个元素自身。函数f是一对一的和映上的，所以是双射。

例 图1-12，几种对应

4.3反函数和函数复合 函数是特殊关系，可以仅关系运算，但结果不一定还是函数 定理 函数的复合仍然是函数。 证明： 设g：A→B、f：B→C 则对于(f g）(a) =f(g(a))，因为g是函数，所以g(a)肯定是一个唯一的值，设为b，则(f g）(a) =f(b)，又因为f是一个函数，所以同样f(b)也是一个唯一肯定的值，设为c，则(f g）(a)=c，即对(f g）：A→C，定义域中的每个元素在C中均有唯一的一个值与之相对应。这满足函数的定义。所以函数的复合仍然是函数。

例9 令g为从{a,b,c}到自己的函数，使g(a)=b，g(b)=c, g(c)=a。令f为从{a,b,c}到{1,2,3}的函数，使f(a)=3，f(b)=2，f(c)=1。而f和g的组合是什么？g和f的组合是什么？ 解： fg的定义是(fg)(a)=f(g(a))=f(b)=2，(fg)(b)=f(g(b))=f(c)=1，(fg)(c)=f(g(c))=f(a)=3。 gf是没有定义的，因为f的值域不是g的定义域的一部分。 与关系的复合一样，函数的复合也不满足交换律 函数的逆不一定是函数 一对一函数的逆不一定是函数 映上函数的逆不一定是函数 定理 f：A→B （1）f-1是函数 f是一一对应 （2）f-1f=IA，ff-1=IB (证明请见下页)

证明：(1)若f-1是函数 则f是一对一的，因为若f不是一对一的，则存在x≠y，但f(x)=f(y)=a,那么对于f-1来说，就有f-1(a)=x或y，这与f-1函数矛盾；f也是映上的，因为若f不是映上的，则A中的某个元素在B中找不到他的像，这也是与函数的定义不符合的。所以f是一一对应的。 若f是一一对应 因为f是函数，所以A中的每个元素在B中只有一个像，这也就是说若f(x)≠f(y),则x≠y，同时因为f是一对一的，即若x≠y，f(x)≠f(y)，所以对于B中的每个元素，只能有A中的一个元素与之对应；又f是满射，即B中的每个元素在A中均有原象。所以f-1是函数。 (2)假定f是从集合A到集合B的一一对应关系，那么存在反函数f-1 ，而且f-1是从A到B的一一对应关系。反函数把原函数的对应关系颠倒过来,所以当f(a)=b 时f-1 (b)=a，当f-1 (b)=a时，f(a)=b。因此， (f-1 f)(a)= f-1(f(a))= f-1(b)=a (f f-1)(b)=f(f-1(b))=f(a)=b 从而f-1 f=IA，f f-1 =IB。

4.4集合的基数 基数是对集合中的元素的数目多或少的程度的度量 有限集的基数A是集合中的元素的个数例 定义2 集合的基数相同 集合A与B的基数相同 f：A→B，f是一一对应 定义3 可数（列）集 与自然数集基数相同的集合 一个集合是可数集可以将它的所有元素排列成一个无限序列 可数集是最小的无限集，无限集都包含可数子集

例10 求证奇正整数集合是可数集合。 解： 为证明奇正整数集合是可数的，我们来建立这一集合与自然数集合之间的一对一对应关系。考虑从自然数集合N到奇正整数集合的函数f(n)=2n-1. 我们证明这是个双向一对一的映上函数，从而f是一一对应关系。要证明f是一对一的，假定f(n)=f(m)。于是2n-1=2m-1，所以n=m；要证明f是映上的，假定t是个奇正整数。于是t比某个偶数2k少1，其中k是个自然数。从而t=2k-1=f(k)。 例11 实数集R是无限集，但不是可数集 （1）(0, 1) 是无限不可数集 （2）(0, 1)与R基数相同：f(x)=tg(x-1/2) 证明： (1)倘若(0,1)可列，那么（0，1）上的实数可以排列成 ： s1,s2,…，sn，… （接下页）

现将sn(n∈N)写成十进无限小数的形式： s1=0.a11a12a13…, s2=0.a21a22a23…, s1=0.an1an2an3…, 那么，对任意n∈N,令 bn=1(ann≠1); bn=2(ann=1) 由此得到无限十进小数r=0.b1b2b3…, r∈(0,1)但对任何n，r≠sn。这与(0,1)中元素已排列成s1,s2,…，sn，… 矛盾。由此得出(0, 1) 是无限不可数集 (2)对x∈(0,1),令f(x)=tg(x-1/2)。那么f是(0,1)到实数集R的一一对应，所以(0,1)与R基数相同。 P(A)>A

4.5不可解的问题 (接下页) 4.5.1不可解问题的存在性 C语言程序的集合是可数集 F={f|f:N→N}，F中存在f,对f不能写出计算它的C程序。 证明：采用反证法，假设对F中的每个映射都可以写出计算它的C程序。 设由所有C程序组成的集合为C。 于是，F与C的一个子集等势，即 。 容易证明：C为可列集（因为C中的程序可以按其长度排成一个无限序列）。 显然，F是无限集，所以F也是可列集。（∵可列集是势最小的无限集） 所以，可设F={f1, f2,..., fn，...}。 (接下页)

(接上页证明) 定义f:N->M如下：f(n)= 显然f(n)F，所以m∈N，使f=fm。 从而，n∈N,f(n)=fm(n)。 特别地，f(m)=fm(m)。 这与f的定义矛盾。 所以，并非对F中的每个映射都可以写出计算它的C程序， 也即F中存在f,对f不能写出计算它的C程序。

4.5.2停机问题是不可解的 停机问题：编写一个C程序halt，它的输入是另一个C程序P以及该程序的输入I。 halt的输出是1，如果P在I下能终止； halt的输出是0，如果P在I下不能终止。 证明：采用反证法。 假定停机问题是可解的，有一个名为halt()的解决停机问题的函数。 int Halt(char *prog, char *input)有两个输入：*prog是程序或函数的源代码字符串，*input是表示输入的字符串。如果程序或函数*prog在给定的输入*input下能终止，则halt()返回1，否则返回0。 (接下页)

再给出一个简单的函数contrary()如下。现将函数contrary()本身作为输入调用contrary()，考察其执行过程。若对halt()的调用返回1，则halt()表明contrary()在对自身运行时将会停机，在这种情况下，contrary()将进入一个无限循环（请考察contrary()的源代码），从而不会停机；若对halt()的调用返回0，则halt()表明contrary()在对自身运行时将不会停机，而在这种情况下，contrary()不会进入无限循环，从而将停机。两种情况中都有矛盾。所以，函数halt()实际上不存在，即停机问题是不可解的。 int halt(char *prog, char *input) void contrary(char *prog) { if (halt(prog，prog)) while (1); }

习题 1.判断下面定义的几个f是不是从Z到R的函数。 a)f(n)=n b）f(n)= c)f(n)=1/(n2-4) 2.给出从N到N的例子，使得： a)一对一但非映上。 b)映上但不一对一。 c)既映上又一对一（但不同于恒等函数）。 d)既非映上又非一对一。 3.如果f和f g都是一对一的，能否得出g也是一对一的？说明理由。 4.令f为从集合A到集合B的函数，令S和T为A的子集，求证： a)f(ST)=f(S)f(T) b) f(ST)f(S)f(T)

5.含n个字位的数据需要用几个字节编码？其中n为： a)4 b)10 c)500 d)3000 6.假定f是从A到B的函数，A和B为有限集，且|A|=|B|。证明f是一对一的当且仅当它是映上的。 7.判断集合{不能被3整除的整数}是否可数，如是可数的，给出自然数集合和该集合之间的一个一对一对应。 8.证明从正整数集合到集合{0,1,2,3,4,5,6,7,8,9}的函数集合是不可数的。（提示：首先找一个0到1之间的实数集合到这些函数的一个子集的一对一对应关系。为此可以让实数 0. d1 d2 d3…dn…对应函数f，使f (n)=dn。）