Closed-world assumption

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 atoms 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

${\displaystyle \{English(Fred)\vee Irish(Fred)\}}$

entails neither ${\displaystyle English(Fred)}$ nor ${\displaystyle Irish(Fred)}$.

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

${\displaystyle \{English(Fred)\vee Irish(Fred),\mathrm{\neg }English(Fred),\mathrm{\neg }Irish(Fred)\}}$

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

${\displaystyle K\cup \{\mathrm{\neg }f|f\in F\}}$.

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

CWA (closed-world assumption)

${\displaystyle f}$ is a positive literal not entailed by ${\displaystyle K}$;

GCWA (generalized CWA)

${\displaystyle f}$ is a positive literal such that, for every positive clause ${\displaystyle c}$ such that ${\displaystyle K⊬c}$, it holds ${\displaystyle K⊬c\vee f}$;

EGCWA (extended GCWA)

same as above, but ${\displaystyle 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 ${\displaystyle 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.

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

Partial-closed world assumption

The language of logic programs with strong negation allows us to postulate the closed-world assumption for some statements and leave the other statements in the realm of the open-world assumption. An intermediate ground between OWA and CWA is provided by the partial-closed world assumption (PCWA). Under the PCWA, the knowledge base is generally treated under open-world semantics, yet it is possible to assert parts that should be treated under closed-world semantics, via completeness assertions. The PCWA is especially needed for situations where the CWA is not applicable due to an open domain, yet the OWA is too credulous in allowing anything to be possibly true.