Linguaggio del primo ordine

Pagina 1

Il Linguaggio del I ordine. La maggior parte delle affermazioni che ci troviamo a trattare non sono frasi che sono vere o false. Ad esempio una frase del tipo “x è un numero primo” sarà vera se alla variabile x si attribuisce il valore 7, ma sarà falsa se ad x si attribuisce il valore 4, mentre la frase “per ogni numero x, x è primo” è sempre falsa e la frase “esiste un numero x tale che x è primo” è sempre vera. Questi semplici esempi mostrano che il linguaggio della logica proposizionale non ha l’espressività sufficiente a formalizzare gran parte dei nostri processi di ragionamento. Per ovviare alle carenze di espressività della logica proposizionale si introduce quindi un nuovo linguaggio, detto linguaggio del primo ordine , il cui alfabeto è costituito da • costanti : a,b,… (al più un’infinità numerabile e quindi spesso indicate anche con ai) • variabili : x,y,… (al più un’infinità numerabile e quindi spesso indicate anche con xi) • lettere funzionali : fi n (i,n interi naturali, l’apice indica l’arità, il pedice distingue eventualmente lettere diverse con la stessa arità) • lettere predicative : A i n (i,n interi naturali, l’apice indica l’arità, il pedice distingue eventualmente lettere diverse con la stessa arità) e da • connettivi : ∼ , ∧ , ∨ , ⇒ , ⇔, • quantificatori : ∀x (detto quantificatore universale ), ∃x (detto quantificatore esistenziale ), dove x è una qualsiasi variabile, • simboli ausiliari : ( , ) Con questi simboli definiamo ricorsivamente i termini , cioè un insieme di espressioni così definito ricorsivamente: • ogni costante è un termine, • ogni variabile è un termine, • se t1,t2,… tn sono termini e fi n è una lettera funzionale, anche fi n(t1,t2,… tn) è un termine, • niente altro è un termine. Con le lettere predicative e i termini possiamo…