\chapter{Quantificatori universale ed esistenziale}\label{cap:LD-003}

\citazioneinizio{%
  La logica matematica differisce dalle altre logiche solo per il fatto di usare i simboli.%
}{Giuseppe Peano, \emph{Formulario Mathematico} (1908)}

% ============================================================
\section{Introduzione motivazionale}\label{sec:ld-003-01-introduzione-motivazionale}
% ============================================================

Nel capitolo precedente abbiamo introdotto i connettivi $\lnot$, $\land$, $\lor$, $\Rightarrow$, $\Leftrightarrow$, che permettono di combinare \emph{proposizioni intere}. Ma molte affermazioni matematiche hanno una struttura più fine: non riguardano un singolo oggetto, riguardano \emph{tutti} gli oggetti di un insieme oppure \emph{almeno uno}.

``Il quadrato di ogni numero reale è non negativo'' è un'affermazione di tipo nuovo: parla simultaneamente di infiniti oggetti. ``Esiste un numero naturale maggiore di un milione'' è anch'essa diversa da una semplice proposizione: dichiara solo che almeno uno c'è. Questi due modi di parlare — l'``ogni'' e l'``esiste'' — sono i \emph{quantificatori}.

Senza quantificatori la matematica resterebbe muta su quasi tutto ciò che le interessa: i teoremi, le definizioni, le proprietà strutturali. In questo capitolo introduciamo i due simboli $\forall$ (``per ogni'') ed $\exists$ (``esiste''), impariamo a leggerli e a scriverli, e soprattutto impariamo a \emph{negarli} correttamente — operazione tutt'altro che ovvia, e fonte di molti errori per chi inizia.

% ============================================================
\section{Predicati e quantificatore universale $\forall$}\label{sec:ld-003-01-quantificatore-universale-forall}
% ============================================================

\begin{definizione}[Predicato]
Un \textbf{predicato} (o \emph{formula aperta}) è una frase contenente una o più variabili, che diventa una proposizione (vera o falsa) non appena le variabili vengano sostituite con valori concreti tratti da un insieme di riferimento, detto \emph{dominio}.
\end{definizione}

Indichiamo i predicati con $P(x)$, $Q(x,y)$, $\ldots$, mettendo tra parentesi le variabili libere. La frase
\[
  P(x): \quad ``x>0'' \qquad \text{(con $x\in\R$)}
\]
non è in sé vera o falsa: $P(3)$ è vera, $P(-1)$ è falsa, $P(\sqrt{2})$ è vera. È solo quando $x$ riceve un valore — o quando viene ``quantificata'' — che si ottiene una proposizione.

Il primo modo di trasformare un predicato in proposizione è dire che il predicato vale per \emph{tutti} gli elementi del dominio.

\begin{definizione}[Quantificatore universale]
Dato un predicato $P(x)$ sul dominio $D$, la proposizione
\[
  \forall x\in D : P(x)
\]
si legge ``per ogni $x$ in $D$, vale $P(x)$'' ed è \emph{vera} quando $P(x)$ è vera per ciascun elemento $x$ del dominio, \emph{falsa} quando esiste almeno un elemento del dominio per cui $P(x)$ è falsa.
\end{definizione}

Il simbolo $\forall$ è una A capovolta (\emph{all}, ``tutti'') e si scrive \emph{a sinistra} della variabile cui si riferisce. Se il dominio è chiaro dal contesto si scrive semplicemente $\forall x: P(x)$.

\begin{esempio}[Vero o falso?]
Stabilire il valore di verità delle seguenti proposizioni.
\begin{itemize}
  \item $\forall x\in\R:\ x^2\ge 0$ — \textbf{vera}: il quadrato di ogni numero reale è non negativo.
  \item $\forall n\in\N:\ n+1>n$ — \textbf{vera}.
  \item $\forall x\in\R:\ x>0$ — \textbf{falsa}: $x=-1$ è un controesempio.
  \item $\forall n\in\N:\ n^2-n\ge 0$ — \textbf{vera}: per $n=0$ vale $0$; per $n\ge 1$, $n^2-n=n(n-1)\ge 0$.
\end{itemize}
\end{esempio}

