Change: Description Logics

created on March 2, 2013, 8:54 p.m. by Hevok & updated on March 6, 2013, 5:58 p.m. by Hevok

Description Logics are a family of Languages for Knowledge Representations. Most Description Logics are a subset of First Order Logic, but in difference to First Order Logic most describe Logics decidable (and computable therefore). Therefore, it is possible to make logical Deductions based on Description Logics, i.e. to create new Knowledge from existing Knowledge.

In general in Description Logics one is talking about Knowledge Bases. For this for example one describes Classes and Individuals. In a Knowledge Base given as Description Logics one distinguishes between the Terminological Knowledge which means the Knowledge about the Concepts of a Domain (Classes, Attributes, Relations) and the Assertional Knowledge, i.e. Knowledge about the Individuals (Instances/Entities). They both together form the Knowledge Base which is the Basis of Logic where one can make Inferences, Deductions and Calculations on.

In Description Logics one has Concepts or Classes. They can be described as unary Predicates and they represent Entities and Classes. They can be described as unary predicate like all students can be defend by a Predicate, if one wants to put this in a Formal Language. This Concepts are Classes and Classes are defined as Individuals that belong to this Class.

On the other hand one is talking about Roles, which means in this Context the same Thing as Properties. Roles are binary Predicates which means they represent the Relations between one Class and another Class. For instance participatesAt connects two individuals that belong to different Classes, e.g. to People and a Lecture. Further assume the Property/Role givesLecture is a Property that connects peoples also to Lecture. The other way around would be isGivenByLecturer is a Property that connects a Lecture with some Person/Professor. It is formally defined as a binary attribute that connects all Individuals x and y that are connected by this binary Predicate.

In Description Logics to just identify Classes and Relations by their Name there is the convention to write Classes with capital Letter and Roles with a lower case first Letter in order to distinguish between them.

  • Concepts (unary Predicates),
    • represent Entities/Classes
    • e.g. Person, Course, Student, Lecturer, Seminar, ... Student: { x | Student(x)}
  • Roles (binary Predicates, Properties)

    • represent Properties/Relations
    • e.g., participatesAt, givesLecture, isGivenByLecturer, ... participatesAt: {(x,y)|participatesAt(x,y)}
  • Individuals (Constants, Individuals Entities, Concept Assertion)

  • e.g. Hevok, EVA, Denigma
  • Syntax: Agent(Hevok)

  • Operators/Constructs (to construct complex representations of Concepts/Roles)

  • Expressivity is limited:
    • Satisfiability and Subsumption is decidable and
    • (preferably) of low complexity
    • Syntax: participatesAt(Hevok, Denigma)

An individual is defined by Instantiation of a Class, e.g. Hevok is of Class Agent. An Instantiation of a Property or a Role, e.g. Hevok participates at Denigma. Then one limits the expressibility of all operators that come now. This means that Satisfiability and Subsumption both for an insertion in Description Logics must be decidable and preferably in a low complexity.

To Define classes one has some fundamental operators like those from Set Theory. One can also quantify Classes and Negations, but they are restricted in some sense in Description Logics

The problem with First Order Logic that it is not computable is most time given be quantifications. i.e. if one does Statements of all individuals of a Class or Existence and non-existence of an Individuals, the problem is when one is dealing with Classes that are potentially unlimited, the computation for instance for Class Membership might not end, because it would take infinitively long. Therefore on has to restrict the Quantification somehow.

One of the most basic and simple Restriction Logics is the Attributive Language with Complement (ALC). Use GPUs via web browser to calculate logic. Conjunction is logical AND and Disjunction means logical OR. There is also Negation.

  • Fundamental operators:
  • Conjunction (∩),
  • Disjunction (∪),
  • Negation (¬)
  • restriction form of Quantification (,)
  • represents Basic Description Logic
  • Attributive Language with Complement

Besides ALC there are many different kinds of Description Logics and they have difficult names which are derived from Operators and Constructors they are using. Also the complexity of a single Description Logic heavily depends on which Constructors can be used inside a Description Logic. So there are several Different Constructors.

A star means that all the Constructors may be in connection with the roles/properties, they may be transitive. Considering transitive Statements and expressions and transitive Roles, then one is not talking anymore about AL, but about S. For instance on can have SHIL of a class if one subsumes all of these Constructors for it.

DescriptionLogics.png

Categories: Concept
Parent: Logic

Comment: Corrected typos.

See entry | Admin

Comment on This Data Unit