一阶逻辑：语法与语义
1. 引言
一阶逻辑（First-Order Logic，FOL）是数学、计算机科学和哲学中用于表达和推理的基本工具。它扩展了命题逻辑，允许我们量化个体和谓词，从而更精确地描述复杂的关系和结构。在本章中，我们将深入探讨一阶逻辑的语法和语义，包括符号表、项与公式的归纳定义、解释与结构、模型与有效性等核心概念。
2. 核心概念讲解
2.1 符号表
一阶逻辑的符号表包括以下几类符号：
- 常量符号：表示特定的个体，如
a,b,c。 - 变量符号：表示任意的个体，如
x,y,z。 - 函数符号：表示个体之间的映射关系，如
f,g,h。 - 谓词符号：表示个体之间的关系或属性，如
P,Q,R。 - 逻辑连接词：如
¬（非）、∧（与）、∨（或）、→（蕴含）、↔（等价）。 - 量词：如
∀（全称量词）、∃（存在量词）。
2.2 项与公式的归纳定义
2.2.1 项的定义
项（Term）是表示个体的表达式，其归纳定义如下：
- 基础情况：任何常量符号或变量符号都是项。
- 归纳步骤：如果
f是一个n元函数符号，且t₁, t₂, ..., tₙ是项，那么f(t₁, t₂, ..., tₙ)也是项。
2.2.2 公式的定义
公式（Formula）是表示命题的表达式，其归纳定义如下：
- 原子公式：如果
P是一个n元谓词符号，且t₁, t₂, ..., tₙ是项，那么P(t₁, t₂, ..., tₙ)是原子公式。 - 复合公式：
- 如果
φ和ψ是公式，那么¬φ,φ ∧ ψ,φ ∨ ψ,φ → ψ,φ ↔ ψ也是公式。 - 如果
φ是公式，且x是变量，那么∀x φ和∃x φ也是公式。
2.3 解释与结构
解释（Interpretation）为一阶逻辑的符号赋予具体的意义。结构（Structure）是解释的数学表示，包括：
- 论域（Domain）：一个非空集合，表示所有个体的集合。
- 常量解释：为每个常量符号指定论域中的一个元素。
- 函数解释：为每个函数符号指定论域上的一个函数。
- 谓词解释：为每个谓词符号指定论域上的一个关系。
2.4 模型与有效性
- 模型（Model）：如果一个结构使得某个公式在该结构下为真，则称该结构是该公式的模型。
- 有效性（Validity）：如果一个公式在所有可能的解释下都为真，则称该公式是有效的。
3. 实例和练习
3.1 实例
实例 1：考虑一阶逻辑语言，其中包含常量符号 a，一元函数符号 f，二元谓词符号 P。构造一个公式 φ 表示“对于所有 x，存在 y 使得 P(f(x), y) 为真”。
解：
φ = ∀x ∃y P(f(x), y)
实例 2：给定结构 M，论域为自然数集，a 解释为 0，f 解释为后继函数，P 解释为小于关系。验证公式 φ 在 M 下是否为真。
解：
在 M 下，φ 表示“对于所有自然数 x，存在自然数 y 使得 x+1 < y”。由于对于任何自然数 x，我们可以选择 y = x+2，使得 x+1 < y 成立。因此，φ 在 M 下为真。
3.2 练习
练习 1：构造一个一阶逻辑公式 ψ 表示“存在一个 x，使得对于所有 y，P(x, y) 为真”。
练习 2：给定结构 N，论域为整数集，a 解释为 1，f 解释为加法函数，P 解释为等于关系。验证公式 ψ 在 N 下是否为真。
4. 总结
本章详细介绍了一阶逻辑的语法和语义。我们首先介绍了符号表，包括常量、变量、函数、谓词、逻辑连接词和量词。然后，我们通过归纳定义的方式讲解了项和公式的构造。接着，我们讨论了解释与结构，以及模型与有效性的概念。最后，通过实例和练习，我们加深了对这些概念的理解。掌握这些基础知识对于进一步学习一阶逻辑的推理和证明至关重要。