OCR Document

Quesiti con variabili

nonno(X,Z):- padre (X,Y) , padre(Y,Z).

nonno(X,Z):- padre(X,Y), madre(Y,Z).

padre (john, bill). (1)

padre (bill, mary) . (2)

padre (bill, thom). (3)

padre (thom,chris). (4)

madre(mary,june). (5)

?-nonno (X, Y) .

X = john, Y = mary; /*1+2*/

X = john, Y = thom; /*1+3*/

X = mary, Y = june; /*2+5*/

X = bill, Y = chris; /*3+4*/

no (non si trovano latri risultati)

Nota: Le variabili logiche non possono essere riassegnate! Durante una computazione, se vengono istanziate mantengono lo stesso valore fino al raggiungimento di un risultato.

Se si richiede (col ‘;’) di cercare un’altra soluzione, allora vengono disistanziate e (se possibile) reistanziate a valori diversi.

Esempi

a	a	unificano
f(a)	f(a)	unificano
g(f(a))	g(f(a))	unificano
V	a	unificano con V/a
X	g(s)	unificano con X/g (5)
X	Y	unificano con X/Y (o Y/X)
f(a)	f(R)	unificano con A/a
f(X)	f(Y)	unificano con X/Y (o Y/X)
p(a,X)	p(Y,c)	unificano con X/c e Y la
p(a,X)	p(Y,f(c))	unificano con X/f(c) e V/a
q(f(X),a)	q(f(b),V)	unificano con X/b e V/a

L'insieme delle sostituzioni Variabile/termine ottenute unificando due strutture si dice unificatore delle strutture

Unificatore più generale

L’ Unificatore più generale (Most general Unifier, o mgu) e’ quello che produce il minor numero possibile di istanziazioni, ossia non fa “ipotesi” non strettamente necessarie sul valore delle variabili.

p(X,R,V,a) e p(f(b),Y,Z,K)

Un unificatore: {X/f(b), R/Y/pippo, V/Z, K/a}

Un altro unificatore: {X/f(b), R/Y/minnie, V/Z/paperina, K}

Lo mgu: {X/f(b), K/a}

Nel linguaggio delle clausole di Horn (e in Prolog) lo mgu esiste sempre ed è unico

Applicazione degli unificatori

Gli unificatori in genere sono indicati con lettere greche, ad es. δ. L'applicazione di un unificatore δ ad un termine t è indicata con tδ, e produce un nuovo termine t' in cui sono state effettuate tutte le sostituzioni variabile/valore indicate in δ.

Nell'esempio precedente, se t1 = p(X,R,V,a) e p(f(b),Y,Z,K),

ed inoltre δ1 = {X/f(b), R/Y/pippo, V/Z, K/a}

e δ2 = {X/f(b), R/Y/minnie, V/Z/paperina, K}

si ha

t1 δ1 = t2 δ1 = p(f(b),pippo,V,a)

Indifferentemente, p(f(b),pippo,Z,a) perchè V e Z sono in condivisione.

Questo vuol dire che se l'unificazione è utilizzata durante il processo

di dimostrazione di una query, il valore preso dall'una sarà assunto

anche dall'altra.

t1 δ2 = t2 δ2 = p(f(b), minnie, paperina, a)

Lo mgu di indica di solito con s.

t1 s = t2 s = p(f(b), R, V, a) = p(f(b), Y, Z, a)

Strategia depth-first (ricerca in profondità)

La strategia depth-first non e' fair, e quindi non e' completa

Motivo: seleziona sempre la sottometa più a sinistra, e usa sempre la prima clausola

Se questa combinazione causa un loop non riesce a uscirne

a(X,Y) :-a(X,Z) ,a(Z,Y).

a(a,b).

a (b,c).

M = {a(a,b) , a(b,c), a(a,c)}

?-a(a,c) , /*Loop*/

a(a,b). % passi base della ricorsione

a(b,c). % sempre per primi

a(X,Y) :-a(X,Z), a(Z,Y).

?-a(a,d) , /*Loop* /

Nota: si adotta la depth-first per ragioni di efficienza, contando sul programmatore per prevenire i loop

Semantica (per grandi linee) del linguaggio delle clausole di Horn

Modello di un programma: sottoinsieme della Base dove tutte le clausole del programma sono vere

clausole = fatti o regole (quantificati universalmente)

A:-B1,...,Bn.

* Un fatto C e' vero in ogni modello

* Una regola A:-B1,...,Bn e' vera in un modello se

· Sia A che B 1 , . . . , Bn sono in modello

· B1,...,Bn non sono nel modello (A può esserci o meno)

Nota: se una proposizione A contiene variabili, dire

"A è nel modello"

significa che il modello contiene tutte le istanze di A ottenute sostituendo le variabili con termini chiusi (o round, ossia privi di variabili)

Clausole il Logica del Prim’Ordine

(First Order Predicate Logic, FOPL)

A:-B1,...,Bn.

sta per

A Ü B1,...,Bn (implicazione logica)

ossia

A Ú ØB1 Ú … Ú ØBn

dove “Ú” è la disgiunzione e “Ø” la negazione

A,B1,...,Bn sono chiamati “atomi” o “letterali positivi” mentre i “ØBn” sono “letterali negativi”

Questa è una clausola di Horn perché contiene un solo letterale positivo.

Risoluzione in FOPL fra clausole di Horn

· Clausole ground

A Ú ØC

ØA Ú ØB

_______

ØC Ú ØB

Concetto sottostante: A e ØA sono sempre uno vero e uno falso. Entrambe le disgiunzioni date però si assumono essere vere. Allora, se A è falso ØC dovrà essere vero. Invece, se A è vero (e quindi ØA è falso) ØC dovrà essere vero. Non sapendo quale dei due casi si presenterà di volta in volta, si sa però che o ØC o ØB dovrà essere vero, il che formalmente significa che la disgiunzione ØC Ú ØB dovrà essere vera.

Analogamente se B e C sono

disgiunzioni di letterali negativi

· Clausole non ground: se s è lo mgu di A1 ed A2, ossia A1s = A2s, allora

A1 Ú ØC

ØA2 Ú ØB

_________

(ØC Ú ØB)s

Risoluzione in FOPL fra clausole di Horn

Caso particolare:

ØA

_______

clausola

vuota

contraddizione!

Concetto sottostante: A e ØA sono sempre uno vero e uno falso, per cui avere (soltanto) A e ØA vuol dire essere caduti in contraddizione (che formalmente si esprime con la clausola vuota)

Esempio:

Base di conoscenza (round)

ØA (1)

A Ú ØB (2)

B (3)

Da 1 e 2 si deriva per risoluzione

ØB (4)

da 3 e 4 si deriva la clausola vuota (contraddizione!)

Risoluzione in Prolog

Esempio precedente:

A Ú ØB

in Prolog si scrive

A :- B. (2)

B. (3)

Inoltre, ØA è una query, indicata con ?-A. (1)

Essa riesce esattamente con i passi mostrati sopra: dalla query (1) e dalla clausola (2) si deriva la nuova query

?- B (4) che sta per ØB.

Dalla nuova query e dalla clausola (unitaria) (3) si arriva alla clausola vuota, e la query è dimostrata.

Formalmente, fare una query vuol dire asserire la negazione della query stessa. Se per risoluzione si arriva alla clausola vuota, ossia ad una contraddizione, allora la query è dimostrata per assurdo.

Proprietà della Risoluzione

Come si comporta la risoluzione, rispetto al Modello Minimo?

Ossia, data la query

?-p (Arg1,.. , Argn)

il successo o fallimento è in relazione con l'appartenenza di p (Arg1,..,Argn) al Modello minimo?

Risposta: La risoluzione corretta e completa rispetto al Modello Minimo di un programma

E' corretta: tutte le proposizioni dimostrabili mediante risoluzione appartengono al modello minimo (sono conseguenze logiche programma)

E' completa: tutte le proposizioni che appartengono al modello minimo sono dimostrabili mediante risoluzione (ad una condizione!)

Condizione per la completezza: la strategia di risoluzione deve essere "fair"!!!

Cioè: ogni sottometa deve prima o poi essere risolta utilizzando ogni possibile clausola. La depth-first non è fair, sta al programmatore evitare i loop!

Descrizione dei Dati in Prolog

●Lista: caso particolare di struttura

[pippo, pluto, c123, f(a)]

● notazione [. . . ]

àabbreviazione per strutture con funtore ‘.’

. (pippo, . (pluto, . (c123, . (f(a) , []))))

● [] è un atomo speciale che sta per la lista vuota

● Liste

à primo elemento: testa (head)

à lista elementi rimanenti: coda, o corpo (tail)

[pippo | [pluto, c123, f(a)]]

[pippo, pluto | [c123, f(a)]]

[pippo, pluto, c123, f(a) | [] ]

Descrizione dei Dati in Prolog

Liste: simbolo speciale ‘|’

separa i primi n elementi dalla lista dei rimanenti

[ E1,…,En | [...] ]

[anna, carla]	=	[anna, carla \| [] ]
[anna, carla]	=	[anna \| [carla] ]
[anna, carla]	=	[anna \| [carla \| [] ]
[anna, carla]	=/=	[anna \| carla]
[anna, carla]	=/=	[ [anna, carla] ]
[anna, carla]	=/=	[anna, carla, [] ]

Uso delle liste nei termini:

compositori(nazionalità(tedesca),

[bach,mozart,brahms]).

?-amico(Gianni,Y).	Esistono dei valori per cui valga amico(Gianni,Y)?
?-amico(X,Y).	Esistono dei valori per cui valga amico(X,Y)?