非单调推理与常识推理

非单调推理（nonmonotonic reasoning）是这样一种推理：加入新信息可能会撤销之前得出的结论。它形式化了人们带着缺省和例外进行的推理，例如“鸟会飞，但企鹅不会”，是 AI 中常识推理的逻辑基础。经典逻辑做不到这一点，因为它是单调的。

1. 为什么经典逻辑是单调的

当每一个使全部前提 $\Gamma$ 为真的解释也使 $\phi$ 为真时，记作 $\Gamma \models \phi$（定义见形式系统）。

现在试着用经典逻辑说“鸟会飞”。取 $\Gamma =\{\forall x(\mathrm{Bird}\left(x\right)\to \mathrm{Flies}\left(x\right)),\mathrm{Bird}(\mathrm{tweety}\left)\right\}$，得到 $\mathrm{Flies}\left(\mathrm{tweety}\right)$。再加入 $\mathrm{Penguin}\left(\mathrm{tweety}\right)$ 和 $\forall x\left(\mathrm{Penguin}\right(x)\to \neg \mathrm{Flies}(x\left)\right)$，由单调性，$\mathrm{Flies}\left(\mathrm{tweety}\right)$ 仍被蕴涵，它的否定也被蕴涵。前提变得不一致，而在经典逻辑中，不一致的集合蕴涵一切。经典逻辑唯一的补救办法，是把每一个例外都写进规则（“不是企鹅、不是鸵鸟、没有受伤……的鸟会飞”），而这张清单谁也写不完。

非单调后承关系通常记作 $|\sim$，它有意放弃了这条性质：$\mathrm{Bird}\left(\mathrm{tweety}\right)|\sim \mathrm{Flies}\left(\mathrm{tweety}\right)$，然而 $\mathrm{Bird}\left(\mathrm{tweety}\right),\mathrm{Penguin}\left(\mathrm{tweety}\right)|\sim \neg \mathrm{Flies}\left(\mathrm{tweety}\right)$。下面每一种形式体系，都是对“哪些结论被允许、何时被撤回”的一种不同回答。同样的需求也出现在框架中：框架的槽缺省值可以被覆盖。

2. 缺省与极小模型

缺省逻辑

谁、何时。Raymond Reiter，《缺省推理的一种逻辑》（A Logic for Default Reasoning），《人工智能》第 13 卷，1980 年 [1]。

如何工作。缺省理论是一个二元组 $(W,D)$：$W$ 是一组普通的一阶事实，$D$ 是一组形如前提 : 辩护 / 结论的缺省规则。这条规则读作：如果前提可推出，且辩护与当前信念一致，就得出结论。“鸟通常会飞”用 Reiter 的记法写作：

特威蒂。取 $W=\left\{\mathrm{Bird}\right(\mathrm{tweety}\left)\right\}$、$D=\left\{\delta \right\}$，辩护 $\mathrm{Flies}\left(\mathrm{tweety}\right)$ 与 $W$ 一致，所以该理论只有一个扩张（extension），即 $W\cup \left\{\mathrm{Flies}\right(\mathrm{tweety}\left)\right\}$ 的演绎闭包。现在扩大事实集：

这时 $\neg \mathrm{Flies}\left(\mathrm{tweety}\right)$ 可由事实推出，辩护不再一致，缺省被阻断，唯一的扩张包含 $\neg \mathrm{Flies}\left(\mathrm{tweety}\right)$。事实更多，缺省结论反而更少：这就是非单调，而且没有产生不一致。

多个扩张。相互冲突的缺省可能产生多个扩张。在尼克松菱形（Nixon diamond）中，尼克松是贵格会信徒（贵格会信徒通常是和平主义者），也是共和党人（共和党人通常不是）；于是有一个扩张里他是和平主义者，另一个里他不是。轻信（credulous）的推理者接受在某个扩张中成立的结论，怀疑（skeptical）的推理者只接受在所有扩张中都成立的结论。局限。推理代价高：在命题情形下，怀疑式蕴涵是 Π₂^P 完全的，轻信式蕴涵是 Σ₂^P 完全的，比 NP 高一层。

限定（circumscription）

