Programmazione Logica: Esercizi di preparazione al compitino

• Esercizi di teoria: Lezione 1
• Esercizi di teoria: Lezioni 2, 3 e 4
• Esercizi di programmazione Prolog sulle liste (Lezione 5 e successive)
• Esercizi vari di programmazione Prolog
• Esercizi su unificazione, cut e negazione
• Esercizi su Prolog with Delay, CLP e CCP

(A)

1. Considerare il seguente programma

   p(X) <- q(X,Y),r(Y)
   q(a,b)
   q(b,c)
   r(a)
   r(b) <- r(b)
   r(c).

   Dire qual'e' il minimo modello di Herbrand, ed esibire almeno un altro modello di Herbrand diverso da quello minimo.
   
   
2. Considerare il programma precedente con la quinta clausola rimpiazzata da

   r(b) <- r(Y)
   

   Dire qual'e' il minimo modello di Herbrand, ed esibire almeno un altro modello di Herbrand diverso da quello minimo. Dire inoltre se, nel nuovo programma P, vale che

   P |= forall X. r(X)
   

   Giustificare formalmente la risposta.

(B)

1. Considerare il seguente programma

   p(f(X)) <- p(X)
   p(a)

   Dire qual'e' il minimo modello di Herbrand, ed esibire, se esiste, un altro modello di Herbrand diverso da quello minimo. Dire inoltre se, detto P il programma, valgono che

   P |= forall X. p(X)
   M(P) |= forall X. p(X)

   Dove M(P) e' il minimo modello di Herbrand. Giustificare formalmente la risposta.



2. Considerare il seguente programma

   p(X) <- p(f(X))
   p(a)

   Dire qual'e' il minimo modello di Herbrand, ed esibire, se esiste, un altro modello di Herbrand diverso da quello minimo. Dire inoltre se, detto P il programma, vale che

   M(P) |= forall X. p(X)
   

   Giustificare formalmente la risposta.



3. Considerare il seguente programma

   p(f(X),X) <- p(X,X)
   p(a,a)

   Dire qual'e' il minimo modello di Herbrand, ed esibire, se esiste, un altro modello di Herbrand diverso da quello minimo.
   
   

(C)

1. Considerare il seguente programma

   p(f(X),g(Y)) <- p(X,Y)
   p(a,b)

   Dire qual'e' il minimo modello di Herbrand, ed esibire, se esiste, un altro modello di Herbrand diverso da quello minimo. Dire inoltre se, detto P il programma, valgono che

   P |= forall X,Y. p(X,Y)
   M(P) |= forall X,Y. p(X,Y)

   Giustificare formalmente la risposta.



2. Per ognuno dei seguenti programmi, dire qual'e' il minimo modello di Herbrand, ed esibire, se esiste, un altro modello di Herbrand diverso da quello minimo.

   Programma 1:	p(f(X)) <- q(X,Y), p(Y) p(a) q(b,Y)
   Programma 2:	p(f(X)) <- q(X) p(a) q(g(X)) <- p(X) q(b)
   Programma 3:	p(X) <- q(a) q(X) <- p(X) q(b)

(A)

1. Considerare il seguente programma

   p(X) <- q(X,Y),r(Y)
   q(a,b)
   q(b,c)
   r(a)
   r(b) <- r(b)
   r(c).

   Costruire l'albero SLD per <- p(X) con regola di selezione leftmost. Dire quali risposte ottiene l'interprete Prolog.
   
   
2. Considerare il programma precedente con la quinta clausola rimpiazzata da

   r(b) <- r(Y)
   

   Costruire l'albero SLD per <- p(X) con regola di selezione leftmost. Dire quali risposte ottiene l'interprete Prolog.

(B)

1. Considerare il seguente programma

   p(f(X)) <- p(X)
   q(a)

   Costruire l'albero SLD per <- p(X) con regola di selezione leftmost. Dire quali risposte ottiene l'interprete Prolog. Dire se esiste almeno un altro albero e, in caso affermativo, costruirlo.
   
   
2. Considerare il seguente programma

   p(a)
   p(f(X)) <- p(Y)
   p(X) <- p(f(X))

   Costruire l'albero SLD per <- p(X) con regola di selezione leftmost. Dire quali risposte ottiene l'interprete Prolog. Dire se esiste almeno un altro albero e, in caso affermativo, costruirlo. Dire se valgono

   P |= forall X p(X)
   M(P) |= forall X p(X)

   Giustificare formalmente la risposta. Dire inoltre se vale

   P |= p(X) {X/f(a)}
   

   Giustificare formalmente la risposta. Puo' {X/f(a)} essere una cas per il goal <- p(X)? Se non lo e', quale e' la cas piu' generale di {X/f(a)} che si ottiene? (sappiamo che esiste per il teorema di completezza generalizzato).



3. Considerare il seguente programma

   p(a,a)
   p(f(X),f(X)) <- p(X,X)

   Costruire l'albero SLD con regola di selezione leftmost per per <- p(X,X) e per <- p(f(X),X). Dire quali risposte ottiene l'interprete Prolog.
   
   

