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

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

Prädikatenlogik und Hornlogik

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

Grundlagen

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

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.