【学习目标】 通过本章的学习,应达到如下目标: ◇ 了解一阶语言和一阶理论的概念和定义,了解它们的基本构成。 ◇ 了解理论T协调的含义和充要条件,清楚Godel完全性定理的内容,进而了解一阶理论与模型的关系。 ◇ 了解Lowenheim-Skolem定理的内容和证明思想,以及该定理与Herbrand定理的关系。 ◇ 了解Herbrand域的定义以及Herbrand定理的内容,大致了解定理的证明思路。 ◇ 了解Godel不完全性定理的内容及其重要地位与影响,大致了解定理的证明思路以及其它变形与扩充(第二不完全性定理与广义不完全性定理)。 【学习指南】 本章主要介绍一阶形式理论及其模型的基本概念及重要结论,学习时应注意把握以下几点: ◇ 一阶语言L与一阶理论T之间的关系,基于一阶语言L的理论T称为一阶理论。 ◇ 注意了解形式理论的语法、语义及相互间的关系。一阶形式理论属于语法的范畴,而一阶理论T的模型属于语义的范畴。 ◇ 通过Godel完全性定理理解理论与模型的基本关系,该定理的证明思想是一阶理论发展史上的一个里程碑,为计算机程序理论的形式语义学奠定了基础,证明过程较复杂,通过3个引理铺垫,是学习证明思想的典型例证。 ◇ Lowenheim-Skolem定理和Herbrand方法,提供了谓词逻辑公式的半可判定算法,具有较强的实用性,学习时应注意加以理解,进一步体会半可判定或非确定性算法的含义。 ◇ Godel不完全性定理是数理逻辑的一个重要定理,它的两个变形与扩充(第二不完全性定理和广义不完全性定理)以及证明过程都蕴含着丰富的理论内容,如Godel配数法和对角线定理等,值得深刻理解和体会。 【重点和难点】 ◇ 本章讨论的是一阶形式理论与模型,涉及的理论知识较多,学习中的难点也相对集中。 ◇ 一阶语言理论的基本构成和理论价值应作为重点掌握,相对而言,7.1与7.2两节的内容比较具体,不难理解。 ◇ Godel完全性定理与不完全性定理是本章的两大难点,也是本门课程的难点之最。由于前者阐述了一阶理论与模型的基本关系,后者揭示了一阶形式理论的固有局限性以及语法及语义的关系,具有深刻的理论内涵,在学习和理解中出现困难是很自然的事情。对于理论基础相对薄弱,抽象思维能力不够丰富的学习者来说更会感到十分艰辛或困难重重。在这种情况下,应把学习的重点放在弄清定理的基本结论并了解证明思路上,而不必过于强求。 ◇ 本章因为涉及到几个著名的定理,所以证明过程占据较大篇幅,有些引理、定理的结论十分抽象,因而了解复杂定理的证明思路、过程与方法是本章学习的又一重点,其中可包括如何将一个复杂问题分解为若干个子问题。如何利用多个引理分别解决,最后完成定理的证明。另外,半可判定算法的概念,"项模型"的方法,Godel配数法以及对角线定理的思想都可作为深入学习的重点。 【预习思考题】 ◇ 一阶语言是如何构成的? ◇ 一阶语言与一阶理论之间有什么关系? ◇ Godel不完全性定理究竟阐述了什么内容?在理论上具有哪些重要意义? ◇ Godel完全性定理揭示了什么关系?具有哪些理论价值? ◇ 半可判定算法是什么含义?它可以解决什么问题? |