\begin{nota}[Quantificatore universale e congiunzione]
Se il dominio è \emph{finito}, $D=\{a_1,a_2,\ldots,a_n\}$, allora
\[
  \forall x\in D: P(x) \quad\equiv\quad P(a_1)\land P(a_2)\land\cdots\land P(a_n).
\]
Il quantificatore universale è dunque una specie di ``congiunzione su tutti gli elementi'' del dominio. Se $D$ è infinito, la congiunzione diventa infinita e $\forall$ è l'unico modo di esprimerla in modo finito.
\end{nota}

\begin{attenzione}[Per smentire un ``$\forall$'']
Per dimostrare che $\forall x\in D: P(x)$ è \emph{falsa} basta un singolo elemento $x_0\in D$ per cui $P(x_0)$ è falsa: si chiama \emph{controesempio}. Trovare un controesempio è sufficiente. Verificare la proposizione su molti casi favorevoli, invece, non è mai sufficiente: il fatto che $P(x)$ valga per i primi cento valori non garantisce nulla sul centunesimo.
\end{attenzione}

\begin{figure}[H]
\centering
\begin{tikzpicture}
  % Quantificatore universale: tutti i punti di A soddisfano P (tutti dello stesso colore)
  \draw[thick, BLU, fill=BLU!8] (0,0) ellipse (2.6cm and 1.5cm);
  \node[BLU] at (-2.2, 1.2) {$D$};
  \foreach \x/\y in {-1.6/0.3, -0.9/-0.4, -0.3/0.5, 0.4/-0.5, 1.1/0.4, 1.7/-0.2, -1.4/-0.6, 0.0/0.0} {
    \fill[VERDE] (\x,\y) circle (3pt);
  }
  \node[BLU] at (0,-2.0) {$\forall x\in D:\ P(x)$\ \ tutti gli elementi soddisfano $P$};
\end{tikzpicture}
\caption{Il quantificatore universale $\forall x\in D: P(x)$ è vero quando \emph{ogni} elemento di $D$ soddisfa il predicato $P$: nella figura, tutti i punti sono ``verdi'' (soddisfano $P$).}
\label{fig:ld-003-universale}
\end{figure}

% ============================================================
\section{Quantificatore esistenziale $\exists$}\label{sec:ld-003-02-quantificatore-esistenziale-exists}
% ============================================================

Il secondo modo di trasformare un predicato in proposizione è dire che il predicato vale per \emph{almeno un} elemento del dominio.

\begin{definizione}[Quantificatore esistenziale]
Dato un predicato $P(x)$ sul dominio $D$, la proposizione
\[
  \exists x\in D : P(x)
\]
si legge ``esiste $x$ in $D$ tale che $P(x)$'' ed è \emph{vera} quando almeno un elemento del dominio soddisfa $P(x)$, \emph{falsa} se nessun elemento del dominio lo soddisfa.
\end{definizione}

Il simbolo $\exists$ è una E rovesciata (\emph{exists}). ``Esiste'' va inteso in senso debole: significa ``ce n'è almeno uno'', non ``ce n'è esattamente uno''.

\begin{esempio}
\begin{itemize}
  \item $\exists n\in\N:\ n>10^6$ — \textbf{vera} (ad esempio $n=10^6+1$).
  \item $\exists x\in\R:\ x^2=-1$ — \textbf{falsa}: nessun reale ha quadrato negativo.
  \item $\exists x\in\R:\ x^2=2$ — \textbf{vera} ($x=\sqrt{2}$, ma anche $x=-\sqrt{2}$).
  \item $\exists p\in\N:\ p$ è primo e $p>100$ — \textbf{vera} (ad esempio $p=101$).
\end{itemize}
\end{esempio}

\begin{nota}[Quantificatore esistenziale e disgiunzione]
Se il dominio è finito, $D=\{a_1,a_2,\ldots,a_n\}$, allora
\[
  \exists x\in D: P(x) \quad\equiv\quad P(a_1)\lor P(a_2)\lor\cdots\lor P(a_n).
\]
L'esistenziale è dunque una ``disgiunzione su tutti gli elementi''. Anche qui, se $D$ è infinito, $\exists$ è l'unico modo finito di esprimerla.
\end{nota}

\begin{definizione}[Esistenza unica]
Si introduce talvolta il simbolo $\exists!$ per esprimere \emph{esistenza e unicità}:
\[
  \exists!\, x\in D : P(x)
\]
significa ``esiste un \emph{unico} $x\in D$ tale che $P(x)$''. Equivale alla congiunzione di due fatti:
\[
  \exists x\in D : P(x) \quad\text{(esistenza)} \qquad \land \qquad \forall x,y\in D :\ (P(x)\land P(y)\Rightarrow x=y) \quad\text{(unicità).}
\]
\end{definizione}

\begin{esempio}
$\exists!\, x\in\R:\ 3x-7=2$: esiste un unico reale tale che $3x-7=2$, ed è $x=3$. L'esistenza si prova esibendolo; l'unicità deriva dall'unicità della soluzione di un'equazione lineare a coefficiente non nullo.
\end{esempio}

\begin{attenzione}[Per smentire un ``$\exists$'']
Per dimostrare che $\exists x\in D: P(x)$ è \emph{falsa} bisogna escludere \emph{ogni} elemento del dominio: equivalentemente, bisogna provare che $\forall x\in D: \lnot P(x)$. Per provarla \emph{vera}, invece, basta esibirne un esempio.
\end{attenzione}

\begin{figure}[H]
\centering
\begin{tikzpicture}
  % Quantificatore esistenziale: almeno un punto verde, gli altri grigi
  \draw[thick, BLU, fill=BLU!8] (0,0) ellipse (2.6cm and 1.5cm);
  \node[BLU] at (-2.2, 1.2) {$D$};
  \foreach \x/\y in {-1.6/0.3, -0.9/-0.4, -0.3/0.5, 1.1/0.4, 1.7/-0.2, -1.4/-0.6} {
    \fill[GRIGIO] (\x,\y) circle (3pt);
  }
  \fill[VERDE] (0.4,-0.5) circle (3.5pt);
  \draw[VERDE, thick, ->] (0.4,-1.05) -- (0.4,-0.7);
  \node[VERDE] at (0.4,-1.25) {\small $x_0$};
  \node[BLU] at (0,-2.0) {$\exists x\in D:\ P(x)$\ \ almeno un elemento soddisfa $P$};
\end{tikzpicture}
\caption{Il quantificatore esistenziale $\exists x\in D: P(x)$ è vero quando \emph{almeno un} elemento $x_0\in D$ soddisfa il predicato $P$: nella figura un solo punto è ``verde'', e ciò basta.}
\label{fig:ld-003-esistenziale}
\end{figure}

% ============================================================
\section{Negazione di proposizioni con quantificatori}\label{sec:ld-003-03-negazione-di-proposizioni-con-quantificatori}
% ============================================================

Negare un'affermazione con quantificatori è una delle operazioni più delicate per chi inizia a fare matematica. La regola, però, è semplice e ricorda da vicino le leggi di De Morgan viste nel capitolo precedente: \emph{negando si scambia $\forall$ con $\exists$ e si nega il predicato}.

\begin{teorema}[Leggi di De Morgan per i quantificatori]
Per ogni predicato $P(x)$ sul dominio $D$:
\[
  \lnot\bigl(\forall x\in D : P(x)\bigr) \;\equiv\; \exists x\in D : \lnot P(x),
\]
\[
  \lnot\bigl(\exists x\in D : P(x)\bigr) \;\equiv\; \forall x\in D : \lnot P(x).
\]
\end{teorema}

\textit{Dimostrazione (idea).} Dire ``non è vero che $P(x)$ vale per ogni $x$'' significa dire ``c'è almeno un $x$ per cui $P(x)$ non vale'': è la prima legge. Specularmente, dire ``non è vero che esiste un $x$ con $P(x)$'' significa dire ``per ogni $x$, $P(x)$ è falso'': è la seconda. Su dominio finito, la verifica è una applicazione iterata delle leggi di De Morgan per $\land$ e $\lor$ già dimostrate.

\begin{formulabox}
\[
  \lnot(\forall x : P(x)) \equiv \exists x : \lnot P(x),\qquad
  \lnot(\exists x : P(x)) \equiv \forall x : \lnot P(x).
\]
\end{formulabox}

