一 数理逻辑与数学基础

符号体系[symbolism] 由一系列符号和它们的组合规则构成的集合体。它常被用来替代自然语言对某些知识体系进行描述、分析和研究。使用符号体系来研究数学能使逻辑分析和推导更加严格和清晰，并能避免自然语言中的一语多义现象。(执笔：金人麟校阅：史念东)

数理逻辑[mathematical logic] 又称盈号逻辑。数学的一个分支。处l-数学和哲学(特别是数学哲学)的交叉部分。数理逻辑一方面使用形式逻辑的思想方法研究数学及数学推理的基本原则和规律；另一方面使用数学工具来表示和研究形式逻辑的性质和结构。包含了很多分支和研究方向，其中主要的分支为模型论、证明论、集合论和递归论(即可计算理论)。这四个分支的发展都和哥德尔(K.Godcl)在20世纪30年代完成的工作有着密切的联系。

数理逻辑是伴随着数学公理化进程而4i断发展的。在19世纪后期到20世纪初，弗雷格(G.Fre.ge)和罗素(B. Russell)致力于用符号逻辑替代自然语言来描述数学原理和数学推理，他们发展了命题演算和谓词演算，使得数学更加系统化和严格化，从而使得数学和逻辑成为一体。他们的工作也使得人们更加了解了数学摊导中逻辑语义和逻辑语法的差别。这推动了数学公理化的进程。但在此发展中产生了对数学公理化过J：乐观的倾向，即认为终可以找到一个相容的、完备的公理系统使得所有的数学定理，包括这个公理系统的相容性，都成为这个公理系统的推论。这就是所谓的希尔伯特计划。但是这个倾向却被哥德尔所否定。

哥德尔关于一阶逻辑的完备性定理表明数学中基于语法上的推导和基于语义上的推理是等价的。基于语法上的推导是一个按照一定规则进行的机械过程，它不依赖于原因、结果以及中问过程的具体含义；基于语义下的推理则通过对每一语句在每个数学结构(模型)中的语义解释和真假值来确立原因和结果的关系。哥德尔完备性定理深刻地揭示出数学理论中语法形式推导和语义内容分析推理之间的一致性；也因此展现了模型在数学推理中的作用，促进了模型论的发展。

哥德尔小性定理成功地应用数学推理来分析逻辑的内涵和其局限性，并证明了希尔伯特计划的不可行性，即对于任意一个相容的、包含了弱算术公理的、可判定的公理系统，总存在一个语句使其不能从该公理系统出发来证明或反证。这成为数理逻辑另一分支证明论的起点。

为了解决在引进了无限集合后产生的各种超出当时想象的问题，糜托尔(G.Cantor)建立了朴素集合论。但在罗素发现了著名的罗素悖论后，对朴素集合论进行改造就迫在眉睫。在策梅洛(E.Zermelo)、弗伦克尔(A.Fraenkel)及其他数学家的努力下，集合论的公理系统如策梅洛一弗伦克尔公理系统，在数理逻辑的框架下得以建立。策梅洛一弗伦克尔公理系统的引入避免了罗素悖论。因为策梅洛弗伦克尔公理系统是作为整个数学的基础理论而引进的，它的相容性就得到数学家们的重视。哥德尔对集合论发展的贡献存在于两个方面。一方面，哥德尔第二不性定理证明了从任意一个相容的、包含了算术公理的、可判定的公理系统出发不可能证明其自身的相容性。所以在策梅洛一弗伦克尔公理系统中不可能证明该系统的相容性，从而使人们避免了在策梅洛弗伦克尔公理系统内寻找本系统相容性的无谓努力。另.-方面，哥德尔引入了可构造性和可构造域，从而建立了选择公理和连续统假设与策梅洛弗伦克尔公理系统的相对相容性。这和以后科恩(P.Cohen)利用力迫法证明的非选择公理以及非连续统假设与策梅洛一弗伦克尔公理系统相对相容的结果一起成了现代公理集合论的独立性证明的样本。

