Prolog - Begriffe

Diskussion am Ende der Seite…

Beispiel

männlich(tobias).
männlich(alexander).
weiblich(susi).
weiblich(dagmar).
weiblich(mina).
kind_von(mina,tobias,susi).
 
tochter_von(X,Y):−
   frau(X),
   kind_von(X,Y,_).
 
tochter_von(X,Y):−
   frau(X),
   kind_von(X,_,Y).

Sprachelemente

Fakt

Eine grundlegende Aussage, die nicht weiter aufgespalten werden kann. Sie stellt eine Beziehung zwischen verschiedenen Entitäten her. Jedes Fakt wird mit einem Punkt abgeschlossen.

Beispiel:

buch('Herr der Ringe', 'J. R. R. Tolkien').

Einer intuitiven Semantik (einer von vielen möglichen) folgend ist die Aussage dieses Fakts die folgende: es gibt ein Buch mit dem Titel Herr der Ringe und dem Autor J. R. R. Tolkien.

Regel

Eine Regel hat die Form

L :- L1, L2, ..., Ln.

wobei die Li Literale sind und zusammen den Regelkörper darstellen. L wird Kopf der Regel genannt. Jede Regel wird mit einem Punkt abgeschlossen.

Semantik: Wenn alle Li wahr sind, dann ist auch L wahr.

Atom

Ein nicht teilbarer Term. Ein Atom ist eine Zeichenkette beginnend mit einem Kleinbuchstaben oder eine zwischen zwei Anführungsstrichen stehende Zeichenkette.

Beispiele:

auto, '/var/lib'

Atome stellen die Grundelemente der Faktenbasis dar.

Literal

Zeichenfolgen, welche die syntaktische Form von Fakten haben (ohne abschließenden Punkt). Literale sind (eventuell via ~ negierte) atomare Aussagen.

Beispiel:

auto(rot)

Klausel

ist die Generalisierung von Fakten und Regeln. Die Stelligkeit von Klauseln, also die Anzahl ihrer Argumente, wird metasprachlich hinter einem Slash angegeben.

Beispiel:

mann/1, frau/1, tochter_von/2 und kind_von/3

Prädikate sind Mengen von Klauseln, die hinsichtlich Ihrer Prädikatnamen und Stelligkeit übereinstimmen. Sowohl Fakten als auch Regeln definieren Prädikate. Listing 2.7 enthält das Prädikat tochter_von/2, das aus zwei Klauseln besteht.

Konstante

Eine Zahl oder ein Atom.

Term

Term ist die grundlegende Datenstruktur in Prolog. Terme werden aus ASCII Zeichen gebildet und sind in Prolog induktiv definiert:

1. Alle Atome und Variablen sind Terme.
2. Ist a ein n-stelliges Prädikat und sind t1, ..tn Terme, so ist auch a(t1, ..tn) ein Term.

Mit Termen können beliebig komplexe, verschachtelte Datenstrukturen beschrieben werden.

Funktor

Besteht aus dem Namen eines Literals oder einer Klausel und dessen Stelligkeit. Der Funktor zu f(p1, …, pn) lautet f/n

Struktur

Besteht aus einem Namen und mindestens einem Argument. Jedes Argument ist ein Term. Beispiel:

buch(titel('Herr der Ringe'), autor('J. R. R. Tolkien'))

(kein Punkt am Ende) Insbesondere kann in Prolog jede Liste als eine Struktur mit dem Punkt (.) als Funktor aufgefasst werden. So kann die Liste [a, b, c] auch folgendermaÿen dargestellt werden:

.(a, .(b, .(c, [])))

, wobei [] die leere Liste repräsentiert.

Prädikat

Repräsentiert eine Menge von Klauseln, deren Köpfe denselben Funktor haben (der Kopf eines Fakts besteht aus dem Fakt selbst).

Beispiel:

 auto(rot). 
 auto(blau). 
 auto(weiss) :- auto(keine_farbe).

sind Klauseln des einstelligen Prädikats auto.

Regeln

werden in der Form einer ’umgedrehten Implikation’ formuliert: Das Regelzeichen ’:-’ in einer Regel p(a):-q(b) liest sich als ”p(a) ist dann wahr, wenn q(b) wahr ist”. Der Regelkopf besteht aus einem Prädikat. Im Rumpf k¨onnen beliebig viele Strukturen logisch verkn¨upft werden, wobei das ’,’ der Konjunktion und das ’;’ der Disjunktion entspricht. Variablen beginnen Großbuchstaben. Zur Unterscheidung beginnen daher Pr¨adikate und Argumente mit Kleinbuchstaben. Die Variablen sind nicht typisiert und binden beliebige Entit¨aten. Sie erm¨oglichen die generische Beschreibung von Regeln und Anfragen.

