解放军文职招聘考试数理逻辑

 数理逻辑

　　1．符号逻辑

　　数理逻辑作为一门数学学科，来源于对数学和逻辑基础的探讨，它最早可追溯到莱布尼茨，他关于逻辑演算的观念预示着布尔代数，而英国数学家布尔(G．Boole 1815—1864)在1847年出版《逻辑的数学分析》一书，正式推出所谓布尔代数，在逻辑上相当于命题演算．其后由英国数学家杰方斯(W．S．Jevons，1835—1882)和小皮尔斯(C．S．Peirce，1839—1914)在1874年加入次序关系，

　　德国数学 卷中加以公理化．第一个完全形式化的语言是德国数学家弗瑞格(G．Frege，1848—1925)在1879年出版的《概念文字》中引进的．他首先定义了全称量词及存在量词．并引进一般的谓词逻辑．不过相应的逻辑代数一直到1950年才由波兰数学家塔斯基(A．Tarski，1902—1983)所发展，他引进所谓“圆柱代数”．1955年美国数学家哈尔莫斯(P．Halmos，1916—)又引进多进代数，形成一般的逻辑代数理论．1889年意大利数学家皮亚诺(G．Peano，1858—1932)提出自然数的公理系统，即后来所谓皮亚诺算术公理．而戴德金在前一年也提出类似的公理系统．弗雷格在1884年出版的《算术基础》中开始提到算术无非是扩展的逻辑．戴德金也提出类似的观点．弗雷格在1893年出版的《算术的基本规律》第一卷中，用五条逻辑公理来推导算术命题．1902年6月罗素给弗雷格一封信，提出著名的罗素悖论，并指出弗雷格的矛盾．弗雷格在1903年出版的《算术的基本规律》第二卷附录中承认这是对他的巨大打击，正是这个悖论，揭开了数理逻辑新的一章．

　　2．罗素悖论

　　罗素的悖论是关于集合论的，康托尔已经意识到不加限制地谈论“集合的集合”会导致矛盾．其他人也发现集合论中存在矛盾．而罗素在1903年出版的《数学的原理》(Principles of Mathematics)中，则十分清楚地表现出集合论的矛盾，从而动摇了整个数学的基础．罗素的悖论是说：可以把集合分成两类：凡不以自身为元素的集合称为第一类集合，凡以自身做为元素的集合称为第二类的集合，每个集合或为第一类集合或为第二类集合．设M表示第一类集合全体所成的集合．如果M是第一类集  现了这个矛盾之后，导致第三次数学危机，在数学界出现了各种意见，从抛弃集合论到尽可能保持集合论在数学中的基础地位的都有．由于20世纪数学的发展主流是建立在集合论基础之上，这里只考虑数学家如何消除悖论．在20世纪初，大致有两种办法，一个办法是罗素的分支类型论，它在1908年发表，在这个基础上罗素与怀特海(A．N．Whitehead，1861—1947)写出三大卷《数学原理》(principia Mathematica，1910—1913)，成为数理逻辑最早一部经典著作．还有一个办法是公理方法限制集合，由此产生公理集合论．

　　3．集合论的公理化

