P1 WS2004/2005
Musterlösung zu Aufgabenblatt 5 - v0.3
Aufgabe 1
---------
a) Aufgabe: p(X,f) p(g,Y)
X=g, Y=f - Erfolgreich
b) Aufgabe: r(a(b(M),N)) r(a(b(K),m))
N=m, K=M - Erfolgreich
c) Aufgabe: h(A,c(C),C) h(B,B,a)
B=C(a), C=a, A=B=C(a) - Erfolgreich
d) Aufgabe: f(a(X),b,b(X)) f(a(Y),Y,b(a))
X=a, Y=b, aber X=Y ist nicht erfüllt - Nicht erfolgreich
e) Aufgabe: a(i(i(i(p))),i(P)) a(i(P),i(i(i(p))))
P=i(i(p)) - Erfolgreich
f) Aufgabe: t(T,t(T)) t(S,S)
S=T=t(T) - Erfolgreich, aber rekursiv
Aufgabe 2
---------
a)
% even(A). --ergibt yes, wenn A gerade ist.
% es werden immer genau zwei "Vorgänger" mit s(s(X)) gesucht
even(0).
even(s(s(X))):-even(X).
b)
% odd(A). --ergibt yes, wenn A ungerade ist.
% ähnlich wie bei even, werden auch hier immer zwei "Vorgänger"
% mit s(s(x)) gesucht, % aber der Rekursionsabschluss ist
% nicht 0, sondern s(0), es folgt also immer noch ein
% letzter, sozusagen "ungrader Schritt".
odd(s(0)).
odd(s(s(X))):-odd(X).
c)
% le(A,B). -- ergibt yes, wenn A kleiner gleich B ist.
le(X,X).
le(X,s(Y)):-le(X,Y).
%%% und gleich noch die Variante mit Typprüfung. Dazu wird
%%% zuerst der Typtest aus dem Script mit verwendet:
% peano(Term). -- Term ist ein Peano-Term.
peano(0).
peano(s(X)):-peano(X).
% le2(A,B) -- ergibt yes, wenn A kleiner gleich B ist und
% beides Peano-Terme sind.
le2(X,X):-peano(X).
le2(X,s(Y)):-le2(X,Y).
%%% Der Vergleich beider Varianten zeigt, dass le/2 den Vorteil
%%% hat, dass es schneller zu einem Ergebnis kommt, da der Fall,
%%% dass zwei gleiche Terme übergeben werden, sofort zu yes
%%% führt. In diesem Fall (der in der Rekursion immer auftritt,
%%% falls A <= B gilt), muss bei le2/2 noch die Rekursion von
%%% peano/1 durchgelaufen werden. Dadurch wird allerdings erreicht,
%%% dass nur Peano-Zahlen yes ergeben können, und nicht etwa auch
%%% le(s(muell),s(muell)).
%%% Interessant ist auch die Reaktion auf die vollständig
%%% uninstanziierte Anfrage: le/2 liefert nur teilinstanziierte
%%% Antworten, während le2/2 nur die vollständig instanziierten
%%% Fälle von Gleichheit erreicht.
d)
%%% Gefordert war eine Multiplikation, also sollte auch eine
%%% Multiplikation implementiert werden.
%add(Summand1,Summand2,Summe) aus dem Script:
add(0,X,X).
add(s(X),Y,s(R)):-add(X,Y,R).
%mult(A,B,C). -- multipliziert die Peanozahlen A und B, das
% Ergebnis ist C
% X*0=0
mult(X,0,0).
% Rekursionsabschluss: X*1=X
mult(X,s(0),X).
% sonst führen wir die Multiplikation auf die Addition zurück
% 5 Rekursion: x*s(y)= (x*y) + x, dazu führen wir den Zwischenwert
% im "[[IntermediateResult]]" mit.
mult(X,s(Y),R):- mult(X,Y,IR),add(X,IR,R).
%%% Nur für den Fall das jemand wissen will wie eine
%%% Subtraktion ginge: sub ist dann eigentlich dasselbe, wie
%%% add aus dem Script, nur die Argumentpositionen haben
%%% sich verändert. Man könnte schreiben: sub(X,Y,R):-add(Y,R,X).
%sub(A,B,C). -- subtrahiert die Peanozahlen A und B, das
% Ergebnis ist C oder 'no', wenn A-B<0.
sub(X,0,X).
sub(s(X),s(Y),R):-sub(X,Y,R).
Der Test ergab für Teilaufgabe a:
---------------------------------
?- even(0).
Yes
?- even(s(0)).
No
?- even(X).
X = 0 ;
X = s(s(0)) ;
X = s(s(s(s(0))))
Yes
Der Test ergab für Teilaufgabe b:
---------------------------------
?- odd(0).
No
?- odd(s(0)).
Yes
?- odd(X).
X = s(0) ;
X = s(s(s(0))) ;
X = s(s(s(s(s(0)))))
Yes
Der Test ergab für Teilaufgabe c:
---------------------------------
?- le(s(0),s(s(0))).
Yes
?- le(s(s(0)),s(s(0))).
Yes
?- le(s(s(s(0))),s(s(0))).
No
?- le(s(s(s(0))),s(s(s(0)))).
Yes
?- le(s(s(s(0))),s(s(s(s(0))))).
Yes
?- le(s(s(s(0))),s(s(s(s(s(0)))))).
Yes
?- le(0,0).
Yes
?- le(0,s(0)).
Yes
?- le(s(0),0).
No
?- le(s(s(0)),X).
X = s(s(0)) ;
X = s(s(s(0))) ;
X = s(s(s(s(0)))) ;
X = s(s(s(s(s(0))))) ;
X = s(s(s(s(s(s(0)))))) ;
X = s(s(s(s(s(s(s(0))))))) ;
X = s(s(s(s(s(s(s(s(0)))))))) ;
X = s(s(s(s(s(s(s(s(s(0))))))))) ;
X = s(s(s(s(s(s(s(s(s(s(...)))))))))) ;
Yes
?- le(X,s(s(s(0)))).
X = s(s(s(0))) ;
X = s(s(0)) ;
X = s(0) ;
X = 0 ;
No
?- le(s(muell),s(muell)).
Yes
Und nun le2:
------------
?- le2(0,0).
Yes
?- le2(s(0),s(s(0))).
Yes
?- le2(s(s(s(0))),s(s(0))).
No
?- le2(muell,s(muell)).
No
?- le2(s(muell),s(muell)).
No
Und nun noch der Trace:
-----------------------
?- trace(le2).
% le2/2: [call, redo, exit, fail]
Yes
[debug] ?- trace(peano).
% peano/1: [call, redo, exit, fail]
Yes
[debug] ?- le2(X,Y).
T Call: (7) le2(_G415, _G416)
T Call: (8) peano(_G415)
T Exit: (8) peano(0)
T Exit: (7) le2(0, 0)
X = 0
Y = 0 ;
T Redo: (8) peano(_G415)
T Call: (9) peano(_G480)
T Exit: (9) peano(0)
T Exit: (8) peano(s(0))
T Exit: (7) le2(s(0), s(0))
X = s(0)
Y = s(0) ;
T Redo: (9) peano(_G480)
T Call: (10) peano(_G482)
T Exit: (10) peano(0)
T Exit: (9) peano(s(0))
T Exit: (8) peano(s(s(0)))
T Exit: (7) le2(s(s(0)), s(s(0)))
X = s(s(0))
Y = s(s(0))
Yes
Der Test ergab für Teilaufgabe d:
--------------------------------
?- mult(s(s(s(s(0)))),s(s(s(s(0)))),X).
X = s(s(s(s(s(s(s(s(s(s(...))))))))))
Yes
?- mult(s(s(s(s(0)))),s(s(s(s(0)))),X),peano2int(X,N).
X = s(s(s(s(s(s(s(s(s(s(...))))))))))
N = 16
Yes
?- mult(s(s(s(s(0)))),s((0)),X),peano2int(X,N).
X = s(s(s(s(0))))
N = 4
Yes
?- mult(s(s(s(s(0)))),s(s(0)),X),peano2int(X,N).
X = s(s(s(s(s(s(s(s(0))))))))
N = 8
Yes
?- mult(s(s(s(s(0)))),0,X),peano2int(X,N).
X = 0
N = 0
Yes
Aufgabe 3
---------
peano2int(0,0).
peano2int(s(Peano),Number):-peano2int(Peano,Predecessor),Number is Predecessor+1.
Test:
(Peano -> Integer)
?- peano2int(s(s(s(s(0)))),X).
X = 4 ;
No
(Integer -> Peano)
?- peano2int(X,5).
X = s(s(s(s(s(0))))) ;
^C
Action (h for help) ? abort
% Execution Aborted
Es wird endlos weitergesucht. Das Prädikat ist also nicht
richtungsunabhängig.
Aufgabe 4
---------
In der Vorlesung und den Übungen sind u.a. die folgenden rekursiven
Bezugnahmen aufgetaucht:
- Mengen und deren rekursive Definition in EBNF
- Rekursive Datenstrukturen wie z.B. Peano-Zahlen
Diese beziehen sich nur auf die syntaktische Form.
- Rekursive Prädikate
Dieses sind rekursive Berechnungsvorschriften.