谁、何时。John McCarthy，《限定：一种非单调推理形式》（Circumscription—A Form of Non-Monotonic Reasoning），发表于同一 1980 年卷 [2]。

如何工作。限定形式化了“除非另有说明，事物都如预期”这一假设，做法是只保留理论的极小模型：在这些模型中，某个选定谓词对尽可能少的对象为真。在 McCarthy 后来的表述中，典型性用一个“异常”谓词来表达：

对 $\mathrm{Ab}$ 做限定，使它只在事实迫使时才为真。只有 $\mathrm{Bird}\left(\mathrm{tweety}\right)$ 时，极小模型中 $\mathrm{Ab}$ 为空，所以特威蒂会飞；再加入“企鹅是异常的”和“特威蒂是企鹅”，极小模型就变了。McCarthy 用一个二阶公式给出了它的语法定义。局限。最小化什么、固定什么、允许什么变化，都是建模决定；Vladimir Lifschitz 引入固定谓词与可变谓词的扩展，提供了更细的控制，而耶鲁射击问题（§5）显示了朴素的最小化会怎样出错。

非单调逻辑（McDermott 与 Doyle）

谁、何时。Drew McDermott 与 Jon Doyle，《非单调逻辑 I》（Non-Monotonic Logic I），同样发表于《人工智能》第 13 卷，1980 年 [3]。如何工作。他们加入一个模态算子 $M$，读作“是一致的”，于是缺省写成 $\mathrm{Bird}\left(x\right)\wedge M\mathrm{Flies}\left(x\right)\to \mathrm{Flies}\left(x\right)$，并把定理定义为一个一致性检查运算的不动点。局限。原始逻辑的语义很难解释；Moore 的自认知逻辑正是从对它的分析中发展出来的。

自认知逻辑

谁、何时。Robert C. Moore，《非单调逻辑的语义考察》（Semantical Considerations on Nonmonotonic Logic），《人工智能》第 25 卷，1985 年 [4]。如何工作。Moore 把模态算子 $L$ 读作“我相信”，把缺省看作对自身信念的推理：$\mathrm{Bird}\left(x\right)\wedge \neg L\neg \mathrm{Flies}\left(x\right)\to \mathrm{Flies}\left(x\right)$，即“如果我不相信特威蒂不会飞，那么特威蒂会飞”。推理者可接受的信念集，是其前提 $A$ 的稳定扩展（stable expansions），即满足下式的集合 $T$：

它之所以是非单调的，是因为推理者不相信什么，会随前提的增加而改变。影响。逻辑程序的稳定模型语义可以看作自认知逻辑的一种简化形式（§3）。

3. 封闭世界与逻辑程序

封闭世界假设

谁、何时。Raymond Reiter，《论封闭世界数据库》（On Closed World Data Bases），收于《逻辑与数据库》（Logic and Data Bases，Gallaire 与 Minker 编，1978） [5]。是什么。在封闭世界假设（CWA）下，任何无法推出的基原子都被当作假。一个没有列出从奥斯陆到利马航班的航班数据库，被读作“没有这样的航班”。为何是非单调的。加入这趟航班，就会撤回“没有航班”的结论。用在哪里。每个关系数据库都这样回答查询。而 OWL 等本体语言则有意采用开放世界假设，在那里缺失的航班只是未知。混用这两种读法是常见的错误来源。

失败即否定

谁、何时。Keith Clark，《失败即否定》（Negation as Failure），收于同一本 1978 年文集 [6]。如何工作。在 Prolog 中，当所有证明 G 的尝试都有限失败时，\+ G（“非 G”）成功。特威蒂写成逻辑程序：

flies(X) :- bird(X), \+ abnormal(X).
abnormal(X) :- penguin(X).
bird(tweety).

查询 flies(tweety) 成功；加入 penguin(tweety). 后它失败。Clark 证明了失败即否定相对于程序的完备化（completion）是可靠的；完备化把每个谓词的子句读成一个“当且仅当”的定义。稳定模型。1988 年，Michael Gelfond 与 Vladimir Lifschitz 为带否定的程序给出了稳定模型语义 [7]，它是回答集程序设计的基础。局限。失败即否定不是经典否定：\+ G 的意思是“G 不能从这个程序中证明”，它的可靠程度取决于程序本身是否完整。