　　康托尔本人没有对集合论进行公理化．集合论公理化是策梅罗(E．Zermelo，1871—1953)在1908年发表的．富兰克尔(A．Fraenkel，1891—1965)等人曾加以改进，形成著名的ZF系统，这是最常用的一个系统，因此大家都希望从中推出常用的选择公理(1904年策梅罗引进它来

　　 设与ZF系统是相容的．1963年，柯亨(P．Cohen，1934—)发明“力迫法”证明这两条“公理”的否定也不能在ZF系统中证明，从而推出其独立性．

　　4．希尔伯特纲领

　　为了使数学奠定在严格公理化基础上，1922年希尔伯特提出希尔伯特纲领，首先将数学形式化，构成形式系统，然后通过有限主义方法证明其无矛盾性．

　　1928年希尔伯特提出四个问题作为实现其纲领的具体步骤：

　　(1)分析的无矛盾性．1924年阿克曼(W．Ackermann，896—1962)和1927年冯·诺伊曼(J．Von Neumann，1903—1957)的工作使希尔伯特相信只要一些纯算术的初等引理即可证明分析的无矛盾性．

　　1930年夏天，哥德尔开始研究这个问题，他不理解希尔伯特为什么要直接证明分析的无矛盾性．哥德尔认为应该把困难分解：用有限主义的算术证明算术的无矛盾性，再用算术的无矛盾性证明分析的无矛盾性．哥德尔由此出发去证明算术的无矛盾性而得出不完全性定理．

　　(2)更高级数学的无矛盾性．特别是选择公理的无矛盾性．这个问题后来被哥德尔在1938年以相对的方式解决．

　　(3)算术及分析形式系统的完全性．这个问题在1930年秋天哥尼斯堡的会议上，哥德尔已经提出了一个否定的解决．这个问题的否定成为数理逻辑发展的转折点．

　　(4)一阶谓词逻辑的完全性，这个问题已被哥德尔在1930年完全解决．

　　这样一来哥德尔把希尔伯特的方向扭转，使数理逻辑走上全新的发展道路．

　　5．哥德尔的三项重大贡献

　　除了连续统假设的无矛盾性之外，哥德尔在1929—1930年证明下面两大定理：

　　(1)完全性定理：哥德尔的学位论文《逻辑函数演算的公理的完全性》解决了一阶谓词演算的完全性问题．罗素与怀特海建立了逻辑演算的公理系统及推演规则之后，数学家最关心的事就是公理系统的无矛盾性及完全性．所谓完全性就是，每一个真的逻辑数学命题都可以由这个公理系统导出，也就是可证明．命题演算的完全性已由美国数学家波斯特(E．Post，1897—1954)在1921年给出证明．而一阶谓词演算的完全性一直到1929年才由哥德尔给出证明．

　　(2)不完全性定理：这是数理逻辑最重大的成就之一，是数理逻辑发展的一个里程碑和转折点．

　　哥德尔证明不完全性定理是从考虑数学分析的无矛盾性问题开始的．1930年秋在哥尼斯堡会议上他宣布了第一不完全性定理：一个包括初等数论的形式系统，如果是无矛盾的，那就是不完全的．不久之后他又宣布：如果初等算术系统是无矛盾的，则无矛盾性在算术系统内不可证明．

　　哥德尔的不完全定理造的是一个不自然的数论问题，数学家一直希望在一阶皮亚诺算术中找到一个数学表述既简单又有趣的数论问题，就像哥德巴赫猜想或费马大定理来说明算术的不完全性．这一直到1977年才由巴黎斯(J．Paris)等人造出，这更加证明希尔伯特纲领是不可能实现的．

　　6．哥德尔以后的数理逻辑．哥德尔的不完全性定理从根本上动摇了数学的基础，它指出绝对的无矛盾性的证明是不可能实现的，数学家只能限制自己的领域及要求．数理逻辑也成为一个专门的学科，它分成四大分支：证明论、递归论、公理集合论及模型论，它们都在30年代发展起来．证明论仍然继续希尔伯特纲领，但不得不放宽有限主义的条件．其中最主要的成就是根岑(G．Gentzen，1909—1945)在1934年用超穷归纳法证明自然数算术的无矛盾性．递归论也奠定基础，1935年克林尼(S.Kleene，1909—1994)定义一般递归函数，1936年图林(A．Tuˉring，1912—)提出图林机概念．同年车尔赤(A．Church1903—)提出车尔赤论点：任何有效可计算函数均等价于一般递归函数．递归论与数学关系至为密切，它不仅为计算机科学奠定基础，同时一系列判定问题则直接涉及数学基本问题：如群的基本问题是问什么时侯两个群同构，对于有限表出群是1908年提出的，到50年后，苏联数学家阿其扬(C．И．Aдьян，)在1957年及以色列数学家拉宾(M．O．Rabin，)在1958年独立证明这问题是不可解的．在这个基础上，小马尔科夫(A．A．MapkoB，1903—1979)证明拓扑学的基本问题——同胚问题也是不可解的，1970年最终证明希尔伯特第十问题是不可解的．模型论首先是处理真假问题，它指出一系列命题在某些模型下为真，而在另外模型下非真．其次它构造一批非标准模型．1934年斯科仑(T．Skolem，1887—1968)给出整数的非标准模型，1961年鲁宾逊(A．Robinson，1918—1974)提出非标准分析，使莱布尼茨的无穷小合法化，创立了非标准数学．