© 2001
François Bry
Dieses Lehrmaterial wird ausschließlich zur privaten Verwendung
angeboten. Eine nichtprivate Nutzung (z.B. im Unterricht oder eine
Veröffentlichung von Kopien oder Übersetzungen) dieses Lehrmaterials
bedarf der Erlaubnis des Autors.
delete
vorlesung(martin, wirsing, info_1, mittwoch,
14, 16, theresienstrasse, e51).
vorlesung(francois, bry, info-1, dienstag,
11, 13, theresienstrasse, 138).
vorlesung(francois, bry, info-1, donnerstag,
9, 11, theresienstrasse, 138).
vorlesung(dozent(martin, wirsing),
info_1,
zeit(mittwoch, 14, 16),
ort(theresienstrasse, e51)).
vorlesung(dozent(francois, bry),
info_1,
zeit(dienstag, 11, 13),
ort(theresienstrasse, 138)).
vorlesung(dozent(francois, bry),
info_1,
zeit(donnerstag, 9, 11),
ort(theresienstrasse, 138)).
dozent(Dozent, Vorlesung) :-
vorlesung(Dozent, Vorlesung, _, _).
arbeitsplan(Dozent, Tag) :-
vorlesung(Dozent, _, zeit(Tag, _, _), _).
besetzt(Raum, Tag, Zeit) :-
integer(Zeit),
vorlesung(_, _, zeit(Tag, Von, Bis), Raum),
Von =< Zeit, Zeit =< Bis.
besetzt(Raum, Tag, Zeitluecke) :-
Zeitluecke = [Von, Bis],
vorlesung(_, _, zeit(Tag, Von, Bis), Raum).
f(a)
und f(a, b, c).
verbunden(X, Y) :- kante(X, Y).
verbunden(X, Y) :- kante(X, Z), verbunden(Z, Y).
kante(k1, k2).
kante(k2, k3).
kante(k3, k1).
verbunden(X, Y) :- kante(X, Y).
verbunden(X, Y) :- verbunden(Z, Y), kante(X, Z).
kante(k1, k2).
kante(k2, k3).
kante(k3, k1).
verbunden(X, Y) :- verbunden(Z, Y), kante(X, Z).
verbunden(X, Y) :- kante(X, Y).
kante(k1, k2).
kante(k2, k3).
kante(k3, k1).
verbunden(X, Y) :- kante(X, Z), verbunden(Z, Y).
verbunden(X, Y) :- kante(X, Y).
kante(k1, k2).
kante(k2, k3).
kante(k3, k1).
natuerliche_zahl(null).
natuerliche_zahl(nf(Z)) :- natuerliche_zahl(Z).
:- natuerliche_zahl(Z).
Z = null More? (;) ;
Z = nf(null) More? (;) ;
Z = nf(nf(null)) More? (;) ;
Z = nf(nf(nf(null))) More? (;) ;
Z = nf(nf(nf(nf(null)))) More? (;)
:-
plus(null, Y, Y) :- natuerliche_zahl(Y).
plus(nf(X), Y, nf(Z)) :- plus(X, Y, Z).
mal(null, Y, null) :- natuerliche_zahl(Y).
mal(nf(X), Y, Z) :- mal(X, Y, XY), plus(XY, Y, Z).
plus(X, null, X) :- natuerliche_zahl(X).
zu der Definition von plus
im Programm P28a hinzufügen.
Das wäre korrekt, aber redundant:
auf die Anfrage plus(null,null,Z)
würde die Antwort Z = null
einmal mit der bisherigen ersten Regel
und einmal mit der zusätzlichen Regel berechnet.
Ebenso überlappt sich die zusätzliche Regel mit der letzten Regel.
plus(X, nf(Y), nf(Z)) :- plus(X, Y, Z).
und die Definition wäre immer noch korrekt, wenn auch redundant.
Das gleiche gilt, wenn die obige Regel nicht als Ersatz für
die letzte dient, sondern zusätzlich als vierte Regel hinzugefügt
wird, nur ist die Redundanz dann noch größer.
fakultaet(null, nf(null)).
fakultaet(nf(Z), F) :-
fakultaet(Z, FZ), mal(nf(Z), FZ, F).
is:
fakultaet(0, 1).
fakultaet(Nplus1, FakNplus1) :-
N is Nplus1 - 1,
fakultaet(N, FakN),
FakNplus1 is FakN * Nplus1.
fakultaet(0, 1).
fakultaet(Nplus1, FakNplus1) :-
Nplus1 >= 1,
N is Nplus1 - 1,
fakultaet(N, FakN),
FakNplus1 is FakN * Nplus1.
. besonders unterstützt,
das sogenannte Listenfunktionsymbol.
[], oder
aus einem Paar der Gestalt .(Kopf, Rumpf)
wobei Rumpf eine Liste ist. Die Liste
.(a, .(b, .(c, []))) kann der Einfachheit halber auch
[a, b, c] dargestellt werden.
.(Kopf, Rumpf) kann auch
[Kopf | Rumpf] dargestellt werden.
:- atom([]).
yes.
:- X = .(a, []).
X = [a]
yes.
:- X = .(a, .(b, .(c, []))) .
X = [a, b, c]
yes.
:- X = .(a, R).
X = [a | R]
R = R
yes.
:- X = .(a, .(b, .(c, R))) .
X = [a, b, c | R]
R = R
yes.
:- [a, b, c] = [K | R].
K = a
R = [b, c]
yes.
:- [a, b, c, d, e] = [K1, K2 | R].
K1 = a
K2 = b
R = [c, d, e]
yes.
:- [H | T] = .(K, R).
H = K
T = R
K = K
R = R
yes.
:- [] = [K | R].
no (more) solution.
:-
tahiti(bry): % eclipse
ECRC Common Logic Programming System [sepia opium megalog]
Version 3.4.5, Copyright ECRC GmbH, Thu Jun 16 11:08 1994
[eclipse 1]: [user].
liste([]).
liste([K | R]) :- liste(R).
*** Warning: Singleton variables in clause 2 of liste/1: K
user compiled traceable 168 bytes in 0.00 seconds
yes.
[eclipse 2]: liste([a, b, c]).
yes.
[eclipse 3]: liste(L).
L = [] More? (;) ;
L = [K] More? (;) ;
L = [K, K] More? (;) ;
L = [K, K, K] More? (;)
yes.
[eclipse 4]:
K mehrmals in der aufgebauten Liste
vorkommt.
Die Programmklausel mit der Variablen K
wird zwar in der Tat immer wieder verwendet,
jedoch muß jedesmal eine neue Variante dieser Klausel benutzt werden,
in der K umbenannt ist in eine Variable,
die bisher nirgends vorkommt.
tahiti(bry): % eclipse
ECRC Common Logic Programming System [sepia opium megalog]
Version 3.4.5, Copyright ECRC GmbH, Thu Jun 16 11:08 1994
[eclipse 1]:
set_flag(output_mode, "QPmV").
yes.
[eclipse 2]: [user].
liste([]).
liste([K | R]) :- liste(R).
*** Warning: Singleton variables in clause 2 of liste/1: K
user compiled traceable 168 bytes in 0.00 seconds
yes.
[eclipse 3]: liste(L).
L = [] More? (;) ;
L = [K_g684] More? (;) ;
L = [K_g684, K_g692] More? (;) ;
L = [K_g684, K_g692, K_g700] More? (;)
yes.
[eclipse 4]:
member(M, [M | _]).
member(M, [_ | T]) :- member(M, T).
append([], L, L).
append([K|R], L1, [K|L2]) :- append(R, L1, L2).
:- append([a,b,c], [d, e], L).
L = [a, b, c, d, e]
yes.
:- append(L1, [d, e], [a, b, c, d, e]).
L1 = [a, b, c] More? (;) ;
no (more) solution.
:- append([a, b, c], L2, [a, b, c, d, e]).
L2 = [d, e]
yes.
:- append(L1, L2, [a, b, c, d, e]).
L1 = []
L2 = [a, b, c, d, e] More? (;) ;
L1 = [a]
L2 = [b, c, d, e] More? (;) ;
L1 = [a, b]
L2 = [c, d, e] More? (;) ;
L1 = [a, b, c]
L2 = [d, e] More? (;) ;
L1 = [a, b, c, d]
L2 = [e] More? (;) ;
L1 = [a, b, c, d, e]
L2 = []
yes.
:-
praefix(P, L) :- append(P, _, L).
suffix(S, L) :- append(_, S, L).
subliste_1(Sub, L) :- praefix(P, L), suffix(Sub, P).
subliste_2(Sub, L) :- suffix(S, L), praefix(Sub, S).
subliste_3(Sub, L) :- praefix(Sub, L).
subliste_3(Sub, [_|R]) :- subliste_3(Sub, R).
member_1(X, L) :- subliste([X], L).
naive_reverse([], []).
naive_reverse([K|L], R_K) :- naive_reverse(L,R), append(R, [K], R_K).
reverse(L, RL) :- hilfsreverse(L, [], RL).
hilfsreverse([K|R], Akk, L) :- hilfsreverse(R, [K|Akk], L).
hilfsreverse([], L, L).
reverse
< reverse([a, b, c, d], RL) >
< hilfsreverse([a, b, c, d], [], RL) >
< hilfsreverse([b, c, d], [a], RL) >
< hilfsreverse([c, d], [b, a], RL) >
< hilfsreverse([d], [c, b, a], RL) >
< hilfsreverse([], [d, c, b, a], RL) >
< hilfsreverse([], [d, c, b, a], [d, c, b, a]) >
length([], 0).
length([K|R], L1) :- length(R, L), L1 is L + 1.
delete delete(Liste, Element, NeueListe).
NeueListe ist eine Liste, die gleich wie Liste ist,
außer daß sie kein Vorkommen von Element enthält. Es soll also gelten:
delete([a,b,c], b, [a,c]).
delete([a,b,c,b], b, [a,c]).
delete([a,b,c], e, [a,b,c]).
delete([K|R], E, L) :- K = E, delete(R, E, L).
delete([K|R], E, [K|L]) :- K \= E, delete(R, E, L).
delete([], _, []).
delete([K|R], E, L) :- K = E, delete(R, E, L).
delete([K|R], E, [K|L]) :- K \= E, delete(R, E, L).
delete([], _, []).
:- delete([a, b, c], b, [a, c]).
yes.
:- delete([a, b, c], b, L).
L = [a, c] More? (;) ;
no (more) solution.
:- delete([a, b, c], d, L).
L = [a, b, c]
yes.
:- delete([a, b, d, c], E, [a, c]).
no (more) solution.
:- delete([a, b, b, c], b, [a, c]).
yes.
:- delete([a, b, b, c], E, [a, c]).
no (more) solution.
:-
delete([K|R], E, L) :- K = E, delete(R, E, L).
delete([K|R], E, [K|L]) :- delete(R, E, L), K \= E.
delete([], _, []).
:- delete([a, a, b], E, [b]).
E = a More? (;) ;
no (more) solution.
:- delete([a, b, b, c], E, [a, c]).
E = b More? (;) ;
no (more) solution.
:- delete([a, b, b, c, b, d], E, [a, c, d]).
E = b More? (;) ;
no (more) solution.
:-
\= ist die Negation von =, kann also keinen Wert
generieren. Daher wurde der Aufruf K \= E an das Ende des Rumpfes
verlegt.
:- a = f(a).
no (more) solution.
:- X = f(X).
X = f(f(f(f(f(f(f(f(f(f(f(...)))))))))))
yes.
:- p(X, X) = p(Y, f(Y)).
X = f(f(f(f(f(f(f(f(f(f(f(...)))))))))))
Y = f(f(f(f(f(f(f(f(f(f(f(...)))))))))))
yes.
:- X = f(X), X = a.
no (more) solution.
:-
X = f(X). wird kein unendlicher Term aufgebaut,
sondern lediglich der "Unifikator" {X = f(X)}. Bei der
Darstellung des Wertes von X unterbricht das PROLOG-System die Darstellung
ab einer gewissen Tiefe -- ohne natürlich dabei zu erkennen, daß es sich
um einen "zyklischen Term" handelt.
% Unifikation ohne Occur-check
unify(X, Y) :- var(X), var(Y), X = Y.
unify(X, Y) :- var(X), nonvar(Y), X = Y.
unify(X, Y) :- nonvar(X), var(Y), X = Y.
unify(X, Y) :- nonvar(X), nonvar(Y),
atomic(X), atomic(Y), X = Y.
unify(X, Y) :- nonvar(X), nonvar(Y),
zg_term(X), zg_term(Y),
unify_zg_term(X, Y).
zg_term(X) :- functor(X, F, N), N \= 0.
unify_zg_term(X, Y) :- X =.. [F|Xargumente], Y =.. [F|Yargumente],
unify_list(Xargumente, Yargumente).
unify_list([], []).
unify_list([K1|R1], [K2|R2]) :- unify(K1, K2), unify_list(R1, R2).
:- functor(f(a), F, N).
F = f
N = 1
yes.
:- functor(f(a,b,g(c,d)), F, N).
F = f
N = 3
yes.
:- functor(a, F, N).
F = a
N = 0
yes.
:- f(a) =.. [F | Argumente].
F = f
Argumente = [a]
yes.
:- f(a,b,g(c,d)) =.. [F | Argumente].
F = f
Argumente = [a, b, g(c,d)]
yes.
:- a =.. [F | Argumente].
F = a
Argumente = []
yes.
:- unify( f(X,b), f(a,Y) ).
X = a
Y = b More? (;) ;
no (more) solution.
:- unify(X, Y).
X = Y
Y = Y More? (;) ;
no (more) solution.
:- unify(a, b).
no (more) solution.
:- unify(f(X), f(a)).
X = a More? (;) ;
no (more) solution.
:- unify(f(X), f(f(X))).
X = f(f(f(f(f(f(f(f(f(f(f(...)))))))))))
yes.
:-
% Unifikation mit Occur-check -- 1
unify(X, Y) :- var(X), var(Y), X = Y.
unify(X, Y) :- var(X), nonvar(Y), not occurs_in(X, Y), X = Y.
unify(X, Y) :- nonvar(X), var(Y), not occurs_in(Y, X), X = Y.
unify(X, Y) :- nonvar(X), nonvar(Y),
atomic(X), atomic(Y), X = Y.
unify(X, Y) :- nonvar(X), nonvar(Y),
zg_term(X), zg_term(Y),
unify_zg_term(X, Y).
zg_term(X) :- functor(X, F, N), N \= 0.
unify_zg_term(X, Y) :- X =.. [F|Xargumente], Y =.. [F|Yargumente],
unify_list(Xargumente, Yargumente).
unify_list([], []).
unify_list([K1|R1], [K2|R2]) :- unify(K1, K2), unify_list(R1, R2).
occurs_in(X, Y) :- atomic(Y), !, fail.
occurs_in(X, Y) :- var(Y), !, Y == X.
occurs_in(X, [H|T]) :- !, occurs_in_list(X, [H|T]).
occurs_in(X, Y) :- nonvar(Y), zg_term(Y), Y =.. [F|Yargumente],
occurs_in_list(X, Yargumente).
occurs_in_list(X, [H|_]) :- occurs_in(X, H).
occurs_in_list(X, [_|T]) :- occurs_in_list(X, T).
:- occurs_in(X, f(Y)).
no (more) solution.
:- unify(X, f(Y)).
X = f(Y)
Y = Y
yes.
:- unify(X, f(X)).
no (more) solution.
:- unify(X, [A, B, X, C]).
no (more) solution.
:- unify(X, [A, B, C, D]).
X = [A, B, C, D]
A = A
B = B
C = C
D = D
yes.
:-
Letzte Änderung: 18. August 1998