I. Grundbegriffe

Variablenfreie Fakten
Variablenfreie Anfragen
Variablen, Substitutionen und Antworten
Einige PROLOG-Systemprädikate
Existentielle Anfragen und universelle Fakten
Konjunktive Anfragen und gemeinsame Variablen
Annahme der Eindeutigkeit der Namen
Funktionssymbole und zusammengesetzte Terme
Regeln

I. Grundbegriffe

Variablenfreie Fakten
Variablenfreie Anfragen
Variablen, Substitutionen und Antworten
Einige PROLOG-Systemprädikate
Existentielle Anfragen und universelle Fakten
Konjunktive Anfragen und gemeinsame Variablen
Annahme der Eindeutigkeit der Namen
Funktionssymbole und zusammengesetzte Terme
Regeln

1. Variablenfreie Fakten

Die einfachsten PROLOG-Programme sind relationalen Datenbanken ähnlich. Sie bestehen aus endlichen (geordneten) Mengen von Fakten, die mit einem . abgeschlossen werden.

1


land(deutschland).
land(daenemark).
land(frankreich).
land(griechenland).
land(grossbritannien).
land(italien).
land(oesterreich).
land(portugal).
land(schweiz).
land(spanien).
 
hauptstadt(kopenhagen, daenemark).
hauptstadt(berlin, deutschland).
hauptstadt(paris, frankreich).
hauptstadt(athen, griechenland).
hauptstadt(london, grossbritannien).
hauptstadt(rom, italien).
hauptstadt(wien, oesterreich).
hauptstadt(lissabon, portugal).
hauptstadt(bern, schweiz).
hauptstadt(madrid, spanien).

Ein Faktum besteht aus einem Relationssymbol wie land oder hauptstadt gefolgt von einer eingeklammerten Liste von Termen wie daenemark oder kopenhagen. Nach jedem Faktum kommt ein Punkt. Relationssymbole und Terme fangen mit Kleinbuchstaben an.

Das PROLOG-Faktum

hauptstadt(kopenhagen, daenemark)

in einem PROLOG-Programm bedeutet, daß die Beziehung hauptstadt zwischen kopenhagen und daenemark gilt. Dieses Faktum hat also die gleiche Bedeutung wie das Tupel

(kopenhagen, daenemark)

in der Relation HAUPTSTADT einer relationalen Datenbank.

Das Relationssymbol land hat die Stelligkeit 1. Das Relationssymbol hauptstadt hat die Stelligkeit 2. Die Stelligkeit ist Teil eines Relationssymbols. Relationssymbole wie z.B. symbol mit Stelligkeit 0 sind möglich. PROLOG läßt die Verwendung des gleichen Symbols mit verschiedenen Stelligkeiten zu

wie im folgenden Programm:

2


hauptstadt(kopenhagen, daenemark).
hauptstadt(berlin, deutschland).
hauptstadt(paris, frankreich).
hauptstadt(athen, griechenland).
 
hauptstadt(kopenhagen).
hauptstadt(berlin).
hauptstadt(paris).
hauptstadt(athen).

Um die Relationssymbole hauptstadt mit Stelligkeit 1 und 2 im Programmm P₂ voneinander zu unterscheiden, schreibt man hauptstadt/1 bzw. hauptstadt/2.

zum Seitenanfang

Variablenfreie Fakten

PROLOG-Programme:

sind relationalen Datenbanken ähnlich
bestehen aus endlichen (geordneten) Mengen von Fakten
werden mit einem . abgeschlossen

1


land(deutschland).
land(daenemark).
land(frankreich).

hauptstadt(kopenhagen, daenemark).
hauptstadt(berlin, deutschland).
hauptstadt(paris, frankreich).

2. Variablenfreie Anfragen

Die atomaren Anfragen unterscheiden sich syntaktisch nicht von Fakten. Der Kontext bestimmt, ob es sich um eine Anfrage oder um ein Faktum handelt. Kommt ein Faktum F nach dem Prompt :- vor, dann handelt es sich um eine (atomare) Anfrage.

Das folgende Beispiel bezieht sich auf das Programm P₁:


:- land(griechenland).
yes.
:- land(norwegen).
no (more) solution.
:-

Komplexere Anfragen ergeben sich durch Negation von atomaren Anfragen, wie im folgenden Beispiel, das sich auf das Programm P₁ bezieht:


:- \+ land(griechenland).
no (more) solution.
:- \+ land(norwegen).
yes.
:-

