递归论

1递归论

recursion theory

数理逻辑的重要分支之一，研究解决问题的可行的计算方法和计算的复杂程度的一门学科。

解决某一类问题的计算方法又称算法。算法是个古老的数学概念。16世纪R.笛卡尔创造的解析几何就是用代数来

解决几何问题的一种典型的算法。但数学中有一些问题长期找不到解决的算法。人们怀疑根本不存在这种算法。为了证明这一点，必须对算法给出精确的定义。20世纪30年代K.哥德尔提出了算法的一种精确定义，S.C.克林据此定义了递归函数。与此同时，A.M.图灵用图灵机（一种理论计算机）来描述算法，并且证明图灵可计算的函数与递归函数等价。图灵机使人们普遍接受了关于算法的丘奇论题：递归函数是可计算函数的精确的数学描述。

递归函数是用数理逻辑的方法定义在自然数集上的可计算函数。如果自然数的一个n 元集的特征函数是递归函数，就称这个集合为递归集，一个递归函数的值域，称为递归可枚举集。递归集就是算法可判定的集合。递归集都是递归可枚举的，但是存在不是递归集的递归可枚举的集合。递归论的研究使人们把一些长期未解决的问题化为非递归的递归可枚举集，从而严格证明了不存在判定这些问题的算法。这些问题称为不可判定的。

递归论进一步研究不可判定的，也就是非递归的递归可枚举集之间的复杂程度问题。1944年E.L.波斯特提出不可

解度的概念。又给出了相对可计算性的构造方法。这就使人们开始对不可解度进行比较，并研究不可解度的代数结构。这方面出现了有穷损害优先方法、无穷损害优先方法等多种有力的研究手段，出现了许多有趣的研究成果。

对可计算的递归集，也可以研究其计算的复杂性，考虑图灵机上计算的时间，空间，就得到计算时间的长短计算所占空间的多少这两个复杂性。计算复杂性的研究对计算机科学的发展有很大影响和作用。

2递归论

递归论讨论的是从形式上刻划一个运算或一个进程的“能行”性这种直观的观念，也就是从原则上讲，它们能机械地进行而产生一个确定的结果。“能行”的这个概念含有可具体实现的、有效的、有实效的等等意思。法国数学家保莱尔首先在1898年他的函数论教科书中引进了这个词，他把数学的对象局限于能行的对象，这种主张实际上就是“法国经验主义”。因为函数论主要讨论集合、函数、积分等等，从这种观点产生出描述集合论、拜尔函数等概念。

递归论中所讨论的函数是比较简单的。它讨论有效可计算的函数，也就是递归函数。递归函数在历史上曾从不同角度提出来，后来证明它们都是等价的。 1931年秋天，丘奇在普林斯顿开了一门逻辑课，克林和罗塞尔当时作为学生记了笔记。丘奇在讲课中引进了他的系统，并且在其中定义自然数。这就很自然引起一个问题，在丘奇系统中如何发展一个自然数理论。于是克林开始进行研究，结果克林和丘奇得到一类可计算的函数，他们称之为A可定义函数。

1934年春天，哥德尔在普林斯顿做了一系列讲演(克林和罗塞尔记了笔记)。在讲演中，哥德尔引进了另外一套可以精确定义的可计算函数类，他称为一般递归函数。据他讲，他是受了厄布朗的启发得到的。

这时自然出现了一个问题。一般递归函数类是否包括所有能行可计算的函数，它是否与克林与丘奇研究的 A可定义函数类重合。1934年春末，丘奇和哥德尔讨论一般递归函数问题，结果丘奇明确提出他的“论点”，所有直觉上可看成能行可计算函数都是λ可定义函数，于是丘奇花了好几个月反复思考。当时克林表示怀疑，他认为这论点不太可能是对的，他想如果从A可定义函数类用对角化方法可以得出另外一个能行可计算函数，那么它就不是A可定义的。但他又想到这事行不通。不久之后，丘奇和克林在1936年分别发表论文，证明A可定义函数类正好就是一般递归函数类。有了这个有力的证据，丘奇于是公开发表他

的“论点”。

也是在1936年，英国年轻数学家图林发表了另外一篇重要文章，这标志着所谓图林机的产生。在这篇文章中，图林也定义了一类可计算函数，也就是用图林机可以计算的函数。同时，他也提出他的一个论点：“能行可计算的函数”与“用图林机可计算的函数”是一回事。1937年图林证明了用图林机可计算的函数类与可定义函数类是一致的，当然，也就和一般递归函数类相重合。这样一来，丘奇的论点与图林的论点就是一回事。当时许多人对于丘奇的论点表示怀疑，由于图林的思想表述得如此清楚，从而消除了许多人的疑虑，哥德尔就是其中一位。从这时起大家对于丘奇—图林论点一般都抱支持的态度了。

与图林同时，美国数学家波斯特也发表了一篇文章，类似于图林的可计算函数，他的文章过于简短，一直到1943年波斯特才发表了第四个表述，结果证明他的与别人的也都一样。

递归的概念并不难理解，它就是由前面的结果可以递推得到后面的结果。哥德尔等人引进的实际上是一般递归函数，一股递归函数都可以由原始递归函数算出来。

另一个复杂一些的概念称为递归集合S，它的定义是存在一种能行的办法来判断任何正整数n是否属于S。正数数集合是递归的当且仅当它与它在N中的补集都是递归可枚举的。任何无穷递归可枚举集都包含一个无穷递归集。但是，存在正整数的递归可枚举集而不是递归集。

于是波斯特提出问题：是否存在两个递归可按举但是非递归的集合，使得第一个集合相对于第二个是递归的，但第二个相对于第一个却不是递归的。一直到十二年后的1956年，苏联人穆其尼克及美国人弗里德伯格才独立地肯定地解决了这个问题。

苏联数学家马尔科夫在1947年发表《算法论》，首先明确提出算法的概念。但是它同以前定义的递归函数及可计算函数的计算过程都是等价的。这几个定义表面上很不相同，并有着十分不同的逻辑出发点，却全都证明是等价的。这件事看来决非巧合。它表明：所有这些定义都是同一个概念，而且这个概念是自然的、基本的、有用的。这就是“算法”概念的精确的数学定义。大家都接受了这个定义之后，判定问题从我们平时直观的概念也上升为精确的数学概念，判定问题也成为一门数理逻辑的重要分支了。从这时起，判定问题有突飞猛进的发展。

判定问题有了精确的数学表述之后，立即在数学基础乃至整个数学中产生了巨大的影响。因为这时一些不可判定命题的出现，标志着人们在数学历史上第一次认识到：有一些问题是不可能找到算法解的。在过去，人们一直模模糊糊地觉得，任何一个精确表述的数学问题总可以通过有限步骤来判定它是对还是错，是有解还是没有解。找到不可判定问题再一次说明用有限过程对付无穷的局限性，它从另外一个角度反映了数学的内在固有矛盾。

怎样得到这些结果的呢？丘奇的论点发表之后，不难看出存在不可计算的函数，也就是非一般递归的函数。因为所有可能不同的算法共有可数无穷多(粗浅来讲，算法都是用有限多个字来描述的)，可是所有数论函数的集合却是不可数的。

不过，头一个明显的不可判定的结果是1936年丘奇得到的。他首先得到与λ可定义性有关的不可判定结果。然后，他把这个结果应用到形式系统的判定问题上，特别他证明，形式化的一阶数论N是不可判定的。也是在1936年，丘

奇证明纯粹的谓词演算也是不可判定的。当时大家的反应是：这种不完全性的范围到底有多广？

甚至于象丘奇这样的数学家，也想找到一条出路能避开哥德尔的结果。比如说，可以采用伺哥德尔所用的系统完全不同的其他的特殊系统。一旦算法的精确定义和丘奇论点出现之后，大家就认识到躲不过哥德尔不完全性定理的影响，可计算性和不完全性这两个概念是紧密联系在一起的。

实际上克林在1936年就证明了(作为丘奇论点的应用)：甚至在能够能行地认出公理和证明的形式系统中，哥德尔的定理仍然成立。消去量词方法对许多理论行不通。一般的判定问题是试图找出一个能行的步骤，通过这个步骤可以决定什么东西具有某种指定的元数学特征。

在纯粹逻辑演算的元理论中，有最明显的一类判定问题：对于给定的演算和给定类的公式，求出一个步骤，能够在有限多步内判定这类的任何特殊公式是否可以形式地推导出来。有些情形、问题已经得到肯定的解决，在另外一些情形，答案是否定的，可以证明不存在这样一个步骤。这种否定的证明，特别对于数学理论，很大程度上依赖于递归论。

最早明确提出的数学判定问题是希尔伯特第十问题。他在1900年国际数学家大会上提出了著名的二十三个问题，其中第十个问题是：给定一个有任意多未知数的、系数为有理整数的丢番图方程，设计一个步骤，通过它可以经有限步运算判定该方程是否有有理整数解。这个到1970年才被否定解决的问题不仅解决了一个重大问题，而且解决问题过程中所得到的工具和结果对数理逻辑和数学发展有着极大影响，比如表示素数的多项式，尤其与整个数理逻辑有关的是得出了一个更确切的哥德尔不完全性定理。

现在我们来看希尔伯特第十问题，为了清楚起见，我们考虑多项式方程，看看一般的多项式丢番图方程的次数和未定元的数目是否可以降低。

1938年斯科兰姆证明，任何丢番图方程的次数可约化成次数小于等于4的方程；1974年马蒂亚谢维奇和罗滨逊证明未定元的数目可约化成小于等于3。对于齐次方程，阿德勒在1971年证明，任何齐次方程可以能行地约化为二次齐次方程组，从而等价于一个四次齐次方程。对于一次方程早就有具体方法解丢番图方程了。对于任意多未定元的二次方程，1972年西格尔也找到一个算法。四次方程不能判定，三次方程尚不知道。

解决丢番图方程解是否存在的判定问题的方法是引进丢番图集。我们把丢番图方程的变元分成两有一组解。每个丢番图集合是递归可枚举集。1970年，苏联大学生马蒂亚谢维奇证明了每个递归可枚举集也是丢番图集合。这样一来，由于存在不可判定的递归可枚举集，所以存在一些特殊的丢番图方程，使得对是否有解的判定问题不可解。当然对一般丢番图方程的判定问题就更不可解了。

另一个判定问题是半群和群论中字的问题，半解问题是挪威数学家图埃在1907年首先提出来的。问题是对于一个半群，如果给定它的有限多生成元和有限多关系，那么能否找到一个方法来判定任何一个特殊的字是否等于单位元素。1947年，波斯特否定地解决了这个问题。

群论中字的问题更为重要，它是在1911年由德恩首先研究的，一直到1955年才由苏联数学家诺维科夫否定解决。这些结果给数学家指明了新的方向：不要妄图去解决一大类问题。不过对于更窄的一类的对象比如一类特殊的群，群的字问题是可解的。

3递归论

数理逻辑的一个分支。它是一门研究递归涵数及其推广的学科。递归函数是数论函数的一种，其定义域与值域都是自然数集。只是由于构作函数方法的不同而有别于其他的数论涵数。将定义域推广到不限于自然数集时，便是所谓广义的递归函数。

历史递归论这门学科最早可以追溯到原始递归式的使用。古代人以及现代的儿童对加法及乘法的理解，实质上就是使用原始递归式。但直到17世纪，法国学者B.巴斯加尔才正式使用与递归式密切相关的数学归纳法。19世纪德国数学家R.戴德金德和意大利的G.皮亚诺正式使用原始递归式,以定义加法与乘法,从而发展了整个自然数论。1923年，T.司寇伦提出并初步证明一切初等数论中的函数都可以由原始递归式作出，即都是原始递归函数。1931年，K.哥德尔在证明其著名的不完全性定理时，以原始递归式为主要工具把所有元数学的概念都算术化了。原始递归函数的重要性遂受到人们的重视，人们开始猜测，原始递归函数可能穷尽一切可计算的函数。但是，德国数学家W.阿克曼的非原始递归的可计算函数的出现，否定了这个猜测，同时也要求人们探讨原始递归函数以外的可计算函数。1934年，哥德尔在J.赫尔布兰德的启示之下，提出了一般递归函数的定义；美国的S.C.克利尼则于1936年证明了这样定义的一般递归函数和A.丘奇所定义的λ可定义函数是相同的，并给出了几种相等价的定义。这样的一般递归函数后来被称为赫尔布兰德-哥德尔-克利尼定义。1936年，丘奇、A.M.图林各自独立地提出一个论点，即凡可计算的函数都是一般递归函数，这就把递归函数论与能行性论紧紧地结合起来，从而使递归函数的应用范围大大地扩展了（见能行性与一般递归）。关于递归函数本身的进展主要在于定义域的推广,从而得到递归字函数、a递归函数和递归泛涵等等。

基本内容递归论研究的函数主要包括本原函数、原始递归函数、递归半函数和递归全函数或称一般递归函数、可摹状函数等等。

本原函数处处有定义的函数叫做全函数，未必处处有定义的函数叫做半函数或部分函数。最简单、最基本的函数有三个，即①零函数，O(x)=0,其值永为0；②广义幺函数或射影函数,Imn(x1,…,x m) =x n(1≤n≤m)；③后继函数，Sx(=x+1)。这三个函数的合称就叫做本原函数。

要想由旧函数而作出新函数，必须使用各种各样的算子以及叠置。叠置又名复合或代入，它是最简单、最重要的构造新函数的方法。其一般形式是：由一个 m元函数f与 m个 n元函数g1，g2，…，g m而造成新函数f

【g1(x1,…,x n),g2(x1,…,x n),…,g m(x1,…,x n)】,后者亦可记为f(g1,…,g m)(x1,…,x n)。最常见的造新函数的算子是原始递归式。具有n个参数的原始递归式如下：

只有一个参数的原始递归式为：

其特点是：不能由A、B两函数而直接计算新函数的一般值f(u,x)，而只能依次计算f(u,0),f(u,1),f(u,2),…。但只要依次计算，必能把任何一个f(u,x) 值都算出来。这就是说，只要A、B为全函数且可计算,则新函数f也是全函数且可计算。

原始递归函数由本原函数出发，经过有限次的叠置与原始递归式而作出的函数叫做原始递归函数。由于本原函数是全函数且可计算，故原始递归函数也是全函数且可计算。原始递归函数所涉及的范围很广，在数论中所使用的数论函数全是原始递归函数。阿克曼却证明了一个不是原始递归的可计算的全函数。经过后人改进后，可表述为如下定义的函数：

这个函数是处处可以计算的。任给 m,n值,如果m为0,可由第一式算出；如果m不为 0而n为0,可由第二式化归为求g(m,1)的值，这时第一变目减少了，如果m,n均不为0，根据第三式可先计算g(m,n-1)(设为A),再计算g(m-1,A)，前者g的第二变目

减少而第一变目不变,后者则第一变目减少。这样一步步地化归,最后必然化归到第一变目为0，从而可用第一式计算。此外，对任一个一元原始递归函数f(x),都可找出一数a使f(x)

原始递归式的推广，可得到下列有序递归式或半递归式：

它与原始递归式的不同点，在于它不是把f(u,Sx)的计算化归于f(u,x,)的计算，而是先化归于f(u,g(u,Sx))的计算,然后化归于f【u,g(u,g(u,Sx))】的计算(可写成f(u,g娾Sx))，再化归于f(u,g咺Sx)的计算，等等。如果有一个m使得g嚲Sx =0即函数g u在Sx处归宿于0，那末最后化归的f(u,g嚲Sx)的计算,将由第一式知f(u,0)=A(u)，依次逐步倒退便可以计算f(u,x)了。如果任何 m均使得g嚲Sx≠0，即函数g u在Sx处不归宿于0,将导致永远化归下去而得不到结果。这样，不但不能计算f(u,Sx)，而且它本身根本没有定义。由此可见,即使A、B与g是处处有定义且可计算的，而由半递归式所定义的函数未必是全函数，也可能是半函数。但只要有定义的地方，即g u归宿于0的地方，就必能计算。

递归半函数和递归全函数从本原函数出发经过有限次的叠置与半递归式构成的函数叫做递归半函数或递归部分函数，也叫做半递归函数或部分递归函数。这里所提到的“半”、“部分”不是限制“递归”而是限制“函数”的。如果作出的函数是全函数，即其中的g u是处处归宿于 0的，便叫做递归全函数也叫做一般递归函数。递归半函数的特点是，它可能没有定义从而没有值，但只要有值必然可以计算。一般递归函数的特点是，它必处处有定义而且处处可以计算。当递归半函数没有定义时，一般是不知道的。这样，即使把f(u,Sx)化归于f(u,g u,Sx)，再化归于f(u,g u2Sx),…,如此永远计算下去,也始终得不到其值,并且始终不知道它没有值。但如果另有办法判定递归半函数是否有值,即是否有定义,情况便大不相同。凡是能够判定某个递归半函数是否有值的，该递归半函数叫做潜伏递归函数。对潜伏递归函数永可在有限步内得出其值，或知道它没有值，而与一般递归函数相同。

