Added to Favorites

Related Searches

Definitions

Nearby Words

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

## Formalization in logic

## See also

## References

## External links

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.

In the knowledge management arena, the closed world assumption is used in at least two situations: 1) when the knowledge base is known to be complete (e.g., a corporate database containing records for every employee), and 2) when the knowledge base is known to be incomplete but a "best" definite answer must be derived from incomplete information. 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 | Closed World Assumption |

Joshua A. Norton | Formal Logic |

Sarah Johnson | Introduction to Spatial Databases |

Charles Ponzi | Formal Logic |

Emma Lee-Choon | Formal Logic |

In the closed world assumption, the table is assumed to be complete (it lists all editor-article relationships), and Sarah Johnson is the only editor who has not edited the article on Formal Logic. In contrast, with the open world assumption the table is not assumed to contain all editor-article tuples, and the answer to who has not edited the Formal Logic article is unknown. There is an unknown number of editors not listed in the table, and an unknown number of articles edited by Sarah Johnson that are also not listed in the table.

The first formalization of the closed world assumption in formal logic consists in adding to the knowledge base the negation of 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

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

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

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

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\; wedge\; \{neg\; f\; ~|~\; f\; in\; F\}$.

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.

- Open world assumption
- Non-monotonic logic
- Circumscription (logic)
- Negation as failure
- Default logic
- Stable model semantics
- Unique name assumption

- 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.
- A. Rajasekar, J. Lobo, and J. Minker (1989). Weak generalized closed world assumption. Journal of Automated Reasoning, 5:293-307.
- 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.
- 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.

- 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

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Saturday October 11, 2008 at 07:21:06 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Saturday October 11, 2008 at 07:21:06 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.