In PROLOG wird die Negation \+ oder not geschrieben. Die Bezeichnung Literal wird als Oberbegriff für eine atomare Anfrage oder die Negation einer atomaren Anfrage verwendet.

Prolog antwortet auf eine Anfrage mit Ja oder Nein. Man kann eine atomare Anfrage also als Aufruf einer booleschen Prozedur auffassen, deren Name das Relationssymbol der Anfrage ist. Die Definition dieser booleschen Prozedur besteht dann aus der Liste aller Fakten mit diesem Relationssymbol und passender Stelligkeit (wir werden später sehen, daß außer Fakten auch sogenannte Regeln erlaubt sind). Eine boolesche Prozedur wird oft auch Prädikat genannt.

Die ersten zehn Fakten im Programm P₁ definieren bei dieser Sichtweise ein einstelliges Prädikat (eine einstellige boolesche Prozedur) mit dem Namen land/1, das durch die obigen Anfragen aufgerufen wird.

zum Seitenanfang

Variablenfreie Anfragen

Die atomaren Anfragen unterscheiden sich syntaktisch nicht von Fakten. Der Kontext bestimmt, ob es sich um eine Anfrage oder um ein Faktum handelt. Kommt ein Faktum F nach dem Prompt :- vor, dann handelt es sich um eine (atomare) Anfrage.

Das folgende Beispiel bezieht sich auf das Programm P₁:


:- land(griechenland).
yes.
:- land(norwegen). 
no (more) solution. 
:-

3. Variablen, Substitutionen und Antworten

PROLOG-Variablen sind logische Variable. Es gibt in PROLOG keine explizite Wertzuweisung, im Gegensatz zu imperativen Programmiersprachen wie Pascal oder C. Variablen, die in einer Anfrage vorkommen, werden so gebunden, daß sich eine Formel ergibt, die aus dem Programm folgt. In PROLOG fangen Variablen mit Großbuchstaben an.

Das folgende Beispiel einer Sitzung bezüglich des Programms P₁ veranschaulicht die Bedeutung von Variablen in Anfragen:


:- land(X).
X = daenemark More? (;) ;

X = deutschland More? (;) ;

X = frankreich More? (;)

:- hauptstadt(kopenhagen, Y).
Y = daenemark
yes.
:- hauptstadt(Y, indien).
no (more) solution.
:-

Wird ; als Antwort zum Prompt More? (;) gegeben, so wird eine weitere Antwort geliefert, wenn noch eine weitere berechnet werden kann. Eine Anfrage kann also entweder keine, oder nur eine oder mehrere Antworten erhalten.

zum Seitenanfang

Variablen, Substitutionen und Antworten

PROLOG-Variablen sind logische Variable.
Es gibt in PROLOG keine explizite Wertzuweisung
In PROLOG fangen Variablen mit Großbuchstaben an.

Ein Beispiel bezüglich des Programms P₁ :


:- hauptstadt(kopenhagen, Y).
Y = daenemark
yes.
:- hauptstadt(Y, indien).
no (more) solution.
:-

4. Einige PROLOG-Systemprädikate

=/2: erfolgreich, wenn die beiden Argumente (durch Variablenbindung) gleich gemacht werden können. Infix notiert.
\=/2: entspricht der Negation \+ von =.
var/1: erfolgreich, wenn der Wert (und nicht der Typ!) des Arguments eine ungebundene Variable ist.
nonvar/1: erfolgreich, wenn der Wert (und nicht der Typ!) des Arguments keine Variable ist.
atom/1: erfolgreich, wenn der Wert (und nicht der Typ!) des Arguments eine Konstante, ein Relationssymbol oder ein Funktionssymbol -- auch PROLOG-Atom genannt -- ist.
Vorsicht: PROLOG-Atome sind keine Atome (d.h., atomare Formeln) im Sinne der mathematischen Logik! In der Logik würde man eher die Bezeichnung "Symbole" dafür verwenden.
integer/1: erfolgreich, wenn der Wert (und nicht der Typ!) des Arguments eine ganze Zahl ist. Ganze Zahlen sind keine PROLOG-Atome.
atomic/1: entspricht der Disjunktion von atom/1 und integer/1.
==/2: erfolgreich, wenn die Werte beider Argumente syntaktisch identisch sind.


:- a = a.
yes.
:- a = b.
no (more) solution.
:- a = X.
X = a
yes.
:- X = b.
X = b
yes.
:- a \= b.
yes.
:- X \= a.
no (more) solution.
:- land(daenemark) = land(Country).
Country = daenemark
yes.