另一个重要的构造新函数的方法是造逆函数，例如由加法造减法，由乘法造除法等。设已有函数f（u,x）（只写一个参数u）就x解方程f(u,x)=t可得x=g(u,t)，这时函数 g叫做f（作为 x的函数）的逆函数，可记为g(u,t) = f層(t)，至于解一般的方程f(u,t,x) =0而得x=g(u,t),可以看作求逆函数，即三元函数f的逆的推广，解方程可以看作使用求根算子，又叫摹状算子。f (u,t,x)=0的最小x根，记为u∝【f(u,t,x) =0】,但当该方程没有根时,则认为u∝【f(u,t,x) =0】, 没有定义。因此，即使f(u,t,x)处处有定义且可计算，但使用摹状算子后所得的函数u∝【f(u,t,x) =0】仍不是全函数，可为半函数。且只要它有定义,那就必然可以计算。如果f(u,t,x)本身就是半函数，则u∝【f(u,t,0) =0】的意义是:当f(u,t,x)可计算且其值为0,而x＜n时f(u,t,x)均可计算，且其值非0,则u∝【f(u,t,x) =0】指n。此外的情况均作为无定义看待。例如，f(u,t,x) =0根本没有x根，或者虽然知道有一根为n，但f(u,t,n-1)不可计算，这时u∝【f(u,t,0) =0】都作为没有定义。

可摹状函数由本原函数出发，经过有限次叠置原始递归式与摹状式而构成的函数叫做可摹状函数。可摹状函数一般是部分函数，当摹状算子处处有定义时，它才是全函数。但不管是否全函数，凡可摹状函数有定义的地方都是可计算的。已经证明，可摹状函数与递归半函数是相同的，可摹状的全函数与一般递归函数也是相同的。凡可摹状函数都可以构作一个图林机器（见图林机器理论）计算它，使得当函数有定义时，相应的图林机器必能终止计算并给出其值；当函数没有定义时，相应的机器或者停止并给出没有定义的信号，或者永不停止。由于递归函数可以与其性质这样不同的函数类相等价,因此丘奇和图林同时提出:可计算函数类恰好是递归函数，可计算的半、全函数分别是递归半、全函数。他们的这个论点现已受到数理逻辑学界的一致赞同，并被当作能行性理论的一个基础。

图林机器理论

英国数学家A.M.图林在1936年提出的一个理想的机器的理论。这种理想的机器，后来被命名为图林机，它的结构非常简单，元件的功能非常弱。对这种机器可描述如下：有一条一端或两端无限伸长的纸带，上面划成一个一个的方格，方格内可印有字母或为空白。有一个元件叫做读头,它每次都注视一个方格,辨认其内容。读头可以不断地处在不同的状态中，也可以说接受不同的指令，然后根据读头注视方格的内容以及当时读头所处的状态或所接受的指令，决定机器当时的动作。动作分以下三种：读头左移(L)而注视左方一格；读头右移(R)而注视右方一格;读头印刷(P)一新字母或抹去原有字母，如果用S0表示空白，则抹去原字母可以说是印刷S0；动作完了以后读头再转入一新状态，即接受一新指令。就图林机而言,方格内所能印的字母是有限个的固定的,设为S0，S1，…，S m（S0表示空白），机器可能处的状态或接受的指令也是固定的、有限的。设为q0，q1，…q n，

并规定q1为开始状态，机器开动时便处在状态q1中；又规定q0为终止状态，而当机器处在状态q0时，便不再动作了。该机器的每个状态及其功能可刻划如下：

q i aLq j，q i aRq j，q i abq j。其意是,处在状态q i的读头,如果注视格内的字母为a,则读头左移或右移,或印字母b，然后转入状态q j。但q0则没有任何动作。由于引入终止状态q0, 并要求除q0以外的任何状态q j对注视格内任何字母都应有所动作, 这样即使没有任何动作而转入q j，也能写成q i aaq j。

每个图林机器都可用字母表A={S0，S1，…，S m}与状态动作表P＝{q i S a H b q j}（这里H b为L、R或一字母）来刻划，如果字母数为m+1，状态数为n+1，则状态动作表共(m+1)n行且q0不出现在最左端。虽然定有终止状态q0，但如果从q1开始，永远转不到终止状态，则图林机必永远运转而不停止。凡对任何开始字均能停止的机器叫做必停机器，未必停止甚至可能永远运转的叫做一般的图林机。

在图林机上,未印字母的格叫做空格,印有字母的格叫做实格。如果规定纸带的两旁必须全是空格，设最左的实格到最右的实格之间所印的字母依次序为a1,a2,…，a n，其间若有空格，则用字母S0表示之，这就使该纸带所表示的字为a1，a2，…a n。如果读头恰好注视了其最左实格a1，则说读头标准注视了a1a2…a n。例如，有一图林机器Ц，它从标准注视字P开始（状态为q1），根据机器的状态动作表而继续变动，直到出现终止状态q0为止，如果这时纸带上所表示的字变成了Ｑ，就表明机器Ц把P改造为Ｑ,记为Ц(P)=Ｑ；如果从标准注视P开始后，继续运转永远达不到终止状态，从而机器也永不结束，则表明Ц对P改造无结果，亦即Ц(P)无意义。

为了使用图林机计算数论函数，须用图林机器字母表上的字表示自然数。为此，最简单的方法是使用两个字母{S0，S1}，S0表示空白，S1相当于一竖,凡两旁为空格而中间有n+1个相邻实格的便表示数n，即用一个实格表示0,两个实格表示1等等。要表示三元数组(a,b,c)可使用一个空格、a+1个实格,一个空格、b+1个实格,一个空格、c+1实格和一个空格。设机器Ц从标准注视x（或标准注视x1，x2，x3）开始，根据状态动作表而依次运转，直到Ц把x变成?（x）,（把x1，x2，x3变成g(x1，x2，x3)）为止，就说机器Ц计算了函数?(x)(函数g(x1，x2，x3))。但如果?(x)(g(x1，x2，x3)) 无定义，则要求Ц永不停止或虽停止而给一个表示无结果的信号，例如，S0，S1以外的任何信号。

表面看来,图林机器的功能是非常弱的。但是,只要提供足够的空间（纸带有足够长）以及足够的时间（步骤足够多），那末它的力量是非常强的，足以代替目前的任何计算机。实际上，任何递归半函数都可以用未必永停的图林机计算，任何递归全函数即任何一般递归函数（见递归论）都可以用永停的图林机计算。反之，凡能用一般图林机器计算的数论函数都是递归半函数，凡能用永停图林机器计算的数论函数都是递归全函数即一般递归函数，两者实质上是一样的。利用图林机器计算递归函数具有很大的方便性。数理逻辑学界一致承认可计算函数与递归函数是相同的，从而一函数是可计算的当且仅当它是可用图林机计算的。

不完全性定理

证明论中的一条重要定理。由K.哥德尔于1931年证明，是数理逻辑发展史上的一个极为重要的定理。

设有一个以皮亚诺自然数论为其子系统的、自身协调的（即不自相矛盾的）形式系统，暂记为U；在形式系统中凡不含自由变元的公式叫做语句；如果语句A和塡A在某形式系统内均不可证，则A就叫做该形式系统的不可判定语句。不完全性定理说，任何一个上述的系统U都必有一个不可判定语句A。依照排中律，A和塡A之间必有一个是真语句，故不完全性定理可改为：任何一个上述的系统U都必有一个真语句是不能推出的。如果一个系统对任何语句A能够推出A或推出塡A，则这个系统叫做完全系统，这样不完全性定理又可改述为：任何一个上述的系统U必是不完全的。

在证明不完全性定理时,主要是使用算术化方法,即先把形式系统中所使用的各符号都逐一给以一个自然数编号，然后依次对各公式也给以一个编号，再后又对各公式序列，例如证明中所使用的公式序列给以一个编号。凡属编号必须满足下列条件，即给出符号或公式或公式序列后，可以唯一地决定其编号。反之，当给出一个自然数后，则可以决定其是否用作编号，如果是，就可以唯一地决定其是符号的或者是公式的，还是公式序列的编号。满足这种条件的编号，叫做哥德尔编号。利用编号可以把有关形式系统的各性质用算术函数算术公式来表示。例如，可以作出一个算术公式prov(a,b)，使得prov(a,b)成立当且仅当编号为a的公式序列是对编号为b的公式的证明,这也表明证明关系是可以算术化的。有了这些（以及别的）算术函数算术公式后，就容易作出不可判定语句。

根据不完全性定理的证明过程，还可以推得下列结论：如果包含皮亚诺自然数论为子系统的形式系统U是协调的，则表示

" U是协调的"这个事实的算术公式不可能在系统U内证明，这个结果叫做第二不完全性定理。它也是证明论中很重要的结果。

虽然证明关系、可证性、协调性等等是可以算术化的，但由不完全性定理却可推得：真假性是不能算术化的，亦即不可能找到一个算术公式tr(a)使得tr(a)成立，当且仅当以a为编号的公式A为真，也就是说,在系统U内下列公式tr(a)凮A（这里a为A的编号）是不可证的。这是不完全性定理的另一内容，它是由A.塔尔斯基首先给出的（见不可定义性理论）。

排中律

传统逻辑基本规律之一。它通常被表述为A是B或不是 B。传统逻辑首先把排中律当作事物的规律，意为任一事物在同一时间里具有某属性或不具有某属性，而没有其他可能。排中律同时也是思维的规律，即一个命题是真的或不是真的，此外没有其他可能。排中律还是关于认识活动的规范性规律，意为任何人不应同时否认一个命题(A)及其否定(并非A)，即对一个命题及其否定不能持两不可之说。排中律还被当作逻辑语义的规律，即任一语词或语句同一上下文中应表达某一思想或不表达这一思想。作为后两种规律，也叫做排中律的要求。排中律并不排除具体事物在其发展过程中有中间环节、以及有多种状态和各种可能性。

在现代逻辑中，A'∨塡A（读作：A或非A）,是排中律在命题逻辑中的体现;凬x(F(x)∨塡F(x))（读作:对任何个体x而言，x有性质F或没有性质F），是排中律在谓词逻辑中的体现。由于构造逻辑不承认现实世界里存在着实无穷，只承认无穷是一个过程，因此，在该逻辑中，涉及无穷对象时排中律不成立；同时，用反证法证明存在命题，也不是一种有效的证明方法。

谓词逻辑-正文

形式逻辑的最根本部分，也是最基本的逻辑系统或理论。在谓词逻辑中，除研究复合命题的命题形式、命题联结词的逻辑性质和规律外，还把命题分析成个体词、谓词和量词等非命题成分，研究由这些非命题成分组成的命题形式的逻辑性质和规律。谓词逻辑把命题逻辑作为子系统，但为了研究方便，同时也由于它具有某些重要的特殊性质，命题逻辑通常又作为一个独立的系统先研究，而在谓词逻辑部分则集中研究由非命题成分组成的命题形式和量词的逻辑性质与规律。只包含个体谓词和个体量词的谓词逻辑称为一阶谓词逻辑，简称一阶逻辑，又称狭义谓词逻辑。此外，还包含高阶量词和高阶谓词的称为高阶逻辑。谓词逻辑也分为经典的谓词逻辑和非经典的谓词逻辑，后者包括作为子系统的非经典的命题逻辑。经典的一阶谓词逻辑是谓词逻辑的基本部分。第一个完整的谓词逻辑系统是G.弗雷格在1879年建立的。K.哥德尔等人系统地研究了谓词逻辑的元逻辑问题，证明了重要的定理。

命题形式最简单的命题，即所谓原子命题，都可以分析为个体词和谓词两类成分。例如,在“5是素数”、“7大于3”这两个命题中，5、7和 3是个体词，“是素数”、“大于”是谓词。在逻辑中，一个论域中的元素称为个体，个体词是表示个体的符号；表示某个论域中的一个特定个体的符号称为个体常项或个体常元，个体常项也就是它所表示或指称的那个个体的名字；不表示某一确定论域中的特定个体的个体词，称为个体变项或个体变元，用符号x,y,z和x1,y1,z1,…表示；个体变项取任一论域中的任一个体为值。谓词是表示个体的性质和个体之间关系的符号。个体的性质也称一元关系，表示个体的性质即一元关系的称为一元谓词。两个个体之间的关系称为二元关系，n个个体之间的关系称为n元关系。表示二元关系的为二元谓词，表示 n元关系的为 n元谓词。如“是素数”就是一元谓词，“大于”是二元谓词,“在…之间”是三元谓词。表示某一论域中的特定的性质或关系的称为谓词常项或谓词常元,“是素数”等都是谓词常项。不表示某一确定论域中的特定性质或关系的称为谓词变项或谓词变元。谓词变项用符号F,G,H和F1，G1，H1，…表示。谓词变项也分为一元的、二元的、…,n元的，等等。谓词变项的元数可以明晰地标示出来，如F1表示F是一元的，G2表示G是二元的，但也可以不这样做。在一公式中，一个谓词变项后面跟的个体变项的个数,就表示这个谓词变项的元数。例如,F(x)中F是一元的，G(x,y)中G是二元的，H(x1,x2,…,x n)中H是n 元的。同一个符号，比如F，在不同的公式中可以表示不同元数，但在一个复杂的公式中，同一符号的几处出现是同一个谓词变项。应用个体变项和谓词变项,“5是素数”、“7大于3”这两个原子命题的形式可分别表示为F(x)和G(x,y)这两个公式。一般地陈述n个个体间有某关系的原子命题的形式，用一个 n元谓词变项后面跟n个个体变项的公式表示,该公式为: F(x1,x2,…,x n)。表示原子命题的形式的公式称为原子公式。

除了个体词和谓词，组成命题的成分还有量词。量词是命题中表示数量的词，它分为全称量词和存在量词。例如，在“所

有阔叶植物是落叶植物”、“有的水生动物是肺呼吸的”这两个命题中的“所有”、“有的”都是量词,其中前者是全称量词,后者为存在量词。在汉语中,“所有”、“一切”、“凡”等表示全称量词,“有的”、“有”、“至少有一”等表示存在量词。全称量词是在符号凬后跟一个个体变项(比如x),表示为(凬x)，读作：“对任一x”，“所有x”。存在量词在符号ヨ后跟一个个体变项（比如x），表示为(ヨx)，读作：“有一x”，“存在一x”。在一个公式前面加上量词，称为量化式,如(凬x)F(x)和(ヨx)F(x)，就分别称为全称量化式和存在量化式。(凬x)F(x)表示“所有x，x是F,即一切事物都是F”；(ヨx)F(x)表示“有一x,x是F,即有一事物是F”。

从原子公式出发，应用量词和命题联结词塡、∧、∨、→和凮就可以构造出表示各种复杂的命题形式的公式。例如，“所有阔叶植物是落叶植物”这一命题形式的公式为：

(凬x)(F(x)→G(x))；

“有的水生动物是肺呼吸的”这一命题形式的公式为：

(ヨx)(F(x)∧G(x))。

“一切自然数有大于它的自然数”、“每人都有一个父亲”这类命题，具有更复杂的公式，即：

(凬x)(F(x)→(ヨy)(F(y)∧G(x,y)))

谓词逻辑中的这种命题形式比命题逻辑更为复杂，其数量也非常多，相应的公式的数目是无穷的。

