predicati, linguaggio dei

Enciclopedia della Matematica (2013)

predicati, linguaggio dei linguaggio formale in cui è possibile rappresentare simbolicamente frasi espresse nel linguaggio naturale aventi una struttura più elaborata degli → enunciati. Il linguaggio degli enunciati, infatti, risulta in molti casi inadatto a esprimere la complessità del linguaggio naturale. Per esempio un ragionamento quale «ogni multiplo di 4 è un numero pari; poiché 8 è multiplo di 4, allora 8 è pari», pur essendo corretto, non può essere tradotto nel linguaggio degli enunciati. Ciò è dovuto, innanzitutto, al fatto che un enunciato non contiene variabili. Inoltre un enunciato elementare è un “atomo” di cui non interessa la struttura interna, cioè le singole parole che lo compongono, e proprio per questo è indicato simbolicamente con una lettera (detta lettera enunciativa). Il linguaggio dei predicati si basa invece non solo sulle connessioni fra le diverse forme predicative (dette comunemente predicati), ma anche sui legami tra le parti che le compongono: i predicati quindi non sono atomi, ma oggetti più complessi da scomporre per analizzarne le relazioni interne. Ciò avviene mediante l’uso non solo di connettivi, ma anche di quantificatori e di simboli che rappresentano funzioni, relazioni e proprietà.

Connettivi

I connettivi del linguaggio dei predicati sono gli stessi utilizzati dal linguaggio degli enunciati: negazione, congiunzione, disgiunzione, implicazione, doppia implicazione.

Quantificatori

I quantificatori sono una peculiarità del linguaggio dei predicati. Un quantificatore è una espressione che si riferisce a una variabile di un predicato e indica in quale modo possa essere estesa la validità del predicato stesso. Esistono due tipi di quantificatori: il quantificatore universale, simbolicamente indicato con ∀ (si legge «per ogni»), che, applicato a x, variabile in un insieme X, indica una congiunzione generalizzata estesa a tutti gli elementi di X; il quantificatore esistenziale, simbolicamente indicato con ∃ (si legge «esiste»), che applicato a x, variabile in un insieme X, indica una disgiunzione generalizzata estesa a tutti gli elementi di X (→ quantificatore). La presenza dei quantificatori nel linguaggio dei predicati è strettamente legata all’utilizzo delle variabili. Infatti non è possibile assegnare un valore di verità a una espressione contenente variabili; non è possibile dire se frasi come «x va a scuola» o «il numero y è il doppio di 5» siano vere o false. Per assegnare loro un valore di verità si può ricorrere a due modalità:

• sostituire delle costanti alle variabili (per esempio, «Carlo va a scuola» dove il nome Carlo è stato sostituito al posto della variabile x nella frase precedente);

• quantificare le variabili, cioè fare un’asserzione su quanti elementi, sostituiti alle variabili, trasformano l’espressione in una formula vera (per esempio, «∃y tale che y è il doppio di 5»).

Per esemplificare il ruolo dei quantificatori nel linguaggio dei predicati si consideri la frase «per ogni numero x esiste un numero y tale che (x + y = 0)». Essa può essere formalizzata dall’espressione «∀x∃y(x + y = 0)»; questa formula è vera se le variabili x e y rappresentano numeri interi, è falsa se rappresentano numeri naturali. La verità di una formula dipende perciò anche dall’insieme a cui appartengono le variabili (dominio di interpretazione). Nel linguaggio dei predicati è possibile applicare i quantificatori solo alle variabili: non si possono quindi applicare i quantificatori né alle costanti né ai simboli funzionali né ai simboli predicativi. Ciò esclude dal linguaggio dei predicati espressioni come «per ogni proprietà P esiste un numero x che la soddisfa» nella quale il quantificatore universale è applicato all’insieme delle proprietà. Per questa caratteristica, il linguaggio dei predicati è un linguaggio del primo ordine (→ primo ordine, teoria del).

Lettere funzionali

