Linguaggio del primo ordine

Da Wikipedia, l'enciclopedia libera.

Questa voce di matematica è solo un abbozzo: contribuisci a migliorarla secondo le convenzioni di Wikipedia.

Nella logica matematica il linguaggio del primo ordine è un linguaggio formalizzato che serve per gestire meccanicamente enunciati e ragionamenti che coinvolgono i connettivi logici, le relazioni e i quantificatori "per ogni ..." ( $\forall$ ) ed "esiste..." ( $\exist$ ). L'espressione "del primo ordine" indica che c'è un insieme di riferimento e i quantificatori possono 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)"; quando si permette che i quantificatori possono spaziare anche tra tutti i possibili sottoinsiemi dell'insieme di riferimento si parla di teoria del secondo ordine.

[modifica] 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(x)" come $P(a_1) \land P(a_2) \land ... \land P(a_n)$ se $a 1, a 2,..., 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 (cioè possibili proprietà o relazioni).

[modifica] Definizione

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

[modifica] Alfabeto

L' alfabeto di un linguaggio del primo ordine include:

simboli per variabili (infiniti): $x 1, x 2, x 3,...$
simboli per costanti individuali (eventualmente nessuno): $a 1, a 2,...$
simboli per predicati (o relazioni), a ciascuno dei quali è associato il suo numero di argomenti: $P 1, Q 1, P 2, Q 2,...$
simboli per funzioni, a ciascuno dei quali è associato un numero corrispondente al numero di argomenti: $f 1, g 1, f 2, g 2,...$
simboli di punteggiatura: "(", ")" e la virgola ","
simboli per connettivi logici: $\neg$ (negazione), $\rightarrow$ (implicazione), $\leftrightarrow$ (se e solo se), $\land$ (e), $\lor$ (oppure)
simboli per quantificatori: $\forall$ (quantificatore universale), $\exists$ (quantificatore esistenziale)

Un esempio è l'alfabeto dell' aritmetica di Peano 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.

[modifica] Termini

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

una costante individuale è un termine
una variabile è un termine
se $t 1,..., t n$ sono n termini e $f$ è un simbolo per funzione n-aria allora $f (t 1,..., 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)

[modifica] Formule ben formate

Per approfondire, vedi la voce Formula ben formata.

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

$A (t 1,..., t n)$

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

1. ogni formula atomica è una fbf
2. se $\mathcal A$ e $\mathcal B$ sono fbf allora lo sono anche

$\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$
$\exist x \mathcal A$

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

Esempi di formule ben formate nel linguaggio dell' aritmetica di Peano 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 di Peano S non è un simbolo per predicato bensì un simbolo per funzione.

[modifica] Sottoformule, variabili libere e formule chiuse

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

$\forall x (P(x) \land Q(y))$

le sottoformule sono

$\forall x (P(x) \land Q(y))$

$P(x) \land Q(y)$

$P(x)\,$

$Q(y)\,$

In una fbf i quantificatori compaiono necessariamente davanti a sottoformule e sono associati ad una variabile (quella che compare immediatamente dopo il simbolo $\forall$ o $\exist$ ).
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.

[modifica] 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;
un insieme di elementi di U da associare a ciascuna costante individuale del linguaggio;
per ogni n un insieme di funzioni da $U n$ in sé stesso da associare a ciascun simbolo di funzione n-aria del linguaggio;
per ogni n un insieme di relazioni n-aria su $U$ da associare a ciascun simbolo di relazione n-aria del linguaggio;

la collezione di questi insiemi individua quello che si chiama un modello per il linguaggio.

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

[modifica] Voci correlate

Estratto da "http://it.wikipedia.org../../../l/i/n/Linguaggio_del_primo_ordine.html"

Categorie: Stub matematica | Logica matematica

Linguaggio del primo ordine

Da Wikipedia, l'enciclopedia libera.

Indice

[modifica] Motivazione

[modifica] Definizione

[modifica] Alfabeto

[modifica] Termini

[modifica] Formule ben formate

[modifica] Sottoformule, variabili libere e formule chiuse

[modifica] Semantica

[modifica] Voci correlate

Views

Navigazione

comunità

Ricerca

Altre lingue