数理逻辑(讲义).pdf

《数理逻辑》教案 许道云 (2011.8) 教 材：《面向计算机科学的数理逻辑》(第二版) (陆钟万著) 出版社：科学出版社 版 本：2006 年6 月第8 次印刷 绪言（课程介绍） 什么是逻辑？命题（判断）对象、以及对象间的（推理）关系。 数理逻辑：用数学的方法研究逻辑。 数理逻辑研究分支：模型论、集合论、递归论、证明论。 数理逻辑研究什么？ 逻辑推理：当前提为真时，保证结论为真。 逻辑研究这样的可推理关系。即，前提和结论之间的推理关系是否正确。演绎推理 演绎逻辑。 它不同于归纳逻辑。归纳逻辑是从前提出发，使用归纳推理，得到的结论与自身协调， 或与前提协调。 数理逻辑属于演绎逻辑范围。只研究推理及可推理关系，不关心前提与结论中各个命题 的真假。 例1. 前提：所有大于2不被自身整除的自然数为素数。 7不被自身整除。 结论：7不是素数。 例2. 前提：所有中学生打网球。 王君不打网球。 结论：王君不是中学生。 命题有内容和形式：内容决定命题的真或假。决定前提和结论之间的可推导关系，是命题逻 辑形式。如： 前提：集合S中的所有元素具有R性质。 a不具有R性质。 结论：a不是S中元素。 命题的陈述需要语言。 元语言：描述对象的所用的最基本语言。 如：自然语言（汉语）。 对象语言：描述 “对象所用元语言”的语言。 如：形式语言（符号语言）。 自然语言中语言上的相似并不保证逻辑形式上的相同。 1 例1：X认识Y。（前提） Y是足球队长。（前提） X认识足球队长。（结论） 例2：X认识A班某学生。（前提） A班某学生是足球队长。（前提） X认识足球队长。（结论） 近代数理逻辑思想： Leibniz力图建立一种精确的、普适的科学语言作为形式语言。直到1879年，Frege才建 立了这样的语言。近代数理逻辑介绍的就是这种形式语言。所以，数理逻辑史从1879年算起。 在数理逻辑中要构造一种符号语言来代替自然语言，这种人工构造的符号语言称为形式 语言。 对象的描述和对象间的推理关系全部用形式语言表示。 数理逻辑研究的主要内容： （1）引入一个形式语言，以表示非结构化对象。并且要求表示公式的语言是递归生成的。 （2）引入一套形式化推理规则，基于这些规则进行符号化演算。引入形式证明的一般形式。 (| A ) （3）引入一套解释系统语义(映射)函数，赋予形式符号在给定环境下的具体含义。 （4）基于语义模型，引入逻辑推理概念。(| A ) （5）研究形式推理与逻辑推理之间的关系。 （可靠性和完备性）。 形式推理系统的可靠性：| A | A 。 形式推理系统的完备性：| A | A 。 一般，逻辑中的语言和推理是某类智能推理的抽象，语言解决表示问题(即，数据结构问 题)。从某种意义上讲，应该是先有具体实例，想找一种一般描述，这就产生了形式语言和形 式推理。实例数据对形式符号给出一种解释(或赋值)。两者之间的映射关系形成一个解释系 统。 实例数据与形式符号有解释(或赋值)和被解释(或赋值)之分。 如：a:=0. 可以理解为：将数字0 赋给符号a. 也可理解为：a 被解释为0. 2 其中，a 是抽象的，而0 是具体的。 为什么会有各种逻辑？ 由逻辑研究内容，我们可以观察下表： 语法 语义 形式语言 解释系统 (表达方式和能力) 语义(映谢)函数 形式推理：| A