数理逻辑(讲义)

2024年1月15日发(作者：考研三数学试卷分数分布)

数理逻辑（讲义）

《数理逻辑》教案

许道云

(2021.8)

教 材：《面向计算机科学的数理逻辑》(第二版)

(陆钟万著)

出版社：科学出版社

版 本：2021年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 可靠性：?|?A??|?A 完备性：?|?A??|?A

在表中，形式语言、解释系统、推理规则是可变的。 (1) 当形式语言的表达能力不够用时，新的语言就会出现。

(2) 不同规则系统的引入，直接关系到形式推理的能力说、有效性、以及单调性等。

(3) 不同的解释系统，给出不同的语义模型。 思考题：

1、逻辑研究的主要内容。 2、为什么会有各种逻辑？

语义 解释系统 语义(映谢)函数 逻辑推理：?|?A

3

第一章 预备知识

集合：某些对象全体。 集合表述方式：

内涵：元素具有的性质P。 外延：所含元素的全体。

自然数集合N上的二元关系

二元关系的性质：自反，对称，等价，……。 集合等势：S~T?|S|?|T| 可数无限集：与自然数集等势的集合。 可数集：有限集或可数无限集。|S|?|N| 定理：（1）可数集的子集仍然可数。

（2）有限个可数集的并仍为可数集。 （3）可数个可数集的并仍为可数集。 自然数集合N的归纳定义： （1） 0?N.

（2）如果n?N，则（后继）n\'?N 。

（3）N只含通过（1）（2）有限次使用得到的数。 等价定义：自然数集合N是满足如下条件的最小集合S （1）0?S 。

（2）如果n?S，则（后继）n\'?S 。 设R是一个性质，R(x)表示x具有性质R。 定理1（数学归纳法）如果 （1）R(0)。

（2）对于任意的n?N，如果R(n) 则 R(n\')。 则对于任意的n?N 有R(n)。

设h,g为两个N上的己知函数。递归定义N上一个函数f如下：

4

感谢您的阅读，祝您生活愉快。