# Quantificatore

Nella logica i quantificatori sono espressioni, che con i rispettivi simboli, consentono di esprimere per quali valori è valido un predicato (cioè quantificano). Essi sono due:
* $\exists$ quantificatore esistenziale (si legge esiste almeno un).
* $\forall$ quantificatore universale (si legge per ogni).
A questi si aggiunge un caso particolare del quantificatore esistenziale, che è il quantificatore unico $\exists !$ (si legge: "esiste ed è unico", che equivale a "è uno e uno solo").

## Storia

Fin dalle origini la logica si è sempre occupata del meccanismo della quantificazione, e la mancanza di una sua analisi che fosse completa ne ha causato il ristagno per interi millenni, fino all'anno 1879 in cui il famoso matematico ottocentesco Frege lo espose come una funzione di livello superiore (cioè avente per argomento una funzione di livello inferiore). Frege fu il padre della logica formale e della logica matematica; e vinse la sfida di esprimere nel linguaggio formale parole come tutti e esiste (presenti in proposizioni come "Tutti gli uomini sono mortali" o "Esiste almeno un filosofo greco") che sembravano impossibili da esprimere.
Nonostante l'idea di quantificatore sia dunque da attribuire a Frege, furono Peano e Gentzen ad ideare i simboli ∃ (1897, Peano) e ∀ (1935, Gentzen), oggi senz'altro più usati del vecchio segno bidimensionale introdotto dall'inventore del XIX secolo per il quantificatore universale (da cui il quantificatore esistenziale si ottiene negandolo; ragion per cui anche oggi molti linguaggio formali sono costruiti usando un solo quantificatore e la negazione per esprimere l'altro) e mai più adoperato in seguito per l'evidente ingombranza.

## Relazioni con i connettivi logici

I quantificatori universale ed esistenziale opportunamente combinati con il connettivo logico di negazione possono svolgere l'uno la funzione dell'altro. L'affermazione "è falso che ogni numero è pari" si può anche esprimere dicendo che "esiste un numero che non è pari". Nel linguaggio formale questo si può tradurre dicendo che
    $\neg (\forall xP(x))$
è equivalente a
    $\exists x\neg P(x)$
e questo vale per qualunque scelta di $P$.
Analogamente l'affermazione "non esiste un numero pari" è equivalente all'affermazione "ogni numero non è pari", formalmente possiamo dire che
    $\neg (\exists xP(x))$
è equivalente a
    $\forall x\neg P(x)$.

## Esistenza e unicità

In matematica si usa l'espressione simbolica
    $\exists !x...$
per abbreviare l'espressione "esiste un unico x...".
Formalmente l'espressione $\exists !xP(x)$ si può esprimere (per non dover inserire una nuova notazione tra i simboli della sintassi del linguaggio) facendo ricorso soltanto ai connettivi standard, ai quantificatori e alla relazione di uguaglianza nel seguente modo:
    $\exists x(P(x)\land \forall y(P(y)\to (y=x)))$.
Si può anche esprimere più brevemente facendo ricorso ad un connettivo bicondizionale (presente tra i cinque connettivi standard):
    $\exists x\,\forall y\,(P(y)\leftrightarrow x=y).$

## Quantificatori annidati

Combinando quantificatori di tipo diverso si possono ottenere frasi di complessità sempre maggiore per cui occorre molta cautela. Un'espressione del tipo
    $\forall x\exists yP(x,y)$
non è equivalente a
    $\exists y\forall xP(x,y)$
per rendersene conto basta pensare a frasi come
    "per ogni numero x esiste un numero y più grande di x"
e
    "esiste un numero y che è più grande di ogni numero x"
la prima afferma che per ogni numero se ne può sempre trovare uno più grande, la seconda afferma che esiste un numero più grande di qualsiasi altro.

## Formula ben formata

Se $\alpha$ è una formula e $x$ una variabile individuale (nome proprio di cosa o di persona), allora in logica vale che:
    se $\alpha$ è ben formata $\rightarrow \exists x\alpha$ è ben formata.
    se $\alpha$ è ben formata $\rightarrow \forall x\alpha$ è ben formata.
Lo stesso vale per tutti i connettivi logici rispetto a due formule $\alpha$ e $\beta$ ben formate:
    se $\alpha$ e $\beta$ è ben formata, allora $\alpha \land \beta$ è ben formata;
    se $\alpha$ e $\beta$ è ben formata, allora $\alpha \lor \beta$ è ben formata;
    se $\alpha$ e $\beta$ è ben formata, allora $\alpha \rightarrow \beta$ è ben formata.

## Quantificazione vacua

Una variabile si dice libera se almeno una delle sue occorrenze in una formula è senza quantificatori. Si dice vincolata (ad un quantificatore) se ogni volta che la troviamo nella formula, compare col quantificatore esistenziale o universale. Esempio:
    $y(M(y,x))$, $x$ è una variabile libera, $y$ è vincolata.
Una formula ben formata si dice aperta se contiene almeno una occorrenza di una variabile non vincolata. Se (tutte le occorrenze di) tutte le variabili hanno un quantificatore, la fbf si dice chiusa.
La quantificazione si dice vacua (o muta o che "opera a vuoto") se la variabile nella formula, non occorre o non occorre libera. Es.:
    $\forall y(M(y,x))$ (1)
equivale a
    $\forall z\exists y(\forall y(M(y,x))$
dove $z$ non ha occorrenze in (1) e (le occorrenze di) $y$ erano già vincolate dal quantificatore.