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
  • Die für Blatt 9 benötigte Datei kinodb.pl
  • Übungsblatt 10: die Module al_def (Grundlegende Definitionen für aussagenlogische Formeln, speichern), al_literals (Literale, speichern) und al_nf (Normalformen, speichern).
  • Übungsblatt 12: die Datei unit_propagation.pl (speichern) und pure_literal.pl (speichern).
  • Übungsblatt 13: die Datei dpll.pl (speichern) und die Datei tseitin.pl (speichern).


    Weiterhin finden Sie nachfolgend Probleminstanzen für SAT-Solver im DIMACS-Format. Wer mehr zu den Beispielen 2--x wissen möchte, kann sich unter http://massimolauria.net/cnfgen/ über die Herkunft der Formeln informieren. Ich habe einige Instanzen mal auf gruenau6 mit unserer Implementation laufen lassen und man kann sehr gut ablesen, wie sich unser Solver so mit steigendem n klarkommt... (Speichern durch Anklicken des Dateinamens)
     
      Name der Datei benötigte Zeit in Sekunden Anzahl der Ableitungen
    Beispiel 2.64 der VL VLBeispiel264.cnf 0.002 seconds 2,814 inferences
    Pebbling formula of:
    Pyramid of height n
    pyramid10.cnf 0.008 seconds 28,386 inferences
      pyramid15.cnf 0.029 seconds 110,095 inferences
      pyramid50.cnf 1.631 seconds 9,668,024 inferences
    Pigeonhole principle formula
    for n+1 pigeons and n holes
    php4_3.cnf 0.003 seconds 10,439 inferences
      php5_4.cnf 0.010 seconds 64,762 inferences
      php6_5.cnf 0.085 seconds 406,535 inferences
      php7_6.cnf 0.489 seconds 2,691,573 inferences
      php8_7.cnf 2.878 seconds 19,514,171 inferences
      php9_8.cnf 22.321 seconds 157,722,886 inferences
      php10_9.cnf 166.006 seconds 1,423,024,293 inferences
      php11_10.cnf 2124.783 seconds 14,237,397,770 inferences
      php12_11.cnf 22926.179 seconds   ~6h22 156,624,865,223 inferences
      php13_12.cnf 275571.056 seconds   ~3T4h33 1,879,522,854,956 inferences
      php14_13.cnf ... ..
      php15_14.cnf ... ..

    Zur Info: aktuelle SAT-Solver brechen auch ab php13_12 ein.

     


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

 


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:

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

 


Woche 10

 

10-01.pl
summe(S, N) :-
    read(S, X),
    \+ X = end_of_file, !,
    summe(S, N2), N is N2 + X.

summe(_, 0).

 

printActors.pl
:- ensure_loaded([kinodb]).

printActors(F) :-
    setof(S, R^film(F, R, S), L),
    displayList(L).
displayList([]) :- nl.
displayList([X|L]) :-
    write(X), tab(1), displayList(L).

% test:
% ?- printActors('Casablanca').
% Humphrey Bogart Ingrid Bergmann
% true.

 

printMovies.pl
:- ensure_loaded([kinodb]).

printMovies(R) :-
    setof(F, S^film(F, R, S),L),
    displayList(L).

displayList([]) :- nl.
displayList([X|L]) :-
    write(X), nl, displayList(L).

% test:
% ?- printMovies('Ridley Scott').
% Alien
% Blade Runner

 


Woche 11

 

11-01.pl
s(Z) :- np(X), vp(Y), append(X,Y,Z).
np(Z) :- det(X), n(Y), append(X,Y,Z).
vp(Z) :- v(X), np(Y), append(X,Y,Z).
vp(Z) :- v(Z).
det([a]).
det([the]).
n([woman]).
n([man]).
v([shoots]).

 

