对逻辑中的表达力与复杂性之间的平衡进行分析.docVIP

对逻辑中的表达力与复杂性之间的平衡进行分析 　　逻辑的主要任务是研究定义、推理或证明( 或计算) 。但是逻辑语言和形式系统的构造往往要求在表达力和复杂性之间获得一种平衡。一般说来，一个形式系统能够表达的东西越多，这一形式系统的例举也就变得越难理解。判定问题由此变得难以回答，甚至最终成为不可判定的。从历史上看，起源于类型论的一阶逻辑，为了获得可公理化以及模型之间的更好的转换性质而放弃了表达力。同样的现象也出现于稍后的从一阶逻辑到模态语言的转换。这种转换体现为放弃更大的表达力，但却收获了可判定性，以及为模态语言发现一种良结构不变性，即互模拟性。显然，作为逻辑系统具有反变关系的这样一组概念，逻辑学家经常要在表达力和复杂性之间做出取舍。不仅如此，在涉及何为逻辑、逻辑是一元的还是多元的、如何评价一种逻辑理论的优劣、逻辑系统之间的元逻辑性质比较等问题上，都会以种种形式与这对概念发生关系。本文以一阶与二阶逻辑为例，从数学哲学和语言哲学的角度分析逻辑在表达力和复杂性方面的一般特征，以及不同的逻辑学家面对表达力和复杂性问题时的不同选择。 　　1 一阶逻辑与二阶逻辑 　　首先应当说明的是，与大多数一阶学科的科学不同，逻辑本质上并不是一阶学科。这里的一阶学科指的是物理学、化学、生物学、地质学、地理学、经济学、心理学、社会学等，它们解释实在的一个特定的领域，因而它们是直接关系到世界的。尽管这些学科中也有某些属于二阶学科的方法论的考虑，本质上它们仍属于一阶学科。按照这样一种用法，逻辑、数学和哲学都不是一阶学科。这并不是说这些学科不是关于世界的，而是说它们是关于世界的二阶性质或概念的。但既然逻辑不是一门一阶学科，它为什么又称为一阶逻辑呢?“一阶”主要是与语言有关的。一个语言是一阶的，仅当它含有一阶变项而无其他变项。一个语言是二阶的仅当它含有一阶和二阶变项而无其他变项。一个语言是高阶的，当且仅当它是二阶的。一阶形式语言的研究被称为一阶逻辑，或者初等逻辑。一阶逻辑是最简单、最富应用性的现代逻辑的分支。作为一种自然的或者直觉上给定的逻辑。 　　不论是日常自然语言的论证还是来自于数学的论证都广泛采用了一阶语言的论证模式。一阶逻辑是研究有效性的好的工具。一阶语言也捕捉到了自然语言语义学的某些重要特征，所以一阶语言逻辑也是研究自然语言语义学的工具。作为一个逻辑系统，它构成了现代逻辑的基础和大部分的内容。一阶逻辑有一个被良好研究的证明论和模型论，有若干有趣的性质: 根据哥德尔完全性定理，一阶逻辑是一个有完全、可靠、而又能行的演绎系统 D: 如果 T 由某个一阶语言中的公式组成并且 G 是该语言中的单个公式，那么 G 在 D 中从 T 可推演当且仅当 T 的任一模型都满足 G。 　　由此可见，一阶逻辑是紧致的。对于由一阶公式组成的任一集合 T 而言，如果 T 的任一有限子集都可满足，那么 T 也是可满足的。但是，一阶逻辑在表达力，尤其是在表达数学家们研究的许多概念方面是能力有限的。根据下降的雷文海姆-斯科伦定理，如果由一阶公式组成的有限或可数无限集 T 为某个无限模型( 个体域为无限集的模型) 所满足，那么 T 也为某个以众自然数为个体域的模型所满足。根据上升的雷文海姆-斯科伦定理，如果 T 是由一阶公式组成的集合并且对各个自然数 n 而言，它为至少有 n 个个体的模型所满足，那么对于各个无限基数 k，T 也一定为某个个体域基数是 k 的模型所满足。这些结果有时称为“局限性定理”，因为它们表明一阶语言在表达资源上的限制。 　　诸如有限性、可数性和良基性等许多中心数学概念都不能在任何一个一阶语言中得到表达，自然数集、实数域以及欧几里得空间等结构也都不能得到充分的描述。二阶逻辑是一阶逻辑的扩展，而一阶逻辑则是命题逻辑的扩展，高阶逻辑是二阶逻辑和类型论的真扩展。一阶逻辑在表达力方面的局限性与它仅涉及个体变元( 话域中的元素) 的量化有直接关系。二阶逻辑的量词除涉及个体之外，还涉及关系。 　　例如，二阶语句Rx( xisin;Por;xP) 表达的是对每一个体的一元关系( 或集合) P，以及每一个体 x，x 或者在 P 中，或者不在 P 中( 排中律) 。二阶逻辑也包括涉及量化函项。具体地说，与一阶逻辑不同，二阶或者高阶逻辑主要体现为一种语言上的扩展。这种扩展分为两个方向: 第一个方向与由非逻辑专门名词组成的集合 K 有关，它们包括二阶变项、非逻辑谓词、关系和函项名称; 第二个方向包含关系的关系、谓词的函项、函项的函项等实体引进的变项。 　　伴随着语言的扩展，二阶逻辑在表达力方面明显增强，尤其是在捕捉中心数学结构及概念的能力方面是一阶逻辑难以企及的。二阶逻辑的语义学确立了每一个句子的意义。与一阶逻辑只有