1绪言预备知识.docx

1绪言预备知识.docx

《1绪言预备知识.docx》由会员分享，可在线阅读，更多相关《1绪言预备知识.docx（8页珍藏版）》请在冰点文库上搜索。

1绪言预备知识

绪言（课程介绍）

什么是逻辑？

命题（判断）对象、以及对象间的（推理）关系。

数理逻辑：

用数学的方法研究逻辑。

数理逻辑研究分支：

模型论、集合论、递归论、证明论。

数理逻辑研究什么？

逻辑推理：

当前提为真时，保证结论为真。

逻辑研究这样的可推理关系。

即，前提和结论之间的推理关系是否正确。

演绎推理---演绎逻辑。

它不同于归纳逻辑。

归纳逻辑是从前提出发，使用归纳推理，得到的结论与自身协调，或与前提协调。

数理逻辑属于演绎逻辑范围。

只研究推理及可推理关系，不关心前提与结论中各个命题的真假。

例1.前提：

所有大于2不被自身整除的自然数为素数。

7不被自身整除。

结论：

7不是素数。

例2.前提：

所有中学生打网球。

王君不打网球。

结论：

王君不是中学生。

命题有内容和形式：

内容决定命题的真或假。

决定前提和结论之间的可推导关系，是命题逻辑形式。

如：

前提：

集合S中的所有元素具有R性质。

a不具有R性质。

结论：

a不是S中元素。

命题的陈述需要语言。

元语言：

描述对象的所用的最基本语言。

如：

自然语言（汉语）。

对象语言：

描述“对象所用元语言”的语言。

如：

形式语言（符号语言）。

自然语言中语言上的相似并不保证逻辑形式上的相同。

例1：

X认识Y。

（前提）

Y是足球队长。

（前提）

X认识足球队长。

（结论）

例2：

X认识A班某学生。

（前提）

A班某学生是足球队长。

（前提）

X认识足球队长。

（结论）

近代数理逻辑思想：

Leibniz力图建立一种精确的、普适的科学语言作为形式语言。

直到1879年，Frege才建立了这样的语言。

近代数理逻辑介绍的就是这种形式语言。

所以，数理逻辑史从1879年算起。

在数理逻辑中要构造一种符号语言来代替自然语言，这种人工构造的符号语言称为形式语言。

对象的描述和对象间的推理关系全部用形式语言表示。

数理逻辑研究的主要内容：

（1）引入一个形式语言，以表示非结构化对象。

并且要求表示公式的语言是递归生成的。

（2）引入一套形式化推理规则，基于这些规则进行符号化演算。

引入形式证明的一般形式。

（

）

（3）引入一套解释系统---语义（映射）函数，赋予形式符号在给定环境下的具体含义。

（4）基于语义模型，引入逻辑推理概念。

（

）

（5）研究形式推理与逻辑推理之间的关系。

（可靠性和完备性）。

形式推理系统的可靠性：

。

形式推理系统的完备性：

。

一般，逻辑中的语言和推理是某类智能推理的抽象，语言解决表示问题（即，数据结构问题）。

从某种意义上讲，应该是先有具体实例，想找一种一般描述，这就产生了形式语言和形式推理。

实例数据对形式符号给出一种解释（或赋值）。

两者之间的映射关系形成一个解释系统。

实例数据与形式符号有解释（或赋值）和被解释（或赋值）之分。

如：

a:

=0.可以理解为：

将数字0赋给符号a.

也可理解为：

a被解释为0.

其中，a是抽象的，而0是具体的。

为什么会有各种逻辑？

由逻辑研究内容，我们可以观察下表：

语法

语义

形式语言

（表达方式和能力）

解释系统

语义（映谢）函数

形式推理：

逻辑推理：

可靠性：

完备性：

在表中，形式语言、解释系统、推理规则是可变的。

（1）当形式语言的表达能力不够用时，新的语言就会出现。

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

（3）不同的解释系统，给出不同的语义模型。

思考题：

1、逻辑研究的主要内容。

2、为什么会有各种逻辑？

第一章预备知识

集合：

某些对象全体。

集合表述方式：

内涵：

元素具有的性质P。

外延：

所含元素的全体。

自然数集合N上的二元关系<（作为集合）：

（内涵）m

存在不为0的自然数x,使得m+x=n。

（外延）{（0，1），（0，2），……}

二元关系的性质：

自反，对称，等价，……。

集合等势：

可数无限集：

与自然数集等势的集合。

可数集：

有限集或可数无限集。

定理：

（1）可数集的子集仍然可数。

（2）有限个可数集的并仍为可数集。

（3）可数个可数集的并仍为可数集。

自然数集合N的归纳定义：

（1）

.

（2）如果

，则（后继）

。

（3）N只含通过

（1）

（2）有限次使用得到的数。

等价定义：

自然数集合N是满足如下条件的最小集合S

（1）

。

（2）如果

，则（后继）

。

设R是一个性质，

表示x具有性质R。

定理1（数学归纳法）如果

（1）

。

（2）对于任意的

，如果

则

。

则对于任意的

有

。

设h,g为两个N上的己知函数。

递归定义N上一个函数f如下：

（1）

.

（2）

.

定理2（递归原理）对于给定的函数g和h，能唯一定义N上一个函数f满足上述递归条件。

一般集合S的归纳定义：

（1）指定一个集合M。

（基元，生成元）

（2）指定k个函数

为生成函数.分别为

元函数。

归纳定义.集合S是满足如下条件的最小集合T：

（1）

。

（2）对于每个

，

如果

，则

。

设

为k+1个己知基函数：

.

递归原理定义S上的一个函数f:

定理3（递归原理）对于给定的函数

，能唯一定义S上一个函数f满足上述递归条件。

归纳系统：

。

递归系统：

。

例：

自然数（算术）系统