(C)

1. Per ognuno dei seguenti programmi e goals, costruire l'albero SLD con regola di selezione leftmost per per i goals specificati. Dire quali risposte ottiene l'interprete Prolog. Dire se esistono altri alberi e, in caso affermativo, esibirne almeno uno.

   Programma 1:	p(a,b) p(f(X),g(Y)) <- p(X,Y)	Goals:	<- p(X,X) e <- p(X,Y).
   Programma 2:	p(f(X)) <- q(X,Y), p(Y) p(a) q(b,Y)	Goal:	<- p(X).
   Programma 3:	p(a) p(f(X)) <- q(X) q(b) q(g(X)) <- p(X)	Goal:	<- p(X).
   Programma 4:	p(X) <- q(a) q(X) <- p(X) q(b)	Goal:	<- p(X).
   Programma 5:	p(X) <- p(X),p(X) p(a) q(b)	Goal:	<- p(X).
   Programma 6:	p(a) q(b) p(X) <- p(X),p(X)	Goal:	<- p(X).

   
   
   

2. Considerare il seguente programma:

   p(X)<- q(X)
   q(a)
   q(f(X))

   Esibire una sostituzione sigma per cui valga

   P |= p(X) sigma
   

   ma tale che sigma non sia una cas per il goal <- p(X). Esibire una cas piu' generale sigma'.

(A)

