Like
first-order logic (FOL), a
syntax defines which collections of symbols are legal expressions in a description logic, and
semantics determine meaning. Unlike FOL, a DL may have several well known syntactic variants.
Syntax The syntax of a member of the description logic family is characterized by its recursive definition, in which the constructors that can be used to form concept terms are stated. Some constructors are related to logical constructors in
first-order logic (FOL) such as
intersection or
conjunction of concepts,
union or
disjunction of concepts,
negation or
complement of concepts,
universal restriction and
existential restriction. Other constructors have no corresponding construction in FOL including restrictions on roles for example, inverse,
transitivity and functionality.
Notation Let C and D be concepts, a and b be individuals, and R be a role. If a is R-related to b, then b is called an R-successor of a.
The description logic ALC The prototypical DL
Attributive Concept Language with Complements (\mathcal{ALC}) was introduced by Manfred Schmidt-Schauß and Gert Smolka in 1991, and is the basis of many more expressive DLs. The following definitions follow the treatment in Baader et al. Let N_C, N_R and N_O be (respectively)
sets of
concept names (also known as
atomic concepts),
role names and
individual names (also known as
individuals,
nominals or
objects). Then the ordered triple (N_C, N_R, N_O) is the
signature.
Concepts The set of \mathcal{ALC}
concepts is the smallest set such that: • The following are
concepts: • \top (
top is a
concept) • \bot (
bottom is a
concept) • Every A \in N_C (all
atomic concepts are
concepts) • If C and D are
concepts and R \in N_R then the following are
concepts: • C\sqcap D (the intersection of two
concepts is a
concept) • C\sqcup D (the union of two
concepts is a
concept) • \neg C (the complement of a
concept is a
concept) • \forall R.C (the universal restriction of a
concept by a
role is a
concept) • \exists R.C (the existential restriction of a
concept by a
role is a
concept)
Terminological axioms A
general concept inclusion (GCI) has the form C \sqsubseteq D where C and D are
concepts. Write C \equiv D when C \sqsubseteq D and D \sqsubseteq C. A
TBox is any finite set of GCIs.
Assertional axioms • A
concept assertion is a statement of the form a : C where a \in N_O and C is a
concept. • A
role assertion is a statement of the form (a,b) : R where a, b \in N_O and R is a
role. An
ABox is a finite set of assertional axioms.
Knowledge base A
knowledge base (KB) is an ordered pair (\mathcal{T}, \mathcal{A}) for
TBox \mathcal{T} and
ABox \mathcal{A}.
Semantics The
semantics of description logics are defined by interpreting concepts as sets of individuals and roles as sets of ordered pairs of individuals. Those individuals are typically assumed from a given domain. The semantics of non-atomic concepts and roles is then defined in terms of atomic concepts and roles. This is done by using a recursive definition similar to the syntax.
The description logic ALC The following definitions follow the treatment in Baader et al. A
terminological interpretation \mathcal{I}=(\Delta^{\mathcal{I}}, \cdot^{\mathcal{I}}) over a
signature (N_C,N_R,N_O) consists of • a non-empty set \Delta^{\mathcal{I}} called the
domain • a
interpretation function \cdot^{\mathcal{I}} that maps: • every
individual a to an element a^{\mathcal{I}} \in \Delta^{\mathcal{I}} • every
concept to a subset of \Delta^{\mathcal{I}} • every
role name to a subset of \Delta^{\mathcal{I}} \times \Delta^{\mathcal{I}} such that • \top^{\mathcal{I}} = \Delta^{\mathcal{I}} • \bot^{\mathcal{I}} = \emptyset • (C \sqcup D)^{\mathcal{I}} = C^{\mathcal{I}} \cup D^{\mathcal{I}}
(union means disjunction) • (C \sqcap D)^{\mathcal{I}} = C^{\mathcal{I}} \cap D^{\mathcal{I}}
(intersection means conjunction) • (\neg C)^{\mathcal{I}} = \Delta^{\mathcal{I}} \setminus C^{\mathcal{I}}
(complement means negation) • (\forall R.C)^{\mathcal{I}} = \{x \in \Delta^{\mathcal{I}} \mid \text{for} \; \text{every} \; y, (x,y) \in R^{\mathcal{I}} \; \text{implies} \; y \in C^{\mathcal{I}} \} • (\exists R.C)^{\mathcal{I}} = \{x \in \Delta^{\mathcal{I}} \mid \text{there} \; \text{exists} \; y, (x,y) \in R^{\mathcal{I}} \; \text{and} \; y \in C^{\mathcal{I}}\} Define \mathcal{I} \models (read
in I holds) as follows
TBox • \mathcal{I} \models C \sqsubseteq D if and only if C^{\mathcal{I}} \subseteq D^{\mathcal{I}} • \mathcal{I} \models \mathcal{T} if and only if \mathcal{I} \models \Phi for every \Phi \in \mathcal{T}
ABox • \mathcal{I} \models a : C if and only if a^{\mathcal{I}} \in C^{\mathcal{I}} • \mathcal{I} \models (a,b) : R if and only if (a^{\mathcal{I}},b^{\mathcal{I}}) \in R^{\mathcal{I}} • \mathcal{I} \models \mathcal{A} if and only if \mathcal{I} \models \phi for every \phi \in \mathcal{A}
Knowledge base Let \mathcal{K} = (\mathcal{T}, \mathcal{A}) be a knowledge base. • \mathcal{I} \models \mathcal{K} if and only if \mathcal{I} \models \mathcal{T} and \mathcal{I} \models \mathcal{A} ==Inference==