Logikprogrammierung ist ein Programmier- , Datenbank- und Wissensrepräsentationsparadigma , das auf formaler Logik basiert . Ein Logikprogramm ist eine Menge von Sätzen in logischer Form, die Wissen über einen bestimmten Problembereich repräsentieren. Die Berechnung erfolgt durch Anwendung logischer Schlussfolgerungen auf dieses Wissen, um Probleme innerhalb des Bereichs zu lösen. Zu den wichtigsten Familien von Logikprogrammiersprachen gehören Prolog , Answer Set Programming (ASP) und Datalog . In all diesen Sprachen werden Regeln in Form von Klauseln geschrieben .

A :- B1, ..., Bn.

und werden als Aussagesätze in logischer Form gelesen:

A if B1 and ... and Bn.

Awird als Kopf der Regel bezeichnet, , ..., wird als Rumpf bezeichnet , und die werden als Literale oder Bedingungen bezeichnet . Wenn n = 0, wird die Regel als Fakt bezeichnet und in der vereinfachten Form geschrieben: B1BnBi

A.

Abfragen (oder Ziele) haben die gleiche Syntax wie die Regelkörper und werden üblicherweise in folgender Form geschrieben:

?- B1, ..., Bn.

Im einfachsten Fall von Horn-Klauseln (oder „definiten“ Klauseln) sind alle A, B₁ , ..., Bₙ atomare Formeln der Form p(t₁ , ..., tₘ ) , wobei p ein Prädikatsymbol ist, das eine Relation wie „Mutterschaft“ bezeichnet, und die tᵢ Terme sind, die Objekte (oder Individuen) benennen. Terme umfassen sowohl Konstanten wie „Charles“ als auch Variablen wie X, die mit einem Großbuchstaben beginnen.

Betrachten wir beispielsweise das folgende Horn-Klausel-Programm: 

Mutterkind ( Elizabeth , Charles ). Vaterkind ( Charles , William ). Vaterkind ( Charles , Harry ). Elternteilkind ( X , Y ) :- Mutterkind ( X , Y ). Elternteilkind ( X , Y ) :- Vaterkind ( X , Y ). Großelternkind ( X , Y ) :- Elternteilkind ( X , Z ), Elternteilkind ( Z , Y ).

Das Programm liefert zu einer gegebenen Anfrage Antworten. Beispielsweise ?- parent_child(X, william)ist die einzige Antwort auf die Anfrage: 

X = Charles

Es können verschiedene Anfragen gestellt werden. Beispielsweise kann das Programm sowohl nach Großeltern als auch nach Enkelkindern gefragt werden. Es kann sogar verwendet werden, um alle Paare von Enkelkindern und Großeltern zu generieren oder einfach zu überprüfen, ob ein gegebenes Paar ein solches Paar ist: 

grandparent_child ( X , william ). X = elizabeth?- grandparent_child ( elizabeth , Y ). Y = william ; Y = harry .?- grandparent_child ( X , Y ). X = elizabeth Y = william ; X = elizabeth Y = harry .?- grandparent_child ( william , harry ). no ?- grandparent_child ( elizabeth , harry ). yes

Obwohl Horn-Klausel-Logikprogramme Turing-vollständig sind [ 1 ] [ 2 ] , müssen sie für die meisten praktischen Anwendungen zu „normalen“ Logikprogrammen mit negativen Bedingungen erweitert werden. Beispielsweise verwendet die Definition von Geschwistern eine negative Bedingung, wobei das Prädikat = durch die Klausel definiert ist X = X : 

sibling ( X , Y ) :- parent_child ( Z , X ), parent_child ( Z , Y ), not ( X = Y ).

Logische Programmiersprachen, die negative Bedingungen beinhalten, verfügen über die Wissensrepräsentationsfähigkeiten einer nicht-monotonen Logik .

In ASP und Datalog haben Logikprogramme ausschließlich eine deklarative Lesart, und ihre Ausführung erfolgt mittels einer Beweisprozedur oder eines Modellgenerators, dessen Verhalten nicht vom Programmierer gesteuert werden soll. In der Prolog-Sprachfamilie hingegen besitzen Logikprogramme auch eine prozedurale Interpretation als Zielreduktionsverfahren. Aus dieser Sichtweise wird die Klausel A :- B 1 ,...,B n wie folgt verstanden:

zu lösen A, zu lösen , und ... und zu lösen .B1Bn

Negative Bedingungen im Hauptteil von Klauseln haben auch eine verfahrensrechtliche Auslegung, die als Negation als Fehlschlag bekannt ist : Eine negative Bedingung not Bgilt genau dann, wenn die positive Bedingung Bnicht gilt.

Ein Großteil der Forschung im Bereich der logischen Programmierung befasste sich mit der Entwicklung einer logischen Semantik für Negation als Fehlschlag sowie mit der Entwicklung anderer Semantiken und Implementierungen für Negation. Diese Entwicklungen waren wiederum wichtig für die Entwicklung formaler Methoden zur logikbasierten Programmverifikation und Programmtransformation .

Geschichte

Die Verwendung mathematischer Logik zur Darstellung und Ausführung von Computerprogrammen ist auch ein Merkmal des Lambda-Kalküls , der in den 1930er Jahren von Alonzo Church entwickelt wurde. Der erste Vorschlag, die Klausellogik zur Darstellung von Computerprogrammen zu nutzen, stammt jedoch von Cordell Green [ 3 ] . Dieser verwendete eine Axiomatisierung einer Teilmenge von LISP zusammen mit einer Darstellung einer Eingabe-Ausgabe-Relation, um die Relation durch Simulation der Programmausführung in LISP zu berechnen. Foster und Elcocks Absys hingegen nutzte eine Kombination aus Gleichungen und Lambda-Kalkül in einer assertionsbasierten Programmiersprache, die keine Einschränkungen hinsichtlich der Reihenfolge der Operationen vorgibt [ 4 ] .

Die Logikprogrammierung mit ihrer heutigen Syntax aus Fakten und Regeln lässt sich auf Debatten der späten 1960er und frühen 1970er Jahre über deklarative versus prozedurale Wissensrepräsentationen in der künstlichen Intelligenz zurückführen . Befürworter deklarativer Repräsentationen arbeiteten insbesondere in Stanford , unter anderem mit John McCarthy , Bertram Raphael und Cordell Green, sowie in Edinburgh mit John Alan Robinson (einem Gastwissenschaftler der Syracuse University ), Pat Hayes und Robert Kowalski . Die Befürworter prozeduraler Repräsentationen konzentrierten sich hauptsächlich am MIT unter der Leitung von Marvin Minsky und Seymour Papert . [ 5 ]

Obwohl Planner , entwickelt von Carl Hewitt am MIT, auf den Beweismethoden der Logik basierte, war es die erste Sprache, die innerhalb dieses prozeduralen Paradigmas entstand. [ 6 ] Planner zeichnete sich durch mustergesteuerte Aufrufe prozeduraler Pläne aus, die von Zielen (Zielreduktion oder Rückwärtsverkettung ) und von Aussagen ( Vorwärtsverkettung ) ausgingen. Die einflussreichste Implementierung von Planner war die Teilmenge Micro-Planner, die von Gerry Sussman , Eugene Charniak und Terry Winograd entwickelt wurde. Winograd nutzte Micro-Planner zur Implementierung des wegweisenden Programms SHRDLU zur Verarbeitung natürlicher Sprache . [ 7 ] Aus Effizienzgründen verwendete Planner eine Backtracking-Kontrollstruktur, sodass jeweils nur ein möglicher Berechnungspfad gespeichert werden musste. Planner war die Grundlage für die Programmiersprachen QA4 [ 8 ] , Popler [ 9 ] , Conniver [ 10 ] , QLISP [ 11 ] und die nebenläufige Sprache Ether [ 12 ] .

Hayes und Kowalski versuchten in Edinburgh, den logikbasierten deklarativen Ansatz der Wissensrepräsentation mit dem prozeduralen Ansatz von Planner zu vereinbaren. Hayes (1973) entwickelte eine Gleichungssprache namens Golux, in der durch Änderung des Verhaltens des Theorembeweisers verschiedene Prozeduren erzeugt werden konnten. [ 13 ]

Währenddessen arbeitete Alain Colmerauer in Marseille an der Verarbeitung natürlicher Sprache . Er nutzte Logik zur Repräsentation von Semantik und Resolution zur Beantwortung von Fragen. Im Sommer 1971 lud Colmerauer Kowalski nach Marseille ein, und gemeinsam entdeckten sie, dass sich die Klausellogik zur Repräsentation formaler Grammatiken eignete und dass Resolutionsbeweiser zum Parsen verwendet werden konnten. Sie beobachteten, dass sich einige Beweiser, wie Hyper-Resolution [ 14 ] , als Bottom-up-Parser und andere, wie SL Resolution (1971) [ 15 ] , als Top-down-Parser verhalten.

Im darauffolgenden Sommer 1972 entwickelte Kowalski, erneut in Zusammenarbeit mit Colmerauer, die verfahrenstheoretische Interpretation von Implikationen in Satzform. Es wurde auch deutlich, dass solche Sätze auf bestimmte Sätze oder Horn-Sätze beschränkt werden konnten und dass die SL-Resolution auf die SLD-Resolution beschränkt (und verallgemeinert) werden konnte . Kowalskis verfahrenstheoretische Interpretation und die SLD wurden in einem 1973 verfassten und 1974 veröffentlichten Memo beschrieben. [ 16 ]

Colmerauer und Philippe Roussel nutzten die prozedurale Interpretation als Grundlage für Prolog, das im Sommer und Herbst 1972 implementiert wurde. Das erste Prolog-Programm, ebenfalls 1972 geschrieben und in Marseille implementiert, war ein französisches Frage-Antwort-System. Die Entwicklung eines Compilers durch David H. D. Warren in Edinburgh im Jahr 1977 gab der Verwendung von Prolog als praktische Programmiersprache einen entscheidenden Schub. Experimente zeigten, dass Edinburgh Prolog hinsichtlich der Verarbeitungsgeschwindigkeit mit anderen symbolischen Programmiersprachen wie Lisp konkurrieren konnte . [ 17 ] Edinburgh Prolog wurde zum De-facto- Standard und beeinflusste die Definition des ISO -Standards Prolog maßgeblich.

Die logische Programmierung erlangte in den 1980er Jahren internationale Aufmerksamkeit, als sie vom japanischen Ministerium für Internationalen Handel und Industrie für die Softwareentwicklung des Projekts „Computersysteme der fünften Generation “ (FGCS) ausgewählt wurde. Ziel des FGCS-Projekts war die Entwicklung fortschrittlicher Anwendungen künstlicher Intelligenz auf massiv parallelen Rechnern mithilfe logischer Programmierung . Obwohl anfänglich die Verwendung von Prolog untersucht wurde, entschied man sich später für die nebenläufige logische Programmierung , da diese besser zur FGCS-Rechnerarchitektur passte.

Die festgeschriebene Auswahlmöglichkeit der nebenläufigen logischen Programmierung beeinträchtigte jedoch die logische Semantik der Sprache [ 18 ] und ihre Eignung für Wissensrepräsentation und Problemlösungsanwendungen. Darüber hinaus konnten die im Projekt entwickelten Parallelrechnersysteme mit den Fortschritten bei der Entwicklung konventionellerer Allzweckrechner nicht mithalten. Diese beiden Probleme führten dazu, dass das FGCS-Projekt seine Ziele verfehlte. Das Interesse an logischer Programmierung und KI ging weltweit zurück. [ 19 ]

In der Zwischenzeit wurden deklarativere Ansätze der Logikprogrammierung, darunter solche auf Basis von Prolog, unabhängig vom FGCS-Projekt weiterentwickelt. Obwohl Prolog ursprünglich zur Kombination deklarativer und prozeduraler Wissensrepräsentationen entwickelt worden war, rückte die rein deklarative Interpretation von Logikprogrammen in den Mittelpunkt von Anwendungen im Bereich deduktiver Datenbanken . Die Arbeiten auf diesem Gebiet erlangten um 1977 Bedeutung, als Hervé Gallaire und Jack Minker in Toulouse einen Workshop zu Logik und Datenbanken organisierten. [ 20 ] Das Forschungsgebiet wurde schließlich in Datalog umbenannt .

Dieser Fokus auf das logische, deklarative Lesen von Logikprogrammen wurde durch die Entwicklung der Constraint-Logikprogrammierung in den 1980er Jahren und der Answer Set Programming in den 1990er Jahren weiter verstärkt. Er erfährt auch in neueren Anwendungen von Prolog [ 21 ] eine erneute Betonung.

Die Association for Logic Programming (ALP) wurde 1986 zur Förderung der logischen Programmierung gegründet. Ihre offizielle Zeitschrift war bis 2000 das „Journal of Logic Programming“ . Gründungsherausgeber war J. Alan Robinson . [ 22 ] Im Jahr 2001 wurde die Zeitschrift in „Journal of Logic and Algebraic Programming“ umbenannt , und die offizielle Zeitschrift der ALP wurde zu „Theory and Practice of Logic Programming“ , herausgegeben von Cambridge University Press .

Konzepte

Logikprogramme zeichnen sich durch eine große Vielfalt an Semantiken und Problemlösungsmethoden sowie durch ein breites Anwendungsspektrum in den Bereichen Programmierung, Datenbanken, Wissensrepräsentation und Problemlösung aus.

Algorithmus = Logik + Steuerung

Die prozedurale Interpretation logischer Programme, die mithilfe von Rückwärtsschlüssen Ziele auf Teilziele reduziert, ist ein Spezialfall der Anwendung einer Problemlösungsstrategie zur Steuerung der Verwendung einer deklarativen, logischen Wissensrepräsentation, um das Verhalten eines Algorithmus zu ermitteln . Allgemeiner lässt sich sagen, dass unterschiedliche Problemlösungsstrategien auf dieselbe logische Repräsentation angewendet werden können, um verschiedene Algorithmen zu erhalten. Alternativ können mit einer gegebenen Problemlösungsstrategie durch die Verwendung unterschiedlicher logischer Repräsentationen verschiedene Algorithmen erzielt werden. [ 23 ]

Die beiden wichtigsten Problemlösungsstrategien sind das Rückwärtsdenken (Zielreduktion) und das Vorwärtsdenken , auch bekannt als Top-Down- bzw. Bottom-Up-Denken.

Im einfachen Fall eines propositionalen Horn-Klauselprogramms und eines atomaren Ziels auf oberster Ebene bestimmt das Rückwärtslogik einen UND-ODER-Baum , der den Suchraum zur Lösung des Ziels darstellt. Das Ziel auf oberster Ebene ist die Wurzel des Baums. Für jeden Knoten im Baum und jede Klausel, deren Kopf mit dem Knoten übereinstimmt, existiert eine Menge von Kindknoten, die den Teilzielen im Rumpf der Klausel entsprechen. Diese Kindknoten sind durch ein „UND“ gruppiert. Die alternativen Mengen von Kindknoten, die alternativen Lösungswegen des Knotens entsprechen, sind durch ein „ODER“ gruppiert.

Für die Suche in diesem Raum kann jede beliebige Suchstrategie verwendet werden. Prolog verwendet eine sequentielle, LIFO-basierte Backtracking-Strategie, bei der jeweils nur eine Alternative und ein Teilziel betrachtet werden. So können beispielsweise Teilziele parallel gelöst und Klauseln parallel ausprobiert werden. Die erste Strategie heißtund parallel , und die zweite Strategie heißtoder parallel . Andere Suchstrategien, wie intelligentes Backtracking [ 24 ] oder die Best-First-Suche zur Ermittlung einer optimalen Lösung [ 25 ] , sind ebenfalls möglich.

Im allgemeineren, nicht-propositionalen Fall, in dem Teilziele Variablen gemeinsam nutzen können, lassen sich andere Strategien anwenden, beispielsweise die Wahl des am häufigsten instanziierten Teilziels oder desjenigen, das ausreichend instanziiert ist, sodass nur eine Prozedur anwendbar ist. [ 26 ] Solche Strategien werden beispielsweise in der nebenläufigen logischen Programmierung eingesetzt .

In den meisten Fällen ist das Rückwärtsdenken ausgehend von einer Anfrage oder einem Ziel effizienter als das Vorwärtsdenken. Bei Datalog und Answer Set Programming kann es jedoch vorkommen, dass keine Anfrage vom gesamten Satz der Klauseln getrennt ist. In solchen Fällen ist es sinnvoll, alle aus den Klauseln ableitbaren Fakten zu generieren. Hier ist ein weiteres Beispiel, bei dem das Vorwärtsdenken dem Rückwärtsdenken in einer eher konventionellen Rechenaufgabe überlegen ist: die Bestimmung ?- fibonacci(n, Result)der n -ten Fibonacci-Zahl. 

Fibonacci ( 0 , 0 ). Fibonacci ( 1 , 1 ).fibonacci ( N , Result ) :- N > 1 , N1 is N - 1 , N2 is N - 2 , fibonacci ( N1 , F1 ), fibonacci ( N2 , F2 ), Result is F1 + F2 .

Hierbei steht die Relation fibonacci(N, M)für die Funktion fibonacci(N) = M, und das Prädikat N is Expressionist die Prolog-Notation für das Prädikat, das die Variable Nauf den Wert von instanziiert Expression.

Das Ziel, die Fibonacci-Zahl von n zu berechnen n, lässt sich durch Rückwärtsrechnen auf die beiden Teilziele der Berechnung der Fibonacci-Zahlen von n-1 und n-2 reduzieren. Das Teilziel der Berechnung der Fibonacci-Zahl von n-1 wird wiederum in die beiden Teilziele der Berechnung der Fibonacci-Zahlen von n-2 und n-3 unterteilt, wobei die Fibonacci-Zahl von n-2 redundant berechnet wird. Dieser Prozess der Reduzierung eines Fibonacci-Teilziels auf zwei Fibonacci-Teilziele wird fortgesetzt, bis die Zahlen 0 und 1 erreicht sind. Seine Komplexität liegt in der Größenordnung von 2<sup> n</sup> . Im Gegensatz dazu generiert das Vorwärtsrechnen die Folge der Fibonacci-Zahlen, beginnend mit 0 und 1, ohne jegliche Neuberechnung, und seine Komplexität ist linear in Bezug auf n.

Prolog kann kein direktes Vorwärtsverstehen durchführen. Es kann jedoch den Effekt des Vorwärtsverstehens im Kontext des Rückwärtsverstehens durch Tabellenbildung erreichen : Teilziele werden zusammen mit ihren Lösungen in einer Tabelle verwaltet. Tritt ein Teilziel erneut auf, wird es direkt mithilfe der bereits in der Tabelle vorhandenen Lösungen gelöst, anstatt die Teilziele redundant erneut zu lösen. [ 27 ]

Beziehung zur funktionalen Programmierung

Logische Programmierung kann als Verallgemeinerung der funktionalen Programmierung betrachtet werden, in der Funktionen ein Spezialfall von Relationen sind. [ 28 ] Beispielsweise kann die Funktion `mother(X) = Y` (jedes X hat genau eine Mutter Y) durch die Relation `mother(X, Y)` dargestellt werden. Insofern ähneln logische Programme relationalen Datenbanken , die Funktionen ebenfalls als Relationen repräsentieren.

Im Vergleich zur relationalen Syntax ist die funktionale Syntax für verschachtelte Funktionen kompakter. Beispielsweise kann die Definition von „mütterlicherseits Großmutter“ in funktionaler Syntax in verschachtelter Form geschrieben werden: 

maternal_grandmother ( X ) = mother ( mother ( X )).

Dieselbe Definition in relationaler Notation muss in der unverschachtelten, flachen Form geschrieben werden: 

maternal_grandmother ( X , Y ) :- mother ( X , Z ), mother ( Z , Y ).

Verschachtelte Syntax kann jedoch als syntaktischer Zucker für nicht verschachtelte Syntax betrachtet werden. Ciao Prolog beispielsweise transformiert funktionale Syntax in relationale Form und führt das resultierende Logikprogramm mit der Standard-Prolog-Ausführungsstrategie aus. [ 29 ] Darüber hinaus kann dieselbe Transformation verwendet werden, um verschachtelte Relationen auszuführen, die nicht funktional sind. Zum Beispiel: 

Großelternteil ( X ) := Elternteil ( Elternteil ( X )). Elternteil ( X ) := Mutter ( X ). Elternteil ( X ) := Vater ( X ).Mutter ( Charles ) := Elizabeth . Vater ( Charles ) := Phillip . Mutter ( Harry ) := Diana . Vater ( Harry ) := Charles .?- Großelternteil ( X , Y ). X = Harry , Y = Elizabeth . X = Harry , Y = Phillip .

Beziehung zur relationalen Programmierung

Der Begriff relationale Programmierung wird für verschiedene Programmiersprachen verwendet, die Funktionen als Spezialfall von Relationen behandeln. Einige dieser Sprachen, wie beispielsweise miniKanren [ 28 ] und relationale lineare Programmierung [ 30 ], sind im Sinne dieses Artikels logische Programmiersprachen.

Allerdings ist die relationale Sprache RML eine imperative Programmiersprache [ 31 ] , deren Kernkonstrukt ein relationaler Ausdruck ist, der einem Ausdruck in der Prädikatenlogik erster Stufe ähnelt.

Andere relationale Programmiersprachen basieren auf dem relationalen Kalkül [ 32 ] oder der relationalen Algebra. [ 33 ]

Semantik von Horn-Klausel-Programmen

Rein logisch betrachtet gibt es zwei Ansätze zur deklarativen Semantik von Horn-Klausel-Logikprogrammen: Der eine Ansatz ist die ursprüngliche logische Folgerungssemantik , die das Lösen eines Ziels als Beweis dafür versteht, dass das Ziel ein Theorem ist, das in allen Modellen des Programms wahr ist .

In diesem Ansatz ist die Berechnung ein Theorembeweis in der Prädikatenlogik erster Stufe ; sowohl Rückwärtsschlüsse , wie bei der SLD-Resolution, als auch Vorwärtsschlüsse , wie bei der Hyperresolution, sind korrekte und vollständige Theorembeweismethoden. Manchmal werden solche Theorembeweismethoden auch als separate beweistheoretische (oder operationelle) Semantik für Logikprogramme betrachtet. Logisch betrachtet sind sie jedoch Beweismethoden und keine Semantik.

