|
|
| Line 1: |
Line 1: |
| {{inline|date=August 2011}}
| | .mw-body, mtext { |
| The '''closed world assumption''' (CWA) is the presumption that what is not currently known to be true is false. The same name also refers to a [[formal logic|logical]] formalization of this assumption by [[Raymond Reiter]]. The opposite of the closed world assumption is the [[Open world assumption|open world assumption (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 can not avoid an explicit revelation of whether the implicit logical backgrounds are based on CWA or OWA.
| | font-family: XITS, STIX; |
| | | } |
| [[Negation as failure]] is related to the closed world assumption, as it amounts to believing false every predicate that cannot be proved to be true.
| | math { |
| | | font-family: XITS Math, STIX Math; |
| In the [[knowledge management]] area, 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”.
| | } |
| | |
| {| border="1" cellspacing="0" cellpadding="2" align="center" | |
| ! colspan="2" style="background:#ffdead;" | Edit
| |
| |-
| |
| ! style="background:#efefef;" | Editor
| |
| ! style="background:#efefef;" | 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 knowledge base|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 [[logic|formal logic]] consists in adding to the knowledge base the negation of the literals that are not currently [[logical consequence|entailed]] by it. The result of this addition is always [[consistent]] if the knowledge base is in [[Horn clause|Horn form]], but is not guaranteed to be consistent otherwise. For example, the knowledge base
| |
| :<math>\{English(Fred) \vee Irish(Fred)\}</math>
| |
| entails neither <math>English(Fred)</math> nor <math>Irish(Fred)</math>.
| |
| | |
| Adding the negation of these two literals to the knowledge base leads to
| |
| :<math>\{English(Fred) \vee Irish(Fred), \neg English(Fred), \neg Irish(Fred)\}</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 <math>K</math> exactly when the intersection of all [[Herbrand model]]s of <math>K</math> is also a model of <math>K</math>; in the propositional case, this condition is equivalent to <math>K</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 <math>K</math> is assumed to be propositional. In all cases, the formalization of the closed world assumption is based on adding to <math>K</math> the negation of the formulae that are “free for negation” for <math>K</math>, i.e., the formulae that can be assumed to be false. In other words, the closed world assumption applied to a [[propositional formula]] <math>K</math> generates the formula:
| |
| :<math>K \wedge \{\neg f ~|~ f \in F\}</math>.
| |
| The set <math>F</math> of formulae that are free for negation in <math>K</math> can be defined in different ways, leading to different formalizations of the closed world assumption. The following are the definitions of <math>f</math> being free for negation in the various formalizations.
| |
| | |
| ; CWA (closed world assumption) : <math>f</math> is a positive literal not entailed by <math>K</math>;
| |
| | |
| ; GCWA (generalized CWA) : <math>f</math> is a positive literal such that, for every positive clause <math>c</math> such that <math>K \not\models c</math>, it holds <math>T \not\models c \vee f</math>;
| |
| | |
| ; EGCWA (extended GCWA): same as above, but <math>f</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 <math>f</math> is an arbitrary formula not containing literals from a given set.
| |
| | |
| The ECWA and the formalism of [[Circumscription (logic)|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 (complexity)|P]] to [[coNP]] for [[Horn clause|Horn formulae]]. Checking whether the original closed world assumption introduces an inconsistency requires at most a logarithmic number of calls to an [[Oracle machine|NP oracle]]; however, the exact complexity of this problem is not currently known.
| |
| | |
| ==See also==
| |
| | |
| * [[Open world assumption]]
| |
| * [[Non-monotonic logic]]
| |
| * [[Circumscription (logic)]]
| |
| * [[Negation as failure]]
| |
| * [[Default logic]]
| |
| * [[Stable model semantics]]
| |
| * [[Unique name assumption]]
| |
| | |
| ==References==
| |
| *{{cite journal |last1=Cadoli |first1=Marco |last2=Lenzerini |first2=Maurizio |title=The complexity of propositional closed world reasoning and circumscription |journal=Journal of Computer and System Sciences |date=April 1994 |volume=48 |issue=2 |pages=255–310 |doi=10.1016/S0022-0000(05)80004-2 |url=http://www.sciencedirect.com/science/article/pii/S0022000005800042 |accessdate=20 February 2013 |issn=0022-0000}}
| |
| *{{cite journal |last1=Eiter |first1=Thomas |last2=Gottlob |authorlink2=Georg Gottlob |first2=Georg |title=Propositional circumscription and extended closed-world reasoning are <math>\Pi^p_2</math>-complete |journal=Theoretical Computer Science |date=June 1993 |volume=114 |issue=2 |pages=231–245 |doi=10.1016/0304-3975(93)90073-3 |url=http://www.sciencedirect.com/science/article/pii/0304397593900733 |accessdate=20 February 2013 |issn=0304-3975}}
| |
| *{{cite journal |last1=Rajasekar |first1=Arcot |last2=Lobo |first2=Jorge |last3=Minker |first3=Jack |authorlink3=Jack Minker |title=Weak Generalized Closed World Assumption |journal=Journal of Automated Reasoning |date=September 1989 |volume=5 |issue=3 |pages=293–307 |doi=10.1007/BF00248321 |url=http://link.springer.com/article/10.1007/BF00248321 |accessdate=20 February 2013 |publisher=Kluwer Academic Publishers |issn=0168-7433}}
| |
| *{{cite journal |last=Lifschitz |first=Vladimir |authorlink=Vladimir Lifschitz |title=Closed-world databases and circumscription |journal=Artificial Intelligence |date=November 1985 |volume=27 |issue=2 |pages=229–235 |doi=10.1016/0004-3702(85)90055-4 |url=http://www.sciencedirect.com/science/article/pii/0004370285900554 |accessdate=20 February 2013 |issn=0004-3702}}
| |
| * J. Minker (1982). On indefinite databases and the closed world assumption. In ''Proceedings of the Sixth International Conference on Automated Deduction (CADE'82)'', pp. 292–308.
| |
| *{{cite book |last=Reiter |first=Raymond |authorlink=Raymond Reiter |editor1-last=Gallaire |editor1-first=Hervé |editor2-last=Minker |editor2-first=Jack |editor2-link=Jack Minker |title=Logic and Data Bases |year=1978 |publisher=Plenum Press |isbn=9780306400605 |url=http://www.springer.com/computer/security+and+cryptology/book/978-0-306-40060-5 |accessdate=21 February 2013 |chapter=On Closed World Data Bases |pages=119–140}}
| |
| *{{cite journal |last1=Duan |first1=Yucong |last2=Cruz |first2=Christophe |title=Formalizing Semantic of Natural Language through Conceptualization from Existence |journal=International Journal of Innovation, Management and Technology |date=February 2011 |volume=2 |issue=1 |pages=37–42 |doi=10.7763/IJIMT.2011.V2.100 |url=http://ijimt.org/abstract/100-E00187.htm |accessdate=21 February 2013 |issn=2010-0248}}
| |
| | |
| ==External links==
| |
| * http://www.betaversion.org/~stefano/linotype/news/91/
| |
| * [http://www.mindswap.org/2005/OWLWorkshop/sub12.pdf Closed World Reasoning in the Semantic Web through Epistemic Operators]
| |
| * [http://books.hammerpig.com/the-closed-world-assumption-of-databases.html Excerpt from Reiter's 1978 talk on the closed world assumption]
| |
| | |
| [[Category:Logic programming]]
| |
| [[Category:Knowledge representation]]
| |
.mw-body, mtext {
font-family: XITS, STIX;
}
math {
font-family: XITS Math, STIX Math;
}