Logica e Sistemi Informatici, II parte – luglio 2013
1. Definire un predicato Prolog assocmin(+L,?E) che ha successo quando L è una lista di
coppie L = [(n1 ,e1 ),(n2 ,e2 ),...], dove i primi elmenti delle coppie ni sono numeri, ed E
è uno degli ei associati al minimo valore ni . Ad esempio, assocmin([(3,a),(2,b),(4,c),
(2,d)],E) avrà successo con E=b o E=d (ovviamente, quando il secondo argomento è una
variabile, verrà istanziato ad un valore appropriato).
2. Si consideri un dominio in cui diversi robot possono raccogliere oggetti dal pavimento, poggiarli sul pavimento, metterli dentro delle scatole e toglierveli. Le azioni possibili sono
raccogli(r, x) (il robot r prende in mano l’oggetto x che sta per terra; ciascun robot può
tenere in mano un unico oggetto alla volta), lascia(r, x) (il robot r lascia sul pavimento
l’oggetto x che ha in mano; il pavimento non ha limiti di spazio); metti(r, x, b) (il robot r
mette nella scatola b l’oggetto x che ha in mano; le scatole non hanno limiti di capienza) e
togli(r, x, b) (il robot r tira fuori dalla scatola b l’oggetto x).
(a) Determinare i fluenti e gli eventuali predicati statici per la rappresentazione del dominio,
descrivendo il significato di ciascuno di essi.
(b) Scrivere (in Prolog) l’assioma delle precondizioni per l’azione metti(r, x, b).
(c) Scrivere (in Prolog) l’assioma dello stato successore per il fluente che rappresenta il fatto
che il robot r ha in mano l’oggetto x.
(d) Definire una procedura GOLOG che, quando eseguita, colloca tutti gli oggetti dentro
qualche scatola. La procedura ha successo anche quando inizialmente il tutti gli oggetti
sono già inscatolati.
3. Si consideri la formula F = 2(¬p ∨ 3q).
(a) Sviluppare un tableau completo per F e caratterizzarne l’insieme dei cammini aperti.
Numerare i nodi del tableau e usare la stessa numerazione al punto successivo.
(b) Determinare un automa di Büchi che corrisponda a F (che cioè accetti tutti e soli i
modelli di F ). Rappresentare graficamente l’automa, evidenziando l’insieme degli stati
di accettazione. Identificare un’esecuzione accettante dell’automa e una parola letta da
tale esecuzione.
4. Sia P = {p, q} e Σ l’insieme di tutti gli insiemi di assegnazioni proposizionali per P (Σ =
P
22 ) – si ricordi che un insieme di assegnazioni corrisponde a una formula. Siano inoltre
A0 = (S0 , ∆0 , I0 , L0 , Σ, F0 ) e A1 = (S1 , ∆1 , I1 , L1 , Σ, F1 ) due automi sullo stesso alfabeto Σ,
dove:
S0 = {a, b}
∆0 = {(a, b), (b, b)}
I0 = {a}
F0 = {b}
L0 (a) = p ∨ q, L0 (b) = ¬p
S1 = {1, 2, 3}
∆1 = {(1, 1), (1, 2), (2, 1), (2, 3), (3, 3)}
I1 = {1, 2}
F1 = {2, 3}
L1 (1) = ¬p, L1 (2) = q, L1 (3) = p
(a) Rappresentare graficamente gli automi A0 e A1 ; costruire l’automa intersezione B =
(S, ∆, I, L, Σ, F ) di A0 e A1 , dandone la rappresentazione grafica. Determinare se il
linguaggio accettato da B è vuoto o no, e, se non è vuoto, fornire un esempio di esecuzione
accettante e una parola letta da tale esecuzione.
(b) Se l’automa A0 rappresenta un sistema e A1 è l’automa che accetta tutte e solo le parole
che rappresentano i contromodelli di una data formula F della logica LTL (A1 è l’automa
che rappresenta ¬F ), cosa si può dedurre dalla costruzione del punto precedente?
(c) Ricordando che automi etichettati da formule (nel linguaggio P ) sono rappresentazioni compatte di automi sull’alfabeto Σ0 = 2P (insieme di tutti i sottoinsiemi di P ),
rappresentare graficamente l’automa sull’alfabeto Σ0 corrispondente a A0 .