quantificatore

quantificatore

quantificatore in logica, termine che indica il corrispettivo formale di locuzioni quali «per ogni», «esiste», «esiste un» ecc. L’introduzione di quantificatori in una scrittura formale contenente variabili permette di trasformarla in un enunciato e assegnare così a essa un valore di verità. I quantificatori sono, quindi, assenti nel linguaggio degli enunciati, che non contiene scritture con variabili, mentre sono introdotti nel linguaggio dei predicati. La presenza dei quantificatori in tale linguaggio è strettamente legata proprio 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 «esiste y tale che y è il doppio di 5»).

Esistono due tipi di quantificatori fondamentali:

• quantificatore universale, rappresentato dal simbolo ∀ (si legge «per ogni»): indica che il predicato che lo segue è verificato per ogni valore della variabile di riferimento. Per esempio, la formula ∀x, x ≥ 0 (che può essere anche scritta come ∀x(x ≥ 0)) assume il seguente significato: «per ogni valore della variabile x (appartenente a un opportuno insieme di definizione) x è maggiore o uguale a 0». Si noti che la verità di una formula contenente un quantificatore dipende dall’insieme a cui appartiene la variabile x. Nell’esempio precedente, infatti, la formula ∀x, x ≥ 0 è vera se x varia nell’insieme dei numeri naturali, mentre è falsa se x varia nell’insieme dei numeri interi;

• quantificatore esistenziale, rappresentato dal simbolo ∃ (si legge «esiste»): indica che il predicato che lo segue è verificato per almeno un valore della variabile di riferimento. Per esempio la formula ∃x, 2 + x = 0 (che può anche essere scritta come ∃x(2 + x = 0)) significa: «esiste un valore della variabile x tale che x + 2 = 0»; tale valore in effetti esiste nell’insieme dei numeri interi ed è x = −2.

La quantificazione universale afferma che un predicato P deve essere soddisfatto da ogni elemento x appartenente a un certo insieme; perciò essa indica una → congiunzione generalizzata a ogni elemento dell’insieme. In altri termini: l’affermazione «ogni elemento dell’insieme {5, 7, 11, 13} è un numero primo» tradotta simbolicamente in ∀xP(x) (dove il simbolo P(x) corrisponde al predicato «x è un numero primo») è equivalente alla congiunzione generalizzata P(5) ∧ P(7) ∧ P(11) ∧ P(13). Un quantificatore esistenziale indica invece una → disgiunzione generalizzata. Per esempio la frase «c’è almeno un numero maggiore di 10» riferita all’insieme precedente {5, 7, 11, 13} può essere tradotta con la formula ∃y, y > 10 che corrisponde alla disgiunzione generalizzata

Si osservi che, per una migliore lettura delle formule con quantificatori, a volte si separa la quantificazione dal predicato a cui si riferisce con una virgola; altre volte, quando la quantificazione si riferisce a una scrittura predicativa più articolata, si racchiude quest’ultima in parentesi. Le proprietà dei due quantificatori possono quindi essere ricavate dalle proprietà dei connettivi congiunzione e disgiunzione. È possibile, come per i connettivi, cambiare l’ordine di più quantificatori dello stesso tipo, senza cambiare l’asserzione complessiva. Non è possibile però cambiare l’ordine di quantificatori di tipo diverso, a meno di non modificare il significato della frase. Per esempio la frase «c’è un abito adatto per ogni stagione» è diversa dalla frase «per ogni stagione c’è un abito adatto». Indicando con A(x, y) il predicato «l’abito x è adatto alla stagione y», le due frasi possono essere espresse rispettivamente dalle formule: ∃x ∀yA(x, y) e ∀y ∃xA(x, y) le quali differiscono per l’ordine dei due quantificatori.