:- var(Vv).
Vv = Vv
yes.
:- var(vV).
no (more) solution.
:- hauptstadt(kopenhagen,X), var(X).
no (more) solution.
:- nonvar(Vv).
no (more) solution.
:- nonvar(vV).
yes.

:- atom(a).
yes.
:- atom(A).
no (more) solution.
:- atom(land(daenemark)).
no (more) solution.
:- atom(land).
yes.
:- atom(daenemark).
yes.
:- atom(12).
no (more) solution.

:- integer(12).
yes.
:- integer(daenemark).
no (more) solution.

:- hauptstadt(kopenhagen,X), X == daenemark.
yes.
:- X == daenemark.
no (more) solution.
:-

zum Seitenanfang

Einige PROLOG-Systemprädikate

=/2: erfolgreich, wenn die beiden Argumente (durch Variablenbindung) gleich gemacht werden können. Infix notiert.
\=/2: entspricht der Negation \+ von =.
var/1: erfolgreich, wenn der Wert (und nicht der Typ!) des Arguments eine ungebundene Variable ist.
nonvar/1: erfolgreich, wenn der Wert (und nicht der Typ!) des Arguments keine Variable ist.
integer/1: erfolgreich, wenn der Wert (und nicht der Typ!) des Arguments eine ganze Zahl ist. Ganze Zahlen sind keine PROLOG-Atome.
atomic/1: entspricht der Disjunktion von atom/1 und integer/1.
==/2: erfolgreich, wenn die Werte beider Argumente syntaktisch identisch sind.

5. Existentielle Anfragen und universelle Fakten

In einer Anfrage gilt eine Variable als (implizit) existentiell quantifiziert. Die Anfrage

:- land(X).

bedeutet also:

Was sind die Bindungen für X, so daß land(X) gilt?

3


land(daenemark).
land(deutschland).

hauptstadt(kopenhagen, daenemark).
hauptstadt(berlin, deutschland).

Die folgende Sitzung bezieht sich auf das Programm P₃:


:- land(X).
X = daenemark More? (;) ;

X = deutschland
yes.
:-

In einem Programm gilt eine Variable als (implizit) universell quantifiziert. In einem Programm bedeutet also das Faktum

land(X).

Für alle Werte von X gilt land(X)

4


land(daenemark).
land(deutschland).
land(X).

hauptstadt(kopenhagen, daenemark).
hauptstadt(berlin, deutschland).

Die folgende Sitzung bezieht sich auf das Programm P₄:


:- land(indien).
yes.
:- land(daenemark).
yes.
:- land(Z).
Z = daenemark More? (;) ;

Z = deutschland More? (;) ;

Z = Z
yes.
:-

zum Seitenanfang

Existentielle Anfragen und universelle Fakten

In einer Anfrage gilt eine Variable als (implizit) existentiell quantifiziert. Die Anfrage

:- land(X).

bedeutet also:

Was sind die Bindungen für X, so daß land(X)gilt?

In einem Programm gilt eine Variable als (implizit) universell quantifiziert. In einem Programm bedeutet also das Faktum

land(X).

Für alle Werte von X gilt land(X)

6. Konjunktive Anfragen und gemeinsame Variablen

In PROLOG wird die Konjunktion durch das Komma dargestellt. Eine konjunktive Anfrage ist eine Konjunktion von atomaren Anfragen oder negierten atomaren Anfragen (also von Literalen).

Alle Vorkommen der gleichen Variablen in einer konjunktiven Anfrage erhalten die gleiche Bindung.

Kommt eine Variable nur ein Mal in einer Anfrage vor und ist ihr Wert uninteressant, so kann sie als anonyme Variable mit _ dargestellt werden. Im Gegensatz zu regulären Variablen stehen mehrfache Vorkommen von _ in der gleichen Anfrage für verschiedenen Variablen.

5


hauptstadt(berlin, deutschland).
hauptstadt(paris, frankreich).
hauptstadt(wien, oesterreich).

sprache(deutsch, deutschland).
sprache(deutsch, oesterreich).
sprache(franzoesisch, frankreich).

Die folgende Sitzung bezieht sich auf P₅.


:- sprache(deutsch, Land), hauptstadt(Stadt,
Land).
Stadt = berlin
Land = deutschland More? (;) ;

Stadt = wien
Land = oesterreich
yes.

:- sprache(Sprache, Land), hauptstadt(Stadt, Land).
Sprache = deutsch
Stadt = berlin
Land = deutschland More? (;) ;

