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

Aus Wikiversity
Zur Navigation springen Zur Suche springen


Prädikatenlogik und Hornlogik[Bearbeiten]

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

Grundlagen[Bearbeiten]

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

Literatur[Bearbeiten]

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.


Vorheriges Thema.jpg Discussion Nächstes Thema.jpg