Oltre a connettivi e quantificatori, il linguaggio dei predicati contiene simboli per rappresentare le funzioni, le relazioni e le proprietà. Le funzioni sono rappresentate dalle cosiddette lettere funzionali (o simboli funzionali). Una lettera funzionale ƒ si applica a variabili o a costanti dando origine a espressioni come ƒ(x) o ƒ(a) (dove a è una costante); lettere funzionali possono anche rappresentare funzioni con più argomenti dando luogo a formule del tipo ƒ(x, y) o g(a, x). Per esempio è possibile rappresentare il successore di un numero naturale con la lettera funzionale s, in questo modo il simbolo s(x) rappresenta il numero successivo a x, quindi s(5) è 6; per rappresentare invece la moltiplicazione di un numero x per un numero y, si può usare una lettera funzionale, per esempio m, applicata a due argomenti e m(x, y) indica x ⋅ y.

Lettere predicative

Relazioni e proprietà sono rappresentate da lettere predicative seguite, in parentesi, dagli argomenti a cui si riferiscono (così costituendo i simboli predicativi). Nel linguaggio naturale relazioni e proprietà hanno una espressione verbale, da cui l’aggettivo predicativo che si dà alle lettere che le rappresentano, che esprime una proprietà di uno o più oggetti; tra queste la proprietà dell’essere posti in relazione. Così, per esempio la proprietà di «avere i capelli rossi» riferibile a un individuo può essere espressa dalla lettera predicativa R e la scrittura R(a) corrisponde alla frase «a ha i capelli rossi»; la relazione «essere minore di» riferibile a due numeri naturali, può essere rappresentata con la lettera L e la scrittura L(x, y) corrisponde alla frase «x è minore di y». Proprietà e relazioni sono dette appunto predicati e gli oggetti a cui si riferiscono sono detti argomenti del predicato. Si osservi che il termine «predicato» è utilizzato spesso sia per indicare la proprietà espressa dalla lettera predicativa, sia le forme predicative costruite a partire da variabili, costanti, connettivi, quantificatori, lettere funzionali, lettere predicative.

Per esemplificare, la frase «ogni multiplo di 4 è un numero pari» può essere espressa come forma predicativa utilizzando: la variabile x per indicare un qualsiasi multiplo di 4; il simbolo di quantificazione ∀ applicato alla variabile x; il simbolo predicativo M(x, 4) per esprimere la relazione «x è un multiplo di 4»; il simbolo predicativo P(x) per indicare la proprietà «x è pari»; il connettivo dell’implicazione ⇒. In questo modo la frase è tradotta simbolicamente dalla formula ∀x(M(x, 4) ⇒ P(x)) (letteralmente, «per ogni x, se x è un multiplo di 4 allora x è un numero pari»). Si noti l’uso della parentesi tonda la quale sta a significare che il quantificatore universale si riferisce a tutta la formula M(x, 4) ⇒ P(x) e non solo all’antecedente M(x, 4). Una volta che le frasi del linguaggio naturale sono state tradotte in espressioni simboliche del linguaggio del predicati, è possibile esprimere, in questo sistema formale, un intero ragionamento in modo da poterlo rendere schematico e valutarne la correttezza.

Alfabeto, termini e formule ben formate

Il linguaggio dei predicati costituisce l’apparato linguistico del calcolo dei → predicati, sistema formale che, traducendo una argomentazione logica in un procedimento deduttivo formalizzato, permette di studiare il processo di ragionamento in maniera controllata.

In termini formali, riassumendo anche quanto detto in precedenza, tale linguaggio è formato, come ogni linguaggio formale da alfabeto, termini e formule ben formate.

L’alfabeto rappresenta l’insieme dei simboli del linguaggio ed è costituito da:

• variabili individuali: x₁, x₂, …; le variabili (come anche le costanti e i simboli di funzione e di relazione) sono un’infinità numerabile;

• costanti individuali: a₁, a₂, …;

