逻辑：表达力与复杂性之间的平衡，本文主要内容关键词为：复杂性论文,逻辑论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
中图分类号：B81 文献标志码：A 文章编号：1672-7835(2015)03-0025-06 doi:10.13582/j.cnki.1672-7835.2015.03.005 逻辑的主要任务是研究定义、推理或证明(或计算)。但是逻辑语言和形式系统的构造往往要求在表达力和复杂性之间获得一种平衡。一般说来，一个形式系统能够表达的东西越多，这一形式系统的例举也就变得越难理解。判定问题由此变得难以回答，甚至最终成为不可判定的。从历史上看，起源于类型论的一阶逻辑，为了获得可公理化以及模型之间的更好的转换性质而放弃了表达力。同样的现象也出现于稍后的从一阶逻辑到模态语言的转换。这种转换体现为放弃更大的表达力，但却收获了可判定性，以及为模态语言发现一种良结构不变性，即互模拟性。 显然，作为逻辑系统具有反变关系的这样一组概念，逻辑学家经常要在表达力和复杂性之间做出取舍。不仅如此，在涉及何为逻辑、逻辑是一元的还是多元的、如何评价一种逻辑理论的优劣、逻辑系统之间的元逻辑性质比较等问题上，都会以种种形式与这对概念发生关系。本文以一阶与二阶逻辑为例，从数学哲学和语言哲学的角度分析逻辑在表达力和复杂性方面的一般特征，以及不同的逻辑学家面对表达力和复杂性问题时的不同选择。 1 一阶逻辑与二阶逻辑 首先应当说明的是，与大多数一阶学科的科学不同，逻辑本质上并不是一阶学科。这里的一阶学科指的是物理学、化学、生物学、地质学、地理学、经济学、心理学、社会学等，它们解释实在的一个特定的领域，因而它们是直接关系到世界的。尽管这些学科中也有某些属于二阶学科的方法论的考虑，本质上它们仍属于一阶学科。按照这样一种用法，逻辑、数学和哲学都不是一阶学科。这并不是说这些学科不是关于世界的，而是说它们是关于世界的二阶性质或概念的。但既然逻辑不是一门一阶学科，它为什么又称为一阶逻辑呢？ “一阶”主要是与语言有关的。一语言是一阶的，仅当它含有一阶变项而无其他变项。一个语言是二阶的仅当它含有一阶和二阶变项而无其他变项。一个语言是高阶的，当且仅当它是二阶的。 一阶形式语言的研究被称为一阶逻辑，或者初等逻辑。一阶逻辑是最简单、最富应用性的现代逻辑的分支。作为一种自然的或者直觉上给定的逻辑。不论是日常自然语言的论证还是来自于数学的论证都广泛采用了一阶语言的论证模式。一阶逻辑是研究有效性的好的工具。一阶语言也捕捉到了自然语言语义学的某些重要特征，所以一阶语言逻辑也是研究自然语言语义学的工具。作为一个逻辑系统，它构成了现代逻辑的基础和大部分的内容。一阶逻辑有一个被良好研究的证明论和模型论，有若干有趣的性质：根据哥德尔完全性定理，一阶逻辑是一个有完全、可靠、而又能行的演绎系统D：如果T由某个一阶语言中的公式组成并且G是该语言中的单个公式，那么G在D中从T可推演当且仅当T的任一模型都满足G。由此可见，一阶逻辑是紧致的。对于由一阶公式组成的任一集合T而言，如果T的任一有限子集都可满足，那么T也是可满足的。 但是，一阶逻辑在表达力，尤其是在表达数学家们研究的许多概念方面是能力有限的。根据下降的雷文海姆—斯科伦定理，如果由一阶公式组成的有限或可数无限集T为某个无限模型(个体域为无限集的模型)所满足，那么T也为某个以众自然数为个体域的模型所满足。根据上升的雷文海姆—斯科伦定理，如果T是由一阶公式组成的集合并且对各个自然数n而言，它为至少有n个个体的模型所满足，那么对于各个无限基数k，T也一定为某个个体域基数是k的模型所满足。 这些结果有时称为“局限性定理”，因为它们表明一阶语言在表达资源上的限制。诸如有限性、可数性和良基性等许多中心数学概念都不能在任何一个一阶语言中得到表达，自然数集、实数域以及欧几里得空间等结构也都不能得到充分的描述。 二阶逻辑是一阶逻辑的扩展，而一阶逻辑则是命题逻辑的扩展，高阶逻辑是二阶逻辑和类型论的真扩展。 一阶逻辑在表达力方面的局限性与它仅涉及个体变元(话域中的元素)的量化有直接关系。二阶逻辑的量词除涉及个体之外，还涉及关系。例如，二阶语句
R
x(x∈P∨x
P)表达的是对每一个体的一元关系(或集合)P，以及每一个体x，x或者在P中，或者不在P中(排中律)。二阶逻辑也包括涉及量化函项。 具体地说，与一阶逻辑不同，二阶或者高阶逻辑主要体现为一种语言上的扩展。这种扩展分为两个方向：第一个方向与由非逻辑专门名词组成的集合K有关，它们包括二阶变项、非逻辑谓词、关系和函项名称；第二个方向包含关系的关系、谓词的函项、函项的函项等实体引进的变项。伴随着语言的扩展，二阶逻辑在表达力方面明显增强，尤其是在捕捉中心数学结构及概念的能力方面是一阶逻辑难以企及的。 二阶逻辑的语义学确立了每一个句子的意义。与一阶逻辑只有一种标准语义学不同，二阶逻辑有两种不同的语义学：标准语义学和亨金语义学。这两种中的任意一种，在解释一阶量词和逻辑连接词方面没有什么不同，只是在涉及二阶变元的解释方面二者有所不同。 在标准语义学(也称为完全语义学)中，量词只涉及适当类型的所有集合和函项。因而一旦一阶变元的论域被确定，那么其余量词的意义也就被确定。正是这些语义学给出了二阶逻辑的表达力。 在亨金语义学中，每一种类型的二阶变元有它自己的特定论域，这些论域可以是那些类的所有的集合或者函项的适当子集。配有亨金语义学的二阶逻辑，亨金定义了这些语义学并证明了对一阶逻辑成立的哥德尔完全性定理和紧致性定理。这是因为亨金语义学几乎等同于多类一阶逻辑语义学，这其中附加的变元类型被增加以模拟二阶逻辑的新变元。具有亨金语义学的二阶逻辑并没有超过一阶逻辑的表达力。 二阶逻辑的演绎系统是一推理规则和逻辑公理的集合，该集合确定何种公式序列构成一有效的证明。对二阶逻辑而言若干有效的公理系统可以被使用，尽管对标准语义学而言它们都是不完全的。这些系统的可靠性意味着任何一个它们能够被用于证明的句子在适当的语义学中是有效的。能够被使用的最弱的演绎系统由标准的一阶逻辑(如自然演绎)的演绎系统加二阶词项的替代规则组成。这样一种演绎系统通常用于二阶算术的研究。 2 二阶逻辑的表达力与复杂性 首先，二阶和高阶语言有远强于一阶语言的表达力，在一阶刻画中缺乏的数学概念在二阶语言中都有充分的刻画。例如，存在着一个二阶公式FIN(X)在一结构中可满足当且仅当指派到X的集合是有穷的。这方面的例子包括自然数、实数、欧几里得空间以及集合论。再如，如果论域是所有实数的集合，人们能够在一阶逻辑中断定每一个实数的加法的逆运算的存在，并将其写为
x
y(x+y=0)。但是人们需要用二阶逻辑断定实数集的最小上确界性质，该性质说每一实数的有界的、非空集合有一上确界。如果这论域是所有实数的集合，下列二阶语句表达了最小上确界性质：
这一公式是“每一非空的、有界集合A有一个最小上确界”的语句的直接的形式表达。最小上确界性质不可能被任何在一阶逻辑中的句子的集合所表达，因为实数是适宜于同构满足这种性质的唯一的有序域，反之，按照紧致性定理，在实数中一阶语句有效性的集合有任意大的模型。 再如，在二阶逻辑中，人们可以形式地表达“论域是有穷的”或者“论域是可数基数”这样的句子。为了说出域是有穷的，人们使用“每一从域到其自身满射函项是内射”这样的句子来表达。为了说出域有可数基数，人们使用句子“在每两个域的无穷子集之间存在着一个双射”来表达。由此推出在一阶逻辑中是不可能描述有穷性和可数性的紧致性定理和向上的雷文海姆一斯科伦定理的。一般地说，二阶语言和高阶语言允许语言学家对许多超出一阶语言的语言学结构进行模化。 另一方面，二阶语言的表达力的丰富是有代价的。二阶逻辑不是紧致的，二阶逻辑对雷文海姆—斯科伦定理是失效的。向上的雷文海姆—斯科伦定理失效，因为在那里存在着一个自然数的范畴特征描述AR。每一AR的模型是可数有穷的。向下的雷文海姆—斯科伦定理失效，因为存在着一个实数的二阶范畴特征描述AN，每一个AN的模型有一个连续的基数，且是不可数的。这些特征的推论和哥德尔不完全性定理表明二阶逻辑是不完全的。对二阶逻辑不存在一个有效、完全和可靠的演绎系统。 二阶逻辑是高度复杂的，在某些方面是深奥难懂的。在没有可靠性和递归可数的演绎性方面，二阶逻辑是内在不一致的。的确，二阶逻辑的真并不在分析的等级层列之中。 二阶逻辑后承的难解性是二阶语言表达力的一个直接和不可避免的后果。在一种意义上，逻辑后承的非形式概念是与语句(命题)意味着什么以及语言的词项指称是什么联系在一起的。因而，如果形式语言的目的是为了捕捉非形式的数学话语的语义学内容，特别是，为了复制指称和可满足的概念——因为非形式的数学话语似乎在刻画诸如有限和结构、自然数和实数等方面有资源，而我们的形式语言应当有这方面的表达力——那么，一般认为，二阶语言的难解性和丰富性就是数学语言的丰富性和难解性的一个后果。从这一观点看，人们应当认为数学和逻辑是一个无间隙的整体，在二者之间不可能划出一条直截了当的界限。 3 来自数学哲学支持和反对高阶逻辑的论证 面对表达力和复杂性带来的二难选择甚至数学家也深感困惑。库勒斯典型地描述了这一情形：“众所周知，一阶语言对于表达数学家研究的许多概念能力有限，并且一阶逻辑(拥有)一个开发广泛而解释充分的模型论。另一方面，丰满的二阶逻辑拥有处理数学概念所必须的全部表达力。”[1] 高阶逻辑的拥护者认为，要捕获非形式数学语言的语义，一个逻辑系统应当登记数学结构及概念的常规描述和交流。迫切需要的是形式语言的表达资源应当跟它模拟的数学讨论相匹配。王浩也采取了一种类似的方针：“当我们感兴趣于集合论或者经典分析时，雷文海姆一斯科伦被认为一阶逻辑中的一种缺点……不是说一阶逻辑是唯一可能的逻辑，相反它说的是我们在某种意义上不实现不可数这一概念时，它是唯一可能的逻辑。”[2]154 克雷塞尔在界定二阶公理化数学理论的某些认识论特征时说，他信赖无限多条经由一个公理模式呈现出来的公理是不自然的。例如，假如询问某人他为什么相信一阶实分析完全性模式的各个的实例对实数成立。这位理论家无法为无限多条公理一一给出独立的理由。他也不能断言这模式刻画了实数，因为正如已经看到的那样，任一个一阶理论都不能刻画这一结构。克雷塞尔认为，数学家们相信这模式的实例的理由就在于，各个实例都可从单个的二阶完全性公理推出。在模式的实例上的非形式概括并不显然就比性质或集合在二阶公理中述说清楚的概括更不成问题[3]138-186。 丘奇在他对二阶逻辑的处理时曾经写道：“我们关于一组公式的(标准二阶)后承的定义可以说是与……处理经典数学的要求并无本质的不同……真的，能行性的后承概念……预设某种绝对的、所有关于个体的命题函项的概念。但这也是在经典数学中预设的。”[4]156 巴威思也阐述了类似的思想：“在基础逻辑的学科中，我们试图对体现于作为逻辑常项的‘逻辑概念’与作为数学概念的其他概念之间做出区别。关于是否存在着这样一条界限，或者是否所有的数学概念有它们自己的逻辑的问题，不存在这条区分线画在何处的问题……作为一个逻辑学家，一方面，说服人们相信逻辑是一阶的，另一方面，又说服人们相信一阶逻辑难以捕捉到现代数学中几乎所有的概念，这样做是在危害逻辑的事业。”[5]5巴威思得出的结论是，不可能再回到逻辑是一阶的观点中去。 哲学家也有理由使得逻辑较容易被处理，或者至少比起二阶后承关系要更容易处理。有一种久已存在的观点，逻辑不应有本体论和形而上学的预设。如果这一点难以做到，那么至少这种预设应保持在最低限度。逻辑后承仅仅取决于逻辑小品词的意义。后承关系应当是透明的，潜在明显的。 作为一阶逻辑的直言不讳的支持者，蒯因反对二阶逻辑。他认为：“大部分的逻辑推理发生在并不预设抽象实体的层面上。这种推理主要是通过量词理论(即一阶逻辑)来进行的。它们的法则能够通过不涉及对类变元的量化来表达。通常按照类、关系甚至偶数所明确表达的大多数内容，都可以在量化理论的模式内被重新表述。”[6]68蒯因后来论述道：二阶逻辑并不是逻辑，而是伪装的集合论，是披着羊皮的狼。 当代逻辑学家提出了一种妥协方案，他们设想在一阶逻辑和二阶逻辑之间存在着一种发展逻辑的可能性。哲学家试图在这两种极端之间寻找一种路径，一种不像一阶逻辑那么弱，但至少保留分析性和透明性这种传统的可欲之物。正式地说，逻辑学家希望逻辑系统比起一阶逻辑应有更强的表达力，但是不像二阶逻辑那样难以理解。这就是当代逻辑学家从事逻辑研究的动机之一。 正如我们后面要指出的，联系到一阶与二阶逻辑优与劣的争论的更深层次的问题涉及一个好的逻辑理论的性质是什么，进而，又涉及逻辑理论的目标和目的，涉及逻辑理论被认为应当完成什么。 如果逻辑是一种演算，是推理有效性的标准，那么二阶逻辑超出了逻辑的范围。另一方面，如果人们的目的是编辑正确推理必须遵循的标准，是刻画描述性和交际性的非形式的数学实践的能力，那么二阶逻辑就有存在的空间。 4 来自语言哲学支持和反对高阶逻辑的论证 当语言哲学家在考虑一个特定的逻辑理论时，他们往往特别关注两个问题：首先，是否理论在便利地刻画它的突出问题时其表达力是足够的；其次，是否理论在实施它的推理行为时其推理能力是足够的。如果我们所关心的是实施有效的推理，那么人们希望避免一种理论，该理论有足够强的表达力以至于它们的定理不是递归可数的。根据这种标准一阶系统比起高阶系统更为可取。 不幸的是，在自然语言语义学的情况下，单就一阶逻辑自身而言，它还不能够提供所要求的上述特征。对我们的目的而言它的表达力是不够充分的，这就是张力形成的根源之所在。因为当一个理论的表达力增强时，它的推理能力也相应的增强。例如，表达集合和关系的性质的能力是由进入到高阶理论的方式实现的。有些人可能认为这样做是很自然的，尽管事实是这样一个系统的定理不是递归可数的。 然而如果人们所关心的是形式表达力以及相关的计算问题，那么我们将会重新考虑是否需要一个高阶逻辑的全部表达力。例如，我们可能不需要表达关于所有集合的性质和关系，而仅仅只需要其中的一部分。如果是这样的话，我们就不需要高阶逻辑的全部表达力。我们能够针对当下的问题构造一种逻辑系统，在该系统中它的定理是递归可数的。 以形式语义学为例，精细化内涵逻辑采纳了高阶逻辑的处理，而柯里类型性质理论则给出了一种较弱的形式陈述，该陈述能够表达适宜于自然语言语义学的性质和关系，而无需对一种高阶系统做出明显的承诺。 4.1 支持高阶理论的论证 赞成对自然语言语义学使用高阶逻辑的标准论证认为：对任何一种自然语言语义学的一般理论而言，一阶逻辑似乎是不够充分的，因为它没有充分的表达力。例如，它没有模态概念、内涵概念或者类型概念。对于一个可行的语义学理论而言，这些都是一些必备的要素。这些关切能够通过接纳一种更有力的理论来满足。 诸如蒙太格这种内涵理论通过提供对类型、模态、内涵性、时态以及回指问题的处理而避免了一阶逻辑的弱点。按理说，如果我们在逻辑的表现方面寻求一种能达到形式简单而又统一的效果的话，高阶逻辑的使用就是自然而然的。也许正是基于这样的理由，尽管这一系统的定理集不是递归可数的，高阶逻辑系统毕竟已经支配了自然语言语义学的研究领域。 假定了内涵逻辑模型的组合性，以及自然语言以组合方式转换为内涵逻辑，甚至有可能取消逻辑作为一个表征层面，而只考虑自然语言在集合论的表征。因为集合论为数学提供了基础，这也意味着任何一个能被数学表达的概念也能被集合论所捕捉到。只要能够发现一个适宜的“编码”，数学的充分资源就能够解决任何语义学问题。 最后，如果我们为了处理比例基数(proportional cardinality)量词而引入算术的话，那么你就必须接纳一种强有力的理论，而不考虑这种理论是一阶的还是高阶的，也不考虑定理是否是递归可数的。这一结果与我们是否用关于集合的量化来表达基数性量词无关。 4.2 反对高阶理论的论证 如果我们的兴趣在于建立一种实用的自然语言系统，那么就应当适当考虑一种语义理论的计算性质问题。一般而言，像蒙太格的内涵逻辑以及其他高阶逻辑这样有力的逻辑不是递归可数的，即我们不能发现所有的定理的证明。这是这类系统的一个不令人满意的性质。即便如此，人们也会认为这不是避免使用这种有力的逻辑的充分理由。不完全性的问题可以在大多数实用考虑的情况下通过诸如对一公式的最大长度施加上界(upper bound)计算设计而避免。但仍存在一些反对高阶逻辑适当性的观点。 有些语言哲学家认为以上给出的有力理论的可接受性和适当性的论证不能应用于自然语言分析的其他方面。有些人认为最有力的理论应当应用于句法的研究，因为它是最有力的理论，因而能够表达它希望表达的任何语法关系。从科学方法论的观点来看，人们倾向于认同能说明经验材料的较弱的理论，因为这样的理论因其使用较少的假说而具有较大的理论解释力。 进一步地说，在某些如集合论这样的一般目的的理论中，偶然给出一个适当结果并不必然意味着我们已经理解了问题的真正本性，或者用具有真知灼见的术语捕捉到了现象。比如说用集合论的概念编码0为空集可能会与我们所希望的目的相混淆。空集也可以作为偶素数集合概念的指称。编码为集合论概念可能使事实上有区别的思想简单地混为同一个东西。 对一个特定的问题可能难以发现一个好的编码。如果这一编码并没有将某些相关现象纳入其中，那么编码所使用的基本理论就难以精确地捕捉到概念。进而人们退而求其次，寻求一种略逊一筹的解决，而这只是因为容易表达罢了。事实上，决定采纳某些有力的一般目的的理论可能会对分析施加某些动机不明的限制。在内涵逻辑中的内涵性的处理可能就是这种情况。 作为一种接纳高阶理论的替代方案，我们可以取一种较弱的系统，通过增加类型、模态和内涵性而增强其表达力。进而所提出的问题就是有多少种手段可输入于相对简单的逻辑而不产生一个像内涵逻辑或集合论这样的有力理论的系统的问题。进而支持和反对高阶逻辑的论证可被描述为：在接纳一个现存的逻辑或者建构一个为特定问题量身定做的逻辑之间做出选择的问题。 收稿日期：2014-12-27
标签：集合论论文; 语义学论文; 自然语言论文; 一阶逻辑论文; 逻辑模型论文; 关系模型论文; 集合运算论文; 关系逻辑论文; 数学论文;
