Introduzione alla logica formale Parte Preambolo: l’algebra di Boole e la logica



Scaricare 461 b.
23.05.2018
Dimensione del file461 b.



Introduzione alla logica formale

  • Parte 1. Preambolo: l’algebra di Boole e la logica

  • Parte 2. Logica proposizionale

  • Parte 3. Logica predicativa del primo ordine





Limiti della logica proposizionale

  • La logica proposizionale ha molte interessanti proprietà:

    • è completa
      • tutte le conseguenze logiche sono derivabili per via sintattica e viceversa
    • è decidibile in modo automatico
  • Il difetto principale è la semplicità del linguaggio:

  • e la conseguente semplicità delle strutture semantiche:

    • solo un insieme {0, 1}
    • nessuna possibilità di caratterizzare strutture più complesse


Limitazioni linguistiche di LP

  • Esempio :

    • a: “Ogni uomo è mortale”
    • b: “Socrate è un uomo”
    • c: “Socrate è mortale”
  • Il legame logico è evidente

  • Nella traduzione in logica proposizionale, le tre proposizioni a, b e c non presentano alcun legame

  • Altro esempio :

    • d: “Se tutti gli interi fossero pari, sarebbero divisibili per 2”
    • e: “Il numero 3 non è divisibile per 2”
    • f: “Non tutti i numeri interi sono pari”


Limitazioni rappresentative di LP

  • Il problema non è solo linguistico ma strutturale

  • Anche semplificando al massimo, il mondo che osserviamo è fatto di oggetti e di relazioni tra oggetti

  • Esempio :

    • come si possono tradurre questi elementi in forma simbolica?
    • come si stabilisce la correttezza dei ragionamenti? (p.es. Amelia e Alba sono sorelle?)


Estensione predicativa: obiettivi

  • Linguaggio formale esteso

    • in grado di rappresentare meglio la struttura delle affermazioni
  • Semantica

    • in riferimento a strutture più complesse, capaci di descrivere oggetti e relazioni tra oggetti
  • Si vuole assolutamente

    • mantenere l’impianto formale del sistema logico-simbolico
    • mantenere la capacità di rappresentazione dei simboli rispetto ai significati (correttezza)
  • Sarebbe meglio

    • mantenere la garanzia di completa rappresentazione dei significati (completezza)


LPO - Linguaggio

  • Un linguaggio predicativo LPO comprende:

    • un insieme di simboli predicativi, aventi un numero prestabilito di argomenti
      • esempio: P(x), G(x, y), Q(x, y, z), etc.
      • unica eccezione (per comodità) ‘=’ (e.g. x = y) (ma è un predicato)
    • un insieme di simboli funzionali, aventi un numero prestabilito di argomenti
      • esempio: f(x), g(x, y), h(x, y, z), ...
    • un insieme di variabili
      • esempio: x, y, z, ...
    • un insieme di costanti individuali
      • esempio: a, b, c, ...
    • i connettivi primari ,  e derivati , , 
    • il quantificatore universale  ed il quantificatore esistenziale
    • le due parentesi ( e )


LPO - Regole di buona formazione

  • Termini

    • ogni variabile o costante individuale è un termine
    • se f è un simbolo funzionale a n argomenti e t1, ..., tn sono termini, allora f(t1, ..., tn ) è un termine
      • esempi: x, a, f(y), g(b, c)
  • Formula atomica

    • se P è un simbolo predicativo a n argomenti e t1, ..., tn sono termini, allora P(t1, ..., tn ) è una formula atomica
      • esempi: P(x), Q(y, a), R(b, c, x)
  • Formule ben formate (fbf)

    • ogni formula atomica è una fbf
    • se  è una fbf, allora () è una fbf
    • se  e  sono fbf, allora anche (  ), (  ), (  ) e (  ) lo sono
    • se  è una fbf, allora anche (x ) e (x ) sono fbf


