Se riscontri problemi nella visualizzazione dei caratteri, clicca qui

Linguaggio del primo ordine

Da Wikipedia, l'enciclopedia libera.

Nella logica matematica il linguaggio del primo ordine è un linguaggio formale che serve per gestire meccanicamente enunciati e ragionamenti che coinvolgono i connettivi logici, le relazioni e i quantificatori "per ogni ..." (∀) ed "esiste..." (∃). L'espressione "del primo ordine" indica che c'è un insieme di riferimento e i quantificatori possano riguardare solo gli elementi di tale insieme e non i sottoinsiemi; ad esempio si può dire "per tutti gli x elementi dell'insieme vale P(x)" ma non si può dire "per tutti i sottoinsiemi A vale P(A)" (le teorie in cui ci sono quantificatori che spaziano sui sottoinsiemi dell'insieme di riferimento sono dette invece del secondo ordine).

Motivazione[modifica | modifica wikitesto]

Nel linguaggio della logica proposizionale è possibile formalizzare argomenti che coinvolgono quantificatori solo nei casi in cui l'insieme in cui si "quantifica" è finito, ad esempio traducendo l'enunciato "per ogni x P(x)" come se denotano tutti gli elementi dell'insieme in cui si sta quantificando. Quando si deve quantificare su insiemi con un numero imprecisato di elementi o su insiemi infiniti - come succede se si sta enunciando un teorema aritmetico come "ogni numero intero ammette un'unica fattorizzazione" - la logica proposizionale non è più in grado di servire allo scopo.

L'idea che c'è dietro al concetto di linguaggio del primo ordine è quella di integrare il linguaggio della logica proposizionale con simboli per i quantificatori, variabili su cui si possa "quantificare" e simboli che rappresentino predicati (cioè possibili proprietà o relazioni).

Definizione[modifica | modifica wikitesto]

Un linguaggio del primo ordine è caratterizzato da:

  • un alfabeto di simboli
  • un insieme di termini (che dovrebbero denotare gli "oggetti" dell'insieme che si sta considerando)
  • un insieme di formule ben formate (o più brevemente fbf o semplicemente formule) cioè un insieme di stringhe composte di simboli dell'alfabeto che vengono considerate sintatticamente corrette

Alfabeto[modifica | modifica wikitesto]

L'alfabeto di un linguaggio del primo ordine include:

  • simboli per variabili (infiniti):
  • simboli per costanti individuali (eventualmente nessuno):
  • simboli per predicati (o relazioni), a ciascuno dei quali è associato il suo numero di argomenti:
  • simboli per funzioni, a ciascuno dei quali è associato un numero corrispondente al numero di argomenti:
  • simboli di punteggiatura: "(", ")" e la virgola ","
  • simboli per connettivi logici: (negazione), (implicazione), (se e solo se), (e), (oppure)
  • simboli per quantificatori: ∀ (quantificatore universale), ∃ (quantificatore esistenziale)

Un esempio è l'alfabeto del Linguaggio dell'aritmetica del primo ordine che contiene due simboli per funzioni a 2 argomenti, , un simbolo per una relazione a due argomenti, =, un simbolo per costante individuale, 0, e un simbolo per funzione a un argomento, S, la funzione successore.

Termini[modifica | modifica wikitesto]

L'insieme dei termini è costituito da tutte quelle stringhe dell'alfabeto che si presume possano denotare degli oggetti specifici, formalmente si dà la seguente definizione induttiva:

  1. una costante individuale è un termine
  2. una variabile è un termine
  3. se sono n termini e è un simbolo per funzione n-aria allora è un termine
  4. nient'altro è un termine

Esempi di termini si possono ottenere applicando iterativamente le regole, si hanno quindi termini come

  • (regola 1)
  • (regola 2)
  • se è un simbolo per funzione binaria (regola 3)
  • se è un simbolo per funzione unaria (regola 3)

Formule ben formate[modifica | modifica wikitesto]

L'insieme delle formule ben formate (o - brevemente - fbf) è formato dalle sequenze di simboli dell'alfabeto con cui si vorrebbero rappresentare enunciati sintatticamente corretti. In modo formale una fbf si definisce nel seguente modo:

Prima si definisce formula atomica una sequenza di simboli del tipo

dove è un simbolo per predicato n-ario e sono termini, poi si da la seguente definizione induttiva:

1. ogni formula atomica è una fbf
2. se e sono fbf e è una variabile allora sono fbf anche

3. tutte e sole le fbf sono definite dalle regole precedenti;

Esempi di formule ben formate nel linguaggio dell'aritmetica del primo ordine sono

Non è invece una fbf

poiché nel linguaggio dell'aritmetica del primo ordine S non è un simbolo per predicato bensì un simbolo per funzione.

Sottoformule, variabili libere e formule chiuse[modifica | modifica wikitesto]

Una sottoformula è una stringa interna a una fbf che è anch'essa una fbf.
Ad esempio nella fbf

le sottoformule sono

In una fbf i quantificatori compaiono necessariamente davanti a sottoformule e sono associati a una variabile (quella che compare immediatamente dopo il simbolo ∀ o ∃).
Una variabile all'interno di una formula si dice libera se non compare in nessuna sottoformula preceduta da un quantificatore associato a tale variabile. Altrimenti si dice vincolata. Nell'esempio precedente x è vincolata mentre y è libera.

Si chiama formula chiusa una fbf che non contenga variabili libere, formula aperta una che le contiene.

Semantica[modifica | modifica wikitesto]

Finora sono state date le regole per una "corretta" formazione degli enunciati di un linguaggio del primo ordine (le fbf) senza considerare che cosa questi volessero significare. Per attribuire un significato alle formule del linguaggio occorre indicare:

  • un insieme di riferimento U (l'universo del discorso) a cui appartengono gli "oggetti" di cui si sta parlando (denotati dalle costanti individuali) e in cui spaziano le variabili dei quantificatori;
  • un insieme di elementi di U da associare a ciascuna costante individuale del linguaggio;
  • per ogni n un insieme di funzioni da in sé stesso da associare a ciascun simbolo di funzione n-aria del linguaggio;
  • per ogni n un insieme di relazioni n-aria su da associare a ciascun simbolo di relazione n-arie del linguaggio;

la collezione di questi insiemi insieme all'associazione di ciascun elemento al proprio "simbolo" individua quello che si chiama un modello per il linguaggio.

Un modello permette di associare univocamente a ogni termine chiuso (cioè senza variabili libere) un elemento dell'universo del discorso e a ogni fbf un valore di verità.

Voci correlate[modifica | modifica wikitesto]

Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica