FMZ

Sistemi basati su conoscenzaProlog (1)

Dott. Fabio Zanzotto

a.a. 2001-2002

FMZ

Prolog

• Linguaggio:– basato su una restrizione della logica del primo

ordine– “dichiarativo”

• Utile per:– Prototipizzazione radipa (di alcuni problemi)– Applicazioni di Intelligenza Artificiale basate

sulla logica

FMZ

Una dimostrazione per F è conseguenza di S

è una sequenza

DIM=P1,P2,…,Pn

dove• Pn=F• PiS oppure Pi è ottenibile da Pi1,…,Pim (con i1<i,.., im<i)

applicando una regola di inferenza

Processo di dimostrazione (limiti)

S F

FMZ

DIM=P1,P2,…,Pn

Come scegliamo:• Il percorso da fare?

• Quale formule Pi1,…,Pim attivano una regola di inferenza?

E’ possibile standardizzare il processo?

Processo di dimostrazione (limiti)

S F

FMZ

Tentativo (In logica proposizionale):

• Ammettiamo formule del tipo:

– A1… AmB (tipo 1)

– B (tipo 2)

con A1,…,Am,B letterali

Processo di dimostrazione (standardizzazione)

FMZ

Processo di dimostrazione (standardizzazione)

Per dimostrare: • In S solo regole di tipo 1 o tipo 2• Partiamo da F=Pn

• Pi è deducibile se:– Pi S– Utilizzando MP e AE,

esiste A1… Am Pi e

A1,…, Am sono deducibili

S F

FMZ

Legami con la logica del primo ordine

Clausole di Horn

x1,…,xn A1… AmB

FMZ

Prolog e la logica del primo ordine

• Prolog è un linguaggio di programmazione basato sulle ‘Horn Clauses’

• Le ‘Horn Clauses’ sono un sottoinsieme dei predicati esprimibili in logica dei predicati– Esiste un algoritmo per cui la dimostrazione di

un teorema scritto in clausole di Horn è computabile in tempo polinomiale

FMZ

Prolog e la logica del primo ordine

x1,…,xn A1… AmB

B:- A1,…,Am

:- si pronuncia se

Sintassi in Prolog

Clausola di Horn

FMZ

Sintassi del prolog

Sintassi legata alla logica del primo ordine

• Costanti costanti individuali

• Variabili variabili individuali

• Funtori lettere funzionali, predicative

FMZ

Sintassi del linguaggio

Atomi: Costanti, funtori• Il simbolo :- è considerato atomo.

• Sequenza di caratteri (lettere o numeri o underscore) che comincia con una lettera minuscola

• Oppure qualsiasi cosa contenuto tra ‘ ’.

FMZ

Sintassi del linguaggio

Variabili:• qualsasi stringa che cominici con una lettera maiuscola o

con un underscore

• Il singolo underscore ‘_’ è cosiderata una variabile anonima, cioè non importante.

• Le variabili vengono istanziate (legate ad un valore) al procedere del programma (nella risoluzione del teorema)

FMZ

Esempi di atomi e variabili:

• Atomi:a_boy, peanut, ‘Jack-Smith’, i12345

• Non Atomi:231as, Jack-Smith, _crack

• Variabili:Answer, X, I_like, _Marbles

• Non variabili:mother, 3blind_mice

FMZ

Costruzione dei predicati

Se t1,…,tn e P sono atomi o variabili allora

P(t1,…,tn) è un predicato

Esempi:• parent(X,Y)• parent(paolo,X)

FMZ

Clausole: come fatti e regole

• I fatti sono predicati seguiti da ‘.’ (punto)

• Le regole sono della forma vista in precedenza per le clausole di Horn

FMZ

“Programmare” in prolog

• Dato un problema costruire S che permetta di dimostrare F (o un insieme di formule)

• Costruire S:– Definire fatti – Definire regole

• Costruito S abbiamo programmato in Prolog

FMZ

Esempio

• Conoscendo il sesso delle persone e se uno è genitore dell’altro, vogliamo sapere – chi è padre di chi– chi è madre di chi

FMZ

Fatti - esempi

male(alan).male(gary).female(margaret).parent(alan, gary).parent(alan, margaret).

FMZ

Regole – esempi

mother(X,Y) :- parent(X,Y), female(Y).

father(X,Y) :- parent(X,Y), male(Y).

FMZ

Interrogare il programma

• Richiedere la dimostrazione di un teorema

?- mother(alan,Mom).

FMZ

Regola di inferenza

Introduzione del quantificatore esistenziale

F(…a…)

xF(…x…)

xB(…x…)

Teorema che si vuole dimostrare

FMZ

Unificazione: regola di inferenza

x.F(…x…)

F(…a…)

x1,…,xn A1… AmB

Eliminazione del quantificatore universale

P B , P

BMP

Modus ponens

FMZ

Interrogare il programma

?- mother(alan,Mom).

Ci stiamo chiedendo

Mom.mother(alan,Mom)

FMZ

L’algoritmo di risoluzione

• in profonditàmale(alan).male(gary).female(margaret).parent(alan, gary).parent(alan, margaret).mother(X,Y) :- parent(X,Y), female(Y).father(X,Y) :- parent(X,Y), male(Y).

Goal: ?- mother(alan,Mom).

FMZ

L’algoritmo di risoluzione

• Criteri:

Dato un goal, ricercare dall’alto verso il basso:• Un fatto che sia una generalizzazione

• Una regola che abbia come ipotesi l’obiettivo

• Istanziare le variabili

• Cercare un percorso che porti ad una soluzione

FMZ

Una puntatina all’interprete prolog

• come si lancia?

• come si esce?

• quale interprete usiamo (dove si trova e dove si trovano i manuali)

• come scrivo un programma?

• come uso un programma all’interno dell’interprete?

FMZ

Una puntatina all’interprete prolog

• come si lancia?swipl

e’ sempre in modalità

?- prompt

ovvero voglio soddisfare un goal

• come si esce??- halt.

FMZ

Una puntatina all’interprete prolog

• quale interprete usiamo SWI Prolog

http://www.swi.psy.uva.nl/projects/SWI-Prolog/download.html– interprete– manuale

• come scrivo un programma? – Con l’editor di testo preferito

• come uso un programma all’interno dell’interprete??- consult(‘NomeProgramma’).oppure?- [‘NomeProgramma’].

FMZ

Le trappole dell’algoritmo di risoluzione

• Scriviamo ancestor(X,Y)

ancestor(X,Y):-

ancestor(X,Z),

parent(Z,Y).

ancestor(X,Y):-

parent(X,Y).

FMZ

L’algoritmo di risoluzione

• in profonditàmale(alan).male(gary).female(margaret).parent(alan, gary).parent(alan, margaret).ancestor(X,Y):-ancestor(X,Z),parent(Z,Y).

ancestor(X,Y):-parent(X,Y).

Goal: ?- ancestor(alan,Mom).

FMZ

Costruzione delle funzioni (Apparente dimenticanza)

Se t1,…,tn e f sono atomi o variabili allora

f(t1,…,tn) è un funzione

Esempi:• parent(X,Y)• parent(paolo,X)

FMZ

Esercizi

Dati fatti del tipo:male(pippo).

female(pippo).

father(pippo,pluto). pippo è padre di pluto

mother(pippo,pluto). pippo è madre di pluto

Definire le regole per :(a) part_of_parent(X,Y). X è uno dei genitori di Y

(b) cousin(X,Y). X è cugino di Y