Der andere Ansatz zur deklarativen Semantik von Horn-Klausel-Programmen ist die Erfüllbarkeitssemantik . Diese versteht die Erfüllung eines Ziels als den Nachweis, dass das Ziel in einem bestimmten (oder Standard-)Modell des Programms wahr (oder erfüllt) ist. Für Horn-Klausel-Programme existiert stets ein solches Standardmodell: Es ist das eindeutige Minimalmodell des Programms.

Informell ausgedrückt ist ein Minimalmodell ein Modell, das, wenn es als die Menge aller (variablenfreien) Fakten betrachtet wird, die im Modell wahr sind, keine kleinere Menge von Fakten enthält, die ebenfalls ein Modell des Programms ist.

Die folgenden Fakten stellen beispielsweise das Minimalmodell des Beispiels familiärer Beziehungen aus der Einleitung dieses Artikels dar. Alle anderen variablenfreien Fakten sind in diesem Modell falsch: 

Mutterkind ( Elizabeth , Charles ). Vaterkind ( Charles , William ). Vaterkind ( Charles , Harry ). Elternteilkind ( Elizabeth , Charles ). Elternteilkind ( Charles , William ). Elternteilkind ( Charles , Harry ). Großelternkind ( Elizabeth , William ). Großelternkind ( Elizabeth , Harry ).

Die Erfüllbarkeitssemantik besitzt auch eine alternative, eher mathematische Charakterisierung als den kleinsten Fixpunkt der Funktion, die die Regeln im Programm verwendet, um in einem einzigen Inferenzschritt neue Fakten aus bestehenden Fakten abzuleiten.

Bemerkenswerterweise sind dieselben Problemlösungsmethoden des Vorwärts- und Rückwärtsschlusses, die ursprünglich für die logische Folgerungssemantik entwickelt wurden, gleichermaßen auf die Erfüllbarkeitssemantik anwendbar: Der Vorwärtsschluss erzeugt das Minimalmodell eines Horn-Klausel-Programms, indem er neue Fakten aus bestehenden Fakten ableitet, bis keine weiteren Fakten mehr generiert werden können. Der Rückwärtsschluss, der ein Ziel in Teilziele zerlegt, bis alle Teilziele durch Fakten gelöst sind, stellt sicher, dass das Ziel im Minimalmodell wahr ist, ohne das Modell explizit zu erzeugen. [ 34 ]

Der Unterschied zwischen den beiden deklarativen Semantiken wird deutlich an den Definitionen von Addition und Multiplikation in der Nachfolgerarithmetik , die die natürlichen Zahlen 0, 1, 2, ...als Folge von Gliedern der Form darstellt 0, s(0), s(s(0)), .... Im Allgemeinen repräsentiert das Glied s(X)den Nachfolger von , X,nämlich . X + 1.Hier sind die Standarddefinitionen von Addition und Multiplikation in funktionaler Notation: 

 X + 0 = X. X + s(Y) = s(X + Y). d. h. X + (Y + 1) = (X + Y) + 1 X × 0 = 0. X × s(Y) = X + (X × Y). also X × (Y + 1) = X + (X × Y).

Hier sind die gleichen Definitionen wie in einem Logikprogramm, wobei add(X, Y, Z)und X + Y = Z,dargestellt multiply(X, Y, Z)werden X × Y = Z: 

add ( X , 0 , X ). add ( X , s ( Y ), s ( Z )) :- add ( X , Y , Z ).multiplizieren ( X , 0 , 0 ). multiplizieren ( X , s ( Y ), W ) :- multiplizieren ( X , Y , Z ), addieren ( X , Z , W ).

Beide deklarativen Semantiken liefern für dieselben existentiell quantifizierten Konjunktionen von Additions- und Multiplikationszielen die gleichen Ergebnisse. Beispielsweise 2 × 2 = Xhat die Lösung X = 4; und X × X = X + Xhat zwei Lösungen X = 0und X = 2: 

?- multiplizieren ( s ( s ( 0 )), s ( s ( 0 )), X ). X = s ( s ( s ( s ( 0 )))).Multipliziere ( X , X , Y ), addiere ( X , X , Y ). X = 0 , Y = 0. X = s ( s ( 0 )), Y = s ( s ( s ( s ( 0 ) ))).

Bei der Semantik der logischen Konsequenzen existieren jedoch nicht-standardmäßige Modelle des Programms, in denen beispielsweise add(s(s(0)), s(s(0)), s(s(s(s(s(0)))))),„ie“ 2 + 2 = 5wahr ist. Bei der Erfüllbarkeitssemantik hingegen existiert nur ein Modell, nämlich das Standardmodell der Arithmetik, in dem „ie“ 2 + 2 = 5falsch ist.

In beiden Semantiken wird das Ziel nicht erreicht. In der Erfüllbarkeitssemantik bedeutet das Nichterreichen des Ziels, dass dessen Wahrheitswert falsch ist. In der Semantik der logischen Folgerung hingegen bedeutet das Nichterreichen, dass der Wahrheitswert des Ziels unbekannt ist. ?-add(s(s(0)),s(s(0)),s(s(s(s(s(0))))))

Negation als Fehlschlag

Die Negation als Fehlschlag (NAF), mit der man die Gültigkeit einer negativen Bedingung beweisen kann, not pindem man zeigt, dass die positive Bedingung pnicht gilt, war bereits ein Merkmal früher Prolog-Systeme. Die daraus resultierende Erweiterung der SLD-Resolution wird SLDNF genannt . Ein ähnliches Konstrukt, „thnot“ genannt, existierte auch in Micro-Planner .

Die logische Semantik von NAF war bis dahin ungeklärt, bis Keith Clark [ 35 ] zeigte, dass NAF unter bestimmten natürlichen Bedingungen eine effiziente, korrekte (und manchmal vollständige) Methode ist, mit der Semantik logischer Konsequenzen zu argumentieren, indem man ein Logikprogramm in Prädikatenlogik erster Stufe vervollständigt .

Die Vervollständigung entspricht in etwa der Betrachtung der Menge aller Programmklauseln mit demselben Prädikat im Kopf, beispielsweise:

A :- Body1.
...
A :- Bodyk.

als Definition des Prädikats:

A iff (Body1 or ... or Bodyk)

wobei iff„genau dann, wenn“ bedeutet. Die Vervollständigung umfasst auch Gleichheitsaxiome, die der Unifikation entsprechen . Clark zeigte, dass die durch SLDNF generierten Beweise strukturell ähnlich sind wie die durch natürliches Deduktionsdenken mit der Vervollständigung des Programms generierten Beweise.

Betrachten wir beispielsweise folgendes Programm: 

should_receive_sanction ( X , punishment ) :- is_a_thief ( X ), not should_receive_sanction ( X , rehabilitation ).sollte_Sanktion_erhalten ( X , Rehabilitation ) :- ist_ein_Dieb ( X ), ist_ein_Minderjähriger ( X ), ist nicht_gewalttätig ( X ).is_a_thief ( tom ).

Angesichts des Ziels, festzustellen, ob Tom eine Sanktion erhalten sollte, zeigt die erste Regel, dass Tom bestraft werden sollte: 

?- sollte_eine_Sanktion_erhalten ( tom , Sanktion ). Sanktion = Strafe .

Dies liegt daran, dass Tom ein Dieb ist und nicht nachgewiesen werden kann, dass Tom resozialisiert werden sollte. Es kann nicht nachgewiesen werden, dass Tom resozialisiert werden sollte, weil nicht nachgewiesen werden kann, dass Tom minderjährig ist.

Sollten wir jedoch neue Informationen erhalten, dass Tom tatsächlich minderjährig ist, wird die bisherige Schlussfolgerung, dass Tom bestraft werden sollte, durch die neue Schlussfolgerung ersetzt, dass Tom rehabilitiert werden sollte: 

is_a_minor ( tom ).?- sollte_eine_Sanktion_erhalten ( tom , Sanktion ). Sanktion = Rehabilitation .

Diese Eigenschaft, eine Schlussfolgerung zurückzuziehen, wenn neue Informationen hinzugefügt werden, wird als Nicht-Monotonie bezeichnet und macht die logische Programmierung zu einer nicht-monotonen Logik .

Wenn uns aber nun mitgeteilt wird, dass Tom gewalttätig ist, wird die Schlussfolgerung, dass Tom bestraft werden sollte, wiederhergestellt: 

is_violent ( tom ).?- sollte_eine_Sanktion_erhalten ( tom , Sanktion ). Sanktion = Strafe .

Der Abschluss dieses Programms ist: 

should_receive_sanction ( X , Sanction ) ff. Sanction = punishment , is_a_thief ( X ), not should_receive_sanction ( X , rehabilitation ) or Sanction = rehabilitation , is_a_thief ( X ), is_a_minor ( X ), not is_violent ( X ).is_a_thief ( X ) genau dann, wenn X = tom . is_a_minor ( X ) genau dann, wenn X = tom . is_violent ( X ) genau dann, wenn X = tom .

The notion of completion is closely related to John McCarthy'scircumscription semantics for default reasoning,[36] and to Ray Reiter'sclosed world assumption.[37]

The completion semantics for negation is a logical consequence semantics, for which SLDNF provides a proof-theoretic implementation. However, in the 1980s, the satisfiability semantics became more popular for logic programs with negation. In the satisfiability semantics, negation is interpreted according to the classical definition of truth in an intended or standard model of the logic program.

In the case of logic programs with negative conditions, there are two main variants of the satisfiability semantics: In the well-founded semantics, the intended model of a logic program is a unique, three-valued, minimal model, which always exists. The well-founded semantics generalises the notion of inductive definition in mathematical logic.[38]XSB Prolog[39] implements the well-founded semantics using SLG resolution.[40]

In the alternative stable model semantics, there may be no intended models or several intended models, all of which are minimal and two-valued. The stable model semantics underpins answer set programming (ASP).

Both the well-founded and stable model semantics apply to arbitrary logic programs with negation. However, both semantics coincide for stratified logic programs. For example, the program for sanctioning thieves is (locally) stratified, and all three semantics for the program determine the same intended model: 

should_receive_sanction(tom,punishment).is_a_thief(tom).is_a_minor(tom).is_violent(tom).

Attempts to understand negation in logic programming have also contributed to the development of abstract argumentation frameworks.[41] In an argumentation interpretation of negation, the initial argument that tom should be punished because he is a thief, is attacked by the argument that he should be rehabilitated because he is a minor. But the fact that tom is violent undermines the argument that tom should be rehabilitated and reinstates the argument that tom should be punished.

Metalogic programming

Metaprogrammierung , bei der Programme als Daten behandelt werden, war bereits ein Merkmal früher Prolog-Implementierungen. [ 42 ] [ 43 ] Beispielsweise enthielt die Edinburgh DEC10-Implementierung von Prolog „einen Interpreter und einen Compiler, die beide in Prolog selbst geschrieben waren“. [ 43 ] Das einfachste Metaprogramm ist der sogenannte „ Vanilla “-Metainterpreter: 

solve ( true ) .solve (( B , C )):- solve ( B ), solve ( C ) .solve ( A ):- clause ( A , B ), solve ( B ).

Dabei steht „wahr“ für eine leere Konjunktion und (B,C) für einen zusammengesetzten Term, der die Konjunktion von B und C repräsentiert. Der Prädikatsatz (A,B) bedeutet, dass es einen Satz der Form A :- B gibt.

Metaprogrammierung ist eine Anwendung des allgemeineren Gebrauchs einer Metalogik oder Metasprache , um eine andere Sprache, die sogenannte Objektsprache , zu beschreiben und über sie zu argumentieren .

Metalogische Programmierung ermöglicht die Kombination von Objekt- und Metaebenenrepräsentationen, analog zur natürlichen Sprache. Im folgenden Programm attends(Person, Meeting)tritt beispielsweise die atomare Formel sowohl als Objektformel als auch als Argument der Metaprädikate auf prohibited.approved.

verboten ( nimmt teil ( Person , Meeting )) :- nicht ( genehmigt ( nimmt teil ( Person , Meeting ))).sollte_eine_Sanktion_erhalten ( Person , Schimpfen ) :- nimmt teil ( Person , Meeting ), hochgestellt ( Person ), verboten ( nimmt teil ( Person , Meeting )). sollte_eine_Sanktion_erhalten ( Person , Verbannung ) :- nimmt teil ( Person , Meeting ), niedriggestellt ( Person ), verboten ( nimmt teil ( Person , Meeting )).genehmigt ( nimmt teil ( Alice , Teeparty )). nimmt teil ( verrückter Hutmacher , Teeparty ). nimmt teil ( Siebenschläfer , Teeparty ).erhaben ( verrückter Hutmacher ). niedrig ( Siebenschläfer ).?- sollte_eine_Sanktion_erhalten ( X , Y ). Person = verrückter_Hutmacher , Sanktion = Schimpfen . Person = Siebenschläfer , Sanktion = Verbannung .

Beziehung zum computergestützten Repräsentationsverständnis des Geistes

In seiner populären Einführung in die Kognitionswissenschaft [ 44 ] stellt Paul Thagard Logik und Regeln als alternative Ansätze zur Modellierung menschlichen Denkens vor. Er argumentiert, dass Regeln der Form „WENN Bedingung, DANN Handlung“ logischen Konditionalsätzen „sehr ähnlich“ seien, aber einfacher und psychologisch plausibler (S. 51). Unter anderem unterscheidet sich Logik laut Thagard dadurch, dass sie auf Deduktion basiert, während Regeln auf Suche beruhen (S. 45) und sowohl für Vorwärts- als auch für Rückwärtsschlüsse verwendet werden können (S. 47). Logische Sätze „müssen als universell wahr interpretiert werden “, Regeln hingegen können als Standardwerte definiert werden und Ausnahmen zulassen (S. 44).

Er führt aus, dass „regelbasierte Systeme im Gegensatz zur Logik auch strategische Informationen darüber, was zu tun ist, leicht darstellen können“ (Seite 45). Zum Beispiel: „Wenn du übers Wochenende nach Hause fahren willst und Fahrgeld für den Bus hast, DANN kannst du den Bus nehmen.“ Er übersieht dabei, dass dieselbe Strategie, ein Ziel in Teilziele zu unterteilen, analog zur logischen Programmierung als Anwendung von Rückwärtsschlüssen auf eine logische Bedingung interpretiert werden kann. 

can_go ( you , home ) :- have ( you , bus_fare ), catch ( you , bus ).

Alle diese Merkmale regelbasierter Systeme – Suche, Vorwärts- und Rückwärtsschlussfolgern, Standardschlussfolgern und Zielreduktion – sind auch definierende Merkmale der logischen Programmierung. Dies legt nahe, dass Thagards Schlussfolgerung (Seite 56), dass:

Ein Großteil des menschlichen Wissens lässt sich naturgemäß durch Regeln beschreiben, und viele Denkweisen, wie zum Beispiel die Planung, können durch regelbasierte Systeme modelliert werden.

Gilt auch für die logische Programmierung.

Weitere Argumente, die zeigen, wie logische Programmierung zur Modellierung von Aspekten des menschlichen Denkens genutzt werden kann, werden von Keith Stenning und Michiel van Lambalgen in ihrem Buch „Human Reasoning and Cognitive Science“ [ 45 ] präsentiert. Sie zeigen, wie der nicht-monotone Charakter logischer Programme genutzt werden kann, um die menschliche Leistung bei einer Vielzahl psychologischer Aufgaben zu erklären. Außerdem zeigen sie (Seite 237), dass „das Denken in geschlossenen Welten in seiner Form als logische Programmierung eine attraktive neuronale Implementierung besitzt, im Gegensatz zur klassischen Logik.“

In „The Proper Treatment of Events“ [ 46 ] untersuchen Michiel van Lambalgen und Fritz Hamm die Verwendung von Constraint-Logik-Programmierung zur Kodierung „zeitlicher Begriffe in natürlicher Sprache, indem sie die Art und Weise betrachten, wie Menschen Zeit konstruieren“.

Wissensrepräsentation

Die Verwendung von Logik zur Darstellung prozeduralen Wissens und strategischer Informationen war eines der Hauptziele bei der frühen Entwicklung der logischen Programmierung. Auch heute noch ist sie ein wichtiges Merkmal der Prolog-Familie logischer Programmiersprachen. Viele Anwendungen der logischen Programmierung, darunter auch Prolog-Anwendungen, konzentrieren sich jedoch zunehmend auf die Verwendung von Logik zur Darstellung rein deklarativen Wissens. Diese Anwendungen umfassen sowohl die Darstellung von allgemeinem Alltagswissen als auch die Darstellung domänenspezifischer Expertise .

Der gesunde Menschenverstand umfasst Wissen über Ursache und Wirkung, wie es beispielsweise im Situationskalkül , Ereigniskalkül und in Aktionssprachen formalisiert ist . Hier ein vereinfachtes Beispiel, das die Hauptmerkmale solcher Formalismen veranschaulicht. Der erste Satzteil besagt, dass ein Sachverhalt unmittelbar nach dem Einleiten (oder Verursachen) dieses Sachverhalts gilt. Der zweite Satzteil ist ein Rahmenaxiom , das besagt, dass ein zu einem Zeitpunkt geltender Sachverhalt auch zum nächsten Zeitpunkt gilt, sofern er nicht durch ein Ereignis, das zu diesem Zeitpunkt eintritt, beendet wird. Diese Formulierung erlaubt das gleichzeitige Eintreten mehrerer Ereignisse. 

hält ( Fakt , Zeit2 ) :- passiert ( Ereignis , Zeit1 ), Zeit2 ist Zeit1 + 1 , initiiert ( Ereignis , Fakt ).hält ( Fakt , Zeit2 ) :- passiert ( Ereignis , Zeit1 ), Zeit2 ist Zeit1 + 1 , hält ( Fakt , Zeit1 ), nicht ( beendet ( Fakt , Zeit1 )).terminated ( Fact , Time ) :- happens ( Event , Time ), terminates ( Event , Fact ).

Hier holdsist ein Metaprädikat, ähnlich dem solveobigen. Während jedoch solvenur ein Argument besitzt, das auf allgemeine Klauseln anwendbar ist, holdsist das erste Argument von eine Tatsache und das zweite Argument ein Zeitpunkt (oder Zustand). Die atomare Formel holds(Fact, Time)drückt aus, dass die FactTatsache zum Zeitpunkt gilt Time. Solche zeitlich veränderlichen Tatsachen werden auch als Fluente bezeichnet . Die atomare Formel happens(Event, Time)drückt aus, dass das Ereignis zum Zeitpunkt eintritt Time.

Das folgende Beispiel veranschaulicht, wie diese Klauseln verwendet werden können, um Kausalität in einer Welt aus Spielzeugbausteinen zu untersuchen . Im Ausgangszustand zum Zeitpunkt 0 befindet sich ein grüner Baustein auf einem Tisch, und ein roter Baustein ist darauf gestapelt (wie eine Ampel). Zum Zeitpunkt 0 wird der rote Baustein auf den Tisch gelegt. Zum Zeitpunkt 1 wird der grüne Baustein auf den roten gelegt. Das Verschieben eines Objekts an einen Ort beendet den Zustand, in dem sich das Objekt an irgendeinem Ort befindet, und beginnt den Zustand, in dem sich das Objekt an dem Ort befindet, an den es verschoben wird. 

hält ( auf ( grüner_Block , Tabelle ), 0 ). hält ( auf ( roter_Block , grüner_Block ), 0 ).passiert ( bewegen ( roter_Block , Tabelle ), 0 ). passiert ( bewegen ( grüner_Block , roter_Block ), 1 ).initiiert ( Bewegung ( Objekt , Ort ), auf ( Objekt , Ort )). beendet ( Bewegung ( Objekt , Ort2 ), auf ( Objekt , Ort1 )).?- hält ( Fakt , Zeit ).Fakt = on ( green_block , table ), Zeit = 0. Fakt = on ( red_block , green_block ), Zeit = 0. Fakt = on ( green_block , table ), Zeit = 1. Fakt = on ( red_block , table ), Zeit = 1. Fakt = on ( green_block , red_block ), Zeit = 2. Fakt = on ( red_block , table ), Zeit = 2.

Vorwärts- und Rückwärtsdenken führen zu denselben Antworten auf das Ziel holds(Fact, Time). Vorwärtsdenken erzeugt jedoch die Ergebnisse progressiv in zeitlicher Reihenfolge, während Rückwärtsdenken die Ergebnisse regressiv erzeugt , wie es bei der domänenspezifischen Anwendung der Regression im Situationskalkül der Fall ist . [ 47 ]

Logische Programmierung hat sich auch für die Darstellung domänenspezifischer Expertise in Expertensystemen als nützlich erwiesen . [ 48 ] Menschliche Expertise ist jedoch, wie allgemeiner gesunder Menschenverstand, meist implizit und stillschweigend , und es ist oft schwierig, solches implizites Wissen in expliziten Regeln abzubilden. Diese Schwierigkeit tritt jedoch nicht auf, wenn logische Programme zur Darstellung der bestehenden, expliziten Regeln eines Unternehmens oder einer Rechtsbehörde verwendet werden.

Hier ist beispielsweise eine vereinfachte Version des ersten Satzes des britischen Staatsangehörigkeitsgesetzes, der besagt, dass eine Person, die im Vereinigten Königreich geboren wird, mit der Geburt die britische Staatsbürgerschaft erwirbt, wenn ein Elternteil der Person zum Zeitpunkt der Geburt die britische Staatsbürgerschaft besitzt: 

initiiert ( Geburt ( Person ), Bürger ( Person , uk )):- Zeit_von ( Geburt ( Person ), Zeit ), Ort_von ( Geburt ( Person ), uk ), Elternteil_Kind ( Andere_Person , Person ), hält ( Bürger ( Andere_Person , uk ), Zeit ).

Historisch gesehen war die Darstellung eines großen Teils des britischen Staatsangehörigkeitsgesetzes als Logikprogramm in den 1980er Jahren [ 49 ] „von enormem Einfluss auf die Entwicklung computergestützter Darstellungen von Gesetzen und zeigte, wie die Logikprogrammierung intuitiv ansprechende Darstellungen ermöglicht, die direkt zur Generierung automatischer Schlussfolgerungen eingesetzt werden können“. [ 50 ]

In jüngerer Zeit hat sich das PROLEG-System [ 51 ] , das 2009 initiiert wurde und aus etwa 2500 Regeln und Ausnahmen des japanischen Zivilgesetzbuches und der Rechtsprechung des Obersten Gerichtshofs besteht, zur möglicherweise größten Rechtsnormensammlung der Welt entwickelt. [ 52 ]

Varianten und Erweiterungen

Prolog

