HOME

TheInfoList



OR:

The closed-world assumption (CWA), in a formal system of logic used for
knowledge representation Knowledge representation and reasoning (KRR, KR&R, KR²) is the field of artificial intelligence (AI) dedicated to representing information about the world in a form that a computer system can use to solve complex tasks such as diagnosing a medic ...
, is the presumption that a statement that is true is also known to be true. Therefore, conversely, what is not currently known to be true, is false. The same name also refers to a
logical Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
formalization of this assumption by
Raymond Reiter 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 ...
. The opposite of the closed-world assumption is the
open-world assumption In a formal system of logic used for knowledge representation, the open-world assumption is the assumption that the truth value of a statement may be true irrespective of whether or not it is ''known'' to be true. It is the opposite of the clo ...
(OWA), stating that lack of knowledge does not imply falsity. Decisions on CWA vs. OWA determine the understanding of the actual semantics of a conceptual expression with the same notations of concepts. A successful formalization of natural language semantics usually cannot avoid an explicit revelation of whether the implicit logical backgrounds are based on CWA or OWA.
Negation as failure Negation as failure (NAF, for short) is a non-monotonic inference rule in logic programming, used to derive \mathrm~p (i.e. that ~p is assumed not to hold) from failure to derive ~p. Note that \mathrm ~p can be different from the statement \neg p ...
is related to the closed-world assumption, as it amounts to believing false every predicate that cannot be proved to be true.


Example

In the context of
knowledge management Knowledge management (KM) is the collection of methods relating to creating, sharing, using and managing the knowledge and information of an organization. It refers to a multidisciplinary approach to achieve organisational objectives by making ...
, 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 In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases span ...
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".
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 Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
consists in adding to the knowledge base the negation of the literals that are not currently
entailed In English common law, fee tail or entail is a form of trust established by deed or settlement which restricts the sale or inheritance of an estate in real property and prevents the property from being sold, devised by will, or otherwise alie ...
by it. The result of this addition is always
consistent In classical deductive logic, a consistent theory is one that does not lead to a logical contradiction. The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a theory is consistent i ...
if the knowledge base is in Horn form, but is not guaranteed to be consistent otherwise. For example, the knowledge base :\ entails neither English(Fred) nor Irish(Fred). Adding the negation of these two literals to the knowledge base leads to :\ 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 model 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 knowledge base K generates the knowledge base :K \cup \. 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 \not\vdash c, it holds K \not\vdash c \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 Circumscription may refer to: *Circumscribed circle *Circumscription (logic) *Circumscription (taxonomy) * Circumscription theory, a theory about the origins of the political state in the history of human evolution proposed by the American anthrop ...
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 In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. ...
for general formulae, and ranges from P to
coNP In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP precisely ...
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.Cadoli, Marco; Lenzerini, Maurizio (April 1994). "The complexity of propositional closed world reasoning and circumscription". Journal of Computer and System Sciences. 48 (2): 255–310. . ISSN 0022-0000. In situations where it is not possible to assume a closed world for all predicates, yet some of them are known to be closed, the
partial-closed world assumption In a formal system of logic used for knowledge representation, the open-world assumption is the assumption that the truth value of a statement may be true irrespective of whether or not it is ''known'' to be true. It is the opposite of the clo ...
can be used. This regime considers knowledge bases generally to be open, i.e., potentially incomplete, yet allows to use completeness assertions to specify parts of the knowledge base that are closed.


See also

*
Open-world assumption In a formal system of logic used for knowledge representation, the open-world assumption is the assumption that the truth value of a statement may be true irrespective of whether or not it is ''known'' to be true. It is the opposite of the clo ...
*
Partial-closed world assumption In a formal system of logic used for knowledge representation, the open-world assumption is the assumption that the truth value of a statement may be true irrespective of whether or not it is ''known'' to be true. It is the opposite of the clo ...
*
Non-monotonic logic A non-monotonic logic is a formal logic whose conclusion relation is not monotonic. In other words, non-monotonic logics are devised to capture and represent defeasible inferences (cf. defeasible reasoning), i.e., a kind of inference in which re ...
*
Circumscription (logic) 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 ...
*
Negation as failure Negation as failure (NAF, for short) is a non-monotonic inference rule in logic programming, used to derive \mathrm~p (i.e. that ~p is assumed not to hold) from failure to derive ~p. Note that \mathrm ~p can be different from the statement \neg p ...
*
Default logic 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 ...
*
Stable model semantics 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 com ...
*
Unique name assumption The unique name assumption is a simplifying assumption made in some ontology languages and description logics. In logics with the unique name assumption, different names always refer to different entities in the world. It was included in Ray Reite ...


References


External links

* https://web.archive.org/web/20090624113015/http://www.betaversion.org/~stefano/linotype/news/91/
Closed World Reasoning in the Semantic Web through Epistemic Operators


{{DEFAULTSORT:Closed-world assumption Logic programming Knowledge representation