4. 保持信念一致

真值维护系统

谁、何时。Jon Doyle，《一个真值维护系统》（A Truth Maintenance System），《人工智能》第 12 卷第 3 期，1979 年 [8]。是什么。真值维护系统（TMS），后来也称理由维护系统，是放在问题求解器旁边的记账组件。求解器报告每个结论及其理由（justification）；TMS 记录由此形成的依赖网络，并保持其一致。如何工作。在 Doyle 的设计中，一条理由有一个入表（必须持有的信念）和一个出表（必须不持有的信念）；只要某条理由有效，节点就处于 IN 状态。一个信念被撤回时，所有依赖它的信念也随之撤回；出现矛盾时，TMS 回溯到造成矛盾的假设，这种技术叫依赖导向回溯。正是出表让这个系统成为非单调的：当“特威蒂是企鹅”处于 OUT 时，“特威蒂会飞”处于 IN。今天。同样的想法，即记录每条推导出的事实为何成立、以便精确撤回，正是数据库中的增量视图维护和增量构建系统所做的事。

基于假设的真值维护（ATMS）

谁、何时。Johan de Kleer，《基于假设的 TMS》（An Assumption-based TMS），《人工智能》第 28 卷，1986 年 [9]。如何工作。ATMS 不维护单一的当前信念集，而是给每条推出的事实标上它成立所需的极小假设集（环境），并把导致矛盾的假设集记为无效集（nogoods）。所有一致的语境同时可用，问题求解器无需反复回溯就能比较各种可能。今天。ATMS 成为基于模型的诊断的标准组件：假设是“部件 c 工作正常”，无效集则指向候选故障。局限。标签可能随假设数量呈指数增长。

信念修正（AGM）

谁、何时。Carlos Alchourrón、Peter Gärdenfors 与 David Makinson，《论理论变更的逻辑》（On the Logic of Theory Change），《符号逻辑杂志》（Journal of Symbolic Logic），1985 年 [10]。是什么。AGM 理论追问：对一个逻辑封闭的信念集 $K$ 做理性的改变，应当是什么样子。它区分扩充 $K+\phi$（加入 $\phi$ 并在后承下闭合，不检查一致性）、收缩 $K-\phi$（放弃 $\phi$）和修正 $K*\phi$（加入 $\phi$ 同时保持一致），并为每种操作给出理性公设。修正可以通过 Levi 恒等式由另外两种操作构造：

信念修正与非单调推理原来是同一主题的两种视角：“$\psi$ 由 $\phi$ 推出”可以读作“$\psi$ 属于 $K*\phi$”，而 AGM 公设可以翻译成这种推理关系的公设。

5. 关于动作与变化的推理

框架问题

谁、何时。John McCarthy 与 Patrick Hayes 于 1969 年为它命名 [11]。是什么。要用逻辑描述一个动作改变了什么，还必须说明它没有改变什么：给一块积木刷漆，不会改变它的位置、其他积木，也不会改变天气。为每个动作和每个不受影响的事实分别写一条框架公理是不可行的。解决办法。非单调推理提供了一般性的答案：缺省地假定事物保持不变，除非已知某个动作改变了它（一条“惯性定律”）。Reiter 的后继状态公理（1991）为情境演算给出了同一想法的单调编码，把一个流（fluent）可能改变的所有方式收集到一条公理中；见情境演算以及规划页中的 STRIPS 假设。到 1980 年代末，技术层面的框架问题被认为已经解决；而更宽泛的哲学问题，即任何系统如何判断什么是相关的，并没有解决。

耶鲁射击问题

谁、何时。Steve Hanks 与 Drew McDermott，《非单调逻辑与时间投射》（Nonmonotonic Logic and Temporal Projection），《人工智能》第 33 卷第 3 期，1987 年 [12]。情境。一只火鸡活着，一把枪没有装弹。枪被装上子弹，过了一段时间，朝火鸡开枪。用限定或缺省来最小化变化，会得到两个同样“极小”的故事：预期的那个里火鸡死了；反常的那个里，枪在等待期间莫名其妙地退了弹，火鸡活了下来。每个故事都恰好包含一次“异常”变化，所以单纯的最小化无法偏向正确的那个。影响。这个问题迫使人们建立更细致的动作理论，包括 Sandewall 的遮蔽（occlusion）、Reiter 带后继状态公理的情境演算，以及动作描述语言。该论文于 2005 年获得 AAAI 经典论文奖。