11-02.pl
s(Z) :- append(X,Y,Z), np(X), vp(Y).
np(Z) :- append(X,Y,Z), det(X), n(Y).
vp(Z) :- append(X,Y,Z), v(X), np(Y).
vp(Z) :- v(Z).
det([a]).
det([the]).
n([woman]).
n([man]).
v([shoots]).

 

11-03.pl
s(X, Z) :- np(X, Y), vp(Y, Z).
np(X, Z) :- det(X, Y), n(Y, Z).
vp(X, Z) :- v(X, Y), np(Y, Z).
vp(X, Z) :- v(X, Z).
det([the|W], W).
det([a|W], W).
n([woman|W], W).
n([man|W], W).
v([shoots|W], W).

 

11-04.pl
s --> np, vp.
np --> det, n.
vp --> v, np.
vp --> v.
det --> [the].
det --> [a].
n --> [woman].
n --> [man].
v --> [shoots].

 

11-05.pl
s --> np, vp.
np --> det, ne.
ne --> n.
ne --> a, ne.
vp --> v, np.
det --> [the].
det --> [a].
n --> [dog].
n --> [bone].
n --> [mouse].
n --> [cat].
v --> [ate].
v --> [chases].
a --> [big].
a --> [brown].
a --> [lazy].

 

11-06.pl
essen --> essen, ['mit'], zutat.
essen --> zutat.
zutat --> ['Kartoffeln'].
zutat --> ['Sahne'].
zutat --> ['Zwiebeln'].
zutat --> ['Schokoladenstreusel'].

 

11-07.pl
essen --> zutat.
essen --> essen, ['mit'], zutat.
zutat --> ['Kartoffeln'].
zutat --> ['Sahne'].
zutat --> ['Zwiebeln'].
zutat --> ['Schokoladenstreusel'].

 

11-08.pl
s --> [].
s --> l, s, r.
l --> [a].
r --> [b].

 


Woche 12

 

12-01.pl
s --> np(subject), vp.
np(_) --> det, n.
vp --> v, np(object).
vp --> v.
det --> [the].
det --> [a].
n --> [woman].
n --> [man].
v --> [shoots].

np(X) --> pro(X).
pro(subject) --> [he].
pro(subject) --> [she].
pro(object) --> [him].
pro(object) --> [her].

 

12-02.pl
s(s(NP,VP)) --> np(NP), vp(VP).
np(np(DET, N)) --> det(DET), n(N).
vp(vp(V, NP)) --> v(V), np(NP).
vp(vp(V)) --> v(V).
det(det(the)) --> [the].
det(det(a)) --> [a].
n(n(woman)) --> [woman].
n(n(man)) --> [man].
v(v(shoots)) --> [shoots].

 

12-03.pl
s(N) --> as(N), bs(N), cs(N).
as(0) --> [].
as(succ(N)) --> [a], as(N).
bs(0) --> [].
bs(succ(N)) --> [b], bs(N).
cs(0) --> [].
cs(succ(N)) --> [c], cs(N).

 

12-04.pl
preorder(node(T, nil, nil), [T]) :- !.
preorder(node(T, L, R), [T|X]) :-
   preorder(L, LX), preorder(R, RX),
   append(LX, RX, X).

 

12-05.pl
bt(node(T, nil, nil)) --> [T].
bt(node(T, L, R)) --> [T], bt(L), bt(R).

 

12-06.pl
lex(the, det). lex(a, det).
lex(woman, n). lex(man, n).
lex(shoots, v).

s --> np, vp.
np --> det, n.
vp --> v, np.
vp --> v.
det --> [Wort], { lex(Wort, det) }.
n --> [Wort], { lex(Wort, n) }.
v --> [Wort], { lex(Wort, v) }.

 

12-07.pl
bst(node(Z, nil, nil), Z, Z) -->
   [Z], { integer(Z) }.
bst(node(Z, L, R), LMin, RMax) -->
   [Z], { integer(Z) },
   bst(L, LMin, LMax),
   bst(R, RMin, RMax),
   { LMax < Z, Z < RMin }.

 


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