内容发布更新时间 : 2024/4/28 17:48:19星期一 下面是文章的全部内容请认真阅读。

总复习

本章对高级数理逻辑所讲述的内容总结，并对已经学习的内容进行回顾。在对所讲述的内容回顾之前，首先对整个数理逻辑学科的组成进行回顾，从而使大家有更深刻的认识。

数理逻辑学科

学科发展

从数理逻辑学中衍生出来的学科有很多，如：递归论、可计算理论、模型论、机器证明、知识工程、布尔代数等。这些理论都是以数理逻辑学为基础的。针对数理逻辑本身，由于这些学科的需求产生了很多不同种类的逻辑系统。 数理逻辑的不同种类，基本上都是从经典的逻辑系统中扩展而来的。这种扩展通常有语法扩展和语义扩展。

? 语法扩展：在经典逻辑系统中，扩充一些符号，从而衍生出新的逻辑系统。如模态

逻辑，二阶谓词逻辑等。

? 语义扩展：对逻辑系统中语义的范围等进行扩展，如模糊逻辑等。 数理逻辑通常划分成以下不同种类的逻辑系统：

1、 经典逻辑：传统的命题逻辑、一阶谓词逻辑等。认为世界是黑白的，对于一个命题

非真既假。

2、 模态逻辑：认为世界上任何事情的真假是与时间有着密切的关系的。

3、 多值逻辑：认为世界上的对与错是没有绝对的，命题的真假是可以是多个甚至连续

值的。

4、 非单调逻辑：讨论如何将人类的常识加入到逻辑系统中去。经典逻辑是单调逻辑，

既事实越多，已有的结论不会消失；而单调逻辑中，可能随着事实的增加原有的结论被否定。

体系构成

在高级数理逻辑（计算逻辑）中，每一种逻辑都自成体系。逻辑的体系过程主要包括以下几个方面：

1、 形式系统：用符号的方式来描述一个逻辑系统的构成。类似于形式语言系统。 2、 语义系统：针对形式进行解释的一套体系，这套体系确定了符号的含义的解释方法

和规则。

3、 元理论：对形式系统组成、语义系统特性和形式与语义之间关系进行研究。从而保

证了数理逻辑的初衷（利用数学演算的方法来研究人类思维过程）。

4、 自动化推理：在形式系统的基础上，研究利用计算机自动进行推理的理论和方法。

以及自动推理的效率提高方法和自动推理完备性研究。

形式系统

形式系统构成

形式系统由{∑, TERM, FORMULA, AXIOM, RULE}等5个部分构成，其中 称为符号表，TERM为项集；FORUMULA为公式集；AIXIOM为公理集；RULE为推理规则集。：

1、 符号表∑为非空集合，其元素称为符号。

2、 设∑为∑上全体字的组合构成的集合。项集TERM为∑的子集，其元素称为项；

项集TERM有子集VARIABLE称为变量集合，其元素称为变量。

3、 设∑为∑上全体字的组合构成的集合。公式结FORMULA为∑的子集，其元素称为公式；公式集有子集ATOM，其元素称为原子公式。

4、 公理集AXIOM是公式集FROMULA的子集，其元素称为公理。

5、 推理规则集RULE是公式集FORMULA上的n元关系集合，即

nRULE={r|?n(n是正整数?n?2?r?FORMULA其元素称为形式系统的)}，

****推理规则。

其中公式集和项集之间没有交叉，即TERM∩FORMULA =φ，公式和项统称为表达式。

由定义可知，符号表∑、项集TERM、公式集FORMULA是形式系统的语言部分。而公理集AXIOM、推理规则集RULE为推理部分。

形式系统的重要问题

1、 符号表 为非空、可数集合（有穷、无穷都可以）。 2、 项集TERM、公式集FORMULA、公理集AXIOM和推理规则集RULE是递归集合，

即必须存在一个算法能够判定给定符号串是否属于集合。

3、 形式系统中的项是用来描述研究的对象，或者称为客观世界的。而公式是用来描述

这些研究对象的性质的。这个语言被称为对象语言。定义公式和项产生方法的规则称为词法。

4、 用来描述形式系统中各个部分性质的语言称为元语言。用于研究形式系统的元语言

又被称为元数学。

形式推导

1、 基本概念

演绎结果与定理：设A为FSPC上一公式，集合?为FSPC上一公式集合。称A为?的演绎结果，记为?├A，如果存在一个公式序列：

A1,A2,A3,?,AL(?A)

使得Ai或者为形式系统FSPC的公理，或者为公式集合Γ中的元素，或者或者为

Aj1,Aj2,Aj3,?,Ajn?1(j1,j2,j3,?,jn?1?i)由推理规则r得到；则称A为FSPC的演

绎结果。当???时，称A为定理FSPC上的定理。称A1,A2,A3,?,AL(?A)为A的证明序列。

逻辑等价：公式A和B分别为两个公式，如果A,B满足B├A，且A├B同时成立，则称公式A和B为逻辑等价公式，记为A├│B。即A,B互为演绎结果。 例如：??A├|A，A?B├|B?A，A?B├|B?A。

对偶：设A为FSPC上由联结词?, ?, ?和原子公式构成的公式。在A中交换?和?，以及原子公式和他的否定公式，得到公式A，则称A为A的对偶。

2、 推理基础

（1）公理代入原理：设A(P)为含有变元P的公理（定理同样适用），如果将公式A中的变元P替换为命题变元B，则A(B)仍为公理（定理）； C?((B?C)?C)

（2）等价替换原理：设命题公式A含有子公式C（C为命题公式），如果C├│D，那么将A中子公式C提换为命题公式D（不一定全部），所得公式B满足A├│B。 （3）对偶原理：设A为FSPC上的公式，A为其对偶，则A├│?A。 （4）演绎定理：

设?为任一公式集合, A,B为任意公式,那么：

? ，A├B 当且仅当?├A?B ? ，A╞B 当且仅当?╞A?B

（5）(变量)改名原理

如果公式A中至少一个量词的指导变元和相应的约束变元都改名为另一个相同变元后得到公式A’，则A’为A的改名式； 如果A’是A的改名式，且A’改用的变元在A中无任何出现，那A├│A’

3、 其他推理方法

根据形式系统的性质，给出一些专用推理规则。

''''