事件演算

谁、何时。Robert Kowalski 与 Marek Sergot，《一种基于逻辑的事件演算》（A Logic-based Calculus of Events），《新一代计算》（New Generation Computing），1986 年 [13]；1990 年代由 Murray Shanahan 与 Rob Miller 用带限定的一阶逻辑重新表述。如何工作。用时间点取代情境。Happens(e, t) 表示事件 e 在时间 t 发生；Initiates(e, f, t) 与 Terminates(e, f, t) 表示它使流 f 变真或变假；HoldsAt(f, t) 表示 f 在 t 时成立。核心的持续公理为：

其中 $\mathrm{Clipped}(t_1,f,t_2)$ 表示在两者之间发生了某个终止 $f$ 的事件。被否定的 $\mathrm{Clipped}$ 通过失败即否定或限定来解读，事件演算正是这样处理框架问题的。今天。它的各种变体在 Prolog 和回答集程序设计中运行，用于叙事理解和数据流中复合事件识别的研究。

6. 统一框架

优先模型与 System P

谁、何时。Sarit Kraus、Daniel Lehmann 与 Menachem Magidor，《非单调推理、优先模型与累积逻辑》（Nonmonotonic Reasoning, Preferential Models and Cumulative Logics），《人工智能》，1990 年 [14]。是什么。KLM 没有再提出一种新逻辑，而是追问任何合理的后承关系 $|\sim$ 应该具有哪些性质。他们的 System P 放弃了单调性，但保留了较弱的规则，其中包括谨慎单调性（cautious monotonicity）：把一个结论加入前提，不会失去其他结论。

从语义上说，当 $\beta$ 在 $\alpha$ 的最受偏好（最正常）的模型中为真时，$\alpha |\sim \beta$ 成立。这为比较各种形式体系提供了共同的尺度。

抽象论辩

谁、何时。Phan Minh Dung，《论论证的可接受性及其在非单调推理、逻辑程序设计与 n 人博弈中的基础作用》，《人工智能》第 77 卷第 2 期，1995 年 [15]。如何工作。论辩框架是一个二元组 $(A,R)$，由抽象的论证和一个攻击关系组成。如果一组论证无冲突，并且能为其中每个成员抵御每一个攻击者，它就是可采纳的；基础（grounded）、优先（preferred）和稳定（stable）扩张是对“可接受集合”的不同选择。Dung 表明，包括缺省逻辑和稳定模型语义下的逻辑程序设计在内的多种非单调形式体系，都可以读作论辩。今天。论辩被用于法律推理、解释和多方决策支持，因为一个被接受的结论会附带为它辩护的论证。

7. 常识推理

常识推理项目

目标。常识推理是得出人们习以为常的日常结论的能力：掉在石头上的玻璃杯多半会碎；一个人在巴黎时不可能同时在东京；餐馆里的顾客通常要付钱。McCarthy 在《具有常识的程序》（Programs with Common Sense，1959）中提出了这一纲领，主张用逻辑表示这类知识 [16]。非单调推理之所以存在，很大程度上是因为常识由缺省构成。

• Cyc（1984 年起）着手大规模地手工编码常识，用语境（微理论）容纳在不同情境下相互冲突的缺省；见知识表示页中的 Cyc [17]。
• Open Mind Common Sense（开放心智常识）于 1999 年在 MIT 媒体实验室启动，从网上的志愿者那里收集常识陈述；它的语义网络 ConceptNet 至今仍在开发。
• Winograd 模式挑战（Levesque、Davis 与 Morgenstern，2012）通过代词消解来测试常识 [18]：在“市议员拒绝给示威者发放许可，因为他们担心暴力”中，他们指市议员；把担心换成鼓吹，就变成指示威者。