Sprache = deutsch
Stadt = wien
Land = oesterreich More? (;) ;

Sprache = franzoesisch
Stadt = paris
Land = frankreich
yes.

:- sprache(_, Land), hauptstadt(Stadt, _).
Land = deutschland
Stadt = berlin More? (;) ;

Land = deutschland
Stadt = paris More? (;) ;

Land = deutschland
Stadt = wien More? (;) ;

Land = oesterreich
Stadt = berlin More? (;)
yes.
:-

zum Seitenanfang

Konjunktive Anfragen und gemeinsame Variablen

In PROLOG wird die Konjunktion durch das Komma dargestellt. Eine konjunktive Anfrage ist eine Konjunktion von atomaren Anfragen oder negierten atomaren Anfragen (also von Literalen).

Alle Vorkommen der gleichen Variablen in einer konjunktiven Anfrage erhalten die gleiche Bindung.

Kommt eine Variable nur ein Mal in einer Anfrage vor und ist ihr Wert uninteressant, so kann sie als anonyme Variable mit _ dargestellt werden. Im Gegensatz zu regulären Variablen stehen mehrfache Vorkommen von _ in der gleichen Anfrage für verschiedenen Variablen.

7. Annahme der Eindeutigkeit der Namen

Ein Term heißt grund oder variablenfrei oder geschlossen, wenn in diesem Term keine Variable vorkommt.

Falls die Werte von zwei Termen T1 und T2 verschiedene Grundterme sind, so sind T1 und T2 für PROLOG ungleich, d.h. die Anfrage T1 = T2 scheitert immer.

Diese Annahme wird Annahme der Eindeutigkeit der Namen (unique name assumption) genannt.

Damit weicht PROLOG sowohl von der mathematischen Logik als auch von der funktionalen Programmierung ab.


:- a = b.
no (more) solution.
:- X = f(a,b), Y = f(a,b), X = Y.
yes.
:-

zum Seitenanfang

Annahme der Eindeutigkeit der Namen

Ein Term heißt grund oder variablenfrei oder geschlossen, wenn in diesem Term keine Variable vorkommt.

Falls die Werte von zwei Termen T1 und T2 verschiedene Grundterme sind, so sind T1 und T2 für PROLOG ungleich, d.h. die Anfrage T1 = T2 scheitert immer.

Diese Annahme wird Annahme der Eindeutigkeit der Namen (unique name assumption) genannt.

8. Funktionssymbole und zusammengesetzte Terme

Funktionssymbole, die keine Konstanten sind, d.h. deren Stelligkeit größer-gleich 1 ist, dienen in Prolog zur Bildung zusammengesetzter Terme. Im Gegensatz zur mathematischen Logik und zur funktionalen Programmierung werden die Funktionssymbole in PROLOG nicht ausgewertet. Sie sind Termkonstruktoren.

6


telefon( name(marianne,fischer), privat(8821921), buero(557932) ).
telefon( name(hans,mueller), privat(20812), buero(423122) ).
telefon( name(peter,klein), privat(344765), buero(9712004) ).

Die folgende Sitzung bezieht sich auf P₆.


:- telefon(A, B, C).
A = name(marianne, fischer)
B = privat(8821921)
C = buero(557932) More? (;) ;

A = name(hans, mueller)
B = privat(20812)
C = buero(423122) More? (;) ;

A = name(peter, klein)
B = privat(344765)
C = buero(9712004)
yes.
:- telefon(name(_, mueller), _, buero(Nr)).
Nr = 423122 More? (;) ;

no (more) solution.
:-

Der Listenkonstruktor von PROLOG ist ., die leere Liste wird [] dargestellt.

Der Lesbarkeit halber können in PROLOG Listen auch wie folgt dargestellt werden:


:- .(a, []) = [a].
yes.
:- X = .(a, []).
X = [a]
yes.
:- Y = .(a, .(b, .(c, []))), Z = [a, b, c], Y = Z.
Y = [a, b, c]
Z = [a, b, c]
yes. :-

Die leere Liste [] ist eine logische Konstante und ein PROLOG-Atom.


:- atom([]).
yes.
:-

Die Notation [Kopf | Rumpf] liefert Selektoren für Kopf und Rumpf einer Liste.


:- [K | R] = [a, b, c].
K = a
R = [b, c]
yes.
:- [K | R] = [].
no (more) solution.
:- [K | R] = [a].
K = a
R = []
yes.
:-

