数理逻辑-余俊伟（二） (5-2)

3.3.5 公式的范式

此节先讲了逻辑等价替换定理、逻辑等价易字定理。

范式：前束范式、埃尔布朗范式、斯库伦范式等。

3.4 公理系统

3.4.1 公理系统

为定义必然推出，引入一阶公理系统，分为公理和（有穷）推理规则。有很多种一阶公理系统但一般都等价。

常见两个公理系统：希尔伯特公理系统（公理多、推理规则少、线性结构）、根岑自然演绎系统（公理少、推理规则多、树形结构）。

常见公理和推理规则：命题公理、代入公理、分配公理、等词公理、概括公理、分离规则MP。

如前所述，推理规则是指从有穷个命题推出某个命题的简单直接的规则。具体到一 阶语言上，推理规则就是指从某个有穷的 L1 的公式集推出某个 L1-公式的简单直 接的规则。而公理是直接得到某个 L1-公式，它可以看作从 ∅ 推出某个 L1-公式的 规则。从这个意义上讲，公理都可以被看作推理规则。

由于推理规则就是指从有穷个命题推出某个命题的简单直接的规则，加之绝大多数 推理规则都是保真的，所以绝大多数推理规则都可以转换成某个逻辑有效式，这就 意味着绝大多数推理规则也可以被看作公理。

3.4.2 证明与演绎

几何证明一般有两种：初等几何从公理出发推出某个结论，这是一种无假设的证明；高等几何则有假设。在一阶逻辑中，无假设叫证明，有假设叫演绎。演绎这个词出自《朱子语类》卷六七：汉儒解经，依经演绎；晋人则不然，舍经而自作文。

注意区分定理、非定理、元定理（元语言中的定理）、内定理（对象语言中的定理）。了解语法蕴含、语法等价等概念。语法蕴涵符号是证明符号的推广，而演绎概念也是证明概念的推广。

3.4.3 重要元定理

演绎序列太长，因此此简化：已经证过的定理编号后列入证明中。但还是太长，就总结元定理和演绎规则。

例如（作为定理或推论）演绎、反证法、假言易位、归谬法、概括、语法等价替换定理、语法等价易字定理等。

3.4.4 演绎规则

例如全称量词引入规则、存在量词引入规则、量词消去规则、等词规则、代入规则等。

3.4.5 逻辑与理论

一阶理论是一阶逻辑的推广。

3.5 完全性定理

即 Γ ⊨ φ 当且仅当 Γ ` φ（符号没打出），这就是本节所要证明的（可数的）哥德尔完全性（Compleness）定理。严格说来，(⇐) 是可靠性（Soundness）定理，而 (⇒) 才是（可数的）哥德尔完全性定理。用亨金构造法证。

3.5.1 可靠性定理

（可靠性）. 设 Γ 是公式集，φ 是公式。如果 Γ ` φ（符号没打出），那么 Γ ⊨ φ。

3.5.2 可满足定理

先给出极大一致集的概念。

（可满足）. 设 Γ 是 L1 的公式集。如果 Γ 是亨金完全的且极大一致的，那么 Γ 是可满足的。

整体思路：先定义一个基于 Γ 的等价关系 ∼Γ，然后借助这个等价关系定义一个模 型 (M, v)，最后证明这个模型就是 Γ 的模型。

3.5.3 可扩张定理‬

可扩张定理断言断言的是所有一致的公式集都可以扩张成亨金完全的、极大一致的公式集。设 Γ 是 L1 的公式集，φ 是公式，c 不在 Γ 的任一公式中出现且 φ(c) 是自 由代入。如果 Γ ` φ，那么 Γ ` ∀xφ(c; x)。

3.5.4 完全性定理

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。