Hausaufgaben Logische Programmierung

Hausaufgaben Logische Programmierung
Elmar Eder
9. Juni 2016
Die Aufgaben sind auf dem Abgabesystem von Dominik Kaaser unter der Internetadresse https://prolog.cosy.sbg.ac.at/ bis zu dem dort angegebenen Termin abzugeben. Bitte alle Programme/Texte mit Return- oder Entertaste beenden!
Alle Aufgaben, bei denen nichts gegenteiliges vermerkt ist, sind selbständig in Teams
von zwei Studenten zu lösen. Am Anfang der von Ihnen fertiggestellten Lösung der Aufgabe müssen die Namen (Familienname Vorname) aller beteiligter Studenten angeführt
sein, im Fall eines Prolog-Programms als Kommentar (mit Prozentzeichen am Anfang
der Zeile). Einigen Sie sich bitte mit Ihrem Teampartner, wer von Ihnen die Datei auf
dem Abgabesystem abgibt!
Wenn bei einer Aufgabe ein Prolog-Programm und dazu ein oder mehr Anfragen an
Prolog zu erstellen sind, dann schreiben Sie bitte die Anfragen in einem Kommentar ans
Ende der Datei, etwa so:
% ?- vater(X,hans).
% ?- tochter(X,anna), tochter(Y,anna), aelter(X,Y).
Alle Programme sind vorher zu testen. Sie müssen unter Prolog lauffähig sein.
Als Dateinamen für Prolog-Programme wählen Sie – soweit nicht anders angegeben –
hN N .pl, wobei N N die zweistellige Nummer der Aufgabe ist (z.B. h07.pl bei Aufgabe
7); entsprechend hN N .txt für reine Text-Dateien! Zeichnungen erstellen Sie bitte als
pdf-Datei hN N .pdf oder (in einem Editor mit Monospace/fixed-width Font) als ASCIIGrafik! Als Alternative akzeptiere ich auch JPEG-Dateien (hN N .jpg).
Pdf-Dateien, die Grafiken enthalten, können Sie z.B. mit (pdf)LATEX und dem Paket
pgf/tikz oder pstricks erstellen. Auch die gängigen Zeichenprogramme können nach
pdf exportieren. Wenn Sie eine klare Handschrift haben, können Sie anstattdessen Ihre
Lösung händisch auf Papier erstellen und dann einscannen oder bei guten Lichtverhältnissen fotografieren. Stellen Sie in diesem Fall aber sicher, dass das Resultat gut lesbar
ist und z.B. deutlich erkennbar ist, ob ein Buchstabe ein Groß- oder Kleinbuchstabe ist
(z.B. x oder X)!
Hier ein fiktives Beispiel (Diese Aufgabe nicht abgeben!): Sie lösen die folgende fiktive
Aufgabe null:
1
Aufgabe 0 Übersetzen Sie die Aussagen
• Max mag Hans.
• Hans mag Max.
• Hans mag Eva.
in ein Prolog-Programm und fragen Sie Prolog danach, wen Hans mag! Zeichnen Sie einen Graphen, der die Relation des Mögens darstellt!
Sie können dann ein Programm h00.pl schreiben, das als Kommentare die Anfrage und
eine ASCII-Grafik enthält:
% Erika Mustermann, Max Mustermann
% mag(X,Y)
Person
mag(max,hans).
%
mag(hans,max).
%
mag(hans,eva).
%
X mag Person Y
Max mag Hans.
Hans mag Max.
Hans mag Eva.
% ?- mag(hans,Person).
%
%
%
%
+-------+
|
|
v
|
Max --> Hans --> Eva
Oder Sie erstellen h00.pl nur mit Programm und Anfrage:
% Erika Mustermann, Max Mustermann
% mag(X,Y)
Person
mag(max,hans).
%
mag(hans,max).
%
mag(hans,eva).
%
X mag Person Y
Max mag Hans.
Hans mag Max.
Hans mag Eva.
% ?- mag(hans,Person).
und dazu eine pdf-Grafik-Datei h00.pdf
Max
Hans
Eva
und laden beide Dateien auf das Abgabesystem hoch.
Auch wenn Sie von einer Aufgabe nur Teile gelöst haben, geben Sie bitte Ihre Lösung
ab! Einige Aufgaben bestehen aus mehreren Teilen, die aufeinander aufbauen. Auch
teilweise Lösungen können positiv in Ihre Bewertung einfließen.
2
Vorab etwas Terminologie und Syntax zu Prolog:
• Unter einer Klausel eines Programms versteht man ein Fakt oder eine Regel dieses
Programms.
• Jede Klausel muss mit einem Punkt „.“ enden.
• Eine Regel hat die Form Kopf :-Rumpf. , wobei der Rumpf die Form
Ziel1 ,. . . ,Zieln hat. Eine Regel hat also die Form Kopf :-Ziel1 ,. . . ,Zieln . .
• Anstatt vom „2-stelligen Prädikat kind“ zu sprechen, sagt man im Prolog-Jargon
kurz kind/2, d.h. man hängt an den Namen des Prädikats einen Schrägstrich und
dann die Stelligkeit an.
Aufgabe 1 Ich hoffe, Sie haben alle einen Partner für Ihr Zweierteam gefunden. Damit
ich weiß, wer mit wem ein Zweierteam bildet, erstellen Sie bitte in einer Datei mit dem
Dateinamen h01.pl ein Prolog-Programm mit einer Zeile
partner(Ihr_Name, Name_Ihres_Partners ).
und, falls für Sie wichtig ist, in welcher Gruppe Sie sind, einer Leerzeile gefolgt von einer
weiteren Zeile
gruppenwunsch(Ihr_Name, Gruppennummer, Grund ).
und testen Sie Ihr Programm (siehe unten) und geben Sie diese Datei auf dem Abgabesystem ab! Dabei schließen Sie bitte Ihren Namen, den Ihres Partners und den Grund
in einfache Anführungsstriche ein! Der Grund kann auch das leere Prologatom ’’ (zwei
einfache Anführungszeichen) sein. Schreiben Sie bitte Ihren Namen, indem Sie erst den
Familiennamen, dann einen Zwischenraum und dann Ihren Vornamen schreiben. Legen
Sie dabei die Schreibung zugrunde, mit der Sie auf PLUS Online gemeldet sind, wobei
Sie aber bitte :a statt ä, :o statt ö, :u statt ü und :s statt ß schreiben! Es gibt nämlich
verschiedene Kodierungssysteme und der Text ist nachher nicht lesbar, wenn jeder seine
eigene Kodierung verwendet.
Beispiel: Nehmen wir an, Sie heißen Hans-Jürgen Peter Höß und Ihre Teampartnerin
heißt Bärbel Kräßig. Sie wollen von 13 bis 15 Uhr die Vorlesung über Kryptographie
besuchen und wollen daher in Gruppe 2 zugeordnet sein. Dann geben Sie bitte eine
Datei h01.pl mit folgendem Inhalt auf dem Abgabesystem ab!
partner(’H:o:s Hans-J:urgen Peter’, ’Kr:a:sig B:arbel’).
gruppenwunsch(’H:o:s Hans-J:urgen Peter’, 2, ’13-15h VO Kryptographie’).
Wenn für Sie sowohl der Termin der ersten als auch der zweiten Gruppe möglich ist,
geben Sie nur eine Zeile, die mit partner( beginnt, ab!
Zum Testen des Programms laden Sie es bitte in Prolog und stellen die Anfragen
?- partner(Ich, Mein_Partner).
?- gruppenwunsch(Ich, Gruppe, Grund).
3
Den Test des Programms nicht abgeben! Bei dieser Aufgabe wird sich Ihre Datei natürlich
von der Ihres Partners unterscheiden. Also bitte jeder für sich bearbeiten!
Abzugeben: Programm h01.pl
Aufgabe 2 Laden Sie die Datei verwandtschaft.pl und fragen Sie Prolog:
(a) Wessen Kind ist Max?
(b) Wer ist Kind von Anna?
(c) Wer ist Kind von wem?
(d) Wer ist Kind von sich selbst?
(e) Welche zwei Personen sind die Eltern (Vater bzw. Mutter) von welcher dritten
Person?
(f) Wer ist Grußmutter von Eva?
Abzugeben: Datei h02.txt mit 6 Anfragen (darüber Ihre Namen!)
Aufgabe 3 Drücken Sie die folgenden Aussagen über verschiedene Tiergruppen und
ihre bevorzugten Fortbewegungsmethoden in Form eines Prologprogramms aus:
(a) Löwe, Rind, Wal und Fledermaus sind Säugetiere.
(b) Star, Strauß und Wasseramsel sind Vögel.
(c) Löwe, Rind und Strauß gehen gerne.
(d) Forelle, Wasseramsel und Wal schwimmen gerne.
(e) Fledermaus, Star und Wasseramsel fliegen gerne.
Fragen Sie Prolog
(a) nach einem Säugetier, das gerne schwimmt
(b) nach einem Vogel, der gerne fliegt
(c) nach einem Vogel, der gerne fliegt und gerne schwimmt
Schreiben Sie diese Anfragen als Kommentare in das Programm hinein!
Abzugeben: Programm mit Anfragen als Kommentare
Aufgabe 4 Definieren Sie drei Prädikate planet/1, rund/1 und eckig/1 durch Fakten,
die die folgenden Aussagen in Prolog-Syntax ausdrücken!
• Die Erde ist ein Planet.
• Der Mars ist ein Planet.
• Die Erde ist rund.
• Der Mars ist rund.
• Der Würfel ist eckig.
Definieren Sie weiter zwei nullstellige Prädikate es_gibt_einen_eckigen_Planeten/0
und es_gibt_einen_runden_Planeten/0 jeweils durch eine Regel unter Bezugnahme
auf die oben definierten Prädikate! Damit sollte Prolog auf folgende Anfragen mit folgenden Antworten reagieren:
?- es_gibt_einen_runden_Planeten.
true .
?- es_gibt_einen_eckigen_Planeten.
false.
4
In Prolog lässt man bei nullstelligen Prädikaten die Klammern weg.
Abzugeben: Programm
Aufgabe 5 Überlegen Sie sich zunächst ohne Verwendung des Computers, welche der
folgenden Zeichenfolgen Prolog-Atome, welche Prolog-Variablen sind!
(a) abc
(b) aBC
(c) 1abc
(d) -1234
(e) Abc
(f) 123.7
(g) -12.34e-23
(h) a_B_c
(i) A1
(j) ab-cd
(k) a1
(l) 2+3
(m) f(g(X,a),h(3,Y,b))
(n) Heinz Schmidt
(o) ’Heinz Schmidt’
Starten Sie nun am Computer Ihr Prolog-System! Für einen Term T liefert eine Anfrage
?- atom(T ). die Antwort yes oder true, wenn T ein Prolog-Atom ist. Wenn T kein
gültiger Prolog-Term ist, sollte eine Fehlermeldung produziert werden. Probieren Sie das
mit Aufrufen wie
?- atom(abc).
Entsprechend wie atom/1 gibt es in Prolog noch andere Typ-Test-Prädikate, z.B. var/1,
number/1, integer/1, float/1, compound/1 (testet, ob ein Term zusammengesetzt ist).
Testen Sie damit für jede der obigen Zeichenfolgen, ob es sich um einen Prolog-Term
handelt, und was jeweils der Typ dieses Terms ist!
Abzugeben: Datei mit Angabe zu Term-Typen
Aufgabe 6 Im Programm verwandtschaft.pl ist unter anderem ein zweistelliges Prädikat kind/2 definiert. Dieses Prädikat lässt sich durch einen Graphen darstellen, z.B.
die ersten beiden Fakten des Prädikats durch
Franz
Max
Christine
(a) Vervollständigen Sie diesen Graphen!
(b) Laden Sie das Programm verwandtschaft.pl in Prolog und fragen Sie Prolog,
wer Nachkomme von wem ist! Bei wiederholter Eingabe eines Strichpunkts sollten
Sie insgesamt 11 Antworten bekommen.
5
(c) Fragen Sie Prolog, wer Nachkomme von Franz ist! Prolog sollte 4 Antworten liefern.
(d) Verlassen Sie nun Prolog, kopieren Sie die Datei verwandtschaft.pl, ändern Sie
die letzte Klausel der Kopie ab zu
nachkomme(N,X) :nachkomme(N,K),
kind(K,X).
und laden Sie diese Datei in Prolog und fragen Sie Prolog wieder, wer Nachkomme
von Franz ist! Erklären Sie, was dabei passiert!
(e) Was passiert, wenn Sie die letzten fünf Zeilen abändern zu
nachkomme(N,X) :nachkomme(N,K),
kind(K,X).
nachkomme(N,X) :kind(N,X).
und wieder dieselbe Anfrage stellen? Wenn Prolog einen Fehler signalisiert und
nicht das Prompt ?- , sondern z.B. nur ein Fragezeichen ohne Minuszeichen ausgibt,
versuchen Sie mit a (= abort) abzubrechen!
(f) Alle diese drei Programme unterscheiden sich nur in der Reihenfolge der Klauseln
oder in der Reihenfolge der Teilziele innerhalb des Rumpfes einer Klausel. Logisch
sind sie zueinander äquvialent, aber im Verhalten beim Aufruf einer Anfrage unterscheiden sie sich voneinander. Schauen Sie sich das Verhalten bei (c) und bei
(d) noch einmal an und formulieren Sie eine Faustregel, wie man die Reihenfolge
der Teilziele bei einer rekursiven Klausel wählen sollte!
Abzugeben: (a) Graphik; (b),(c) Anfragen; (d),(e),(f) Text
Aufgabe 7 Ein Gatter (englisch: gate) ist eine einfache elektronische Schaltung mit
ein oder mehr Eingängen und einem Ausgang. An jedem der Eingänge kann ein Signal
angelegt werden und das Gatter verarbeitet die Eingangssignale zu einem Signal am
Ausgang. Für jedes Signal gibt es zwei mögliche Werte, die als Wahrheitswerte w (für
„wahr“) und f (für „falsch“) interpretiert werden. Ein Beispiel für ein Gatter ist das oderGatter. Bezeichnen wir die Eingangssignale mit A und B und das Ausgangssignal mit C.
Dann ist C=w genau dann, wenn A=w oder B=w ist. Hier ist eine graphische Darstellung
des oder-Gatters als Kasten mit zwei Eingängen A und B oben und einem Ausgang C
unten, daneben die Wahrheits(wert)tabelle (englisch truth table), in der jede Zeile eine
Möglichkeit für die Wahrheitswerte von A und B und den dazugehörigen Wahrheitswert
von C angibt. Daneben ist eine Darstellung der Wahrheitstabelle als Prolog-Programm:
A B
oder
C
A
w
w
f
f
B
w
f
w
f
C
w
w
w
f
% oder(A,B,C)
oder(w,w,w).
oder(w,f,w).
oder(f,w,w).
oder(f,f,f).
C = (A oder B)
Schreiben Sie das Programm in eine Datei h07.pl und stellen Sie die Anfrage
6
?- oder(A,B,C).
und lassen Sie sich durch wiederholte Eingabe eines Strichpunkts nacheinander alle Antworten von Prolog ausgeben! Es sollten nacheinander die folgenden Antworten kommen:
A=w,
A=w,
A=f,
A=f,
B=w,
B=f,
B=w,
B=f,
C=w ;
C=w ;
C=w ;
C=f
Die genaue Form, in der Prolog diese Antworten präsentiert, unterscheiden sich von
Prolog-System zu Prolog-System. Überzeugen Sie sich, dass die Antworten, die Ihr
Prolog-System liefert, äquivalent sind zu den oben angeführten Antworten!
Weitere Beispiele für Gatter sind das und-Gatter und das nicht-Gatter, hier graphisch
als Kästen dargestellt und rechts daneben jeweils die Wahrheitstabelle:
A
w
w
f
f
A B
und
C
B
w
f
w
f
C
w
f
f
f
A
nicht
B
A
w
f
B
f
w
Ergänzen Sie Ihr Programm h07.pl um Prädikate und/3 und nicht/2 gemäß dieser
beiden Wahrheitstabellen!
Gatter können zu komplexeren Schaltungen kombiniert werden. Hier ist ein Halbaddierer graphisch als Kasten dargestellt und im Detailaufbau aus Gattern gezeigt,
daneben die Definition der Relation zwischen Ein- und Ausgaben als Prolog-Prädikat
halbaddierer/4.
A B
und
A
oder
nicht
B
D
und
Halbaddierer
C
S
E
C
S
halbaddierer(A,B,C,S) :und(A,B,C),
nicht(C,D),
oder(A,B,E),
und(D,E,S).
Fügen Sie diese Definition Ihrem Programm hinzu und lassen Sie es mit der Anfrage
?- halbaddierer(A,B,C,S).
laufen! Erstellen Sie aus den Antworten, die Ihnen Prolog liefert, die Wahrheitstabelle
für den Halbaddierer!
Hier sind zwei Schaltungen mit Rückkoppelungen:
7
A
B
oder
oder
E
A
F
nicht
nicht
C
D
nicht
Die linke Schaltung ist instabil. Stellen Sie an Prolog die Anfrage
?- nicht(A,A).
Dann sehen Sie, dass es keine stabile Lösung gibt. Die rechte Schaltung ist ein Flipflop
und ist bistabil. Wenn die Eingangssignale A=f und B=f sind, gibt es zwei verschiedene
Lösungen für die Ausgangssignale C und D. Um das mit Prolog zu testen, definieren Sie
ein Prolog-Prädikat flipflop/4 durch eine Definition
flipflop(A,B,C,D) :...
für die stabilen Zustände des Flipflop und stellen Sie dann die Anfrage
?- flipflop(A,B,C,D).
Prolog gibt Ihnen alle Antworten für stabile Zustände des Flipflop. Erstellen Sie daraus
eine Wahrheitstabelle! Zu den Einbagesignalen A=f und B=f wird Ihre Tabelle zwei
Zeilen haben.
Abzugeben: Programm; Wahrheitstabellen für Halbaddierer und für stabile Zustände
des Flipflop
Aufgabe 8 In der vorigen Aufgabe haben wir uns mit Logikschaltungen beschäftigt.
Aber die Signale, mit denen wir es dort zu tun hatten, kann man auch als Zahlen
1 für w (wahr) und 0 für f (falsch) deuten. Meist wählt man dann die Reihenfolge der
Aufschreibung so, dass zuerst 0, dann 1 drankommt. Kopieren Sie das Programm h07.pl
nach h08.pl und schreiben Sie h08.pl wie oben angedeutet um, wobei Sie 0 statt f und
1 statt w schreiben!
Der Halbaddierer kann jetzt verwendet werden, um zwei einstellige Zahlen im Zweiersystem (=Dualsystem=Binärsystem) zu addieren. Dabei kann es einen Übertrag (englisch carry C) geben. Die Summe A+B kann also zweistellig werden:
02 + 02 = 002
02 + 12 = 012
12 + 02 = 012
12 + 12 = 102
8
Die erste Stelle der Summe (Zweierstelle) ist der Übertrag C und die zweite Stelle (Einerstelle) das S (für Summe). Probieren Sie das mit dem Programm h08.pl aus!
Beim Addieren mehrstelliger Zahlen, z.B.
10012 +
10112 =
101002
addiert man zunächst die rechten Stellen (Einerstellen) der Summanden. Das ergibt
hier Summe 0 (als Einerstelle des Ergebnisses) und Übertrag 1. Dann addiert man die
zweitletzten Stellen der Summanden (Zweierstellen) und muss noch den Übertrag, hier
1 dazuaddieren: 02 + 12 + 12 ergibt hier 2, also 102 , d.h. wieder Summe 0 (als Zweierstelle
des Ergebnisses) und Übertrag 1 auf die drittletzte Stelle (Viererstelle), u.s.w. Es müssen
also für die Berechnung einer jeden Stelle des Ergebnisses im Zweiersystem bis zu drei
einstellige Zahlen addiert werden. Dies tut der Volladdierer
A
B
Halbaddierer
A
Cout
S1
B
C1
Volladdierer
Cin
Halbaddierer
C2
Cin
oder
Cout
S
S
Ergänzen Sie das Programm h08.pl um die Definition des Prädikats volladdierer/5:
volladdierer(A,B,Cin,Cout,S) :...
Verwenden Sie dabei das Prädikat halbaddierer/4! Stellen Sie nun die Anfrage
?- volladdierer(A,B,Cin,Cout,S).
und lassen Sie sich von Prolog mit Strichpunkt alle Antworten ausgeben! Überzeugen Sie
sich, dass tatsächlich die Summe A+B+Cin im Zweiersystem ausgerechnet wird, wobei
das Ergebnis aus den zwei Ziffern Cout und S besteht. Aus vier Volladdierern kann man
nun einen Vier-Bit-Addierer bauen:
A3
C4
B3
Volladdierer
S3
A2
C3
B2
Volladdierer
A1
C2
S2
B1
Volladdierer
S1
9
A0
C1
B0
Volladdierer
S0
C0
Ergänzen Sie Ihr Programm h08.pl dementsprechend um ein Prädikat vierbitaddierer/14:
vierbitaddierer(A3,B3,A2,B2,A1,B1,A0,B0,C0,C4,S3,S2,S1,S0) :...
Normalerweise wird man C0=0 wählen. Um die Verwendung des Prädikats etwas übersichtlicher zu machen, kann man die Bits jedes Summanden und der Summe jeweils in
eine Liste zusammenfassen:
vierbitaddierer1([A3,A2,A1,A0],[B3,B2,B1,B0],[C4,S3,S2,S1,S0]) :vierbitaddierer(A3,B3,A2,B2,A1,B1,A0,B0,0,C4,S3,S2,S1,S0).
Stellen Sie für obiges Beispiel 10012 + 10112 = 101002 die Anfragen
?- vierbitaddierer1([1,0,0,1],[1,0,1,1],Summe).
?- vierbitaddierer1(Summand1,Summand2,[1,0,1,0,0]).
und vergewissern Sie sich, dass Prolog die richtigen Antworten liefert!
Abzugeben: Programm
Aufgabe 9 Bei dieser Aufgabe geht es um die Situation einer Familie und die Frage,
wer mit wem sein Hobby gemeinsam ausüben kann. Viele Hobbies kann man außerhalb der Urlaubs- oder Ferienzeit, etwa am Abend oder Wochenende ausüben, und zwei
Personen, die nahe beieinander wohnen, können dies gemeinsam tun. Andere Hobbies,
z.B. segeln auf hoher See erfordern eine mehrwöchige Urlaubs- oder Ferienzeit. Zwei
Menschen können ein solches Hobby gemeinsam ausüben, wenn sie zur gleichen Zeit frei
haben, unabhängig davon, wie weit entfernt voneinander sie wohnen.
Die Verwandtschaftsbeziehungen der Familie seien durch den folgenden Graphen gegeben:
Hans
Anna
Karl
Max
Dora
Franz
Eva
Bert
Karl ist z.B. ein Kind von Anna. Jede der Personen hat mindestens ein Hobby:
• Hans spielt Schach und segelt.
• Anna spielt Schach und geht gerne einkaufen.
• Karl geht gerne auf Parties.
• Max angelt und segelt.
• Dora spielt Tennis, segelt und geht gerne einkaufen.
• Franz geht wandern, segelt und spielt Schach.
• Eva reitet.
10
• Bert angelt, spielt Tennis, segelt und geht gerne einkaufen.
Die Familie ist über zwei Städte verstreut:
• Hans, Anna, Karl, Max und Dora wohnen in St. Pölten.
• Franz, Eva und Bert wohnen in Los Angeles.
Die Mitglieder der Familie haben in unterschiedlichen Monaten frei:
• Hans, Anna und Karl haben immer frei.
• Max und Dora haben im August frei.
• Franz, Eva und Bert haben im Juli frei.
Zur Lösung der Aufgabe noch die folgenden Informationen:
• Wenn zwei Personen in der gleichen Stadt wohnen, dann wohnen sie nahe beieinander.
• Wenn zwei Personen nahe beieinander wohnen und eines der Hobbies „Schach
spielen“, „einkaufen“, „auf Parties gehen“, „angeln“, „Tennis spielen“, „wandern“
und „reiten“ gemeinsam haben, können sie dieses Hobby gemeinsam ausüben.
• Wenn zwei Personen dasselbe Hobby haben, können sie es gemeinsam ausüben,
wenn sie im gleichen Monat frei haben.
Frage:
• Wer kann sein Hobby gemeinsam mit seinem Enkelkind ausüben? Gesucht sind
alle möglichen Antworten. Jede Antwort soll jeweils die Person, das Enkelkind und
das Hobby nennen.
Übersetzen Sie die hier angegebene Kind-Eltern-Beziehung und alle mit • gekennzeichneten Aussagen in ein Prolog-Programm, übersetzen Sie die ebenfalls mit • gekennzeichnete
Frage am Ende der Problemstellung in eine Prolog-Anfrage und fügen Sie diese Anfrage
am Ende der Datei als Kommentar dem Programm hinzu!
Abzugeben: Programm mit Anfrage
Aufgabe 10 Erweitern Sie das Programm verwandtschaft.pl um ein Prädikat bruder/2,
wobei bruder(B,P) bedeuten soll: B ist Bruder der Person P. Gehen Sie dazu zunächst
von der folgenden Definition aus:
B ist Bruder von P, wenn B Kind von X ist, B männlich ist und P Kind von
X ist.
Fragen Sie Prolog danach, wer Bruder vom wem ist! Was fällt Ihnen dabei auf? Definieren
Sie nun ein Prädikat verschieden/2, mit Fakten darüber, welche Personen voneinander
verschieden sind! Verwenden Sie dabei keine eingebauten Prädikate – die nehmen wir
erst später durch! Schreiben Sie stattdessen explizit z.B.
verschieden(max,franz).
und Entsprechendes für alle anderen Paare von zueinander verschiedenen Personen! Es
müssen insgesamt 30 Fakten für das Prädikat verschieden/2 sein. Wir werden später
sehen, wie man das in Prolog bequemer machen kann. Verwenden Sie dieses Prädikat,
um die Definition des Prädikats bruder/2 richtigzustellen! Dabei werden Sie aber noch
immer Antworten doppelt bekommen. Warum? Was würde passieren, wenn wir andere
11
Fakten für das Prädikat kind/2 hätten derart, dass eine Person Halbbruder einer anderen
Person ist? Ändern Sie schließlich die Definition des Prädikats bruder/2 so ab, dass
keine Antworten doppelt kommen und in Antworten nur echte Brüder, nicht Halbbrüder
genannt werden!
Abzugeben: Programm mit Anfrage und Text als Kommentar
Aufgabe 11 (Vierfarbenproblem) Österreich besteht aus den Bundesländern Vorarlberg, Tirol, Salzburg, Oberösterreich, Kärnten, Steiermark, Niederösterreich, Wien
und Burgenland (siehe Datei oesterreichkarte.png). Beim Vierfarbenproblem geht es
darum, mit vier Farben – sagen wir Rot, Grün, Blau und Gelb – eine Karte zu zeichnen, bei der jeweils zwei aneinander angrenzende1 Länder verschiedene Farben haben.
In unserem Beispiel muss etwa die Farbe von Tirol verschieden sein von der Farbe von
Kärnten, da die Länder Tirol und Kärnten aneinander angrenzen.
Zeichnen Sie zunächst einen Graphen, in dem jedes Bundesland als Knoten dargestellt ist und für je zwei aneinander angrenzende Bundesländer eine Kante die beiden
entsprechenden Knoten verbindet! Schreiben Sie dann ein Prolog-Programm mit Fakten
darüber, welche Farben voneinander verschieden sind! Verwenden Sie dabei keine eingebauten Prädikate – die nehmen wir erst später durch! Schreiben Sie stattdessen explizit
z.B.
verschieden(rot,gruen).
und Entsprechendes für alle anderen Paare von verschiedenen Farben. Es müssen insgesamt 12 Fakten sein. Fügen Sie schließlich eine Regel hinzu so, dass die Anfrage
?- loesung(Farbe_Vorarlberg,
Farbe_Tirol,
Farbe_Salzburg,
Farbe_Oberoesterreich,
Farbe_Kaernten,
Farbe_Steiermark,
Farbe_Niederoesterreich,
Farbe_Wien,
Farbe_Burgenland).
alle Lösungen des Vierfarbenproblems für die Landkarte von Österreich findet! Eine
Lösung ist zum Beispiel
Farbe_Burgenland = gruen
Farbe_Kaernten = blau
Farbe_Niederoesterreich = rot
Farbe_Oberoesterreich = gruen
Farbe_Salzburg = rot
Farbe_Steiermark = gelb
1
Gemeint ist, dass sie eine gemeinsame Grenzlinie (nicht nur einen gemeinsamen Grenzpunkt) haben.
12
Farbe_Tirol = gruen
Farbe_Vorarlberg = rot
Farbe_Wien = gruen
(hier die Ausgabe einer der Lösungen bei GNU-Prolog; bei SWI-Prolog kommt die gleiche Lösung – etwas anders dargestellt – heraus). Der Vierfarbensatz besagt, dass in
der Ebene (oder auch auf der Kugeloberfläche) jede Landkarte, bei der jedes Land zusammenhängend ist,2 sich mit vier Farben färben lässt. Seit 1852 haben Mathematiker
versucht, dies zu beweisen. Ein Beweis konnte erst 1976 mit Computerhilfe gefunden
werden und war so kompliziert, dass er von Menschen nicht nachvollzogen werden kann.
Abzugeben: Graph, Programm
Aufgabe 12 (Cliquen-Problem) Ein bekanntes schwieriges Problem der Informatik
ist das Cliquenproblem. In einer Menge von Personen gibt es einige Paare von miteinander befreundeten Personen. Eine Clique ist nun eine Teilmenge von Personen, in der
jede Person mit jeder anderen Person befreundet ist. Eine Clique aus n Personen wird
eine n-Clique oder n-er-Clique genannt. Hier ein Beispiel:
(a) Anton und Berta sind miteinander befreundet.
(b) Anton und Christa sind miteinander befreundet.
(c) Anton und Dora sind miteinander befreundet.
(d) Anton und Ernst sind miteinander befreundet.
(e) Berta und Dora sind miteinander befreundet.
(f) Berta und Ernst sind miteinander befreundet.
(g) Berta und Franz sind miteinander befreundet.
(h) Christa und Dora sind miteinander befreundet.
(i) Christa und Ernst sind miteinander befreundet.
(j) Dora und Ernst sind miteinander befreundet.
(k) Dora und Franz sind miteinander befreundet.
(l) Ernst und Franz sind miteinander befreundet.
Dann ist die Menge {Dora, Anton, Ernst, Berta} eine Vierer-Clique, da sie aus vier
Personen besteht, die alle miteinander befreundet sind. Ziel der Aufgabe ist es, für
dieses Beispiel ein Prologprogramm zu schreiben, das alle Vierer-Cliquen findet. Wir
könnten die oben genannte Vierer-Clique als Term menge(dora,anton,ernst,berta)
darstellen. Leider ist diese Darstellung aber nicht eindeutig, da etwa der Prologterm
menge(anton,berta,dora,ernst) dieselbe Clique darstellt. Jede Vierer-Clique hat 24
verschiedene Darstellungen als Prologterm. Um Eindeutigkeit zu erreichen, wollen wir
denjenigen Prologterm verwenden, bei dem die vier Mitglieder der Clique in lexikographischer (=alphabetischer) Reihenfolge genannt sind, also im Beispiel den Term
menge(anton,berta,dora,ernst).
Stellen Sie zunächst das Problem durch einen Graphen dar mit je einem Knoten für
jede beteiligte Person und einer Kante für jedes Paar von befreundeten Personen! Schreiben Sie dann ein Prologprogramm, in dem Sie ein Prädikat befreundet/2 gemäß (a)–(l)
2
Im Falle Österreichs ist Tirol nicht zusammenhängend, da Osttirol nicht mit dem Hauptteil von Tirol
zusammenhängt, aber die Landkarte Österreichs lässt sich trotzdem mit vier Farben färben.
13
durch Fakten definieren, wobei befreundet(A,B) bedeuten soll, dass die Personen A
und B miteinander befreundet sind und Person A in der lexikographischen Reihenfolge vor Person B steht! Definieren Sie nun ein Prädikat ist_Viererclique/1, wobei
ist_Viererclique(C) bedeuten soll, dass C eine Vierer-Clique ist! Dabei soll C als
Prologterm wie oben dargestellt sein, wobei die vier Mitglieder der Vierer-Clique in
lexikographischer Reihenfolge genannt sind. Schreiben Sie die Erklärungen, was die Prädikate bedeuten, jeweils als Kommentar vor die entsprechenden Klauseln. Ihr Programm
sollte alle Vierercliquen finden können und sich etwa so verhalten:
?- ist_Viererclique(Viererclique).
Viererclique = menge(anton, berta, dora, ernst) ;
Viererclique = menge(anton, christa, dora, ernst) ;
Viererclique = menge(berta, dora, ernst, franz)
Das Cliquen-Problem besteht darin, zu einem gegebenen endlichen ungerichteten Graphen (wie im Beispiel) und zu einer gegebenen natürlichen Zahl n festzustellen, ob es
eine n-Clique gibt. Es gehört zur Klasse der sogenannten NP-vollständigen Probleme.
Für diese Probleme ist es bis heute keinem Forscher gelungen, einen effizienten Algorithmus anzugeben. Es wird vermutet, dass es für NP-vollständige Probleme keine effizienten
Algorithmen gibt, aber auch das konnte bisher niemand beweisen. Die Frage, ob es einen
effizienten Algorithmus dafür gibt (P=NP? seit 1971), ist das bekannteste bis heute ungelöste Problem der Theoretischen Informatik. Für kleine Mengen von Personen ist das
Problem mit Prolog leicht lösbar, aber für große Mengen wird der Rechenaufwand gigantisch.
Abzugeben: Graph, Programm samt Kommentaren
Aufgabe 13 Geben Sie für jeden der folgenden Terme 1. den Funktor (samt Stelligkeit,
z.B. k/4), 2. die unmittelbaren Teilterme, 3. alle Teilterme an und zeichnen Sie 4. den
Strukturbaum:
(a) h(a,b,c)
(b) f(g(h(X,a),Y,h(Z,X)),c,3)
(c) d
(d) 10-5-4
(e) a*b+U*c-V/X
Hinweis: Bitte versuchen Sie zunächst die Aufgabe ohne Computerhilfe zu lösen. Danach (und bitte erst danach!) schauen Sie sich bitte die Dokumentation des eingebauten Prolog-Prädikats functor/3 an! In SWI-Prolog können Sie das etwa tun, indem
Sie ?- help. aufrufen und ins Eingabefeld in der Fußzeile des sich öffnenden HilfeFensters functor eingeben, gefolgt von einem RETURN oder einem Klick auf den HelpButton. Probieren Sie dieses eingebaute Prädikat aus:
?- functor(k(X,f(Y)),Funktor,Stelligkeit).
Funktor = k, Stelligkeit = 2
Wenn Sie den Funktor und die Stelligkeit haben, können Sie z.B. mit
14
?- k(Teilterm1,Teilterm2) = k(X,f(Y)).
Prolog nach den unmittelbaren Teiltermen des Terms fragen. Mit
?- arg(2,k(X,f(Y)),Teilterm2).
können Sie Prolog nach dem zweiten unmittelbaren Teilterm des Terms fragen. Lesen
Sie sich dazu auch die Dokumentation von arg/3 durch!
Abzugeben: jeweils Funktor, unmittelbare Teilterme, alle Teilterme, Strukturbaum
Aufgabe 14 Wir wollen einen Vektor (X, Y, Z) im dreidimensionalen euklidischen Raum
darstellen als Prologterm vektor(X,Y ,Z). Hier ist ein Programm zur Berechnung der
Summe zweier Vektoren und des Betrags, d.h. der Länge eines Vektors.
%vektorsumme(+Vektor,+Vektor,-Vektor)
%vektorsumme(V1,V2,V) Vektor V ist Summe der Vektoren V1 und V2.
vektorsumme(vektor(X1,Y1,Z1),vektor(X2,Y2,Z2),vektor(X,Y,Z)) :X is X1+X2,
Y is Y1+Y2,
Z is Z1+Z2.
%betrag(+Vektor,-Zahl)
%betrag(V,B) B ist der Betrag des Vektors V.
betrag(vektor(X,Y,Z),B) :B is sqrt(X*X+Y*Y+Z*Z).
In den Kommentaren bedeutet das + bei +Vektor, dass beim Aufruf des Prädikats das
betreffende Argument voll instantiiert sein soll, also z.B. nicht eine Variable. Das - in
-Vektor und -Zahl heißt, dass beim Aufruf des Prädikats das betreffende Argument
uninstantiiert (also eine Variable) sein soll.
Fragen Sie Prolog nach der Summe der beiden Vektoren (2, 5, 4) und (−3, 2, 1) und
nach dem Betrag des Vektors (2, 5, 4)! Um zu sehen, was passieren kann, wenn die
im Kommentar vorgeschriebene Instantiierung oder Nicht-Instantiierung nicht beachtet
wird, stellen Sie die Anfragen
?- betrag(X,B).
?- betrag(vektor(0,0,0),0).
Erklären Sie, warum es zu einer Fehlermeldung bzw. zu einer unerwarteten Antwort
kommt! Erweitern Sie das Programm nun um zwei Prologprädikate skalarprodukt/3
und vektorielles_Produkt/3 zur Berechnung des Skalarprodukts beziehungsweise des
vektoriellen Produkts zweier Vektoren!
Abzugeben: Anfragen, Erklärung, Programm
Aufgabe 15 Eine
√ komplexe Zahl hat die Form a + bi, wobei a und b reelle Zahlen
sind und i = −1 ist. Wir wollen eine solche komplexe Zahl a + bi darstellen als
Prologterm komplex(a,b). Definieren Sie Prologprädikate kompl_add/3, kompl_sub/3,
15
kompl_mul/3 und kompl_div/3 zur Addition, Subtraktion, Multiplikation und Division
zweier komplexer Zahlen und stellen Sie dazu Anfragen zur Berechnung von (1 + i)(1 − i)
3
und von 4−5i
!
Abzugeben: Programm, Anfragen
Aufgabe 16 Übersetzen Sie die folgenden Aussagen über Paare und ihre Wohnorte in
Prologfakten!
• Das Paar Max und Eva wohnt in Salzburg.
• Das Paar John und Jane wohnt in London.
• Das Paar Hans und Anna wohnt in Salzburg.
Stellen Sie dabei jedes Paar als zusammengesetzten Prologterm dar, z.B. das Paar Max
und Eva als den Prologterm paar(max,eva)! Fragen Sie nun Prolog nach den Paaren,
die in Salzburg wohnen. Prolog sollte darauf antworten mit
Paar = paar(max, eva) ;
Paar = paar(hans, anna).
Fragen Sie schließlich nach den Frauen, die einem Paar angehören, das in Salzburg wohnt!
Prolog sollte darauf antworten mit
Frau = eva ;
Frau = anna.
Hinweis: Schreiben Sie Ihre Anfrage zunächst so, dass Prolog antwortet mit
Mann = max, Frau = eva ;
Mann = hans, Frau = anna.
und ersetzen Sie dann die Variable Mann in der Anfrage durch die „anonyme Variable“ _
(Unterstreichungsstrich oder underscore)! Dann gibt Ihnen Prolog den Mann nicht aus.
Abzugeben: Programm und zwei Anfragen
Aufgabe 17 Stellen Sie an Prolog die Anfrage
?- f(A,B,C) = f(g(B,B),g(C,C),g(D,D)).
und beobachten Sie, was Prolog antwortet! Schreiben Sie eine entsprechende Anfrage
mit zehnstelligem Funktor f/10:
?- f(A,B,C,D,E,F,G,H,I,J) =
f(g(B,B),g(C,C),g(D,D),g(E,E),g(F,F),g(G,G),g(H,H),g(I,I),g(J,J),g(K,K)).
Schaun Sie sich die Antwort an, die Prolog liefert! Besonders der Term, zu dem Prolog
die Variable A instanziiert, ist recht lang. Je nach der Einstellung des Prologsystems
kann es sein, dass Prolog diesen Term dabei abkürzt. Bestimmen Sie trotzdem, wie oft
das K in diesem Term vorkommt! Begründen Sie Ihre Antwort!
Abzugeben: Text
16
Aufgabe 18 (Listen) In Prolog können wir mehrere Terme zu einer Liste zusammenfassen. Dazu schreiben wir die Terme zwischen eckige Klammern und durch Kommas
voneinander getrennt. Zum Beispiel ist [a,b,c] die Liste, die aus den Termen (Elementen) a, b und c besteht. Die leere Liste [] enthält keine Elemente, die Liste [a] nur ein
Element a. Prolog verwendet für Listen nicht einen eigenen Datentyp. Stattdessen sind
Listen ganz gewöhnliche Terme. Die leere Liste ist ein Prologatom []. Alle anderen Listen
sind zusammengesetzte Terme, die aus den Elementen der Liste und aus der leeren Liste
[] mit Hilfe des zweistelligen Funktors ./2 (also Punkt) aufgebaut sind.3 So ist [a,b,c]
nur eine abkürzende Schreibweise für den Prologterm .(a, .(b, .(c, []))) und kann
optional anstatt der kanonischen Schreibung .(a, .(b, .(c, []))) verwendet werden. Prolog verwendet in seinen Antworten standardmäßig stets die Listenschreibweise
[a,b,c]:
?- X = .(a, .(b, .(c, []))).
X = [a, b, c].
?- X = .(a, [b,c,d]).
X = [a, b, c, d].
Wie man sieht, dient hier der zweistellige Funktor ./2 dazu, ein neues Element a an
eine existierende Liste [b,c,d] vorne anzuhängen. Allgemein ist .(A,L) die Liste, die
entsteht, indem man an die Liste L vorne das neue Element A anhängt.
Man kann sich die kanonische Schreibweise mit write_canonical/1 ausgeben lassen:
?- write_canonical([a,b,c]).
’.’(a,’.’(b,’.’(c,[])))
Dabei hat Prolog den Funktor ./2 (Punkt) der Deutlichkeit halber in einfache Anführungszeichen gesetzt.
Der Strukturbaum der Liste [a,b,c] ist
.
.
a
.
b
c
[]
Listen können auch selbst wieder Listen als Elemente enthalten und beliebig tief verschachtelt sein. Geben Sie die kanonische Schreibung sowie den Strukturbaum für die
Liste [a,[b,c]] an!
Abzugeben: Text, Strukturbaum
3
In SWI-Prolog soll ist ab Version 7 der Name dieses Funktors ’[|]’ statt des Punktes, um den Punkt
für andere Dinge verwenden zu können.
17
Aufgabe 19 (Unifikation) Unifizieren Sie die beiden Terme f(X,h(Y,Z),a) und
f(g(U),U,Y) mit dem Unifikationsalgorithmus der Vorlesung! Kennzeichnen Sie dabei für jeden Schritt die Nichtübereinstimmungsmenge durch Hervorhebung in Farbe
oder Unterstreichung und geben Sie für jeden Schritt die Substitution σi an sowie den
resultierenden allgemeinsten Unifikator!
Aufgabe 20 (Listensumme) Schreiben Sie ein Prologprädikat listensumme/2 zur
Bestimmung der Summe einer Liste von Zahlen! Beispiel:
?- listensumme([3,5,9],Summe).
Summe = 17.
In vielen Prologs ist ein solches Prädikat bereits eingebaut. Implementieren Sie das
Prädikat aber bitte selber, wobei Sie keine eingebauten Prädikate außer dem Prädikat
is/2 verwenden sollen!
Abzugeben: Programm
Aufgabe 21 (Ableitung) In der Differentialrechnung gibt es einfache Regeln, um die
Ableitung einer Funktion nach einer Variablen x zu bestimmen, zum Beispiel
(a) Ableitung einer konstanten Funktion ergibt 0.
(b) Ableitung von x nach x ergibt 1.
(c) Summenregel
(d) Produktregel
Wir wollen hier annehmen, dass die Funktion gegeben ist durch einen einfachen arithmetischen Ausdruck, der aus den Zahlen 0 und 1 und aus den Buchstaben a und x mit
Addition und Multiplikation aufgebaut ist. Im Sinne der Differentialrechnung soll dabei
nach x differenziert werden, während 0, 1 und a als Konstanten behandelt werden.
In Prolog stellen wollen wir einen solchen Ausdruck darstellen durch einen Term, der
aufgebaut ist aus den Prolog-Konstanten 0, 1, a und x mit den Funktoren +/2 und */2, also durch einen Term aus dem Herbrand-Universum zur Menge {0/0, 1/0, a/0, x/0, +/2, */2}.
Beispiel: Der Prologterm a*x+(1+a)*x*(1+x) steht für die Funktion f , die definiert ist
durch f (x) = ax + (1 + a)x(1 + x). Beachten Sie, dass wir die Variable x, nach der
differenziert wird (ebenso wie den Buchstaben a) in Prolog als Konstante darstellen.
Unseren Begriff des „einfachen Ausdrucks“ kann man in Prolog definieren durch das
folgende Prädikat.
einfacher_Ausdruck(0).
einfacher_Ausdruck(1).
einfacher_Ausdruck(a).
einfacher_Ausdruck(x).
einfacher_Ausdruck(A+B) :einfacher_Ausdruck(A),
einfacher_Ausdruck(B).
einfacher_Ausdruck(A*B) :einfacher_Ausdruck(A),
einfacher_Ausdruck(B).
18
Die Anfrage ?- einfacher_Ausdruck(a*x+(1+a)*x*(1+x)). gelingt dann.
Definieren Sie ein Prädikat abl_x/2 zur Bestimmung der Ableitung eines einfachen
Ausdrucks nach x! Übersetzen Sie dazu die obigen Regeln (a)–(d) in Prologklauseln!
Beispiel einer Anfrage und einer möglichen Antwort von Prolog:
?- abl_x(a*x+(1+a)*x*(1+x),Ableitung).
Ableitung = 0*x+a*1+(((0+0)*x+(1+a)*1)*(1+x)+(1+a)*x*(0+1))
Den Ausdruck, den Prolog hier geliefert hat, könnte man noch deutlich vereinfachen,
was aber für diese Aufgabe nicht verlangt ist.
Abzugeben: Programm
Aufgabe 22 (Negation as failure) In Prolog kann man nicht direkt ausdrücken, dass
ein Prädikat auf bestimmte Objekte nicht zutrifft. Stattdessen nimmt man – ähnlich wie
in anderen Datenbank-Sprachen – an, dass ein Prädikat auf Objekte nicht zutrifft, wenn
im Programm nicht explizit steht oder es logisch aus dem Programm folgt, dass das
Prädikat auf diese Objekte zutrifft. Beispiel: Der Individuenbereich, also die Menge der
betrachteten Objekte bestehe aus den Vögeln Amsel, Strauß, Fink, Pinguin, Adler und
Habicht. Die Definition des Prädikats flugunfaehiger_Vogel/1 sei
flugunfaehiger_Vogel(strauss).
flugunfaehiger_Vogel(pinguin).
Dann besagt die Closed World Assumption, dass das Prädikat flugunfaehiger_Vogel/1
auf Amsel, Fink, Adler und Habicht nicht zutrifft, da z.B. flugunfaehiger_Vogel(amsel)
nicht logisch aus dem Programm folgt. Leider ist es oft schwierig zu beweisen, dass ein
Ziel wie z.B. flugunfaehiger_Vogel(amsel) nicht logisch aus einem Programm folgt.
Im Allgemeinen ist die Frage sogar unentscheidbar, d.h. es gibt grundsätzlich keinen
Algorithmus, der immer entscheiden könnte, ob ein gegebenes Ziel aus einem gegebenen
Programm folgt oder nicht. Als Annäherung an die Closed World Assumption verwendet Prolog die Negation as Failure (Negation als Fehlschlag). Die Negation as Failure
eines Ziels G wird mit \+G bezeichnet. Wenn das Ziel \+G aufgerufen wird, versucht
Prolog zunächst das Ziel G zu beweisen. Wenn der Aufruf von G gelingt, dann schlägt
der Aufruf von \+G fehl. Wenn der Aufruf von G fehlschlägt, dann gelingt der Aufruf
von \+G. Der Aufruf von G könnte aber auch in eine Endlosschleife führen.
Betrachten wir wieder das Beispiel von oben zusammen mit der folgenden Definition
eines Prädikats vogel/1:
vogel(amsel).
vogel(strauss).
vogel(fink).
vogel(pinguin).
vogel(adler).
vogel(habicht).
Wir möchten nun wissen, welche Vögel fliegen können. Dazu stellen wir die Anfrage
19
?- vogel(V), \+ flugunfaehiger_Vogel(V).
Wir fragen also Prolog nach einem Vogel, der nicht ein flugunfähiger Vogel ist. Prolog ruft
als erstes das Ziel vogel(V) auf. Dieses Ziel gelingt mit V=amsel. Nun ruft Prolog damit
das zweite Ziel der Anfrage auf, also \+ flugunfaehiger_Vogel(amsel). Da dies eine
Negation as Failure ist, ruft Prolog zunächst das Ziel flugunfaehiger_Vogel(amsel)
auf, was fehlschlägt. Daher gelingt der Aufruf von \+ flugunfaehiger_Vogel(amsel)
und Prolog liefert die Antwort V=amsel.
Wenn man mit einem Strichpunkt nach einer weiteren Antwort fragt, macht Prolog ein
Redo des ersten Ziels vogel(V) und findet dafür eine zweite Lösung V=strauss. Damit
ruft Prolog das zweite Ziel der Anfrage auf, also \+ flugunfaehiger_Vogel(strauss).
Da dies eine Negation as Failure ist, ruft Prolog zunächst das Ziel
flugunfaehiger_Vogel(strauss) auf, was gelingt. Daher schlägt der Aufruf von
\+ flugunfaehiger_Vogel(strauss) fehl. Dieser Fehlschlag des zweiten Ziels der Anfrage bewirkt ein Redo des ersten Ziels vogel(V). Prolog findet dafür eine dritte Lösung
V=fink. . . .
Setzen Sie bitte die Analyse des Programmablaufs ab hier fort! Sie können sich als
Hilfe von Prolog einen Trace anzeigen lassen. Der Trace, den GNU-Prolog ausgibt ist da
etwas detaillierter und für diese Aufgabe hilfreicher als der von SWI-Prolog. GNU-Prolog
ist ebenso wie SWI-Prolog auf unseren Rechnern installiert (Aufruf mit gprolog).
Stellen Sie nun die Anfrage umgekehrt:
?- \+ flugunfaehiger_Vogel(V), vogel(V).
Erklären Sie, was dabei passiert und warum die Reihenfolge der Ziele in der Anfrage für
die Menge der gelieferten Antworten eine Rolle spielt und daher die Negation as Failure
nicht exakt der logischen Negation entspricht!
Abzugeben: Text (Fortsetzung der Analyse des Programmablaufs, Erklärung)
Aufgabe 23 Unter dem Herbrand-Universum einer Menge von Funktoren versteht man
die Menge aller Terme, die man aus diesen Funktoren bilden kann. Betrachten wir zum
Beispiel einen zweistelligen Funktor f, in Prolog geschrieben als f/2, und eine Konstante a, in Prolog geschrieben a/0. Dann enthält das Herbrand-Universum der Menge
{f/2, a/0} den Term f(f(a,a),f(a,f(a,a))):
in_Herbrand_Universum_fa(a).
in_Herbrand_Universum_fa(f(T1,T2)) :in_Herbrand_Universum_fa(T1),
in_Herbrand_Universum_fa(T2).
?- in_Herbrand_Universum_fa(f(f(a,a),f(a,f(a,a)))).
yes
Schreiben Sie ein Prolog-Programm zur Ermittlung der Anzahl der Vorkommen der Konstanten a in einem Term aus dem Herbrand-Universum der Menge {f/2, a/0}! Beispiel
für eine Anfrage und Prologs Antwort:
20
?- anzahl_a(f(f(a,a),f(a,f(a,a))),Anzahl).
Anzahl = 5
Abzugeben: Programm
Aufgabe 24 Unter den Zahlen spielen die natürlichen Zahlen 0, 1, 2, 3, . . . eine besondere Rolle. Man kann sie induktiv charakterisieren durch die folgenden beiden Regeln:
• Die Zahl 0 ist eine natürliche Zahl.
• Wenn n eine natürliche Zahl ist, dann ist auch n + 1 eine natürliche Zahl.
Übersetzen Sie diese beiden Regeln in zwei Prolog-Programm-Klauseln, die durch Rekursion ein Prolog-Prädikat natuerliche_Zahl/1 mit folgendem Verhalten definieren!
?- natuerliche_Zahl(N).
N = 0 ;
N = 1 ;
N = 2 ;
N = 3 ;
...
Das Prädikat natuerliche_Zahl/1 zählt also bei Aufruf mit einer Variablen N als Argument genau die Menge der natürlichen Zahlen auf. Verwenden Sie in Ihrem Programm
keine eingebauten Prädikate von Prolog außer is/2!
Wenn M eine Menge ist und man durch Rekursion ein Prädikat definieren kann, das
die Menge M aufzählt, sagen wir auch, die Menge M sei rekursiv aufzählbar (englisch
recursively enumerable oder einfach r.e.). Die Menge der natürlichen Zahlen ist also
rekursiv aufzählbar.
Erweitern Sie nun Ihr Programm um ein weiteres Prädikat quadratzahl/1, das die
Menge der Quadratzahlen aufzählt:
?- quadratzahl(Q).
Q = 0 ;
Q = 1 ;
Q = 4 ;
Q = 9 ;
...
Sie sehen, dass auch die Menge der Quadratzahlen rekursiv aufzählbar ist.
Abzugeben: Programm
Aufgabe 25 Schreiben Sie ein Prolog-Programm, das zu jeder gegebenen Liste von a’s
und b’s die entsprechende Liste berechnet, bei der jedes a durch ein b und jedes b
durch ein a ersetzt ist! So wird z.B. aus der Liste [a,b,b,a,a] die Liste [b,a,a,b,b].
Verwenden Sie in Ihrem Programm keine eingebauten Prädikate von Prolog!
Abzugeben: Programm
Aufgabe 26 Schreiben Sie ein Prolog-Programm, das zu einer Liste von Zahlen die
Liste der Quadrate dieser Zahlen berechnet! So wird z.B. aus der Liste [2,8,3] die
21
Liste [4,64,9]. Verwenden Sie in Ihrem Programm keine eingebauten Prädikate von
Prolog außer is/2!
Abzugeben: Programm
Aufgabe 27 Wir wollen Punkte in der Ebene darstellen als zusammengesetzte Prologterme, z.B. den Punkt (2, 3) als Term punkt(2,3). Wenn man Punkte P1 , . . . , Pn
miteinander durch Strecken verbindet, und zwar P1 mit P2 , P2 mit P3 , . . . , Pn−1 mit
Pn , dann erhält man einen Streckenzug. Einen solchen Streckenzug wollen wir in Prolog
darstellen durch einen zusammengesetzten Term streckenzug([P1 , . . . ,Pn ]) mit Funktor streckenzug/1 und der Liste der Punkte als Argument. Beispiel: Die drei Punkte
P1 = (2, 3), P2 = (1, 1) und P3 = (3, 2) definieren einen Streckenzug
P1
P3
P2
,
den wir durch den Prologterm streckenzug([punkt(2,3),punkt(1,1),punkt(3,2)])
darstellen. Die Länge eines Streckenzuges ist die Summe der Längen seiner Strecken.
Schreiben Sie ein Prolog-Programm zur Bestimmung des Abstandes zweier Punkte voneinander sowie der Länge eines Streckenzuges! Beispiele für Anfragen an Prolog und
Prologs Antworten:
?- abstand(punkt(2,3),punkt(1,1),Abstand).
Abstand = 2.23606797749979
?- streckenzuglaenge(streckenzug([punkt(2,3),punkt(1,1),punkt(3,2)]),Laenge).
Laenge = 4.47213595499958
Abzugeben: Programm
Aufgabe 28 (Tail-Recursion mit Akkumulator) Für jede natürliche Zahl n sei f (n)
die Summe der reziproken Werte der ganzen Zahlen von 1 bis n, also
f (n) =
n
X
1
k=1
k
=
1 1 1
1
+ + + ··· + .
1 2 3
n
Dann ist z.B. f (3) = 1 + 12 + 13 = 1, 8333 . . . . Um f (n) mit Prolog zu berechnen, müssen
wir f als zweistelliges Prädikat, sagen wir sumrez/2 definieren, wobei sumrez(N,S)
bedeutet, dass S = f (N) ist. Definieren Sie zunächst das Prädikat sumrez/2 durch
Rekursion! Dann definieren Sie ein Prädikat sumrezakk/2, das dasselbe Ergebnis wie
sumrez/2 liefern soll, aber mit Tail-Recursion unter Verwendung eines Akkumulators!
Hierzu müssen Sie ein dreistelliges Hilfsprädikat, sagen wir sumrezakk1/3 verwenden,
wobei sumrezakk1(N,A,S) bedeutet, dass S = A+f (N) ist. Dabei ist A der Inhalt des Akkumulators. Stellen Sie eine Anfrage zur Berechnung von f (1 000 000) mit sumrezakk/2
sowie mit sumrez/2! Wie verhält sich Prolog in beiden Fällen?
Abzugeben: Programm, Anfragen, Text
22

Download Report