数理逻辑-第一章-逻辑、集合和函数-函数增长

1、数理逻辑Mathematical Logic 第一章 逻辑、集合和函数Chapter 1 Logic、set and function复习函数定义域、伴域、值域、像、原像单射、满射、双射反函数函数组合函数图像底函数、顶函数复习序列算术序列几何序列序列求和求和符号的下标移位复习1, 5, 11, 27, 65, 157, 379, 915 an=2 an-1+an-2; a0=1, a1=5. 0,2,10,30,68,130,222 n3+n 复习设X=1,2,3，Y=p,q，Z=a,b，f=(1,p),(2,p),(3,p)，g=(p,b),(q,b)，求gf 解：f: XY, g: YZ,

2、 gf: XZ gf=g(f(x) gf (1)=g(f(1)=g(p)=b; gf (2)=g(f(2)=g(p)=b; gf (2)=g(f(2)=g(p)=b; 所以， gf =(1,b), (2,b), (3,b)。复习证明：令f g是一个复合函数 若f g是满射的，则f 是满射的； 若f g是单射的，则g是单射的； 若f g是双射的，则f 是满射的，g是单射的；证明：设g: AB, f: BC (1)对C中的任意一个z，因为f g是满射的，所以A中存在一个x使得f g(x)=z，则存在B中的一个元素y，使得g(x)=y并且f(y)=z，所以，存在y使得f(y)=z，f是满射的；复习证

3、明：设g: AB, f: BC (2)对g的值域中的任意y，若存在x1,x2属于A，使得g(x1)=g(x2)=y，对于这个y存在C中的元素z，使得f(y)=z，则f(g(x1)=f(g(x2)=z，又因为f g是单射，故x1=x2，所以g是单射的。 (3) 由(1),(2)得证。当f g是满射的，g不一定是满射的；当f g是单射的，f 不一定是单射的。1.8 函数增长The Growth of Functions一、大O符号一个计算机程序实用性的重要因素之一是计算机要花多长时间才能运算完成。如将n个整数按照增序排列为n个整数重新排序所需要的时间小于f(n)微秒，其中f(n)=100nlogn

4、+25n+9要分析此程序的实用性，我们需要了解当n增长时，这一函数增长得多快常用一个专门的符号来描述函数增长一、大O符号定义：令f和g为从整数集合或实数集合到实数集合的函数。我们说f(x)是O(g(x)，如果有常数C和k，使得只要xk，就有 |f(x)|C|g(x)|O(g(x)读作f(x)是大O g(x)一、大O符号注意：要证明f(x)是O(g(x)，只要找到一对C和k，使得只要xk就有|f(x)|C|g(x)|。定义中要求的一对C和k不是唯一的。只要有一对这样的数存在，就有无穷多这样的数对；若C,k是这样的一对，那么只要C1,k1满足CC1，kk1k的x成立一、大O符号例：证明f(x)=x

5、2+2x+1是O(x2)。因为只要x1，就有x2+2x+1x2+2x2+x2=4x2根据大O的定义，取C=4，k=1所以f(x)是O(x2)；当x2时，2xx2，x2+2x+1x2+x2+x2=3x2C=3，k=2一、大O符号若f(x)是O(g(x)，而对足够大的x，h(x)是一个函数值的绝对值大于g(x)的函数，则有f(x)是O(h(x)。如果xk就有|f(x)|C|g(x)|，同时|h(x)|g(x)|对所有xk成立，那么当xk时，|f(x)|C|h(x)|成立，于是f(x)是O(h(x)。一、大O符号f(x)=x2+2x+1是O(x2)，x2可以被函数值大于x2的任何函数取代；f(x)是

6、O(x3)f(x)是O(x2+2x+7)等等x2是O(x2+2x+1)也成立一、大O符号在使用大O符号时，在f(x)是O(g(x)这一关系中，函数g总是选得尽可能小（有时选自某个参考函数集合）常用的有：g(x)=1；g(x)=logx； g(x)=nlogx；g(x)=x； g(x)=x2；g(x)=xn ；g(x)=nx ； g(x)=x!一、大O符号f(x)=x2+2x+1g(x)=x2f(x)是O(g(x)并且g(x)是O(f(x)满足上述两个大O关系的函数f(x)和g(x)称为同阶的。一、大O符号f(x)是O(g(x)还可以写作：f(x)=O(g(x)注意等号的含义：对于这些函数定义域

7、中足够大的数而言，函数f和g的之间有个不等式关系成立。巴赫曼1892年首次引入大O符号；大O符号有时也称为兰多符号；克努思（高德纳）推进了大O符号的广泛使用，他还引入了大和大符号。http:/www-/knuth/一、大O符号计算机程序设计艺术是Knuth一生中最重要的事业，他写这本书的目的是“组织和总结所知道的计算机方法的相关知识，并打下坚实的数学、历史基础”。1974年图灵奖。1999年底被美国科学家期刊（American Scientist）列为20世纪最佳12部学术专著之一。任何人发现书上的错误，都可以向他举发，并领取 $2.56美金。比尔盖茨在1995年说，“如果你认为你是一名真正优

8、秀的程序员，就去读第一卷，确定可以解决其中所有的问题。如果你能读懂整套书的话，请给我发一份你的简历。”一、大O符号例：证明7x2是O(x3)。解：只要x7，7x2k，就有x3C(7x2 )，其等价于x7C，由于x可以任意大，所以不存在这样的C；x3不是O(7x2)。一、大O符号多项式常用于估计函数的增长；希望找到一个总是可以用来估计多项式增长的结论；定理：令f(x)=anxn+an-1xn-1+a1x+a0，其中a0,a1,an-1,an为实数，那么f(x)是O(xn)。一、大O符号证：如果x1，我们有|f(x)|=|anxn+an-1xn-1+a1x+a0| |an|xn+|an-1|xn-

9、1+|a1|x+|a0| = xn(|an|+|an-1|/x+|a1|/xn-1+|a0|/xn) xn(|an|+|an-1|+|a1|+|a0|) = C xn其中C=|an|+|an-1|+|a1|+|a0|一、大O符号几个与定义域为正整数集合的函数有关的例子例：用O符号估计前n个正整数的和。解：由于前n个正整数都不超过n，所以 1+2+nn+n+n=n2 所以前n个正整数的和是O(n2)，其中C=1和k=1。一、大O符号n!=12 n；增长迅速（n=20?）20!=2 432 902 008 176 640 000例：给出阶乘函数和其对数的大O估计。解：乘积中的每一项都不超过n，所以

10、 n!=12 nnn n=nn 所以阶乘函数是O(nn)。两边取对数log(n!)nlogn 阶乘函数的对数是O(nlogn)一、大O符号P84 例6二、函数组合的增长许多算法都由两个或更多独立的子过程组成；其所需要的步数是这些子过程使用步数的和；用大O估计时，必须找出对每个子过程的估计，再把它们组合在一起。往往要估计两个函数和与积的增长。二、函数组合的增长假定f1(x)是O(g1(x)，f2(x)是O(g2(x)；从大O符号的定义，有常数C1，C2，k1，k2，使得：当xk1时，|f1(x)|C1|g1(x)|，当xk2时，|f2(x)|C2|g2(x)|，要估计f1(x)和f2(x)的和，

11、注意：|(f1+f2)(x)|=|f1(x)+f2(x)|f1(x)|+|f2(x)|二、函数组合的增长当x大于k1和k2时，有：|f1(x)|+|f2(x)|C1|g1(x)|+C2|g2(x)| (C1+C2)|g(x)|=C|g(x)|其中C=C1+C2，g(x)=max(|g1(x)|,|g2(x)|)。所以，|(f1+f2)(x)|C|g(x)|在xk时成立，其中k=max(k1,k2)。二、函数组合的增长定理：假定f1(x)是O(g1(x)，f2(x)是O(g2(x)，那么(f1+f2)(x)是O(max(g1(x),g2(x)。推论：假定f1(x)和f2(x)都是O(g(x)，那

12、么(f1+f2)(x)也是O(g(x)。类似的方法可以推导出f1和f2的乘积的大O估计。二、函数组合的增长当xmax(k1,k2)时，我们有：|(f1f2)(x)|=|f1(x)|f2(x)|C1|g1(x)|C2|g2(x)|=C1C2|g1(x)g2(x)|=C1C2|(g1g2)(x)|=C|(g1g2)(x)|其中C=C1C2；f1(x)f2(x)是O(g1g2)。二、函数组合的增长定理：假定f1(x)是O(g1(x)，f2(x)是O(g2(x)，那么(f1f2)(x)是O(g1(x)g2(x)。用大O符号来估计函数的目的，是选一个相对增长较慢的函数g(x)，使得f(x)是O(g(x)

13、。例：给出f(n)=3nlog(n!)+(n2+3)logn的大O估计，其中n是一个正整数。二、函数组合的增长f(n)=3nlog(n!)+(n2+3)logn解：首先估计3nlog(n!)。我们知道3n是O(n)以及log(n!)是O(nlogn)，所以3nlog(n!)是O(n2logn)；下一步估计(n2+3)logn。我们知道n2+3是O(n2)，logn是O(n)【见例6】，所以(n2+3)logn是O(n3)。二、函数组合的增长(n2+3)logn2n2lognn3 当n2时。因此(n2+3)logn是O(n2logn)。所以f(n)是O(n2logn)。二、函数组合的增长例：给出

14、f(x)=(x+1)log(x2+1)+3x2的大O估计。解：首先找出(x+1)log(x2+1)的大O估计。 (x+1)是O(x)。 当x1时，x2+1x2+x2=2x2 ； log(x2+1)2时， log2+2logxlogx+2logx=3logx；二、函数组合的增长例：给出f(x)=(x+1)log(x2+1)+3x2的大O估计。解：因此，log(x2+1)是O(logx)； (x+1)log(x2+1)是O(xlogx)；又3x2是O(x2)； 所以，f(x)是O(max(xlogx, x2)，又xlogx1时，于是f(x)是O(x2)。二、函数组合的增长做大O估计时常用的函数有：

15、1, logn, n, nlogn, n2, 2n, n!它们之间的关系是从左到右依次增大，当n无限增长时。P86 图1-21。三、大和大符号大O符号广泛用于描述函数的增长，但它有其局限性；如f(x)是O(g(x)，估计的是f(x)大小的一个上限；要估计f(x)的下限，那么我们使用大符号；要估计f(x)的上、下限时，使用大符号。三、大和大符号定义：令f和g为从整数集合或实数集合到实数集合的函数，我们说f(x)是(g(x)，如果存在正常数C和k，使得xk时，|f(x)|C|g(x)|读作f(x)是大 g(x)。三、大和大符号f(x)是(g(x)当且仅当g(x)是O(f(x)。例：f(x)=8x3

16、+5x2+7是(x3)解：由于f(x)=8x3+5x2+78x3，对于所有正整数都成立，所以f(x)是(x3)。g(x)=x3是O(8x3+5x2+7)？x38x3+5x2+7，成立。三、大和大符号我们希望知道相对于一个简单参照函数而言，某函数增长的阶。要知道函数增长的阶，就需要了解函数大小的上界和下界。给定一个函数f(x)，我们想要一个参照函数g(x)，使得f(x)是O(g(x)和f(x)是(g(x)。三、大和大符号定义：令f和g为从整数集合或实数集合到实数集合的函数。如果f(x)是O(g(x)并且f(x)是(g(x)，就说f(x)是(g(x)。读作f(x)是大 g(x)。也称f(x)是g(

17、x)阶的。若f(x)是(g(x)，g(x)也是(f(x)。g(x)通常是一个相对简单的参考函数。三、大和大符号例：前n个正整数的和是O(n2)，这个和是n2阶的吗？令f(n)=1+2+3+n，只需要找到C使得对足够大的n，f(n)Cn2。1+2+3+nn/2+(n/2+1)+n n/2+n/2+n/2 = (n-n/2+1)n/2(n/2)(n/2)=n2/4所以，f(n)是(n2)；因此，f(n)是n2阶的。记作f(n)是(n2)。三、大和大符号如果能找到正实数C1，C2和k，使得对xk，C1|g(x)|f(x)|C2|g(x)|，则f(x)是(g(x)。例：证明f(x)=3x2+8xlog

18、x是(x2)当x1时，8xlogx8x2， 3x2+8xlogxk时，|f(x)|C|g(x)|。f(x)=O(g(x)。f(x)是O(g(x)，其中g(x)可以用具有更大绝对值的函数替换。小结估计多项式增长f(x)=anxn+an-1xn-1+a1x+a0，其中a0,a1,an-1,an为实数，那么f(x)是O(xn)。常用的函数1, logn, n, nlogn, n2, 2n, n!在使用大O符号时，在f(x)是O(g(x)这一关系中，函数g(x)总是选得尽可能小。小结函数组合的增长假定f1(x)是O(g1(x)，f2(x)是O(g2(x)，那么(f1+f2)(x)是O(max(g1(x