哥德尔不性定理证明中的一个重要步骤是分析可证明语句的计算复杂性。哥德尔证明了在一个相容的、包含了弱算术公理的、可判定的公理系统中，所有可证明语句的集合是不可判定的，所以一定存在一个不在该集合中的语句使得此语句的否定也不在该集合中。为了完善对可判定性的描述，丘奇(A.Church)、图灵(A.M.Turing)等提炼出递归函数和图灵可计算性等概念。对这些概念的深入研究促发了递归论的产生和发展。

数理逻辑足一个广泛的领域，以下四个分支并不包含所有数理逻辑的内容。另外如多值逻辑、模糊逻辑、模态逻辑等，都是数理逻辑有趣的组成部分。(执笔：金人麟校阅：史念东)

符号逻辑[symbolic logic] 即数理逻辑。

1.1模型论

模型论bnodel theory] 数理逻辑的一个分支，它丰要研究形式语言及其在模型中的语义解释之间的关系。例如，群论公理是形式语言中有关一个乘法符号.和一个常元符号e的三个语句，即。关于群论公理的一个模型则是一个具体的群，如整数加群、正方形可逆矩阵乘法群、n个元素上的置换群等。群论公理在一个群，如可逆矩阵乘法群中的解释可以叙述为：①e是一个右单位矩阵；②对每个可逆矩阵都存在一个右逆矩阵；③矩阵乘法满足结合律。模型论中的基本定理有哥德尔完备性定理、紧致性定理、勒文海姆一斯科伦定理等。

从20世纪初以来，模型论得到了蓬勃发展，而且模型论的纯理论研究和其在其他数学领域中的应用已经相互交织在一起。稳定性理论是模型论中的一个藁要研究方向。它从初的对理论和模型的分类研究，发展出了很多方法和技巧。这些方法和技巧被应用于解决代数及代数几何中的问题。强极小理论和序极小理论也是模型论中有趣的研究领域。分析利用强极小和序极小模型中可定义集的良好性质，代数闭域、实数域和其他数学结构中的很多新的有趣的现象被揭示出来。非标准分析也是模型论的一部分。利用模型论中的紧致性定理，人们可以构造一个实数域的扩张，使在其中存在无穷大和无穷小的正实数。这些无穷人和无穷小数可以作为工具来帮助人们发现数学中新的现象和定理。模型论中还有很多有趣的研究领域，如抽象模型论、有限模型论、概率模型论、递归模型论等。(执笔：金人麟校阅：史念东)

稳定性理论[stability theory] 见模型论。

逻辑演算[logical calculus] 各种逻辑形式系统的总称。如命题演算、谓词演算等都是逻辑演算。有时逻辑演算还指逻辑推导的一些法则。各种彤式语言可被用于描述各种不同的知识系统，但是逻辑推导的法则应该独立于这些系统的个性。比如从“甲是真”和“甲推出乙”可以推出“乙是真”，就是逻辑演算的一个法则。(执笔：金人麟校阅：史念东)

逻辑符号[logical symbol] 在形式语言中用以表示一些逻辑联结词的符号。例如一(其语义一般为“不”或“否定”)，一(其语义一般为“如果 ，那么 ”或“推出”)，一(其语义一般为“当日.仅当”或“等价于”)，(其语义一般为“和”或“合取”)，V(其语义一般为“或”或“析取”)，等等。(执笔：金人麟校阅：史念东)

形式语言[formal language] 各种有严格定义的人.f=语言的总称。每一种形式语言都包括一个预先设定的词汇表和一些组成公式或语句的形成规则或语法规则。形式语占是人类自然语言的抽象化和理想化。用形式语言来讨论数学和逻辑问题可以避免自然语言中一词多义或一语多义现象带来的不确定性。(执笔：金人麟校阅：史念东)

符号语言[symbolic language] 一种形式语言。其词汇表是由4些符号组成。例如命题逻辑所使用的符号语言词汇表包含了等符号，其中Ai，A2， 被称为命题符号。(执笔：金人麟校阅：史念东)

形成规则[formation rule] 一些在形式语言中组成公式的语法规则。例如命题逻辑中的形成规则包含了以下法则：“对每个正整数k，Ak是一个公式”，“如果p是一个公式，那么-p就是一个公式”，“如果p和q是两个公式，那么p—q，p—q，pAg，pVq也都足公式”。(执笔：金人麟校阅：史念东)