公式的解释谓词逻辑的公式可以分为普遍有效的、可满足的和不可满足的三类。普遍有效的公式表达谓词逻辑的规律。为了刻划公式的普遍有效性和可满足性，首先需要说明对公式的解释。一个解释由一个非空个体域D和一个赋值υ组成，对每一个体变元x,υ都赋与D中的一个个体为值，如果对个体变元x1,x2,…,x n,υ分别赋以D中的个体a1,a2，…,a n为值，υ对个体变元的n元组（x1,x2,…,x n）所赋之值即为(a1,a2,…,a n)；对n元谓词变元F,υ赋与F的值是D中的一个n元关系。令A为一个原子公式F(x1,x2,…,x n)，υ(A)即υ【F(x1,x2,…,x n)】的值可以为1(即真),也可以为0（即假）。如果 (x1,x2,…,x n)所赋之值 (a1,…,a n)属于F所赋之值，υ(A)的值为1,否则为0。υ(A)的值为 1，也就是公式A在此解释下是D中的真命题。每一赋值υ也给出一个真值赋值。令A、B是任意的公式。υ(塡A)的值为1,当且仅当υ(A)的值为0。υ(A∧B)的值为1,当且仅当υ(A)和υ(B)的值都为1。υ(A∨B)的值为1,当且仅当υ(A)或υ(B)的值为1。υ(A→B)的值为1, 当且仅当υ(A)的值为0或υ(B)的值为1。υ(A凮B)的值为1，当且仅当υ(A)和υ(B)的值相同。υ(凬x)A(x)的值为1,当且仅当，设A的赋值已经给定, 对每一D中的个体a，A(a)的值为1,即(凬x)A(x)是真的,当且仅当, 设A的赋值已给定，对于D中的每一个体a，A(a)真。υ(ヨx)A(x)的值为1, 当且仅当, 设A的赋值已给定, 有 D中的个体a，使得A(a)的值为1。

一个公式 A称为可满足的，如果有一不空的个体域D和赋值υ，在此解释下，A为真。

一个公式 A称为普遍有效的，如果对任一解释，也就是对任一不空的个体域和任一赋值，A都真。A普遍有效也就是A常真，记为F A。

显然，一个公式 A是普遍有效的，当且仅当，它的否定塡 A是不可满足的。一个不可满足的公式是常假的，也称为矛盾的。

这里所说的个体域、解释、赋值、真假、普遍有效性和可满足性等概念，都是语义概念。

公理系统谓词逻辑的普遍有效的公式为数无穷，在一定意义上它们都是逻辑规律。为了系统地研究这类规律,需要对它们作整体的考虑,将它们总括在一个系统之中。谓词演算或者一阶谓词演算就是这样的系统。谓词演算是把谓词逻辑公理化和形式化而建立的形式系统。按照对作为演算出发点的初始符号、公理和变形规则的不同挑选，可以建立不同的谓词演算系统。在初始符号中有符号=的，称为带等词的一阶谓词演算，等词=是一个谓词常元；不带等词的系统就称为（一阶）谓词演算。构成一个谓词逻辑的公理系统的基本要素有：初始符号、形成规则、公理和变形规则等。对此，可以从一个不带等词的系统 F得到说明。F的初始符号，包括个体变元、谓词变元、联结词和量词以及技术性符号四类。个体变元符号的小写拉丁字母为：x,y,z,x1,y1,z1,x2,…；谓词变元符号为大写拉丁字母，即：F,G,H,F1,G1,…。在原则上,对每一n≥1，应分别列出n元谓词变元，如：F1,G1,H1,…;F 2,G 2,H 2,…；等等。不过,省去上标1,2,…,n，在实践上不会产生混乱。联结词和量词符号为：塡、→、凬；技术性符号为括弧（，）和逗号，。

形成规则规定怎样的符号序列或符号的组合是F中的合式公式。合式公式经解释后是有意义的。用来描述和讨论F系统的语言即元语言的符号有：小写希腊字母α，α1，…,αn，δ表示任意的个体变元；f n表示任意的n元谓词变元;大写拉丁字母X,Y 表示任意的符号序列。这些符号称为语法变元。F的形成规则有4条：①如果f n是一n元谓词变元,α1,…,αn是个体变元，则

f n(α1,…,αn)是一合式公式；

②如果 X是合式公式，则塡X是合式公式。如果X、Y 是合式公式，则(X→Y)是合式公式；

③如果X是合式公式，α是个体变元，则(凬α)X是合式公式；

④只有适合以上①～③的是合式公式。合式公式简称公式。用字母A,B,C表示任意的公式。A,B,C也是语法变元，属于元语言。

