Direkt zum InhaltDirekt zur SucheDirekt zur Navigation
▼ Zielgruppen ▼

Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Logik in der Informatik

Prolog Übung

zur Vorlesung Logik in der Informatik



Aktuelles

Die erste Prolog Übung findet am 28.10.21 statt.


Abgabehinweise

Abgabehinweise für die -digitale- Abgabe der Prolog-Übungsaufgaben über moodle (ab Übungsblatt 3).

Die Abgabe der Datei mit dem Prolog-Quellcode muss den Namen blattx.pl tragen, wobei x durch die aktuelle Blattnummer ersetzt wird. So sollte die Datei für die Abgabe von Aufgabe 4 von Blatt 3 den Namen blatt3.pl tragen.

In jeder Abgabe soll das Prädikat matnr/1 exakt für Ihre Matrikelnummer gelten. Wenn Sie also die Matrikelnummer 123456 haben, soll Prolog auf die Anfrage ?- matnr(X). mit X = 123456. antworten. Wird die Datei über einen moodle-Account abgegeben, werden frühere Abgaben für diese Aufgabe überschrieben.

Beachten Sie, dass wir Ihre Bearbeitung dieser Aufgaben nur dann bewerten, wenn sich der abgegebene Prolog-Quellcode von SWI-Prolog auf gruenau6 ohne Fehlermeldungen laden lässt und die Abarbeitung gegebener Beispielanfragen nicht länger als 10 Sekunden dauert!

Korrekturanmerkungen zu Ihren Prolog-Abgaben können in Moodle unter Bewertungen (in der Navigationsleiste) eingesehen werden.


Downloads

Hier finden Sie zu gegebener Zeit die für die Lösung einzelner Aufgaben benötigten Dateien:

  • Die für Blatt 7 (und folgende) benötigte Datei al.pl

Beispiele aus der Übung


Definition eines Suchbaumes:

Ein Suchbaum der Anfrage A über der Wissensbasis WB ist eine Erweiterung eines geordneten Baums dessen Knoten und Kanten Beschriftungen tragen können mit den folgenden Eigenschaften:

  • Die Wurzel ist mit A gekennzeichnet.
  • Alle Knoten sind mit einer Anfrage beschriftet, insbesondere enthalten Blätter entweder die leere Anfrage oder sind zusätzlich unterhalb der Blätter mit † gekennzeichnet.
  • Ein Blatt ist genau dann zusätzlich mit † gekennzeichnet, falls der erste Term der Anfrage (Beschriftung des Blattes) mit keinem Kopf irgendeiner Regel (bzw. Fakt) aus WB unifiziert werden kann.
  • Ist Knoten v ein Kindknoten von Knoten w, dann
    1. ) existiert eine Regel r in WB, so dass der erste Term der Anfrage (Beschriftung von w) sich mit dem Kopf von r unifizieren läßt.
    2. ) Sei r' eine Regel, entstanden aus r, bei der alle Variablen so umbenannt sind, dass sie nicht in der Anfrage vorkommen.
    3. ) Sei S die Menge der Variableninstanziierungen bei der Unifikation des Kopfes von r' mit dem ersten Term der Anfrage (von w).
    4. ) Die Beschriftung von v entsteht durch Ersetzen des ersten Terms der Anfrage von w durch den Körper der umbenannten Regel r' und der Ersetzung von Variablen entsprechend S.
    5. ) Die Instanziierungen der Variablen des ersetzten Terms der Anfrage stehen an der Kante von w nach v.
  • Knoten v mit Beschriftung A besitzt für jede Regel r, deren Kopf sich mit dem ersten Term der Anfrage A unifizieren läßt, einen Kindknoten. Die Reihenfolge der Kindknoten, wird durch die Reihenfolge der Vorkommen der angewendeten Regeln in WB bestimmt.


Woche 01

 

01-01.pl
joker_verdaechtig :-geld_verbrannt,lachgas.
geld_verbrannt.
lachgas.

 

01-02.pl
woman(mia).
woman(jody).
woman(yolanda).
loves(vincent, mia).
loves(marsellus, mia).
playsAirGuitar(jody).
party.

 

01-03.pl
loves(ramona,roxy).
loves(ramona,todd).
time_flies(_).
ramonasEvilExes(lucas).
ramonasEvilExes(X) :- time_flies(X), loves(ramona,X).
fights(knives,X):-loves(X,scott).
fights(scott,X):- ramonasEvilExes(X).

 

