Teoria del primo ordine

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da Logica del prim'ordine)
Vai alla navigazione Vai alla ricerca

Nella logica matematica, una teoria del primo ordine (o calcolo dei predicati) è un particolare sistema formale, cioè una teoria formale, in cui è possibile esprimere enunciati e dedurre le loro conseguenze logiche in modo del tutto formale e meccanico. La teoria del prim'ordine estende di fatto la logica proposizionale con l'introduzione di quantificatori esistenziali e universali, predicati, funzioni, variabili e costanti, che apportano maggiore potenza espressiva al calcolo dei predicati[1].

Come per la logica proposizionale, la teoria del primo ordine può essere scissa in due parti separate:

  • la sintassi, che definisce il vocabolario simbolico di base e le regole per la costruzione di enunciati complessi,
  • la semantica, che interpreta questi enunciati come espressione delle relazioni tra gli elementi di un dominio, aggregati mediante un assegnamento.

Un predicato è un'espressione linguistica che può essere collegata a uno o più elementi del dominio per formare una frase. Ad esempio, nella frase "Marte è un pianeta", l'espressione "è un pianeta" è un predicato che è legato al nome (un simbolo costante) "Marte" per formare una frase. Nella frase "Giove è più grande di Marte", l'espressione "è più grande di" è un predicato che collega i due nomi, "Giove" e "Marte", per formare una frase.

In logica matematica, quando un predicato è legato a un'espressione, si dice che esprime una proprietà (come la proprietà di essere un pianeta nell'esempio precedente), e quando è legato a due o più espressioni, si dice che esprime una relazione (come la relazione per un pianeta di essere più grande di un altro). Così è ragionare su affermazioni come "Ogni x è bello" e "Esiste un x tale che per ogni y, x è amico di y", che simbolicamente è espresso dalla formula: .

Va notato che la teoria del primo ordine non contiene in sé nessuna relazione specifica (come una relazione d'ordine, inclusione o uguaglianza).

Gli elementi che definiscono una teoria del primo ordine sono:

Esempi di teorie del primo ordine sono l'aritmetica di Peano, l'aritmetica di Robinson, la teoria degli insiemi di Zermelo-Fraenkel.

Dimostrazioni formali

[modifica | modifica wikitesto]

Una dimostrazione di una formula in una teoria del primo ordine T è una sequenza ordinata di formule

tale che

  • ogni formula o è un assioma di T o è deducibile da una o più formule ad essa precedenti mediante una regola di inferenza.

Una formula che ha una dimostrazione formale in T si dice dimostrabile o derivabile. Se la formula è dimostrabile in T si usa la notazione

o semplicemente

se la teoria di riferimento è evidente dal contesto.

Proprietà sintattiche

[modifica | modifica wikitesto]

Una teoria del primo ordine T si dice:

  • sintatticamente completa se per ogni formula si ha
oppure
  • sintatticamente coerente se non esiste nessuna formula per cui si ha
e contemporaneamente
  1. ^ Asperti e Ciabattoni, pp. 99-100.
  • Andrea Asperti e Agata Ciabattoni, 4. Logica dei predicati, in Logica a informatica, McGraw-Hill, 1997.

Voci correlate

[modifica | modifica wikitesto]

Collegamenti esterni

[modifica | modifica wikitesto]
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica