推理的基本概念
所谓推理，是指按照某种策略，从已知事实和知识出发，推出蕴含在前提之中的新结论的思维过程。在人工智能系统中，推理由程序自动完成，称为机器推理：综合数据库中存放事实，知识库中存放规则与一般性知识，而推理机负责在二者之间建立推导链条。
推理的分类
| 分类标准 | 类型 | 含义 |
|---|---|---|
| 逻辑基础 | 演绎推理 | 从一般到个别：前提真则结论必然真，如三段论。 |
| 归纳推理 | 从个别到一般：由大量实例总结规律，结论具有或然性，是机器学习的重要思想来源。 | |
| 默认推理 | 在知识不完全时，先按默认假设行动，若出现反例再撤销结论（非单调）。 | |
| 知识确定性 | 确定性推理 | 前提与结论都是精确的，结论按逻辑必然得出（本章主题）。 |
| 不确定性推理 | 前提含概率或模糊性，结论带置信度（第 5 章主题）。 | |
| 结论单调性 | 单调推理 | 随知识增加，结论只增不减，经典逻辑推理均属此类。 |
| 非单调推理 | 新事实可能推翻旧结论（如"鸟会飞，企鹅是鸟"后需修正），默认推理、界限推理属此。 |
推理方向与控制策略
推理方向解决"从何处开始推"的问题：
正向推理
又称数据驱动。从已知事实出发，匹配可用规则，把结论加入事实库，继续匹配直到得到目标。优点是能主动推出信息，缺点是可能推出大量无关结论、存在盲目性。
反向推理
又称目标驱动。先提出假设，再寻找支持该假设的规则与证据。目的性强、解释性好，适合解空间较小的诊断类问题；不适合需要主动发现结论的场合。
双向推理
正向与反向同时进行，在中间某处"会师"，兼顾目的性与信息获取能力，是实践中常用的折中方案。
推理过程中，规则与事实的匹配组合往往很多，必须有控制策略决定先试哪一条，主要包括：
- 求解策略：只求一个解，还是求所有解或最优解；
- 搜索策略：对规则树/图的遍历顺序（盲目搜索、启发式搜索，详见第 4 章）；
- 冲突消解策略：多条规则同时触发时如何取舍，常见有专一性优先（条件多者优先）、新鲜度优先（使用新加入事实者优先）、优先级排序、规则编号排序等；
- 限制策略：对推理深度、宽度、时间、空间设限，防止无限推理与组合爆炸。
自然演绎推理
自然演绎推理是从一组已知为真的谓词公式出发，直接运用经典逻辑的推理规则推出结论的过程。最常用的规则有：
| 推理规则 | 形式 | 含义 |
|---|---|---|
| 假言推理（取假式） | P，P → Q ⊢ Q | 若 P 真且"P 蕴含 Q"成立，则 Q 真。 |
| 拒取式 | ¬Q，P → Q ⊢ ¬P | 后件为假，则前件必为假。 |
| 三段论 | P → Q，Q → R ⊢ P → R | 蕴含关系可以传递。 |
| 合取/析取规则 | P, Q ⊢ P∧Q；P ⊢ P∨Q | 构造合取或析取式。 |
已知：① 所有的人都会死：∀x (Man(x) → Mortal(x))；② 苏格拉底是人：Man(Socrates)。
对①作全称固化（用 Socrates 替换 x），得 Man(Socrates) → Mortal(Socrates)；再由②与假言推理，得 Mortal(Socrates)——苏格拉底会死。
自然演绎推理表达自然、证明过程符合人的思维习惯，但规则众多、推导步骤灵活，容易产生大量与目标无关的中间公式，难以在计算机上机械执行。为寻找统一、可自动化的证明方法，人们发展出了归结演绎推理。
归结演绎推理
归结演绎推理建立在鲁滨逊归结原理（J. A. Robinson, 1965）之上。它的革命性在于：把复杂多样的逻辑推理统一为一条简单规则（归结），使定理证明能够完全机械化，成为自动定理证明、逻辑程序设计语言 Prolog 的理论基础。
子句集及其化简
文字是谓词公式或其否定；子句是若干文字的析取式，如 P(x) ∨ ¬Q(x) ∨ R(x)；不含任何文字的子句称为空子句 □（NIL），它恒为假，不可满足。不含变量的子句称为基子句。
任意一个谓词公式都可以等价地化为一个子句集（有限个子句的合取），步骤如下：
① 消去蕴含与等价符号
利用 P → Q ≡ ¬P ∨ Q、P ↔ Q ≡ (¬P∨Q) ∧ (¬Q∨P)。
② 把否定号 ¬ 内移到谓词旁边
用德摩根律与量词否定律：¬(P∧Q) ≡ ¬P∨¬Q，¬∀x P ≡ ∃x ¬P，¬∃x P ≡ ∀x ¬P，使每个否定只作用于单个谓词。
③ 变量标准化
使不同量词约束的变量使用不同名字，如 ∀x P(x) ∨ ∃x Q(x) 改写为 ∀x P(x) ∨ ∃y Q(y)。
④ 消去存在量词（Skolem 化）
若 ∃ 不受 ∀ 约束，用一个新常量替换（如 ∃x P(x) → P(A)）；若 ∃ 在 ∀ 的辖域内，则用以这些全称变量为参数的 Skolem 函数替换（如 ∀x ∃y Mother(y,x) → Mother(f(x), x)）。
⑤ 化为前束范式
此时公式中只剩全称量词，把它们全部移到最前端，得到"全称量词串 + 母式"的前束形。
⑥ 母式化为合取范式
利用分配律 P ∨ (Q∧R) ≡ (P∨Q) ∧ (P∨R)，使母式成为若干析取式的合取。
⑦ 消去全称量词与合取符号
默认所有变量都受全称约束，省略量词；把合取式拆成独立子句，组成子句集；再对变量更名，使各子句变量互不重名。
子句集的化简在"不可满足性"意义下保持等价：原谓词公式不可满足，当且仅当其子句集不可满足。这保证了归结证明的有效性。
置换与合一
谓词归结要求两个互补文字（一个肯定、一个否定）在谓词与参数上完全一致，这就需要置换与合一。
- 置换（Substitution）：用项替换变量，形如
{t1/x1, …, tn/xn}。例如对P(x)作置换{a/x}得P(a)。 - 合一（Unification）：寻找一个置换 θ，使两个谓词公式经替换后完全相同。若存在，则称它们是可合一的，θ 为合一置换；其中"最一般"的合一置换（MGU，对变量约束最少）尤为重要。
合一算法的基本操作是差异集（不一致集）匹配：自左向右找出两个公式第一处不同的符号对，若一个是变量、另一个是不含该变量的项，就以该项置换该变量；反复进行直到两公式一致，或发现无法合一（如两个不同常量、不同谓词名）。
归结式与归结反演
命题逻辑的归结规则：设两个子句 C1、C2 分别含有一对互补文字 L 与 ¬L，把它们消去，剩余部分组成的析取式就是二者的归结式：
⟹ R(C1, C2) = C1' ∨ C2'
例如：C1 = P ∨ Q，C2 = ¬Q ∨ R，消去互补对 Q/¬Q，得归结式 P ∨ R。
谓词逻辑的归结规则：若子句 C1 中的文字 L1 与 C2 中文字 L2 的否定存在最一般合一置换 θ，则归结式为：
- 第一步：将所有已知前提条件化为子句集 S；
- 第二步：把待证目标 G 否定，得到 ¬G，化为子句后并入 S；
- 逻辑核心：若能从 S ∪ {¬G} 推出空子句 □（矛盾），说明该集合不可满足，从而 S ⊨ G，目标得证。
- 第三步：反复在子句间进行归结，把新归结式加入子句集，直到归结出空子句为止。
已知前提：
① 所有动物都需要食物：∀x (Animal(x) → NeedFood(x))
② 凡需要食物的都是生物：∀y (NeedFood(y) → Living(y))
③ 猫是动物：Animal(Cat)
目标：Living(Cat)。先否定目标得 ④ ¬Living(Cat)。
建立子句集：
C1： ¬Animal(x) ∨ NeedFood(x)
C2： ¬NeedFood(y) ∨ Living(y)
C3： Animal(Cat)
C4： ¬Living(Cat) ← 目标的否定归结过程：
C5： NeedFood(Cat) ← C1 与 C3 归结，置换 {Cat/x}
C6： Living(Cat) ← C2 与 C5 归结，置换 {Cat/y}
C7： □（空子句） ← C6 与 C4 归结，矛盾！归结出空子句，反证成立，因此 Living(Cat) 得证。
鲁滨逊归结原理在一阶谓词逻辑意义下是完备的：若子句集确实不可满足，则一定存在一条归结出空子句的路径。但"完备"不等于"高效"——不加限制地归结会产生大量无用子句。为此发展出删除策略（删除重言式、被包孕子句）、支持集策略、线性输入策略、祖先过滤策略等，以在保证（或部分保证）完备性的前提下缩小搜索空间。
除了证明定理，归结反演还可用于问题求解：在目标子句中加入一个"回答文字"，归结过程中让它随置换不断积累，最终空子句位置留下的回答文字实例就是问题的答案（如求解"张三的祖父是谁"）。
与或形演绎推理
归结演绎要求把公式全部化为子句（合取范式），这一过程可能破坏公式原有的结构信息，且推导目标不够直观。与或形演绎则保留知识的"与—或"树状结构，直接进行演绎。
与或形与与或树
与或形是用 ¬、∧、∨ 表示、不含蕴含符的公式（但不必进一步展开为合取范式）。公式的结构可画成与或图：
- 一个合取式
P ∧ Q的各支用一段圆弧连起，表示"与"——各支必须同时成立； - 一个析取式
P ∨ Q的各支不连弧，表示"或"——任一支成立即可。
演绎所使用的蕴含式分为两类：F 规则形如 L → W（单个文字蕴含任意与或形），用于正向演绎；B 规则形如 W → L（任意与或形推出单个文字），用于反向演绎。使用前需把规则右侧（或左侧）化为与或形。
正向与或形演绎
从事实表达式的与或树出发，对图中的目标文字节点匹配 F 规则的前件，把规则后件接到图上，直到产生的图中包含一个目标表达式的一致解图为止。推理轨迹天然构成一棵证明树，便于解释。
反向与或形演绎
从目标表达式的与或树出发，用 B 规则反向展开：目标中的文字与规则后件匹配，把其前件作为新的子目标（与节点展开为多个需同时满足的子目标），直到所有叶节点都与已知事实或证据合一为止。专家系统中的反向链推理即源于此。
在含变量的与或图中，同一变量可能在不同分支被置换为不同的项。只有当解图中所有置换的复合彼此相容、不产生冲突（即存在一个统一的合一置换）时，该解图才是"一致"的，证明才有效。
与或形演绎保留了知识的自然结构、规则形式接近产生式、推理过程可解释，是许多知识系统推理机的实现方式之一；其代价是需要维护较复杂的图结构与一致置换，完备性依赖于规则的组织。
自测与思考
为什么把子句集的化简称为在"不可满足性意义下等价"？Skolem 化会不会改变公式本身的含义？
归结反演为什么推出空子句 □ 就能说明目标成立？
设子句 C1 = P(x) ∨ Q(x)，C2 = ¬P(a) ∨ R(y)，请写出它们的归结式。
Q(a) ∨ R(y)。