量词的辖域指一量词后的最短公式，表示一个量词在一个公式中的作用范围。例如,在公式 (凬y)【(凬x)F(x)→G(y)】中，(凬x)的辖域是公式F(x)，(凬y)的辖域是公式【(凬x)F(x)→G(y)】。变元α在一个公式A中的某次出现是约束出现，如果α的这次出现是在(凬α)中或（凬α）的辖域中；α在一公式 A中的某次出现是自由出现，如果α在A中的这次出现不是约束的。例如，在公式(凬y)【(凬(x)F(x)→G(y)】中, x和y的两次出现都是约束的；在公式【(凬x)F(x)→G(y)】中,x的两次出现是约束的,y的唯一一次出现是自由的。个体变元α可以在A中既有约束出现又有自由出现, 例如, (凬α)F(x)→G(x)。如果个体变元α在A中自由或约束出现,它在A中就是自由或约束出现的。δ对A(α)中的α是自由的, 如果在A(α)中α的自由出现不在(凬δ)的辖域中。

F的公理有无穷多条，并由5个公理图式给出，每个图式都代表无穷多条公理。公理图式用语法变元陈述这5个公理图式是：

① A→(B→A);

②【A→(B→C)】→【(A→B)→(A→C)】;

③ (塡A→塡B)→(C塡A→B→A);

④ (凬α)(A→B)→【A→(凬α)B】，如果α在A中没有自由出现。

⑤ (凬α)A(α)→A(δ),如果δ对A(α)中的α是自由的。

该图式的A(α)是一合式公式,α是在其中有自由出现的个体变元，A(δ)则是用δ代替α在A(α)中的每处自由出现而得的公式。

根据④以下的公式都是公理：

(凬x)【F(y)→G(x,y)】→【F(y)→(凬x)G(x,y);

(凬x)【(凬x)F(x)→F(y)】→【(凬x)F(x)

→(凬y)F(y)】。

但公式(凬x)【F(x)→G(x,y)】→【F(x)→(凬x)G(x,y)】却不是公理，因为它不符合图式④中关于x在F(x)中没有自由出现的规定。

根据图式⑤，以下的公式都是公理：

(凬x)F(x)→F(y);

(凬y)G(y)→G(y);

(凬x)F(x,y)→F(y,y);

(凬y)【F(y)→G(x,y)】→【F(y)→(凬y)G(y,y)】。

但 (凬x) 【F(x)→(凬y)G(x,y)】→【F(y)→(凬y)G(y,y)】不是公理。因为该公式的y对F(x)→(凬y)G(x,y)中的x不是自由的，不符合图式⑤的条件。

变形规则也称推理规则。变形规则的陈述，除使用语法变元，还使用语法符号儱。符号儱在一个公式的前面，表示紧接在儱后面的公式是定理。例如，儱A,表示A是定理。F的变形规则有两条，即：①分离规则,从A和A→B，可以推出B；②概括规则,从A,可以推出(凬α)A。

F中的一个证明，指一有穷公式序列A1,A2, …, A n，其中的每一A k(k=1,2,…,n)或者是一个公理，或者是由公式A i和A j(i,j j=A i→A k)应用分离规则而得，或者是由公式A j(j k=(凬α)A j。一个证明也可以说是此证明的最后一个公式的证明。F中的一个公式 B是F的定理，如果B有一个证明，或者说，存在一个证明 A1,A2,…，A n，这个证明的最后一个公式A n即是 B。根据这个定义，每一公理都是定理，即单独一个公理构成自身的一个证明。一个公式 B，如果存在它的一个证明,就说B是可证明的。一个公式是定理，当且仅当它是可证明的。一个公式B是由公式A1,A2,…,A m可推演的,记作：A1,A2,…,A m儱B。如果存在一个公式的有穷序列 C1,C2,…,C n，其中每一 C k(k=1,…,n)或者是一公理, 或者是A1,…,A m中的一个，或者是由C i、C j(i、j j=C i→C k)应用分离规则而得,或者是由C j(j n是B。如m=0，则儱B当且仅当B是一定理。

F的初始符号中不包括∧、∨、凮、ヨ这几个符号,但它们可以通过定义引入，即：

(A∨B)定义为(塡A→B)；

(A∧B)定义为塡(A→塡B)；

(A凮B)定义为(A→B)∧(B→A)；

(ヨα)A定义为塡(凬α)塡A。

关于谓词演算F,只涉及符号、符号序列、符号序列的变换等等，完全没有涉及符号、公式等的意义。这种不涉及符号、公式等的意义的研究，是语法的研究。定理、可证明性等概念，都是语法概念。而对符号、公式的解释,以及关于公式和它的意义的关系等等,都属于语义的研究。关于F的解释称为标准解释或标准语义。在这个标准解释下,F的公理图式以及公理本身都是普遍有效的，而变形规则具有保持普遍有效性的性质，即从普遍有效的公式经应用变形规则而得到的公式也是普遍有效的。所以，F的定理都是普遍有效的。

谓词演算F有许多元逻辑定理或称元定理。不过元定理并不是F中的定理，而是关于F的定理，是对F这个系统的某些重要性质的研究的结果。重要的元定理有 3个：①可靠性定理，表述为：如果儱A，则喺A。这条定理表明F的定理都是普遍有效的。

②一致性定理。这条定理表明F是一致的，即不存在一个公式A，A和塡A都是定理。

③完全性定理，它表述为：如果喺A，则儱A。该定理表明,F在凡普遍有效的公式都是定理这一意义上是完全的。

可靠性定理表明，谓词演算F对演绎推理形式的反映是可靠的。设A是一个推理的前提的命题形式，B是结论的命题形式，这个推理的形式就是 A→B。F的定理都是普遍有效的,这就意味着F只反映有效的推理形式。而完全性定理则表明,F对有效推理的形式的反映是完全的。设A→B是一个有效的推理的形式,当A真时B一定真,A→B是普遍有效的，因而是F的定理。这两个定理也表明,对F来说，语法和语义是一致的、相符合的。也就是说,可证明性和普遍有效性是相符合的，一个公式是可证明的或是定理，当且仅当它是普遍有效的。

自然推理系统除了F这样的形式系统，谓词逻辑还可用另一种方式系统化，即建立自然推理系统。例如，有一个与F 相应的自然推理系统，其初始符号和形成规则与F相同。在该系统的规则中,A、B是任意公式，A(α)、A(δ)也和 F A1,…,A n喩A1(i=1,…,n)。这是肯定前提规则；

(τ)如果г喩Δ喩（Δ不空）,则г喩A。这是演绎推理传递规则；

(→)如果г，塡A喩B，并且г，塡A喩塡B，则г喩A。这是否定词消去规则；

(→﹣)A→ B,A喩B。这是蕴涵词消去规则；

(→﹢)如果г,A喩B，则г喩A→B。它是蕴涵词引入规则；

(凾)(凬α)A(α)喩A(δ)，这是全称量词消去规则；

(刄)如果г喩A(α),α在г中的公式中没有自由出现，则г儱(凬α)A(α )。这是全称最词引入规则。

规则(τ)表示，从г能推出Δ,从Δ能推出A，则从г能推出A,推出关系是传递的。规则(→)也称反证律。在这一自然推理系统中，符号∨、∧、凮和ヨ也可以通过定义引入，并导出相应的规则。

关于这个自然推理系统，有如下的结果：如果 A普遍有效,即喺A，则喩A；并且，如果喩A，则A普遍有效。在F和这个自然推理系统之间，有如下关系：对任一公式A，如果A在F中可证,即儱A，则喩A；反之，如果A在自然推理中不需任何前提就能推出，即喩A，则 A在F中可证。这个自然推理系统也和F一样具有可靠性、一致性和完全性。

形式逻辑

形式逻辑（formallogic）是研究演绎推理及其规律的科学，包括对于词项和命题形式的逻辑性质的研究、思维结构的研究与必然推出的研究，它提供检验有效的推理和非有效推理的标准。它总结了人类思维的经验教训，以保持思维的确定性为核心，用一系列规则、方法帮助人们正确地思考问题和表达思想，是人们认识世界和改造世界的必要工具，是人类认识发育到一定阶段后出现思维方法。康德首先使用了这个术语。

形式逻辑-内涵

形式逻辑的研究方法形式逻辑研究的推理中的前提和结论之间的关系，是由作为前提和结论的命题的逻辑形式决定的，而命题的逻辑形式（简称命题形式）的逻辑性质则是由逻辑常项决定的。要弄清逻辑常项的性质，系统地揭示推理规律，就要通过建立逻辑演算，进行元逻辑的研究。研究元逻辑的方法是形式化的公理方法。

形式逻辑的规则同一律、矛盾律、排中律和理由充足律。这四条规律要求思维必须具备确定性、无矛盾性、一贯性和论证性。形式逻辑的缺陷与超越，人的思维由其内容与形式构成。而形式逻辑企图在不考虑思维内容的情况下通过把握思维的形式来了

解思维的全貌，这显然是不可能的。这种企图遭遇了东西方两方面的批判。

名家没有像黑格尔那样依照内容去建立逻辑，而是通过操纵内容把形式逻辑搞垮了就满意了。他们以辩论为乐，把对手说糊涂了，他们就高兴了。于是，他们就不能避免诡辩的诱惑。黑格尔则在批判形式逻辑的时候同时着手建设新的逻辑。另外，就批判对象而言，当时中国的形式逻辑的发育程度还不高，其主张带有破碎性，这就导致名家在批判过后所能给出的是一个个孤立的诡辩命题。而黑格尔所批判的形式逻辑是系统的，若要使批判成功，则需要找到一种同样系统的逻辑来替代之，而不是玩弄几个命题。自然，黑格尔的辩证逻辑也是也还有缺陷。比方说绝对精神只否定自身两次——为什么没有第三次否定呢？此外由于对形式逻辑批过了头，导致辩证逻辑停留在纯粹思辨的层面上。这些唯心辩证法所遗留的问题，终于在唯物辩证法这里得到了解决。

形式逻辑-发展历程

形式逻辑已经历了2000多年的历史，19世纪中叶以前的形式逻辑主要是传统逻辑，19世纪中叶以后发展起来的现代形式逻辑，通常称为数理逻辑，也称为符号逻辑。

传统逻辑通常把命题分为直言命题、选言命题和假言命题，并研究这几种命题的形式和推理形式。传统逻辑还包括关于矛盾律和排中律等逻辑规律的理论，以及有关词项的理论。

形式逻辑在欧洲的创始人是古希腊的亚里士多德。亚里士多德的建立了第一个逻辑系统，即三段论理论。其论述形式逻辑的代表作有《形而上学》和《工具论》。继亚里士多德之后，麦加拉-斯多阿学派逻辑揭示出命题联结词的一些重要性质，发现了若干与命题联结词有关的推理形式和规律，发展了演绎逻辑。而古希腊的另一位哲学家伊壁鸠鲁则认为归纳法是唯一科学的方法。中世纪的一些逻辑学家，发展和丰富了形式逻辑。到了近代，培根和约翰·缪勒则进一步发展了归纳法。

在中国，形式逻辑的产生基本与欧洲同时。代表学派有墨家与名家，此外还有儒家的荀子。有意思的是，墨家研究逻辑为的是找到逻辑的原则，而名家为的是建立诡辩体系。墨家对于逻辑的认识集中体现在《墨经》中，该书对于逻辑已有了系统地论述。例如它区分了充分条件与必要条件，提出“大故（充分条件），有之必然，无之必不然”与“小故（必要条件），有之不必然，无之必不然”。而名家的惠施则提出了“合同异”的诡辩原则，目的是取消概念的边界。与惠施相反，同属名家的公孙龙则提出了“离坚白”的诡辩原则，认为任何独立的概念都有且只能有单一的属性。名家提出了许多诡辩命题，例如“白马非马”、“鸡有三足”、“孤犊无母”、“连环无扣”、“白狗黑”以及“今适越而昔来”等等。

显然，名家此种“开倒车”的研究方法是中国特有的，它能够建立其诡辩体系恰恰表明当时逻辑发育的水平很低，有着大量漏洞——因此名家才有机可乘。不过，名家此举也使得这些漏洞得到了充分的暴露，为后人的研究提供了垫脚石——若要发展逻辑，就必须去克服名家的诡辩命题。此外，名家的诡辩命题中也有合理因素——有的确实击中了形式逻辑的要害，这就意味着，除了形式逻辑之外，还有其他逻辑。最后，名家的部分命题里，可能含有合理的关于自然界以及人的认知过程的认识。比如一个命题是“天下之中央，燕之北越之南”，这个命题若要成立，则必须以“地球是圆的”作为前提。在当时天圆地方的“盖天说”占主导的情况下，名家能有这样的认识是不易的。再有一个命题是认为“飞鸟未尝动”，若做正解，应该是名家认识到我们对于“运动”的直观概念是建立在将归纳了两次静止的认识的基础之上的。当时能做出这些判断实在不容易，可惜这些认识都是以诡辩的形式出现的。

在古印度，公元前四世纪时，胜论派和正理派开创了因明学，至六世纪时陈那将其完善，称新因明学。因明学，即形式逻辑。数理逻辑它是现代形式逻辑。之所以称为数理逻辑，一方面是由于在研究中广泛地使用了人工的符号语言，并发展为使用一种形式化的公理方法，同时也应用了某些数学的工具和具体的结果；另一方面则是由于现代形式逻辑的发展受到数学基础研究的推动，特别是受到深入研究数学证明的逻辑规律和数学基础研究中提出来的逻辑问题的推动。数理逻辑之所以又被称为符号逻辑，是由于它使用人工的符号语言。数理逻辑的创始人是G.W.莱布尼兹。莱布尼兹提出建立“普遍的符号语言”、推理演算和思维机械化的思想。尽管莱布尼兹本人并没有实现他所提出的目标，但数理逻辑的发展却逐步（还没有全部）实现了莱布尼兹的理想。G.弗雷格在1879年发表的《概念语言》一书中，建立了第一个一阶逻辑体系。19世纪70年代，G.康托尔创立了集合论。集合论，特别是第一个一阶逻辑体系的建立，是形式逻辑的发展进入现代阶段的标志。

形式逻辑-曲解与再认识

世纪30至40年代，苏联曾把形式逻辑当作形而上学来批判，并把辩证法当作惟一科学的逻辑。讲辩证法一定要批判形式逻辑。在此影响下，当时中国也有人“宣判”了形式逻辑的“死刑”。不过在1949年前这种全盘否定形式逻辑的思潮在中国还不属主流思想。1949年到1950年间这种思潮也成为中国的主流思想。

1950年斯大林的《马克思主义和语言学问题》发表后，中国才为形式逻辑“平反”。然而“平反”并不彻底，跟苏联一样，形式逻辑仍带有“初等逻辑”的帽子，而“高等逻辑”自然非辩证法或辩证逻辑莫属。否定、贬低形式逻辑不仅阻碍了逻辑科学的发展，而且造成诡辩盛行的恶果。黑格尔曾十分轻蔑地评论过莱布尼茨的数理逻辑设想。马克思主义产生以后才冒出来的数理逻辑（第一个数理逻辑系统是费雷格于1879年提出的），在20世纪50年代初被视为帝国主义时代为垄断资产阶级服务的伪科学。

1961年代才开始突破苏联50至60年代逻辑教材的某些框框，清除了苏联教材散布的种种常识性错误。

形式逻辑-与其他逻辑间的关系

逻辑，是对思维过程的抽象。研究逻辑的目的是要在思维的层面上弄清楚得到结论的原因。从这个研究任务上来看，凡是具有得出结论的作用的思维过程，都是逻辑过程。据此，人的逻辑应分为三大类，即朴素逻辑、工具逻辑（包括称名逻辑、形式逻辑、表象逻辑）和辩证逻辑。

相较于朴素逻辑，形式逻辑的缺陷在于无法解释部分生活事件，也无法解释不符合形式逻辑本身的逻辑的来源。具体例子是，这样的语言结构“连……（名词A）我都不认为……（形容词Z），那么……（名词B）还会是……（形容词Z）吗？”形式逻辑就是不能解释的。而朴素逻辑则可解释为：大前提“A比B更Z”，小前提“A不是Z”，结论“B更不Z”。究其原因，在于形式逻辑不承认表述对比关系的句子可以当作三段论的命题，因此使得其不能解释朴素逻辑中的“对比”过程。此外，朴素逻辑中的“虚设”、“浸染”、“替代”、“赋色”、“逆向解释”、“近解释”以及“类比”等逻辑过程在形式逻辑看来都是无法理解的，但它们在生活中又是存在的。虚设，例如我们假设有外表全然均匀的绳子，则这个绳子可用于提取质量无穷大的物体。在这里，若按照形式逻辑的观点来看，由于前提假设是背离客观事实的，所以这个逻辑过程就是全然没有意义的。但是正是各种各样虚设的情景在影响着人的行动。物理上的各种极限就是虚设，比如绝对零度。它是不可能达到的，但是并不因为其不可能达到就否认绝对零度的意义。

浸染，例如“近朱者赤，近墨者黑”这种想法，尽管大家都知道是有问题的，但是却总是不能避免在考虑问题的时候落入这种俗套。比方说，成绩好的学生一定什么都好——尽管谁都知道这是有问题的，但是评价三好生的时候，有多少班级可以避免这种俗套呢？若形式逻辑是绝对的，那么这种情况就是不可能出现的。替代，例如“我觉得好的东西，别人也觉得好”或是反过来“对别人有用的东西，对我也会有用”。再有，则是两种表述的否定形式——无非是建立在“我和别人不可替代”这个前提之上，无非是替代的反向使用。其实，到底好不好、有用与否，要试了才知道，那么能不能说替代这种朴素逻辑就没有用呢？不能。因为“替代”起到的是动机的作用，例如当我断定“我觉得好的东西，别人也觉得好”的时候，我就会用言行来促使别人也去使用那个东西。而形式逻辑根本不可能承认替代的价值，因为这在形式逻辑看来是属于偷换概念、东拉西扯的事情。赋色，例如一个音乐家，一个会画家，一个雕塑家，看到同一个艺术事件，会被其认知为不同的概念客体，分别是旋律、颜色、空间。这实际上是这三类艺术家在用自己本身所具有的属性来“涂抹”同一个事件后所得出的结论，他们给客观世界以自己认定的“色彩”。用形式形式逻辑来分析问题本身就是一个赋色过程，但是其显然觉察不到这一点。

逆向解释，即用时间次序上后发生事件来解释先发生的事件。我们说，汪精卫是个阴谋家，在于他前期追随并保卫孙中山，后期当了汉奸。之所以能说他是阴谋家，就要求逆向解释——用其后来汉奸的事实来解释其先前的“良好表现”。用形式逻辑一贯性的观点来看，汪精卫由“好人”变成了“坏人”就是全然不可解释的。

近解释，例如我们走进房间，看到一个人坐在一张桌子面前，桌子上放着一瓶水。我们会自动把这瓶水的主人假定为那个人，理由就是两者靠近。这是物理上的接近引起的近解释。还有关系上的接近引起的近解释，即如果初中生的算术不好，初中的老师可能会假设，该生小学老师的教法有问题。理由就是“该生是那个（小学）老师教出来的”，两者有关系。最后则是相似性引起的近解释。包括物理相似与概念相似。物理相似，例如了解了金属钠的特性，对于金属钾的特性就可以做猜测，理由是两者同属一个主族。概念相似，比方说“朴素辩证法”、“唯心辩证法”、“唯物辩证法”三者有什么区别？对于没有专门学过的人，解释这些词语的时候就是用他最了解该类词语中的一个，加上被解释对象的形容词的含义，来给出定义。形式逻辑自然不能承认近解释，因为这属于瞎猜乱说的范畴。但上述现象的存在证明了形式逻辑的相对性。

类比，即打比方是生活中常用的逻辑，同时也是朴素哲学一般的立论方法。它自然是有漏洞的——番茄和苹果不是同一个东西，怎么能“比”呢？按照形式逻辑的观点来看，这是全然不可接受的。但是这却是常见的逻辑现象。

朴素逻辑应该还有其他的逻辑过程。自然，朴素逻辑也有其局限性，即它能解释任何事情，因此无法排谬。也就是说，在朴素逻辑里，就没有“错误的逻辑”这种概念。这显然是不正确的。

朴素逻辑是自发的、不系统的逻辑过程。自发，就在于很多时候，我们在使用着朴素逻辑，但是却没有意识到。不系统，即朴素逻辑的具体过程可以单独存在。我可以用逆向解释来分析这个问题，再用对比的方法来分析另一个问题，而全然不用考虑两个问题是否有关，以及这种“差别对待”是否合理。朴素逻辑支撑着我们大部分的日常生活，同时，显然这种逻辑会不断地制造错误。此时，工具逻辑就登场了。

工具逻辑是自觉的系统的逻辑。它很清楚其任务是对思维进行梳理、改正、引导，其目的是明确的。再有则是工具逻辑的原则是不能单独地存在的，有一条原则，其他的原则是其必然推出。之所以说它是工具，在于它的机械与刻板，且处于各种形式的对立情况下的双方都可以使用它来为自己自圆其说——它本身不具备价值，只能体现其使用者的价值取向。

对于工具逻辑能否全面解决朴素逻辑所带来的问题，答案显然是否定的。原因在于工具逻辑全然否定或是不考虑朴素逻辑，也就是说，它对朴素逻辑否定过度了。这种过度否定导致工具逻辑不能彻底清理朴素逻辑中的错误，不能甄别朴素逻辑中的正确成分。其次，工具逻辑本身是由三个矛盾的子范畴构成，即称名逻辑、形式逻辑与表象逻辑。这就导致工具逻辑不能以一个统一的标准来梳理朴素逻辑。若依照系统化的程度来说，朴素逻辑是基础的，工具逻辑是相对高级的。朴素逻辑与工具逻辑构成矛盾。他们之间斗争的一面不必多说，联系的一面则是称名、推理、表象加工三者在朴素逻辑中都可找到对应的行为。在朴素逻辑里，称名就是叫出“XX”的名字，说说它的内容，推理就是“猜”，表象加工就是幻想。这些具体的内容在朴素逻辑里是很一般的事情，但是在下一阶段的逻辑里，却都自成体系了。

按照认知的串行形式与并行形式的观点来看，称名逻辑是转换逻辑。它实现串行思维（如语言加工）与并行思维（如表象加工）间的转换——将串行思维的结论展开，将并行思维的结论点化。它担负着对客体进行直接识别的功能，将处于潜意识的朦胧认识或是观念之外的实在物概念化至意识层面的功能，并为形式逻辑与表象逻辑提供严格的素材（确切的起点），同时又要对形式逻辑与表象逻辑的结论进行再加工，再次开始称名。

称名逻辑要求所得出的名称或是属性与相应的前提以及称名的对象范畴相一致——在形式上，反对在同一个前提下，违反概念与范畴一一对应的情况，违反概念间单一形式的从属关系的情况；在内容上，反对称名过度或是称名不足而导致的概念范畴与对象范畴显著地不一致。具体来说，比如实在的香蕉被叫做“香蕉”与“菠萝”，概念的“番茄”对应实在的番茄与哈密瓜，概念的“粉笔”既对应粉笔本身还对应实在的物质，以及黑色的马叫做“马”白马则不是“马”等诡辩的情况都是称名逻辑所反对的。

称名逻辑的操作过程是对属于一定范畴的事物进行命名与描述。命名，是把范畴本身当作一个不可分割的元素进行命名（元素命名）。描述，是把范畴本身当作描述的疆界来描述范畴本身所具有的属性（属性描述）。在元素命名的过程中，涉及命名精度的问题。比如一棵榉树，一般的人看见了，说“有一棵树”就可以了。但是搞植物的人，就可以说出是属于什么种属的哪种榉树。元素命名要使其元素的名称与精度的要求相一致。属性描述，则涉及描述的前提范畴的问题（注意，是描述的前提范畴，不是描述的对象范畴）。由于一个范畴的属性是举之不尽的，因此就需要对描述行为本身加以限制。例如要求谈谈你自己，可能会不好说，因为可以说的东西太多了，而且一旦说起来，如条件允许是可以说到生命终止的那一刻的。所以就要限定“说”本身，比方说，要求你在“XX方面”谈一谈你自己。

总之，在称名逻辑将一个事物描述为一个点（元素命名）或是许多条线（属性描述）之后，若要对“点”或“某一条线”进行继续加工，就要用到形式逻辑，若要对若干条线组成的面这个整体进行加工，则需要表象逻辑。这就是称名逻辑之所以是另外两种逻辑的起点的原因了。之所以说“严格”，乃是由于表象逻辑与形式逻辑并不会像称名逻辑那样自觉考虑自己的起点的性质是什么。也就是说，这两类逻辑对于其起点是跟着感觉走，觉得什么是对的，就以什么作为起点。例如费尔巴哈，他认为人是纯粹自然的生物，又认为人有超自然的价值与习性——他对于“人”的称名是混乱的。于是，在他的人本机械唯物论里，就既承认物质第一性，又承认是人的意识创造了历史与社会，还提出了纯粹只有“爱”这个属性的神。他就是称名的工作没有做好，然后用形式逻辑一杆子捅到底，就形成其机械唯物论。形式逻辑最怕的就是矛盾，但是形式逻辑所催生的哲学之一——机械唯物论却是充满了不能自圆其说的东西的。

这里再简单说一下表象逻辑与形式逻辑。表象逻辑是并行逻辑，其要求人同时把握并操作多个属性。运用这种逻辑的人，会说其脑袋里有一幅图，或是他在脑袋里搬运、翻转、修改某个“物品”。艺术创作、图纸任务、空间任务以及顿悟式的学习过程都是离不开表象逻辑的。形式逻辑是串行逻辑，其本质是直线式的推导，其任务在根本上是对某个属性进行深度加工。其逻辑的每一项只能由单一的内容，至少是没有矛盾的内容构成。

接下来，我们就可以看看形式逻辑与称名逻辑和表象逻辑相比有什么差异了。与称名逻辑相比，形式逻辑的直接动力是逻辑的规则与要求，称名逻辑的直接动力则依赖于“发现”。在语言功能上，称名逻辑提供语言的齿轮，形式逻辑使之运转起来。形式逻辑的优点是运动性，即形式逻辑是一个不断推导的过程，但称名逻辑却只能进行一次转换。形式逻辑的缺点是，由于其只能加工单一的属性，这就使得用它来把握复杂事物的时候会不可避免地带来事物属性的丢失，导致原本完整的事物变得支离破碎，原本有联系的事物变得孤立起来，甚至在意识层面上自相矛盾。形式逻辑使得称名逻辑有价值，但是却不会自觉按照称名逻辑的要求来规范自己的逻辑起点。由于起点的不严谨，这就可能产生出完全符合形式逻辑的规则的谬论。

与表象逻辑相比，形式逻辑的前进是步步为营，表象逻辑主要依赖顿悟（不知怎么地一下子就想到了，就觉得应该那样）。形式逻辑是语言的、听觉的逻辑。表象逻辑则是图画的、视觉的逻辑。在语言上，表象逻辑不容易表达（需要用称名逻辑将表象转化为语言），但是形式逻辑却不存在这个问题。形式逻辑的优点是可以对事物的局部进行深度加工，缺点是无法在一个逻辑过程中既把握局部又把握整体。因此，在形式逻辑进行归纳活动的时候，往往会犯以偏概全或是用一般来推特殊的毛病。

形式逻辑的推导过程，是一个不断变换范畴的过程。他可能变到了与其起点，与之原有整体相矛盾的那边还不自知——因为它否认矛盾，所以自身矛盾了却还不知道。不过，由于起点的不严格与对整体的把握的缺失，出现这样的错误是必然的。需要再次强调的是，形式逻辑同样可以催生哲学。除了机械唯物论，还有客观唯心主义以及神学都是形式逻辑的产物。自然，形式逻辑也生产着西方自然科学。此种形式逻辑的自然科学方法，被叫做逻辑实证主义。形式逻辑完全失灵了的形态则是繁琐哲学。有意思的是，同一个母亲的孩子相互间都是矛盾的，自身也是充满矛盾的。可这位母亲却千方百计地否认矛盾——这正应验了唯物辩证法的观点：若要掩盖矛盾，那么被“掩盖”了的矛盾将以更加光怪陆离的形式在其他方面表现出来。

不难看出，如果我们的只承认形式逻辑，那么朴素逻辑、称名逻辑、表象逻辑都将非法。但是形式逻辑本身又完成不了另外这些逻辑的任务，也就是说，形式逻辑并不是最一般的逻辑。再加上形式逻辑也不能统合其他逻辑，也就是说，形式逻辑不是最抽象的逻辑。因此，最抽象而又最一般的逻辑就登场了，即辩证逻辑。

辩证逻辑的三条原则，即对立统一、否定之否定、质量互变。另外，辩证逻辑有五个维度，即原因维度（内因外因、根本原因－主要原因－次要原因）、主次维度（主次矛盾、主次方面）、一般－特殊、相对－绝对、整体－局部。三条原则与五个维度集中体现为“矛盾”的观点及分析方法。在方法上，辩证逻辑要求用全面的、发展的、联系的、矛盾的观点看待问题，要求具体问题具体分析，要求明确讨论问题的前提范畴。主张确定的范畴下，有确定的真理。

辩证逻辑不是把矛盾封装起来，其本身就是建立在矛盾之上的——这是辩证逻辑与次协调逻辑的本质区别。辩证逻辑不是要维护一个将要崩溃的粉饰出来的没有矛盾的逻辑系统，而是把矛盾本身当做内容来研究。形式逻辑所做的正确的事情，在辩证逻辑看来，那或者是在论述量变，或者是在论述一个处于缓和状态下的矛盾，或者是在论述一般性。这种论述本身是有意义的，但是若形式逻辑要将其方法贯穿到一切领域里，由于它不兼容且无法调节处于辩证逻辑下位的其他逻辑间的矛盾，因此夸大形式逻辑不是正确的做法。

辩证逻辑除了有特有的分析方法外，还是其他逻辑的元逻辑——它调节操纵着朴素逻辑与工具逻辑。实际上，辩证逻辑与包括工具逻辑与朴素逻辑在内的非辩证逻辑构成矛盾关系。朴素逻辑中，我们可以看到“联系”、“对立”等观点。在工具逻辑里，我们可以看到整体的观点、范畴的观点、局部的观点。这些观点终于在辩证逻辑里统一了起来，并可以各司其职。

辩证逻辑并不要取消其下位逻辑。就逻辑本身来说，其本来就是在下位逻辑存在矛盾的基础上产生的。这正应验了辩证逻辑本身的一个观点，即矛盾自身推动自身发展。因为其下位逻辑存在矛盾，所以它才能也是必然出现。所以如果取消了下位逻辑，就等于取消了下位逻辑间的矛盾，那么辩证逻辑也就会失去其逻辑上的来源。但是如果说辩证逻辑的产生对下位逻辑没有影响，这显然又是一种错误。如果说辩证逻辑出现以前，下位逻辑是处在乱斗中，那么辩证逻辑出现以后，下位逻辑间的关系就变得可以解释与控制了。

不过对于具体的个人来说，由于先天后天的影响，对于具体来说的五种逻辑（朴素、称名、形式、表象、辩证）的接受情况不同。因此，若是擅长使用非辩证逻辑的人遇到了问题，不妨试试用辩证逻辑来调节一下。下位逻辑能够解决的问题，那就用下位逻辑来解决，如果不能，就要用上位逻辑来解决。相较于辩证逻辑巨大的思维工作量，有时下位逻辑能够用少量的脑细胞给出一个适当的答案。

形式逻辑-其他观点

黑格尔的大小逻辑讲的是哲学，不讨论从形式上讲有什么样的前提可以得到什么样的结论这样的推理形式方面的问题。其实，在现今的非经典演绎逻辑中确实有一支是与辩证逻辑有很多相似之处的，这种逻辑就是次协调逻辑（又常称为费协调逻辑、亚相容逻辑，也有人称之谓悖论逻辑、辩证逻辑）。这种逻辑承认经典演绎逻辑中的“矛盾律”并不普遍有效，试图将“矛盾”封装起来，不让其危害整个系统。

许多认同黑格尔辩证逻辑的人也是因为看到了现代经典逻辑中的悖论问题，而企望黑格尔的辩证逻辑能解决这个问题。但事实上，类似的方法已经有了，这就是次协调逻辑。然而，次协调逻辑是隶属于现代非经典演绎逻辑的，如果次协调逻辑真是辩证逻辑的话，那么这种辩证逻辑属于现代非经典演绎逻辑的一支，而不是独立于其外。不过，次协调逻辑尽管与黑格尔的辩证逻辑有许多相似之处，但也有许多区别，并不能简单的说它是辩证逻辑。

4因明学-因明学介绍

因明是古代印度佛家五明之一。五名所指如玄奘法师所云：“一声明，释古训字，诠目疏别。二工巧明，伎术机关，阴阳历数。三医方明，禁咒闲邪，药名针艾。四因明考定正邪，研核真伪。五内明，究畅五乘，因果妙理”[1][1]。此五明有层次之别。因明初为佛家论义之方便法。其用于与其他各派、甚至是大小乘之间的辩论。在佛家因明产生之前，古代印度已有的学问一般称之为正理。正理思想首先由小乘开始研究。佛家有关因明的第一部著作是由法救著的《论义门论》，此书已失传，据说与龙树菩萨的《方便心论》相似。此后到弥勒、无著的大乘时代他们觉得正理思想可以采用，因而改造为佛家之因明。因明这一词语就首先出现在无著所著的《瑜伽师地论》中。在无著之后，世亲又继续发展因明，并著有《论轨》和《论式》两书。因明发展至此，虽直承正理，但与佛家根本教义相融合，他们已经开始将因明与内明相辅发展。这是弥勒、无著及世亲共同努力的结果。

因明学-作者介绍

因明发展至世亲再传弟子陈那时，就开始具有了量论的性质。因此，因明也分为古因明和新因明。陈那（意译为大域龙，约450----520）生于南印度的婆罗门，后出家随世亲学习大小乘经典。陈那一生有许多文论，其中关于量论因明学主要的著作有《观三世论》《观总相论》《观境论》《因门论》《取事施设论》《因明正理门论》和其晚期在许多小品论文的基础上加以总结而成的《集量论》。其中《因明正理门论》和《集量论》后世影响最大，这两部著作各有偏重。《因明正理门论》主要讨论“立”和“破”的问题。《集量论》是陈那的晚期著作，这部大著与早期的《因明正理门论》有极大的差别，《因明正理门论》较少讨论量，而《集量论》则主要讨论的是量，并且在这部著作中陈那将获取知识的方法分为现量和比量。在《因明正理门论》中主要讨论的“立”“破”问题在《集量论》中则归为比量部分。从陈那的《集量论》中可以看出陈那晚期已完全突破了古因明单纯论义的性质，而成就了量论因明学。所谓量论是古代印度所特有的认识论。古代印度各派都有自己的认识论体系。量分

为所量和能量，所灵指认识对象，能量指认识能力，以能量见之所量当下的结果即是量果（量的结果），而关于量的知识即为量论。因明发展至陈那时代，陈那将因明与佛家量论融合在一起，形成了佛家所独有的量论因明学。

因明学-因明七论

继陈那之后法称是佛家量论因明学的最得力贡献者，法称所著的量论因明学的著作有七部，即“因明七论”，分别为：《释量论》、《定量论》、《正理滴论》、《因滴论》、《关系论》、《悟他论》、《净理论》。至此，佛家量论因明学发展至顶峰。以后再也无人超越法称。此后，量论因明学的发展仅仅只是将法称的七部著作进行某一方面的阐释。但这些并没有从根本上推进量论因明学向前发展。实质上，法称已从根本上终结了量论因明学的理论。也就是说，法称已从根本上解决了量论因明学的所有问题。而法称量论因明学的最终完成在另外一个更深的意义上则标志着大乘理论的终结。这是因为法称所建立的量论因明学已彻底摆脱了单纯的论义的性质，而是将量论因明学变成了一种可以达到真理的理论，《正理滴论。总诠》：“众人所务，凡得成遂，必以正智为其先导”[2][2]。这就是法称对量论因明学的界定，即指出量论因明学就是达到正智（真理）的前提性条件，量论因明学即是达到真理的保证。而佛家的最终真理即是佛本身，故法称最终确立的量论因明学是一个用于最终悟道的法门。因此，从这个意义上说，法称所确立的量论因明学是终结了佛教的大乘理论，事实上佛教的发展也是证明了这一点，自法称之后佛教即进入密教时代。此后，法称的量论因明学在西藏所发展的藏传佛教中成为实践修行所依据的重要理论。

因明学-思想背景

从古印度思想发展来看，印度佛家量论因明学之成就既是佛家思想发展之必然，也是古印度思想发展之必然，古印度思想学派众多正统有正理、胜论、数论、声论、瑜伽、吠檀多六派。佛言有九十六种外道。虽然学派众多却有一共同的目的，即解脱。这是从古印度思想思想区别于西方思想的重要体现，印度思想无纯粹只为知识之理论，其无论为何种思想皆以解脱为目的。故佛家量论因明学之成就正是在此思想背景之下的必然发展。而法称《释量论》中《定量品》正是佛家量论因明思想的最高成就。何以？所谓量者，无欺智也。无欺智者唯有佛陀，故佛家之最终极真理即是佛，唯有佛陀方是定量士夫。从而可言是法称《释量论》完成了世间法于出世间法的圆融，是真正的正智——人类普遍的知识学。

5高阶逻辑-正文

又称广义谓词逻辑。它是一阶逻辑（见一阶理论及其元逻辑）的推广。在一阶逻辑中，量词只能用于个体变元，即只有个体约束变元，并且只有个体变元能作谓词变元的主目(见谓词逻辑)。这样就限制了一阶逻辑的语言的表达能力。如果去掉一阶逻辑中的上述限制，命题变元和谓词变元也能作约束变元，即受量词约束，并且作谓词变元的主目，以此构造起来的逻辑系统就是高阶逻辑。它包括二阶逻辑、三阶逻辑……以至无穷阶逻辑。

二阶逻辑一阶逻辑的一个很自然的推广是二阶逻辑。修改一阶逻辑中与量词有关的形成规则：如果A(α)是合式公式,α是自由变元（个体变元、命题变元或谓词变元），则凬αA(α)和ヨαA(α)是合式公式；同时,确定适当的公理和变形规则，所得到的系统就是一个二阶逻辑（二阶谓词演算）。例如，凬X【F(x)∨塡F(x)】是一阶逻辑中的合式公式,凬F凬x【F(x)∨塡F(x)】就是一个二阶逻辑的合式公式，它表示凬x【F(x)∨塡F(x)】对一切性质F都成立。二阶逻辑具有比一阶逻辑更强的表达能力。例如，对于数学归纳原则:“如果一公式对数0成立，并且如果它对某一个数成立则对该数的后继也成立，那末这个公式就对所有的（自然）数成立”，就不能在一阶逻辑陈述的算术理论中，用一个公式表达。而在二阶逻辑中，由于有了谓词量词，就可以用一个公式把该数学归纳原则表示为：

凬F【F(0)∧凬x(F(x)→F(x+1))→凬x F(x)】。

简单类型论进一步推广二阶逻辑，可以构造出三阶逻辑、四阶逻辑等等，而对于每一自然数 n，可以构造 n阶逻辑。三阶逻辑是在二阶逻辑中引进谓词的谓词。在一阶和二阶逻辑中，谓词表示个体的性质或个体间的关系，以个体常元（个体的名字）或个体变元作主目。这样的谓词称为一层谓词；一阶和二阶逻辑中的谓词变元称为一层谓词变元。有的谓词不是表示个体的性质或个体间的关系，而是表示某个谓词的性质或关系。例如，对一个关系R，我们说R是对称的，即如果R(x,y)，则R(y,x);或者说是传递的，即如果R(x,y)且R(y,z)，则R(x,z)。而这种对称性、传递性等都是关于关系的性质。用sym(R)、tr(R)表示

关系R是对称的、传递的，而sym和tr都以一层谓词作主目。主目中包括一层谓词（谓词变元）的谓词（谓词变元）称为二层的。一个包括二层谓词变元，但二层谓词变元只作为自由变元出现的逻辑系统，就是三阶逻辑。在三阶逻辑中，不但引进二层谓词变元，而且还要区别谓词变元（一层的、二层的）的不同的型。个体变元的型为i;一层谓词变元F(x)的型为(i),G(x,y)的型为(i,i)；二层谓词sym(R),其主目R的型为(i,i),sym的型为［(i,i)］;二层谓词变元H［G(x,y),i)］的型为［(i,i),i)］,等等。对三阶逻辑的形成规则，不但要考虑到新增加的二层谓词变元，还要根据谓词变元的型的区分，对二阶逻辑的形成规则加以修改，并确定适当的公理和变形规则。如果修改三阶逻辑的形成规则，而且允许二层谓词变元也作约束变元，并且确定适当的公理和变形规则,就得到四阶逻辑。类似地,还可以引入三层谓词变元、四层谓词变元等，构造五阶逻辑、六阶逻辑，等等。这样，就可以构造出所有有穷阶逻辑。简单类型论就是ω阶逻辑，它是把所有有穷阶逻辑总汇在一起的系统。简单类型论的公理，除了有一阶逻辑、二阶逻辑等的公理外，还包括另外两条公理，即外延公理和选择公理。这两条公理与公理集合论中的外延公理和选择公理相当。

一阶逻辑与高阶逻辑一阶逻辑具有完全性，即系统中的普遍有效的公式都是系统中可证明的。这是一阶逻辑的一个重要特征。此外，一阶逻辑还有两个重要的定理,即紧致性定理和勒文海姆-司寇伦定理（见司寇伦定理）。一阶逻辑还有一个区别于高阶逻辑的重要性质，即一阶逻辑是在运算塡,∧,ョ下封闭的唯一能够满足紧致性定理和勒文海姆-司寇伦定理的逻辑。虽然一阶逻辑的表达能力是受限制的，但也已很强了，特别是有了公理集合论以后，用一阶逻辑的语言可以陈述当今数学的全部分支。因此，有许多逻辑学家认为，除一阶逻辑而外无需研讨高阶逻辑。然而，用一阶逻辑陈述许多相当简单的定义和证明显得十分复杂，而通过高阶逻辑陈述这些定义和证明则要简单得多。尽管通过集合论可以把高阶逻辑归纳到一阶逻辑，但却造成定义和证明的大大复杂化。高阶逻辑的表达力和易推导性比一阶逻辑强有力得多。因此，在数理逻辑中高阶逻辑仍是有生命力的。

高阶逻辑的一个重大不足是没有完全性，它的任何公理系统，都不能证明系统中的全部普遍有效公式。

6紧致性定理

模型论中的一条基础性的定理。在一阶模型论中，该定理的含义是：如果一阶语言中一个命题集（形式理论）T的任何有限子集都有模型，则T自身有模型。在非一阶模型论中，紧致性定理不一定成立，但有时有较弱的结论或能起类似作用的定理。

根据紧致性定理证明T有模型，只需证明T的每一有限子集都有模型,而证明后者往往比直接证明T有模型要容易得多，这就是该定理之所以能在模型论以及其他一些数学分支中起重要作用的主要原因。例如，非标准分析是数学中一个新分支，它是建立在这样的有序域垬之上的，即垬和实数域R具有十分类似的普通性质,但垬中含有很多互不相等的无限小元及无限大元，这样的垬用普通数学方法是难以构作的，但其存在性则可以用紧致性定理证明。因为，利用垬中的无限小元，可以避开通常的"ε-δ"方式，而用比较自然但又严格的方式定义R中数列的极限概念及函数的连续性概念等，进而也可以比较简便地讨论各种分析数学问题，这就是非标准分析。它是模型论、特别是其中的紧致性定理对于数学的一个既有数学意义又有方法论意义的重要应用。在代数中，利用紧致性定理可以得到一些逻辑性的"转移原理"。例如:设ψ是一个关于群的一阶命题,若ψ对于每个无限群都真,则ψ也对每个元数相当大的有限群为真。对其他代数结构，如环、域等，也有类似的"转移原理"。又如：设ψ是一个关于域的一阶命题。若ψ对于每个特征数零的域都真,则ψ也对每个特征数P相当大的域为真,等等。这些原理，都是难以用普通数学方法证明的。

紧致性定理也可用于探讨一些数学命题间的和谐性、独立性问题，例如可以用它证明数论中一些待解问题相对于自然数一阶理论的一些较弱子理论的和谐性或独立性。

7司寇伦定理

模型论中的一条重要定理。它的发展了的形式通常也被称为勒文海姆-司寇伦-塔尔斯基定理,简称LST定理。在一阶模型论中，LST定理的含义是：设一阶语言L中所能表达的语句个数为λ（是一个超限数）,如果L中的一个形式理论T有无限模型，则T有基数为任何α≥λ的模型。在非一阶模型论中，LST定理不一定成立。

由于这个定理，在讨论问题时可以改换不同基数的模型而不影响所关心的理论T。例如，在用个体常量0,1；个体变量；函数符号+，×；关系符号=；命题连接词及量词所表达的一阶语言中,令T表示在对上述诸符号的通常解释下被整数环I所适合的

一切语句组成的集合（称为I的完备理论），则由于I是T的无限模型，由LST定理可知T有基数任意大的无限模型。这些模型显然都与I具有完全相同的一阶性质，除I自身外，其他模型都称为T的非标准模型。同理可知，存在着基数任意大的无限模型，它们分别与有理数域、实数域、复数域等具有完全相同的一阶性质。这些非标准模型往往有助于研究通常的标准模型。此外，还可顺便看出，任何一个无限模型，如整数环、有理数域、实数域、复数域等都不可能在一阶语言范围内公理化，即不存在一阶语句集T1，使整数环是T1的唯一模型，等等。在公理集合论（见集合论）中，用力迫法可以证明很多集合论命题的和谐性、独立性，而在应用力迫法构作各种集合论模型时，为了方便，一般都是从一组集合论公理的一个可数模型出发。这种可数模型的存在性，就是在该组公理“有模型存在”的假设下引用LST定理而得到的。

8选择公理

集合论中的一条公理。它肯定对任何由非空集合组成的非空集合S，存在函数?:S→∪S使对每个x∈S有f(x)∈x，f称作S的选择函数。容易推知，当S的元素互不相交时，f【S】就是 S的代表集。由ZF公理（见集合论）加上选择公理组成的系统记作ZFC。

由于在一个有穷长的证明中不能容纳无穷多次选择，因而需要有一种方法能“一下子”作完无穷多次选择。而ZF系统并不能保证这种方法常有，所以需要有选择公理。1904年，德国数学家E.策尔梅洛在证明良序定理时第一次明确地提出了选择公理。从此，学术界就开始了对选择公理的探讨和争论，特别是在A.N.怀特海和B.A.W.罗素的工作表明全部数学都可在 ZFC中叙述之后，这种探讨就显得尤有意义。

选择公理在大多数数学分支中都有着极为重要的作用，强完全性定理和紧致性定理的证明都离不开它，也正是根据该公理，人们才知道G.F.P.康托尔和R.戴德金德对无穷所下的两种定义是等价的，并由此得以建立各种简便易行的基数运算法则。如果没有选择公理就无法证明连续函数的两种定义等价，也无法保证每个向量空间都有基，就连“可数个可数集的并集仍然可数”这样一个看上去颇为自然的命题也无法证明，良序定理和左恩引理是数学中的得力工具，它们也都与选择公理等价。不过，选择公理也有反常的一面。1905年，G.维塔利使用这一公理构造了一个非勒贝格可测的实数集，这好象是顺理成章的。然而此后的20年中，德国的F.豪斯多夫、S.巴纳赫和A.塔尔斯基应用类似于维塔利的方法陆续证明了一项大出意外的结果，即分球悖论。这就是利用选择公理，可以把一个球切成有穷多块，再把这些块重新组合起来就得到两个和原先的球大小相同的球。选择公理就是这样一个既自然又很不自然的命题，它的真实性问题至今尚未解决。不过它的相对一致性和独立性研究都已取得圆满成果。这些成果是：1938年，由K.哥德尔证明了如果ZF一致则 ZF+AC一致；1963年，P.J.科恩则证明如果 ZF一致则ZF+塡AC也一致。柯恩还证明了“对可数个非空实数集组成的族，选择函数存在”这一命题独立于ZF。为了避开诸如分球悖论这样的怪事，集合论研究者还探讨了不少选择公理的弱形式，而且根据柯恩的研究结果，这些弱形式也都独立于ZF。

60年代以来，集合论研究者深入探讨了一些与选择公理对立的假设。其中最引人注意的是决定性公理，简称AD。该公理指自然数上具有完全信息的长度为ω的二人无穷零和对策有必胜策略。按照决定性公理，可以推出原来意义上的连续统假设，还可以推出实数是不可良序的以及每个实数集都是勒贝格可测的等等。进一步加强决定性公理，例如将对策的长度变为ω1，或将自然数博弈改为实数集的幂集上的博弈，都会与ZF不一致。但该公理的某些弱形式又是在ZF或 ZFC中可证的。关于决定性公理的相对一致性研究一直没有什么结果，因此集合论研究者普遍认为决定性公理不及选择公理可靠，而只把它当作一种工作假设。

9连续统假设

数学上关于连续统势的假设。常记作CH。通常称实数集即直线上点的集合为连续统，而把连续统的势（大小）记作C。2000多年来，人们一直认为任意两个无穷集都一样大。直到1847年，G.康托尔证明：任何一个集合的幂集（即它的一切子集构成的集合）的势都大于这个集合的势，人们才认识到无穷集合也可以比较大小。自然数集是最小的无穷集合，自然数集的势记作。康托尔证明连续统势等于自然数集的幂集的势。是否存在一个无穷集合，它的势比自然数集的势大，比连续统势小？这个问题被称为连续统问题。康托尔猜想这个问题的解答是否定的，即连续统势是比自然数集的势大的势中最小的一个无穷势，记作1。这个猜想就称为连续统假设。1938年，K.哥德尔证明了CH对ZF公理系统（见公理集合论)是协调的，1963年，P.J.科恩是不可能判定真假的。证明CH对ZF公理系统是独立的。这样，在ZF公理系统中，CH是不可能判定真假的。

10构造逻辑

一种非经典的逻辑系统。它主要由对数学持直觉主义、构造主义或致力于构造性数学研究和发展的数学家和逻辑学家建立和使用。在数理逻辑和数学基础中,“构造性”一词有几种不同的理解并在几种不同的意义下使用,其共同之处在于它们都满足下列构造性要求:①对存在命题ヨxAx的一个证明是构造性的,如果从这个证明能找到（构造出）一个特殊的对象x，它满足A；②不能无条件地使用排中律。按照构造性观点,对于p∨塡p,只有在有一个方法能判明p与塡p中哪一个是真的情况下，才能承认它是真的，而不承认任一命题非真即假。按照这些构造性观点建立的逻辑就是构造逻辑。

从构造性观点看不可接受的证明的例子，如定理：

存在两个无理数a和b，使得a b 是有理数。

该定理的一个非构造性证明是：或者是有理数或者是无理数,假若是有理数,取a=b=匇,因匇是无理数，故所取的

a和b满足定理；假若匇是无理数,取,b=匇，则a和b是无理数且是有理数，故所取的a和b满足定理。于是定理得证。从经典的逻辑和数学的观点看，该证明是无懈可击的，因而该定理确是成立的。

但从构造性的观点来看，这个证明仅是根据排中律肯定或者是有理数或者是无理数而作出的，但没有任何方法指明

究竟是有理数还是无理数，因而也没有指出究竟怎样去构造出满足定理的a和b。因此这个证明不是构造性的，不承认这个定理已经有一个证明。

说明经典逻辑和构造逻辑之间的对照的一个简单例子，是考虑所谓肯定的蕴涵演算，这个演算只有一个逻辑常项，即蕴涵词，它有两个公理和一条推理规则：

A1.A→(B→A)；

A2.(A→(B→C))→((A→B)→(A→C))；

规则E.如果A并且A→B，那么B。从构造性数学观点看，这个系统是足够的。但是，它并没有在下述意义上刻划出作为一个真值函项的蕴涵，即A→B是真的当且仅当 A假或者B真。例如,【((A→B)→A)→A】（即Peirce律）是一个重言式，但它在这个系统中是不能证明的。如果在该系统中增加以下两个关于否定的公理，能得到就蕴涵和否定而言的构造命题演算。这两个关于否定的公理为：

A3.(A→塡A)→塡A；

A4.塡A→(A→B)。

但要得到经典命题演算，则需要在上面系统中再增一条公理

A5.塡塡A→A。和排中律一样，该公理在构造逻辑中也是不成立的。

在构造逻辑中，对于逻辑联结词塡（非）、∧（并且）、∨（或者）、→（如果,则，）和量词ヨx（存在一个 x，有一个x）、凬 x（所有x）的理解如下：①对A∧B的一个证明由A的一个证明和B的一个证明一起构成；②对 A∨B的一个证明由特别指定的A的一个证明或者由特别指定的 B的一个证明构成；③对A→B的一个证明由一个构造c构成，构造c可把A的任一证明转换成B的一个证明，即构造 c具有如果d是A的一个证明，把c与d结合起来就产生 B的一个证明这种性质；④以符号⊥表示一个不可证的命题,对塡A的一个证明由一个构造c构成,构造c把对A的任一证明转换成对⊥的一个证明；⑤如果个体变元x取值于某个“基本的”个体域D，则对凬xA(x)的一个证明由一个构造c组成,当把构造c应用于域D中的任一个体d时,就产生对A(d)的一个证明c(d)；⑥如果个体变元x取值于某个“基本的”个体域D，则对ヨ xA(x)的一个证明由一个构造 c和域D中的一个个体d构成，并且构造 c是对A(d)的一个证明。

在构造逻辑中，各个联结词和量词都是彼此独立、不能相互定义的。

从20世纪30年代以来，构造逻辑已建立了多个形式系统。其中，K.哥德尔在1958年构作的系统为：

①A,A→B崊B;

②A→B,B→C崊A→C;

③A∨A→A,A→A∧A;

④A→A∨B,A∧B→A;

⑤A∨B→B∨A,A∧→B∧A;

⑥A→B崊C∨A→C∨B;

⑦A∧B→C崊A→(B→C)

⑧A→(B→C)崊A∧B→C;

⑨⊥→A;

⑩B→A(x)崊B→凬xA(x)（x在 B中不自由出现）；

凬xA(x)→A(t)（t对于A中的x自由）；

A(t)→ヨxA(x)（t对于A中的x自由）；

A(x)→B崊ヨxA(x)→B（x在 B中不自由出现），其中的崊为元数学符号。

11不可定义性理论

模型论中关于形式语言表达能力的一种研究。在这种研究中，影响较大的有A.帕多瓦、A.塔尔斯基和E.W.贝特等人。可（不可）定义性概念在递归论和公理集合论（见集合论）中被广泛使用，其中有不少特殊的可定义性概念及有关结果，如递归论中的分层理论，公理集合论中的可构成集等。

设u是形式语言L的一个模型，a是u的一个元素，如果存在L中一个式子嗞(x)，使a是u中唯一的适合嗞(x) 的元素，则称a为u中的可定义元素，否则称a为u中的不可定义元素。类似的还可以给出可(不可)定义的函数、集合等概念，它们都可被包含在下述的"可（不可）定义谓词"概念中。设P(x1,...,x n)是u上的一个谓词，如果存在L中一个式子嗞(x1,...,x n)，使对u中任何元素a1,...,a n都有：P(a1,...,a n) 成立当且仅当嗞(x1,...,xn)在u中为真，则称P(x1,...,x n)为在u上可定义的谓词；否则称P（x1,...,x n）为在u上不可定义的谓词。在一般情况下，并不提出特定的模型u,而是在形式语言中讨论可定义性概念。设L是一个形式语言,P 和P'是L之外的两个不同的n元谓词符号，∑(P)是语言L∪｛P｝中的一组语句，∑(P')是语言L∪{P'}中相应的语句组。①如果在∑(P)∪∑(P')的每一模型中都有(凬x1,...,x n)【P(x1,...,x n)凮P'(x1,...,x n)】成立，则称∑(P)隐含地定义了谓词P。②如果存在L中一个式子嗞(x1,...,x n)，使在∑(P)的每一个模型中都有

(凬x1,...,x n)【P(x1,...,x n)凮嗞(x1,...,x n)】成立，则称∑(P)明显地定义了谓词P。

由以上定义可以看出，如果∑(P)明显地定义P，则它也隐含地定义P。所以，如果要说明某一组语句∑(P)不能明显地定义P，只需说明∑(P)不能隐含地定义P就够了，换句话也就是说，只需找到∑(P)∪∑(P')的一个模型,在其中P与P'有不同的解释就够了。这一方法称为帕多瓦方法。在这方面，贝特在帕多瓦和塔尔斯基的工作基础上进一步证明了：∑(P)隐含地定义P当且仅当∑(P)明显地定义P。从而表明,如果∑(P)不能明显地定义P，则这种不可定义性必能用帕多瓦方法来说明。

在具体模型中的不可定义性方面，塔尔斯基有一个关于自然数系统中真语句集不可定义性的著名定理，其内容如下:令语言L={+,·,S,O},取L的模型=(N,+,·,S,O),其中N为自然数集,S为"后继"运算，考虑L中一切在中为真的语句的集合T,通过适当的有效编码,就可以把T看作N的子集。塔尔斯基定理是说：T是不可定义的。该定理与关于的判定问题的不可解性有

一定联系。

80年代以来，在模型论中对于模型的范畴性，也就是它的完备理论的范畴性，有较多的研究，从性质上说，这是一种关于可定义性的广义研究。例如，有理数域不是埲-范畴的，其含义是：在可数无限域范围内，有理数域不能用关于它的一切一阶真语句所成的集合唯一地刻划；又如，复数域是埌-范畴的，其含义是：在基数为埌的无限域范围内，复数域可以用关于它的一切一阶真语句所成的集合唯一地刻划。

递归论或可计算性理论，是一个数理逻辑分支。它起源于可计算函数和图灵度的研究。它的领域增长为包括一般性的可计算性和可定义性的研究。在这些领域中，这门理论同证明论和能行描述集合论(effective descriptive set theory)有所重叠。

递归算法的优缺点

○1优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 ○2缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 边界条件与递归方程是递归函数的二个要素 应用分治法的两个前提是问题的可分性和解的可归并性 以比较为基础的排序算法的最坏倩况时间复杂性下界为0(n·log2n)。 回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。 舍伍德算法设计的基本思想: 设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为 这显然不能排除存在x∈Xn使得的可能性。希望获得一个随机化算法B，使得对问题的输入规模为n的每一个实例均有 拉斯维加斯( Las Vegas )算法的基本思想: 设p(x)是对输入x调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x均有p(x)>0。 设t(x)是算法obstinate找到具体实例x的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x求解成功或求解失败所需的平均时间，则有： 解此方程可得：

蒙特卡罗(Monte Carlo)算法的基本思想: 设p是一个实数，且1/2

数列通项的十一种求法

数列通项公式的十一种方法 知识概要 一．利用递推关系式求数列通项的11种方法： 累加法、 累乘法、 待定系数法、 阶差法（逐差法）、 迭代法、 对数变换法、 倒数变换法、 换元法（目的是去递推关系式中出现的根号）、 数学归纳法、 不动点法（递推式是一个数列通项的分式表达式）、 特征根法 二。四种基本数列：等差数列、等比数列、等和数列、等积数列及其广义形式。等差数列、等比数列的求通项公式的方法是：累加和累乘，这二种方法是求数列通项公式的最基本方法。 三．求数列通项的方法的基本思路是：把所求数列通过变形，代换转化为等差数列或等比数列。 四．求数列通项的基本方法是：累加法和累乘法。 五．数列的本质是一个函数，其定义域是自然数集的一个函数。

一、累加法 1．适用于：1()n n a a f n +=+ ----------这是广义的等差数列 累加法是最基本的二个方法之一。 2．若1()n n a a f n +-=(2)n ≥， 则 21321(1) (2) () n n a a f a a f a a f n +-=-=- = 两边分别相加得 111 ()n n k a a f n +=-= ∑ 例1 已知数列{}n a 满足1121 1n n a a n a +=++=，，求数列{}n a 的通项公式。 解：由121n n a a n +=++得121n n a a n +-=+则 11232211 2 ()()()()[2(1)1][2(2)1](221)(211)1 2[(1)(2)21](1)1 (1)2(1)1 2 (1)(1)1n n n n n a a a a a a a a a a n n n n n n n n n n n ---=-+-++-+-+=-++-+++?++?++=-+-++++-+-=+-+=-++= 所以数列{}n a 的通项公式为2 n a n =。 例2 已知数列{}n a 满足112313n n n a a a +=+?+=，，求数列{}n a 的通项公式。 解法一：由1231n n n a a +=+?+得1231n n n a a +-=?+则 11232211122112211()()()()(231)(231)(231)(231)3 2(3333)(1)3 3(13)2(1)3 13 331331 n n n n n n n n n n n n a a a a a a a a a a n n n n --------=-+-++-+-+=?++?+++?++?++=+++++-+-=+-+-=-+-+=+-所以3 1.n n a n =+-

(完整版)常见递推数列通项公式的求法典型例题及习题

常见递推数列通项公式的求法典型例题及习题 【典型例题】 [例1] b ka a n n +=+1型。 （1）1=k 时，}{1n n n a b a a ?=-+是等差数列，)(1b a n b a n -+?= （2）1≠k 时，设)(1m a k m a n n +=++ ∴ m km ka a n n -+=+1 比较系数：b m km =- ∴ 1-= k b m ∴ }1{-+ k b a n 是等比数列，公比为k ，首项为11-+k b a ∴ 11)1(1-?-+=-+ n n k k b a k b a ∴ 1)1(11--?-+=-k b k k b a a n n [例2] )(1n f ka a n n +=+型。 （1）1=k 时，)(1n f a a n n =-+，若)(n f 可求和，则可用累加消项的方法。 例：已知}{n a 满足11=a ，)1(1 1+= -+n n a a n n 求}{n a 的通项公式。 解： ∵ 11 1)1(11+- =+= -+n n n n a a n n ∴ n n a a n n 1111--= -- 112121---=---n n a a n n 21 3132-- -=---n n a a n n …… 312123-= -a a 21112-=-a a 对这（1-n ）个式子求和得： n a a n 111- =- ∴ n a n 1 2- =

（2）1≠k 时，当b an n f +=)(则可设)()1(1B An a k B n A a n n ++=++++ ∴ A B k An k ka a n n --+-+=+)1()1(1 ∴ ???=--=-b A B k a A k )1()1( 解得：1-=k a A ，2 )1(1-+-=k a k b B ∴ }{B An a n ++是以B A a ++1为首项，k 为公比的等比数列 ∴ 1 1)(-?++=++n n k B A a B An a ∴ B An k B A a a n n --?++=-11)( 将A 、B 代入即可 （3）n q n f =)(（≠q 0，1） 等式两边同时除以1 +n q 得q q a q k q a n n n n 1 11+?=++ 令 n n n q a C = 则q C q k C n n 1 1+ =+ ∴ }{n C 可归为b ka a n n +=+1型 [例3] n n a n f a ?=+)(1型。 （1）若)(n f 是常数时，可归为等比数列。 （2）若)(n f 可求积，可用累积约项的方法化简求通项。 例：已知： 311= a ，1121 2-+-=n n a n n a （2≥n ）求数列}{n a 的通项。 解：123537532521232121212233 2211+= ?--?--?+-=???-----n n n n n n n a a a a a a a a a a n n n n n n ΛΛ ∴ 1211231+= +? =n n a a n [例4] 11 --+?? =n n n a m a m k a 型。

递归算法详解完整版

递归算法详解标准化管理处编码[BBX968T-XBB8968-NNJ668-MM9N]

递归 冯文科一、递归的基本概念。 一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自己来定义自己的方法，称之为递归或递归定义。在程序设计中，函数直接或间接调用自己，就被称为递归调用。 二、递归的最简单应用：通过各项关系及初值求数列的某一项。 在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简 a与前面临近几项之间的关单，于是人们想出另一种办法来描述这种数列：通过初值及 n 系。 要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各项的关系。 比如阶乘数列 1、2、6、24、120、720…… 如果用上面的方式来描述它，应该是： a的值，那么可以很容易地写成这样： 如果需要写一个函数来求 n

这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一些特殊情况——这也是递归函数的第一个出口，再处理递归关系——这形成递归函数的第二个出口。 递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问题的解。 以上面求阶乘数列的函数) f为例。如在求)3(f时，由于3不是特殊值，因此需 (n 要计算)2( 3f，但)2(f是对它自己的调用，于是再计算)2(f，2也不是特殊值，需要计 * 算)1( f，返回 )1(= 2f，需要知道)1(f的值，再计算)1(f，1是特殊值，于是直接得出1 * 上一步，得2 3 * )2( )3(= = f，从而得最终 =f )1( 3 2 * * )2(= =f 2 f，再返回上一步，得6 解。 用图解来说明，就是

九类常见递推数列求通项公式方法

递推数列通项求解方法 类型一：1n n a pa q += +（1p ≠） 思路1（递推法）：()123()n n n n a pa q p pa q q p p pa q q q ---??=+=++=+++=?? ......121(1n p a q p p -=++++ (2) 1 1)11n n q q p a p p p --??+=+?+ ? --?? 。 思路2（构造法）：设()1n n a p a μμ++=+，即()1p q μ-=得1 q p μ= -，数列 {}n a μ+是以1a μ+为首项、p 为公比的等比数列，则1 111n n q q a a p p p -??+ =+ ?--??，即1111n n q q a a p p p -??=++ ? --?? 。 例1 已知数列{}n a 满足123n n a a -=+且11a =，求数列{}n a 的通项公式。 解：方法1（递推法）： ()123232(23)3222333n n n n a a a a ---??=+=++=+++=?? (1) 22 3(122n -=++++ (2) 11 332 )12232112n n n --+??+=+?+=- ? --? ?。 方法2（构造法）：设()12n n a a μμ++=+，即3μ=，∴数列{}3n a +是以134 a +=为首项、2为公比的等比数列，则113422n n n a -++=?=，即1 23n n a +=-。

1n n +思路1（递推法）： 123(1)(2)(1)(3)(2)(1)n n n n a a f n a f n f n a f n f n f n ---=+-=+-+-=+-+-+-= …1 11 ()n i a f n -==+∑。 思路2（叠加法）：1(1)n n a a f n --=-，依次类推有：12(2)n n a a f n ---=-、 23(3)n n a a f n ---=-、…、21(1)a a f -=，将各式叠加并整理得1 11 ()n n i a a f n -=-= ∑ ，即 1 11 ()n n i a a f n -==+ ∑ 。 例2 已知11a =，1n n a a n -=+，求n a 。 解：方法1（递推法）：123(1)(2)(1)n n n n a a n a n n a n n n ---=+=+-+=+-+-+= ......1[23a =+++ (1) (1)(2)(1)]2 n i n n n n n n =++-+-+= = ∑ 。 方法2（叠加法）：1n n a a n --=，依次类推有：121n n a a n ---=-、232n n a a n ---=-、…、 212a a -=，将各式叠加并整理得12 n n i a a n =-= ∑ ，12 1 (1)2 n n n i i n n a a n n ==+=+ = = ∑ ∑ 。

专题由递推关系求数列的通项公式(含答案)

专题 由递推关系求数列的通项公式 一、目标要求 通过具体的例题，掌握由递推关系求数列通项的常用方法： 二、知识梳理 求递推数列通项公式是数列知识的一个重点，也是一个难点，高考也往往通过考查递推数列来考查学生对知识的探索能力，求递推数列的通项公式一般是将递推公式变形，推得原数列是一种特殊的数列或原数列的项的某种组合是一种特殊数列，把一些较难处理的数列问题化为熟悉的等差或等比数列。 三、典例精析 1、公式法：利用熟知的公式求通项公式的方法称为公式法。常用的公式有???≥???????-=????????????????=-21 11n S S n S a n n n 及 等差数列和等比数列的通项公式。 例1 已知数列{n a }中12a =，2 +2n s n =，求数列{n a }的通项公式 评注 在运用1n n n a s s -=-时要注意条件2n ≥，对n=1要验证。 2、累加法：利用恒等式()()1211+......+n n n a a a a a a -=+--求通项公式的方法叫累加法。它是求型如 ()1+f n n n a a +=的递推数列的方法（其中数列(){}f n 的前n 项和可求）。 例2 已知数列{n a }中112a =，121 ++32 n n a a n n +=+，求数列{n a }的通项公式 评注 此类问题关键累加可消中间项，而(f n ）可求和则易得n a 3、.累乘法：利用恒等式3 21121 n n n a a a a a a a a -=? ???????()0n a ≠求通项公式的方法叫累乘法。它是求型如()1n n a g n a +=的递推数列的方法(){}() g n n 数列可求前项积

递归论理论

递归论 文章整理编辑：论文文库工作室（QQ1548927986）论文写作发表辅导 递归论或可计算性理论，是一个数理逻辑分支。它起源于可计算函数和图灵度的研究。它的领域增长为包括一般性的可计算性和可定义性的研究。在这些领域中，这门理论同证明论和能行描述集合论(effective descriptive set theory)有所重叠。 数理逻辑中的可计算性理论家经常研究相对可计算性、可归约性概念和程度结构的理论。相对于计算机科学家，他们研究次递归层次，可行的计算和公用于可计算性理论研究的形式语言。在这两个社区之间有着相当大的知识和方法上的重叠，而没有明显的界限。 概述：计算的概念 递归论所考虑的基本问题是，给定一个从自然数到自然数的函数f，f是否是可以被计算的。“可以被计算”，我们先将其当作一个直观的概念。根据直觉，人们一般会认为，一个函数可以被计算是存在一个给定的过程，接受一个自然数n后，该过程进行一定的操作并给出f(n)作为输出。将计算这一直观的概念上升到数学层面的形式化定义这一工作是递归论的根本，并由哥德尔、邱奇、图灵、克莱尼和Emil Post等人在1930年代奠定。他们将图灵可计算性作为有效计算的形式化。 在递归论的基本概念被给定之后，一方面人们将该观念应用于数学中，从而证明了一系列自然的问题，如字问题，以及希尔伯特第十问题等问题是不可计算的。另一方面，理论家们进一步拓展，开始了相对可计算性，图灵度等问题的研究。如今，递归论仍是数理逻辑中活跃的领域。 历史 递归论理论起源自哥德尔、邱奇、图灵、克莱尼和Emil Post在1930 年代的工作。他们获得的基本结果建立了图灵可计算性作为有效计算的非正式想法的正确的形式化。通过能行计算的严格定义带来了在数学中有些问题是不可有效判定的最初证明。邱奇和图灵独立的证明了停机问题不能能行判定，而Post 证明了在Thue系统中确定一个字符串是否有规范形式(类似于在λ演算中一个项是否有规则形式)不能有效的确定。 不可解度结构的研究，包括图灵度、多一度和类似的结构，是这个领域的重要部分。图灵度的研究发起自Kleene 和Post [1954]。大量的可计算性理论中的研究已经投入到图灵度的性质的研究中。开始于1970 年代，图灵度的研究焦点已经从局部结构性质转移到全局性质， 比如图灵度的自同构(automorphism)和的可定义性。 在1930 年代确定了最初的例子之后，很多数学问题已经被证实是不可判定的。Novikov 和Boone 在1950 年代证实，给出在一个有限出现群中的一个字，没有有效的过程来判定这个字所表示的元素是否是这个群的单位元素。这个结果被用来证实很多其他问题是不可判定的，比如两个有限单形(simplicial complex)是否表现同胚空间的问题。在1970 年，尤里·马季亚谢维奇对希尔伯特第十问题给出了否定答案，它提问是否有有效的过程来判定有有限多个有理数上的变量的丢番图方程是否有在有理数上的解。这个否定解答是对Martin Davis、Hilary Putnam 和Julia Robinson 在1961 年给出的部分解答的巩固。 递归论包括可计算性的一般概念的研究，比如超算术可归越性(hyperarithmetic degrees)、α-

用递归法解决问题

3.5用递归法解决问题 【教材分析】 “用递归法解决问题”是《算法与程序设计》第三章第5节的内容，学业水平测试对本节内容也达到了B级要求，本节内容是在学习了VB基础知识中的三种基本结构，并且学习了数组、用解析法和穷举法解决问题等算法。本节先后介绍了“什么是递归法”、“自定义函数”、以及应用自定义函数结合递归算法来解决问题实例。通过本节内容的学习可以培养学生分析和分解问题的能力。从教材的结构上看“自定义函数”和“递归算法”是独立的，可以分别讲解，但在使用时两者是相辅相成的。 【学情分析】 这节课的教学对象是高中二年级学生，已经学习了算法与程序设计VB中的一些基础知识，初步了解了算法的概念。特点是在学习循环结构的过程中，学生已经积累了一些“递归”和“穷举”的算法。但是学生对函数尤其是“自定义函数”非常陌生，而“自定义函数”和“递归法”是本册的学习重点，也是以后编程的重点。学习本节内容学生可以充分体会递归算法的思想过程，扩大原来的知识面，进一步认识程序设计的功能，进一步激发学生学习算法与程序设计的兴趣。 【教学目标】 1．知识与技能： 理解什么是递归法，会用递归法的思想分析和解决问题 理解什么是自定义函数，能应用自定义函数实现递归算法的编程 2．过程与方法 学生通过思考、探究，体验递归算法和发现问题与解决问题的步骤 3．情感态度与价值观 在建立数学模型中培养学生的抽象思维能力，培养学生多维度思考问题和解决能力。 树立多学科整合的思想意识，能够用联系的观点解决问题。 【教学重点】 理解什么是递归算法，学会用递归法的思想分析问题。 理解自定义函数的概念。 【教学难点】 用自定义函数和递归算法编写程序解决问题 【教学方法及策略】

已知数列递推公式求通项公式的几种方法

已知数列递推公式求通项公式的几种方法 Revised on November 25, 2020

求数列通项公式的方法 一、公式法 例1 已知数列{}n a 满足1232n n n a a +=+?，12a =，求数列{}n a 的通项公式。 解：1232n n n a a +=+?两边除以12n +，得 113222n n n n a a ++=+，则11 3 222 n n n n a a ++-=，故数列{}2n n a 是以1222 a 1 1==为首项，以23 为公差的等差数列，由等差数列的通项公式，得31(1)22n n a n =+-，所以数列{}n a 的通项公式为31()222n n a n =-。 评注：本题解题的关键是把递推关系式1232n n n a a +=+?转化为 11 3 222 n n n n a a ++-=，说明数列{}2 n n a 是等差数列，再直接利用等差数列的通项公式求出3 1(1) 22n n a n =+-，进而求出数列{}n a 的通项公式。 二、累加法 例2 已知数列{}n a 满足11211n n a a n a +=++=，，求数列{}n a 的通项公式。 解：由121n n a a n +=++得121n n a a n +-=+则 所以数列{}n a 的通项公式为2n a n =。 评注：本题解题的关键是把递推关系式121n n a a n +=++转化为 121n n a a n +-=+，进而求出11232211()()()()n n n n a a a a a a a a a ----+-+ +-+-+， 即得数列{}n a 的通项公式。 例3 已知数列{}n a 满足112313n n n a a a +=+?+=，，求数列{}n a 的通项公式。 解：由1231n n n a a +=+?+得1231n n n a a +-=?+则 所以3 1.n n a n =+-

备战2020数学高考三大类递推数列通项公式的求法

三大类递推数列通项公式的求法 湖北省竹溪县第一高级中学徐鸿 一、一阶线性递推数列求通项问题 一阶线性递推数列主要有如下几种形式： 1. 这类递推数列可通过累加法而求得其通项公式(数列{f(n)}可求前n项和). 当为常数时，通过累加法可求得等差数列的通项公式．而当为等差数列时， 则为二阶等差数列，其通项公式应当为形式，注意与等差数列求和公式一般形式的区别，后者是，其常数项一定为０． 2. 这类递推数列可通过累乘法而求得其通项公式(数列{g(n)}可求前n项积). 当为常数时，用累乘法可求得等比数列的通项公式． 3.； 这类数列通常可转化为，或消去常数转化为二阶递推式 . 例１已知数列中，,求的通项公式． 解析：解法一：转化为型递推数列． ∵∴又，故数列｛｝是首项为２，公比为２的等比数列．∴，即． 解法二：转化为型递推数列． ∵=2x n-1+1(n≥2) ①∴=2x n+1 ② ②－①，得(n≥2)，故｛｝是首项为x 2-x 1 =2， 公比为２的等比数列，即，再用累加法得．解法三：用迭代法． 当然,此题也可用归纳猜想法求之，但要用数学归纳法证明．

例２已知函数的反函数为 求数列的通项公式. 解析：由已知得，则． 令=,则.比较系数，得. 即有．∴数列｛｝是以为首项，为 公比的等比数列，∴，故． 评析：此题亦可采用归纳猜想得出通项公式，而后用数学归纳法证明之． （4） 若取倒数,得，令，从而转化为（1）型而求之. （5）； 这类数列可变换成，令，则转化为(1)型一阶线性递推公式. 例３设数列求数列的通项公式．解析：∵，两边同除以，得．令，则有．于是，得，∴数列是以首项为，公比为的等比数列，故，即，从而．例４设求数列的通项公式． 解析：设用代入，可解出．

常见递推数列通项公式求法(教案)

问题 1:已知数列{a } ， a 1 = 1 ， a n +1 = n + 2 ，求{a n }的通项公式。 2 常见递推数列通项公式的求法 一、课题：常见递推数列通项公式的求法 二、教学目标 (1)会根据递推公式求出数列中的项，并能运用叠加法、叠乘法、待定系数 法求数列的通项公式。 (2) 根据等差数列通项公式的推导总结出叠加法的基本题型，引导学生分 组合作并讨论完成叠乘法及待定系数法的基本题型。 (3)通过互助合作、自主探究培养学生细心观察、认真分析、善于总结的良 好思维习惯，以及积极交流的主体意识。 三、教学重点：根据数列的递推关系式求通项公式。 四、教学难点：解题过程中方法的正确选择。 五、教学课时： 1 课时 六、教学手段：黑板，粉笔 七、教学方法： 激励——讨论——发现——归纳——总结 八、教学过程 （一）复习回顾： 1、通项公式的定义及其重要作用 2、区别递推公式与通项公式，从而引入课题 （二）新知探究： a n 变式： 已知数列 {a n } ， a 1 = 1 ， a n +1 = a n + 2n ，求{a n }的通项公式。 活动 1：通过分析发现形式类似等差数列，故想到用叠加法去求解。教师引导学 生细致讲解整个解题过程。 解：由条件知： a n +1 - a = 2n n 分别令 n = 1,2,3,? ? ? ? ??,(n - 1) ，代入上式得 (n - 1) 个 等式叠加之， 即 (a 2 - a 1 ) + (a 3 - a 2 ) + (a 4 - a 3 ) + ? ? ? ? ? ? +(a n - a n -1 ) = 2 + 2 ? 2 + 2 ? 3 + 2 ? (n - 2) + 2 ? (n - 1) 所以 a - a = (n - 1)[2 + 2 ? (n - 1)] n 1 a = 1,∴ a = n 2 - n + 1 1 n

题型最全的递推数列求通项公式的习题.

高考递推数列题型分类归纳解析 各种数列问题在很多情形下，就是对数列通项公式的求解。特别是在一些综合性比较强的数列问题中，数列通项公式的求解问题往往是解决数列难题的瓶颈。我现在总结出几种求解数列通项公式的方法，希望能对大家有帮助。 类型1 )(1n f a a n n +=+ 解法：把原递推公式转化为)(1n f a a n n =-+，利用累加法(逐差相加法)求解。 例1. 已知数列{}n a 满足211= a ，n n a a n n ++=+211，求n a 。 变式: 已知数列1}{1=a a n 中，且a 2k =a 2k －1+(－1)K , a 2k+1=a 2k +3k , 其中k=1,2,3,……. （I ）求a 3, a 5；（II ）求{ a n }的通项公式. 类型2 n n a n f a )(1=+ 解法：把原递推公式转化为)(1 n f a a n n =+，利用累乘法(逐商相乘法)求解。 例1:已知数列{}n a 满足321=a ，n n a n n a 11+= +，求n a 。 例2:已知31=a ，n n a n n a 2 3131 +-=+ )1(≥n ，求n a 。 变式:（2004，全国I,理15．）已知数列{a n }，满足a 1=1，1321)1(32--+???+++=n n a n a a a a (n ≥2)，则{a n }的通项1 ___n a ?=?? 12n n =≥ 类型3 q pa a n n +=+1（其中p ，q 均为常数，)0)1((≠-p pq ）。 解法（待定系数法）：把原递推公式转化为：)(1t a p t a n n -=-+，其中p q t -=1，再利用换元法转化为等比数列求解。 例:已知数列{}n a 中，11=a ，321+=+n n a a ，求n a . 变式:（2006，重庆,文,14） 在数列{}n a 中，若111,23(1)n n a a a n +==+≥，则该数列的通项n a =_______________ 变式:（2006. 福建.理22.本小题满分14分） 已知数列{}n a 满足*111,21().n n a a a n N +==+∈ （I ）求数列{}n a 的通项公式； （II ）若数列{b n }滿足121 11 *444(1)(),n n b b b b n a n N ---=+∈ 证明：数列{b n }是等差数列； （Ⅲ）证明： *122311...().232 n n a a a n n n N a a a +-<+++<∈ 类型4 n n n q pa a +=+1（其中p ，q 均为常数，)0)1)(1((≠--q p pq ）。 （或1n n n a pa rq +=+,其中p ，q, r 均为常数） 。 解法：一般地，要先在原递推公式两边同除以1 +n q ，得： q q a q p q a n n n n 111+?=++引入辅助数列{}n b （其中n n n q a b =），得：q b q p b n n 1 1+=+再待定系数法解决。 例:已知数列{}n a 中，651= a ,1 1)2 1(31+++=n n n a a ，求n a 。 变式:（2006，全国I,理22,本小题满分12分） 设数列{}n a 的前n 项的和1412 2333 n n n S a += -?+，1,2,3,n = （Ⅰ）求首项1a 与通项n a ；（Ⅱ）设2n n n T S =，1,2,3,n = ，证明：1 32n i i T =<∑

数据结构与算法分析论文(递归的讨论)

数据结构与算法分析论文 递归算法的讨论 学号 1415211013 姓名李莉姗 班级 14电子1班 华侨大学电子工程系

递归算法的讨论 所谓递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程）来表示问题的解。一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数)。递归过程一般通过函数或子过程来实现。递归方法：在函数或子过程的内部，直接或者间接地调用自己的算法。递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。递归算法解决问题的特点： (1) 递归就是在过程或函数里调用自身。 (2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。 (3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。 (4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。下面就让我们结合例子详细讨论一下递归算法。 一、递归算法的原理 递归算法简单的说就是在函数中调用函数自身，不断调用，直到满足函数得出计算结果(某个条件)。因为其需要不断循环的调用自身，所以称为递归调用。递归的原理,其实就是一个栈(stack), 比如求5的阶乘,要知道5的阶乘,就要知道4的阶乘,4又要是到3的,以此类推,所以递归式就先把5的阶乘表示入栈, 在把4的入栈,直到最后一个,之后呢在从1开始出栈, 看起来很麻烦,确实很麻烦,他的好处就是写起代码来,十分的快,而且代码简洁,其他就没什么好处了,运行效率出奇的慢。还有一个十分形象的例子：从前有座山，山里有个庙，庙里有个老和尚正在讲故事：从前有座山，山里有个庙，庙里有个老和尚正在讲故事：从前有座山，山里有个庙，庙里有个老和尚正在讲故事……如此循环往复

递推数列通项公式求法(教案设计)

递推数列通项公式的求法 彭山一中 郑昌建 一、课题：常见递推数列通项公式的求法 二、教学目标 1、知识与技能： 会根据递推公式求出数列中的项，并能运用累加、累乘、待定系数等方法求数列的通项公式。 2、过程与方法： ①复习回顾所学过的通项公式的求法，对比递推公式与通项公式区别认识到由递推公式求通项公式的重要性，引出课题。 ②对比等差数列的推导总结出累加法的试用题型。 ③学生分组讨论完成累乘法及待定系数法的相关题型。 3、情感态度与价值观： ①通过对数列的递推公式的分析和探究，培养学生主动探索、勇于发现的求知精神； ②通过对数列递推公式问题的分析和探究，使学生养成细心观察、认真分析、善于总结的良好思维习惯； ③通过互助合作、自主探究等课堂教学方式培养学生认真参与、积极交流的主体意识。 三、教学重点：根据数列的递推关系式求通项公式。 四、教学难点：解题过程中方法的正确选择。 五、教学课型，课时：复习课 1课时 六、教学手段：多媒体课件，黑板，粉笔 七、教学方法： 激励——讨论——发现——归纳——总结 八、教学过程 （一）复习回顾： 1、通项公式的定义及其重要作用 2、学过的通项公式的几种求法 3、区别递推公式与通项公式，从而引入课题 （二）新知探究： 问题1:已知数列}{n a ，1a =1，1n a +=n a +2，求n a ? 变式： 已知数列}{n a ，1a =1，1n a +=n a +2n ，求n a ?

活动：通过分析发现形式类似等差数列，故想到用累加法去求解。教师引导学生细致讲解整个解题过程。 解：由条件知：n a a n n 21=-+ 分别令)1(,,3,2,1-??????=n n ，代入上式得)1(-n 个等式累加之， 即)()()()(1342312--+??????+-+-+-n n a a a a a a a a )1(2)2(232222-?+-?+?+?+=n n 所以[]2)1(22)1(1-?+-=-n n a a n 由 1a =1，12+-=∴n n a n 练习： 已知数列}{n a ，1a =1，n n n a a 2 11=-+，求n a ? 总结：类型1：)(1n f a a n n =-+，利用累加法(逐差相加法)求解。 问题2： 已知数列{a n }满足)(,2,111*+∈==N n a a a n n ，求{a n }的通项公式。 变式：若条件变为)(,21*+∈=N n a a n n n 方法归纳：利用累乘法求数列通项 活动：类比类型1推导过程，让学生分组讨论研究相关解题方案。 解：1342312-??????????n n a a a a a a a a 1 2212222--??=n n 即) 1()2(2112-+-+++=n n n a a 练习： 已知数列{}n a 满足321=a ，n n a n n a 11+=+，求n a 。 总结：类型2型如 用累乘法求解 问题3： 已知数列{a n }满足)(,12,111*+∈+==N n a a a n n ，求{a n }的通项公式。 发现：)1(21,112111+=+++=+++n n n n a a a a 即 令b n =a n +1,则b n+1=a n+1+1 即21=+n n b b ) (1n f a a n n ?=+222n n n a -=∴2=++∴ +11n 1n a a

常见递推数列通项公式的求法

常见递推数列通项公式的求法 教学目标： (1)知识与技能：会根据递推公式求出数列中的项，并能运用累加、累乘、待定系数等方法求数列的通项公式。 (2)过程与方法： ①复习回顾所学过的通项公式的求法，对比递推公式与通项公式区别认识到由递推公式求通项公式的重要性，引出课题。 ②对比等差数列的推导总结出累加法的试用题型。 教学重点：根据数列的递推关系式求通项公式。 教学难点：解题过程中方法的正确选择。 教学过程: （一）复习回顾： 1、通项公式的定义及其重要作用 2、学过的通项公式的几种求法 3、区别递推公式与通项公式，从而引入课题 （二）新知探究： 问题1:已知数列}{n a ，1a =1，1n a +=n a +2，求n a ? 变式： 已知数列}{n a ，1a =1，1n a +=n a +2n ，求n a ? 活动：通过分析发现形式类似等差数列，故想到用累加法去求解。教师引导学生细致讲解整个解题过程。 练习： 已知数列}{n a ，1a =1，n n n a a 2 11=-+，求n a =? 总结：类型1：)(1n f a a n n =-+，利用累加法求解。 问题2： 已知数列{a n }满足)(,2,111*+∈==N n a a a n n ，求{a n }的通项公式。 变式：若条件变为)(,21*+∈=N n a a n n n 练习： 已知数列{}n a 满足321=a ，n n a n n a 1 1+=+，求n a 。 总结：类型2型如 用累乘法求解 问题3： 已知数列{a n }满足)(,12,111*+∈+==N n a a a n n ，求{a n }的通项公式。 变式：)(,64,311*+∈-==N n a a a n n ，求{a n }的通项公式。 ) (1n f a a n n ?=+

最全的递推数列求通项公式方法

高考递推数列题型分类归纳解析 各种数列问题在很多情形下，就是对数列通项公式的求解。特别是在一些综合性比较 强的数列问题中，数列通项公式的求解问题往往是解决数列难题的瓶颈。本文总结出几种求解数列通项公式的方法，希望能对大家有帮助。 类型1 )(1n f a a n n +=+ 解法：把原递推公式转化为)(1n f a a n n =-+，利用累加法(逐差相加法)求解。 例:已知数列{}n a 满足211= a ，n n a a n n ++=+211，求n a 。 解：由条件知：1 1 1)1(1121+-=+=+= -+n n n n n n a a n n 分别令)1(,,3,2,1-??????=n n ，代入上式得)1(-n 个等式累加之，即 )()()()(1342312--+??????+-+-+-n n a a a a a a a a )111()4131()3121()211(n n --+??????+-+-+-= 所以n a a n 1 11-=- 211=a ，n n a n 1231121-=-+=∴ 变式:（2004，全国I ，个理22．本小题满分14分） 已知数列1}{1=a a n 中，且a 2k =a 2k －1+(－1)K , a 2k+1=a 2k +3k , 其中k=1,2,3,……. （I ）求a 3, a 5； （II ）求{ a n }的通项公式. 解： k k k a a )1(122-+=-，k k k a a 3212+=+ ∴k k k k k k a a a 3)1(312212+-+=+=-+，即k k k k a a )1(31212-+=--+ ∴)1(313-+=-a a ， 2235)1(3-+=-a a …… …… k k k k a a )1(31212-+=--+ 将以上k 个式子相加，得 ]1)1[(2 1 )13(23])1()1()1[()333(22112--+-=-+???+-+-++???++=-+k k k k k a a 将11=a 代入，得

几种递推数列通项公式的求法

几种递推数列通项公式的求法 递推数列常常是高考命题的热点之一.所谓递推数列,是指由递推公式所确定的数列.由相邻两项的关系给出的递推公式称为一阶递推公式，由相邻三项的关系给出的递推公式称为二阶递推公式，依次类推.等差数列和等比数列是最基本的递推数列.递推数列基本问题之一是由递推关系求通项公式.下面是常见的递推数列及其通项公式的求法． 1 一阶线性递推数列求通项问题 一阶线性递推数列主要有如下几种形式： （1）1()n n x x f n +=+ 这类递推数列可通过累加法而求得其通项公式(数列{f(n)}可求前n 项和). 当()f n 为常数时，通过累加法可求得等差数列的通项公式．而当()f n 为等差数列时， 则1()n n x x f n +=+为二阶等差数列，其通项公式应当为2 n x an bn c =++形式，注意与等差数列求和公式一般形式的区别，后者是2 n S an bn =+，其常数项一定为０． （2）1()n n x g n x += 这类递推数列可通过累乘法而求得其通项公式(数列{g(n)}可求前n 项积). 当()g n 为常数时，用累乘法可求得等比数列的通项公式． （3）1(,0,1)n+n x =qx +d q,d q q ≠≠为常数； 这类数列通常可转化为1()n n x p q x p ++=+，或消去常数转化为二阶递推式 211()n n n n x x q x x +++-=-. ［例１］已知数列n x ｛｝中，11121(2)n n x x x n -==+≥，,求n x ｛｝的通项公式． ［解析］解法一．转化为1()n n x p q x p ++=+型递推数列． ∵121(2)n n x x n -=+≥，∴112(1)(2)n n x x n -+=+≥，又112x +=，故数列｛1n x +｝是首项为２，公比为２的等比数列．∴12n n x +=，即21n n x =-． 解法二．转化为211()n n n n x x q x x +++-=-型递推数列． ∵n x =2x n-1+1(n ≥2) ① ∴1n x +=2x n +1 ② ②－①，得112()n n n n x x x x +--=-(n ≥2)，故｛1n n x x +-｝是首项为x 2-x 1=2， 公比为２的等比数列，即1 1222n n n n x x -+-== ，再用累加法得21n n x =-．

递推数列通项公式求法(教案)

由递推数列求通项公式 马鞍中学--- 李群花 一、课题：由递推数列求通项公式 二、教学目标 1、知识与技能： 会根据递推公式求出数列中的项，并能运用累加、累乘、待定系数等方法求数列的通项公式。 2、过程与方法： ①复习回顾所学过的通项公式的求法，对比递推公式与通项公式区别认识到由递推公式求通项公式的重要性，引出课题。 ②对比等差数列的推导总结出叠加法的试用题型。 ③学生分组讨论完成叠乘法及待定系数法的相关题型。 3、情感态度与价值观： ①通过对数列的递推公式的分析和探究，培养学生主动探索、勇于发现的求知精神； ②通过对数列递推公式问题的分析和探究，使学生养成细 心观察、认真分析、善于总结的良好思维习惯；

③通过互助合作、自主探究等课堂教学方式培养学生认真参与、积极交流的主体意识。 三、教学重点：根据数列的递推关系式求通项公式。 四、教学难点：解题过程中方法的正确选择。 五、教学课型，课时：复习课 1课时 六、教学手段：多媒体课件，黑板，粉笔 七、教学方法：激励——讨论——发现——归纳——总结 八、教学过程 （一）复习回顾： 1、通项公式的定义及其重要作用 2、学过的通项公式的几种求法 3、区别递推公式与通项公式，从而引入课题 （二）新知探究： 问题1:在数列{a n}中 a1=1，a n-a n-1=2n-1（n ≥ 2），求数列{a n} 的通项公式。

活动：通过分析发现形式类似等差数列，故想到用叠加法去求解。教师引导学生细致讲解整个解题过程。 总结：类型1：)(1n f a a n n =-+，利用叠加法(逐差相加法)求解。 问题2：例2在数列{a n }中 a 1=1， （n ≥ 2），求数列{a n } 的通项公式。 方法归纳：利用叠乘法求数列通项 活动：类比类型1推导过程，让学生分组讨论研究相关解题方案。 练习2设{a n }是首项为1的正项数列，且(n+1)a n 2+1 –na n 2 +a n+1a n =0, （n=1,2,3…），求它的通项公式a n 。 n n n a a 21 =-) (1n f a a n n ?=+