Kurs:Algorithmen und Datenstrukturen/Vorlesung/Prädikatenlogik&Hornlogik


Prädikatenlogik und HornlogikBearbeiten

In diesem Kapitel werden die Grundlagen der Prädikatenlogik und Hornlogik erläutert.

GrundlagenBearbeiten

Sei U eine Menge von Konstanten, V eine Menge von Variablen, und P eine Menge von Prädikatsymbolen.

  • Ein Term ist entweder eine Konstante oder eine Variable (prinzipiell sind auch Funktionsterme möglich, werden hier aber ignoriert)
  • X,Y,... sind Variablen (und Terme)
  • anna, bob, dave,... sind Konstanten (und Terme)
  • Ein Atom ist ein n-stelliges Prädikat, gefolgt von n Termen
  • parent(bob,anna) ist ein Atom
  • sibling(anna, X) ist ein Atom
  • Eine atomare Konjunktion ist eine Menge von Atomen
  • parent(X,anna) ∧ sibling(anna,Y) ∧ parent (anna,tina)
  • Bei logischer Programmierung wird oft das Komma für die Konjunktion verwendet: parent (X,anna), sibling(anna,Y), parent(anna,tina)
  • Eine Hornklausel ist eine Implikation einer atomaren Konjunktion zu einem Atom
  • grandparent(X,Y) ⇐ parent(X,Z) ∧ parent(Z,Y)
  • In Prolog: grandparent(X,Y) :- parent(X,Z), parent(Z,Y).
  • Anmerkung: Ein Hornklausel ist eigentlich definiert als eine Disjunktion mit maximal einem positiven Atom

LiteraturBearbeiten

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 3.4.1 zu finden.