Le proprietà della negazione relativamente alla congiunzione e alla disgiunzione portano a stabilire equivalenze logiche che coinvolgono i quantificatori (→ De Morgan, leggi di). La negazione di una espressione che contiene un predicato preceduto da un certo numero di quantificatori si ottiene sostituendo ogni quantificatore esistenziale con un quantificatore universale e viceversa e sostituendo il predicato con la sua negazione. Si consideri a tal proposito la negazione di ∀xP(x) (cioè ￢∀xP(x)); essa è logicamente equivalente a ∃x ￢P(x): per esempio, affermare «non è vero che a marzo è piovuto ogni giorno» equivale a dire che «c’è stato un giorno di marzo in cui non è piovuto». Si ottengono quindi le seguenti equivalenze logiche:

• ￢∀xP(x) equivale a ∃x￢P(x)

• ￢∃xP(x) equivale a ∀x￢P(x)

• ∀xP(x) equivale a ￢∃x￢P(x)

• ∃xP(x) equivale a ￢∀x￢P(x)

Una variabile che compare subito dopo un quantificatore è detta indice del quantificatore (in ∀x la variabile x è l’indice del quantificatore) mentre il predicato a cui si riferisce il quantificatore è detto campo d’azione del quantificatore; per esempio in ∃x(P(x) ⇒ Q(y)) ∨ R(x), il predicato P(x) ⇒ Q(y) è il campo d’azione del quantificatore esistenziale, racchiuso tra parentesi, mentre R(x) non ne fa parte. Si dice che una variabile x ha una occorrenza vincolata o legata in una formula se x è l’indice di un quantificatore oppure se x è nel campo d’azione di un quantificatore. Un’occorrenza non vincolata da quantificatori si dice occorrenza libera; una variabile è libera se ha almeno un’occorrenza libera: nella formula (∀x∃y A(x, y)) ⇒B(x), la variabile x è libera, perché ha un’occorrenza libera nella formula B(x), mentre la variabile y è vincolata.

A partire dai due quantificatori fondamentali, se ne costruiscono a volte altri, utili per la semplificazione delle scritture formali. Tra questi, il particolare quantificatore modificato «esiste un solo x» che indica l’esistenza e l’unicità di un elemento che soddisfa un predicato ed è indicato con ∃! (o in alcuni testi con ∃′). La scrittura ∃!xP(x) è logicamente equivalente a ∃xP(x) ∧ ∀y(y ≠ x ⇒ ￢P(y)). L’introduzione del quantificatore ∃! si riduce, quindi, a una mera semplificazione di scrittura, a partire dai due quantificatori fondamentali.

Si deve a G. Frege l’intuizione che i quantificatori possano essere pensati come denotanti concetti di concetti. Si consideri per esempio l’enunciato «qualcosa si muove»: lo si può parafrasare dicendo che il concetto denotato da «si muove» ha estensione non vuota. Risulta perciò naturale pensare il quantificatore esistenziale (∃) come denotante il concetto di secondo livello sotto cui cadono tutti e solo quei concetti di primo livello la cui estensione è non vuota. Considerazioni analoghe rendono plausibile pensare il quantificatore universale (∀) come denotante il concetto di secondo livello sotto cui cadono tutti e solo quei concetti di primo livello la cui estensione contiene tutti gli oggetti. L’analisi di Frege dei quantificatori è oggi spesso espressa dicendo che i quantificatori esistenziale e universale denotano insiemi di insiemi. Per riferirsi a espressioni qualsiasi, eventualmente diverse da “qualcosa” e “ogni cosa”, che possono essere pensate come denotanti insiemi di insiemi, si parla di quantificatori generalizzati. In ambito logico-matematico lo studio dei quantificatori generalizzati fu avviato negli anni Cinquanta del xx secolo dal matematico polacco A. Mostowski, mentre più di recente, soprattutto per merito del matematico e logico statunitense K.J. Barwise e del linguista computazionale Robin Cooper (1947), è stata riconosciuta l’importanza della nozione di quantificatore generalizzato per la semantica del linguaggio naturale.