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:


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:

crosswd_slide.jpg

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:

 

4col_slide.png

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

 

trees.png

 

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:

fakultaet.png

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).

 


Woche 07

 

07-01.pl
distribute(A * (B + C), A*B + A*C).
distribute((A + B)*C, A*C + B*C).

 

07-02.pl
numbers(X, [X]) :- number(X).
numbers(L + R, X) :-
  numbers(L, XL), numbers(R, XR),
  append(XL, XR, X).
numbers(L * R, X) :-
  numbers(L, XL), numbers(R, XR),
  append(XL, XR, X).

 

07-03.pl
complexterm(X) :- nonvar(X), X=..[_, _|_].

 

07-04.pl
sym(N, A) :-
  atom_codes(N, SN),
  atom_codes("x", XN),
  append(XN, SN, S),
  atom_codes(A, S).

 


Woche 08

 

08-01.pl
s(X, Y) :- q(X, Y).
s(0, 0).
q(X, Y) :- i(X), i(Y).
q(3, 3).
i(1).
i(2).

 

08-02.pl
s(X, Y) :- q(X, Y).
s(0, 0).
q(X, Y) :- i(X), !, i(Y).
q(3, 3).
i(1).
i(2).

 

08-03.pl
max(X, Y, Y) :- X =< Y.
max(X, Y, X) :- X > Y.

 

08-04.pl
max(X, Y, Y) :- X =< Y, !.
max(X, Y, X) :- X > Y.

 

08-05.pl
max(X, Y, Y) :- X =< Y, !.
max(X, _, X).

% Try
%
% ?-max(2,3,X).
%
% ?- max(3,2,X).
%
% ?- max(2,3,2).

 

08-06.pl
max(X, Y, Z) :- X =< Y, !, Y = Z.
max(X, _, X).

 

08-07.pl
mag(etienne,X) :- fach2(X), !, fail .
mag(etienne,X) :- schule(X).

schule(X) :- fach1(X).
schule(X) :- fach2(X).
schule(X) :- non_fach(X).

non_fach(hofpause).
non_fach(mittagspause).
non_fach(kleine_pause).

fach1(sport).
fach1(musik).
fach1(kunst).

fach2(deutsch).
fach2(englisch).

 

08-08.pl
neg(Ziel) :- Ziel, !, fail.
neg(_).

 

08-07a.pl
mag(etienne,X) :- schule(X), \+ fach2(X).

schule(X) :- fach1(X).
schule(X) :- fach2(X).
schule(X) :- non_fach(X).

non_fach(hofpause).
non_fach(mittagspause).
non_fach(kleine_pause).

fach1(sport).
fach1(musik).
fach1(kunst).

fach2(deutsch).
fach2(englisch).

 

08-09.pl
not_member(X, L) :- \+ member(X, L).

 

 


Woche 09

 

09-01.pl
sun(X) :-
    retract(sad(X)),
    assert(happy(X)).

 

Offen: Der Klassiker der Rekursion

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

fakultaet.png

Definieren Sie

  • ein Prädikat fak/2, dass bei Anfrage fak(X,Y) die Fakultät von X mit Y unifiziert. Verwenden Sie eine Lookup-Tabelle um bereits berechnete Funktionswerte wieder zu verwenden.

 

09-03.pl
child(martha, charlotte).
child(charlotte, caroline).
child(caroline, laura).
child(laura, rose).
descend(X, Y) :- child(X, Y).
descend(X, Y) :- child(X, Z), descend(Z, Y).

% Try
%
% ?- descend(martha, X).
%
% ?- findall(X, descend(martha, X), L).

 


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.


  • ein Prädikat fak/2, dass bei Anfrage fak(X,Y) die Fakultät von X mit Y unifiziert. Nutzen Sie eine Lookup-Tabelle für die Wiederverwendung bereits berechneter Funktionswerte (Stichpunkt: Memoization).