封闭世界假定

维基百科，自由的百科全书

封闭世界假定是当前不是已知的事物都为假的假定。这个名字也称呼 Ray Reiter 对这个假定的逻辑形式化。与封闭世界假定相对立的使用开放世界假定，宣称知识的缺乏不蕴涵虚假。

否定为失败与封闭世界假定有关，因为它总体上相信不能被证明为真的所有命题都是假的。

封闭世界假定经常暗含在数据库中，因为所有没有明确的包换在表中记录都暗含的假定表示这是假(而不是未知)这个事实。例如，如果数据库包含下列表，报告写作给定文章的人的，关于没有编辑形式逻辑的文章的人的查询，经常被预期返回 “Sarah”。

编辑
编辑者	文章
John	形式逻辑
John	Joshua A. Norton
Sarah	Charles Ponzi
Emma	形式逻辑

这个结果服从表中不包含 Sarah 在第一个位置而“形式逻辑”在第二个位置的行的事实。这个论证暗含的是基于表中缺乏“Sarah|形式逻辑”这样的行蕴涵 Sarah 没有编辑关于形式逻辑的文章的假定。所以，这个查询的结果基于的是封闭世界假定，与之相对，在开放世界假定中，没有明确的陈述的事物是未知的而不是假的。在开放世界假定中，Sarah 编辑这个文章是未知的；在封闭世界假说中，她没有编辑这个文章是已知的。

[编辑] 逻辑形式化

封闭世界假定首要逻辑形式化在于向知识库增加当前不被它所蕴涵的文字。如果知识库是Horn 范式的，则这种增加的结果总是相容的，但是在其他情况下就不保证了。例如，知识库

$\{English(Fred) \vee Irish(Fred)\}$

不蕴涵 $E n g l i s h (F r e d)$ 也不蕴涵 $I r i s h (F r e d)$ 。

向知识库增加这两个文字的否定会导致

$\{English(Fred) \vee Irish(Fred), \neg English(Fred), \neg Irish(Fred)\}$

这是矛盾的。换句话说，封闭世界假定的这种形式化有时把相容的知识库转变成矛盾的。在知识库 $K$ 的所有 Herbrand 模型的交集也是 $K$ 的模型的时候，封闭世界假定完全不会把矛盾介入 $K$ ；在命题的情况下，这个条件等价于 $K$ 有一个单一的最小化模型，这里模型是最小化的，如果没有其他模型拥有被指派为真的这些变量的子集。

不能忍受这个问题的可供选择的形式化已经被提出了。在下列描述中，考虑的知识库 $K$ 被假定为是命题的。在所有情况下，封闭世界假定的形式化都是基于向 $K$ 增加 $K$ 的“自由否定”--就是说可以被假定为假的公式的否定。换句话说，封闭世界假定应用于命题公式 $K$ 生成公式:

$K \wedge \{\neg f ~|~ f \in F\}$ 。

$K$ 的自由否定的公式集合 $F$ 可以用不同方式定义，这导致封闭世界假定的不同的形式化。下面是在各种形式化中是自由否定的 $f$ 的定义。

CWA (封闭世界假定): $f$ 是不被 $K$ 蕴涵的肯定文字；

GCWA (普遍 CWA): $f$ 是肯定命题，使得对于 $K \not\models c$ 的所有肯定子句 $c$ ， $T \not\models c \vee f$ 成立；

EGCWA (扩展 GCWA): 同上，但 $f$ 是肯定文字的合取；

CCWA (仔细 CWA): 同于 GCWA，但是只考虑肯定子句，如果它是由给定集合的肯定文字和来自其他集合的(肯定和否定二者)文字构成的；

ECWA (扩展 CWA): 类似于 CCWA，但是 $f$ 是不包含来自给定集合的文字的任意公式。

ECWA 和界限的公式化在命题理论上是一致的。查询答复的复杂性(在封闭世界假定下检查一个公式是否被另一个公式所蕴涵)对于一般公式集典型的是在多项式层次中第二级中的，并且对于 Horn 公式范围是从 P 到 coNP。检查最初的封闭世界假定是否介入矛盾，要求对 NP oracle 的最多对数次的调用，这个问题的精确的复杂性还不知道。

[编辑] 参见

[编辑] 引用

M. Cadoli and M. Lenzerini (1994). The complexity of propositional closed world reasoning and circumscription. Journal of Computer and System Sciences, 48:255-310.

T. Eiter and G. Gottlob (1993). Propositional circumscription and extended closed world reasoning are $\Pi^p_2$ -complete. Theoretical Computer Science, 114:231-245.

V. Lifschitz (1985). Closed-world databases and circumscription. Artificial Intelligence, 27:229-235.

J. Minker (1982). On indefinite databases and the closed world assumption. In Proceedings of the Sixth International Conference on Automated Deduction (CADE'82), pages 292-308.

A. Rajasekar, J. Lobo, and J. Minker (1989). Weak generalized closed world assumption. Journal of Automated Reasoning, 5:293-307.

R. Reiter (1978). On closed world data bases. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pages 119-140. Plenum Publ.\ Co., New York.