Post on 01-May-2015
FMZ
Linguaggi di ProgrammazioneDa logica proposizionale a logica del primo ordine
FMZ
Logica proposizionale Sintassi vs Semantica
Sintassi Semantica Mondo
Concetto di modello
Funzione di interpretazione
SimboliFBFASSIOMIRegole di inferenza
S F S F
???
FMZ
Una dimostrazione per
è una sequenza
DIM=P1,P2,…,Pn
• Pn=F• PiS• PiASSIOMI• Pi è ottenibile da Pi1,…,Pim (con i1<i,.., im<i)
applicando una regola di inferenza
Sintassi vs Semantica Osservazioni
S F
FMZ
DIM=P1,P2,…,Pn
Problema: introduciamo sempre formule vere?• PiS vere per ipotesi
• PiASSIOMI veri poiché tautologie
• Pi è ottenibile da Pi1,…,Pim (con i1<i,.., im<i) applicando una regola di inferenza
Sintassi vs Semantica Osservazioni
anello debole
FMZ
Sintassi vs Semantica Regole di inferenza e veridicità
VVFF
VFVF
A BVFVV
AB
VVFF
VFVF
A BVFFF
AB
P B , P
BMP
A1,…,An
A1… An
A1… An
Ai
AE
AI
FMZ
Sintassi vs Semantica
• La preservazione della veridicità è osservabile per induzione
• Formalmente:– (Meta)Teorema di completezza– (Meta)Teorema di Deduzione (+ Ogni teorema
di L è una tautologia)
FMZ
Logica proposizionale (limiti)
Socrate è un uomo.Gli uomini sono mortali. (A)Allora Socrate è mortale.
Traduzione di (A) nella logica proposizionaleSe Gino è un uomo, allora Gino è mortale.Se Pino è un uomo, allora Pino è mortale.Se Rino è un uomo, allora Rino è mortale.Se Socrate è un uomo, allora Socrate è mortale.…
Se X è un uomo, allora X è mortale.
FMZ
Logica del primo ordine(logica dei predicati del primo ordine)
SintassiIngredienti:
Simboli LL– LetteraliLetterali
• Costanti individuali Ai
• Variabili individuali i
• Lettere funzionali fi
• Lettere predicative Pi
– Connettivi LogiciConnettivi Logici: {,,,,(,)},
FMZ
Logica del primo ordine Sintassi
Ingredienti:Termine TTermine T
costanti individuali T variabili individuali T
Se t1,…,tn T allora
fi(t1,…,tn) T (applicazione di un simbolo di funzione n-ario a n termini)
Termine groundTermine ground - senza variabili (oggetti dell'Universo del discorso)Es.: padre(padre(giovanni))
FMZ
Formule Atomiche (atomi)Formule Atomiche (atomi)
Se t1,…,tn T alloraPi(t1,…,tn) è una formula atomicaformula atomica
Logica del primo ordine Sintassi
Esempi:Esempi: uomo(paolo)maggiore(X,3)maggiore(più(X,1),Y)ama(giovanni,maria)ama(padre(giovanni),giovanni)ama(padre(padre(giovanni)),giovanni)
maggiore(più(più(1,giovanni),Y),padre(3))
FMZ
Logica del primo ordine Sintassi
Ingredienti:Formule Ben FormateFormule Ben Formate
– Le Formule Atomiche sono FBF
– Se f1 e f2FBF e x è una variabile individuale allora
x.f1FBF
x.f1FBF
f1FBF
f1 f2FBF
f1 f2FBF
f1f2FBF
FMZ
Logica del primo ordine Sintassi
Ingredienti:Regole di inferenzaRegole di inferenza
– Eliminazione del quantificatore universale
– Eliminazione del quantificatore esistenziale
– Introduzione del quantificatore esistenziale
x.F(…x…)SUBST({x/a},F(…x…)}
x.F(…x…)
SUBST({x/a},F(…x…)}
F(…a…)
x.F(…x…)
Dove a non appartiene a costanti già introdotte
FMZ
1) un esempio filosofico(X)(uomo(X) mortale(X)) uomo(socrate) mortale(socrate)
2) due degli assiomi di base dei numeri naturaliinterpretare f e g come funzioni successore e predecessore la costante 0 come zero il predicato u come uguaglianza ) (X)(Y)(u(Y,f(X)) (Z)(u(Z,f(X)) u(Y,Z))) (X)( ~u(X,0)
((Y)(u(Y,g(X)) (Z)(u(Z,g(X)) u(Y,Z)))))
3) nella formula (X) p(X,Y), tutte le occorrenze di X sono vincolate, mentre Y è libera
Logica del primo ordine Sintassi esempiSintassi esempi
FMZ
Dare una interpretazione alle espressioni sintatticamente corrette. Definire se certe espressioni sono vere o false in base al significato che si dà ai componenti dell'espressione.InterpretazioneInterpretazione (I):• Insieme DInsieme D (dominio)
I(ai) = di per ciascuna costante individuale
• Insieme di funzioni I(fi) = fi
fi: Dn D per ciascuna lettera funzionale fi
• Insieme di relazioniI(Pi)=Pi
Pi Dn per ciascuna lettera predicativa Pi
Logica del primo ordine SemanticaSemantica
FMZ
Logica del primo ordine SemanticaSemantica
Interpretazione• Interpretazione delle formule atomiche
– I(Pi(a1,…,an)) =V se (I(a1),…,I(an))I(Pi)=F altrimenti
– I(x.Pi(a1,…,x,…,an)) =V
se per tutti gli x d accade che (I(a1),…,x,…,I(an))I(Pi)
=F altrimenti
FMZ
Logica del primo ordine SemanticaSemantica
Interpretazione• Interpretazione delle formule quantificateI(x.Pi(a1,…,x,…,an))=V se per tutti gli x D accade
che (I(a1),…,x,…,I(an))I(Pi)
=F altrimenti
I(x.Pi(a1,…,x,…,an)) =V se esiste x D tale che (I(a1),…,x,…,I(an))I(Pi)
=F altrimenti
FMZ
una sostituzionesostituzione è un insieme finito della forma{v1 t1,…, vn tn}
vi è una variabileti è un termine diverso da vi
le variabili vi, i=1,…,n sono tra loro distinteuna sostituzione è una funzione da variabili a termini
l’applicazione di ad E è l’espressione ottenuta da E sostituendo simultaneamente ogni occorrenza della variabile vi, i=1,…,n con il termine ti il risultato dell’applicazione (denotato da E) è unaistanza di E.
Sostituzione
FMZ
siano = {X1 t1,…, Xn tn} e = {Y1 u1,…, Ym um} due sostituzionila composizionecomposizione di e (denotata da ) è la sostituzione così definita
i) costruiamo l’insieme
{X1 t1,…, Xn tn, Y1 u1,…, Ym um}
ii) eliminiamo dall’insieme gli elementiXi titali che ti = Xi
iii) eliminiamo dall’insieme gli elementi Yj uj tali che Yj occorre in {X1,…, Xn}
Sostituzione: Composizione
FMZ
= {X f(Y), Y Z} = {X a, Y b, Z Y}
costruzione di costruzione di i) {X f(b), Y Y, X a, Y b, Z Y}ii) {X f(b), X a, Y b, Z Y}iii) {X f(b), Z Y}
costruzione di costruzione di i) {X a, Y b, Z Z, X f(Y), Y Z}ii) {X a, Y b, X f(Y), Y Z}iii) {X a, Y b}
Sostituzione: Composizione
FMZ
L’unificazione è un meccanismo che permette di calcolare unasostituzione al fine di rendere uguali due espressioni. Per espressione intendiamo un termine, un letterale o una congiunzione o disgiunzione di letterali.
Sia dato un insieme di espressioni (termini, atomi, etc.) {E1,…, Ek} una sostituzione è un unificatoreunificatore per {E1,…, Ek}se e solo se E1= E2 = …= EkUn insieme {E1,…, Ek} è unificabileunificabile se e solo se esiste una sostituzione tale che è un unificatore per {E1,…, Ek}ESEMPIOESEMPIO: l’insieme {p(a,Y), p(X,f(b))} è unificabile
dato che la sostituzione = {X a, Y f(b)} è un unificatore per l’insieme
Unificazione
FMZ
• un unificatore per l’insieme {E1,…, Ek} èl’unificatore più generale (most generalunifier, mgu) se e solo se per ogni unificatore dell’insieme {E1,…, Ek} esiste unasostituzione tale che =
• esiste un algoritmo (algoritmo diunificazione), che, dato un insieme diespressioni E = {E1,…, Ek},
rivela la sua non unificabilità, oppurecalcola un unificatore più generale per E
Unificazione
FMZ
Logica proposizionale vs. Logica del primo ordine
“Aggiunte”:
• Strutturazione dei letterali
• Introduzione delle variabili
• Introduzione dei quantificatori
FMZ
Logica del primo ordine
Socrate è un uomo.
Gli uomini sono mortali.
Allora Socrate è mortale.
• Costanti individuali{Socrate, Pino, Gino, Rino}
• Lettere predicative{Uomo,Mortale}
FMZ
Logica del primo ordine
Socrate è un uomo.Gli uomini sono mortali. Allora Socrate è mortale.
• Traduzione affermazioniUomo(Socrate)x.(Uomo(x) Mortale(x))
• Traduzione goalMortale(Socrate)
FMZ
Logica del primo ordine
x.(Uomo(x) Mortale(x))
(SUBST({x/Socrate},Uomo(x) Mortale(x))
Universal Elimination
Uomo(Socrate) Mortale(Socrate) , Uomo(Socrate) MP
Mortale(Socrate)