zum Seitenanfang

Funktionssymbole und zusammengesetzte Terme

Funktionssymbole, die keine Konstanten sind, d.h. deren Stelligkeit größer-gleich 1 ist, dienen in Prolog zur Bildung zusammengesetzter Terme. Im Gegensatz zur mathematischen Logik und zur funktionalen Programmierung werden die Funktionssymbole in PROLOG nicht ausgewertet. Sie sind Termkonstruktoren.
Der Listenkonstruktor von PROLOG ist ., die leere Liste wird [] dargestellt.
Die leere Liste [] ist eine logische Konstante und ein PROLOG-Atom.
Die Notation [Kopf | Rumpf] liefert Selektoren für Kopf und Rumpf einer Liste.

9. Regeln

PROLOG-Regeln sind Ausdrücke der Gestalt

Kopf Rumpf

wobei Kopf ein Atom ist und Rumpf eine Anfrage ist, die mit :- anfängt und mit . endet. Das Zeichen :- steht für ein (umgekehrtes) Implikationszeichen <==. Die Regel steht für ihren Allabschluß.

7


telefon(name(marianne,fischer), privat(8821921), buero(557932)).
telefon(name(hans,mueller), privat(20812), buero(423122)).
telefon(name(peter,klein), privat(344765), buero(9712004)).

privat_telefon(Vorname,Nr) :- telefon(name(Vorname,_), privat(Nr), _).

Die folgende Sitzung bezieht sich auf P₇.


:- privat_telefon(marianne, T).
T = 8821921 More? (;) ;

no (more) solution.
:-

PROLOG-Regeln sind Datanbanksichten (views) ähnlich.

8


kante(a, b).
kante(b, c1).
kante(b, c2).
kante(b, c3).
kante(c1, d1).
kante(d1, e1).
kante(c2, d2).

verbunden(X,Y) :- kante(X,Y).
verbunden(X,Y) :- kante(X,Z), kante(Z,Y).
verbunden(X,Y) :- kante(X,Z1), kante(Z1,Z2), kante(Z2,Y).
verbunden(X,Y) :- kante(X,Z1), kante(Z1,Z2), kante(Z2,Z3),
kante(Z3,Y).

Die folgende Sitzung bezieht sich auf P₈.


:- verbunden(a, d2).
a = c2 More? (;) ;

a = b More? (;) ;

a = a More? (;) ;

no (more) solution.
:- verbunden(a, Y).
Y = b More? (;) ;

Y = c1 More? (;) ;

Y = c2 More? (;) ;

Y = c3 More? (;) ;

Y = d1 More? (;) ;

Y = d2 More? (;) ;

Y = e1 More? (;) ;

no (more) solution.
:- verbunden(d1, d2).
no (more) solution.
:-

Eine PROLOG-Regel ist auch ein PROLOG-Term, dessen zweistellige Funktionssymbol :- ist.


:- R = (p(X) :- q(X), r(X,Y)).
R = p(X) :- q(X), r(X,Y)
X = X
Y = Y
yes.
:-

Ein PROLOG-Programm ist eine endliche (geordnete) Menge von Fakten und Regeln. Die Bezeichnung Programmklausel oder einfach Klausel wird als Oberbegriff für ein Faktum oder eine Regel verwendet.

Ein PROLOG-Programm kann als intentionale Spezifikation einer relationalen Datenbank angesehen werden. Im Gegensatz zu den meisten relationalen Datenbanken läßt PROLOG jedoch zusammengesetzte Terme zu.

zum Seitenanfang

Regeln

PROLOG-Regeln sind Ausdrücke der Gestalt
Kopf Rumpf
wobei Kopf ein Atom ist und Rumpf eine Anfrage ist, die mit :- anfängt und mit . endet. Das Zeichen :- steht für ein (umgekehrtes) Implikationszeichen <==. Die Regel steht für ihren Allabschluß.
Eine PROLOG-Regel ist auch ein PROLOG-Term, dessen zweistellige Funktionssymbol :- ist.
Ein PROLOG-Programm ist eine endliche (geordnete) Menge von Fakten und Regeln. Die Bezeichnung Programmklausel oder einfach Klausel wird als Oberbegriff für ein Faktum oder eine Regel verwendet.
Ein PROLOG-Programm kann als intentionale Spezifikation einer relationalen Datenbank angesehen werden. Im Gegensatz zu den meisten relationalen Datenbanken läßt PROLOG jedoch zusammengesetzte Terme zu.