出现[occurrence] 数理逻辑术语。指一个变元或一个子式在表达式中的存在形式。如果一个符号或一串符号被用在了一个公式中的某个部位，这个符号或这串符号就被称为在这个公式中在这个部位的一次“出现”。例如在公式(A2A(A2一Ai))- Ai中符号Ai“出现”了两次。(执笔：金人麟校阅：史念东)

规矩公式[well-formed formula] 曾称良构公式，义称合式公式。指形式语言中按照一定的形成规则而构造出来的符号序列(表达式)。(执笔：金人麟校阅：史念东)

良构公式[weH-formed formula] 规矩公式的旧称。

合式公式[well-formed formula] 即规矩公式。

辖域[scope] 谓词逻辑用语。一个量词(如全称量词Vx)的辖域指的是谓词逻辊公式中这个量词的作用范围。例如，在公式中带下划线的部分是个全称量词的辖域。(执笔：金人麟校阅：史念东)

逻辑运算[logical operation] 逻辑量(逻辑变量或逻辑常量)之间的运算。当逻辑符号被赋弘实际意义时，它们可被看成一种运算。例如，在0-1布尔代数中通常可定义，所以可以被看作一个在0-1布尔代数中的二元运算。这样的运算可以被推广到所有(有限或无限)0-1序列上。这些和逻辑符号对应的运算被称为逻辑运算。(执笔：金人麟校阅：史念东)

矢列式[scqucnt] 形式为A—B的公式。在某些逻辑系统中A可以是一个公式或一串公式。(执笔：金人麟校阅：史念东)

语法[syntax] 在形式语言中，指的是语言、公式和语句组成的规则以及对规则的研究。这些规则通常独立于公式和语句的具体意义。在命题逻辑和谓词逻辑中基于一个公理系统上的。一个形式证明可以被定义为按照一些规则构造的一个有着有限个公式的序列，而这样的构造是机械的，不依赖于公理系统和所要证明结论的具体意义。这样的证明被称为一个语法上的证明。(执笔：金人麟校阅：史念东)

语义[scmantics] 在形式语言中，指的足语言、公式和语句在一定的环境或模型巾的含义以及对语言中公式、语句及其含义之间关系的研究。在命题逻辑和谓词逻辑中，如果对每一个使公式p取真值的模型，公式q在其中都取真值，那么可以称q是p的逻辑结果。这样的从p到q的推论被称为是一个语义上的推论。这是因为这样的推论涉及了公式p和q在模型中的意义。(执笔：金人麟校阅：史念东)

解释[interpretation] 0在形式语言中，指为一个符号、一个公式或一组公式在一个环境或一个模型中赋予特定的意义。例如，在集合论中符号∈在全集域中的解释为“属于”，语句在全集域中的解释为“如果集合A和B含有相同的元素，那么A和B就是相同的集合”。

在谓词逻辑中还有 处用到词语“解释”，即.个理论在另一个理论中的解释。假设孔和Ti足在各自语言Co和Li中的理论。如果Co中的每个符号都可用Li中的公式在孔中来定义，全称量词Vx在死意义下的全域也可以用Li中的公式在2j中来定义，那么Co中的公式都可以在以上的定义下自然地翻译成Li中的公式。如果To昀语句的翻译都是Ti的推论，那么To的翻译就可被称为To在Ti中的一个解释。例如佩亚诺公理系统可以在策梅洛一弗伦克尔公理系统中得到解释。(执笔：金人麟校阅：史念东)

论题[thesis] 被很多证据支持的、其真实性有待被证明的命题。在数理逻辑巾著名的论题可能是.丘奇图灵论题。丘奇论题提出每一个可有效计算的函数都是递归的。图灵论题提出每一个可有效计算的函数都是图灵可计算的，即计算可由图灵机来完成。因为可有效计算性是一个没有严格定义的直觉概念，丘奇论题和图灵论题不被认为是定理，而是论题。丘奇论题和图灵论题被证明是等价的。(执笔：金人麟校阅：史念东)

归纳证明[proof by induction] 数学中一种广泛应用的证明方法。例如，在数学中为了证明具有秩序或有秩偏序的全域中每一元素都有某一性质，可以先证明每一个极小元有这个性质，再证明对任意一个元素，如果每个