Description Logic - Consistency, Coherence, Entailment & Reduction
Consistency
The simplest form of error is inconsistency. A knowledge base $\mathcal K$ is inconsistent if it is impossible to satisfy:
- $\mathcal K$ is inconsistent if for every $\mathcal I$ we have $\mathcal I\nvDash\mathcal K$.
In addition to knowledge bases, TBoxes and ABoxes can also be inconsistent by themselves.
Coherence
A concept is coherent if it is possible, according to the knowledge base, for there to be objects satisfying it:
- A concept $X$ is coherent in $\mathcal K$ if there is some interpretation $\mathcal I$ such that $\mathcal I\vDash\mathcal K$ and $X^\mathcal I\neq\emptyset$.
Incoherent concepts are not necessarily errors:
- Incoherence of an atommic concept is almost always an error.
- Incoherence of non-atomic concepts are a warning sign, by often not an error.
Coherence Example
For the following TBox:
- $\text{parent}\equiv\text{person}\sqcap\exists\text{hasChild}.\top$
- $\text{grandparent}\equiv\text{person}\sqcap\exists\text{hasChild}.\text{parent}$
The concept $\text{parent}\sqcap\text{grandparent}$ is coherent, while $\neg\text{parent}\sqcap\text{grandparent}$ is not.
Entailment
An assertion $o:X$ is entailed by $\mathcal K$ if every interpretation satisfying $\mathcal K$ also satisfies $o:X$. This is written as:
\[\mathcal K\vDash o:X\]A subsumption $X\sqsubseteq Y$ is entailed by $\mathcal K$ if every interpretation satisfying $\mathcal K$ also satisfies $X\sqsubseteq Y$ (this is also true for $X\equiv Y$). We write this as:
\[\mathcal K\vDash X\sqsubseteq Y\]Only concept assertions can be entailed, therefore $\mathcal K\vDash (o_1,o_2):r$ is impossible.
Entailment Example
Let $\mathcal K=(\mathcal A,\mathcal T)$ be given by:
| ABox |
|---|
| $\text{Ann}:\text{person}\sqcap\neg\text{grandparent}$ |
| $(\text{Ann},\text{Claire}):\text{hasChild}$ |
| TBox |
|---|
| $\text{parent}\equiv\text{person}\sqcap\exists\text{hasChild}.\top$ |
| $\text{grandparent}\equiv\text{person}\sqcap\exists\text{hasChild}.\text{parent}$ |
We have:
- $\mathcal K\vDash\text{Claire}:\neg\text{parent}$
- $\mathcal K\vDash\text{grandparent}\sqsubseteq\text{person}$
Reductions to Consistency
Coherence and entailment are related to consistency:
- Coherence:
- $X$ is coherent in $\mathcal K$ if and only if $(\mathcal A\cup\{o:X\},\mathcal T)$ is consistent, where $o$ does not occur in $\mathcal A$.
- Entailment:
- $\mathcal K\vDash o:X$ if and only if $(\mathcal A\cup\{o:\neg X\},\mathcal T)$ is inconsistent.
- $\mathcal K\vDash X\subseteq Y$ if and only if $(\mathcal A\cup\{o:X,o:\neg Y\},\mathcal T)$ is inconsistent, where $o$ does not occur in $\mathcal A$.
As a result of the reductions, if we can determine whether a knowledge base is consistent, we can also determine coherence and entailment.