Logikprogrammierung: Definition, Prinzipien & Prolog-Beispiele

Grundprinzipien der Logikprogrammierung

Logikprogramme bestehen typischerweise aus zwei grundlegenden Elementen:

• Fakten: atomare Aussagen, die als wahr angenommen werden (z. B. mutter(anna, bob).).
• Regeln: Implikationen, die Beziehungen zwischen Fakten beschreiben (z. B. großmutter(X, Z) :- mutter(X, Y), mutter(Y, Z).).

Die Ausführung eines Logikprogramms erfolgt durch das Stellen von Fragen (Anfragen/Queries) an die Wissensbasis. Das System versucht dann, die Anfrage aus Fakten und Regeln abzuleiten. Wichtige Konzepte dabei sind:

• Unifikation: Mustervergleich, der Variablen so bindet, dass zwei Terme gleich werden.
• Resolution / SLD-Resolution: Ein formales Ableitungsverfahren, das Prolog-Engines zur Suche nach Beweisen nutzen.
• Backtracking: Systematisches Zurückgehen bei Fehlschlägen, um alternative Beweispfade zu versuchen.

Operationelles Verhalten: Unifikation und Backtracking

Wenn eine Anfrage gestellt wird, versucht die Prolog-Engine passende Regeln oder Fakten zu finden. Dabei werden Variablen durch Unifikation gebunden. Gelingt eine Bindung, wird die Suche fortgesetzt; führt ein Pfad zu keinem Beweis, geht das System zurück (Backtracking) und versucht die nächsten Alternativen. Dieses Verhalten macht Prolog effizient für Such- und Kombinationsprobleme, kann aber bei naiver Modellierung leicht zu exponentiellem Suchaufwand führen.

Negation als Fehlschlag und Semantik

Die oben erwähnte Negation als Fehlschlag (engl. negation as failure) beruht auf der Closed-World-Annäherung: Alles, was nicht bewiesen werden kann, gilt als falsch. Das ist pragmatisch nützlich, führt aber zu Unterschieden zur klassischen Logik:

• Sie ist nicht monotone: Das Hinzufügen neuer Fakten kann zuvor gültige Schlüsse ungültig machen.
• Sie entspricht nicht immer der Aussagenlogik mit expliziter Negation; es gibt Erweiterungen (z. B. explizite Negation, stratified negation, Well-Founded Semantics, Answer Set Programming), die komplexere Formen der Negation behandeln.

Einfaches Prolog-Beispiel

Beispiel-Fakten und -Regeln:

elternteil(anna, bob). elternteil(bob, carl).  vorfahre(X, Y) :- elternteil(X, Y). vorfahre(X, Y) :- elternteil(X, Z), vorfahre(Z, Y). 

Beispielanfragen (Queries):

?- vorfahre(anna, carl). % Antwort: true  ?- vorfahre(anna, Who). % Antwort: Who = bob ; Who = carl ; (je nach Backtracking) 

Negation als Fehlschlag in Prolog (häufig mit \+ oder not geschrieben):

läuft_nicht(X) :- \+ läuft(X). 

Wichtig: \+ läuft(X) liefert true genau dann, wenn das System nicht beweisen kann, dass läuft(X) wahr ist.

Anwendungen und Erweiterungen

• Wissensbasierte Systeme und Expertensysteme
• Natürlichsprachliche Verarbeitung (Parsing, semantische Analyse)
• Planung, Scheduling, Constraint-Satisfaction (Constraint-Logic-Programming)
• Formale Verifikation und automatisches Theorembeweisen
• Antwortmengenerzeugung in Datenbanken und semantischen Webanwendungen

Vor- und Nachteile

• Vorteile: deklarativer Stil (Was soll erreicht werden, nicht wie), klare Formulierung von Wissen, mächtig für symbolische Probleme.
• Nachteile: Performance-Probleme bei großen Suchräumen, subtile Semantik bei Negation, manchmal schwierigerer Übergang zu imperativen Aufgaben wie Ein-/Ausgabe oder Zustandshandhabung.

Weiterführende Hinweise

Wichtige Implementierungen und Erweiterungen (ohne Anspruch auf Vollständigkeit) sind z. B. SWI-Prolog, GNU Prolog, sowie Erweiterungen wie Constraint Logic Programming (CLP) und Answer Set Programming (ASP). Beim Entwurf von Logikprogrammen ist es hilfreich, sowohl die deklarative Bedeutung als auch das operationelle Verhalten (Suchstrategie, Reihenfolge von Regeln, Gebrauch von Cut-Operatoren in Prolog) zu berücksichtigen, um korrekte und effiziente Programme zu erhalten.