01-04.pl
loves(ramona,scott).
loves(ramona,roxy).
loves(ramona,todd).
time_flies(_).
ramonasEvilExes(lucas).
ramonasEvilExes(X) :- time_flies(X), loves(ramona,X).
fights(knives,X):-loves(X,scott).
fights(scott,X):- ramonasEvilExes(X).

 

 


Woche 02

 

02-01.pl
good_dancer(vincent).
loves(mia,X) :- good_dancer(X).
kills(marsellus,X) :- loves(mia,X).

 

02-02.pl
f(a).
f(b).
g(a).
g(b).
h(b).
k(X) :- f(X), g(X), h(X).

 

Programmieren mit Unifikation:

Aufgabe 2.4 aus [BBS]

Die Worte werden dabei wie folgt in der Wissensbasis repräsentiert:

 

words.pl
word(astante, a,s,t,a,n,t,e).
word(astoria, a,s,t,o,r,i,a).
word(baratto, b,a,r,a,t,t,o).
word(cobalto, c,o,b,a,l,t,o).
word(pistola, p,i,s,t,o,l,a).
word(statale, s,t,a,t,a,l,e).

 

Programmieren mit Nicht-Unifizierbarkeit:

 

Aufgabe von Lucas Heimberg aus WS16/17

 


Woche 03

 

03-01a.pl
kind(anne, brigitte).
kind(brigitte, carolin).
kind(carolin, donna).
kind(donna, emilie).

nachkomme(X, Y) :- kind(X, Y).
nachkomme(X, Y) :- kind(X, Z), nachkomme(Z, Y).

 

03-01b.pl
kind(anne, brigitte).
kind(brigitte, carolin).
kind(carolin, donna).
kind(donna, emilie).

nachkomme(X, Y) :- kind(X, Z), nachkomme(Z, Y).
nachkomme(X, Y) :- kind(X, Y).

 

03-01c.pl
kind(anne, brigitte).
kind(brigitte, carolin).
kind(carolin, donna).
kind(donna, emilie).

nachkomme(X, Y) :- nachkomme(Z, Y), kind(X, Z).
nachkomme(X, Y) :- kind(X, Y).

 

03-01d.pl
kind(anne, brigitte).
kind(brigitte, carolin).
kind(carolin, donna).
kind(donna, emilie).

nachkomme(X, Y) :- kind(X, Y).
nachkomme(X, Y) :- nachkomme(Z, Y), kind(X, Z).

 

03-02.pl
numeral(0).
numeral(succ(X)) :- numeral(X).

 

add.pl
double(0, 0).
double(succ(X),succ(succ(Y))) :- double(X,Y).

add(0,Y,Y).
add(succ(X),Y,succ(Z)):- add(X,Y,Z).

greater(succ(_),0).
greater(succ(X),succ(Y)):-greater(X,Y).

 


Woche 04

 

 

swap.pl
swap(leaf(X), leaf(X)).
swap(tree(L, R), tree(Rs, Ls)) :- swap(L, Ls), swap(R, Rs).

 

04-01.pl
element(X,[X|_]).
element(X,[_|T]) :- element(X,T).

 

04-02.pl
invert([],[]) .
invert([a|T1],[b|T2]) :- invert(T1,T2).
invert([b|T1],[a|T2]) :- invert(T1,T2).

evenElements([], []).
evenElements([_, X|T1], [X|T2]) :- evenElements(T1,T2).

 


Woche 05

 

05-01.pl
distance(point(X1, Y1), point(X2, Y2), D) :- D is sqrt((X2 - X1)**2 + (Y2 - Y1)**2).

 

05-02.pl
laenge([] , 0) .
laenge([_|T],L) :- laenge(T,LT),L is LT + 1.

 

05-03.pl
laenge([],A,A).
laenge([_|T],A,N) :- AT is A + 1 , laenge(T,AT,N).
laenge(L, N) :- laenge(L,0,N).

 

05-04.pl
prod(L, P) :- prod(L, 1, P).
prod([], A, A).
prod([H|T], A, P) :- A2 is A * H, prod(T, A2, P).

 

