Linguaggio del primo ordine

Nella logica matematica il linguaggio del primo ordine, detto anche logica dei predicati 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

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^{1}$(x)" come $P^{1}(a_{1})\land P^{1}(a_{2})\land \ldots \land P^{1}(a_{n})$ se $a_{1},a_{2},\ldots ,a_{n}$ 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 e funzioni, cioè possibili proprietà o relazioni fra le variabili.

Definizione

Un linguaggio del primo ordine è caratterizzato da:

• un alfabeto di simboli (che siano simboli rappresentanti variabili, costanti, predicati, funzioni, connettivi, quantificatori o punteggiatura);
• un insieme di termini (che denotano 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

L'alfabeto di un linguaggio del primo ordine include:

simboli per variabili: $x_{1},x_{2},x_{3},\ldots$; simboli per costanti individuali: $a_{1},a_{2},\ldots$; simboli per predicati (o relazioni), a ciascuno dei quali è associato il suo numero di argomenti: $P^{1},Q^{1},P^{2},Q^{2},\ldots$; simboli per funzioni, a ciascuno dei quali è associato un numero corrispondente al numero di argomenti: $f^{1},g^{1},f^{2},g^{2},\ldots$; simboli ausiliari: "(", ")" e la virgola ","; simboli per connettivi logici: $\neg$ (negazione), $\rightarrow$ (implicazione), $\leftrightarrow$ (se e solo se), $\land$ (congiunzione), $\lor$ (disgiunzione); simboli per quantificatori: ∀ (quantificatore universale), ∃ (quantificatore esistenziale).

Ciascun simbolo di funzione e di predicato è denotato da un'arità. Essa indica il numero di argomenti o di oggetti ai quali la funzione o il predicato sono applicati. Le costanti possono essere considerati funzioni di arità 0.

Un esempio di alfabeto è quello del linguaggio dell'aritmetica del primo ordine che contiene due simboli per funzioni a 2 argomenti, $+,\times$, 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. Una frase sull'alfabeto dell'aritmetica del primo ordine è, ad esempio: $S(S(0))\times S(0)=S(S(0))$.

Termini

L'insieme dei termini del linguaggio è costituito dal minimo insieme di stringhe dell'alfabeto che possano denotare degli oggetti specifici, formalmente si dà la seguente definizione induttiva:

una costante individuale è un termine; una variabile è un termine; se $t_{1},\ldots ,t_{n}$ sono $n$ termini e $f^{n}$ è un simbolo di funzione $n$-aria del linguaggio, allora $f^{n}(t_{1},\ldots ,t_{n})$ è un termine; nient'altro è un termine.

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

• $a_{1}$ (regola 1);
• $x_{1}$ (regola 2);
• $f^{2}(a_{1},x_{1})$ se $f^{2}$ è un simbolo per funzione binaria (regola 3);
• $f^{1}(f^{2}(a_{1},x_{1}))$ se $f^{1}$ è un simbolo per funzione unaria (regola 3).

Formule ben formate

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:

Per un linguaggio del primo ordine dato, l'insieme delle formule ben formate è il minimo insieme tale che:

ogni formula atomica $A^{n}(t_{1},\ldots ,t_{n})$ è una fbf, dove $A^{n}$ è un simbolo per predicato $n$-ario e $t_{1},\ldots ,t_{n}$ sono termini se ${\mathcal {A}}$ e ${\mathcal {B}}$ sono fbf e $x$ è una variabile, allora sono fbf anche $\bot$ $\neg {\mathcal {A}}$ ${\mathcal {A}}\rightarrow {\mathcal {B}}$ ${\mathcal {A}}\leftrightarrow {\mathcal {B}}$ ${\mathcal {A}}\land {\mathcal {B}}$ ${\mathcal {A}}\lor {\mathcal {B}}$ $(\forall x){\mathcal {A}}$ $(\exists x){\mathcal {A}}$ tutte e sole le fbf sono definite dalle regole precedenti.

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

$x+y=0,$

$\forall z(x+y=0),$

$(x=x)\to \forall x(S(x)=S(y)).$

Non è invece una fbf

$(x=x)\to \forall x(S(x)),$

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

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

Ad esempio nella fbf

$\forall x(P^{1}(x)\land Q^{1}(y))$

le sottoformule sono

$\forall x(P^{1}(x)\land Q^{1}(y))$

$P^{1}(x)\land Q^{1}(y)$

$P^{1}(x)$

$Q^{1}(y)$

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

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;
• per ogni $n$ un insieme di funzioni da $U^{n}$ in $U$ da associare a ciascun simbolo di funzione $n$-aria del linguaggio;
• per ogni $n$ un insieme di relazioni $n$-arie su $U$ da associare a ciascun simbolo di relazione $n$-arie del linguaggio;

la collezione di questi insiemi, unita 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à.

Bibliografia

• Andrea Asperti e Agata Ciabattoni, 4. Logica dei predicati, in Logica a informatica, McGraw-Hill, 1997.

Voci correlate

• Linguaggio dell'aritmetica del primo ordine
• Logica proposizionale
• Teoria del primo ordine

Collegamenti esterni

• (EN) first-order language, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.