Closed World Assumption

Information about Closed World Assumption

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 Raymond 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.

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.

Formalization in logic

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

$\text{[math]}$

entails neither $\text{[math]}$ nor $\text{[math]}$ .

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

$\text{[math]}$

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 $\text{[math]}$ exactly when the intersection of all Herbrand models of $\text{[math]}$ is also a model of $\text{[math]}$ ; in the propositional case, this condition is equivalent to $\text{[math]}$ 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 $\text{[math]}$ is assumed to be propositional. In all cases, the formalization of the closed world assumption is based on adding to $\text{[math]}$ the negation of the formulae that are “free for negation” for $\text{[math]}$ , i.e., the formulae that can be assumed to be false. In other words, the closed world assumption applied to a propositional formula $\text{[math]}$ generates the formula:

$\text{[math]}$ .

The set $\text{[math]}$ of formulae that are free for negation in $\text{[math]}$ can be defined in different ways, leading to different formalizations of the closed world assumption. The following are the definitions of $\text{[math]}$ being free for negation in the various formalizations.

CWA (closed world assumption): $\text{[math]}$ is a positive literal not entailed by $\text{[math]}$ ;

GCWA (generalized CWA): $\text{[math]}$ is a positive literal such that, for every positive clause $\text{[math]}$ such that $\text{[math]}$ , it holds $\text{[math]}$ ;

EGCWA (extended GCWA): same as above, but $\text{[math]}$ 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 $\text{[math]}$ 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.

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 $\text{[math]}$ -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

Logic (from Classical Greek λόγος logos; meaning word, thought, idea, argument, account, reason, or principle) is the study of the principles and criteria of valid inference and demonstration.
..... Click the link for more information.

Raymond Reiter (June 12, 1939 – September 16, 2002), was a Canadian computer scientist and logician. He was one of the founders of the field of non-monotonic reasoning with his work on default logic, model-based diagnosis, closed world reasoning, and truth maintenance systems.
..... Click the link for more information.

The introduction to this article provides insufficient context for those unfamiliar with the subject matter.
Please help [ improve the introduction] to meet Wikipedia's layout standards.

..... Click the link for more information.

Negation as failure (NAF, for short) is a non-monotonic inference rule in logic programming, used to derive from failure to derive . It has been an important feature of logic programming since the earliest days of both Planner and Prolog.
..... Click the link for more information.

Knowledge Management ('KM') comprises a range of practices used by organisations to identify, create, represent, and distribute knowledge for reuse, awareness and learning.
..... Click the link for more information.

database is a structured collection of records or data that is stored in a computer system so that a computer program or person using a query language can consult it to answer queries. The records retrieved in answer to queries are information that can be used to make decisions.
..... Click the link for more information.

In mathematical logic, a Horn clause is a clause (a disjunction of literals) with at most one positive literal. They are named for the logician Alfred Horn, who first pointed out the significance of such clauses in 1951, in the article "On sentences which are true of direct unions
..... Click the link for more information.

Circumscription is a non-monotonic logic created by John McCarthy to formalize the common sense assumption that things are as expected unless otherwise specified. Circumscription was later used by McCarthy in an attempt to solve the frame problem.
..... Click the link for more information.

In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines.

Definitions

There are multiple equivalent definitions of the classes of the polynomial hierarchy.
..... Click the link for more information.

In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.
..... Click the link for more information.

oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any complexity class.
..... Click the link for more information.

The introduction to this article provides insufficient context for those unfamiliar with the subject matter.
Please help [ improve the introduction] to meet Wikipedia's layout standards.

..... Click the link for more information.

A non-monotonic logic is a formal logic whose consequence relation is not monotonic. Most studied formal logics have a monotonic consequence relation, meaning that adding a formula to a theory never produces a reduction of its set of consequences.
..... Click the link for more information.

Default logic is a non-monotonic logic proposed by Raymond Reiter to formalize reasoning with default assumptions.

Default logic can express facts like “by default, something is true”; by contrast, standard logic can only express that something is true or that
..... Click the link for more information.

The concept of a stable model, or answer set, is used to define a declarative semantics for logic programs with negation as failure. This is one of several standard approaches to the meaning of negation in logic programming, along with program completion and the well-founded
..... Click the link for more information.

This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.

Herod_Archelaus

iPedia Free Information Center