LPO - Formule aperte, enunciati

  • Variabili libere e vincolate

    • una variabile (in una fbf) è vincolata se si trova nel raggio di azione di un quantificatore
    • una variabile è libera se non è vincolata
      • esempi di variabile vincolata:
        • x P(x)
        • x (P(x)  (A(x)  B(x))
      • esempi di variabile libera:
        • P(x)
        • y (P(y)  (A(x, y)  B(y))
  • Formule aperte e chiuse

    • si dice aperta una fbf in cui occorre almeno una variabile libera
    • si dice chiusa o anche enunciato in caso contrario
    • solo le fbf chiuse, cioè gli enunciati, hanno un valore di verità
      • (in quanto rappresentano delle affermazioni ...)


LPO - Strutture e interpretazioni

  • La struttura semantica di riferimento assai più complessa di {0, 1} ...

  • Una struttura <U, i > per un linguaggio LPO contiene:

    • un insieme di oggetti U (l’universo del discorso)
    • un’interpretazione i, cioè una funzione che associa
      • ad ogni simbolo predicativo a n argomenti una relazione n-aria in Un
      • ad ogni simbolo funzionale a n argomenti una funzione n-aria in Un
      • ad ogni costante individuale un elemento di U
  • Per le variabili

    • una assegnazione s è una funzione che associa
      • ad ogni variabile un elemento di U


LPO - Esempio 1

  • Linguaggio

    • simboli predicativi: Uomo(.), Pollo(.), Mortale(.)
    • variabili: x, y, z, ...
    • costanti individuali: Socrate, Aristotele, Platone, Gino, Mino, Tino
  • Interpretazione

    • universo del discorso U: {Socrate, Aristotele, Platone, Gino, Mino, Tino}
    • interpretazione i:
      • costanti individuali: i(Socrate) = Socrate, i(Aristotele) = Aristotele, etc.
      • simboli predicativi: i(Uomo(.)) = {Socrate, Aristotele, Platone} i(Pollo(.)) = {Gino, Mino, Tino} i(Mortale(.)) = {Socrate, Aristotele, Platone, Gino, Mino, Tino}
  • Assegnazione

    • esempio: s ={[x/Socrate], [y/Platone], ...} (i.e. per tutte le variabili)


LPO - Esempio 2

  • Linguaggio

    • simboli predicativi: Uomo(.), Donna(.), Fratello(..), Sorella(..), Genitore(..)
    • simboli funzionali: madre(.), padre(.)
    • variabili: x, y, z, ...
    • costanti individuali: Mario, Paola, Remo, Oscar, Amelia, Alba
  • Interpretazione

    • universo del discorso U: {Mario, Paola, Remo, Oscar, Amelia, Alba}
    • interpretazione i:
      • costanti individuali: i(Mario) = Mario, i(Paola) = Paola, etc.
      • simboli predicativi: i(Uomo(.)) = {Mario, Remo, Oscar} i(Donna(.)) = {Paola, Amelia, Alba} i(Fratello(.)) = {<Oscar, Mario>, < Mario, Oscar>, < Remo, Paola>} i(Sorella(.)) = {<Paola, Remo>, <Alba, Amelia>, <Amelia, Alba>}
      • simboli funzionali: i(madre(.)) = {<Alba, Paola>, <Amelia, Paola>} i(padre(.)) = {<Alba, Mario>, <Amelia, Mario>}


LPO - Soddisfacimento

  • Formule atomiche

    • data una struttura <U, i >, un’assegnazione s ed una formula atomica 
    • si ha che <U, i >  [s] sse
      • se  ha la forma t1 = t2 allora i(t1) [s]  s(t2) [s] (se si usa l’identità)
      • se  ha la forma P(t1, ... , tn) allora <i(t1) [s], ..., i(tn) [s]>  i(P )
  • Fbf qualsiasi

    • si ha che <U, i >  [s] sse
      • se  è una formula atomica, vedi sopra
      • se  allora <U, i >  [s]
      • se    allora <U, i >  [s] e <U, i >  [s]
      • se    allora <U, i >  [s] o <U, i >  [s]
      • se    allora non <U, i >  [s] e <U, i >  [s]
      • se x  allora per ogni d U si ha <U, i >  [s][x/d]
      • per definizione x   x 


LPO - Esempio 3

  • (in riferimento alla interpretazione dell’esempio 2)

  • Soddisfacimento

    • <U, i >  Uomo(Mario)
      • in quanto Marioi(Uomo(.))
    • <U, i >  Uomo(padre(Alba))
      • in quanto <Alba, Mario>  i(padre(.)) e Marioi(Uomo(.))
    • <U, i >  Uomo(Paola)
      • in quanto Paolai(Uomo(.))
    • <U, i >  Uomo(Mario)  Genitore(Mario, Alba)
      • in quanto Marioi(Uomo(.)) e <Mario, Alba>  i(Genitore(..))
    • <U, i >  x (Uomo(x)  Donna(x))
      • in quanto per ogni d U si ha che <U, i >  (Uomo(x)  Donna(x)) [x/d]
  • Assegnazione

    • <U, i >  Donna(x)[x/Paola, ...]
    • <U, i >  Donna(x)[x/Mario, ...]


LPO - Modelli, validità

  • Verità e modelli

    • un enunciato  è vero in una struttura <U, i > sse
      • esiste un’assegnazione s tale per cui <U, i >  [s]
      • per un enunciato, l’esistenza di una s equivale a “per ogni s
    • una struttura <U, i > tale da rendere vero un enunciato  è detta modello di 
    • una struttura <U, i > è detta modello di un insieme di enunciati  sse rende veri tutti gli enunciati in 
      • si scrive allora <U, i >  
  • Validità

    • un enunciato  è valido se è vero in qualunque struttura <U, i >
      • si scrive allora  
  • Inconsistenza

    • un enunciato  è inconsistente se non ha un modello


LPO - Derivazione, teorie, assiomi

  • Come nel caso di LP, si ha un’unica regola di derivazione

    • il modus ponens   ,   
  • La definizione di derivazione o dimostrazione (intesa come successione di passi) è identica a quella di LP

  • Un qualsiasi insieme di fbf  può essere detto una teoria

  • Dato un insieme di fbf , l’insieme dei teoremi di  è l’insieme di tutte le fbf derivabili a partire da 

    • teoremi() = { :   }
  • Un  è una assiomatizzazione di  sse

    •   teoremi()


Costruzione e uso di teorie in LPO

  • Il sistema di assiomi Ax descrive la teoria delle fbf valide

    • le fbf valide si applicano a qualsiasi ragionamento (sono ‘leggi logiche’ o, meglio, leggi di LPO)
  • Analogamente possono essere costruite teorie particolari

    • si definisce un insieme  di fbf (assiomi o fatti noti) che descrive le proprietà degli oggetti di cui si parla
  • La derivazione di teoremi serve a ‘scoprire’, cioè a rendere espliciti, gli elementi di una teoria

    • in particolare quelli non direttamente descritti in 
  • Due problemi per il calcolo

    • escludendo la possibilità di derivare ‘a pioggia’ tutti i teoremi
    • in che modo ipotizzare i teoremi
    • come dimostrare che lo sono (o che non lo sono)


LPO - Sistema di assiomi

  • Sei schemi di assioma per LPO:

    • Ax1   (  )
    • Ax2 (  (  ))  ((  )  (  ))
    • Ax3 (  )  (  )
    • Ax4 x   [x/t] se t è sostituibile per x in 
    • Ax5 x (  )  (x   x )
    • Ax6   x  se x non occorre libera in 
    • ogni sostituzione di ,  e  con una fbf è un assioma
  • Altri due schemi di assioma se si usa l’identità:

    • Ax7 t = t
    • Ax8 (t = u)  ([x/t]  [x/u])


LPO - Esempio 4

  • Derivazione: “Socrate è mortale”:

    • {x (Uomo(x)  Mortale(x)), Uomo(Socrate)}  Mortale(Socrate) 1: x (Uomo(x)  Mortale(x)) (premessa) 2: Uomo(Socrate)  Mortale(Socrate) (Ax4 con [x/Socrate]) 3: Uomo(Socrate) (premessa) 4: Mortale(Socrate) (mp 2, 3)


LPO - Esempio 5

  • Derivazione: “Alba è sorella di Amelia”

    • Regole: xy ((Donna(x)  z (Genitore(z, x)  Genitore(z, y)))  Sorella(x, y))
    • Fatti: Donna(Alba), Donna(Amelia), Genitore(Mario, Alba), Genitore(Mario, Amelia)
    • 1: y ((Donna(Alba)  z (Genitore(z, Alba)  Genitore(z, y)))  Sorella(Alba, y)) (Ax4 con [x/Alba]) 2: (Donna(Alba)  z (Genitore(z, Alba)  Genitore(z, Amelia)))  Sorella(Alba, Amelia) (Ax4 con [y/Amelia]) 3: (Genitore(Mario, Alba)  Genitore(Mario, Amelia))  z (Genitore(z, Alba)  Genitore(z, Amelia)) (teorema) 4: Genitore(Mario, Alba)  Genitore(Mario, Amelia) (premesse) 5: z (Genitore(z, Alba)  Genitore(z, Amelia)) (mp 3, 4) 6: Donna(Alba) (premesse) 7: (Donna(Alba)  z (Genitore(z, Alba)  Genitore(z, Amelia))) (5 + 6) 8: Sorella(Alba, Amelia) (mp 2, 7)


LPO - Correttezza e completezza

  • Correttezza di LPO       

  • Completezza di LPO     

  • Validità del sistema di assiomi

    • le fbf del sistema di assiomi Ax per LPO sono valide
  • Completezza del sistema di assiomi

    • la teoria delle fbf valide di LPO coincide con l’insieme dei teoremi del sistema di assiomi Ax
    •   teoremi(Ax)   


LPO - Esempio 6: semantica intuitiva

  • “Ogni uomo è mortale”

    • l’insieme degli uomini è incluso nell’insieme dei mortali
    • infatti: x (Uomo(x)  Mortale(x)) è soddisfatto in una struttura <U, i > dove x (Uomo(x)  Mortale(x)) (equivalenza logica) x (Uomo(x)  Mortale(x)) (De Morgan) x (Uomo(x)  Mortale(x)) (definzione di x) quindi in <U, i > non esistono d tali per cui <U, i >  Uomo(x)[x/d] e <U, i >  Mortale(x)[x/d]
  • “Socrate è mortale”

    • l’oggetto Socrate appartiene all’insieme dei mortali
  • Alba è sorella di Amelia

    • la relazione “sorella” include


LPO - Generalità

  • Assumendo come riferimento la teoria (intuitiva) degli insiemi, la logica predicativa del primo ordine ha un raggio d’azione molto generale

  • Il valore pragmatico è notevole

    • rappresentazione di ragionamenti in astratto
    • a patto di avere una ‘macchina’ efficiente
  • Il valore filosofico è anche maggiore

    • possiamo fondare teorie tramite il linguaggio?


LPO - Limitazioni intrinseche

  • -incompletezza

    • la teoria dei numeri contiene degli enunciati veri (nella struttura di riferimento) che sono tuttavia indimostrabili (Gödel)
  • Indimostrabilità della consistenza (esistenza di un modello)

    • all’interno della teoria dei numeri non è possibile dimostrare che la teoria stessa è consistente (Gödel)
  • Indecidibilità

    • non esiste una procedura automatica di valore generale (Church)
  • Inoltre:

    • le teorie che includono il simbolo di identità sono sempre interpretabili in una struttura in cui la relazione corrispondente non è l’identità tra oggetti
    • alcune proprietà non sono caratterizzabili da una teoria
      • ogni teoria che ammette un modello infinito ha anche un modello numerabile (Löwenheim-Skolem)





©astratto.info 2017
invia messaggio

    Pagina principale