fmz sistemi basati su conoscenza prolog (1) dott. fabio zanzotto a.a. 2001-2002
TRANSCRIPT
![Page 1: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/1.jpg)
FMZ
Sistemi basati su conoscenzaProlog (1)
Dott. Fabio Zanzotto
a.a. 2001-2002
![Page 2: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/2.jpg)
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
![Page 3: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/3.jpg)
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
![Page 4: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/4.jpg)
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
![Page 5: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/5.jpg)
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)
![Page 6: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/6.jpg)
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
![Page 7: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/7.jpg)
FMZ
Legami con la logica del primo ordine
Clausole di Horn
x1,…,xn A1… AmB
![Page 8: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/8.jpg)
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
![Page 9: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/9.jpg)
FMZ
Prolog e la logica del primo ordine
x1,…,xn A1… AmB
B:- A1,…,Am
:- si pronuncia se
Sintassi in Prolog
Clausola di Horn
![Page 10: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/10.jpg)
FMZ
Sintassi del prolog
Sintassi legata alla logica del primo ordine
• Costanti costanti individuali
• Variabili variabili individuali
• Funtori lettere funzionali, predicative
![Page 11: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/11.jpg)
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 ‘ ’.
![Page 12: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/12.jpg)
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)
![Page 13: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/13.jpg)
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
![Page 14: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/14.jpg)
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)
![Page 15: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/15.jpg)
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
![Page 16: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/16.jpg)
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
![Page 17: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/17.jpg)
FMZ
Esempio
• Conoscendo il sesso delle persone e se uno è genitore dell’altro, vogliamo sapere – chi è padre di chi– chi è madre di chi
![Page 18: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/18.jpg)
FMZ
Fatti - esempi
male(alan).male(gary).female(margaret).parent(alan, gary).parent(alan, margaret).
![Page 19: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/19.jpg)
FMZ
Regole – esempi
mother(X,Y) :- parent(X,Y), female(Y).
father(X,Y) :- parent(X,Y), male(Y).
![Page 20: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/20.jpg)
FMZ
Interrogare il programma
• Richiedere la dimostrazione di un teorema
?- mother(alan,Mom).
![Page 21: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/21.jpg)
FMZ
Regola di inferenza
Introduzione del quantificatore esistenziale
F(…a…)
xF(…x…)
xB(…x…)
Teorema che si vuole dimostrare
![Page 22: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/22.jpg)
FMZ
Unificazione: regola di inferenza
x.F(…x…)
F(…a…)
x1,…,xn A1… AmB
Eliminazione del quantificatore universale
P B , P
BMP
Modus ponens
![Page 23: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/23.jpg)
FMZ
Interrogare il programma
?- mother(alan,Mom).
Ci stiamo chiedendo
Mom.mother(alan,Mom)
![Page 24: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/24.jpg)
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).
![Page 25: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/25.jpg)
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
![Page 26: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/26.jpg)
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?
![Page 27: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/27.jpg)
FMZ
Una puntatina all’interprete prolog
• come si lancia?swipl
e’ sempre in modalità
?- prompt
ovvero voglio soddisfare un goal
• come si esce??- halt.
![Page 28: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/28.jpg)
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’].
![Page 29: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/29.jpg)
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).
![Page 30: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/30.jpg)
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).
![Page 31: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/31.jpg)
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)
![Page 32: FMZ Sistemi basati su conoscenza Prolog (1) Dott. Fabio Zanzotto a.a. 2001-2002](https://reader036.vdocumenti.com/reader036/viewer/2022062512/5542eb74497959361e8dcb63/html5/thumbnails/32.jpg)
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