Transcript
Logica dei Predicati: 1
Semantica
Corso di Logica e Reti Logiche, a.a. 2014-15 Roberto Basili (Università di Roma Tor Vergata)
Roberto Basili
4/22/2015
2
Outline Obbiettivi della Semantica Riferimento nel Mondo e verità
La nozione di interpretazione Semantica della FOL Alcune riflessioni sulla sostituzione Conseguenza semantica e Deduzione in FOL Esempi ed esercizi proposti
Roberto Basili
4/22/2015
3
Esempi di linguaggi Linguaggio puro dei predicati L’operatore di uguaglianza è assente Simboli di predicati n-ari sono denotati con le lettere: Pn, Qn, Mn, …
Simboli costanti: a, b, c, … Nessun simbolo funzionale
Esempi di FBF: x Q(x) P(x) x y ( P(x,y) M(y)) Q(y).
xM(x) y(W(y) L(x,y)).
Roberto Basili
4/24/2015
4
Esempi di linguaggi (2) Linguaggio della teoria dei numeri (interi) L’operatore di uguaglianza è presente Un solo simbolo di predicato binario : ‘<‘ Simbolo costante: 0 Simboli funzionali Unario: s (successore) Binari: x, +
Esempi di FBF: xy (x + s(y)) = s(x+y)
x ( (x=0) y (x = s(y)) ) xy ((x, , } Clear= {a, d}
Table= {c, e} Block= {a, b, c, d, e} On= {, } Clear= {a, c, d} Table= {a, b, e} Block= {a, b, c, d, e} Roberto Basili
4/22/2015
6
Il significato: il problema e la prospettiva Cosa significa assegnare significato ad una formula? La sua verità è indipendente dallo stato del mondo? Problemi: Verità vs. (im)possibilità Contingenza vs. Validità
Applicazioni: Verificare le proprietà di affermazioni/teoremi utili ad una disciplina Unicità dello 0
Verificare le proprietà dei programmi Fornire regole di deduzione a sistemi di ragionamento Roberto Basili automatico 4/22/2015
7
Calcolo dei Predicati: Formule Ben Formate (FBF) Ogni formula atomica è una formula; Ogni espressione della forma j, se j è una formula; Ogni espressione della forma (j y), (j y), (j y) (j y)
è una formula, se j e y sono formule; Ogni espressione della forma xj
e
xj
è una formula, se x è una variabile e j è una formula. Roberto Basili
4/22/2015
9
Interpretazione: il dominio L’interpretazione dei i simboli non logici richiede necessariamente un insieme non vuoto D di individui, detto dominio dell’interpretazione. L’idea è che D contenga tutti gli individui (di qualunque natura) che costituiscono l’universo del discorso di una certa applicazione.
Esempio: D : l’insieme dei blocchi e oggetti fisici contenuti in una stanza, D : l’insieme dei numeri naturali, D : l’insieme dei punti di uno spazio euclideo, o l’insieme degli esseri umani. Attenzione: è necessario non confondere i simboli che denotano elementi del dominio (come a, b, c, ...) con i simboli (a, b, c, ...) che costituiscono le costanti del linguaggio formale. Roberto Basili
4/22/2015
10
Interpretazione dei simboli del linguaggio logico Definiamo allora la funzione d’interpretazione i(.) nel modo seguente: per ogni costante a, l’interpretazione i(a) è un elemento di D; (funzione di scelta) per ogni funtore f di arità n, l’interpretazione i(f) è una funzione i(f) : Dn D;
per ogni predicato P di arità n, l’interpretazione i(P) è una funzione i(P) : Dn {0,1},
ovvero la funzione caratteristica di una relazione n-aria su D. Roberto Basili
4/22/2015
11
Interpretazione delle variabili E le variabili? Si tratta di un’ulteriore funzione e(.) tale che:
per ogni variabile x, l’assegnamento e(x) è un elemento di D. Vedremo più avanti come la funzione e(.) ci permetta di assegnare un significato ai quantificatori.
Roberto Basili
4/22/2015
12
Interpretazione dei termini del linguaggio Definiamo cosa denotino i termini del linguaggio, dati un assegnamento e(.) ed un modello (struttura) M = D, i(.), dove D è il dominio ed i(.) una funzione d’interpretazione. La interpretazione (anche detta denotazione) *t di un termine t è l’elemento del dominio così definito:
*a = i(a) per ogni costante a del linguaggio; *x = e(x) per ogni variabile x del linguaggio; *f(t1,...,tn) = i(f)(*t1,...,*tn) per ogni termine funzionale del linguaggio di arità n.
Roberto Basili
4/22/2015
13
Interpretazione dei predicati del linguaggio Un assegnamento e(.) ed un modello M = D, i(.), dove D è il dominio ed i(.) una funzione d’interpretazione, ci consentono anche di interpretare i simboli predicativi, Pn nei termini di relazioni n-arie in D. Formalmente:
La denotazione *Pn di un predicato n-ario è una relazione *Pn Dn
Roberto Basili
4/22/2015
La soddisfacibilità di una formula j rispetto ad un modello M ed un assegnamento e(.), si denota con Uguaglianza (M, e) = j sintattica (in L) e si definisce ricorsivamente:
(M, e) = j sse j = , (M, e) j sse j =
14
Semantica del FOL
Uguaglianza semantica (i.e. in D)
(M, e) = P(t1, …, tn) sse <*t1, …, *tn> *P Dn (M, e) = t1= t2
sse *t1=*t2
(M, e) = j sse (M, e) j (M, e) = j y sse
(M, e) = j
e (M, e) = y
(M, e) = j y sse
(M, e) = j
oppure (M, e) = y
(M, e) = j y sse
(M, e) = j
implica che (M, e) = y
(M, e) = j y (M, e) = j e (M, e) = y oppure (M, e) j e (M, e) y ... Roberto Basili
4/22/2015
15
Semantica del FOL (2) La soddisfacibilità di una formula j rispetto ad un modello M ed un assegnamento e(.), si denota con (M, e) = j e si definisce ricorsivamente:
… (M, e) = xj
sse
per ogni dD, (M, e) = j (d/x)
(M, e) = xj sse esiste un certo dD, per cui è verificato che (M, e) = j (d/x)
Roberto Basili
4/22/2015
16
Esempio Sia:
j: x y P(y,x)
(1)
M1 - Mondo 1. D è l’insieme degli esseri umani e l’interpretazione di P è «padre di». La formula (*) ci appare vera, i.e. (M1,e) = j
M2 - Mondo 2. D è l’insieme dei numeri naturali e l’interpretazione di P è «maggiore di» (<). La formula (*) ci appare per altri motivi vera, i.e. (M2,e) = j Ogni Mondo costituisce una interpretazione diversa ed indipendente. Roberto Basili
4/22/2015
17
Verità di una formula Diciamo che una formula F è soddisfatta dalla valutazione IV, se IV(F) = 1. Una formula F è soddisfacibile se esiste una valutazione IV, tale che IV(F) = 1.
Notare che data IV, stabilire se IV(F) = 1 è un calcolo facile. Viceversa trovare IV tale che IV(F) = 1 può essere molto difficile (computazionalmente). Una formula F è una tautologia se per ogni valutazione IV, F è soddisfatta dalla valutazione IV. Una formula F è una contraddizione se per ogni valutazione IV, F non è soddisfatta dalla valutazione IV.
Roberto Basili
4/22/2015
18
Variabili, Connettivi e Quantificatori Esempi: x (P(X) Q(X))
vs. x (P(X) Q(X))
x (P(X) Q(X)) vs.
x (P(X) Q(X))
Osserviamo quindi che: (M1, e1) = j sse
(M2, e2) = j
corrisponde ad una equivalenza tra (M1, e1) ed (M2, e2) In particolare esse debbono coincidere con tutte le scelte su: Simboli costanti e funzionali che occorrono in j (M1, M2) Variabili che occorrono in j (e1 vs. e2) Simboli predicativi che occorrono in j (M1, M2) Roberto Basili
4/22/2015
19
Variabili e Quantificatori In realtà debbono concordare SOLO sulle variabili libere, poiché la semantica delle varabili quantificate è sotto il controllo della proprietà per cui: (M1, e1) = j sse
(M2, e2) = j
Allora ragionando sul ruolo delle variabili vincolate … Esempio (formula chiusa) x y (P(x,y) z P(y,z)) Immaginiamo M per cui D corrisponda ai numeri interi e P sia ‘‘
La soddisfacibilità qui non dipende da alcun assegnmento e(). Roberto Basili
4/22/2015
20
Modelli e formule Se per ogni assegnazione e() si ha che (M, e) = j (e questo è sempre vero per formule chiuse) allora si dice che j è conseguenza logica di M, si scrive
M = j e che M è un modello per j .
Una scrittura alternativa è: =M j
Se j è tale che M = j è vera per ogni M, allora diciamo che j è una formula valida del calcolo
Roberto Basili
4/22/2015
21
Validità e contingenza Tutte le formule non valide sono contingenti Esempi:
P(a) x ( S(x,100) y Q(y,x) ) x (C(x) y( P(x,y,a) ) )
Roberto Basili
4/22/2015
22
Formule logiche e lingue If Bill or John is leaving, then Mary and Sue aren’t happy (leave(b) leave(j)) (happy(m) happy(s))
Every cat gave a book to Bill x (cat(x) y( give(x,y,b) ) ) Ogni amica di Bill gli ha regalato un libro
Roberto Basili
4/22/2015
23
Insiemi di formule e soddisfacibilità Un insieme di formule è soddisfacibile se esiste un modello ed un assegnamento (M, e) tale che valga (M, e) = j
per ogni j
Nel caso in cui tutte le formule j1, …., jn in sono chiuse, la soddisfacibilità coincide con la verità di tutte le formule di ji In qualche modo stiamo asserendo la verità secondo il modello M della congiunzione logica ( i ji ) di tutte le formule di .
⋀
Roberto Basili
4/22/2015
24
Implicazione Logica di formule Dati un insieme di formule ed una formula j, si dice che implica logicamente j che si scrive
= j sse per ogni modello ed assegnamento (M, e) tale che valga (M, e) =
si verifica anche (M, e) = j
Roberto Basili
4/22/2015
25
Esempio di implicazione logica Nel mondo M dei blocchi Fatti: On= {, } Table= {a, b, e} Block= {a, b, c, d, e}
Linguaggio Costanti = {a,b,c,d,e} Predicati = {on2, block1, table1, clear1} = { block(a), …, block(e),
table(a), table(b), table(e),
on(c,b), on(d,e), x ( (block(x) y on(y,x)) clear(x)) } Se j = clear(c) si può dire:
= j Roberto Basili
4/22/2015
26
Esempio di implicazione logica Nel mondo M dei blocchi Fatti: On= {, } Table= {a, b, e} Block= {a, b, c, d, e}
Linguaggio Costanti = {a,b,c,d,e} Predicati = {on2, block1, table1, clear1} = { block(a), …, block(e),
table(a), table(b), table(e),
on(c,b), on(d,e), x ( (block(x) y on(y,x)) clear(x)) } Qual’è la interpretazione i(.) in M per cui:
= j Roberto Basili
4/24/2015
27
Esempio di implicazione logica (2) E’ ancora vero che = clear(c) j se lo stato del mondo M è cambiato?
E’ vero che
(M, e) j Ma è anche vero che M non è più un modello per poiché si verifica anche (M, e) (infatti ad esempio table(a) è falso!)
Il legame tra e j è preservato !!
Roberto Basili
4/22/2015
28
Equivalenza Semantica nel FOL Date due formule j e y, esse sono semanticamente (o logicamente) equivalenti e si scrive
j y se per ogni modello ed assegnamento (M, e) si verifica che: (M, e) = j
Roberto Basili
sse (M, e) = y
4/22/2015
Ancora sulla sostituzione
29
Data la definizione di equivalenza segue che due formule che differiscono per i soli nomi delle variabili legate sono equivalenti. Infatti: sia (M, e) un modello ed un assegnamento, t un termine allora vale che 1. Se y non compare in t, allora la denotazione *t secondo il modello (M, e) per cui e(x)=d corrisponde alla denotazione § *t(y/x) del termine t(y/x) secondo il modello (M, e) per cui e(y)=d. 2. Se y non compare in una formula j allora detti (M, e) ed (M, e’) che differiscono per la sola assunzione e(x)=d ed e(y)=d, si ha che (M, e) = j
sse (M, e’) = j(y/x)
§
t(y/x) denota la riscrittura del termine t in cui ogni occorrenza della variabile x è sostituita con la variabile y. Roberto Basili
4/22/2015
30
Sostituzione e variabili libere Nella formula contingente y (x = y)
(per esempio vera per una interpretazione verso insiemi con più elementi distinti) Il termine y non è liberamente sostituibile ad x poiché x è nell’ambito di uno dei quantificatori di y.
Infatti sostituendo y al posto di x otterremmo una formula evidentemente falsa y (y = y)
Roberto Basili
4/22/2015
Sostituzione e Quantificatori
31
Si ha che: 1. x j x j
2. x j x j 3. x j x j 4. x j x j La 1 coincide con: (M, e) = x j
sse (M, e) = x j
(M, e) = x j ci dice che per ogni dD si ha che j(d/x) è vera, e cioè che per ogni dD segue M= x j(d/x)
Quindi per nessun dD segue (M, e)= j(d/x)
Quindi (M, e) x j(d/x)
Quindi (M, e) = x j(d/x)
(il viceversa segue dal non ver mai usato alcuna ipotesi direzionale)
Roberto Basili
4/22/2015
32
Alcune equivalenze utili x y j y x j x y j y x j x j j se x var(j) x j j se x var(j)
x (j y) x j x y
x (j y) x j x y x (j y) x j y
se x var(y )
x (j y) x j y
se x var(y ))
??? x (j y) x j x y Roberto Basili
4/22/2015
33
Riflessione: perché logica del primo ordine Le variabili nel FOL possono essere usate per denotare oggetti del dominio (i.e. membri di D), non per rappresentare funzioni, predicati o formule. Sebbene D possa contenere funzioni o predicati, i nomi di tali funtori o predicati non possono essere usati al posto di funzioni o predicati del linguaggio f x f(x)=x
(esistenza dell’identità)
f Identita(f) p Buonaqualita(p) Ha(giorgio,p) p Buonaqualita(p) p(giorgio)
Roberto Basili
4/22/2015
34
Esercizi (1) Determinare possibili formule valide tra le seguenti: xH(x) (x G(x, f(y)) H(y)) x H(a) G(b) L(x,g(b,x)) x (P(x) Q(x)) x (P(x) Q(x)) x (P(x) P(x)) x (P(x) P(x)) x H(x) G(b) x L(x,b)
x (H(x) G(b) P(x,y)) x L(x,b) x (H(x) G(b) P(x,y)) x L(x,b)
Roberto Basili
4/22/2015
Esercizi (2) Dimostrare le seguenti conseguenze logiche x P(x) P(x)
35
x P(x) P(x) x P(x) P(x) x P(x) Q(x) x P(x) Q(x)
Roberto Basili
4/22/2015
36
Genealogie
Roberto Basili
4/22/2015
37
Genealogie (2) Scrivere in un linguaggio del primo ordine un insieme di formule per la genealogia della pagina precedente. Progettare una interpretazione e il corrispondente insieme di parametri che rendano il grafo di pagina precedente un modello per le formule Dimostrare per via semantica, che l’enunciato «Crono è un avo di Apollo» è una conseguenza logica delle formule scritte.
Roberto Basili
4/22/2015
38
Riferimenti [2] C.L. Chang and Lee R.C.T. Symbolic Logic and Mechanical Theorem Proving. Academic Press, 1973. trad. it. Tecniche Nuove.
[5] E. Mendelson. Introduction to Mathematical Logic. Van Nostrand, 1964. Trad. it. Boringhieri. Carlucci Aiello Luigia, Pirri Fiora, Strutture, logica, linguaggi, 2005, 336 p., Editore Pearson (collana Accademica).
McCarthy, J., and P. Hayes (1969). Some philosophical problems from the standpoint of artificial intelligence. In B. Meltzer and D. Michie, eds., Machine Intelligence 4, Edinburgh University Press, Edinburgh, UK. Nilsson, N. J. (1998). Artificial intelligence: A new synthesis, Morgan Kaufmann, San Francisco, CA. Anche: dispense M. Cialdea Mayer. Logica (Home page)
Roberto Basili
4/22/2015
