Description Logic

1. Description Logics
 : A family of knowledge representation formalisms
 - a subset of first order predicate logic (FOPL)
 - decidable: trade-off of expressivity against algorithmic complexity

 - Description logics restrict the predicate types that can be used
  1) Person(x): unary predicates denote class membership
  2) hasChild(x, y): binary predicates denote relations (roles) between instances

 - Defining ontologies with Description Logics
  1) describe classes (concepts) in terms of their necessary and sufficient attributes (roles)
   * A is a necessary attribute of C: If an object is an instance of C, then it has A
   * A is a sufficient attribute of C: If an object has A, then it is an instance of C

 - Description Logic Reasoning Tasks
  1) satisfaction: can this class have any instances?
  2) subsumption: is every instance of class A necessarily an instance of class B?
  3) classification: what classes is this object an instance of?

 https://en.wikipedia.org/wiki/Description_logic


2. Syntax
 - Concept Constructors

Boolean class constructors	￢C, C ∩ D, C ∪ D	Child ∩ Happy  => the class of things which are both children and happy
Restrictions on role successors	∀R.C, ∃R.C	∀hasPet.Cat  => the class of things all of whose pets are cats     or, which only have pets that are cats    ! includes those things which have no pets  ∃hasPet.Cat  => the class of things which have some pet that is a cat     ! must have at least one pet
Number restrictions (cardinality constraints) on roles	≤n R, ≥n R, =n R	≥2 originCountry  => the class of things with more than one country of origin
Nominal (singleton concepts)	{x}
Universal class, top	Τ
Contradiction, bottom	⊥

 - Role Constructors

Inverse roles	R-
Transitive roles	R+
Role composition	R ° S

 - OWL and Description Logics
  1) Not every description logic supports all constructors
  2) More constructors = more expressive = higher complexity
  3) OWL DL is equivalent to the logic SHOIN(D)
  http://www.cs.man.ac.uk/~ezolin/dl/


 - Knowledge Bases
  1) TBox terminology: a set of axioms describing the structure of the domain (concepts, roles)

Concept inclusion	C ⊆ D
Concept equivalence	C ≡ D
Role inclusion	R ⊆ S
Role equivalence	R ≡ S
Role transitivity	R+ ⊆ R

  2) ABox terminology: a set of axioms describing a concrete situation (instances)

Concept instantiation	x:D
Role instantiation	<x, y>:R

3. Semantics
 - Description Logics and Predicate Logic
  1) Description Logics are a subset of first order Predicate Logic
  2) Every DL expression can be converted into an equivalent FOPL expression

 - Every concept C is translated to a formula ΦC(x)
  1) Boolean class constructors
   ￢ΦC(x) = Φ￢C(x)
   ΦC∩D(x) = ΦC(x) ∩ ΦD(x)
   ΦC∪D(x) = ΦC(x) ∪ ΦD(x)

  2) Restrictions
   Φ∀R.C(y) = ∀x.R(y,x) ⇒ ΦC(x)
   Φ∃R.C(y) = ∃x.R(y,x) ∧ ΦC(x)

  3) Concept inclusion
   C ⊆ D = ∀x.C(x) ⇒ ΦD(x)

  4) Concept equivalence
   C ≡ D  = ∀x.C(x) ⇔ ΦD(x)

 - Interpretation function : ext()

Syntax	Semantics	Notes
ext(￢C)	△\ext(C)	Complement
ext(C ∩ D)	ext(C) ∩ ext(D)	Conjunction
ext(C ∪ D)	ext(C) ∪ ext(D)	Disjunction
ext(∀R.C)	{x| ∀y.<x,y> ∈ ext(R) ⇒ y ∈ ext(C)}	Universal
ext(∃R.C)	{x| ∃y.<x,y> ∈ ext(R) ∧ y ∈ ext(C)}	Existential
≤n R	{x| #{y| <x,y> ∈ ext(R)} ≤ n }	Max Cardinality
≥n R	{x| #{y| <x,y> ∈ ext(R) ≥ n }	Min Cardinality
=n R	{x| #{y| <x,y> ∈ ext(R) = n }	Cardinality
ext(Τ)	△	Top
ext(⊥)	Ø	Bottom

https://arxiv.org/pdf/1201.4089.pdf