数理逻辑引论——计算机科学与系统的天然基础

第1章导论 学习一门学问，研究一个领域或一个方向，首先应该溯其本源，明确其基本概念，了解其研究和解决的基本问题，并追踪其发展历程。这有助于学习者明确相关研修的目标，建立研修兴趣，为进一步的深入研究奠定坚实基础。鉴此，本章将介绍逻辑(logic)的基本概念，讨论其研究和解决的基本问题，并简述数理逻辑的发展史。我们也会论及数理逻辑研究中对人类思维及推理规律的思考及其所产生的指导作用，尤其要特别讨论数理逻辑与数学的关系，以及数理逻辑在各个科学与工程领域中所扮演的重要的基础性角色。*后，我们将基于计算理论及计算机科学与技术的视角，阐述数理逻辑在这一特定领域的地位与作用。 本章第1.1节和第1.2节首先介绍数理逻辑的起源、研究的基本问题，相关概念和术语等；第1.3节介绍从亚里士多德逻辑到近代数理逻辑的发展和演化，以及逻辑与数学的关系。*后，第1.4节讨论数理逻辑在计算机科学中的核心基础性地位，以及它对计算科学，尤其是程序语言设计和程序分析验证等领域发展的影响，并展望其对未来一些方向发展的重要性。对这一章的学习可以根据自己的背景选择性地进行：第1.1节和第1.2节对专业知识的假设很少，更适合一般性的读者；第1.3.2节需要一些数学常识，可以结合本书的第2章和第7章学习；第1.4节需要一些计算机科学的概念和知识，该节后面部分关于程序语言语义和程序的形式化验证的讨论需要一些形式化方法的基础知识，计算机专业的读者可以结合自己专业进行研读。本书第8章有对程序语言的语法和语义的介绍，读者可以在研读第8章后再回来读第1.4节。总之，这一章的内容可以在学习本书的过程中反复研读和思考。 1.1逻辑的基本概念和术语 我们在日常生活的言谈中经常用到“逻辑”一词，譬如说“你这是什么逻辑？”，“这不合乎逻辑”，“某某的逻辑性很强”等。但是，如果讲授逻辑课的教授在**节开始时想了解一下学生对逻辑的认识，并请学生们谈谈他们对“什么是逻辑”“逻辑的用途和意义”“逻辑研究什么”等问题的看法。一般情况下，学生们需要经过一定的努力和引导方能归结并提及如下的某些关键术语：断言(assertion)、命题(proposition)、真(true)、假(false)、推理(reasoning)和论证(argument)、证明(proof)、定理(theorem)、矛盾(contradiction)、悖论(paradox)、一致性(consistency)等。再多进行一些尝试和努力，可能会进而提到可靠性(soundness)、合理性(validity)、完备性(completeness)和严密、验证等更高深些的术语。这一情况说明，一般人都有一些与逻辑相关的基本常识。但也非常遗憾，多数计算机专业本科毕业生缺乏对逻辑的系统认知，不清楚上述术语的确切含义及相互间的关系。阅读完这本书以后要达到的一个基本的目标是能够清晰和系统地理解这些术语的定义、内涵和外延，及这些概念之间的相互关系。 为了系统地认识逻辑及其相关问题，我们先考虑一类*简单的逻辑，称为二值逻辑(two-valued logic)。在二值逻辑中，一个命题就是一个或者为真或者为假的陈述句。也就是说，一个命题只有两种可能的“值”，如果它“事实上”成立则其值为真（或简单说它为真），不成立则它为假。下面我们通过一些例句来帮助读者理解命题的二值特征。 例1.1我们不难判断下面几个例句的真假： [例句1]所有人都喜欢吃巧克力。 [例句2]有些人不喜欢吃巧克力。 [例句3]这块黑板是黑色的。 例1.2但我们无法判断如下陈述句是真或假： [例句4]刘备跑得快。 [例句5]这句话是谎言。 例1.2中例句5就是著名的“说谎者的悖论(The Liar’s Paradox)”：如果这句话（“这句话是谎言”）为真，则“这句话”就为假；而如果“这句话”为真，则“这句话是谎言”就应该为假。研究如何避免悖论正是逻辑学兴起的一个重要原因。 逻辑一词本身也是一个多义词，它有时指一个具体的逻辑系统，即由一套逻辑语言、公理和推理规则构成的具体的逻辑。有时却指一种逻辑类别，如：根据不同的推理方式，逻辑可以分为演绎逻辑(deductive logic)和归纳逻辑(inductive logic)；按照不同的哲学理念，又可以分为经典逻辑(classical logic)和直觉主义逻辑(intuitionistic logic)；从表达静态与动态关系的方面考虑，静态的命题逻辑(propositional logic)和谓词逻辑(predicate logic)又可以扩展到相应的模态逻辑(modal logic)；另外还有一阶逻辑(first-order logic)和高阶逻辑(higher-order logic)之分。看到这么多分门别类的逻辑和术语，可能使人对研修数理逻辑有些望而生畏。本章和本书后面的章节将梳理和讨论各种不同逻辑的共同的和基础的性质。 每个具体逻辑系统(logic system)都有一个表达断言或命题的逻辑语言(logic language)，通过一组严格的语法规则(syntactic rule)定义，还有一套规定如何做推理及判断命题真假的公理(axiom)和推理规则(inference rule)。在这样的逻辑（系统）里可以： (1)严格地表述断言或者命题； (2)判断并确定命题的真值(truth value)，或说其为真还是为假； (3)进行推理论证，以确定断言的真假和推理本身的合理性； (4)从一组断言演绎出（或说推导出）另一些断言，或者确定一些断言是否为以另一些断言为假设的正确结论，或者确定推演过程的正确性。 在一个逻辑系统中，上述(1)(4)都必须能按严格的规则，通过一些机械步骤完成，而不能是通过试错或依靠直觉来完成。这种过程必须是可重复的，其正确性可以根据规则机械地检验。本节**段中提到的术语，基本都是与所有逻辑系统相关的基本概念。在理想情况下，一个逻辑系统应该具有如下的基本性质： (L1)有严格的语法，保证断言满足语法正确性，能严格、机械地检查； (L2)有严格的公理、推理规则及推理过程的定义，保证推理过程的构造的正确性，能严格、机械地检查； (L3)公理和推理规则都是有效的，也称可靠性(sound)，是指由公理和推理规则证明的定理都是真的，在正确的前提下，推理的结果也是正确的。 (L4)推理系统是一致的，是指使用推理系统的公理和推理规则不会推导出相互矛盾的结论。一致性也称为协调性和相容性。注意，有效性保证一致性，但反之不成立。 (L5)公理、推理规则的推理能力足够强大，也称推理系统有充分的推理能力，能推导出所有为真的命题。这一保证称为该逻辑系统的充分性/完全性(adequacy)。 这里“机械”的意思可以理解为存在自动完成该项工作的计算机算法或程序。 本书将讨论一些常见的、有广泛应用的逻辑系统的构建，帮助读者学习并练习在这些逻辑中进行推理和论证，掌握主要的逻辑论证方法，学习如何定义和证明一个逻辑的可靠性和完备性，从中理解逻辑论证、逻辑系统的可靠性、充分性和相容性的重要意义。 1.2逻辑学 根据牛津字典的解释，逻辑(logic)一词源于希腊语 logikē，意指推理的艺术(art of reasoning)。作为一门学问，逻辑学*初属于哲学的范畴，数学也如此。即便今天，数学学士和硕士在牛津大学、剑桥大学等一些西方大学仍属于人文学科（Arts）的学位。逻辑学的内涵是研究思维的规律。人们认为，思维的三种基本形式是：概念、命题和推理。命题也称为断言，推理也称为论证或证明。 1.2.1概念与命题 概念是对一个事物、现象或想法的抽象表述和定义。一个概念具有两个基本特征，即概念的内涵(intention)和外延(extension)。内涵是对概念所指称的对象（类别）的意义、目的和本质的抽象描述；外延则指满足概念定义的所有对象或实例。概念具有结构性和层次性，一个概念可以由其他概念定义，或由其他概念的外延中的对象定义，一个概念也可能是另一个概念外延中的个体对象。逻辑中的命题就是刻画分析概念之间这种结构性和层次性关系，逻辑中的推理证明就是分析和判断这些命题的真或假的过程。 定义1.1(命题)一个简单命题是对某概念的某种属性或几个概念的相互关系的一个陈述，或是描述概念外延中的对象性质或几个概念的外延中对象之间关系的一个语句，表述对象是否具有某种性质。根据概念的定义和对象的属性可以判定一个命题的真值，即该命题的成立与否。命题是一个有主语和谓语的句子，主语亦称为主项(subject term)，谓语也称为谓项(predicate term)。 例1.3例如，如果“大学生”这个概念的内涵是指在大学中为获取学位而学习的人，且学生的属性包括“性别”“年龄”“所修课程”等，则如下的各个陈述都是命题： [例句6]张三是大学生。 [例句7]李四不是大学生。 [例句8]所有大学生都修了 Java 程序课。 [例句9]所有大学生都没有修逻辑课。 [例句10]有些大学生是18岁以上。 [例句11]有些大学生不是18岁以上。 上面例子显示了一个命题可涉及多个概念，而且一个概念也可由其他概念所定义。命题可以是特称命题(particular proposition)，如上面的例句6和7；也可以是全称命题，如上面的例句8和9。上面的例句10和11也称为存在命题。存在命题也属于特称命题，因为它们陈述的事实是针对某个（某些）未予明示的特定对象，而不是全部对象。根据命题中谓词的情况又可以将其分类为肯定命题和否定命题，这样就可以分出四种简单命题：全称肯定命题、全称否定命题、特称肯定命题和特称否定命题。除了简单命题，我们还可以表达更复杂的命题，称为复合命题(composite proposition)。 例1.4下面是几个复合命题： [例句12]张三是大学生，而且张三 Java 程序课的成绩是95分。 [例句13]李四是大学生，而且李四 Java 程序课的成绩不到85分。 复合命题是由简单命题通过连接词(connective)组合而成。进一步说，上面的“大学生”概念可以通过（已知的）概念“人”来定义的，即“大学生”是“人”的一个子概念。概念 A 的一个子概念 B 定义了一个对象集合，其中的对象也是其（超）概念 A 的实例。故如下命题是真。 [例句14]如果张三是大学生，则张三是人。 这个命题是用连接词“如果则 ”将简单命题“张三是学生”与“张三是人”连接而构成的复合命题。在面向对象的软件技术中，概念用类(class)表示。这样，子概念就是子类(subclass)，超概念就是超类(superclass)。一个类定义一个对象集合，一个子类的任何对象也是其超类的对象。 本章接下来的部分不再进一步讨论连接词和复合命题。 1.2.2推理论证 推理是论述一个命题的“合理性”或说“正确性”的过程，通常表示为一个有穷的命题序列。序列的*后一个命题称为该推理的结论(conclusion)，其余命题为其前提(premise)。我们希望推理中出现的每个命题都有清晰的证据说明其“言之有理”，如果确实如此，就说这一推理是有效的。 例1.5下面是一些表示推理的命题序列，其中前提之间用逗号分隔，分号之后是结论： [推理1]张三是大学生；所以，张三是人。 [推理2]所有的人都会死，苏格拉底是人；所以，苏格拉底会死。 [推理3]所有大学生都是人，张三是大学生；所以，张三是人。 [推理4]有