Die Logikprogrammierung verwendet mathematische Logik, um Computerprogramme zu schreiben. Es gibt spezialisierte Programmiersprachen, in denen der Benutzer logische Aussagen direkt eingeben kann. Die wohl bekannteste dieser Sprachen heißt Prolog. Alonzo Church verwendete eine Form der Logikprogrammierung in dem, was heute als Lambda-Kalkül bekannt ist. Logikprogrammierung wurde auch in LISP verwendet.
Programme bestehen aus einer Reihe von Regeln und Fakten. In den meisten Fällen verwendet die Logikprogrammierung die so genannte Negation als Fehlschlag oder schwache Negation: Das bedeutet, dass, wenn es nicht möglich ist, aus den Fakten und Regeln einen Satz p {\darstellungsstil p}
abzuleiten, das System annimmt, dass seine Negation wahr ist.
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.