• lettere funzionali: ƒ₁¹, ƒ₂¹, ..., ƒ₁², ƒ₂², ..., ƒ₁ⁿ, ƒ₂ⁿ, ... dove l’apice indica il numero di argomenti di una funzione; per esempio la funzione ƒ₅³ è la quinta funzione a tre argomenti;

• lettere predicative: A₁¹, A₂¹, ..., A₁², A₂², ..., A₁ⁿ, A₂ⁿ, ..., dove l’apice indica il numero di argomenti di un predicato;

• simboli logici (connettivi e quantificatori): ¬, ∧, ∨, ⇒, ⇔, ∀, ∃;

• simboli ausiliari: ( , ).

I termini sono i costituenti fondamentali delle formule del linguaggio e sono tutti e soli quelli formati secondo le regole seguenti:

• le variabili e le costanti sono termini;

• se t è un termine e ƒ è un simbolo di funzione allora ƒ(t ) è un termine. Più in generale se t₁, t₂, …, t_n sono n termini e ƒ_iⁿ rappresenta una funzione di n argomenti allora ƒ_iⁿ(t₁, t₂, …, t_n) è un termine.

Un termine si dice chiuso se non contiene variabili. Infine, le formule ben formate, cioè le formule predicative vere e proprie, sono tutte e sole quelle formate secondo le seguenti regole:

• se A_iⁿ è una lettera predicativa e t₁, t₂, … t_n sono termini, allora A_iⁿ(t₁, t₂, …, t_n) è una formula atomica;

• le formule atomiche sono formule ben formate;

• se α e β sono formule ben formate, allora anche ¬α, α ∧ β, α ∨ β, α ⇒ β, α ⇔ β, ∀x α, ∃x α sono formule ben formate.

Nella costruzione delle formule ben formate è possibile ridurre il numero dei connettivi e dei quantificatori, secondo le equivalenze logiche che legano rispettivamente gli uni e gli altri.

Interpretazione

A ogni formula chiusa del linguaggio dei predicati può essere attribuito un valore di verità; per stabilire tale valore occorre, come si è visto negli esempi precedenti, scegliere una interpretazione degli oggetti del linguaggio (variabili, costanti, …). Formalmente, una interpretazione consiste in un insieme D (detto dominio di interpretazione) e in una funzione g che associa:

• a ogni costante individuale a del linguaggio, un elemento del dominio D;

• a ogni lettera funzionale ƒ_iⁿ, una funzione di dominio Dⁿ e codominio D;

• a ogni lettera predicativa A_jⁿ una relazione a n posti nell’insieme D (cioè un sottoinsieme del prodotto cartesiano Dⁿ).

A titolo di esempio viene riportata una interpretazione del linguaggio dei predicati nell’insieme dei numeri naturali. Per semplicità si considera una sola costante a, un solo simbolo di funzione ƒ a un argomento e un solo simbolo di relazione ρ a due argomenti. Si assume come dominio di interpretazione l’insieme N dei numeri naturali. La funzione g è così definita:

• g(a) = 0 cioè la funzione associa all’unica costante il numero 0;

• g associa all’unico simbolo di funzione ƒ, la funzione successore di dominio N e codominio N (ƒ(0) = 1, ƒ(1) = 2, ƒ(2) = 3…);

• g associa all’unico simbolo di relazione ρ, la relazione «essere maggiore di» definita in N × N.

In questo modo la formula ben formata ∀x ρ(ƒ(x), a) ha la seguente interpretazione: «dato un qualsiasi numero naturale x, il successore di x è maggiore di 0». In generale, ogni formula ben formata del calcolo dei predicati può essere interpretata in un dominio D attribuendo alle variabili della formula in questione i valori di D. Una formula ben formata A del calcolo dei predicati si dice formula valida se è soddisfatta in tutte le interpretazioni, in tal caso si scrive ⊨ A. L’apparato deduttivo del linguaggio dei predicati ha lo scopo di dedurre, da un insieme ristretto di formule (gli assiomi), tutte le formule valide del linguaggio dei predicati mediante le regole di inferenza (→ predicati, calcolo dei).