Die SLD-Resolutionsregel für Inferenz ist neutral hinsichtlich der Reihenfolge, in der Teilziele in den Klauselrümpfen zur Lösung ausgewählt werden können . Aus Effizienzgründen beschränkt Prolog diese Reihenfolge auf die Reihenfolge, in der die Teilziele geschrieben wurden. SLD ist auch neutral hinsichtlich der Strategie zur Suche im Raum der SLD-Beweise. Prolog durchsucht diesen Raum von oben nach unten in Tiefensuche und probiert verschiedene Klauseln zur Lösung desselben (Teil-)Ziels in der Reihenfolge ihrer Schreibweise aus.

Diese Suchstrategie hat den Vorteil, dass der aktuelle Zweig des Baums effizient durch einen Stapel dargestellt werden kann . Wird eine Zielklausel oben im Stapel auf eine neue Zielklausel reduziert, wird diese neue Zielklausel oben auf den Stapel gelegt. Kann das ausgewählte Teilziel in der Zielklausel oben im Stapel nicht gelöst werden, geht die Suchstrategie zurück , entfernt die Zielklausel vom Stapel und versucht die Lösung des ausgewählten Teilziels in der vorherigen Zielklausel mit der nächsten passenden Klausel erneut.

Backtracking lässt sich durch ein Teilziel namens ` cut` (geschrieben als `!`) einschränken, das immer erfolgreich ist, aber nicht rückgängig gemacht werden kann. `cut` kann die Effizienz steigern, aber auch die logische Bedeutung von Klauseln beeinträchtigen. In vielen Fällen kann die Verwendung von `cut` durch Negation als Fehlschlag ersetzt werden. Tatsächlich lässt sich Negation als Fehlschlag in Prolog definieren, indem man `cut` zusammen mit einem beliebigen Literal, beispielsweise ` fail` , verwendet, das mit dem Kopf einer `no`-Klausel unifiziert. 

nicht ( P ) :- P , !, fail . nicht ( P ).

Prolog bietet neben `cut` weitere Funktionen, die keine logische Interpretation haben. Dazu gehören die eingebauten Prädikate `assert` und `retract` , mit denen der Programmzustand während der Programmausführung destruktiv verändert werden kann.

Das oben genannte Beispiel der Spielzeugbausteinwelt kann beispielsweise ohne Rahmenaxiome mithilfe destruktiver Zustandsänderungen implementiert werden: 

