The closed world assumption is the presumption that what is not currently known to be true is false. The same name also refer to a logical formalization of this assumption by Ray Reiter. The opposite of the closed world assumption is the open world assumption, stating that lack of knowledge does not imply falsity.

Negation as failure is related to the closed world assumption, as it amounts to believe false every predicate that cannot be proved to be true.

The closed world assumption is often implicit in databases, as every record not explicitly contained in a table is implicitly assumed to represent a fact that is false (rather than unknown). For example, if a database contains the following table reporting editors who have worked on a given article, a query on the people not having edited the article on formal logic is usually expected to return “Sarah Johnson”.

Edit
Editor	Article
John Doe	Formal logic
John Doe	Joshua A. Norton
Sarah Johnson	Charles Ponzi
Emma Lee	Formal logic

This result follows from the fact that no row of the table contains Sarah Johnson in the first position and “Formal logic” in the second position. This argument is implicitly based on the assumption that the lack of a row “Sarah Johnson|Formal logic” from the table implies that Sarah Johnson has not edited the article on formal logic. Therefore, the result of the query is based on the closed world assumption. On the contrary, in the open world assumption, what is not explicitly stated is unknown rather than false. In the open world assumption, Sarah Johnson is not known to have edited the article; in the closed world assumption, she is known not to have edited it.

Formalization in logic

---

The first formalization of the closed world assumption in formal logic consists in adding to the knowledge base the literals that are not currently entailed by it. The result of this addition is always consistent if the knowledge base is in Horn form, but is not guaranteed to be consistent otherwise. For example, the knowledge base

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

entails neither $English(Fred)$ nor $Irish(Fred)$.

Adding the negation of these two literals to the knowledge base leads to

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

which is inconsistent. In other words, this formalization of the closed world assumption sometimes turns a consistent knowledge base into an inconsistent one. The closed world assumption does not introduce an inconsistency on a knowledge base $K$ exactly when the intersection of all Herbrand models of $K$ is also a model of $K$; in the propositional case, this condition is equivalent to $K$ having a single minimal model, where a model is minimal if no other models has a subset of variables assigned to true.

Alternative formalizations not suffering from this problem have been proposed. In the following description, the considered knowledge base $K$ is assumed to be propositional. In all cases, the formalization of the closed world assumption is based on adding to $K$ the negation of the formulae that are “free for negation” for $K$, i.e., the formulae that can be assumed to be false. In other words, the closed world assumption applied to a propositional formula $K$ generates the formula:

$K\; \backslash wedge\; \backslash \{\backslash neg\; f\; ~|~\; f\; \backslash in\; F\backslash \}$.

The set $F$ of formulae that are free for negation in $K$ can be defined in different ways, leading to different formalizations of the closed world assumption. The following are the definitions of $f$ being free for negation in the various formalizations.

CWA (closed world assumption) : $f$ is a positive literal not entailed by $K$;

GCWA (generalized CWA) : $f$ is a positive literal such that, for every positive clause $c$ such that $K\; \backslash not\backslash models\; c$, it holds $T\; \backslash not\backslash models\; c\; \backslash vee\; f$;

EGCWA (extended GCWA): same as above, but $f$ is a conjunction of positive literals;

CCWA (careful CWA): same as GCWA, but a positive clause is only considered if it is composed of positive literals of a given set and (both positive and negative) literals from another set;

ECWA (extended CWA): similar to CCWA, but $f$ is an arbitrary formula not containing literals from a given set.

The ECWA and the formalism of circumscription coincide on propositional theories. The complexity of query answering (checking whether a formula is entailed by another one under the closed world assumption) is typically in the second level of the polynomial hierarchy for general formulae, and ranges from P to coNP for Horn formulae. Checking whether the original closed world assumption introduces an inconsistency requires at most a logarithmic number of calls to an NP oracle; however, the exact complexity of this problem is not currently known.

See also

---

• Open World Assumption
• Non-monotonic logic
• Circumscription
• Negation as failure
• Default logic

References

---

• 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 $\backslash 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.

External links

---

• http://cs.wwc.edu/~aabyan/Logic/CWA.html
• http://www.betaversion.org/~stefano/linotype/news/91/
• http://esw.w3.org/topic/ClosedWorldAssumptions
• Closed World Reasoning in the Semantic Web through Epistemic Operators

Logic in computer science | Databases

封闭世界假定