• Istituto
    • Chi Siamo
    • La nostra storia
  • Magazine
    • Agenda
    • Atlante
    • Il Faro
    • Il Chiasmo
    • Diritto
    • Il Tascabile
    • Le Parole Valgono
    • Lingua italiana
    • WebTv
  • Catalogo
    • Le Opere
    • Bottega Treccani
    • Gli Ebook
    • Le Nostre Sedi
  • Scuola e Formazione
    • Portale Treccani Scuola
    • Formazione Digitale
    • Formazione Master
    • Scuola del Tascabile
  • Libri
    • Vai al portale
  • Arte
    • Vai al portale
  • Treccani Cultura
    • Chi Siamo
    • Come Aderire
    • Progetti
    • Iniziative Cultura
    • Eventi Sala Igea
  • ACQUISTA SU EMPORIUM
    • Arte
    • Cartoleria
    • Design & Alto Artigianato
    • Editoria
    • Idee
    • Marchi e Selezioni
  • Accedi
    • Modifica Profilo
    • Treccani X

aritmetica di Presburger

di Luca Tomassini - Enciclopedia della Scienza e della Tecnica (2008)
  • Condividi

aritmetica di Presburger

Luca Tomassini

Versione semplificata dell’aritmetica di Peano, ottenuta da quest’ultima eliminando l’operazione di moltiplicazione. Più precisamente, l’aritmetica di Presburger si ottiene da quella di Peano conservando invariati tutti gli assiomi con l’eccezione di quelli della moltiplicazione, rimossi dal sistema con il simbolo stesso dell’operazione (×) ed è per questa ragione meno potente. Restano quindi: (a) gli assiomi che definiscono il successore s(n) di un numero intero n e escludono che lo 0 sia il successore di un qualche numero; (b) gli assiomi che definiscono le proprietà elementari dell’addizione, ossia che (per ogni n e m) n+0=n e n+s(m)=s(n+m); (c) l’assioma di induzione, secondo il quale ogni proprietà P dei numeri naturali esprimibile nell’aritmetica tale che P è soddisfatta da 0 e da s(n) qualora sia soddisfatta da n allora essa è soddisfatta per ogni intero m. Come è evidente, la formulazione di quest’ultimo assioma si fonda su una quantificazione nella classe delle proprietà ­esprimibili nell’aritmetica (si parla di ogni proprietà P) e fa dunque intervenire la logica al secondo livello (quella appunto che ‘parla’ dei teoremi della logica al primo). Nell’aritmetica di Peano, per formulare l’assioma di induzione al primo livello della logica si paga un prezzo molto alto: esso è sostituito da un insieme infinito di assiomi, uno per ciascuna proprietà P. La caratteristica fondamentale dell’aritmetica di Presburger è proprio di poter essere finitamente assiomatizzata, ossia in essa è possibile sostituire gli infiniti ‘assiomi di induzione’ di cui sopra con un numero finito di altri assiomi ottenendo una teoria con gli stessi identici teoremi. Un’importante conseguenza di questo fatto è la completezza della teoria nel senso di Hilbert-Gödel, dimostrata dal matematico polacco Mojzesz Presburger nel 1929: differentemente dall’arit­metica di Peano, in quella di Presburger ogni proposizione vera (ossia che non ammette controesempi) è anche dimostrabile (in un numero finito di passi). In altri termini, nell’aritmetica di Presburger ogni proposizione è decidibile.

→ Programmazione, algoritmi di

Vedi anche
numeri interi In matematica, si chiamano interi positivi (o naturali) i numeri della successione infinita 1, 2, 3, 4, ... ciascuno dei quali si ottiene dal precedente aggiungendo a esso l’unità. Gli interi negativi sono numeri della successione −1, −2, −3, ... Gli interi positivi e negativi, insieme con lo zero, si ... postulato linguistica Forme o parole postulate Quelle forme o parole antiche, di solito contrassegnate con asterisco, che non sono documentate in alcun testo, ma di cui viene ragionevolmente supposta l’esistenza come etimi di parole moderne (per es., il lat. *rocca che, pur non ricorrendo in alcun testo latino, ... teorema In matematica e nelle scienze deduttive, ogni enunciato (o formula o proprietà) che può essere dimostrato, cioè che può essere dedotto logicamente dagli enunciati primitivi, detti assiomi o postulati. In un sistema assiomatico moderno la distinzione fra teorema e assiomi non è però netta e assoluta in ... addizione matematica Operazione aritmetica mediante la quale si trova la somma di due o più numeri (detti addendi o termini). Nell’accezione più comune il termine addizione si riferisce al caso dei numeri interi positivi. Nell’ambito dei numeri cardinali l’addizione si definisce in questo modo: date due collezioni ...
Categorie
  • LOGICA in Filosofia
Vocabolario
aritmètica
aritmetica aritmètica (ant. arismètica e arismètrica) s. f. [dal lat. arithmetĭca (lat. mediev. arismet[r]ica), gr. ἀριϑμητική (τέχνη): v. aritmetico]. – 1. Parte della matematica concernente lo studio dei numeri, soprattutto dei numeri...
aritmètico
aritmetico aritmètico (ant. arismètico e arismètrico) agg. [dal lat. arithmetĭcus (lat. mediev. arismet[r]icus), gr. ἀριϑμητικός, der. di ἀριϑμός «numero» (pl. m. -ci). – 1. Che riguarda l’aritmetica, o anche, che concerne i numeri interi;...
  • Istituto
    • Chi Siamo
    • La nostra storia
  • Magazine
    • Agenda
    • Atlante
    • Il Faro
    • Il Chiasmo
    • Diritto
    • Il Tascabile
    • Le Parole Valgono
    • Lingua italiana
    • WebTv
  • Catalogo
    • Le Opere
    • Bottega Treccani
    • Gli Ebook
    • Le Nostre Sedi
  • Scuola e Formazione
    • Portale Treccani Scuola
    • Formazione Digitale
    • Formazione Master
    • Scuola del Tascabile
  • Libri
    • Vai al portale
  • Arte
    • Vai al portale
  • Treccani Cultura
    • Chi Siamo
    • Come Aderire
    • Progetti
    • Iniziative Cultura
    • Eventi Sala Igea
  • ACQUISTA SU EMPORIUM
    • Arte
    • Cartoleria
    • Design & Alto Artigianato
    • Editoria
    • Idee
    • Marchi e Selezioni
  • Accedi
    • Modifica Profilo
    • Treccani X
  • Ricerca
    • Enciclopedia
    • Vocabolario
    • Sinonimi
    • Biografico
    • Indice Alfabetico

Istituto della Enciclopedia Italiana fondata da Giovanni Treccani S.p.A. © Tutti i diritti riservati

Partita Iva 00892411000

  • facebook
  • twitter
  • youtube
  • instagram
  • Contatti
  • Redazione
  • Termini e Condizioni generali
  • Condizioni di utilizzo dei Servizi
  • Informazioni sui Cookie
  • Trattamento dei dati personali