on ( green_block , table ). on ( red_block , green_block ).move ( Object , Place2 ) :- retract ( on ( Object , Place1 )), assert ( on ( Object , Place2 ).

Die Abfolge der Bewegungsereignisse und die daraus resultierenden Positionen der Blöcke können durch Ausführen der Abfrage berechnet werden: 

?- move ( red_block , table ), move ( green_block , red_block ), on ( Object , Place ).Objekt = roter_Block , Ort = Tisch . Objekt = grüner_Block , Ort = roter_Block .

Zur Bereitstellung eines logischen Rahmens für solche destruktiven Zustandsänderungen wurden verschiedene Erweiterungen der logischen Programmierung entwickelt. [ 53 ] [ 54 ] [ 55 ]

Die breite Palette an Prolog-Anwendungen, sowohl isoliert als auch in Kombination mit anderen Sprachen, wird im Year of Prolog Book [ 21 ] hervorgehoben, das anlässlich des 50-jährigen Jubiläums von Prolog im Jahr 2022 erscheint.

Prolog hat auch zur Entwicklung anderer Programmiersprachen beigetragen, darunter ALF , Fril , Gödel , Mercury , Oz , Ciao , Visual Prolog , XSB und λProlog .

Constraint-Logikprogrammierung

Constraint Logic Programming (CLP) kombiniert Horn Clause Logic Programming mit Constraint Solving . Es erweitert Horn Clauses, indem es die Verwendung bestimmter, als Constraint-Prädikate deklarierter Prädikate als Literale im Rumpf einer Klausel ermöglicht. Constraint-Prädikate werden nicht durch die Fakten und Regeln des Programms definiert, sondern sind durch eine domänenspezifische modelltheoretische Struktur oder Theorie vordefiniert.

Prozedural werden Teilziele, deren Prädikate durch das Programm definiert sind, mittels Zielreduktion gelöst, wie in der herkömmlichen logischen Programmierung. Die Bedingungen werden jedoch vereinfacht und ihre Erfüllbarkeit durch einen domänenspezifischen Constraint-Solver geprüft, der die Semantik der Constraint-Prädikate implementiert. Ein Ausgangsproblem wird gelöst, indem es auf eine erfüllbare Konjunktion von Bedingungen reduziert wird.

Interessanterweise enthielt die erste Version von Prolog bereits ein Constraint-Prädikat dif(term1, term2) aus Philippe Roussels Dissertation von 1972, das erfolgreich ist, wenn beide Argumente unterschiedliche Terme sind, aber verzögert wird, wenn einer der Terme eine Variable enthält. [ 52 ]

Das folgende Constraint-Logik-Programm stellt eine einfache temporale Datenbank der john'sGeschichte als Lehrbeispiel dar: 

unterrichtet ( john , Hardware , T ) : 1990 ≤ T , T < 1999. unterrichtet ( john , Software , T ) : 1999 ≤ T , T < 2005. unterrichtet ( john , Logik , T ) : 2005 ≤ T , T ≤ 2012. Rang ( john , Dozent , T ) : 1990 ≤ T , T < 2010. Rang ( john , Professor , T ) : 2010 ≤ T , T < 2014.

Hierbei ≤handelt <es sich um Einschränkungsprädikate mit ihrer üblichen beabsichtigten Semantik. Die folgende Zielklausel fragt die Datenbank ab, um herauszufinden, wann johnsowohl gelehrt logicals auch war professor: 

?- lehrt ( john , Logik , T ), Rang ( john , Professor , T ).

Die Lösung 2010 ≤ T, T ≤ 2012 ergibt sich aus der Vereinfachung der Nebenbedingungen. 2005 ≤ T, T ≤ 2012, 2010 ≤ T, T < 2014.

Die Constraint-Logikprogrammierung wird zur Lösung von Problemen in Bereichen wie Bauingenieurwesen , Maschinenbau , Verifikation digitaler Schaltungen , automatisierter Flugplanung , Flugsicherung und Finanzwesen eingesetzt . Sie ist eng mit der abduktiven Logikprogrammierung verwandt .

Datenprotokoll

Datalog ist eine Datenbankdefinitionssprache, die eine relationale Sichtweise von Daten, wie in relationalen Datenbanken , mit einer logischen Sichtweise, wie in der logischen Programmierung, kombiniert.

Relationale Datenbanken verwenden einen relationalen Kalkül oder eine relationale Algebra mit relationalen Operationen wie Vereinigung , Schnittmenge , Mengendifferenz und kartesischem Produkt, um Abfragen zu spezifizieren, die auf eine Datenbank zugreifen. Datalog verwendet logische Verknüpfungen wie „ oder“ , „ und “ und „nicht“ in den Regelkörpern, um Relationen als Teil der Datenbank selbst zu definieren.

Bereits früh in der Entwicklung relationaler Datenbanken wurde erkannt, dass rekursive Anfragen weder in der relationalen Algebra noch im relationalen Kalkül ausgedrückt werden können und dass dieser Mangel durch die Einführung eines Fixpunktoperators behoben werden kann. [ 56 ] [ 57 ] Im Gegensatz dazu lassen sich rekursive Relationen auf natürliche Weise durch Regeln in Logikprogrammen definieren, ohne dass neue logische Verknüpfungen oder Operatoren erforderlich sind.

Datalog unterscheidet sich von allgemeinerer logischer Programmierung dadurch, dass es nur Konstanten und Variablen als Terme verwendet. Darüber hinaus sind alle Fakten variablenfrei, und die Regeln sind so eingeschränkt, dass bei ihrer Bottom-up-Ausführung auch die abgeleiteten Fakten variablenfrei sind.

Betrachten wir beispielsweise die Familiendatenbank: 

Mutter_Kind ( Elizabeth , Charles ). Vater_Kind ( Charles , William ). Vater_Kind ( Charles , Harry ). Elternteil_Kind ( X , Y ) :- Mutter_Kind ( X , Y ). Elternteil_Kind ( X , Y ) :- Vater_Kind ( X , Y ). Vorfahre_Nachkomme ( X , Y ) :- Elternteil_Kind ( X , X ). Vorfahre_Nachkomme ( X , Y ) :- Vorfahre_Nachkomme ( X , Z ), Vorfahre_Nachkomme ( Z , Y ).

Die Bottom-up-Ausführung ermittelt die folgenden zusätzlichen Fakten und wird beendet: 

parent_child ( elizabeth , charles ). parent_child ( charles , william ). parent_child ( charles , harry ).Vorfahre_Nachkomme ( Elizabeth , Charles ). Vorfahre_Nachkomme ( Charles , William ). Vorfahre_Nachkomme ( Charles , Harry ).Vorfahre_Nachkomme ( elizabeth , william ). Vorfahre_Nachkomme ( elizabeth , harry ).

Die Top-Down-Ausführung liefert die gleichen Antworten auf die Anfrage: 

?- ancestor_descendant ( X , Y ).

Dann gerät es jedoch in eine Endlosschleife. Die Top-Down-Ausführung mit Tabellenfunktion liefert hingegen die gleichen Ergebnisse und beendet sich ohne Schleife.

Antwortmengenprogrammierung

Wie Datalog ist auch Answer Set Programming (ASP) nicht Turing-vollständig. Anstatt Ziele (oder Anfragen) vom Programm zu trennen, das zur Lösung dieser Ziele verwendet wird, behandelt ASP das gesamte Programm als Ziel und löst dieses, indem ein stabiles Modell generiert wird, das das Ziel erfüllt. Zu diesem Zweck verwendet es die Semantik stabiler Modelle , nach der ein logisches Programm null, ein oder mehrere beabsichtigte Modelle haben kann. Beispielsweise stellt das folgende Programm eine degenerierte Variante des Kartenfärbungsproblems dar, bei dem zwei Länder rot oder grün eingefärbt werden sollen: 

Land ( oz ).Land ( iz ).angrenzend ( oz , iz ) .Farbe ( C , rot ) : - Land ( C ), nicht ( Farbe ( C , grün )). Farbe ( C , grün ) :- Land ( C ) , nicht ( Farbe ( C , rot )).

Das Problem hat vier Lösungen, die durch vier stabile Modelle dargestellt werden: 

Land ( oz ). Land ( iz ). angrenzend ( oz , iz ). Farbe ( oz , rot ). Farbe ( iz , rot ).Land ( oz ). Land ( iz ). angrenzend ( oz , iz ). Farbe ( oz , grün ). Farbe ( iz , grün ).Land ( oz ). Land ( iz ). angrenzend ( oz , iz ). Farbe ( oz , rot ). Farbe ( iz , grün ).Land ( oz ). Land ( iz ). Angrenzend ( oz , iz ). Farbe ( oz , grün ). Farbe ( iz , rot ).

Um die Standardversion des Kartenfärbungsproblems darzustellen, muss die Einschränkung hinzugefügt werden, dass zwei benachbarte Länder nicht die gleiche Farbe haben dürfen. In ASP kann diese Einschränkung als Klausel der folgenden Form geschrieben werden: 

:- Land ( C1 ), Land ( C2 ), angrenzend ( C1 , C2 ), Farbe ( C1 , X ), Farbe ( C2 , X ).

Mit dieser zusätzlichen Einschränkung hat das Problem nun nur noch zwei Lösungen: 

Land ( oz ). Land ( iz ). angrenzend ( oz , iz ). Farbe ( oz , rot ). Farbe ( iz , grün ).Land ( oz ). Land ( iz ). Angrenzend ( oz , iz ). Farbe ( oz , grün ). Farbe ( iz , rot ).

Durch das Hinzufügen von Einschränkungen der Form :- Body.werden Modelle eliminiert, in denen Bodydies zutrifft.

Verwirrenderweise unterscheiden sich Constraints in ASP von Constraints in CLP . Constraints in CLP sind Prädikate, die Antworten auf Anfragen (und Lösungen von Zielen) qualifizieren. Constraints in ASP hingegen sind Klauseln, die Modelle ausschließen, die andernfalls die Ziele erfüllen würden. Sie ähneln Integritätsbedingungen in Datenbanken.

Diese Kombination aus gewöhnlichen Logikprogrammierungsklauseln und Constraint-Klauseln veranschaulicht die Generieren-und-Testen-Methodik der Problemlösung in ASP: Die gewöhnlichen Klauseln definieren einen Suchraum möglicher Lösungen, und die Constraints filtern unerwünschte Lösungen heraus. [ 58 ]

Die meisten Implementierungen von ASP erfolgen in zwei Schritten: Zuerst wird das Programm auf alle möglichen Arten instanziiert und so auf ein aussagenlogisches Programm reduziert (bekannt als Grounding ). Anschließend wird ein Problemlöser für aussagenlogische Probleme angewendet, beispielsweise der DPLL-Algorithmus oder ein Boolescher SAT-Löser . Einige Implementierungen, wie etwa s(CASP) [ 59 ], verwenden jedoch ein zielgerichtetes, Top-Down-Verfahren, das der SLD-Resolution ähnelt und ohne Grounding auskommt.

Abduktive Logikprogrammierung

Abduktive logische Programmierung (ALP) [ 60 ] erweitert, ähnlich wie CLP, die normale logische Programmierung, indem sie es erlaubt, dass Klauselrümpfe Literale enthalten, deren Prädikate nicht durch Klauseln definiert sind. In ALP werden diese Prädikate als abduzierbar (oder annehmbar ) deklariert und wie beim abduktiven Schließen verwendet , um Beobachtungen zu erklären oder allgemeiner, um dem Programm neue Fakten (als Annahmen) hinzuzufügen und so Ziele zu erreichen.

Nehmen wir beispielsweise an, wir haben einen Anfangszustand, in dem sich zum Zeitpunkt 0 ein roter Block auf einem grünen Block auf einem Tisch befindet: 

hält ( auf ( grüner_Block , Tabelle ), 0 ). hält ( auf ( roter_Block , grüner_Block ), 0 ).

Angenommen, uns wird auch das Ziel vorgegeben: 

?- hält ( auf ( grüner_Block , roter_Block ), 3 ), hält ( auf ( roter_Block , Tabelle ), 3 ).

Das Ziel kann eine Beobachtung darstellen, in welchem ​​Fall die Lösung eine Erklärung dieser Beobachtung ist. Oder das Ziel kann einen angestrebten zukünftigen Zustand darstellen, in welchem ​​Fall die Lösung ein Plan zur Erreichung des Ziels ist. [ 61 ]

Wir können die zuvor vorgestellten Regeln für Ursache und Wirkung nutzen, um das Ziel zu erreichen, indem wir das happensPrädikat als abduzierbar behandeln: 

hält ( Fakt , Zeit2 ) :- passiert ( Ereignis , Zeit1 ), Zeit2 ist Zeit1 + 1 , initiiert ( Ereignis , Fakt ).hält ( Fakt , Zeit2 ) :- passiert ( Ereignis , Zeit1 ), Zeit2 ist Zeit1 + 1 , hält ( Fakt , Zeit1 ), nicht ( beendet ( Fakt , Zeit1 )).terminated ( Fact , Time ) :- happens ( Event , Time ), terminates ( Event , Fact ).initiiert ( Bewegung ( Objekt , Ort ), auf ( Objekt , Ort )). beendet ( Bewegung ( Objekt , Ort2 ), auf ( Objekt , Ort1 )).

ALP löst das Ziel, indem es rückwärts argumentiert und dem Programm Annahmen hinzufügt, um abduzierbare Teilziele zu lösen. In diesem Fall gibt es viele alternative Lösungen, darunter: 

happens ( move ( red_block , table ), 0 ). happens ( tick , 1 ). happens ( move ( green_block , red_block ), 2 ).
passiert ( tick , 0 ). passiert ( move ( red_block , table ), 1 ). passiert ( move ( green_block , red_block ), 2 ).
happens ( move ( red_block , table ), 0 ). happens ( move ( green_block , red_block ), 1 ). happens ( tick , 2 ).

Hierbei tickhandelt es sich um ein Ereignis, das den Zeitablauf markiert, ohne irgendwelche Fluente zu initiieren oder zu beenden.

Es gibt auch Lösungen, bei denen die beiden moveEreignisse gleichzeitig eintreten. Zum Beispiel: 

happens ( move ( red_block , table ), 0 ). happens ( move ( green_block , red_block ), 0 ). happens ( tick , 1 ). happens ( tick , 2 ).

Solche Lösungen können, falls nicht gewünscht, durch Hinzufügen einer Integritätsbedingung entfernt werden, die einer Constraint-Klausel in ASP ähnelt: 

:- happens ( move ( Block1 , Place ), Time ), happens ( move ( Block2 , Block1 ), Time ).

Abduktive Logikprogrammierung wurde für Fehlerdiagnose, Planung, Verarbeitung natürlicher Sprache und maschinelles Lernen eingesetzt. Sie wurde auch verwendet, um Negation als Fehler zu interpretieren, was eine Form des abduktiven Schließens darstellt. [ 62 ]

Induktive Logikprogrammierung

Induktive logische Programmierung (ILP) ist ein Ansatz des maschinellen Lernens , der logische Programme als hypothetische Verallgemeinerungen positiver und negativer Beispiele erzeugt . Ausgehend von einem logischen Programm, das Hintergrundwissen und positive Beispiele repräsentiert, sowie Einschränkungen, die negative Beispiele darstellen, erzeugt ein ILP-System ein logisches Programm, das die positiven Beispiele verallgemeinert und gleichzeitig die negativen Beispiele ausschließt.

ILP ähnelt ALP insofern, als beide als Hypothesengenerierung zur Erklärung von Beobachtungen und als Anwendung von Beschränkungen zum Ausschluss unerwünschter Hypothesen betrachtet werden können. Im Gegensatz dazu sind die Hypothesen bei ALP variablenfreie Fakten, während sie bei ILP allgemeine Regeln darstellen. [ 63 ] [ 64 ]

Beispielsweise können aktuelle ILP-Systeme, wenn nur Hintergrundwissen über die Mutter-Kind- und Vater-Kind-Beziehungen sowie geeignete Beispiele für die Großeltern-Kind-Beziehung vorliegen, die Definition von Großeltern-Kind generieren, indem sie ein Hilfsprädikat erfinden, das als Eltern-Kind-Beziehung interpretiert werden kann: [ 65 ].

grandparent_child ( X , Y ):- auxiliary ( X , Z ), auxiliary ( Z , Y ). auxiliary ( X , Y ):- mother_child ( X , Y ). auxiliary ( X , Y ):- father_child ( X , Y ).

Stuart Russell [ 66 ] bezeichnete die Erfindung neuer Konzepte als den wichtigsten Schritt, der für das Erreichen einer KI auf menschlichem Niveau notwendig sei.

Neuere Arbeiten im Bereich der ILP, die Logikprogrammierung, Lernen und Wahrscheinlichkeit kombinieren, haben die Gebiete des statistischen relationalen Lernens und der probabilistischen induktiven Logikprogrammierung hervorgebracht .

Parallele Logikprogrammierung

Die nebenläufige logische Programmierung integriert Konzepte der logischen Programmierung mit der nebenläufigen Programmierung . Ihre Entwicklung erfuhr in den 1980er Jahren einen großen Aufschwung durch ihre Wahl zur Systemprogrammiersprache des japanischen Projekts der fünften Generation (FGCS) . [ 67 ]

Ein Programm für nebenläufige Logik ist eine Menge von bewachten Horn-Klauseln der Form:

H :- G1, ..., Gn | B1, ..., Bn.

Die Konjunktion wird als Schutz des Satzes bezeichnet, und | ist der Verpflichtungsoperator. Deklarativ werden geschützte Horn-Sätze als gewöhnliche logische Implikationen gelesen: G1, ... , Gn

H if G1 and ... and Gn and B1 and ... and Bn.

Prozedural werden jedoch, wenn mehrere Klauseln existieren, deren Kopf Heinem gegebenen Ziel entspricht, alle Klauseln parallel ausgeführt, wobei geprüft wird, ob ihre Bedingungen erfüllt sind. Sind die Bedingungen mehrerer Klauseln erfüllt, wird eine Klausel ausgewählt, und die Ausführung wird mit den Teilzielen der ausgewählten Klausel fortgesetzt. Auch diese Teilziele können parallel ausgeführt werden. Somit implementiert die nebenläufige logische Programmierung eine Form von „Don't-Care-Nichtdeterminismus“ anstelle von „Don't-Know-Nichtdeterminismus“. G1, ... , GnB1, ..., Bn

Das folgende nebenläufige Logikprogramm definiert beispielsweise ein Prädikat , mit dem zwei Listen und gemischt und zu einer einzigen Liste kombiniert shuffle(Left, Right, Merge)werden können , wobei die Reihenfolge der beiden Listen und erhalten bleibt : LeftRightMergeLeftRight

shuffle ([], [], []). shuffle ( Left , Right , Merge ) :- Left = [ First | Rest ] | Merge = [ First | ShortMerge ], shuffle ( Rest , Right , ShortMerge ) .shuffle ( Left , Right , Merge ) :- Right = [ First | Rest ] | Merge = [ First | ShortMerge ], shuffle ( Left , Rest , ShortMerge ).

Hierbei []steht für die leere Liste und [Head | Tail]für eine Liste, deren erstes Element Headvon der Liste gefolgt wird Tail, wie in Prolog. (Beachten Sie, dass das erste Vorkommen von | in der zweiten und dritten Klausel der Listenkonstruktor ist, während das zweite Vorkommen von | der Commit-Operator ist.) Das Programm kann beispielsweise verwendet werden, um die Listen [ace, queen, king]und [1, 4, 2]durch Aufruf der Zielklausel zu mischen: 

shuffle ([ ace , queen , king ], [ 1 , 4 , 2 ], Merge ).

Das Programm wird nichtdeterministisch eine einzige Lösung generieren, zum Beispiel Merge = [ace, queen, 1, king, 4, 2].

Carl Hewitt argumentierte [ 68 ] , dass die nebenläufige logische Programmierung aufgrund der Unbestimmtheit nebenläufiger Berechnungen keine allgemeine Nebenläufigkeit implementieren könne. Gemäß der logischen Semantik ist jedoch jedes Ergebnis einer Berechnung eines nebenläufigen logischen Programms eine logische Konsequenz des Programms, auch wenn nicht alle logischen Konsequenzen abgeleitet werden können.

Parallele Constraint-Logikprogrammierung

Die nebenläufige Constraint-Logikprogrammierung [ 69 ] kombiniert nebenläufige Logikprogrammierung und Constraint-Logikprogrammierung und nutzt Constraints zur Steuerung der Nebenläufigkeit. Eine Klausel kann eine Bedingung (Guard) enthalten, die eine Menge von Constraints darstellt, welche die Anwendbarkeit der Klausel unter Umständen verhindern. Sind die Bedingungen mehrerer Klauseln erfüllt, entscheidet sich die nebenläufige Constraint-Logikprogrammierung für die Verwendung einer einzigen Klausel.

Logikprogrammierung höherer Ordnung

Mehrere Forscher haben die logische Programmierung um Programmierfunktionen höherer Ordnung erweitert, die von der Logik höherer Ordnung abgeleitet sind , wie beispielsweise Prädikatvariablen. Zu diesen Sprachen gehören die Prolog-Erweiterungen HiLog [ 70 ] und λProlog [ 71 ] .

Lineare Logikprogrammierung

Die Implementierung der Logikprogrammierung auf Basis linearer Logik hat zur Entwicklung von Logikprogrammiersprachen geführt, die deutlich ausdrucksstärker sind als solche, die auf klassischer Logik basieren. Horn-Klausel-Programme können Zustandsänderungen lediglich durch die Änderung von Prädikatarargumenten darstellen. In der linearen Logikprogrammierung hingegen kann die umgebende lineare Logik zur Unterstützung von Zustandsänderungen genutzt werden. Zu den frühen Entwürfen von Logikprogrammiersprachen auf Basis linearer Logik gehören LO [ 72 ] , Lolli [ 73 ] , ACL [ 74 ] und Forum [ 75 ] . Forum bietet eine zielgerichtete Interpretation der gesamten linearen Logik.

Objektorientierte Logikprogrammierung

F-Logik [ 76 ] erweitert die logische Programmierung um Objekte und die Frame-Syntax.

Logtalk [ 77 ] erweitert die Programmiersprache Prolog um Unterstützung für Objekte, Protokolle und weitere OOP-Konzepte. Es unterstützt die meisten standardkonformen Prolog-Systeme als Backend-Compiler.

Programmierung der Transaktionslogik

Die Transaktionslogik [ 53 ] ist eine Erweiterung der logischen Programmierung mit einer logischen Theorie zustandsverändernder Aktualisierungen. Sie besitzt sowohl eine modelltheoretische als auch eine prozedurale Semantik. Eine Implementierung einer Teilmenge der Transaktionslogik ist im Flora-2 -System [ 78 ] verfügbar. Weitere Prototypen existieren ebenfalls .

Siehe auch

Zitate

  1. ^ Tärnlund, S.Å. (1977). „Horn clause computability“. BIT Numerical Mathematics . 17 (2): 215– 226. doi : 10.1007/BF01932293 . S2CID  32577496 .
  2. ^ Andréka, H.; Németi, I. (1978). „Die verallgemeinerte Vollständigkeit der Horn-Prädikatenlogik als Programmiersprache“ . Acta Cybernetica . 4 (1): 3–10 .
  3. ^ Green, Cordell. Anwendung des Theorembeweisens zur Problemlösung (PDF) . IJCAI 1969.
  4. ^ Foster, JM; Elcock, EW (1969). ABSYS 1: Ein inkrementeller Compiler für Assertions: Eine Einführung . Vierter jährlicher Workshop über Maschinelle Intelligenz. Maschinelle Intelligenz. Band 4. Edinburgh, UK: Edinburgh University Press . S.  423–429 .
  5. ^ Kowalski, RA (1988). „Die Anfänge der logischen Programmierung“ (PDF) . Communications of the ACM . 31 : 38–43 . doi : 10.1145/35043.35046 . S2CID 12259230 . 
  6. ^ Hewitt, Carl . Planner: Eine Sprache zum Beweisen von Theoremen in Robotern (PDF) . IJCAI 1969.
  7. ^ Winograd, Terry (1972). „Understanding natural language“. Cognitive Psychology . 3 (1): 1– 191. doi : 10.1016/0010-0285(72)90002-3 .
  8. ^ Jeff Rulifson ; Jan Derksen; Richard Waldinger (November 1973). QA4, Ein prozeduraler Kalkül für intuitives Denken (PDF) (Technischer Bericht). SRI AI Center Technical Note 73.
  9. ^ Davies, JM, 1971. POPLER: ein POP-2-Planer. Universität Edinburgh, Abteilung für Maschinelle Intelligenz und Wahrnehmung.
  10. ^ McDermott, DV ; Sussman, GJ (Mai 1972). Das Conniver-Referenzhandbuch (Technischer Bericht). Artificial Intelligence Memo Nr. 259.
  11. ^ Reboh, R.; Sacerdoti, ED (August 1973). Ein vorläufiges QLISP-Handbuch (Technischer Bericht). Zentrum für Künstliche Intelligenz, SRI International.
  12. ^ Kornfeld, WA; Hewitt, CE (1981). „Die Metapher der wissenschaftlichen Gemeinschaft“. IEEE Transactions on Systems, Man, and Cybernetics . 11 (1): 24–33 . Bibcode : 1981ITSMC..11...24K . doi : 10.1109/TSMC.1981.4308575 . hdl : 1721.1/5693 . S2CID 1322857 . 
  13. ^ Hayes, Pat (1973). „Computation and Deduction“. Proceedings of the 2nd MFCS Symposium . Czechoslovak Academy of Sciences . S.  105–118 .
  14. ^ Robinson, J. (1965). „Automatisches Beweisen mit Hyperauflösung“. International Journal of Computer Mathematics . 1 (3): 227–234 . doi : 10.2307/2272384 . JSTOR 2272384 . 
  15. ^ Kowalski, Robert; Kuehner, Donald (1971). „Lineare Resolution mit Selektionsfunktion“ (PDF) . Künstliche Intelligenz . 2 ( 3–4 ): 227–260 . doi : 10.1016/0004-3702(71)90012-9 .
  16. ^ Kowalski, Robert (1973). „Prädikatenlogik als Programmiersprache“ (PDF) . Abteilung für Künstliche Intelligenz, Universität Edinburgh . Memo 70.Ebenfalls enthalten in: Proceedings IFIP Congress, Stockholm, North Holland Publishing Co., 1974, S. 569–574.
  17. ^ Warren, DH; Pereira, LM; Pereira, F. (1977). „Prolog – die Sprache und ihre Implementierung im Vergleich mit Lisp“. ACM SIGPLAN Notices . 12 (8): 109–115 . doi : 10.1145/872734.806939 .
  18. ^ Ueda, K., 2018. Logik-/Constraint-Programmierung und Parallelverarbeitung: Die hart erkämpften Lehren aus dem Projekt des fünften Computers. Science of Computer Programming, 164, S. 3–17.
  19. ^ HP Newquist, 2020. Die Schöpfer des Gehirns: Die Geschichte der künstlichen Intelligenz. The Relayer Group.
  20. ^ Gallaire, Hervé; Minker, John „Jack“, Hrsg. (1978), „Logic and Data Bases, Symposium on Logic and Data Bases, Centre d'études et de recherches de Toulouse, 1977“, Advances in Data Base Theory , New York: Plenum Press, ISBN 978-0-306-40060-5Die
  21. ^ a b Warren, DS (2023). „Einführung in Prolog“. In: Warren, DS; Dahl, V; Eiter, T; Hermenegildo, MV; Kowalski, R.; Rossi, F. (Hrsg.). Prolog: Die nächsten 50 Jahre . Lecture Notes in Computer Science(). Band 13900. Springer, Cham. S.  3–19 . doi : 10.1007/978-3-031-35254-6_1 . ISBN 978-3-031-35253-9Die
  22. ^ Robinson, J. Alan (2001). „Eingeladener Leitartikel“ . Theorie und Praxis der logischen Programmierung . 1 (1). Cambridge University Press : 1. doi : 10.1017/s1471068400000028 .
  23. ^ R. A. Kowalski (Juli 1979). „Algorithmus = Logik + Kontrolle“ . Communications of the ACM . 22 (7): 424–436 . doi : 10.1145/359131.359136 . S2CID 2509896 . 
  24. ^ Bruynooghe, M.; Pereira, L. M. (1984). „Deduktionsrevision durch intelligentes Backtracking“. Implementierungen von Prolog . Chichester, England: Ellis Horwood. S.  194–215 .
  25. ^ Nakamura, K. (Juli 1985). Heuristic Prolog: Logikprogrammausführung durch heuristische Suche . Konferenz über Logikprogrammierung. Berlin, Heidelberg: Springer Berlin Heidelberg. S.  148–155 .
  26. ^ Genesereth, MR; Ginsberg, ML (1985). „Logische Programmierung“ . Communications of the ACM . 28 (9): 933–941 . doi : 10.1145/4284.4287 . S2CID 15527861 . 
  27. ^ Swift, T.; Warren, DS (Januar 2012). „XSB: Erweiterung von Prolog mit tabellarischer Logikprogrammierung“. Theory and Practice of Logic Programming . 12 ( 1–2 ): 157–187 . arXiv : 1012.5123 . doi : 10.1017/S1471068411000500 . S2CID 6153112 . 
  28. ^ a b Daniel Friedman; William Byrd; Oleg Kiselyov; Jason Hemann (2018). The Reasoned Schemer, Second Edition . The MIT Press .
  29. ^ A. Casas, D. Cabeza, MV Hermenegildo. Ein syntaktischer Ansatz zur Kombination von funktionaler Notation, verzögerter Auswertung und höherer Ordnung in LP-Systemen. 8. Internationales Symposium über funktionale und logische Programmierung (FLOPS'06), Seiten 142–162, April 2006.
  30. ^ Kersting, K., Mladenov, M. und Tokmakov, P., 2017. Relationale lineare Programmierung. Künstliche Intelligenz, 244, S. 188-216.
  31. ^ Beyer, D., Mai 2006. Relationale Programmierung mit CrocoPat. In: Proceedings der 28. Internationalen Konferenz für Software-Engineering (S. 807-810).
  32. ^ MacLennan, Bruce James (März 1983). Wexelblat, Richard L. (Hrsg.). „Overview of relational programming“ . ACM SIGPLAN Notices . 18 (3). New York, NY: Association for Computing Machinery: 36–45 . doi : 10.1145/988209.988213 . hdl : 10945/29034 . ISSN 0362-1340 . OCLC 25073822. Abgerufen am 8. Mai 2025 .  
  33. ^ Behnke, R., Berghammer, R., Meyer, E. und Schneider, P., 1998. RELVIEW – Ein System für Berechnungen mit Relationen und relationaler Programmierung. In: Fundamental Approaches to Software Engineering: First International Conference, FASE’98, im Rahmen der Joint European Conferences on Theory and Practice of Software, ETAPS’98, Lissabon, Portugal, 28. März – 4. April 1998, Proceedings 1 (S. 318–321). Springer Berlin Heidelberg.
  34. ^ Van Emden, MH; Kowalski, RA (Oktober 1976). „Die Semantik der Prädikatenlogik als Programmiersprache“ . Journal of the ACM . 23 (4): 733–742 . doi : 10.1145/321978.321991 . S2CID 11048276 . 
  35. Clark , K. L. (1977). „Negation as Failure“. Logic and Data Bases . Boston, MA: Springer US. S.  293–322 . doi : 10.1007/978-1-4684-3384-5_11 . ISBN 978-1-4684-3386-9Die
  36. ^ Gelfond, M.; Przymusinska, H.; Przymusinski, T. (1989). „Über die Beziehung zwischen Zirkumskription und Negation als Fehlschlag“. Artificial Intelligence . 38 (1): 75–94 . doi : 10.1016/0004-3702(89)90068-4 .
  37. ^ Shepherdson, JC (1984). „Negation als Fehlschlag: Ein Vergleich von Clarks vollständiger Datenbank und Reiters Annahme einer geschlossenen Welt“. The Journal of Logic Programming . 1 (1): 51–79 . doi : 10.1016/0743-1066(84)90023-2 .
  38. ^ Denecker, M.; Ternovska, E. (2008). „Eine Logik nichtmonotoner induktiver Definitionen“ . ACM Transactions on Computational Logic . 9 (2): 14:1–14:52. arXiv : cs/0501025 . doi : 10.1145/1342991.1342998 . S2CID 13156469 . 
  39. ^ Rao, P.; Sagonas, K.; Swift, T.; Warren, D. S.; Freire, J. (28.–31. Juli 1997). XSB: Ein System zur effizienten Berechnung wohlfundierter Semantiken . Logic Programming And Nonmonotonic Reasoning: 4. Internationale Konferenz, LPNMR’97. Schloss Dagstuhl, Deutschland: Springer Berlin Heidelberg. S.  430–440 . doi : 10.1007/3-540-63255-7_33 .
  40. ^ W. Chen; DS Warren (Januar 1996). „Tabellenbasierte Auswertung mit Verzögerung für allgemeine Logikprogramme“ . Journal of the ACM . 43 (1): 20–74 . doi : 10.1145/227595.227597 . S2CID 7041379 . 
  41. ^ Phan Minh Dung (1995). „Über die Akzeptabilität von Argumenten und ihre fundamentale Rolle beim nichtmonotonen Schließen, der logischen Programmierung und n-Personen-Spielen“ . Künstliche Intelligenz . 77 (2): 321–357 . doi : 10.1016/0004-3702(94)00041-X .
  42. ^ Colmerauer, A. und Roussel, P., 1996. Die Entstehung von Prolog. In: Geschichte der Programmiersprachen---II (S. 331-367).
  43. ^ a b Warren, DH, Pereira, LM und Pereira, F., 1977. Prolog – die Sprache und ihre Implementierung im Vergleich zu Lisp. ACM SIGPLAN Notices, 12(8), S. 109–115.
  44. ^ Thagard, Paul (2005). Mind: Introduction to Cognitive Science . The MIT Press. S. 11. ISBN 9780262701099Diehttps://www.google.co.uk/books/edition/Mind_second_edition/gjcR1U2HT7kC?hl=en&gbpv=1&pg=PP11&printsec=frontcover
  45. ^ Stenning, Keith; van Lambalgen, Michiel (2008). Menschliches Denken und Kognitionswissenschaft . MIT-Presse . ISBN 978-0-262-19583-6Diehttps://philpapers.org/archive/STEHRA-5.pdf
  46. ^ Van Lambalgen, M. und Hamm, F., 2008. Die richtige Behandlung von Ereignissen. John Wiley & Sons. https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=3126320bb6e37ca3727fed404828b53fc56ff063
  47. ^ Reiter, R., 1991. Das Rahmenproblem im Situationskalkül: Eine einfache Lösung (manchmal) und ein Vollständigkeitsresultat für die Zielregression. Artificial and Mathematical Theory of Computation, 3.
  48. ^ Merritt, D., 2012. Building expert systems in Prolog. Springer Science & Business Media. https://ds.amu.edu.et/xmlui/bitstream/handle/123456789/4434/%28Text%20Book%29%20Building%20Expert%20Systems%20in%20Prolog.pdf?sequence=1&isAllowed=y
  49. ^ Sergot, MJ; Sadri, F.; Kowalski, RA; Kriwaczek, F.; Hammond, P; Cory, HT (1986). „The British Nationality Act as a logic program“ (PDF) . Communications of the ACM . 29 (5): 370–386 . doi : 10.1145/5689.5920 . S2CID 5665107 . 
  50. ^ Prakken, H.; Sartor, G. (Oktober 2015). „Recht und Logik: Eine Übersicht aus argumentationstheoretischer Perspektive“ (PDF) . Künstliche Intelligenz . 227 : 214–245 . doi : 10.1016/j.artint.2015.06.005 . S2CID 4261497 . 
  51. ^ Satoh, K., 2023. PROLEG: Praktisches juristisches Argumentationssystem. In: Prolog: Die nächsten 50 Jahre (S. 277–283). Cham: Springer Nature Schweiz.
  52. ^ ein b Körner, Philipp; Leuschel, Michael; Barbosa, João; Costa, Vítor Santos; Dahl, Verónica; Hermenegildo, Manuel V.; Morales, Jose F.; Wielemaker, Jan; Diaz, Daniel; Abreu, Salvador; Ciatto, Giovanni (November 2022). „Fünfzig Jahre Prolog und darüber hinaus“ . Theorie und Praxis der Logikprogrammierung . 22 (6): 776–858 . arXiv : 2201.10816 . doi : 10.1017/S1471068422000102 . ISSN 1471-0684 . 
  53. ^ a b Bonner, AJ und Kifer, M., Februar 1993. Transaktionslogische Programmierung. In ICLP (Vol. 93, S. 257-279).
  54. ^ Genesereth, M., 2023. Dynamische logische Programmierung. In: Prolog: Die nächsten 50 Jahre (S. 197–209). Cham: Springer Nature Schweiz.
  55. ^ Kowalski, R., Sadri, F., Calejo, M. und Dávila, J., 2023. Kombination von logischer und imperativer Programmierung in LPS. In: Prolog: Die nächsten 50 Jahre (S. 210–223). Cham: Springer Nature Schweiz.
  56. ^ Aho, AV und Ullman, JD, Januar 1979. Universalität von Datenabfragesprachen. In: Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages ​​(S. 110-119).
  57. ^ Maier, D., Tekle, KT, Kifer, M. und Warren, DS, 2018. Datalog: Konzepte, Geschichte und Ausblick. In: Deklarative Logikprogrammierung: Theorie, Systeme und Anwendungen (S. 3-100).
  58. ^ Eiter, T., Ianni, G. und Krennwallner, T., 2009. Answer Set Programming: A Primer. In Reasoning Web. Semantic Technologies for Information Systems: 5th International Summer School 2009, Brixen-Bressanone, Italien, 30. August - 4. September 2009, Tutorial Lectures (S. 40-110).
  59. ^ Arias, J.; Carro, M.; Salazar, E.; Marple, K.; Gupta, G. (2018). „Constraint Answer Set Programming without Grounding“ . Theory and Practice of Logic Programming . 18 ( 3–4 ): 337–354 . arXiv : 1804.11162 . doi : 10.1017/S1471068418000285 . S2CID 13754645 . 
  60. ^ Denecker, M.; Kakas, AC (Juli 2000). „Sonderausgabe: Abduktive Logikprogrammierung“ . Journal of Logic Programming . 44 ( 1–3 ): 1–4 . doi : 10.1016/S0743-1066(99)00078-3 .
  61. ^ Eshghi, K., 1988, August. Abduktive Planung mit Ereigniskalkül. In ICLP/SLP (S. 562-579).
  62. ^ Eshghi, K. und Kowalski, RA, Juni 1989. Abduktion im Vergleich zur Negation durch Fehlschlagen. In ICLP (Bd. 89, S. 234-255).
  63. ^ Nienhuys-Cheng, Shan-hwei; Wolf, Ronald de (1997). Grundlagen der induktiven logischen Programmierung . Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence. Berlin Heidelberg: Springer. S. 173. ISBN 978-3-540-62927-6Die
  64. ^ Flach, PA und Kakas, AC, 2000. Über die Beziehung zwischen abduktivem und induktivem Lernen. In: Abduktives Denken und Lernen (S. 1–33). Dordrecht: Springer Netherlands.
  65. ^ Cropper, A. und Dumančić, S., 2022. Induktive Logikprogrammierung mit 30: Eine neue Einführung. Journal of Artificial Intelligence Research, 74, S. 765-850.
  66. ^ Russell, S., 2019. Menschkompatibel: Künstliche Intelligenz und das Problem der Kontrolle. Penguin.
  67. ^ Shunichi Uchida und Kazuhiro Fuchi. Tagungsband des FGCS-Projektbewertungsworkshops . Institut für Computertechnologie der neuen Generation (ICOT). 1992.
  68. ^ Hewitt, Carl (27. April 2016). „Inkonsistenzrobustheit für Logikprogramme“ . Hal Archives. S.  21–26 . Abgerufen am 7. November 2016 .
  69. ^ Saraswat, VA und Rinard, M., Dezember 1989. Concurrent constraint programming. In Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages ​​(S. 232-245).
  70. ^ Chen, Weidong; Kifer, Michael; Warren, David S. (Februar 1993). „HiLog: Eine Grundlage für die Logikprogrammierung höherer Ordnung“ . Journal of Logic Programming . 15 (3): 187–230 . doi : 10.1016/0743-1066(93)90039-J .
  71. ^ Miller, D. A. und Nadathur, G., Juli 1986. Logikprogrammierung höherer Ordnung. In: Internationale Konferenz über Logikprogrammierung (S. 448–462). Berlin, Heidelberg: Springer Berlin Heidelberg.
  72. ^ Andreoli, Jean-Marc (1. Juni 1992). „Logische Programmierung mit fokussierenden Beweisen in der linearen Logik“. Journal of Logic and Computation . 2 (3): 297–347 . doi : 10.1093/logcom/2.3.297 .
  73. ^ Hodas, Joshua; Miller, Dale (1994). „Logische Programmierung in einem Fragment der intuitionistischen linearen Logik“ . Information and Computation . 110 (2): 327–365 . doi : 10.1006/inco.1994.1036 .
  74. ^ Kobayashi, Naoki; Yonezawa, Akinori (1994). Asynchrones Kommunikationsmodell basierend auf linearer Logik . US/Japan Workshop on Parallel Symbolic Computing. S.  279–294 . CiteSeerX 10.1.1.42.8749 . 
  75. ^ Miller, Dale (30. September 1996). „Forum: Eine Spezifikationslogik mit mehreren Schlussfolgerungen“ . Theoretical Computer Science . 165 (1): 201–232 . doi : 10.1016/0304-3975(96)00045-X .
  76. ^ Kifer, M. und Lausen, G., Juni 1989. F-Logik: Eine Sprache höherer Ordnung zum Schließen über Objekte, Vererbung und Schemata. In: Proceedings der internationalen ACM SIGMOD-Konferenz 1989 über Datenmanagement (S. 134–146).
  77. ^ de Moura, PJL, 2003. Entwurf einer objektorientierten logischen Programmiersprache (Doktorarbeit, Universidade da Beira Interior).
  78. ^ Yang, G. und Kifer, M., Juli 2000. FLORA: Implementierung eines effizienten DOOD-Systems mithilfe einer tabellierten Logik-Engine. In: Internationale Konferenz über Computerlogik (S. 1078–1093). Berlin, Heidelberg: Springer Berlin Heidelberg.

Quellen

Allgemeine Einführungen

Andere Quellen

Weiterführende Literatur