一、符号主义概述
1.1 核心思想
符号主义是人工智能实现的第三条途径，也是最古老的方法。其核心思想是：机器可以不了解符号的实际物理世界含义，仅通过符号的改写来完成与人推理结果相同的推理，即实现自动推理（Automatic Reasoning）。
符号主义与另外两条 AI 路径形成对比：
- 仿生学/连接主义：基于神经系统构造神经网络模型，目前已成为机器学习与人工智能中最大的领域，近十几年的主要 AI 进展主要来自于此。
- 进化主义：将优化问题转化为基因表达，通过选择、交叉、变异三个算子使种群向最优解靠拢，目前在三大 AI 学派中相对处于劣势，主要退化为组合优化技术。
1.2 本章四部分
- 逻辑学基础：符号主义的理论基础
- 逻辑学系统的本质：有哪些逻辑系统及其可计算性问题
- 消解原理（Resolution Principle）：将符号主义变成可在计算机内部自动运行的算法
- Prolog 语言：基于消解原理的编程语言（Programming in Logic）
二、逻辑学系统基础
2.1 逻辑学系统的三部分
- 逻辑学（Logic）：帮助判断系统中的逻辑断言是否包含冗余，或各表达式之间是否存在矛盾的形式化系统
- 本体论（Ontology）：规定形式化系统中出现的符号必须有明确的含义。核心原则——所有概念在逻辑系统中有唯一的字符串表示（名称不同即对象不同，无歧义）
- 计算理论结合：只有与计算理论结合后，才能将逻辑系统放入计算机内自动推理
2.2 认识逻辑系统的五个维度
任何一个逻辑学系统，从以下五方面分析即可理解其本质：
- 符号（Symbols）：系统引入了哪些符号
- 项（Terms）：符号如何定义——常元（constant）、变元（variable）、函元（function）
- 语句（Expressions/Sentences）：如何用连接算子从基础命题构造复杂语句
- 语义（Semantics）：如何解释语句的真假
- 推理算法（Inference Algorithm）：如何进行自动化推理
三、命题逻辑
命题逻辑（Propositional Logic）：最基础、最简单的逻辑系统。
3.1 符号系统
- 命题符号：大写字母 P, Q, R, S… 表示命题（断言）
- 真值：True（真）或 False（假），二值逻辑
- 连接算子（Logical Connectives）：
- $\land$（合取/Conjunction）：两个命题都为真时，合取表达式才为真
- $\lor$（析取/Disjunction）：只要有一个命题为真，析取表达式即为真
- $\neg$（否定/Negation）
- $\rightarrow$（蕴含/Implication）
- $\equiv$（等价/Equivalence）
3.2 语义与善意推定
命题逻辑的语义通过真值表定义。
善意推定（Benevolent Assumption）是蕴含式的语义规定：在逻辑学系统中，如果前提是 False，不管结论是 True 还是 False，该蕴含式都被认为成立。唯一不被认可的情况是前提为 True 但结论为 False。
以”下雨 → 地湿”为例：
| 下雨 | 地湿 | 是否认可 |
|---|---|---|
| F | F | ✓ |
| F | T | ✓（地湿可能是其他原因） |
| T | F | ✗（不能接受） |
| T | T | ✓ |
关键结论：计算机内部自动推理的本质——在定义了符号系统之后，利用等价公式对符号进行纯语法层面的改写（计算机不知道 P 代表”下雨”、Q 代表”地湿”）。
3.3 真值表推理的局限
- 有 $N$ 个命题时，需要考虑 $2^N$ 种世界（解释）
- 复杂度指数级增长，效率低下
- 真值表证明方式复杂度太高，需要更好的方法
3.4 命题逻辑的致命缺陷
给定”所有人都会死”和”苏格拉底是人”，在命题逻辑中计算机无法推导出”苏格拉底会死”。因为命题逻辑不区分个体和集合之间的关系——计算机只能做字符串的完全匹配，缺乏变量替换机制。
四、一阶谓词逻辑
一阶谓词逻辑（First-Order Predicate Logic, FOL）：在命题逻辑基础上引入集合（变量）的概念。
4.1 新增符号
除了保留命题逻辑的 True/False 和五个连接算子外，新增：
- 常元（Constant）：如 “Socrates”（苏格拉底）
- 变元（Variable）：如 $x, y, z$，可代表集合中的任意个体
- 函元（Function）：如 $\text{mother}(x), \text{father}(x)$
- 谓词（Predicate）：表示个体间的关系，如 $\text{man}(x), \text{die}(x), \text{parent}(x, y)$
新增两个量词（Quantifier）：
| 量词 | 符号 | 含义 | 来源 |
|---|---|---|---|
| 全称量词（Universal Quantifier） | $\forall$ | 对所有的… | All 的 A 倒写 |
| 存在量词（Existential Quantifier） | $\exists$ | 存在某个… | Exist 的 E 反转 |
4.2 解决命题逻辑的缺陷
苏格拉底问题在一阶谓词逻辑中被解决：
\[\forall x (\text{man}(x) \rightarrow \text{die}(x))\]因为 $x$ 在全称量词辖域内，可以替换为任意个体。将 $x$ 替换为 Socrates：
\[\text{man}(\text{Socrates}) \rightarrow \text{die}(\text{Socrates})\]与事实 $\text{man}(\text{Socrates})$ 匹配后，直接推导出 $\text{die}(\text{Socrates})$。
4.3 表达能力
一阶谓词逻辑可以表达丰富的领域知识：
- 数学领域：常元是数字（0、1、自然数、浮点数、无理数），函元是数学函数（$\sin, \log, +$），谓词表示相等（$=$）、小于（$<$）、共轭关系等
- 人物关系分析（如《红楼梦》）：常元是人物（贾宝玉、史湘云、刘姥姥），变元代表任意集合（男性集合、女性集合），谓词表示父亲、母亲、兄弟等关系
形式化系统提供了严谨的表达领域知识的方法：将所有知识编码为逻辑表达式，让计算机自动推理。
4.4 与深度学习的对比
符号主义方法有两个深度学习不具备的优势：
- 知识复用的高效性：一条规则就能让系统理解关系（深度学习需要大量样本）
- 可解释性：推理链条可追踪，可以知道新知识是利用了哪些已有知识推导出来的
符号神经计算（Symbolic Neural Computing）是一个新兴领域，试图结合符号主义的数学优雅、知识利用高效性和可解释性，与神经网络对复杂模式的挖掘能力。
五、推理的数学基础
5.1 推理的定义
推理（Inference）：给定一组用逻辑表达式表示的知识集合，推导出新的正确表达式。
5.2 逻辑蕴含的判断条件
核心问题：什么时候能断言新推导出来的知识是原有知识的必然逻辑结果（Logical Consequence）？
判断条件（基于可满足性/Satisfiability）：所有能够满足知识库 S（使 S 中所有表达式为真）的解释，是否也都能满足新表达式 X？如果能，X 就是 S 的必然逻辑结果。
- 可满足（Satisfiable）：能找到一个解释（世界）使表达式为真
- 不可满足（Unsatisfiable）：在所有解释下表达式都为假
- 推理时只关心知识库中所有表达式都为真的那些世界（因为前提为假时，善意推定使得结论真假无法判断）
5.3 封闭世界假设与开放世界假设
封闭世界假设（Closed World Assumption, CWA）：如果无法证明某个命题为真，就默认它为假。这是多数逻辑系统遵循的原则。
CWA 并非总是正确。以 Oedipus 希腊神话为例：在封闭世界假设下会推导出不合理的结论。
描述逻辑（Description Logic）遵循与 CWA 不同的假设：
- 描述逻辑遵循开放世界假设（Open World Assumption）：可以对未知真假的事物做假设
- 描述逻辑是现代知识图谱（Knowledge Graph）的理论基础
- 开放世界假设更合理，但计算复杂度更高
六、消解原理
消解原理为给定公理或定理的情况下，机器能够自动完成推理奠定了理论基础。
6.1 核心思想（反证法）
要证明新命题 $E$ 是知识库 $KB = \{A, B, C, D\}$ 的必然逻辑结果：
- 将 $E$ 的否定 $\neg E$ 加入知识库，得到扩展集合 $\{A, B, C, D, \neg E\}$
- 尝试证明扩展集合不可满足（产生矛盾）
- 如果产生矛盾（消解出空子句），说明 $\neg E$ 与 KB 不相容
- 在 KB 都为真的世界中，$\neg E$ 必为假 → $E$ 必为真 → $E$ 是 KB 的必然逻辑结果
其逻辑是：将待证命题的否定放入系统，如果能推导出矛盾（空子句/否认），则表明新添加的命题造成了不相容——因为 KB 本身是可满足的。因此，必然在原 KB 都为真的世界里，$\neg E$ 为假 → $E$ 为真 → $E$ 是原 KB 的必然逻辑结果。
6.2 消解步骤
每一步消解：
- 找一对逻辑表达式，其中一个包含正文字（如 $P$），另一个包含副文字（如 $\neg P$），且这两个文字对应同一谓词
- 进行变量替换（统一化/Unification），使两个文字完全相同
- 消去这一对正/副文字，剩余部分合并（析取关系保留）
重复此过程。如果最终消解出空子句（$\square$，即矛盾），则证明成功。
6.3 保真性（Soundness）
消解是保真的：任何情况下，消解产生的结果都是原两个表达式的必然逻辑结果。
证明（分情况讨论）：
- 若正文字为 True → 另一表达式中的副文字为 False → 该表达式必须依赖其他析取项为 True
- 若正文字为 False → 同理，另一表达式的其他析取项必须使整体为 True
- 无论哪种情况，消去正副文字对后剩余的部分必为真
6.4 示例：Fido 会死吗？
知识库：
- $\forall x (\text{dog}(x) \rightarrow \text{animal}(x))$
- $\forall y (\text{animal}(y) \rightarrow \text{die}(y))$
- $\text{dog}(\text{Fido})$
问题：Fido 会死吗？即证明 $\text{die}(\text{Fido})$。
消解过程：
- 将蕴含式转为析取范式：$\neg\text{dog}(x) \lor \text{animal}(x)$，$\neg\text{animal}(y) \lor \text{die}(y)$
- 将 $\neg\text{die}(\text{Fido})$ 加入
- 变量替换 $y \rightarrow x$，消去 $\text{animal}(x)$ 和 $\neg\text{animal}(x)$ → 得到 $\neg\text{dog}(x) \lor \text{die}(x)$
- 变量替换 $x \rightarrow \text{Fido}$，$\neg\text{dog}(\text{Fido})$ 与 $\text{dog}(\text{Fido})$ 消去 → 得到 $\text{die}(\text{Fido})$
- $\text{die}(\text{Fido})$ 与 $\neg\text{die}(\text{Fido})$ 消去 → 空子句 ✓
七、自然语言到消解：完整流程与例题
7.1 完整流程
将自然语言描述的知识库用于消解证明的完整流程：
- 逐条转换为逻辑表达式
- 转换为析取范式
- 用消解原理进行推理证明
7.2 例题一：Happy Student（快乐学生）
自然语言：
- 任何人通过历史考试且赢得彩票 → 快乐
- 任何人学习或幸运 → 可通过任何考试
- John 不学习但幸运
- 任何幸运的人 → 赢得彩票
问题：John 快乐吗？
逻辑表达式：
- $\forall x [\text{pass}(x, \text{history}) \land \text{win}(x, \text{lottery}) \rightarrow \text{happy}(x)]$
- $\forall x \forall y [\text{study}(x) \lor \text{lucky}(x) \rightarrow \text{pass}(x, y)]$
- $\neg\text{study}(\text{John}) \land \text{lucky}(\text{John})$
- $\forall x [\text{lucky}(x) \rightarrow \text{win}(x, \text{lottery})]$
消解证明：依次消去 win、happy、pass、lucky 对应的正副文字对，最终得空子句 → John 是快乐的。
7.3 例题二：Exciting Life（精彩人生）
自然语言：
- 所有人如果不穷（rich 且 smart）→ happy
- 能阅读的人不愚蠢（阅读 → smart）
- John 能阅读且 wealthy（not poor）
- Happy people have exciting life
问题：是否存在某个人拥有 exciting life？（非指名道姓的问题）
关键区别：问题涉及存在量词 $\exists w(\text{exciting}(w))$。消解过程中的变量替换会在答案中揭示这个人是谁——沿消解路径回溯变量替换即可：$w \rightarrow Z \rightarrow X \rightarrow Y \rightarrow \text{John}$，所以答案就是 John。
7.4 例题三：Great Grandparents（曾祖父母）
自然语言：
- 每一个人都有一个 parent
- Parent 的 parent 是 grandparent
- John 有没有 grandparent？
关键：第一条 $\forall x \exists y (\text{parent}(y, x))$ 含有存在量词。
Skolem 化：将存在量词 $y$ 替换为函元 $\text{pa}(x)$（表示 x 的 parent），消除存在量词。
消解完成后答案：John 的 grandparent 是 $\text{pa}(\text{pa}(\text{John}))$ — 即 John 的 parent 的 parent。
八、析取范式的九步转换
将任意一阶谓词逻辑表达式转为析取范式（CNF/Clausal Form）的九个步骤：
| 步骤 | 操作 | 说明 |
|---|---|---|
| 1 | 消去蕴含 | $A \rightarrow B \equiv \neg A \lor B$，$A \equiv B \equiv (\neg A \lor B) \land (A \lor \neg B)$ |
| 2 | 否定内移 | 将否定符号 $\neg$ 移到原子命题前。$\neg\forall x P \equiv \exists x \neg P$，$\neg\exists x P \equiv \forall x \neg P$；De Morgan 定律 |
| 3 | 变量换名 | 不同量词辖域内的变量名必须不同（避免同名冲突） |
| 4 | 量词前移 | 将所有量词移到表达式最前面（保持原顺序） |
| 5 | Skolem 化 | 消除存在量词：$\forall x \exists y P(x,y) \rightarrow \forall x P(x, f(x))$，引入新的函元 $f$ 代替依赖于 $x$ 的 $y$ |
| 6 | 去除全称量词 | Skolem 化后只剩全称量词，默认所有变量均受全称量词约束，可省略 |
| 7 | 合取分配 | $A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$，拆成多个子句 |
| 8 | 拆分子句 | 合取连接的多个子句拆成独立的逻辑表达式 |
| 9 | 再次换名 | 不同子句间的变量名保持独立 |
九、消解策略与算法效率
9.1 消解策略
实际编程实现消解原理时需要考虑策略选择（每一步可能有多对表达式可消解）：
| 策略 | 说明 | 特点 |
|---|---|---|
| 宽度优先（Breadth-First） | 每一层尝试所有可能的消解对 | 完备但复杂度极高，不可用 |
| 支撑集策略（Set of Support） | 消解对中至少一个来自”支撑集”（问题的否定或由其产生的子句） | 缩小搜索空间 |
| 线性消解（Linear Resolution） | 每次消解对中必有一个是上一步消解的结果 | 高效，是支撑集策略的特例 |
| 单元优先（Unit Preference） | 优先选择只有一个谓词的单元子句进行消解（使析取项减少最快） | 加速收敛 |
9.2 线性消解不完备
线性消解虽然高效，但不具备完备性（Completeness）——某些本可证明的命题用线性消解可能陷入无限循环。
不完备示例：集合 $\{P \lor Q, \neg P \lor Q, P \lor \neg Q, \neg P \lor \neg Q\}$ 本身不可满足（可消解出空子句），但线性消解会陷入无限循环（$\neg Q, \neg P, Q, P, \neg Q, \dots$）。
9.3 Soundness 与 Completeness
- 合理性（Soundness）：推理算法推导出的所有结论都是正确的
- 完备性（Completeness）：所有可推导的正确结论，算法都能推导出来
十、一阶谓词逻辑的不可判定性
10.1 半可判定性
一阶谓词逻辑是半可判定的（Semi-decidable）：
- 如果待证命题与知识库不相容（逻辑蕴含成立）→ 算法一定会停机，告知结果
- 如果待证命题与知识库相容（逻辑蕴含不成立）→ 算法可能永不停止
10.2 Herbrand 结构与无穷论域
只要逻辑系统中有：
- 至少一个常元（如 $a$）
- 至少一个函元（如 $f(x)$）
就可以产生无穷序列：$a, f(a), f(f(a)), f(f(f(a))), \dots$
这意味着论域是无穷的。在无穷论域上全称量词和存在量词的验证都需要遍历无穷多个体，因此无法停机。
10.3 语义树分析
逻辑表达式的可满足性问题可以用语义树（Semantic Tree）来分析：
- 树的每条从根到叶的路径对应一种解释（对系统中谓词的真假规定）
- 如果集合不可满足，树的每个分支都会在某处截断（矛盾出现，无需继续扩展）
- 如果集合可满足，某些分支会因函元的无穷嵌套而永远扩展下去
10.4 与计算理论的关系
- 逻辑推理的核心问题就是可满足性问题（SAT/Satisfiability）
- SAT 问题是 NP 完全问题的”最高端”——所有 NP 完全问题（哈密尔顿圈、旅行商、背包等）都是 SAT 的演化版本
- 命题逻辑的 SAT 是 NP 完全的（P 类），一阶谓词逻辑是不可判定的
10.5 逻辑系统的三分法
| 类别 | 代表 | 表达能力 | 计算复杂度 |
|---|---|---|---|
| 表达能力弱 | 命题逻辑 | 不能表示个体与集合的关系 | P 类（近似线性） |
| 表达能力极强 | 一阶谓词逻辑、高阶逻辑 | 可表示丰富的领域知识 | 不可判定 |
| 折中 | 描述逻辑的子集 | 有一定表达能力 | 可判定 |
其他逻辑系统：缺省逻辑（Default Logic，处理”鸟会飞但鸵鸟不会”这类带例外的知识）、模态逻辑（Modal Logic，引入”必然”和”可能”算子，在软件工程中用于程序验证）。
十一、霍恩子句与 Prolog
11.1 从一阶谓词逻辑到霍恩子句
为了让推理算法高效且可判定，必须在一阶谓词逻辑基础上做语法限制——每个逻辑表达式最多只有一个正文字（其余均为副文字），这就是霍恩子句（Horn Clause）。
霍恩子句的形式（析取范式视角）：
\[\neg B_1 \lor \neg B_2 \lor \dots \lor \neg B_n \lor A\]等价于蕴含形式：
\[B_1 \land B_2 \land \dots \land B_n \rightarrow A\]- 右边（$A$）只有一个正文字 ← 这是霍恩子句的核心限制
- 左边可以有多个条件
霍恩子句的高效之处：
- 消解时只需找到一个正文字对应的副文字即可对消
- 消去一个事实（无条件子句）→ 子目标直接减少
- 消去一个规则 → 子目标可能增多（展开为规则的条件）
11.2 Prolog 语言基础
Prolog = Programming in Logic
Prolog 中霍恩子句的三种形式：
| 形式 | Prolog 语法 | 逻辑含义 |
|---|---|---|
| 事实（Fact） | A. |
无条件成立的断言（只有正文字） |
| 规则（Rule） | A :- B1, B2, ..., Bn. |
$B_1 \land \dots \land B_n \rightarrow A$ |
| 目标（Goal） | ?- G1, G2, ..., Gn. |
将 $\neg G$ 放入系统，启动消解证明 |
语法对应：
,（逗号）= 合取 $\land$;（分号）= 析取 $\lor$:-= 蕴含 $\leftarrow$（反向书写）not= 否定 $\neg$
11.3 Prolog 的执行机制
Prolog 的推理过程与消解原理完全一致：
- 从目标出发，取第一个子目标
- 在知识库中寻找头部（正文字）与该子目标匹配的规则或事实
- 进行变量替换（Unification）使两者相同
- 消去该子目标，若匹配的是事实：子目标被消除；若匹配的是规则：子目标被替换为规则的条件部分
- 重复直到所有子目标被消去（成功）或无可匹配项（失败）
Prolog 采用深度优先搜索 + 回溯（Backtracking）：
- 按子句在程序中出现的顺序依次尝试匹配
- 当一条路径失败时，回溯到上一个选择点尝试其他可能
- 使用 Cut 运算符（
!）阻止对已匹配部分进行回溯
11.4 列表与模式匹配
Prolog 中列表的表示：
[a, b, c]— 普通列表[H|T]— H 是头部（第一个元素），T 是尾部（剩余列表）[]— 空列表- 列表可嵌套
Cut（|）匹配规则：
- 竖线前面只能匹配一个元素
- 竖线后面可以匹配多个元素（包括零个）
11.5 例题：骑士巡游问题
在 3×3 棋盘上，马按国际象棋走法（日字形），求从格子 1 到格子 3 的路径。
Prolog 解法只需：
- 枚举所有一步可到达的事实（如
move(1,6). move(1,8). ...） - 两条规则：
- 到达目标则结束
- 否则找中间路径（避免重复访问），继续探索
短短几行代码即可解决——这正是 Prolog 的强大之处：只需写知识和规则，推理引擎自动完成搜索。
11.6 例题：农夫过河问题
农夫带狼、羊、菜过河，每次只能带一个。Prolog 建模：
- 用状态向量 (F, W, G, C) 表示各方在西岸(0)还是东岸(1)
- 定义合法的一步转移（move）
- 用路径搜索规则寻找从初始状态到目标状态的路径
11.7 Prolog 编程注意事项
Prolog 编写规则时必须注意顺序：
- 简单规则写在前面，复杂规则写在后面 — 否则推理时间显著增加
- 简单条件写在前面，复杂条件写在后面 — 否则可能永不停止
永不停机示例：若将递归规则 ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y) 写在基础规则 ancestor(X,Y) :- parent(X,Y) 之前，且复杂条件在前面，Prolog 每次都会先尝试递归，导致无限展开。
十二、总结：符号主义自动推理的发展脉络
人工智能的第三种实现思路——符号主义，旨在将人类知识编码为形式化系统，使系统能自动推理。
发展脉络：
- 最早关注命题逻辑 → 表达能力太弱（不能区分个体和集合）
- 转向一阶谓词逻辑 → 引入变量、全称量词、存在量词
- 发现推理的核心本质是逻辑表达式的可满足性问题
- 理论证明一阶谓词逻辑不可判定（半可判定）
- 退而求其次，限制表达能力 → 霍恩子句（每条最多一个正文字）
- 基于霍恩子句发展出 Prolog 编程语言
Prolog 的核心（反向推理/目标驱动）：
- 从目标出发 → 找证据 → 匹配消去 → 直到空（成功）
- 消去事实：子目标减少；消去规则：子目标可能增加
- 内置回溯机制
Prolog 推导的结果具有严谨的逻辑学基础保证其正确性，这与深度学习在 AI for Science（如数学证明）中只能提供灵感、存在严重幻觉形成对比。
Prolog 曾被日本指定为下一代 AI 的主要编程语言，并开发了专门的 Prolog 硬件推理机，可见符号主义推理在 AI 历史上曾受到的重视程度。