ALC , the basic DL containing all Boolean connectives, and the relevant inference problems. Then, we consider different possibilities for extending ALC to more expressive DLs. Definition 1 ( ALC Syntax). Let Nc, Nr, and N, be countable and pairwise disjoint sets of concept, role, and individual names, respectively. The set of ALC concept descriptions is the smallest set such that 1. every concept name is a concept description,

2. if C and D are concept descriptions and R is a role name, then the following expressions are also concept descriptions:
- ¬ C (negation), C ∩ D (conjunction), C ∩ D (disjunction), - Ð R.C (existential restriction), and VR.C (value restriction).
We use T as an abbreviation of A ∪ ¬ A and ⊥ as an abbreviation for A ∩ ¬ A (where A is an arbitrary concept name).

Let C and D be concept descriptions. Then C ⊆ D is a general concept inclusion axiom
(GCI). A finite set of such axioms is called a T Box .

Let C be a concept description, R a role name, and i, j individual names. Then C ( i ) is a concept assertion and R ( i, j ) a role assertion. A finite set of such assertions is called an ABox.

The meaning of ALC-concept descriptions, TBoxes, and ABoxes can be defined with the help of a set-theoretic semantics. Definition 2 ( ALC Semantics). An ALC-interpretation I is a pair ( Δ X, X ), where Δ X
is a nonempty set, the domain of the interpretation, and . I is the interpretation function.

The interpretation function maps
- each concept name A to a subset A T of A T
- each role name R to a subset R x of ∆ x × ∆ x,

- each individual name i to an element i T of ∆ T such that different names are mapped to different elements (unique name assumption).
For a role name R and an element a ∈ ∆ x we define R x ( a ) := { b | ( a, b ) ∈ R x }. The interpretation function can inductively be extended to complex concepts as follows:
(¬C) x := A x \ C x
(C Π D ) Z := C Z ∩ D Z (C U D ) I := C I U D I
(ÐR.C) T := { a ∈ Δ T | R T ( a ) ∩ C T ̸ = ∅}
( AR C ) T := { a ∈ Δ T | R T ( a ) ⊆ C T }
An interpretation I is a model of the TBox T iff it satisfies C I ⊆ D I for all GCIs C ⊆ D
in T . It is a model of the ABox A iff it satisfies i T E C T for all concept assertions C (i) E A
and ( i X, j X ) ∈ R X for all role assertions R ( i, j ) ∈ A.  Finally, I is a model of an ABox relative to a TBox iff it is a model of both the ABox and the TBox.