1. Definire un predicato filter(L,L') che, data la lista L, restituisca la lista L' contenente tutti e soli gli elementi di L che soddisfano p, dove p e' un predicato unario che si suppone di aver gia' definito.
   
   
2. Definire un predicato merge(L1,L2,L3) che, assumendo che L1 e L2 siano due liste numeriche ordinate, restituisca la lista L3 contenente tutti e soli gli elementi di L1 e L2, ordinati.

(B)

1. Definire un predicato flatten(L,L') che, data una lista di liste L, restituisca la lista "appiattita" L'. Per esempio, se L=[[a],[],[[b],c]], la lista risultante deve essere L'=[a,[b],c]
   
   
2. Definire un predicato flatten_n(L,L') che, data una lista di liste di liste ... di liste (n volte, con n numero noto) L, restituisca la lista "appiattita fino a livello n" L'. (Notare che il problema precedente e' un caso particolare di questo, per n=2). Per esempio, se n=3 e L=[[[a]],[[]],[[[b],c]]], la lista risultante deve essere L'=[a,[b],c]



3. Definire un predicato flatten_any_level(L,L') che, data una lista qualsiasi L, restituisca la lista "appiattita a tutti i livelli" L'. Per esempio, se L=[[[a]],[[]],[[[b],c]]], la lista risultante deve essere L'=[a,b,c]

(C)

1. Definire un predicato remove_repetitions(L,L') che, data una lista qualsiasi L, restituisca la lista L' che contiene tutti gli elementi di L, ma una sola volta. Per esempio, se L=[a,[a],b,a,b,c ], la lista risultante deve essere L'=[a,[a],b,c]
   
   
2. Definire un predicato primi(N,L) che restituisca la lista L, di tutti i numeri primi piu' piccoli di N, dove N e' un numero dato.

(A)

1. Definire un predicato visit(T,L) che, dato un albero binario T in una qualche rappresentazione restituisca la lista L che si ottiene visitando l'albero secondo l'ordine anticipato. La definizione della rappresentazione dell'albero e' considerata parte dell'esercizio.
   
   
2. Definire un predicato occur(N,T) che, assumendo che T sia un albero di ricerca, e N un numero, abbia successo se e solo se N compare in T.



3. Definire un predicato search_tree(L,T) che, data una lista di numeri L ordinata e senza ripetizioni, costruisca l'albero di ricerca T contenente tutti gli elementi di L, che sia il piu' bilanciato possibile. Ignorare il problema dell'efficienza.

(B)

1. Definire un predicato prodotto_cartesiano(L,L') che, data una lista qualsiasi L, restituisca la lista L' delle coppie ordinate che si possono formare con elementi di L. Per esempio, se L=[a,b,c,], la lista risultante deve essere L'=[(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a),(c,b),(c,c)].
   
   
2. Scrivere un programma che risolva il problema delle N regine: ossia restituisca una rappresentazione della disposizione di N regine su una scacchiera N x N in modo che non siano in scacco fra loro. Ignorare il problema dell'efficienza.

(C)

1. Supponendo di avere un database di persone con definite le solite relazioni binarie padre e madre, definire la relazione binaria cugino.
   
   
2. In relazione all'esercizio precedente, definire un predicato all_ancestors(X,L) che restituisca la lista L di tutti gli antenati di X.



3. Scrivere un programma che contenga la definizione di un predicato next tale che, quando il goal ?- next(X). viene invocato per la n-esima volta, l'interprete restituisce la cas X=n e poi si ferma (cioe' non da' altre risposte, le dara' solo se viene ri-invocato).
   
   
4. Scrivere un metainterprete Prolog che implementi una regola di selezione fair.

(A)

1. Calcolare, se esiste, il most general unifier dell'equazione f(X,g(Y,Z),a) = f(h(Y),W,Y)
   
   
2. Dato il programma

   p(a).
p(X) :- q(X), !.
p(b).
q(c).
q(d).

   Dire cosa risponde l'interprete Prolog con la chiamata ?- p(Y).
   
   
3. Dato il programma

   p(X) :- not(q(X)).
q(a).

   Dire cosa risponde l'interprete Prolog con le chiamate ?- not(p(Y))., ?- not(p(a)). e ?- not(p(b))..

(B)

1. Calcolare, se esiste, il most general unifier dell'equazione f(X,Y) = f(h(Y),X)
   
   
2. Dato il programma

   p(a).
p(X) :- !, q(X).
p(b).
q(c).
q(d).

   Dire cosa risponde l'interprete Prolog con la chiamata ?- p(Y).
   
   
3. Dato il programma

   p(X) :- not(q(X)).
q(a) :- q(a).
q(b).

   Dire cosa risponde l'interprete Prolog con le chiamate ?- not(p(Y))., ?- not(p(a)). e ?- not(p(b))..

(C)

1. Calcolare, se esiste, il most general unifier dell'equazione f(g(X,Y),g(a,Z),Z) = f(W,W,b)
   
   
2. Dato il programma

   p(X,Y) :- q(X,Y),!, r(Y).
q(a,b).
q(a,Y).
r(c).

   Dire cosa risponde l'interprete Prolog con la chiamata ?- p(X,Y).
   
   
3. Dato il programma

   p(X) :- not(q(X)).
q(a).
q(b) :- p(X).

   Dire cosa risponde l'interprete Prolog con le chiamate ?- not(p(Y))., ?- not(p(a)). e ?- not(p(b))..

(A)

1. Assumendo di avere la seguente dichiarazione di Delay:

   DELAY append(L1,L2,L3) UNTIL nonvar(L1) OR nonvar(L2)

   e la definizione di append usuale, dire cosa risponde l'interprete Prolog alla chiamata ?- append([a|L],L',L), L=[b,d].. Dire cosa sarebbe successo se non si avesse avuto tale dichiarazione.
   
   
2. Considerare il seguente programma CLP su constraints della forma "equazioni e disequazioni fra espressioni lineari su numeri interi":

   p(X,Y) :- X > Y+1, r(Y).
p(X,Y) :- X > Y, r(Y).
r(Y) :- Y > 2.

   Dire quali sono le risposte (semplificate) per le chiamate ?- p(X,Y). e ?- p(X,0)..
   
   
3. Dire quali sono le possibili computazioni del seguente agente CCP, sul constraint system di Herbrand (identita' sintattiche).

   tell(X=a) || ( (ask(true) -> tell(X=b)) + (ask(X=a) -> tell(Y=b))

   
   

(B)

1. Assumendo di avere la seguente dichiarazione di Delay:

   DELAY sum(X,Y,Z) UNTIL nonvar(X) AND nonvar(Y)

   e la definizione di sum (somma di naturali) usuale, dire cosa risponde l'interprete Prolog alla chiamata ?- sum(0,Y,succ(0)).. Dire cosa sarebbe successo se non si avesse avuto tale dichiarazione.
   
   
2. Considerare il seguente programma CLP su constraints della forma "equazioni e disequazioni fra espressioni lineari su numeri interi":

   p(X,Y) :- X > Y, r(X,Z), r(Z,Y).
r(X,Y) :- X < Y.
r(X,Y) :- X = Y.

   Dire quali sono le risposte (semplificate) per la chiamata ?- p(X,Y)..
   
   
3. Dire quali sono le possibili computazioni del seguente agente CCP, sul constraint system di Herbrand (identita' sintattiche).

   (ask(X=f(b)) -> tell(Z=c) || tell(X=f(Y)) || ask(X=f(Y)) -> tell(Y=b)

   
   

(C)

1. Assumendo di avere la seguente dichiarazione di Delay:

   DELAY sum(X,Y,Z) UNTIL nonvar(X) OR nonvar(Z)

   e la definizione di sum (somma di naturali) usuale, dire cosa risponde l'interprete Prolog alla chiamata ?- sum(X,Y,Z), Z=succ(0).. Dire cosa sarebbe successo se non si avesse avuto tale dichiarazione.
   
   
2. Considerare il seguente programma CLP su constraints della forma "equazioni e disequazioni fra espressioni lineari su numeri interi":

   p(X,Y,Z) :- X > Y+Z, q(Y), r(Z).
q(X) :- X > 1.
q(X) :- X = 1.
r(X) :- X > 2.
r(X) :- X = 2.

   Dire quali sono le risposte (semplificate) per la chiamata ?- p(X,Y)..
   
   
3. Dire quali sono le possibili computazioni del seguente agente CCP, sul constraint system di Herbrand (identita' sintattiche).

   ( (ask(Y=b) -> tell(Z=c) + ask(X=a) -> tell(W=d) ) || tell(X=a) || ( (ask(X=a) -> tell(Y=b) + ask(W=d) -> tell(Y=c) )