现状。大型预训练语言模型大约在 2019–2020 年间在原始的 Winograd 模式上达到了接近人类的准确率，于是人们又构建了规模更大的对抗版本 WinoGrande [19]。基准上的准确率并不等于保证：语言模型会在上下文变化时改变答案，但没有任何东西说明它会撤回哪些结论、为什么撤回。本页的符号形式体系能精确给出这种说明，代价是必须有人把缺省写出来。

8. 时间线

9. 今天用在哪里，以及它的局限

• 数据库与逻辑程序。关系数据库在封闭世界假设下回答查询；建立在稳定模型之上的回答集程序设计，用于带缺省和例外的配置、排程和规划问题。
• 带例外的规则。法律、监管和商业政策都写成带例外和优先级的一般规则，而这正是缺省逻辑和论辩所建模的；执行这类政策的规则引擎见专家系统。
• 诊断与变化。基于模型的诊断中的 ATMS 式推理，以及用于追踪随时间成立之事的事件演算。

局限。非单调推理比经典推理更难，常常在多项式层级中高出整整一层。多个扩张迫使人在轻信与怀疑的答案之间作出选择。不同的形式体系在同一个例子上可能给出不同答案，所以选择形式体系本身就是一个建模决定。而且它们都预设有人已经写好了缺省，这又把问题带回了知识表示的瓶颈。历史脉络见符号 AI 的历史；这一家族在全部符号方法中的位置，见符号 AI 技术总览和符号 AI 概述。

10. 与失效安全模型的联系

失效安全模型是这样一种 AI 模型：失败会把它推向受控的安全状态；证据缺失时它弃权，它的学习可以收窄它的行为，却永远不能扩大它被授权做的事。非单调推理在两个方向上与之相关。它诚实地说明了新证据到来时结论应当如何撤回；一个能够准确说出哪些结论依赖于某个被撤回事实的系统（真值维护系统就能做到），就是一个错误可以被追溯和撤销的系统。

它也提醒我们哪里不该耍聪明。缺省是一种在被反驳之前允许成立的猜测。对于事实，失效安全的设计把尚未接纳的东西当作未知，即开放世界的读法，而不是用缺省去填补空缺；对于权限，它把尚未授予的东西当作拒绝，即封闭世界的读法。两种空缺都不用猜测来填。Perslis Research 的 Peel 据我们所知是第一个失效安全模型：它的知识是有类型、有来源的卡片，学习是可读的计数，做决定的回路中没有神经网络。语言模型可以提议；只有地板能接纳一条事实。Peel 是研究原型，并非经过认证的安全系统。

11. 常见问题

什么是非单调推理？

非单调推理是这样一种推理：加入新信息可能撤销之前得出的结论。从“特威蒂是一只鸟”出发，它得出特威蒂会飞；得知特威蒂是企鹅之后，它收回这个结论。它形式化了带缺省和例外的推理，而经典逻辑做不到这一点。

为什么经典逻辑是单调的？

在经典逻辑中，当一个结论在前提的每个模型中都为真时，它才由前提推出。加入前提只会去掉模型，所以在原来所有模型中都为真的东西，在剩下的模型中仍为真。一个结论一旦被蕴涵，无论再加入什么都仍被蕴涵。

什么是缺省逻辑？

缺省逻辑由 Raymond Reiter 于 1980 年提出，它在一阶逻辑上加入缺省规则。缺省规则说的是：如果前提成立，且辩护与当前信念一致，就得出结论。例如，如果 x 是鸟，且 x 会飞与已知一致，就得出 x 会飞。一个缺省理论所支持的结论集合称为扩张。

缺省逻辑与限定有什么区别？

缺省逻辑加入的是在辩护一致时触发的推理规则。限定由 John McCarthy 于 1980 年提出，它保留普通逻辑，但只考虑极小模型，即让“异常”等选定谓词对尽可能少的对象为真的模型。两者都允许在加入事实时撤回结论。

什么是失败即否定？

失败即否定是 Prolog 等逻辑程序设计语言使用的规则：当所有证明 G 的尝试都失败时，“非 G”成功。Keith Clark 于 1978 年证明它相对于程序的完备化是可靠的。它是非单调的，因为加入一个使 G 可证的事实，会让“非 G”由真变假。

什么是真值维护系统？

真值维护系统由 Jon Doyle 于 1979 年提出，它记录问题求解器的每个结论为什么被相信，并保持这些依赖关系一致。当一个信念被撤回时，所有依赖它的信念也随之撤回。Johan de Kleer 1986 年提出的基于假设的变体，同时追踪所有一致的假设集。

AI 中的框架问题是什么？

框架问题由 McCarthy 与 Hayes 于 1969 年命名，指的是：要在逻辑中说明一个动作没有改变什么，却不为每个不受影响的事实写一条公理，这很困难。非单调推理的应对办法是假定事实会保持不变，除非已知某个动作改变了它；Reiter 的后继状态公理给出了一种紧凑的单调编码。

AI 中的常识推理是什么？

常识推理是得出人们习以为常的日常结论的能力，例如掉落的玻璃杯可能会碎。McCarthy 于 1959 年提出用逻辑表示常识。相关项目包括 Cyc、ConceptNet 和 Winograd 模式挑战。大型语言模型如今在这类基准上得分很高，但并没有说明它们会撤回哪些结论、为什么撤回。

12. 参考文献

1. R. Reiter. A Logic for Default Reasoning. Artificial Intelligence 13(1–2):81–132, 1980.
2. J. McCarthy. Circumscription—A Form of Non-Monotonic Reasoning. Artificial Intelligence 13(1–2):27–39, 1980. doi:10.1016/0004-3702(80)90011-9.
3. D. McDermott, J. Doyle. Non-Monotonic Logic I. Artificial Intelligence 13(1–2):41–72, 1980. doi:10.1016/0004-3702(80)90012-0.
4. R. C. Moore. Semantical Considerations on Nonmonotonic Logic. Artificial Intelligence 25(1):75–94, 1985. doi:10.1016/0004-3702(85)90042-6.
5. R. Reiter. On Closed World Data Bases. In H. Gallaire, J. Minker (eds.), Logic and Data Bases. Plenum Press, 1978.
6. K. L. Clark. Negation as Failure. In H. Gallaire, J. Minker (eds.), Logic and Data Bases, 293–322. Plenum Press, 1978.
7. M. Gelfond, V. Lifschitz. The Stable Model Semantics for Logic Programming. Proceedings of the Fifth International Conference on Logic Programming (ICLP), 1070–1080. MIT Press, 1988.
8. J. Doyle. A Truth Maintenance System. Artificial Intelligence 12(3), 1979.
9. J. de Kleer. An Assumption-based TMS. Artificial Intelligence 28:127–162, 1986.
10. C. E. Alchourrón, P. Gärdenfors, D. Makinson. On the Logic of Theory Change: Partial Meet Contraction and Revision Functions. Journal of Symbolic Logic 50(2):510–530, 1985.
11. J. McCarthy, P. J. Hayes. Some Philosophical Problems from the Standpoint of Artificial Intelligence. In B. Meltzer, D. Michie (eds.), Machine Intelligence 4, 463–502. Edinburgh University Press, 1969.
12. S. Hanks, D. McDermott. Nonmonotonic Logic and Temporal Projection. Artificial Intelligence 33(3):379–412, 1987.
13. R. Kowalski, M. Sergot. A Logic-based Calculus of Events. New Generation Computing, 1986. doi:10.1007/BF03037383.
14. S. Kraus, D. Lehmann, M. Magidor. Nonmonotonic Reasoning, Preferential Models and Cumulative Logics. Artificial Intelligence, 1990. doi:10.1016/0004-3702(90)90101-5.
15. P. M. Dung. On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games. Artificial Intelligence 77(2):321–357, 1995.
16. J. McCarthy. Programs with Common Sense. Symposium on Mechanization of Thought Processes, National Physical Laboratory, Teddington, 1959.
17. D. B. Lenat. CYC: A Large-Scale Investment in Knowledge Infrastructure. Communications of the ACM 38(11), 1995.
18. H. J. Levesque, E. Davis, L. Morgenstern. The Winograd Schema Challenge. Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR 2012), 2012.
19. K. Sakaguchi, R. Le Bras, C. Bhagavatula, Y. Choi. WinoGrande: An Adversarial Winograd Schema Challenge at Scale. Proceedings of AAAI 2020. doi:10.1609/aaai.v34i05.6399. arXiv:1907.10641.