Metaprädikate

treffen Aussagen über andere Prädikate und können neue Anfragen während der Ausführung formulieren.

Listen

Listen sind weitere Sprachkomponenten von Prolog. Sie können beliebige Elemente enthalten. Syntaktisch sind zwei verschiedene Schreibweisen möglich:

Kommaseparierte Darstellung

Liste mit den Elementen a,b,c. a ist der Kopf (Head), also das erste Element der Liste. [b,c] der Schwanz (Tail) der Liste und enthält die restlichen Elemente.

[a,b,c]

Alternative Darstellung

Der Head der Liste wird vom Tail durch das Pipe-Symbol '|’ getrennt. Head und Tail können wieder als Listen dargestellt werden. Die alternative Darstellung von Listen ermöglicht die Beschreibung der inneren Struktur einer Liste. Die folgenden Darstellungen beschreiben die selbe Liste a,b,c.

[a|[b, c]]
[a|[b|[c]]]
[a,b|[c]]

Die leere Liste wird mit '[]' dargestellt.

Konsultieren

Das Schreiben/Einbringen von Prolog-Programmen in eine Faktenbasis, wobei die Programme als Textdatei vorliegen.

Unifikation

Bezeichnet das Gleichsetzen zweier Terme durch konsistente Ersetzung von Variablen durch andere geeignete Terme. Wenn eine Variable durch einen Term substituiert wurde, ist sie gebunden. Zwei ungebundene Variablen unifizieren immer. Zwei Atome unifizieren nur, wenn sie identisch sind. Die Unifation zweier Terme scheitert, wenn sie syntaktisch nicht gleich sind oder wenn die Argumentwerte in den gleichen Argumentpositionen beider Terme nicht unifizieren.

Beispiel: die Terme schwester(anna, petra) und schwester(anna, X) können unifiziert werden, indem X durch petra ersetzt wird.

Überarbeitete Version des Originals. Quelle: [Facb]

Substitution

TODO

Backtracking

Backtracking ist das Zurücksetzen des Beweisganges an den letzten Verzweigungspunkt des Beweisbaumes, um eine weitere Alternative zu versuchen. Bei diesem Schritt werden allfällige Variablenbindungen bis zum Verzweigungspunkt zurück aufgelöst.

Diskussion

Logisch vs Komisch

Wenn ich mich auf “Logik beziehe, meine ich meistens das Skript zur Logik I VL von Koepke. Für uns interessant sind die Definitionen in den Abschnitten 4 und 5. Ich probiere mal ein Beispiel.

?- r(A,f(x)).
  • r(A,f(x)) ist eine Formel
  • f(x), A sind Terme
  • f ist ein Funktionssymbol mit Stelligkeit 1
  • r ist ein Relationssymbol mit Stelligkeit 2
  • x ist wahlweise ein Konstantensymbol oder ein Funktionssymbol mit Stelligkeit 0
  • A ist eine Variable
  • ?- ist was besonderes :-)

?- gehört (zunächst einmal) nicht zur Sprache. Intuitiv heißt es “Ist die (folgende) Formel in meiner Theorie ableitbar?”

Es sei an dieser Stelle noch mal darauf hingewiesen - Günter erwähnte es bereits - Das Formeln und Terme, insb. syntatktisch, NICHT das selbe sind. So sind insb. die Mengen der Funktions- und der Relationssymbole disjunkt. In Prolog schmeißt man das schonmal durcheinander.

Funktor vs Funktionssymbol

Synonym? Wenn nicht, kann jemand den Unterschied klären?

Konstantensymbol

Wird in vielen Logikbüchern einfach als Funktionssymbol mit Stelligkeit 0 betrachtet. Ich denke das macht Sinn. Koepke macht das nicht. Ist aber im Prinzip auch egal.

Atom vs atomare Formel vs relationale Formeln vs Gleichungen

  • In Prolog-Sprech bezeichnet atom ein Konstantensymbol. Siehe z.b. build-in atom/1.
  • In der Logik nennt man Formeln, die keine Junktoren enthalten atomar.
  • Koepke nennt Formeln, die aus einem einzelnen Relationssymbol gebildet werden auch relationale Formeln
  • Es spricht vermutlich nichts dagegen, semantisch Gleichheit als Relation und damit auch syntaktisch eine Gleichung als relationale Formel aufzufassen. Oder übersehe ich jetzt was? Hab das jetzt nicht so 100% zu ende gedacht…

Prädikat vs Relation

Kann man synonym behandeln, denke ich.

Last modified: 2014/08/17 03:22
*