\begin{procedura}[Negare una proposizione quantificata]
Per negare un'affermazione che contiene quantificatori:
\begin{enumerate}
  \item si scambia ogni $\forall$ con $\exists$ e viceversa, mantenendo lo stesso dominio;
  \item si nega il predicato finale, applicando se serve le regole sui connettivi (in particolare $\lnot(p\Rightarrow q)\equiv p\land\lnot q$).
\end{enumerate}
\end{procedura}

\begin{esempio}[Negazione di una frase universale]
Negare: ``ogni numero primo è dispari''.

\textit{Soluzione.} Posto $P(p):$ ``$p$ è dispari'', la frase è $\forall p\in\mathbb{P}: P(p)$ (dove $\mathbb{P}$ è l'insieme dei primi). La sua negazione è $\exists p\in\mathbb{P}: \lnot P(p)$, ovvero ``esiste un primo che non è dispari'', cioè ``esiste un primo pari''. Un controesempio esiste: $p=2$. Quindi la frase di partenza è falsa.
\end{esempio}

\begin{esempio}[Negazione di una frase esistenziale]
Negare: ``esiste un numero reale uguale al proprio quadrato e diverso da $0$ e $1$''.

\textit{Soluzione.} Posto $P(x):$ ``$x^2=x \land x\neq 0 \land x\neq 1$'', la frase è $\exists x\in\R: P(x)$. La negazione è $\forall x\in\R: \lnot P(x)$, ovvero ``per ogni $x\in\R$, $x^2\neq x$ oppure $x=0$ oppure $x=1$''. (Equivalentemente: ``ogni reale che soddisfa $x^2=x$ è $0$ o $1$''.) Quest'ultima è vera: $x^2=x\Leftrightarrow x(x-1)=0\Leftrightarrow x=0\lor x=1$. Quindi la frase di partenza è falsa.
\end{esempio}

\begin{esempio}[Negazione di un'implicazione quantificata]
Negare: ``per ogni $n\in\N$, se $n$ è primo allora $n$ è dispari''.

\textit{Soluzione.} Posto $p(n):$ ``$n$ è primo'' e $q(n):$ ``$n$ è dispari'', la frase è $\forall n\in\N : (p(n)\Rightarrow q(n))$. Negandola:
\[
  \exists n\in\N : \lnot(p(n)\Rightarrow q(n)) \equiv \exists n\in\N : (p(n)\land\lnot q(n)),
\]
cioè: ``esiste un $n\in\N$ primo e non dispari'', ovvero ``esiste un primo pari''. È vera ($n=2$): quindi la frase di partenza è falsa, e $n=2$ è il controesempio.
\end{esempio}

% ============================================================
\section{Quantificatori multipli}\label{sec:ld-003-04-quantificatori-multipli}
% ============================================================

Molte definizioni della matematica usano \emph{più} quantificatori in cascata. Per esempio, ``per ogni numero reale esiste un naturale più grande di esso'' contiene un $\forall$ seguito da un $\exists$. La cosa importante da capire è che \emph{l'ordine dei quantificatori conta}.

\begin{definizione}[Quantificatori dello stesso tipo]
Quantificatori dello stesso tipo, in posizioni adiacenti, \emph{commutano}:
\[
  \forall x\,\forall y : P(x,y) \;\equiv\; \forall y\,\forall x : P(x,y),
  \qquad
  \exists x\,\exists y : P(x,y) \;\equiv\; \exists y\,\exists x : P(x,y).
\]
\end{definizione}

Si scrivono spesso in forma compatta: $\forall x,y : P(x,y)$ oppure $\exists x,y : P(x,y)$.

\begin{attenzione}[Quantificatori di tipo diverso non commutano]
$\forall x\,\exists y : P(x,y)$ e $\exists y\,\forall x : P(x,y)$ \textbf{non sono equivalenti}.
\begin{itemize}
  \item $\forall x\,\exists y : P(x,y)$ — ``per ogni $x$ esiste un $y$ (eventualmente \emph{dipendente da $x$}) tale che $P(x,y)$'';
  \item $\exists y\,\forall x : P(x,y)$ — ``esiste un $y$ \emph{unico e indipendente da $x$} tale che $P(x,y)$ valga per tutti gli $x$''.
\end{itemize}
La seconda è molto più forte: ne segue la prima, ma non viceversa.
\end{attenzione}

\begin{esempio}[Caso tipico]
Sia $P(x,y):$ ``$y>x$'', con $x,y\in\R$.
\begin{itemize}
  \item $\forall x\in\R\,\exists y\in\R : y>x$ — \textbf{vera}: per ogni $x$, basta scegliere $y=x+1$.
  \item $\exists y\in\R\,\forall x\in\R : y>x$ — \textbf{falsa}: nessun reale può essere maggiore di tutti i reali (in particolare, non può essere maggiore di sé stesso $+1$).
\end{itemize}
La differenza è nella dipendenza di $y$ da $x$.
\end{esempio}

\begin{nota}[Negare quantificatori in cascata]
La regola si applica passo per passo, da sinistra a destra:
\[
  \lnot\bigl(\forall x\,\exists y : P(x,y)\bigr) \equiv \exists x : \lnot\bigl(\exists y : P(x,y)\bigr) \equiv \exists x\,\forall y : \lnot P(x,y).
\]
Ogni quantificatore si rovescia, e il predicato finale si nega.
\end{nota}

\begin{esempio}[Negazione di una definizione tipica]
La definizione di ``$0$ è l'unico massimo di $-x^2$ su $\R$'' è del tipo $\forall x\in\R: -x^2\le 0$. La sua negazione sarebbe: $\exists x\in\R: -x^2>0$, cioè ``esiste un reale con quadrato negativo'', falsa.

Più in generale, la negazione di ``$M$ è un \emph{maggiorante} di $A$'', cioè $\forall x\in A: x\le M$, è $\exists x\in A: x>M$ (``c'è almeno un elemento di $A$ più grande di $M$''). È così che si nega ``maggiorante''.
\end{esempio}

\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=0.95]
  % Caso 1: per ogni x esiste un y > x (y dipende da x)
  \begin{scope}
    \draw[->, GRIGIO] (-0.3,0) -- (5,0) node[right] {$\R$};
    \foreach \x/\lbl in {0.5/x_1, 1.7/x_2, 3.1/x_3} {
      \fill[BLU] (\x,0) circle (2pt);
      \node[BLU, below] at (\x,-0.05) {\small$\lbl$};
    }
    \foreach \x/\y/\lbl in {0.5/1.0/y_1, 1.7/2.2/y_2, 3.1/3.6/y_3} {
      \fill[VERDE] (\y,0) circle (2pt);
      \node[VERDE, above] at (\y,0.05) {\small$\lbl$};
      \draw[->, VERDE, dashed] (\x,0.25) to[bend left=30] (\y,0.25);
    }
    \node at (2.3,-1.0) {\small$\forall x\,\exists y : y>x$ (V): a ogni $x$ corrisponde un proprio $y$};
  \end{scope}
  % Caso 2: esiste un y > x per ogni x (un solo y per tutti)
  \begin{scope}[shift={(0,-3.2)}]
    \draw[->, GRIGIO] (-0.3,0) -- (5,0) node[right] {$\R$};
    \foreach \x/\lbl in {0.5/x_1, 1.7/x_2, 3.1/x_3, 4.2/x_4} {
      \fill[BLU] (\x,0) circle (2pt);
      \node[BLU, below] at (\x,-0.05) {\small$\lbl$};
    }
    \fill[ROSSO] (3.5,0) circle (3pt);
    \node[ROSSO, above] at (3.5,0.1) {\small$y$ (unico)};
    \draw[->, ROSSO, dashed] (3.5,0.4) to[bend right=30] (4.2,0.4);
    \node at (2.3,-1.0) {\small$\exists y\,\forall x : y>x$ (F): un $y$ unico non può superare TUTTI gli $x$};
  \end{scope}
\end{tikzpicture}
\caption{La non commutatività di $\forall\exists$ e $\exists\forall$. Sopra: per ogni $x$ si sceglie un $y$ \emph{proprio} (ad esempio $y=x+1$). Sotto: un singolo $y$ fissato non può essere maggiore di ogni reale; il punto rosso non supera $x_4$.}
\label{fig:ld-003-non-commutativita}
\end{figure}

% ============================================================
\section{Esempi svolti}\label{sec:ld-003-06-esempi-svolti}
% ============================================================

\begin{esempio}[Tradurre dal linguaggio naturale]
Tradurre in simboli: ``ogni numero naturale maggiore di $1$ ha almeno un divisore primo''.

\textit{Soluzione.} Posto $D(p,n):$ ``$p$ divide $n$'', la frase è
\[
  \forall n\in\N,\ n>1\ :\ \exists p\in\N\ (p\ \text{primo}\ \land\ D(p,n)).
\]
Il quantificatore universale è ristretto agli $n>1$ (lo si può anche scrivere $\forall n\in\N: n>1 \Rightarrow \cdots$, equivalente). All'interno, l'esistenziale dichiara la presenza di un divisore primo.
\end{esempio}

\begin{esempio}[Negare una proposizione complessa]
Negare: ``per ogni $\varepsilon>0$ esiste un intero positivo $n$ tale che $\tfrac{1}{n}<\varepsilon$''.

\textit{Soluzione.} La proposizione, in simboli, è
\[
  \forall\varepsilon>0\ \exists n\in\N^*\ :\ \tfrac{1}{n}<\varepsilon.
\]
Applicando le regole di negazione due volte:
\[
  \exists\varepsilon>0\ \forall n\in\N^*\ :\ \tfrac{1}{n}\ge\varepsilon.
\]
Cioè: ``esiste un $\varepsilon>0$ tale che $\tfrac{1}{n}\ge\varepsilon$ per ogni intero positivo $n$''. (La proposizione originale è la cosiddetta ``proprietà archimedea'' di $\R$: è vera, dunque la sua negazione è falsa.)
\end{esempio}

\begin{esempio}[Dipendenza di $y$ da $x$]
Dire se le proposizioni
\[
  \varphi: \forall x\in\R\ \exists y\in\R\ :\ y^2=x \qquad
  \psi: \exists y\in\R\ \forall x\in\R\ :\ y^2=x
\]
sono vere.

\textit{Soluzione.} $\varphi$ chiede che ogni reale sia il quadrato di qualche reale: \textbf{falsa}, perché i reali negativi non lo sono. $\psi$ chiede che esista un $y$ tale che $y^2=x$ \emph{per ogni} $x\in\R$: \textbf{falsa}, perché un $y$ fissato dà un unico valore $y^2$ e non può essere uguale a tutti i reali contemporaneamente. Le due sono diverse anche se entrambe false.

Se restringiamo il dominio a $\R_{\ge 0}$, la prima diventa vera: $\forall x\ge 0\ \exists y\ge 0 : y^2=x$ (basta $y=\sqrt{x}$). La seconda resta falsa.
\end{esempio}

\begin{esempio}[Controesempio in un \emph{universale}]
Stabilire se è vera: ``per ogni $n\in\N$, $n^2+n+41$ è primo''.

\textit{Soluzione.} La proprietà vale per $n=0,1,\ldots,39$ (è la classica ``formula di Eulero''): $0+0+41=41$ è primo, $1+1+41=43$ è primo, e così via. Si è tentati di crederla vera. Però per $n=40$:
\[
  40^2+40+41 = 1600+40+41 = 1681 = 41^2,
\]
che non è primo. Quindi la proposizione è \emph{falsa}, e $n=40$ è il controesempio. Conferma del principio: nessuna quantità di casi favorevoli prova un universale; un solo caso sfavorevole lo confuta.
\end{esempio}

% ============================================================
\section{Esercizi proposti}\label{sec:ld-003-07-esercizi-proposti}
% ============================================================

\begin{eserciziobox}
\begin{enumerate}
  \item Stabilisci il valore di verità delle seguenti proposizioni e, in caso di falsità, fornisci un controesempio:\quad
        (a) $\forall x\in\R:\ x^2>0$;\quad
        (b) $\forall n\in\N:\ n+1>0$;\quad
        (c) $\exists x\in\R:\ x^2+1=0$;\quad
        (d) $\exists n\in\N:\ n^2=n+1$;\quad
        (e) $\forall n\in\N:\ 2n$ è pari.
  \item Traduci in linguaggio simbolico (scegliendo opportunamente i predicati):\quad
        (a) ``il prodotto di due numeri pari è pari'';\quad
        (b) ``esistono due interi distinti con lo stesso quadrato'';\quad
        (c) ``non tutti i numeri primi sono dispari'';\quad
        (d) ``ogni triangolo equilatero è isoscele''.
  \item Scrivi la negazione delle seguenti proposizioni, riformulandola in italiano nel modo più naturale possibile:\quad
        (a) $\forall x\in\R:\ x^2\ge 0$;\quad
        (b) $\exists n\in\N:\ n>10^{10}$;\quad
        (c) ``ogni studente della classe ha consegnato il compito'';\quad
        (d) ``esiste almeno un libro non letto sullo scaffale''.
  \item Per ciascuna delle implicazioni quantificate, scrivi la negazione e indica se sei in grado di stabilire chi è vero (l'originale o la negazione):\quad
        (a) $\forall n\in\N:\ n$ primo $\Rightarrow n$ dispari;\quad
        (b) $\forall x\in\R:\ x>0\Rightarrow x^2>0$;\quad
        (c) $\forall n\in\N:\ n^2$ pari $\Rightarrow n$ pari.
  \item Distingui in italiano e in simboli le due proposizioni\quad
        (a) ``per ogni allievo esiste un libro che ha letto'';\quad
        (b) ``esiste un libro che ogni allievo ha letto''.\quad
        Quale delle due è più forte? Quale implica l'altra?
  \item Sia $P(x,y)$: ``$x+y=10$'' con $x,y\in\Z$. Stabilisci il valore di verità di:\quad
        (a) $\forall x\in\Z\ \exists y\in\Z : P(x,y)$;\quad
        (b) $\exists y\in\Z\ \forall x\in\Z : P(x,y)$;\quad
        (c) $\exists x,y\in\Z : P(x,y)$;\quad
        (d) $\forall x,y\in\Z : P(x,y)$.
  \item Sia $\mathbb{P}$ l'insieme dei numeri primi. Traduci in simboli ``esiste un primo pari ed è unico''. Riconosci il quantificatore $\exists!$.
  \item (Discussione.) Verifica con due controesempi, presi nel dominio $D=\{1,2,3,4,5\}$, la non commutatività di $\forall\exists$ e $\exists\forall$ per il predicato $P(x,y): y>x$. Confronta poi con il caso $D=\R$.
\end{enumerate}
\end{eserciziobox}

% ============================================================
\section{Riepilogo del capitolo}\label{sec:ld-003-08-riepilogo-del-capitolo}
% ============================================================

\begin{riepilogo}
\begin{itemize}
  \item Un \emph{predicato} $P(x)$ contiene variabili libere e diventa proposizione solo quando le variabili ricevono un valore o vengono \emph{quantificate}.
  \item Il \emph{quantificatore universale} $\forall x\in D : P(x)$ è vero se ogni elemento di $D$ soddisfa $P$. Per smentirlo basta un \emph{controesempio}.
  \item Il \emph{quantificatore esistenziale} $\exists x\in D : P(x)$ è vero se almeno un elemento di $D$ soddisfa $P$. Per provarlo vero basta esibire un esempio.
  \item Esistenza e unicità si esprimono con $\exists!\, x\in D : P(x)$, equivalente a esistenza più ``due qualunque soluzioni coincidono''.
  \item Leggi di De Morgan per i quantificatori:
        $\lnot(\forall x:P(x))\equiv\exists x:\lnot P(x)$,\
        $\lnot(\exists x:P(x))\equiv\forall x:\lnot P(x)$.
  \item Per negare un'affermazione quantificata: \emph{scambiare ogni $\forall$ con $\exists$ e viceversa, e negare il predicato finale}. In particolare $\lnot(p\Rightarrow q)\equiv p\land\lnot q$ (capitolo \ref{cap:LD-002}).
  \item I quantificatori dello stesso tipo \emph{commutano}; quelli di tipo diverso \textbf{non} commutano: $\forall x\,\exists y$ ammette $y$ dipendente da $x$, mentre $\exists y\,\forall x$ pretende un $y$ unico valido per tutti gli $x$.
\end{itemize}
\end{riepilogo}