13 可计算函数
13.1 原始递归函数
前面章节的讨论揭示了这样一个事实：一个能够被精确描述的语言不能保证它能够被图林机识别，类似地，一个能够被精确定义的函数不能保证能够被图林机计算。我们已经有了不能计算函数的例子，因为根据定义，非递归语言的特征函数是不能计算的。在本章，我们集中讨论数值函数，有0个或多个非负整数变量，函数值是非负整数，尽力发现一种方法来刻画可计算的函数的特征。将焦点放在数值函数上并不是象听起来那么受局限，因为我们很快就会找到一个方法将字符串映射到字符串的函数的定义域和值域都转换成整数数值。
回忆从N到N的部分函数f是可计算的条件是存在一个图林机T，使得对每个f定义的n，输入字符串1n，T都能够停机，且停机时输出1f(n)，对于没有定义的n，则T不停机。由于一个图林机至多计算一个函数，因此容易应用10.3节的非构造性论据说明存在许多不可计算函数。图林机集合是可数的，而从N到N的部分函数集合是不可数的，因此不可计算函数集合一定是不可数的。（注意，存在两个因素导致部分函数集合是不可数的，一是函数的定义域的可能性很多，二是给定定义域的情况下，对应的值域的可能性很多，其中一个因素就足以导致部分函数集合是不可数的。）
就像我们给出了非递归语言的例子，我们也给出从N到N的不可计算函数的明确的例子。我们的第一个例子，也许你已经想到，与图林机和对角参数法有关。
例子13.1（忙碌海狸函数）让我们定义函数b: N N如下，f(0)=0，对每个n>0，b(n)是定义如下，考虑一个有n个非停机状态，设为Q={q1,...,qn}，的图林机，磁带字母表是{0,1}。因此这样的图林机个数是有限的，现在我们只考虑在输入为1n的情况下停机的图林机。令b(n)是所有这样的图林机在停机时留在磁带上的最大的1的数目。b(n)是衡量这类图林机忙碌程度的一个标准。（某些研究者认为术语“忙碌海狸”来自磁带上的1与海狸布置小树枝类似。）我们利用反证法证明函数b是不可计算的。假设b是可计算的，那么存在一个图林机Tb 计算函数b。令T=T b T1，其中T1是一个图林机，它的磁带字母表也是{0,1}，它在磁带头的初始位置上写上0，然后将磁带头移到右边第一个为0或空符号的格子上，并写上1，将磁带头返回到起始位置，擦掉0，然后停机。令m是T的状态的数目。根据函数b的定义，没有一个状态数为m和磁带字母表为{0,1}的图林机在输入字符串为1m的条件下，停机时磁带上的1的数目大于b(m)。然而前面构造的T，它属于这类图林机，且停机时的输出结果是1b(m)+1，得到矛盾，假设不成立。
一方面，函数b被精确地定义（b(n)是状态数为n，磁带字母表为{0,1}的图林机在输入字符串为1n时，停机后留在磁带上的最大的1的数目），但是它是不可计算的。另一方面，一个公式，比如
f(n)=|2n+5-(3n+1)8|
定义的函数很明显是可计算的。这两种形式的定义的区别是一个是语言描述，另一个是数学公式。考虑函数b2，b2(n)是具有两个状态，磁带字母表是{0,1}的图林机在输入字符串为1n时，停机后输出的最大的1的数目，这也是一个描述性定义，表面上几乎与函数b相同。但是b2是可计算的（？？？）。b2和f的一个共同特点是都存在一个相应的构造性定义，而前面的证明显示了函数b不具备这样的性质。
判定一个描述定义的函数是否存在相应的构造性定义是很困难的或不可能的。在本章，我们形式化定义概念“构造性”，因此在这种方法下能够得到定义的函数就恰好是可计算函数。感觉而言，代数公式定义的函数f是“构造性”的，是因为它是通过在很简单的基本函数（标识函数和常数函数）上施加有限的数学运算得到的。我们采用同样的方法，除了使用的运算比
代数运算，比如加法、乘法等，更通用。我们从基本函数的精确定义开始，注意所有的初始函数都是全域函数。 定义13.1（初始函数）初始函数定义如下：
1. 常量函数：对于每个k>=0和a>=0，常量函数N N C k k a →:定义公式如下
)(X C k
a ＝a, ?X ∈N k
当k=0时，N k
=φ，此时X 不存在，我们指定0a C =a 。
2. 后继函数：s: N →N 定义如下
s(x)=x+1
3. 投射函数：对于每个k>=1且1= ),...,,...,(1k i k i x x x p ＝x i 现在，我们准备考虑组合简单函数得到新函数的方法。我们一开始讨论的两个方法中一个是复合，另一个涉及到一种原始递归。我们将证明，尽管这些运算足以生成大多数我们熟悉的数值函数，但是我们还需要一个运算得到所有的可计算函数。 函数的复合运算定义在第1章，此处我们引入稍有不同的术语和记号。为了方便，小写字母表示整数，大写字母表示向量或m 元组。 定义13.2（复合）假设f 是从N k 到N 的部分函数，且对于每个1= 部分函数，那么从N m 到N 的部分函数h=f(g1,...,gk)定义如下， h(X)=f(g1(X),...gk(X)), X ∈N m h 称为由函数f 和g1,...,gk 复合得到。 函数h 可以写成f ?g ，如果令g(X)=(g1(X),...,gk(X))，这是一个从N m 到N k 的函数，但由于我们只讨论函数值为单个整数的函数，因此避免这种写法。 注意函数的复合运算的次序是重要的，前面定义中是“函数f 和g1,...,gk ”复合。另一个注意的是，为了h(X)（即函数h 在X 上）被定义，每个gi(X)也需要是被定义的，同时f(g1(X),...,gk(X))也是被定义的。如果f, g1,...,gk 都是全域函数，则h 是全域函数。 作为一个熟悉的例子，令Add: N ×N →N 是通常的加法函数（Add(x,y)=x+y ），令f 和g 是从Nk 到N 的部分函数，则函数Add(f,g)是Add, f, g 复合得到的，通常写成f+g 。 定义从N 到N 的函数f 最简单的递归方法是首先定义f(0)，然后任给k>=0，利用f(k)定义f(k+1)，一个标准的例子是阶乘函数： 0!＝1 (k+1)!＝(k+1)*k! 在递归步骤，f(k+1)的表达式包含k 和f(k)。为了得到更通用的方式，我们用h(k,f(k))代替(k+1)*f(k)，其中h 是一个有两个变量的函数。为了将这个方法用于多个变量的函数f ，我们仅仅将递归限制在最后一个变量上。换句话说，我们的递归基础定义的函数是f(x1,...,xn,0)，其中x1,...,xn 可以任意选择。如果n=0，这表示定义了一个常数（不是常数函数，没有变量），在n ≠0的通用形式，则定义了一个有着n 个变量的函数。在递归推导部分，利用f(x1,...,xn,k)定义f(x1,...,xn,k+1)。我们用X 表示n 元组(x1,...,xn)，则更准确地说，f(X,k+1)的定义除了依赖于f(X,k)，还依赖于X 和k 。因此，有了上面的记号，递归推导部分的通用形式是 f(X,k+1)=h(X,k,f(X,k)) 定义13.3（原始递归函数）假设n>=0，且g 和h 分别是n 和n+2个变量的函数。函数f: N n+1→N 定义如下， f(X,0)=g(X) f(X,k+1)=h(X,k,f(X,k)) 任给X ∈N n ，k>=0。我们称f 是函数g 和h 通过原始递归运算得到的。 在阶乘函数例子中，n=0，g 是一个数值（或没有变量的常数函数）01C =1，h(x,y)=(x+1)*y 。显然，如果g 和h 是全域函数，则f 是全域函数，否则如果g 在X ∈N n 上没有定义，则显然f(X,0)没有定义，f(X,1)=h(X,0,f(X,0))也没有定义，更一般地，对于每个k ，f(X,k)都没有定义。类似地，如果f(X,k)对于某个k 没有定义，不妨说k=k0，那么对于每个k>=k0，f(X,k)都没有定义。等价地说，如果f(X,k1)是定义的，则对于每个k<=k1，f(X,k)都是定义的。这些观察为后面证明下面的命题提供了帮助：可计算函数经过原始递归运算生成的新函数仍然是可计算的。 现在，我们有了一些初始函数和两个生成新函数的运算。虽然我们已经指出了还需要其他运算才能生成所有的可计算函数，但是利用现有工具生成的函数集合是值得形式化和讨论的。 定义13.4（原始递归函数）原始递归函数集合PR 定义如下， 1. 所有初始函数是PR 的一个元素； 2. 对于每个k>=0和m>=0，如果f: N k →N 和g1,...,gk: N m →N 是PR 的元素，那么f 和g1,...,gk 的复合函数f(g1,...,gk)也是PR 的一个元素； 3. 对于每个n>=0，函数g: N n →N 和h: N n+2→N 都是PR 的元素，那么g 和h 的原始递归 函数f: N n+1→N 也是PR 的一个元素； 4. PR 中没有其他函数。 在第2章，我们讨论了这类定义（递归定义）的其他相当的形式化方法。PR 可以描述成包含初始函数且在复合和原始递归运算下封闭的最小函数集合。原始递归函数另一个更明显的特征（参见例子2.18后面的讨论）是具有一个原始递归推导。一个函数f 具有原始递归推导的含义是存在一个函数序列f0,...,fj ，fj=f ，且序列中的每个函数fi 要么是初始函数，要么由它前面的函数经过复合运算或原始递归运算得到。 例子13.2 我们展示从N ×N 到N 的函数Add 和Mult ，定义的公式如下， Add(x,y)=x+y Mult(x,y)=x*y 都是原始递归运算的结果。现在我们发现函数Add 的原始递归推导。既然Add 不是初始函数，而且没有一个明显的方法通过复合运算得到Add ，因此我们尝试应用原始递归运算。如果Add 是函数g 和h 原始递归运算的结果，那么g 和h 分别是1个变量和3个变量的函数，满足下面的式子， Add(x,0)=g(x) Add(x,k+1)=h(x,k,Add(x,k)) 容易发现g ，由于Add(x,0)=x ，而x 是初始函数1 1p 。现在我们希望从x, k, x+k 得到Add(x,k+1)，我们不直接需要x 和k ，可以简单地选用x+k 的后继，即h(x,k,Add(x,k))应该是s(Add(x,k))。这 意味着h(x1,x2,x3)应该是s(x3)，或))3,2,1((3 3x x x p s 。因此函数Add 的一个推导序列是 f0＝1 1p // 初始函数 f1＝s // 初始函数 f2＝3 3p // 初始函数 f3＝s(3 3p ) // f1和f2的复合函数 f4＝Add // f0和f3的原始递归函数 推导顺序不是唯一的，比如前面三个函数的顺序是不重要的，只要Add 在序列的最后，s 和3 3p 在s(3 3p )之前就可以了。 类似地，我们应用原始递归运算推导Mult 。 Mult(x,0)＝0 Mult(x,k+1) ＝x*(k+1) ＝Add(x*k,x) ＝Add(x,Mult(x,k)) 注意，我们尝试用形式h(x,k,Mult(x,k))写出Mult 的推导，既然x 和Mult(x,k)是3元组(x,k,Mult(x,k)) 的第一个和第三个元组，我们可以使用函数f=Add(31p ,33p )，它是Add 和31p , 33p 的复合函数。因此函数Mult 由函数0（初始函数10C ）和f 经过原始递归运算得到，它也是原始递归函数。 问题：术语“原始递归函数”的含义有两个1）两个函数的原始递归运算得到的函数2）属于PR 集合的函数。但是术语“原始递归的”一般指第二种情况的函数。 函数Mult 的推导中，许多涉及原始递归函数的论据能够利用下面的通用结果得到简化。 定理13.1 f 是一个有n 个变量的原始递归函数，则 1. 对于每个k>=1，任何有n+k 个变量的函数g ，g 由f 中引入k 个“哑元”变量得到（比 如，n=2, k=1，g(x1,x2,x3)=f(x1,x3)），是原始递归函数。 2. 每个有n 个变量的函数g ，g 由f 改变变量排列顺序得到（比如，n=2, g(x2,x1)=f(x1,x2)）， 是原始递归函数。 3. 对于每个k, 1= 常量得到（比如，n=2, k=1，g(x)=f(5,x)），是原始递归函数。 4. 对于每个k ，1= 得到（比如，n=3, k=1，g(x1,x2)=f(x1,x2,x1)），是原始递归函数。 证明：上面的各种变化都是下面的通用形式的特例。 g(x1,...,xr)=f(z1,...,zn) 其中，每个zi 要么是投射函数，存在某个j ，x j =),..,(1r r j x x p ，要么是常数函数，存在某个a ， a=),...,(1r r a x x C 。比如命题1中的函数g 可以是 g(x1,x2,x3)=f(),,(),,,(3213 332131x x x p x x x p ) 因此，4种情况中的函数g 都是f 和一些初始函数，r j p 和r a C ，复合得到的，它们都是原始递归函数。 例子13.3 令f 是一个有两个变量的函数，定义如下 f(x,y)=y x +x x +x 7 此处，我们定义00=1，使得f 在全域上都有定义。为了显示f 是原始递归函数，我们首先考察 f1，它对应的是f 1(x,y)=x y 。定义如下 f1(x,0)=1 f1(x,k+1) =Mult(x,x k ) =Mult(x,f1(x,k)) 选取h(x,y,z)=Mult(x,z)，利用定理13.1的命题1，知道h 是原始递归函数，则f1是1和h 的原始递归运算的结果函数，因此是原始递归函数。根据命题2知道y x 是原始递归函数，分别根据 命题4和3知道x x 、x 7 是变量为x 的原始递归函数，再根据命题1知道它们也是变量为x,y 的原始递归函数。最后 f(x,y)=Add(Add(y x ,x x ),x 7 ) 它是多个原始递归函数的复合函数，由于复合运算保持原始递归性质，因此f 是原始递归的。 例子13.4（前继函数和适当减法函数）适当减法函数Sub （subtraction 的缩写）是保证函数 值为非负数的减法函数，它是原始递归的。为了证明这一点，我们从前继函数Pred （predecessor 的缩写）开始讨论。 Pred(x)＝? ??≥=-0010 x x x 因此 Pred(0)=0 Pred(k+1)=k 根据定理13.1的命题1，Pred 能够由原始递归函数经过原始递归运算得到。如果我们定义Sub 如下， Sub(x,y)＝?? ?≥-otherwise y x y x 0 则有 Sub(x,0)＝x Sub(x,k+1)＝Pred(Sub(x,k)) 因此Sub 是原始递归的。这个运算常常写作“－”，称为适当减法。 虽然我们还没有完成原始递归函数的举例，本节后面证明两个结果，它们共同证明了原始递归函数集是可计算函数集的真子集。 定理13.2 每个原始递归函数都是一个全域可计算函数。 证明：我们定义原始递归函数的递归方法使得结构归纳法是一个证明它们具备某个性质的合适的方法。我们证明下面三个命题：1）每个初始函数是一个全域可计算函数；2）任何一个由全域可计算函数经过复合运算得到的函数是全域可计算函数；3）任何一个由全域可计算函数经过原始递归运算得到的函数是全域可计算函数。 我们前面观察到，初始函数都是全域函数，并且全域函数经过复合运算和原始递归运算得到的函数仍然是全域函数。现在我们将讨论集中到可计算性的证明上。显然所有的初始函数都是可计算的。为了证明简洁，我们省略一些细节，证明一个简单的情况。h: N m →N 由f: N 2→N 和g1, g2: N m →N 复合而成，如果f, g1, g2是可计算函数，则h 也是可计算函数。这个结论甚至在这些函数是部分函数的条件下也成立。而且这个结论容易推广到f 是k 个变量的函数的情况。 令Tf, T1, T2分别是计算f, g1, g2的图林机，我们将构造一个计算h 的图林机Th 。为了简 化记号，我们用X 表示m 元组(x1,...,xm)，用1X 表示字符串m x x 1 (11) ??。图林机Th 的输入字 符串是?1X ，它使用这个字符串两次，一次用于计算每个gi ，因此复制字符串得到 ?1?1X 执行T1得到 )(111X g X ?? 然后再复制一份1X ，然后执行T2得到 ) () (211 1 1X g X g X ??? 此时删除初始输入字符串，然后在) () (2111X g X g ?上执行Tf ，得到希望的结果。 对于每个可能的X 的值，如果gi(X)是未定义的，或者gi(X)是定义的，但f(g1(X),g2(X))是未定义的，都将导致Th 无法停机。因此Th 计算h 。 作为证明的最后一步，假设g: Nn →N 和h: Nn+2→N 是可计算的，f 由g 和h 经过原始递归运算得到。令Tg 和Th 分别是计算g 和h 的图林机，我们构造计算f 的图林机Tf 。Tf 的磁带初始内容是 1 111...1+???n n x x x 它的缩写形式是 111+??n x X 正如前面说明，X 表示(x1,...,xm)。如果f(X,xn+1)是定义的，Tf 工作步骤如下。首先，决定x n+1是否是0，如果是，Tf 磁带头回到0号格子，执行Tg ，然后停机。如果x n+1不是0，那么存在k>=0，磁带内容是 1 11+??k X 此时，Tf 计算f(X,0)，然后利用这个结果计算f(X,1)，然后f(X,2)，直到利用f(X,k)计算f(X,k+1)。为了完成这系列计算，先准备磁带内容如下 #1X ?1k ?1X ?1k-1?...?11?1X ?10?1X 由于f(X,0)=g(X)，先执行Tg ，然后移动磁带头得到 #1X ?1k ?1X ?1k-1?...?11?1X ?10?1f(X,0) 现在Tf 开始循环处理，每次处理都是执行Th 并且移动磁带头，第一趟处理后，既然f(X,1)=h(X,0,f(X,0))，磁带内容变成 #1X ?1k ?1X ?1k-1?...?1X ?11?1f(X,1) 然后可以计算f(X,2)了。循环处理结束后，得到 #1X ?1k ?1f(X,k) 此时将0号格子的#改成?，再执行一次Th 得到希望的结果。 从定义13.3后面的讨论，我们知道如果f(X,k+1)是定义的，上面计算过程的每一步都能成功进行。如果f(X,k+1)是未定义的，那么或者Tg 在1X 上的处理不能导致停机，或者对于某个i ， 0= 上停机当且仅当f(X,k+1)是定义的。 定理13.3 存在一个从N 到N 的全域可计算函数，它不是原始递归函数。 证明：我们非严格证明上面定理。我们描述一个不是原始递归的函数，并且根据Church-Turing 论题说明它是可计算的。 我们从修改字母表∑开始，它包含我们描述数值函数需要的所有的符号。任何一个原始递归函数都可以用一个原始递归推导来说明，即可以用∑上的一个字符串说明。每个函数可能有多个不同的推导不会影响这个表示（即可能多个字符串表示同一个函数）。余下的证明依赖于下面的命题：给定∑*中的一个字符串，存在一个算法判定这个字符串是否表示了某个单变量函数的原始递归推导。尽管详细描述这个算法很繁琐，但是从直观上容易感觉是存在的。 我们用对角参数法来证明。首先在∑*上定义一个顺序，不妨选规范顺序（先根据长度排序，然后根据字母排序）。现在定义函数f: N →N 如下。对每个i ，按序检查∑*上的每个字符串，抛掉那些不能表示某个从N 到N 的函数的原始递归推导的字符串，直到发现第i 个表示那样的推导的字符串。设被推导的函数是f i ，令 f(i)=f i (i)+1 显然函数f 是全域的。一方面，由于我们描述了一个发现fi 的推导的算法，且这个推导构成了计算f(i)的算法，因此f 是可计算的。另一方面，f 不是原始递归的，因为每个单变量的原始递归函数都是某个fi ，而且无论i 是什么值，都有f(i)≠f i (i)，因此f 不会是fi 。 存在更方便的方法定义全域、可计算的、非原始递归函数。其中最著名的方法是Ackermann 函数，它的定义涉及一种递归，因此它显然是可计算的，但是它的增长速度比任何一个原始递归函数都要快。Hennie 在1977年讨论了这种函数。 （加入张立昂35页Ackermann 函数内容） 13.2 原始递归谓词和一些限制运算 上一节中有几个函数，比如Pred 和Sub ，是分情况定义的。这两个函数比较简单，因此容易发现它们直接的原始递归推导。然而，对于任意一个分情况定义的函数f f(X)＝true x P true x P true x P x f x f x f k k ===??? ?? ??)(...)()()(... )()(2121 我们希望发现通用的原则，使得能够根据函数f i (X)和条件P i (X)的性质得到f 的一些结论。 条件P 的值依赖于变量X ∈N n ，要么是true ，要么是false ，称为谓词，更精确的说，条件P 是n 位谓词，是从N n 到{true,false}的部分函数。显然P 也表示了一个集合，与谓词P 紧密相关的是它的特征函数x p : Nn →{0,1}，定义如下 x p (X)＝?? ?=otherwise true X P )(0 1 既然xp 是一个数值函数，那么我们在13.1节讨论的函数的性质都适合于x p ，同样也适合于P 。特别地，如果xp 是可计算的，则P 也是可计算的，如果x p 是原始递归的，P 也是原始递归的，称为原始递归谓词。当我们说语言L 的特征函数xL 是可计算的，意味着我们能够判定给定的字符串是否属于L 。当我们说xp 是可计算的，含义相似于前面，即存在一个算法判定给定X 是否满足P ，或P(X)是否为真。 谓词取真或假，因此可以对谓词施加逻辑运算∧（与）∨（或）?（非）。比如(P1∧P2)(X)为真当且仅当P1(X)和P2(X)都为真。显然这些逻辑运算保持了谓词的原始递归性。 定理13.4 如果P1和P2是n 位原始递归谓词，那么谓词P1∧P2，P1∨P2，?P1也是原始递归谓词。 证明：上面的结论来自下面三个等式，而这三个等式是显然成立的。 2 1 P P x ∧＝1 P x *2 P x 21P P x ∨＝1P x +2P x -21P P x ∧ )(1P x ?＝1-1P x 注意此处的减法是例子13.4引入的适当减法。 例子13.5（关系谓词）关系谓词属于最简单的谓词，关系谓词有L T, EQ, GT, LE, GE, NE 。LT(x,y)为真当且仅当x 函数Sg 的含义是如果变量值为0，则函数值为0，否则为1。显然Sg 是一个原始递归函数。现在我们有 x LT (x,y)＝Sg(y-x) 既然x 注意如果x LE=LT ∨EQ GT=?LE GE=?LT NE=?EQ 根据定理13.4，逻辑运算保持原始递归性，因此上面的4个谓词都是原始递归的。 如果P 是一个n 位谓词并且有函数f1,...,fn: N k →N ，我们可以得到一个k 位谓词Q=P(f1,...,fn)，显然Q 的特征函数x Q 是x P 和f1,...,fn 的复合函数，因此，如果P 是原始递归谓词，所有的fi 是原始递归函数，则Q 是原始递归的。将这个通用事实与定理13.4组合考虑，我们发现只要基本组件是原始递归的，任意一个通过关系运算和逻辑运算构造的复杂谓词都是原始递归的，比如 (f 1=(3f 2)2 ∧(f 3 对于每个X ∈N n ，有且只有一个P i (X), 1= x P true x P x f x f x f k k ===?? ? ?? ??)(...)()()(...)()(2121 证明：条件“在任何情况下，只有一个谓词为真”是为了保证函数f 无歧义。它隐含了对于每个X ，只有一个)(X P i x 为1，其他都是0。因此有 f ＝f 1*1 P x +...+f k *k P x 即f 是等式右面所有函数的复合函数，因此如果右面的函数都是原始递归函数，则f 是原始递归函数。 例子13.6（模和商函数）对于自然数x 和y （y>0），记号Div(x,y)和Mod(x,y)分别表示x 除以y 的整数商和余数。比如，Div(8,5)=1，Mod(8,5)=3，Mod(12,4)=0。由于除数不能为0，因此它们不是全域函数，为了讨论方便，我们扩展上面的定义，令Div(x,0)=0，Mod(x,0)=0。下面我们说明它们是原始递归的。因为 x=y*Div(x,y)+Mod(x,y) 且当y>0，有 0= 根据定理13.1的命题2，如果能够说明R 是原始递归的，则Mod 也是原始递归的。下面的公式容易验证 R(x,0)=Mod(0,x)=0 R(x,k+1)=Mod(k+1,x)=01),(01),(0101),(==+∧≠<+∧≠?? ? ? ?++x x k x R x x k x R x k k x R 比如由于5≠0并且Mod(6,5)+1=1+1<5， R(5,6+1)=Mod(7,5)=Mod(6,5)+1 由于5≠0并且Mod(9,5)+1=4+1=5， R(5,9+1)=Mod(10,5)=0 函数h 定义如下 h(x 1,x 2,x 3)=0101010 111311312 3==+∧≠<+∧≠??? ??++x x x x x x x x x 由于在x 1≠0且x 3+1>x 1情况下（对于本例，这类情况实际上不会出现），h 没有定义，因此h 不是全域函数。我们稍作修改如下， h(x 1,x 2,x 3)=0101010 111311312 3=≥+∧≠<+∧≠??? ??++x x x x x x x x x 使用效果与前者相同。因此R 由初始函数1 0C 和修改后的h 经过原始递归运算得到，根据定理 13.5知道h 是原始递归的，因此R 和Mod 都是原始递归函数。 函数Div 能够以相似的方式处理。如果我们定义 Q(x,y)＝Div(y,x) 那么经过原始递归运算得到Q 的两个函数分别是1 0C 和h1 h 1(x 1,x 2,x 3)=01),(01),(00111121112133 ==+∧≠<+∧≠?? ? ??+x x x x Mod x x x x Mod x x x 显然它们都是全域原始递归函数。 我们知道，能够施加到谓词的运算除了“与或非”这样的逻辑运算，还可以是全称量词和存在量词。比如，Sq 是一个2位谓词，定义如下 Sq(x,y)=(y 2=x) 可以对第二个变量y 施加存在量词，从而得到一个1位谓词PerfectSquare ， PerfectSquare(x)=(存在y ，使得y 2=x) 显然谓词Sq 是一个原始递归谓词，那么是否可以依此导出PerfectSquare 也是原始递归谓词？答案是“否”，即我们不能直接依据Sq 推导得到。答案是“是”，因为PerfectSquare 确实是原始递归的。结论是对一个原始递归谓词施加存在量词不能保证得到新的原始递归谓词，并且对一个可计算谓词施加存在量词不能保证得到新的可计算谓词。 容易给第二个命题发现一个例子，考虑第12章的一个熟悉的情况。给定字母表∑，我们可以规定它的一个顺序，从而确定∑*上的规范顺序。对于一个自然数x ，s x 表示这个顺序中的第x 个字符串。令Tu 是9.7节讨论的通用图林机，H 是一个2位谓词，定义如下， H(x,y)＝(Tu 在输入字符串为s x 时，经过y 步移动停机) 显然H 是可计算的，实际上我们后面将看到它是一个原始递归谓词。然后由它定义的1位谓词 Halts(x)＝(Tu 在输入字符串位s x 时，存在一个y ，Tu 经过y 步移动停机) 是不可计算的，因为这是我们前面讨论过的停机问题，它是无解问题。 为什么同样是施加存在量词，PerfectSquare 保持了可计算性，而Halts 却无法保持？两个例子中一个明显的区别是当给定x 值，是否存在y 的一个明确的限制，使得对“存在一个y ”这样的条件进行有效的检验。比如，对于例子PerfectSquare ，任何一个满足y 2=x 的y 都满足y<=x ， 因此存在一个算法在给定x 的情况下，按照升序逐个检验y ，知道发现一个y 满足y 2 =x ，或y>x 。而言对于Halts 谓词，不存在y 的限制，因此逐个检验的算法也不存在，而且往往任何算法都不存在。 这个讨论预示了如果我们从任意一个n+1位谓词P 开始，对P 的最后一个变量施加存在量词，得到一个新的谓词Ep ，如果存在量词是有界的，那么Ep 可能具备一些好的性质。同样的 讨论可以施加到全称量词上，后面我们将发现，这两种有界量词，都能保持谓词的原始递归性。 定义13.5（有界量词）令P 是一个n+1位谓词，P 的有界存在谓词（bounded existential quantification ）是n+1位谓词Ep ，定义如下， Ep(X,k)＝(存在y ，0≤y ≤k ，使得P(X,y)为真) P 的有界全称谓词是n+1位谓词Ap ，定义如下， Ap(X,k)＝(对于每个y ，0≤y ≤k ，使得P(X,y)为真) 注意有界量词与普通量词的区别，有界量词没有减少谓词的位数。 定理13.6 如果P 是一个n+1位原始递归谓词，那么它的有界存在谓词Ep 和有界全称谓词Ap 都是原始递归的。 分析：为了简化13.6的证明，我们引入另外两个“限制运算”。我们先考虑一个简单的特例，它的结果函数是我们熟悉的函数。 在第2章我们给出了阶乘函数的递归定义，现在我们给出另一种形式， x!＝∏=x i i 1 记号∏表示连乘，比如 ∏ =k j i i p ＝? ? ?<≥+j k j k p p p k j j 1*...**1 k 这个规定也使得x=0时前面的阶乘式子也成立。我们可以进一步抽象这个定义式，给出更通用的形式，可以有更多的变量和运算符，比如加法。 引理13.1 令n>=0，并且假设g: N n+1→N 是原始递归的，则如下定义的函数f1, f2: N n+1→N 也是原始递归的。 f 1(X,k)=∑=k i i X g 0),( f 2(X,k)=∏=k i i X g 0 ),( 其中，X ∈N n ，k>=0。（f1和f2分别称为函数g 的“有界和”和“有界积”函数。） 证明：我们给出f1的证明，f2可以完全类似证明。显然有 f1(X,0)=g(X,0) f1(X,k+1)=f1(X,k)+g(X,k+1) 令 g1(X)=g(X,0) h(X,y,z)=z+g(X,y+1) 因此f1是两个原始递归函数g1和h 经过原始递归运算得到的，f1也是原始递归的。 注意一个小的区别，此处定义的有界积从i=0开始，而前面定义的阶乘x!从1开始。因此我们给出引理13.1更通用的形式，它使得“有界和”和“有界积”可以从任何一个固定的值i 0开始。 定理13.6的证明：有界全称谓词A P (X,k)为真当且仅当对于每个0= x =1当且仅当每个x P (X,i)都为1，即下面等式成立 ),(k X A P x ＝∏=k i P i X x 0 ),( 根据引理13.1立即得到谓词A P 是原始递归的。 说存在一个i ，0= 因此E P (X,k)也是原始递归的。 至此，我们说明了存在量词和全称量词的有界形式保持了谓词的原始递归性，尽管无界的情况甚至不能保持可计算性。为了把可计算函数刻画成由一组简单的初始函数和有限的运算得到，我们至少需要一个运算，它保持可计算性，但是不保持原始递归性。这是因为初始函数都是原始递归的，而我们知道存在非原始递归的可计算函数。运算minimalization （最小化）显示出这个性质，我们在下一节讨论它的通用形式，此处引入它的有界形式。 对于一个n+1位的谓词P 和给定的X ∈N n ，我们可以考虑使得P(X,y)为真的y 的最小值。考虑它的有界情况。我们指定一个值k ，在不大于k 的范围里寻找满足P(X,y)的最小的y 。也许不存在这样的y （无论我们是否用k 约束可能的选择），而我们希望函数的有界形式是全域函数，因此我们给这种情况引入一个合适的缺省值。 定义13.6（有界最小函数）对于一个n+1位谓词P ，P 的有界最小函数m P : Nn+1→N 定义如下 m P (X,k)＝? ? ?+∧≤≤otherwise empty not is set the if k y X P k y y _____1 ),(0|min( 符号μ常常用于上面的最小化运算，有时写成 m P (X,k)＝)],([y X P y k μ 一个重要的特例是，如果P(X,y)是(f(X,y)=0)，其中f: N n+1→N ，则m P 写成m f ，表示对函数f 施加有界最小化运算。 定理13.7 如果P 是一个n+1位原始递归谓词，那么它的有界最小函数m P 是一个原始递归函数。 证明：我们显示m P 能够通过在原始递归函数上施加原始递归运算得到。对于X ∈N n ，如果P(X,0)为真，则m P (X,0)为0，否则m P (X,0)为1。为了估计m P (X,k+1)的值，我们分三种情况考虑。第一，如果存在y<=k ，使得P(X,y)为真，则m P (X,k+1)=m P (X,k)；第二，如果没有那样的y ，但是P(X,k+1)为真，则m P (X,k+1)=k+1；第三，如果前两种情况都不成立，则m P (X,k+1)=k+2。因此函数m P 能够对函数g 和h 施加原始递归运算得到，其中 g(X)=?? ?=otherwise true X P )0,(1 h(X,y,z)=?? ? ??=+?∧?=+∧?=++true y X P y X E true y X P y X E true y X E y y z P P P )1,(),()1,(),(),(21 既然P 和E P 都是原始递归谓词，因此g 和h 都是原始递归函数。 例子13.7 对于n>=0，令PrNo(n)等于第n 个素数，比如 PrNo(0)=2 PrNo(1)=3 PrNo(2)=5 ... 说明PrNo(n)是原始递归函数。 分析：首先我们考察1位谓词Prime ，定义如下 Prime(n)=(n>=2)∧?(?y(y>=2∧y<=n-1∧Mod(n,y)=0)) 显然Prime 是原始递归的，且Primt(n)为真当且仅当n 为素数。 对于任意的k ，PrNo(k+1)是比PrNo(k)大的最小的素数，因此，如果我们能够给大于PrNo(k)的整数域添加一个限制，使得检测空间就是有界的，那么我们就能够利用有界最小化运算和原始递归运算得到PrNo 。例子2.5证明了数论的一个结论，对于任意的正整数m ，存在一个大于m 和不大于m!+1的素数。我们可以利用这个结论施加限制。令 P(x,y)=(y>x ∧Prime(y)) 则 PrNo(0)=2 PrNo(k+1)=m P (PrNo(k),PrNo(k)!+1) 因此函数PrNo 可以由下面两个函数的原始递归运算得到，02C 和h h(x,y)=m P (y,y!+1) 因此PrNo 是一个原始递归函数。 13.3 无界的最小化运算和μ递归函数 对于一个谓词P ，我们已经定义了m P (X,k)或)],([y X P y k μ是在区间[0,k]上使得P(X,y)为真的最小的y 值，如果存在这样的y ，则函数值为k ，否则为k+1。指定缺省值的目的是使得m P 是一个全域函数。现在我们要去掉定义中施加在y 上的区间限制。如果至少存在一个y 使得P(X,y)成立，那么我们只要按照升序检验每个y 值就能确保找到这个最小值，如果不存在这样的y ，那么可能永远检验下去，永远不知道不存在这样的y 。由于我们希望无界的最小化运算能够保持可计算性，那么我们不应该给函数指定缺省值，因为在函数值应该是这个值（缺省值）的情况下，我们也许不能确定这种情况（？？？）。因此无界最小化运算不再保证得到一个全域函数，甚至施加在原始递归谓词上。因此我们不再期望无界最小化运算保持原始递归性质。 定义13.7（无界最小化）如果P 是一个n+1位谓词，P 的无界最小化函数是部分函数M P : Nn →N ，定义如下 M P (X)=min{y|P(X,y)=true} 如果对于某个X ∈N n ，不存在满足P(X,y)的y ，则称M P (X)未定义。 M P (X)有时也记为μyP[(X,y)]。在特别情况下，P(X,y)=(f(X,y)=0)，我们将M P 记为M f ，表示f 的无界最小化函数。 我们希望对于每个可计算谓词P ，M P 都是一个可计算的部分函数，这带来另一个结果。假设计算M P (X)的简单算法是按照y 的升序逐个检验谓词P(X,y)。也假设对于某个y0，P(X,y0)是未定义的，但可能存在y1>y0，P(X,y1)为真。但前面的简单算法将陷入检验P(X,y0)的无限循环中，从而无法检验P(X,y1)。我们可以通过只在全域谓词或全域函数上施加无界最小化运算来避免这个问题。 无界最小化运算是我们引入的最后一个用来刻画可计算函数的运算。注意下面的定义中，这个运算只是施加在由某些函数值为0的数值函数定义的谓词上。 定义13.8（μ递归函数）μ递归（或简称递归）部分函数组成的集合M 定义如下 1. 所有的初始函数属于M 。 2. M 中的函数经过复合或原始递归运算后得到的新函数属于M 。 3. 对于任意n>=0和M 中任意的全域函数f: N n+1→N ，函数M f : N n →N 定义如下 M f (X)=μy[f(X,y)=0] M f 属于M 。 4. M 中没有其他元素。 正如原始递归函数的性质，函数属于M 当且仅当它存在一个有限的、一步接一步的推导，在每一步，要么引入了一个新的初始函数，要么三种运算（复合、原始递归、无界最小化）中的一种施加到前面推导出的函数或初始函数上得到的新函数。只要没有使用无界最小化运算，那么推导序列中每步得到的函数都是原始递归的。一旦无界最小化运算出现在序列中，函数可能失去原始递归性，甚至全域性。注意如果f 由复合和原始递归运算得到，即使参与运算的函数不都是全域函数，f 仍可能是全域函数。可以想象在一个μ递归函数的推导中，即使无界最小化运算的第一次使用就导致了非全域函数，但它仍然可以多次使用。但是后面定理13.10的证明显示了对于每个μ递归函数，存在一个无界最小化运算只出现一次的推导序列。 定理13.8 所有的μ递归部分函数都是可计算的。 证明：我们用构造性证明。在定理13.2的证明中，我们已经观察到初始函数是可计算的，同样可计算函数经过复合和原始递归运算后得到的部分函数仍然是可计算的。因此，此处只需要证明如果f:N n+1→N 是可计算的全域函数，那么它的无界最小化函数M f 是可计算的部分函数。 如果Tf 是计算f 的图林机，我们已经提到构造计算M f 的图林机T 的直观思路。T 简单地计算f(X,0), f(X,1), ...，直到发现一个i 满足f(X,i)=0，则停机并输出i 。如果没有那样的i ，这个计算过程永远进行下去，由于此时M f (X)是没有定义的，这个无限处理过程是合理的。显然T 是计算M f 的图林机，构造细节省略。 13.4 Godel 编码 使用英语阐明有关英语本身的命题不仅是可能的，而且在实际中是常见的。在9.7节，我们已经在形式语言中做过类似的事情：我们构造0和1组成的字符串来描述包含0和1组成的字符串的语言，并在这个意义上，它们说明了接受语言的图林机。正是这种看似无害的技术导致了对角线参数法的应用，对角线参数法的自相关性质（图林机能够或者不能接受它自身编码）导致了有关计算局限性的深远的结果。 逻辑学家Kurt Godel 在1930年代（与Turing, Church, Post et al.最初发表论文同时代）使用相似的思想，发展了一个编码体系，能够对一个公理系统中的命题和公式进行编码。结果，Godel 能够用表示编码关系的编码公式描述公理系统中对象间的逻辑关系。他的独创性在于使用这个技术得出了有关逻辑系统中存在无法证明的命题的革命性和影响深远的结果。 尽管我们不直接讨论Godel 的结果，但Godel 编码的思想对我们是有用的。第一步是简单地将几个数字组成的序列编码成单个数字。这个编码思想的一个应用展示了一个比我们前面考虑过的更通用的递归定义的类型能够带来原始递归函数。稍后，我们将这种“算术”扩展到比如图林机这样的对象。这将使得我们可以用一个数字序列表示表示一个涉及数字的计算序列，并且它称为证明所有的可计算函数都是μ递归的主要成分。 存在多种Godel 编码体系，但是大多数基于有关数字的一个熟悉的事实：每个正整数能够被分解成多个素数因子，并且如果不考虑因子的顺序，这个因子分解的结果是唯一的。 定义13.9（自然数序列的Godel 数）对于任意一个自然数组成的有限序列x0,...,xn ，这个序列的Godel 数是 gn(x 0,...,x n )=n x x x x n No )) (...(Pr 5322 1 其中PrNo(n)表示第n 个素数（参见例子13.7）。 每个序列的Godel 数都大于或等于1，并且每个大于或等于1的整数都是某个序列的Godel 数。函数gn 不是一一映射的，比如 gn(0,1,2)=gn(0,1,2,0,0)=203152 但是，如果 gn(x 0,...,x m )=gn(y 0,...y m ,y m+1,...,y m+k ) 则 ∏ =m i x i i No 0 ) (Pr ＝∏=m i y i i No 0 ) (Pr ∏ ++=k m m i y i i No 1 ) (Pr 并且由于一个数字只有一个素数因子分解结果，则一定满足 x i =y i , 0= 因此，如果忽略序列后部的0，具有相同Godel 数的序列是相同的。特别地，对于一个特定的n>=1，任何一个正整数都是至多对应一个长度为n 的序列的Godel 数。 对于任意的n>=1，定义在长度为n 的序列上的Godel 编码确定了一个从N n 到N 的函数。此处我们非严格地使用记号gn 表示所有这类函数，它们都是原始递归的。 如果我们从正整数g 开始，希望对g 解码，得到一个自然数序列x0,...xn ，它的Godel 数是g ，那么处理的方式可以是将g 分解成素数的乘积。对于每个i ，xi 是素数PrNo(i)在g 的因子分解中出现的次数。比如数字59895的因子分解结果是 59895=3251113=20325170113 因此，它对应的序列是0,2,1,0,3（或者在这个序列后面添加0得到的任何序列）。素数31的Godel 数对应的序列是0,0,0,0,0,0,0,0,0,0,1（因为31=PrNo(10)）。这类计算将会常常用到，我们引入一个专门的函数处理它。 例子13.8 指数函数Exponent: N 2→N 定义如下，当x>0时，Exponent(i,x)表示x 的素数因子分解结果中第i 个素数PrNo(i)的指数；当x=0时，Exponent(i,x)等于0。比如 Exponent(4,59895)=3 注意2时第0个素数，因此59895的因子分解结果中，第4个素数是11，共出现了3次。 函数Exponent 是原始递归的，对于x>0，i>=0，只要y<=Exponent(i,x)，PrNo(i)y 就能整除x 。换句话说，Exponent(i,x)+1是最小的y ，使得PrNo(i)y 不能整除x 。这个说法隐含了最小化运算，又由于针对给定的x ，我们能够容易地找到一个k ，使得PrNo(i)k 不能整除x （比如k=x ），因此我们可以构造一个有界最小化运算。对于x>0 Exponent(i,x)=1]0))(Pr ,([->y k i No x Mod y μ Exponent 的原始递归性由此得到。 许多常见的递归定义不是明显地符合原始递归运算要求的模式，比如Fibonacci 函数的标准定义如下 f(n+1)=f(n)+f(n-1) 等式的右边不是h(n,f(n))的形式，它还依赖f(n-1)。在更通用的形式中，f(n+1)可以依赖更多的，甚至全部前面的项f(0),...,f(n)。这种类型的递归称为course-of-values 递归，它与普通原始递归的关系，相似于我们在2.3节讨论的数学归纳法的强原则与普通原则的关系。 简单地应用Godel 数可以将course-of-values 递归转换成不同递归形式。假设函数f 是递归定义的，f(n+1)依赖前面多个（或全部）函数值f(0),...,f(n)（当然也可能依赖n ）。直观地，为了用原始递归的形式描述f ，我们需要满足下面条件的另一个函数f1， 1. 知道了f1(n)，就能够计算f(n) 2. f1(n+1)只依赖n 和f1(n) 如果我们放松函数f1(n)的限制，它的函数值可以不是一个数值，可以是一个n 元组，那么构造f1(n)如下 f1(n)=(f(0),...,f(n)) 显然，f1(n)满足条件1，因为f(n)是f1(n)表示的n 元组的最后一项，因此很容易根据f1(n)得到f(n)。另外，f1(n+1)={f(0),...,f(n),f(n+1)}，而f(n+1)依赖n 和{f(0),...,f(n)}=f1(n)，因此f1(n+1)只依赖n 和f1(n)，满足条件2。为了使得f1符合我们对函数的要求，函数值是一个数值，又要保持上面的性质，只需求这个序列的Godel 数。因此我们不说f(n+1)依赖序列f(0),...,f(n)，而说f(n+1)依赖Godel 数gn(f(0),...,f(n))。由于从单个数值gn(f(0),...,f(n))能够推导出每个f(i)，因此这种方法与前面方法等价。 定理13.9 假设g: N n →N 和h: N n+2→N 是原始递归函数，函数f: N n+1 →N 是g 和h 通过course-of-values 递归运算得到，即 f(X,0)=g(X) f(X,k+1)=h(X,k,gn(f(X,0),...,f(X,k))) 那么f 是原始递归的。 证明：首先我们定义f1: N n+1→N 如下 f1(X,k)=gn(f(X,0),...,f(X,k)) 则f 能够从f1直接得到 f(X,k)=Exponent(k,f1(X,k)) 因此，我们只需要证明f1是原始递归的。因为 f1(X,0)=gn(f(X,0))=2f(X,0)=2g(X) f1(X,k+1)＝∏+=1 0),()(Pr k i i X f i No ＝∏=++*k i k X f i X f k No i No 0 )1,(),()1(Pr )(Pr ＝f1(X,k)*))) ,(),...,0,((,,()1(Pr k X f X f gn k X h k No + ＝f1(X,k)*)) ,(,,(1) 1(Pr k X f k X h k No + ＝h1(X,k,f1(X,k)) 其中 h1(X,y,z)=z*PrNo(y+1)h(X,y,z) 由于2g 和h1都是原始递归函数，f1由它们经过原始递归运算得到，因此f1也是原始递归函数。 现在我们准备将Godel 编码技术用到图林机中。图林机计算函数f 可以表示成一个计算步骤序列。如果我们能够将这些步骤表示成数字的运算，那么我们就有了一个从更基本的函数构造函数f 的方法。因为图林机的移动被看成是图林机的一个格局转换到另一个格局，因此为了对移动进行数字化，我们只需要将格局编码成一个数字。 首先我们给每个状态指定一个数字，停机状态赋予数字0。设Q 是图林机的状态集，令Q 的元素为q1,...,qs ，其中总是假设q1是初始状态。 描述磁带头位置的明显的方法是磁带头当前的磁带格子号码。最后，我们赋予空符号?为数字0（以后，我们有时写成0，而不写成?），假设非空磁带符号是1,2,..,t 。因此我们可以将图林机在任何时候的磁带内容（每个格子对应序列的一个数值，得到一个数字序列，是0和1组成的序列）定义成当前符号序列对应的Godel 数，称为磁带数字，记为tn 。注意由于我们将?指定为0，因此无论我们把多少磁带后面空符号包含进符号序列，它们对应的磁带数字是相同的。空磁带的磁带数字为1。 既然图林机的格局由三部分决定，状态、磁带头位置、当前磁带内容，那么我们可以用下面的Godel 数表示一个格局，称为格局数字， gn(q, P, tn) 其中q 是当前状态的数字，P 是当前磁带头位置的数字，tn 是当前磁带数字。格局数字的一个重要性质是，根据它，我们能够完全重构格局的所有细节，在下一节，我们将看到图林机的这 种编码方法的意义。 问题：补充Gopel 不完全定理 13.5 所有的可计算函数都是μ递归函数 定理13.10 每个可计算函数f: Nn →N 都是μ递归函数。 分析：我们将定理13.10的证明分成多个部分。证明的提纲来自上节讨论的Godel 编码方法和图林机的“算术化”。如果函数f 被图林机T 计算，那么下面的公式成立 f=Result T f T InitConfig (n) 如果我们能够证明等式右边的三个函数都是μ递归的，那么就证明了f 是μ递归的。 对于任意的n 元组X ，InitConfig (n) (X)是图林机T 当输入字符串为X 时的初始格局对应的格局数字。由于我们已经规定每个图林机的初始状态都是q1，应此这个初始格局数字与图林机无关，只与输入字符串X 相关。数值函数f T 对应图林机T 的处理过程，f T 的变量值为初始格局数字，计算结果是T 最终到达的停机格局对应的格局数字。函数Result T 取值停机格局数字，这个数字包含了图林机T 处理结束时的输出结果f(X)，Result T 返回数值f(X)。 类似前面讨论过的其他一些函数，Result T 首先要判断输入数值m 是否是T 的一个格局数字，因此第一步检验工作可以用下面定义的1位谓词IsConfig T 来完成， IsConfig T (n)=(n 是T 的一个格局数字） 引理13.2 IsConfig T 是原始递归谓词。 证明：令s T 和ts T 分别表示非停机状态的数字和图林机T 的非空白磁带符号的数字。数值m 是T 的一个格局数字当且仅当 m=2q 3p 5tn 其中q ≤s T ，p 是任意的数值，tn 是一组自然数序列对应的Godel 数，序列中每个数值都介于0到ts T 之间。 命题“m 的因子分解结果的形如2a 3b 5c ”等价于命题“m>=1，对于每个i>2，Exponent(i,m)=0。”表示成下面的公式 (m>=0)∧(?i(i<=2∨Exponent(i,m)=0)) 除此以外，m 在q 和tn 上需要满足的条件表示如下 (Exponent(0,m)<=s T )∧(Exponent(2,m)>=1)∧(?i(Exponent(i,tn)<=ts T )) 为了说明两个谓词的联合形式是一个原始递归谓词，只要分别说明两个谓词都是原始递归谓词，其中关键是说明说明其中的全称量词可以是有界全称量词，第一个谓词和第二个谓词分别做如下的修改，不会影响谓词结果。 ?i<=m(i<=2∨Exponent(i,m)=0) ?i<=tn(Exponent(i,tn)<=ts T ) 因此IsConfig T 是原始递归的。 引理13.3 函数InitConfig (n): N n →N 是原始递归的。 证明：因为每个图林机T 的初始状态被指定为q1，并且磁带头的初始位置是0号格子，因此可以写成 InitConfig (n)(x1,...,xn)=gn(1,0,t (n)(x1,...,xn)) 其中，t (n)(x1,...,xn)是磁带内容为 n x x 1 (11) ??? 的磁带数字，它来自Godel 编码。因此我们只需证明t (n)是原始递归函数。对n 使用数学归纳法。 1. 归纳基础，n=0，此时t (n)是一个常数，即一个初始函数，显然是一个原始递归函数； 2. 归纳推理，设k>=0，t (k+1)是原始递归函数，数字 t (k+1)(x 1,...,x k ,x k+1)=t (k+1)(X,x k+1) 是下面磁带内容的磁带数字 1 11 1...1+????k k x x x 统计n x x 1 ...11???的长度为∑=+ k i i x k 1 ，我们发现字符串11+k x 在磁带上的位置是从 ∑=+ k i i x k 1 +1到∑=+ k i i x k 1 +x k+1，这意味着磁带上最后一块1组成的字符串11+k x 给磁带数字添加 了下面的因子 PrNo(∑=+ k i i x k 1 +j), 1= 即磁带数字可以写成 t (k+1) (X,x k+1)=t (k) (X)*∏∑+==++ 1 1 1 )(Pr k x j k i i j x k No 等式右边的第一项是变量为X 的函数，根据归纳假设，它是原始递归函数，根据定理13.1，如果把它看成k+1个变量，即(X,x k+1)，的函数，它仍然是原始递归函数。第二项的形式是 ∏ +=1 1 ),(k x j j X g 其中g 是原始递归函数，根据引理13.1，它也是原始递归函数。因为乘法运算保持原始递归性， 因此t (k+1) (X,x k+1)是原始递归函数。 引理13.4 函数Result T : N →N 是原始递归的。 证明：对于每个格局数字n ，ResultT(n)等于n 表示的格局中磁带上最后（或最右）一个非空符号的位置（或格子号码）。因为对于格局数字n ，磁带数字是Exponent(2,n)，而且磁带数字的素数因子对应非空符号的格子号，因此有 Result T (n)=otherwise true n IsConfig n Exponent ime Highest T =? ? ?)(0 )),2((Pr 其中对于任意的正数k ，HighestPrime(k)表示k 的最大的素数因子的号码，如果k=0，则HighestPrime(k)=0。比如HighestPrime(2355192)=7，因为19=PrNo(7)。容易证明HighestPrime 是原始递归函数，因此得证Result T 是原始递归的。 现在唯一还没有证明的是函数f T ，它是对应于图林机T 处理过程的数值函数。在这里，我们引入一个简化假设，T 永远不会出现因为磁道头移到0号格子之左而导致的崩溃，这个假设不失一般性，因为对于任何一个图林机T ，我们都能构造出满足上面假设的对等的图林机。我们再引入一组函数，分别从格局数字计算得到当前状态、磁带头位置、磁带数字和当前磁带符号。 State(m)=Exponent(0,m) Posn(m)=Exponent(1,m) TapeNum(m)=Exponent(2,m) Symbol(m)=Exponent(PrNo(Posn(m)), TapeNum(m)) ??? 直接用Posn(m) 4个式子都适用于m 是一个T 的格局数字，否则，4个函数的函数值都定义为0。由于IsConfig T 是原始递归谓词，因此4个函数都是原始递归函数。 复合函数f T 的一个主要成分是Move T : N →N ，简单地说，它反映了T 的一步移动的结果。精确地说，如果m 是T 的一个格局数字，且在这个格局下，T 能移动，那么Move T (m)是这步移动后的格局数字，如果m 是一个停机格局数字，或任何其他不能移动的格局数字，那么Move T (m)=0。 引理13.5 函数Move T : N →N 是原始递归的。 证明：根据Move T 的定义，有 Move T (m)=? ? ?=otherwise true m IsConfig m NewTapeNum m NewPosn m NewState gn T )(0 ))(),(),(( 当m 不是一个格局数字时，三个函数，NewState, NewPosn, NewTapeNum ，的函数值都是0。如果m 是一个格局数字，NewState(m)表示T 从m 表示的格局移动后的新状态的号码，否则等于State(m)。其他两个函数可作类似定义。因此为了证明Move T 是原始递归的，只要证明上面三个函数是原始递归的。为了证明方便，我们引入一个类似的函数NewSymbol 。 至此，我们分三种情况说明了函数NewState(m)，一种情况对应原始递归谓词?IsConfig T (m)，其他两种情况可以分成很多子情况，分别对应State(m)和Symbol(m)的各种可能的组合情况。因为这两个函数是原始递归的，因此定义这些子情况的谓词也是原始递归的。在每个子情况，NewState(m)的值或者是State(m)，或者是T 的转移表规定的值。因此分情况定义NewState 所涉及的所有函数和谓词都是原始递归的，则NewSate 也是原始递归的。同理可以证明NewSymbol 也是原始递归的。 NewPosn 的证明方法几乎与上面相同，它也是分情况定义。各个情况的定义相同于NewState 的证明。如果m 不是一个格局数字，那么NewPosn(m)=0；如果m 不能从格局m 移动或者移动方向是静止（即S ），则NewPosn(m)=Posn(m)；如果是右移（即R ），则NewPosn(m)=Posn(m)+1；如果是左移（即L ），则NewPosn(m)=Posn(m)-1。显然NewPosn 是原始递归函数。 使用同样的分情况方法定义NewTapeNum ，只是公式更复杂一些。假设Posn(m)=i ，Symbol(m)=j ，NewSymbol(m)=j ’，那么TapeNum(m)和NewTapeNum(m)的区别是前者涉及的因 子是PrNo(i)j ，后者是PrNo(i)j ’ 。指数差 j ’-j=NewSymbol(m)-Symbol(m) 如果NewSymbol(m)>=Symbol(m)，则 NewTapeNum(m)=TapeNum(m)*PrNo(Posn(m))NewSymbol(m)-Sy mbol(m) 否则 NewTapeNum(m)=Div(TapeNum(m), PrNo(Posn(m))Symbol(m)-NewSymbol(m) ) 注意上面两个式子中用到的是前面讨论过的适当减法。由于这些函数都是原始递归函数，因此NewTapeNum 也是原始递归函数。 我们已经描述了计算T 在格局数字上一步移动的函数，现在我们描述更通用的函数，它计算T 的k 步移动。考虑下面定义的函数Trace T : N 2→N ， Trace T (m,0)=?? ?=otherwise true m Isconfig m T )(0 Trace T (m,k+1)= ? ? ?=otherwise true m Isconfig k m Trace Move T T T )(0)),(( 根据引理13.5，Trace T 由两个原始递归函数经过原始递归运算得到，因此也是原始递归函数。 假设m 是一个格局数字，那么Trace T (m,k)表示了T 从格局m 开始，经过k 步移动后的格局数字，如果T 在k 步移动以内就停止了，那么Trace T (m,k)表示停止时的格局数字。 为了完成定理13.10的证明，我们还需要一个辅助函数。函数Halting T : N →N 定义如下 Halting T (m)=otherwise m Exponent m IsConfig T 0),0()(1 0=∧?? ? Halting T (m)=0当且仅当m 是T 的停机格局数字，显然这是一个原始递归函数。 定理13.10的证明：我们只需要将前面证明的各个结果组合在一起，就能完成定理13.10 的证明。如前面讨论，令T 是计算f 的图林机。对于任意的m 和k ，函数Halting T (Trace T (m,k))的值为0当且仅当m 是T 的一个格局数字，并且从m 开始，T 在k 步内停机。定义函数MovesToHalt: N →N 如下 MovesToHalt(m)＝μk[Halting T (Trace T (m,k))=0] 并且定义f T : N →N 如下 f T (m)=Trace T (m,MovesToHalt(m)) 我们可以描述函数MovesToHalt 和f T 如下。如果m 是T 的一个格局数字，并且T 从m 出发最终停机，则MovesToHalt(m)是从m 到停机所经过的步数，f T (m)是停机格局数字。对于任何其他数值m ，这两个函数都是未定义的。由于MovesToHalt 由一个全域原始递归函数经过无界最小化运算得到，因此它是μ递归函数，由于f T 由一个原始递归函数和一个μ递归函数复合得到，因此f T 也是μ递归函数。 我们说函数 f=Result T (f T (InitConfig (n) )) 对于任意的X ，f(X)是定义的当且仅当Result T (f T (InitConfig (n)))是定义的，并且如果它们在X 上是定义的，则它们的值相等。为了说明这一点，一方面，假设f(X)是定义的，此时，如果T 从格局InitConfig (n)(X)开始，那么它最终会停机。因此f T (InitConfig (n) (X))是停机格局(h, ?1f(X))的格局数字，并且Result T 作用到这个格局数字，得到f(X)。另一方面，假设f(X)是未定义的，那么T 不能在输入X 时停机，这意味着f T (InitConfig (n) (X))是未定义的。因此证明完成。 13.6 非数值函数；可计算性的其他方法 Godel 编码技术允许我们将原始递归和μ递归的概念扩展到涉及字符串的函数，并得到相应的更通用的定理13.8和定理13.10。扩展思路如下，如果函数f 将字符串x 映射到字符串f(x)，那么我们可以用相关的数值函数p f 描述f ，p f 将x 的Godel 数映射到f(x)的Godel 数。为了讨论简便，本节我们考虑只有一个变量的函数，然而扩展到多个变量的函数的方法是显而易见的。 定义13.10（字符串的Godel 编码）令∑是一个字母表，它的元素是a 1,...,a s 。字符串 x=m i i i a a a (1) ∈∑* 的Godel 数gn(x)定义如下 gn(x)=gn(i 0,i 1,...,i m )=m i i m No )(Pr (20) 空字符Λ的Godel 数定义为1。 显然gn(x)的计算式中没有一个指数为0，这带来两个结果：首先，既然一个正整数的素数因子分解是唯一的，那么函数gn: ∑*→N 是一一映射的；第二，比如3=2031或10=213051不会是任何字符串的Godel 数。（另外还要注意，对于任意的x ∈∑*，出现在gn(x)的因子分解结果中的任何一个素数的指数的最大值不超过∑的元素个数，或|∑|。） 因为gn: ∑*→N 不是双射，因此不存在逆函数gn -1。但是容易定义一个从N 到∑*的gn 的左逆（left inverse ）函数gn ’， gn ’(n)=?? ?=??=Λ)) (() (x gn n x x gn n x 其中，缺省值Λ是随意选择的。gn ’称为gn 的左逆函数的原因是，任给x ∈∑* gn ’(gn(x))=x 现在假设f: ∑1*→∑2*是一个部分函数，其中∑1和∑2是字母表。我们定义相应的数值函数pf: N →N 如下，如果n 是x 对应的Godel 数，那么pf(n)是f(x)对应的Godel 数。注意gn 的一一映射性质是这个定义成立的基础。我们还可以利用Godel 编码函数的左逆函数简洁地表示pf 。如果g1: ∑1*→N 和g2: ∑2*→N 分别是∑1和∑2的Godel 编码函数，且g1’和g2’分别是它们的 左逆函数，那么 pf(n)=g2(f(g1’(n))) 为了更好理解上面的式子，参加图13-1跟踪等式右边的各个函数的复合过程，从图的坐下角开始，pf计算的过程是先后跟随向上、向右、向下的箭头完成的。 既然g1’是g1的左逆函数，则有 pf(g1(x)) =g2(f(g1’(g1(x)))) =g2(f(x)) 对任意x∈∑1*都成立。这个式子说明从图13-1的左上角到右下角的两个路径得到相同的结果，这也是说明函数pf是f镜像（如果f将字符串x映射到y，那么pf将数值gn(x)映射到gn(y)）的另一个方法。 定义13.11 令f: ∑1*→∑2*和pf: N→N是前面定义的函数。函数f称为原始递归函数当且仅当pf是原始递归函数。相似地，函数f称为μ递归函数当且仅当pf是μ递归函数。 定理13.11令f: ∑1*→∑2*，则f是可计算的当且仅当f是μ递归函数。 证明：同前面一样，我们用记号g1和g2分别表示两个字母表的Godel编码函数，并且g1’和g2’分别是它们的左逆函数。 一方面，假设f是可计算的，令Tf是计算f的图林机（Tf的磁带字母表包含∑1和∑2的字母）。我们希望证明f对应的pf是μ递归函数，根据定理13.10，只需证明pf是可计算的。在这里，我们不给出构造计算pf的图林机的细节，但是容易发现，根据pf的定义，计算pf的图林机可由下面3个简单图林机组合得到。第一个接受初始输入?1n后，停机时输出?g1’(n)，第二个是图林机Tf，它接受?g1’(n)后，停机时输出?f(g1’(n))，第三个计算Tf输出结果的Godel数，得到结果，g2(f(g1’(n)))=pf(n)。 另一方面，假设f是μ递归函数，则根据定义pf也是μ递归函数。根据定理13.8，pf是可计算函数，令T是计算pf的图林机。根据pf的定义式得到 g2’(pf(n))=g2’(g2(f(g1’(n)))) =f(g1’(n)) 参见图13-1，上面式子反映了从左下角到右上角的两条路径得到相同的结果。当n=g1(x)时，应用上面的式子得到 f(x)=f(g1’(g1(x)))=g2’(pf(g1(x))) 类似前面的证明，我们可以根据等号右边式子构造一个计算f的复合图林机Tf，从而证明f是可计算的。 可计算理论和递归函数是得到广泛和深入研究的课题，本章的内容只是一个简短的导引。结束之前，我们还简单提及其他一些方法。 正如无限制文法提供了生成语言的一种方法，它们也可以用于刻画可计算函数。如果G=(V,∑,S,P)是一个文法，f是一个从∑*到∑*的部分函数。G被称为计算f，如果满足下面条件：如果A, B, C, D是V中的非终结符，对于任意的x,y∈∑*， f(x)=y当且仅当AxB?G*CyD 利用定理11.1和定理11.2的结论，能够证明上面方式定义的可计算函数等价于以图林机方式定义的可计算函数。 用高级程序设计语言书写的计算机程序可以被视为从字符串集合到字符串集合的函数。我们很自然地考虑能够被程序（比如C语言程序）计算的函数的集合。如果我们忽略任何一个具体实现中的物理限制，比如假设计算机的内存是无限大的，能够表示的整数也没有限制等等，那么“C语言可计算”与“图林机可计算”是等价的。 虽然高级程序设计语言，比如C，包含许多特性以便书写程序，但是这些特性没有改变它能计算的函数的范围。我们可以考虑一个非常简单的程序语言，它只有一个变量，只有一种数据类型，自然数。只有下面几种语句 新定义问题（一）（讲义） 知识点睛 新定义问题是在已学知识基础上，以未接触过的新定义为载体，现学现用，侧重考查理解、分析、应用等能力的问题。 此类问题的一般思路： ①结合图形，理解新定义关键词； ②借助题目正反举例，理解新定义实质，尝试“化生为熟”； ③结合背景信息，借助新定义求解． 精讲精练 1.如图，边长为8的正方形OABC的两边在坐标轴上，以C为 顶点的抛物线经过点A，P是抛物线上点A，C间的一个动点（含端点），过点P作PF⊥BC于点F．点D，E的坐标分别为(0，6)，(-4，0)，连接PD，PE，DE． （1）请直接写出抛物线的解析式． （2）小明探究点P的位置发现：当点P与点A或点C重合时，PD与PF的差为定值．进而猜想：对于任意一点P，PD与PF的差为定值．请你判断该猜想是否正确，并说明理由．（3）小明进一步探究得出结论：若将使△PDE的面积为整数的点P记作“好点”，则存在多个“好点”，且使△PDE的周长最小的点P也是一个“好点”．请直接写出所有“好点”的个数，并求出△PDE的周长最小时“好点”的坐标． 2.已知抛物线2y ax bx c =++，若a ，b ，c 满足b =a +c ，则称抛 物线2y ax bx c =++为“恒定”抛物线． （1）求证：“恒定”抛物线2y ax bx c =++必过x 轴上的一个定点A ； （2）已知“恒定”抛物线233y x =-的顶点为P ，与x 轴的另一个交点为B ，是否存在以Q 为顶点，与x 轴另一个交点为C 的“恒定”抛物线，使得以PA ，CQ 为边的四边形是平行四边形？若存在，求出抛物线解析式；若不存在，请说明理由． 一、MATLAB常用的基本数学函数 abs(x)：纯量的绝对值或向量的长度 angle(z)：复数z的相角(Phase angle) sqrt(x)：开平方 real(z)：复数z的实部 imag(z)：复数z的虚部 conj(z)：复数z的共轭复数 round(x)：四舍五入至最近整数 fix(x)：无论正负，舍去小数至最近整数 floor(x)：地板函数，即舍去正小数至最近整数ceil(x)：天花板函数，即加入正小数至最近整数rat(x)：将实数x化为分数表示 rats(x)：将实数x化为多项分数展开 sign(x)：符号函数(Signum function)。 当x<0时，sign(x)=-1； 当x=0时，sign(x)=0; 当x>0时，sign(x)=1。 rem(x,y)：求x除以y的馀数 gcd(x,y)：整数x和y的最大公因数 lcm(x,y)：整数x和y的最小公倍数 exp(x)：自然指数 pow2(x)：2的指数 log(x)：以e为底的对数，即自然对数或 log2(x)：以2为底的对数 log10(x)：以10为底的对数 二、MATLAB常用的三角函数 sin(x)：正弦函数 cos(x)：余弦函数 tan(x)：正切函数 asin(x)：反正弦函数 acos(x)：反馀弦函数 atan(x)：反正切函数 atan2(x,y)：四象限的反正切函数 sinh(x)：超越正弦函数 cosh(x)：超越馀弦函数 tanh(x)：超越正切函数 asinh(x)：反超越正弦函数 acosh(x)：反超越馀弦函数 atanh(x)：反超越正切函数 三、适用於向量的常用函数有： min(x): 向量x的元素的最小值 max(x): 向量x的元素的最大值 mean(x): 向量x的元素的平均值 median(x): 向量x的元素的中位数 std(x): 向量x的元素的标准差 diff(x): 向量x的相邻元素的差 sort(x): 对向量x的元素进行排序（Sorting）length(x): 向量x的元素个数 norm(x): 向量x的欧氏（Euclidean）长度sum(x): 向量x的元素总和 prod(x): 向量x的元素总乘积 cumsum(x): 向量x的累计元素总和cumprod(x): 向量x的累计元素总乘积 dot(x, y): 向量x和y的内积 cross(x, y): 向量x和y的外积 四、MATLAB的永久常数 函数中的新定义问题 一、填空题 1、定义区间[x1,x2](x1?x2)的长度为x2?x1,已知函数 f(x)?|log1x|的定义域为[a,b],值域为[0,2],则区间[a,b]的长度的最大值与最小值的差 2 为 . 2、（2015余杭区模拟）已知函数f（x）的定义域为R，若存在常数m＞0，对任意x∈R，有|f（x）|≤m|x|，则称函数f（x）为F﹣函数．给出下列函数：①f（x）=x；②f（x）= x2；③f（x）=2；④f（x）=sin2x．其中是F﹣函数的序号为． 3、（2009厦门十中）定义：若存在常数k，使得对定义域D内的任意两个x1,x2?x1?x2?，均有f?x1??f?x2?kx1?x2成立，则称函数f?x?在定义域D上满足利普希茨条件。若函数f?x?? 4、（2012格致三模）已知全集为U，P??U，定义集合P的特征函数为x?x?1?满足利普希茨条件，则常数k的最小值为_____。 ??1,x?P,fP?x???，对于A??U， B??U，给出下列四个结论： 0,x?eP.?U? ①对任意x?U，有feUA?x??fA?x??1； ②对任意x?U，若A??B，则fA?x??fB?x?； ③对任意x?U，有fAIB?x??fA?x??fB?x?； ④对任意x?U，有fA?B?x??fA?x??fB?x?。 其中，正确结论的序号是__________。 5、定义运算：a*b=，对于函数f（x）和g（x），函数|f（x）﹣g（x）|在闭区间[a，b]上的最大值称为f（x）与g（x）在闭区间[a，b]上的“绝对差”，记为（f（x），g（x）），则（sinx*cosx，1）= ． Excel函数应用之逻辑函数 编者语：Excel是办公室自动化中非常重要的一款软件，很多巨型国际企业都是依靠Excel 进行数据管理。它不仅仅能够方便的处理表格和进行图形分析，其更强大的功能体现在对数据的自动处理和计算，然而很多缺少理工科背景或是对Excel强大数据处理功能不了解的人却难以进一步深入。编者以为，对Excel函数应用的不了解正是阻挡普通用户完全掌握Excel 的拦路虎，然而目前这一部份内容的教学文章却又很少见，所以特别组织了这一个《Excel 函数应用》系列，希望能够对Excel进阶者有所帮助。《Excel函数应用》系列，将每周更新，逐步系统的介绍Excel各类函数及其应用，敬请关注！ 用来判断真假值，或者进行复合检验的Excel函数，我们称为逻辑函数。在Excel中提供了六种逻辑函数。即AND、OR、NOT、FALSE、IF、TRUE函数。 一、AND、OR、NOT函数 这三个函数都用来返回参数逻辑值。详细介绍见下： （一）AND函数 所有参数的逻辑值为真时返回TRUE；只要一个参数的逻辑值为假即返回FALSE。简言之，就是当AND的参数全部满足某一条件时，返回结果为TRUE，否则为FALSE。 语法为AND(logical1,logical2, ...)，其中Logical1, logical2, ... 表示待检测的1 到30 个条件值，各条件值可能为TRUE，可能为FALSE。参数必须是逻辑值，或者包含逻辑值的数组或引用。举例说明： 1、在B2单元格中输入数字50，在C2中写公式=AND(B2>30,B2<60)。由于B2等于50的确大于30、小于60。所以两个条件值（logical）均为真，则返回结果为TRUE。 图1 AND函数示例1 2、如果B1-B3 单元格中的值为TRUE、FALSE、TRUE，显然三个参数并不都为真，所以在B4单元格中的公式=AND(B1:B3) 等于FALSE Excel利用函数进行数据计算（教案） ——制作歌手大奖赛成绩统计表 （执教人：信息技术教研组王荔虹） [课题] Excel利用函数进行数据计算 [教学内容] Excel数据的函数运算 [教学对象] 1、子江中学初一（1）班。 2、对Excel有了初步的认识。 [教学目标] 知识目标：1、了解函数的定义、组成和使用方法； 2、掌握SUM、A VERAGE、MAX、MIN等几种函数的使用方法； 3、了解设置单元格格式的基本方法； 4、学会利用函数进行简单的计算。 过程与方法：通过对Excel运用公式与函数运算的对比，能够在实际运用中正确选择和使用何种方法进行数据处理。 情感目标：体验应用公式和函数解决问题的优势。，感受计算机的优势，增强学生学习计算机的兴趣。[教学重点] 掌握SUM、A VERAGE、MAX、MIN等几种函数的使用方法。 [教学难点] 1、理解函数的参数和函数参数的格式。 2、函数中的选定数据范围（包括连续和不连续）。 [教学方法] 1、创设情境法：教师创设好Excel的故事导入情境，激发学生的学习兴趣。 2、游戏讲授法：通过有趣的游戏环节，讲解Excel中什么是函数，通过故事内容中的数据让学生区分公式运算与函数运算。 3、任务驱动法：根据布置任务的具体要求，利用习得的知识经验进行迁移学习，从而达到相应的教学目标。 4、自主探究法：分小组结合书本、教师提示，自主探究、合作学习相应的教学目标。 [教学准备] 1、教师准备：提供Excel运算的辅助材料，如练习、导入材料等。 2、学生准备：课前分好小组。 3、教学环境：多媒体网络教室。 [课时] 1课时 [教学过程] 使用函数计算和统计数据 一、案例背景信息： 1．模块四：用计算机处理数据第4单元在 Excel中进行数据计算第二课时使用函数计算和统计数据 2．年级：八年级 3．所用教材版本：电子工业出版社（编著） 4．学时数：1课时 二、教学设计 （一）教学目标: 知识目标：1、理解函数的概念 2、了解SUM、AVERAGE、COUNTIF函数的功能； 3、掌握SUM、AVERAGE、COUNTIF函数的使用方法； 技能目标：1、培养学生自主探究，合作学习的能力； 2、培养学生分析数据，处理数据的能力； 情感目标：让学生亲身体验EXCEL强大的运算功能，通过系统学习，培养学生积极思考、敢于动手、自主探究的能力。 教学重点：学会利用三个函数进行计算； 教学难点：数据范围的选择，条件的输入； （二）内容分析： 课程标准规定，第4单元主要是利用Excel提供的各种公式和函数，完成对工作表中数据的统计分析，提高学生处理信息的能力。随着社会的进步，人们在日常生活中产生的数据越来越多，对处理数据的速度和精度要求也越来越高。计算机成为最有效的数据处理工具。本节课是在学生学习了如何在工作表利用公式进行数据计算的基础上，进一步让学生学会如何在Excel中使用函数计算和统计数据使学生对数据处理有个感性认识。这部分内容在整册课本中是重点也是难点。在本课时中，主要介绍了求和函数SUM、求平均值函数AVERAGE，条件统计函数CO UNTIF，这部分内容相对初中学生的知识水平来说比较复杂。我认为教学的重点应该放在三个函数的基本使用方法上，而难点则应该放在用函数进行计算时在编辑栏或“函数参数”对话框中进行单元格区域的修改。 （三）学生分析： 八年级的学生思维活跃，想象力丰富，好奇心强，同时又有了一定的自学能力和动手能力。通过前面课程的学习，学生已基本掌握了在工作表中利用公式计算三科总分、折算后总分，总分的基本操作，在此基础上进一步让学生学会如何在E xcel中使用函数进行数据计算，使学生对数据处理有个感性认识。 （四）教学策略设计 1．教学方法设计： (１)、自学法 对于内容比较简单，并且教材有明确答案的知识点，采用自学法，既可以体现学生的主体地位，又可以培养学生的自学能力。 与函数有关的新定义题型 1．(2016长沙25题10分)若抛物线L ：y ＝ax 2＋bx ＋c(a ，b ，c 是常数，abc ≠0)与直线l 都经过y 轴上的一点P ，且抛物线L 的顶点Q 在直线l 上，则称此直线l 与该抛物线L 具有“一带一路”关系．此时直线l 叫做抛物线L 的“带线”，抛物线L 叫做直线l 的“路线”． (1)若直线y ＝mx ＋1与抛物线y ＝x 2－2x ＋n 具有“一带一路”关系，求m ，n 的值； (2)若某“路线”L 的顶点在反比例函数y ＝6 x 的图象上，它的“带线”l 的解析式为y ＝2x －4， 求此“路线”L 的解析式； (3)当常数k 满足1 2≤k ≤2时，求抛物线L ：y ＝ax 2＋(3k 2－2k ＋1)x ＋k 的“带线”l 与x 轴， y 轴所围成的三角形面积的取值范围． 2．(2015长沙25题10分)在直角坐标系中，我们不妨将横坐标、纵坐标均为整数的点．．．．．．称之为“中国结”． (1)求函数y ＝3x ＋2的图象上所有“中国结”的坐标； (2)若函数y ＝k x (k ≠0，k 为常数)的图象上有且只有两个“中国结”，试求出常数k 的值与 相应“中国结”的坐标； (3)若二次函数y ＝(k 2－3k ＋2)x 2＋(2k 2－4k ＋1)x ＋k 2－k (k 为常数)的图象与x 轴相交得到两个不同的“中国结”，试问该函数的图象与x 轴所围成的平面图形中(含边界)，一共包含有多少个“中国结”？ 3．(2014长沙25题10分)在平面直角坐标系中，我们不妨把横坐标与纵坐标相等的点称为“梦之点”．例如点(－1，－1)，(0，0)，(2，2)，…都是“梦之点”，显然，这样的“梦之点”有无数个． (1)若点P (2，m )是反比例函数y ＝n x (n 为常数，n ≠0)的图象上的“梦之点”，求这个反比 例函数的解析式； (2)函数y ＝3kx ＋s －1(k ，s 是常数)的图象上存在“梦之点”吗？若存在，请求出“梦之点”的坐标；若不存在，请说明理由； (3)若二次函数y ＝ax 2＋bx ＋1(a ，b 是常数，a >0)的图象上存在两个不同的“梦之点”A (x 1，x 1)，B (x 2，x 2)，且满足－2 公式运用： 请在注册后使用：音视频转换工具软件 名称: crsky 注册码: WHAT-DOYO-UWAN-TTOD-00CE-58F8-5D10-2F1A 常用公式： 一、 1：求和:SUM 可以利用来算一行或一列数字的总和。如算总分。 2：求平均数:average 可以利用来算一行或一列数字的平均值。如算平均分 3：求非空单元格的个数:counta /count 可以利用来算一行或一列（有内容/有数字）的单元格个数。如算参加考试的学生数。4：求满足条件的非空单元格的个数:countif 可以利用来算一行或一列有内容的同时又满足某个条件的单元格个数。如算满足60分以上的学生人数，即及格人数。 5：标准差:STDEVP 可以利用来算一行或一列数字的标准差。标准差是一组数值自平均值分散开来的程度的一种测量观念。一个较大的标准差，代表大部分的数值和其平均值之间差异较大；一个较小的标准差，代表这些数值较接近平均值。反映学生的分数分化差异。 二、自由公式的运用 1.加减乘除四则运算：电脑键盘的右边，小键盘上有。 加：+ （如：=A1+A2)也可: =5+5 减：- （如：=A1-A2)也可: =5-5 乘：* （如：=A1*A2)也可: =5*5 除：/ （如：=A1/A2)也可: =5/5 2.组合公式运算： A.算及格率：组合公式原理：知道及格人数和总人数。利用及格人数除以总人数 及格人数公式：countif来计算。=COUNTIF（A1：A50，”>=60”) 总人数：可以手写如50，也可以counta来算。 公式组合：= COUNTIF（A1：A50，”>=60”)/ counta（A1：A50） B.算优秀率：组合公式原理：知道优秀人数和总人数。利用优秀人数除以总人数 优秀人数公式：countif来计算。 总人数：可以手写如50，也可以counta来算。 公式组合：= COUNTIF（A1：A50，”>=80”)/ counta（A1：A50） C.算难度系数：组合公式原理：知道平均分和总分。利用平均分除以总分 平均分公式：average来计算。 总分：试卷小题有标注，如3分 公式组合：= average （A1：A50)/ 3 D.选择题选A率：组合公式原理：知道选择了A的总数和班级总人数。利用选择了A的总数除以班级总人数 选择A的总数公式：countif来计算。 Excel函数应用之统计函数 Excel的统计工作表函数用于对数据区域进行统计分析。例如，统计工作表函数可以用来统计样本的方差、数据区间的频率分布等。是不是觉得好像是很专业范畴的东西？是的，统计工作表函数中提供了很多属于统计学范畴的函数，但也有些函数其实在你我的日常生活中是很常用的，比如求班级平均成绩，排名等。在本文中，主要介绍一些常见的统计函数，而属于统计学范畴的函数不在此赘述，详细的使用方法可以参考Excel帮助及相关的书籍。 在介绍统计函数之前，请大家先看一下附表中的函数名称。是不是发现有些函数是很类似的，只是在名称中多了一个字母A？比如，AVERAGE与AVERAGEA；COUNT与COUNTA。基本上，名称中带A的函数在统计时不仅统计数字，而且文本和逻辑值（如TRUE 和 FALSE）也将计算在内。在下文中笔者将主要介绍不带A的几种常见函数的用法。 一、用于求平均值的统计函数AVERAGE、TRIMMEAN 1、求参数的算术平均值函数AVERAGE 语法形式为AVERAGE(number1,number2, ...) 其中Number1, number2, ...为要计算平均值的 1～30 个参数。这些参数可以是数字，或者是涉及数字的名称、数组或引用。如果数组或单元格引用参数中有文字、逻辑值或空单元格，则忽略其值。但是，如果单元格包含零值则计算在内。 2、求数据集的内部平均值TRIMMEAN 函数TRIMMEAN先从数据集的头部和尾部除去一定百分比的数据点，然后再求平均值。当希望在分析中剔除一部分数据的计算时，可以使用此函数。比如，我们在计算选手平均分数中常用去掉一个最高分，去掉一个最低分，XX号选手的最后得分，就可以使用该函数来计算。语法形式为TRIMMEAN(array,percent) 其中Array为需要进行筛选并求平均值的数组或数据区域。Percent为计算时所要除去的数据点的比例，例如，如果 percent = 0.2，在 20 个数据点的集合中，就要除去 4 个数据点（20 x 0.2），头部除去 2 个，尾部除去 2 个。函数 TRIMMEAN 将除去的数据点数目向下舍为最接近的 2 的倍数。 3、举例说明：示例中也列举了带A的函数AVERAGEA的求解方法。 求选手Annie的参赛分数。在这里，我们先假定已经将该选手的分数进行了从高到底的排序，在后面的介绍中我们将详细了解排序的方法。 图1 《使用公式计算数据》教学设计 一、案例背景信息 1．模块4：用计算机处理数据 2．年级：八年级下 3．所用教材版本：宁夏教育厅教研室电子工业出版社 4．学时数：1学时 教材分析： 本节课教学内容是选自电子工业出版社出版，宁夏教育厅教研室编著的，初中信息技术教材八年下册第4单元第1课时使用公式计算数据的教学内容，本节课是在学生学习了工作表的编辑和美化的基础上，主要介绍利用Excel所提供的各种公式，完成对工作表中数据统计分析，提高学生处理信息的能力。 学情分析: 教学对象是八年级学生，从学生的特点来看，思维活跃，想象力丰富，好奇心强，同时又有了一定的自学能力和动手能力。但多数情况下还比较肤浅和不够成熟，尤其对于一些知识和技能的掌握还处于一知半解的状态。通过前面的学习，学生已基本掌握了在工作表输入数据、编辑、修饰工作表的基本操作，在此基础上进一步学会如何在Excel中进行数据计算，使学生对数据处理有个感性认识。因此，根据学生心理特点，以帮助老师计算学生考试总分入手，激发学生学习兴趣，利用课本资源，从单纯学习信息技术处理技能转为更加注重对学生信息素养提高教育，使学生在独自处理信息的过程中，既满足对新知的渴求，又体验信息技术教学的魅力。 教学目标: 1、情感、态度与价值观： 让学生亲身体验EXCEL中公式运算的功能，培养学生合作学习、善于思考、敢于动手、细心认真、自主探究的能力，能够应用所学知识解决生活中所遇到的问题。 2、过程与方法： 教师讲解和学生尝试操作探究相结合；体验Excel中的数据计算的方法和过程。 3、知识与技能： 了解公式的概念及输入公式的基本操作步骤，学会创建、修改公式，正，能结合数学内容理解公式的概念并能灵活使用，培养学生的动手操作能力和探究新知的能力。 教学重点及解决措施： 创建和编辑公式、掌握利用公式进行数据计算的方法是本课的教学重点，通过教材中的“做一做”和“试试看”练习体会掌握使用公式计算数据的方法。 教学难点及解决措施 公式的应用是本节课的难点。通过观察操作提示及同学间的交流与协作互助，让学生在遇到学习困难时，懂得寻求协助，从而突破难点。 教学设计思路 本节课的知识，在电子表格使用公式计算数据中是本册书的难点之一，教师应改变传统的简单地向学生介绍如何操作，以及对知识点枯燥地讲解，而是安排学生实际操作，自己动手做，从中观察、体会、理解、掌握使用公式计算数据中对单元格的引用，在学生上机操作过程，善于抓住典型问题，然后引导学生运用教材中的“金钥匙”和“小博士”中的知识来解决问题，让学生在教师引导下分析任务、完成任务。 教学方法： 专题训练(四)与二次函数相关的新定义问题 ?类型之一应用型：阅读——理解——建模——应用 图4－ZT－1 1．2017·巴中如图4－ZT－1，我们把一个半圆与抛物线的一部分合成的封闭图形称为“蛋圆”，点A，B，C，D分别是“蛋圆”与坐标轴的交点，AB为半圆的直径，且抛物线的函数表达式为y＝x2－2x－3，则半圆圆心M点的坐标为________. 2．一个函数的图象关于y轴成轴对称图形时，我们称该函数为“偶函数”．如果二次函数y＝x2＋bx－4是“偶函数”，该函数的图象与x轴交于点A和点B，顶点为P，那么△ABP 的面积是________． 3．2017·余杭区一模如果两个二次函数的图象关于y轴对称，我们就称这两个二次函数互为“关于y轴对称二次函数”，如图4－ZT－2所示，二次函数y1＝x2＋2x＋2与y2＝x2－2x＋2是“关于y轴对称二次函数”． (1)直接写出两条图中“关于y轴对称二次函数”图象所具有的特点． (2)二次函数y＝2(x＋2)2＋1的“关于y轴对称二次函数”表达式为____________；二次函数y＝a(x－h)2＋k的“关于y轴对称二次函数”表达式为____________． (3)平面直角坐标系中，记“关于y轴对称二次函数”的图象与y轴的交点为A，它们的两个顶点分别为B，C，且BC＝6，顺次连结点A，B，O，C得到一个面积为24的菱形，求“关于y轴对称二次函数”的表达式． 图4－ZT－2 ?类型之二探究型：阅读——理解——尝试——探究 4．若抛物线y＝ax2＋bx＋c过定点M(1，1)，则称此抛物线为定点抛物线． (1)张老师在投影屏幕上出示了一个题目：请你写出一条定点抛物线的函数表达式．小敏写出了一个答案：y＝2x2＋3x－4，请你写出一个不同于小敏的答案； (2)张老师又在投影屏幕上出示了一个思考题：已知定点抛物线y＝－x2＋2bx＋c＋1，求该抛物线顶点纵坐标的值最小时的函数表达式．请你解答． 5．2017·衢州定义：如图4－ZT－3①，抛物线y＝ax2＋bx＋c(a≠0)与x轴交于A，B 两点，点P在该抛物线上(点P与A，B两点不重合)，若△ABP的三边满足AP2＋BP2＝AB2，则称点P为抛物线y＝ax2＋bx＋c(a≠0)的勾股点． (1)直接写出抛物线y＝－x2＋1的勾股点的坐标； (2)如图②，已知抛物线C：y＝ax2＋bx(a≠0)与x轴交于A，B两点，点P(1，3)是抛物线C的勾股点，求抛物线C的函数表达式； (3)在(2)的条件下，点Q在抛物线C上，求满足条件S△ABQ＝S△ABP的点Q(异于点P)的坐标． EXCEL的常用计算公式大全 一、单组数据加减乘除运算： ①单组数据求加和公式：=（A1+B1） 举例：单元格A1：B1区域依次输入了数据10和5，计算：在C1中输入 =A1+B1 后点击键盘“Enter（确定）”键后，该单元格就自动显示10与5的和15。 ②单组数据求减差公式：=（A1-B1） 举例：在C1中输入 =A1-B1 即求10与5的差值5，电脑操作方法同上； ③单组数据求乘法公式：=（A1*B1） 举例：在C1中输入 =A1*B1 即求10与5的积值50，电脑操作方法同上； ④单组数据求乘法公式：=（A1/B1） 举例：在C1中输入 =A1/B1 即求10与5的商值2，电脑操作方法同上； ⑤其它应用： 在D1中输入 =A1^3 即求5的立方（三次方）； 在E1中输入 =B1^（1/3）即求10的立方根 小结：在单元格输入的含等号的运算式，Excel中称之为公式，都是数学里面的基本运算，只不过在计算机上有的运算符号发生了改变——“×”与“*”同、“÷”与“/”同、“^”与“乘方”相同，开方作为乘方的逆运算，把乘方中和指数使用成分数就成了数的开方运算。这些符号是按住电脑键盘“Shift”键同时按住键盘第二排相对应的数字符号即可显示。如果同一列的其它单元格都需利用刚才的公式计算，只需要先用鼠标左键点击一下刚才已做好公式的单元格，将鼠标移至该单元格的右下角，带出现十字符号提示时，开始按住鼠标左键不动一直沿着该单元格依次往下拉到你需要的某行同一列的单元格下即可，即可完成公司自动复制，自动计算。 二、多组数据加减乘除运算： ①多组数据求加和公式：(常用) 举例说明：=SUM（A1:A10）,表示同一列纵向从A1到A10的所有数据相加； =SUM（A1:J1）,表示不同列横向从A1到J1的所有第一行数据相加； ②多组数据求乘积公式：（较常用） 举例说明：=PRODUCT（A1:J1）表示不同列从A1到J1的所有第一行数据相乘； =PRODUCT（A1:A10）表示同列从A1到A10的所有的该列数据相乘； ③多组数据求相减公式：(很少用) 举例说明：=A1-SUM（A2:A10）表示同一列纵向从A1到A10的所有该列数据相减； =A1-SUM（B1:J1）表示不同列横向从A1到J1的所有第一行数据相减； ④多组数据求除商公式：(极少用) 举例说明：=A1/PRODUCT（B1:J1）表示不同列从A1到J1的所有第一行数据相除； =A1/PRODUCT（A2:A10）表示同列从A1到A10的所有的该列数据相除； 三、其它应用函数代表： ①平均函数 =AVERAGE（:）；②最大值函数 =MAX （:）；③最小值函数 =MIN （:）； ④统计函数 =COUNTIF（:）：举例：Countif ( A1：B5，”>60”) 一、导入（3分钟） 创设情景：减肥问题，怎样知道自己现在的体重是否正常？ BMI体重指数的计算方法，数据繁复，可以利用excel快速确凿的计算结果。 引入新课：（板书）在excel中使用公式计算数据 二、新授 以简单例子入手体会公式的优势，然后逐步解决难题。学生阅读课本，初步了解公式的使用，并熟悉输入公式的步骤（2分钟） 1、公式的概念：对数据进行运算的算式。（8分钟） 请学生说教师演示计算三科总分的方法，演示过程中讲解输入公式的步骤。 ①确定并选定存放计算结果的xx ②输入“=”：可以在编辑栏里输入，也可以在单元格中输入。强调公式的标志“=”③输入=C3+D3+E3（所有参与运算的数值与符号都必须是英文半角字符，结果正确吗？刚才同学们看课本，发现有这样一句话，在excel中输入公式时，大凡不输入数字，而是在公式中引用单元格地址。为什么要用单元格地址呢？演示修改某科成绩其结果发生变化。）④确认输入（回车或者编辑栏里的对勾），提示取消输入的方法 2、复制公式：（3分钟） 做完第一位同学的成绩后，第二位、第三位的怎么做？（引导学生学习62页的小博士） 三、小组对抗（小组内相互协助，小组间竞争）（14分钟） 1、学生活动：将班级学生分为3大组，第一组完成任务一、第二组完成任务二、第三组完成任务三，完成任务的同学可以去完成其两组的任务。（6分钟） 2、学生演示：请各组一位同学上教师机演示操作，并针对出现问题统一讲解（6分钟） 3、根据小组内完成情况给小组评分（2分钟） 四、实践活动（3分钟） 学以致用，请用你今天学到的知识解决课前提出的问题，利用公式计算每位职工的体重指数。 提示：BMI=体重/（身高*身高） 学生演示，教师小结：使用公式计算数据过程中注意优先顺序，使用括号（2分钟）情感价值：了解自己的健康状况，不要盲目减肥，帮助你的家人或者朋友诊断他们的健康状况。 五、课堂小结（2分钟） 想一想，这节课你都学到了什么？哪位同学可以站起来说一说。 幻灯展示本节课的知识点，引导学生一起总结，强调输入公式的四个步骤。 六、评价（1分钟）填写自评表，并计算总分。 Excel常用函数公式大全 1、查找重复内容公式：=IF(COUNTIF(A:A,A2)>1,"重复","")。 2、用出生年月来计算年龄公式：=TRUNC((DAYS360(H6,"2009/8/30",FALSE))/360,0)。 3、从输入的18位身份证号的出生年月计算公式： =CONCATENATE(MID(E2,7,4),"/",MID(E2,11,2),"/",MID(E2,13,2))。 4、从输入的身份证号码内让系统自动提取性别，可以输入以下公式： =IF(LEN(C2)=15,IF(MOD(MID(C2,15,1),2)=1,"男","女"),IF(MOD(MID(C2,17,1),2)=1,"男","女"))公式内的“C2”代表的是输入身份证号码的单元格。 1、求和：=SUM(K2:K56) ——对K2到K56这一区域进行求和； 2、平均数：=AVERAGE(K2:K56) ——对K2 K56这一区域求平均数； 3、排名：=RANK(K2，K$2:K$56) ——对55名学生的成绩进行排名； 4、等级：=IF(K2>=85,"优",IF(K2>=74,"良",IF(K2>=60,"及格","不及格"))) 5、学期总评：=K2*0.3+M2*0.3+N2*0.4 ——假设K列、M列和N列分别存放着学生的“平时总评”、“期中”、“期末”三项成绩； 6、最高分：=MAX(K2:K56) ——求K2到K56区域（55名学生）的最高分； 7、最低分：=MIN(K2:K56) ——求K2到K56区域（55名学生）的最低分； 8、分数段人数统计： （1）=COUNTIF(K2:K56,"100") ——求K2到K56区域100分的人数；假设把结果存放于K57单元格； （2）=COUNTIF(K2:K56,">=95")－K57 ——求K2到K56区域95～99.5分的人数；假设把结果存放于K58单元格； （3）=COUNTIF(K2:K56,">=90")－SUM(K57:K58) ——求K2到K56区域90～94.5分的人数；假设把结果存放于K59单元格； （4）=COUNTIF(K2:K56,">=85")－SUM(K57:K59) ——求K2到K56区域85～89.5分的人数；假设把结果存放于K60单元格； 专题突破(十) 新定义问题 1． 在平面直角坐标系xOy 中，⊙C 的半径为r ，P 是与圆心C 不重合的点，点P 关于⊙O 的反称点的定义如下：若在射线．．CP 上存在一点P ′，满足CP ＋CP ′＝2r ，则称P ′为点P 关于⊙C 的反称点，如图Z10－1为点P 及其关于⊙C 的反称点P ′的示意图． (1)当⊙O 的半径为1时． ①分别判断点M (2，1)，N (3 2，0)，T (1，3)关于⊙O 的反称点是否存在，若存在，求其 坐标； ②点P 在直线y ＝－x ＋2上，若点P 关于⊙O 的反称点P ′存在，且点P ′不在x 轴上，求点P 的横坐标的取值范围． (2)当⊙C 的圆心在x 轴上，且半径为1，直线y ＝－ 3 3 x ＋2 3与x 轴、y 轴分别交于点A ，B.若线段AB 上存在点P ，使得点P 关于⊙C 的反称点P ′在⊙C 的内部，求圆心C 的横坐标的取值范围． 图Z10－1 2． 对某一个函数给出如下定义：若存在实数M >0，对于任意的函数值y ，都满足－M ≤y ≤M ，则称这个函数是有界函数．在所有满足条件的M 中，其最小值称为这个函数的边界值．例如，图Z10－2中的函数是有界函数，其边界值是1. (1)分别判断函数y ＝1 x (x >0)和y ＝x ＋1(－4 常用函数 一、投资函数 （一）PV 1．含义：返回投资的现值。现值为一系列未来付款当前值的累积和。例如，借人方的借人款即为贷出方贷款的现值。 2．语法：PV (rate, nper, pmt, fv, type)。其中： rate为各期利率。例如，如果按10％的年利率借人一笔贷款来购买汽车，并按月偿还贷款，则月利率为0.83%（即10%/12)。可以在公式中输人10%/12或0.83％或0.0083作为rate 的值。 nper为总投资（或贷款）期，即该项投资（或贷款）的付款期总数。例如，对于一笔4年期按月偿还的汽车贷款，共有48（即4x12)个偿款期次。可以在公式中输人48作为nper 的值。 pmt为各期所应付给（或得到）的金额，其数值在整个年金期间（或投资期内）保持不变。通常pmt包括本金和利息，但不包括其他费用及税款。例如，10 000元的年利率为12％的4年期汽车贷款的月偿还额为263.33元。可以在公式中输人263.33作为pmt的值。 fv为未来值或在最后一次支付后希望得到的现金余额，如果省略fv，则假设其值为零（一笔贷款的未来值即为零）。例如，如果需要在18年后支付50 000元，则50 000元就是未来值。可以根据保守估计的利率来决定每月的存款额。 type为数字0或1，用以指定各期的付款时间是在期初还是期末。如果省略type，则假设其值为零，期末付款。 说明：应确认所指定的rate和nper单位的一致性。例如，同样是4年期年利率为12％的贷款，如果按月支付，rat。应为12 % /12, nper应为48（即4x12)；如果按年支付，rate 应为12%，nper为4。 3．示例。假设要购买一项保险年金，该保险可以在今后20年内于每月未回报500元。此项气金的购买成本为60 000元，假定投资回报率为8。现在可以通过函数PV计算一下这笔投资是否值得。该项年金的现值为： PV(0.08 /12,12＊20,500-0)＝一59 777.15（元） 结果为负值，因为这是一笔付款，亦即支出现金流。年金59 777.15元的现值小于实际支付的60 000元。因此，这不是一项合算的投资。 （二）NPV 1．含义：基于一系列现金流和固定的各期贴现率，返回一项投资的净现值。投资的净现值是指未来各期支出（负值）和收人（正值）的当前值的总和。 2．语法：NPV (rate, value 1, value 2,…）。其中： rate为各期贴现率，是一固定值。 value 1, value 2,…代表1-29笔支出及收人的参数值。 (1) value 1, value 2,…所属各期间的长度必须相等，而且支付及收人的时间都发生在期末。 (2) NPV按次序使用value 1, value 2,？来注释现金流的次序。所以一定要保证支出和收人的数额按正确的顺序输人。 (3)如果参数是数值、空白单元格、逻辑值或表示数值的文字表达式，则都会计算在内；如果参数是错误值或不能转化为数值的文字，则被忽略。 (4）如果参数是一个数组或引用，只有其中的数值部分计算在内。忽略数组或引用中的 计算机等级考试 =公式名称（参数1，参数2，。。。。。） =sum(计算范围) =average(计算范围) =sumifs(求和范围，条件范围1，符合条件1，条件范围2，符合条件2，。。。。。。) =vlookup(翻译对象，到哪里翻译，显示哪一种，精确匹配) =rank(对谁排名，在哪个范围里排名) =max(范围) =min(范围) =index(列范围，数字) =match(查询对象，范围，0) =mid(要截取的对象，从第几个开始，截取几个) =int(数字) =weekday(日期，2) =if(谁符合什么条件，符合条件显示的内容，不符合条件显示的内容) =if(谁符合什么条件，符合条件显示的内容，if(谁符合什么条件，符合条件显示的内容，不符合条件显示的内容)) EXCEL的常用计算公式大全 一、单组数据加减乘除运算： ①单组数据求加和公式：=（A1+B1） 举例：单元格A1：B1区域依次输入了数据10和5，计算：在C1中输入=A1+B1 后点击键盘“Enter（确定）”键后，该单元格就自动显示10与5的和15。 ②单组数据求减差公式：=（A1-B1） 举例：在C1中输入=A1-B1 即求10与5的差值5，电脑操作方法同上； ③单组数据求乘法公式：=（A1*B1） 举例：在C1中输入=A1*B1 即求10与5的积值50，电脑操作方法同上； ④单组数据求乘法公式：=（A1/B1） 举例：在C1中输入=A1/B1 即求10与5的商值2，电脑操作方法同上； ⑤其它应用： 在D1中输入=A1^3 即求5的立方（三次方）； 在E1中输入=B1^（1/3）即求10的立方根 小结：在单元格输入的含等号的运算式，Excel 中称之为公式，都是数学里面的基本 运算，只不过在计算机上有的运算符号发生了改变——“×”与“* ”同、“÷”与 “/ ”同、“^”与“乘方”相同，开方作为乘方的逆运算，把乘方中和指数使用成分数 就成了数的开方运算。这些符号是按住电脑键盘“Shift ”键同时按住键盘第二排 相对应的数字符号即可显示。如果同一列的其它单元格都需利用刚才的公式计算，只 需要先用鼠标左键点击一下刚才已做好公式的单元格，将鼠标移至该单元格的右下 角，带出现十字符号提示时，开始按住鼠标左键不动一直沿着该单元格依次往下拉到 你需要的某行同一列的单元格下即可，即可完成公司自动复制，自动计算。 3 实数b的取值范围． 变式 如果二次函数的二次项系数为l，则此二次函数可表示为y=x2+px+q，我们称[p，q]为此函数的特征数，如函数y=x2+2x+3的特征数是[2，3]． (1)若一个函数的特征数为[-2，1]，求此函数图象的顶点坐标． (2)探究下列问题： ①若一个函数的特征数为[4，-1]，将此函数的图象先向右平移1个单位，再向上平移1个单位，求得到的图象对应的函数的特征数． ②若一个函数的特征数为[2，3]，问此函数的图象经过怎样的平移，才能使得到的图象对应的函数的特征数为[3，4]？ 例3．如图1，抛物线y =ax 2 +bx +c （a ＞0）的顶点为M ，直线y =m 与x 轴平行，且与抛物线交于点A ，B ，若△AMB 为等腰直角三角形，我们把抛物线上A ，B 两点之间的部分与线段AB 围成的图形称为该抛物线对应的准蝶形，线段AB 称为碟宽，顶点M 称为碟顶，点M 到线段AB 的距离称为碟高． （1）抛物线2 12 y x = 对应的碟宽为 ；抛物线y =4x 2对应的碟宽为 ；抛物线y =ax 2（a ＞0）对应的碟宽为 ；抛物线y =a (x -2)2 +3（a ＞0）对应的碟宽为 ； （2）抛物线2 543 y ax ax =--（a ＞0）对应的碟宽为6，且在x 轴上，求a 的值； （3）将抛物线y =a n x 2+b n x +c n （a n ＞0）的对应准蝶形记为F n （n =1，2，3…），定义F 1， F 2，…，F n 为相似准蝶形，相应的碟宽之比即为相似比．若F n 与F n ﹣1的相似比为1 2 ，且F n 的碟顶 是F n ﹣1的碟宽的中点，现将（2）中求得的抛物线记为y 1，其对应的准蝶形记为F 1． ①求抛物线y 2的表达式； ②若F 1的碟高为h 1，F 2的碟高为h 2，…F n 的碟高为h n ，则h n = ，F n 的碟宽有端点横坐标为2；若F 1，F 2，…，F n 的碟宽右端点在一条直线上，请直接写出该直线的表达式；若不是，请说明理由。 1、查找重复内容公式：=IF(COUNTIF(A:A,A2)>1,"重复","")。 2、用出生年月来计算年龄公式： =TRUNC((DAYS360(H6,"2009/8/30",FALSE))/360,0)。 3、从输入的18位身份证号的出生年月计算公式： =CONCATENATE(MID(E2,7,4),"/",MID(E2,11,2),"/",MID(E2,13,2))。 4、从输入的身份证号码内让系统自动提取性别，可以输入以下公式： =IF(LEN(C2)=15,IF(MOD(MID(C2,15,1),2)=1,"男","女"),IF(MOD(MID(C2,17,1),2)=1,"男","女"))公式内的“C2”代表的是输入身份证号码的单元格。 1、求和：=SUM(K2:K56) ——对K2到K56这一区域进行求和； 2、平均数：=AVERAGE(K2:K56) ——对K2 K56这一区域求平均数； 3、排名：=RANK(K2，K$2:K$56) ——对55名学生的成绩进行排名； 4、等级：=IF(K2>=85,"优",IF(K2>=74,"良",IF(K2>=60,"及格","不及格"))) 5、学期总评：=K2*0.3+M2*0.3+N2*0.4 ——假设K列、M列和N列分别存放着学生的“平时总评”、“期中”、“期末”三项成绩； 6、最高分：=MAX(K2:K56) ——求K2到K56区域（55名学生）的最高分； 7、最低分：=MIN(K2:K56) ——求K2到K56区域（55名学生）的最低分； 8、分数段人数统计： （1）=COUNTIF(K2:K56,"100") ——求K2到K56区域100分的人数；假设把结果存放于K57单元格； （2）=COUNTIF(K2:K56,">=95")－K57 ——求K2到K56区域95～99.5分的人数；假设把结果存放于K58单元格； （3）=COUNTIF(K2:K56,">=90")－SUM(K57:K58) ——求K2到K56区域90～94.5分的人数；假设把结果存放于K59单元格； （4）=COUNTIF(K2:K56,">=85")－SUM(K57:K59) ——求K2到K56区域85～89.5分的人数；假设把结果存放于K60单元格； （5）=COUNTIF(K2:K56,">=70")－SUM(K57:K60) ——求K2到K56区域70～84.5分的人数；假设把结果存放于K61单元格； （6）=COUNTIF(K2:K56,">=60")－SUM(K57:K61) ——求K2到K56区域60～69.5分的人数；假设把结果存放于K62单元格； （7）=COUNTIF(K2:K56,"<60") ——求K2到K56区域60分以下的人数；假设把结果存放于K63单元格；二次函数新定义问题(一)(讲义及答案)
(完整版)MATLAB常用函数大全
函数中的新定义问题
考勤工资计算常用Excel函数
Excel利用函数进行数据计算(教案)
使用函数计算和统计数据教学设计
与函数有关的新定义题型
常用计算公式和函数
Excel函数应用之统计函数
《使用公式计算数据》教学设计
二次函数新定义问题
Excel常用的函数计算公式大全
在Excel中使用公式计算数据
Excel常用函数公式大全(实用)
中考数学专题突破十：新定义问题(含答案)
财务常用函数
Excel常用的函数计算公式大全(一看就会)精编版
新定义函数-中考新题型
(完整版)excel基本常用函数公式大全
相关主题
文本预览