05-05.pl
max([], A, A).
max([H|T], A, MT) :- H > A, max(T, H, MT).
max([H|T], A, MT) :- H =< A, max(T, A, MT).
max([H|T], M) :- max(T, H, M).

 

Offen: Der Klassiker der Rekursion

Die Fakultät n! einer natürlichen Zahl n ist definiert durch:

Definieren Sie

  • ein Prädikat fak/2, dass bei Anfrage fak(X,Y) die Fakultät von X mit Y unifiziert.
  • ein Prädikat fakAcc/2, dass äquivalent zu fak/2 ist und "End-Rekursiv” realisiert.

 


Woche 06

 

06-01.pl
% verkettet
verkettet([], Y, Y).
verkettet([H|T], Y, [H|T2]) :- verkettet(T, Y, T2).

% praefix
praefix(X, Y) :- verkettet(X, _, Y).

% suffix
suffix(X, Y) :- verkettet(_, X, Y).

 

06-02.pl
% ohne Akkumulator
umgedreht([], []).
umgedreht([H|T], R) :-
  umgedreht(T, RT), verkettet(RT, [H], R).

% mit Akkumulator
umgedrehtAcc([], A, A).
umgedrehtAcc([H|T], A, R) :-
  umgedrehtAcc(T, [H|A], R).
umgedrehtAcc(L, R) :- umgedrehtAcc(L, [], R).

% verkettet
verkettet([], Y, Y).
verkettet([H|T], Y, [H|T2]) :- verkettet(T, Y, T2).

 

06-03.pl
not_member(_, []).
not_member(X, [H|T]) :- X \= H, not_member(X, T).

 

06-04.pl
atree(leaf(_)).
atree(tree(L, R)) :- atree(L), atree(R).

 

sumLabels.pl
sum_labels(leaf(N), N).
sum_labels(tree(L, R), N) :-
  sum_labels(L, NL), sum_labels(R, NR),
  N is NL + NR.

 

06-05.pl
lookup(X,[(X,Y)|_],Y).
lookup(X,[_|T],Y) :- lookup(X,T,Y).

 

06-06.pl
node(a). node(b). node(c). node(d). node(e).
node(f). node(g). node(h). node(i). node(j).

edge(a, j).
edge(c, e).
edge(d, e).
edge(e, f).
edge(f, g).
edge(g, h). edge(g, j).
edge(h, g). edge(h, i).
edge(i, a). edge(i, b). edge(i, j).
edge(j, b). edge(j, c). edge(j, d). edge(j, f).

erreichbar(X, X).
erreichbar(X, Y) :-
  edge(X, Z), erreichbar(Z, Y).

% Try: ?- erreichbar(a, g).
% Try: ?- erreichbar(h, a).

 

06-06a.pl
node(a). node(b). node(c). node(d). node(e).
node(f). node(g). node(h). node(i). node(j).

edge(a, j).
edge(c, e).
edge(d, e).
edge(e, f).
edge(f, g).
edge(g, h). edge(g, j).
edge(h, g). edge(h, i).
edge(i, a). edge(i, b). edge(i, j).
edge(j, b). edge(j, c). edge(j, d). edge(j, f).

erreichbarMem(X, Y) :- erreichbar(X, Y, [X]).
erreichbar(X, X, _) .
erreichbar(X, Y, Pfad) :-
  edge(X, Z), not_member(Z, Pfad),
  erreichbar(Z, Y, [Z|Pfad]).

% Try: ?- erreichbarMem(a, g).
% Try: ?- erreichbarMem(h, a).

% not_member

not_member(_, []).
not_member(X, [H|T]) :- X \= H, not_member(X, T).

 


Literatur

[BBS] Patrick Blackburn, Johan Bos, Kristina Striegnitz, Learn PROLOG Now!. Kings College Publications, 2006. Online version.
 

Browser-Erweiterung

Matthias Vogt hat eine Browser-Erweiterung für Chromium [installieren] und Firefox [installieren] veröffentlicht, welche der Online-Version von Learn PROLOG Now! ein moderneres Aussehen verleiht. Die Quellen sind auf GitHub [hier] verfügbar.

[SS] Ehud Shapiro, Leon Sterling, The Art of PROLOG: Advanced Programming Techniques. 2nd Edition, MIT Press, 1994.

Programmierresourcen

SWI-Prolog. Ein Kurzanleitung für den Einstieg in SWI-Prolog finden Sie hier.