\chapter{Implicazione condizione necessaria e sufficiente}\label{cap:LD-004}

\citazioneinizio{%
  Risolvere un problema significa stabilire un legame preciso fra ciò che è dato e ciò che è cercato.%
}{George Pólya, \emph{How to Solve It} (1945)}

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

Nei capitoli precedenti abbiamo definito l'implicazione $p\Rightarrow q$ come connettivo logico (capitolo \ref{cap:LD-002}) e abbiamo visto come si comporta con i quantificatori (capitolo \ref{cap:LD-003}). Ora facciamo un passo in più: \emph{interpretiamo} l'implicazione come la struttura portante di ogni teorema, cioè di ogni affermazione matematica che intendiamo dimostrare.

Un teorema ha sempre la forma ``se vale $p$, allora vale $q$'': $p$ è l'\emph{ipotesi} (ciò che si suppone), $q$ è la \emph{tesi} (ciò che si vuole concludere). Le parole \emph{necessario} e \emph{sufficiente}, che usiamo nel linguaggio comune in modo intercambiabile, in matematica indicano due cose nettamente diverse: ``sufficiente'' è la condizione che, da sola, basta a far succedere qualcosa; ``necessaria'' è la condizione senza la quale quel qualcosa non può succedere.

Capire bene questa distinzione è essenziale per leggere correttamente gli enunciati, per non confondere un'implicazione con la sua inversa, e per impostare in modo pulito le dimostrazioni. In questo capitolo affrontiamo la struttura logica dei teoremi e introduciamo le quattro forme che si ottengono da un'implicazione: \emph{diretta}, \emph{inversa}, \emph{contraria} e \emph{contronominale}.

% ============================================================
\section{Premessa e conclusione}\label{sec:ld-004-01-premessa-e-conclusione}
% ============================================================

\begin{definizione}[Struttura di un teorema]
La maggior parte degli enunciati matematici ha la forma
\[
  \text{se } p \text{ allora } q, \qquad \text{in simboli} \qquad p\Rightarrow q.
\]
La proposizione $p$ si dice \textbf{ipotesi} (o \emph{premessa}, \emph{antecedente}). La proposizione $q$ si dice \textbf{tesi} (o \emph{conclusione}, \emph{conseguente}).
\end{definizione}

Talvolta la struttura ``se\ldots allora'' è esplicita; più spesso è nascosta nel linguaggio. Riconoscerla è la prima abilità da sviluppare.

\begin{esempio}[Riconoscere ipotesi e tesi]
\begin{itemize}
  \item ``In ogni triangolo rettangolo il quadrato dell'ipotenusa è uguale alla somma dei quadrati dei cateti'' \\
  Ipotesi $p$: ``il triangolo è rettangolo''. Tesi $q$: ``vale $a^2+b^2=c^2$ con $c$ ipotenusa''. È il teorema di Pitagora, $p\Rightarrow q$.
  \item ``Un numero divisibile per $6$ è divisibile per $3$.'' \\
  Ipotesi: ``$n$ è divisibile per $6$''. Tesi: ``$n$ è divisibile per $3$''.
  \item ``Due rette parallele tagliate da una trasversale formano angoli alterni interni congruenti.'' \\
  Ipotesi: ``le rette $r$ ed $s$ sono parallele''. Tesi: ``gli angoli alterni interni formati con la trasversale $t$ sono congruenti''.
\end{itemize}
\end{esempio}

\begin{attenzione}
Una stessa frase può sembrare formulata senza ``se\ldots allora'', e contenere comunque un'implicazione implicita: ``i quadrati hanno i lati uguali'' significa ``se una figura è un quadrato, allora ha i lati uguali''. Saper riformulare un enunciato in forma esplicita di implicazione è il primo passo per dimostrarlo o confutarlo.
\end{attenzione}

\begin{nota}[Interpretazione insiemistica]
Se $p$ corrisponde a ``$x\in A$'' e $q$ a ``$x\in B$'' (dove $A$ e $B$ sono gli insiemi degli oggetti che soddisfano rispettivamente le due proprietà), allora l'implicazione $p\Rightarrow q$ equivale all'inclusione $A\subseteq B$: tutti gli elementi di $A$ sono in $B$. Lo riprenderemo nella figura \ref{fig:ld-004-inclusione}.
\end{nota}

% ============================================================
\section{Condizione sufficiente}\label{sec:ld-004-03-condizione-sufficiente}
% ============================================================

\begin{definizione}[Condizione sufficiente]
Se vale l'implicazione $p\Rightarrow q$, si dice che $p$ è \textbf{condizione sufficiente} per $q$. In altre parole: ``$p$ basta a garantire $q$''; non appena è verificata $p$, anche $q$ è automaticamente vera.
\end{definizione}

\begin{esempio}
\begin{itemize}
  \item ``Essere divisibile per $6$ è condizione sufficiente per essere divisibile per $3$''. Se $n$ è multiplo di $6$, di sicuro è multiplo di $3$.
  \item ``Essere un quadrato è condizione sufficiente per essere un rombo'': ogni quadrato ha i quattro lati uguali, dunque è un rombo.
  \item ``Avere $x>5$ è condizione sufficiente per avere $x^2>20$'': se $x>5$ allora $x^2>25>20$.
\end{itemize}
\end{esempio}

\begin{attenzione}
``Sufficiente'' non significa ``unica via''. ``Essere un quadrato'' è sufficiente per essere un rombo, ma non è l'unica strada: un rombo non quadrato (con angoli diversi da $\ang{90}$) esiste. \emph{Sufficiente} esprime una freccia che parte; non esclude che ce ne siano altre dirette allo stesso punto.
\end{attenzione}

% ============================================================
\section{Condizione necessaria}\label{sec:ld-004-02-condizione-necessaria}
% ============================================================

\begin{definizione}[Condizione necessaria]
Se vale l'implicazione $p\Rightarrow q$, si dice che $q$ è \textbf{condizione necessaria} per $p$. In altre parole: ``per poter avere $p$ è indispensabile che valga $q$''; senza $q$, $p$ non può essere vera.
\end{definizione}

La definizione si capisce meglio considerando la contrapposta. $p\Rightarrow q$ equivale (capitolo \ref{cap:LD-002}) a $\lnot q\Rightarrow\lnot p$: se $q$ non vale, allora non può valere neppure $p$. Ecco perché diciamo che $q$ è ``necessaria''.

\begin{esempio}
\begin{itemize}
  \item ``Essere divisibile per $3$ è condizione necessaria per essere divisibile per $6$'': se $n$ non è divisibile per $3$, allora certamente non è divisibile per $6$.
  \item ``Avere quattro lati è condizione necessaria per essere un quadrato'': se una figura non ha quattro lati, non può essere un quadrato.
  \item ``Avere $x^2>0$ è condizione necessaria per avere $x>5$'': se $x^2\le 0$ (cioè $x=0$), allora $x$ non può essere $>5$.
\end{itemize}
\end{esempio}

\begin{attenzione}
``Necessaria'' non significa ``sufficiente''. Avere quattro lati è necessario per essere un quadrato, ma non basta: anche un rettangolo non quadrato ha quattro lati. Una condizione \emph{necessaria} è una condizione \emph{minima}; può essere ben lontana dal garantire la conclusione.
\end{attenzione}

\begin{nota}[Una stessa implicazione, due letture]
L'implicazione $p\Rightarrow q$ si legge in due modi simmetrici:
\begin{itemize}
  \item ``$p$ è sufficiente per $q$'' (la freccia parte da $p$);
  \item ``$q$ è necessaria per $p$'' (la freccia arriva a $q$, e senza $q$ non si arriva a $p$).
\end{itemize}
Sono due descrizioni della stessa freccia, lette in due direzioni opposte.
\end{nota}

\begin{figure}[H]
\centering
\begin{tikzpicture}
  % Diagramma di Eulero: A dentro B, con A = "essere quadrato" e B = "essere rombo"
  \draw[thick, BLU, fill=BLU!8] (0,0) ellipse (3cm and 2cm);
  \draw[thick, VERDE, fill=VERDE!20] (-0.5,0) ellipse (1.4cm and 0.9cm);
  \node[VERDE] at (-0.5, 0) {$A$};
  \node[BLU]   at ( 2.2, 1.4) {$B$};
  \fill[ROSSO] (-0.5, 0.3) circle (2pt) node[above right] {\small$x$};
  \fill[ARANCIO] (1.5, -0.6) circle (2pt) node[above right] {\small$y$};
  \node at (0,-2.6) {\small$A\subseteq B$\quad equivale a\quad$\forall x:\ x\in A\Rightarrow x\in B$};
\end{tikzpicture}
\caption{Lettura insiemistica dell'implicazione. Se $A$ è l'insieme degli oggetti che soddisfano $p$ e $B$ l'insieme di quelli che soddisfano $q$, allora $p\Rightarrow q$ equivale a $A\subseteq B$. Ogni elemento di $A$ è in $B$ (caso di $x$); un elemento di $B$ può non essere in $A$ (caso di $y$).}
\label{fig:ld-004-inclusione}
\end{figure}

% ============================================================
\section{Condizione necessaria e sufficiente}\label{sec:ld-004-04-condizione-necessaria-e-sufficiente}
% ============================================================

Quando un'implicazione è vera \emph{in entrambi i sensi}, le due proposizioni $p$ e $q$ stanno ``alla pari'': l'una vale se e solo se vale l'altra. Si parla allora di condizione necessaria e sufficiente.

\begin{definizione}[Condizione necessaria e sufficiente]
Se valgono entrambe le implicazioni $p\Rightarrow q$ e $q\Rightarrow p$, si dice che $p$ è \textbf{condizione necessaria e sufficiente} (in breve: \emph{c.n.s.}) per $q$, e si scrive
\[
  p\Leftrightarrow q,
\]
si legge ``$p$ se e solo se $q$''.
\end{definizione}

In termini insiemistici, $p\Leftrightarrow q$ equivale all'uguaglianza $A=B$ tra gli insiemi associati: ogni $x\in A$ è in $B$ e viceversa.

\begin{esempio}[Caratterizzazioni notevoli]
\begin{itemize}
  \item ``$n$ è pari $\Leftrightarrow$ $n^2$ è pari'' (sui naturali). Sia ``pari $\Rightarrow$ $n^2$ pari'' che il viceversa sono veri.
  \item ``Un quadrilatero è un rombo $\Leftrightarrow$ ha le diagonali perpendicolari e che si bisecano''.
  \item ``$ax^2+bx+c=0$ con $a\neq 0$ ha due soluzioni reali distinte $\Leftrightarrow$ il discriminante $\Delta=b^2-4ac>0$''.
\end{itemize}
\end{esempio}

\begin{procedura}[Dimostrare un ``se e solo se'']
Per dimostrare un enunciato della forma $p\Leftrightarrow q$ si procede in due passi:
\begin{enumerate}
  \item \emph{Dimostrazione del ``solo se''} (freccia $\Rightarrow$): si suppone $p$ e si conclude $q$.
  \item \emph{Dimostrazione del ``se''} (freccia $\Leftarrow$): si suppone $q$ e si conclude $p$.
\end{enumerate}
Le due dimostrazioni vanno fatte separatamente: nessuna delle due implica l'altra.
\end{procedura}

\begin{esempio}[Pari e quadrato pari]
Dimostrare: $n$ è pari $\Leftrightarrow$ $n^2$ è pari, per $n\in\N$.

\textit{Soluzione.} Spezziamo in due implicazioni.

($\Rightarrow$) Sia $n$ pari: $n=2k$ con $k\in\N$. Allora $n^2=4k^2=2(2k^2)$ è pari.

($\Leftarrow$) Per contrapposizione: se $n$ è dispari, $n=2k+1$, allora $n^2=4k^2+4k+1=2(2k^2+2k)+1$ è dispari. Quindi se $n^2$ è pari, $n$ non può essere dispari, dunque è pari.

Le due implicazioni insieme provano l'equivalenza.
\end{esempio}

% ============================================================
\section{Implicazione contraria, inversa, contronominale}\label{sec:ld-004-05-implicazione-contraria-inversa-contronominale}
% ============================================================

Data un'implicazione $p\Rightarrow q$ (detta \emph{diretta}), si possono costruire tre implicazioni derivate scambiando o negando ipotesi e tesi.

\begin{definizione}[Le quattro implicazioni]
Data l'implicazione \emph{diretta} $p\Rightarrow q$, si chiamano:
\begin{itemize}
  \item \textbf{inversa}: $q\Rightarrow p$ (si scambiano ipotesi e tesi);
  \item \textbf{contraria}: $\lnot p\Rightarrow\lnot q$ (si negano ipotesi e tesi);
  \item \textbf{contronominale} (o \emph{contrapposta}): $\lnot q\Rightarrow\lnot p$ (si scambiano e si negano).
\end{itemize}
\end{definizione}

\begin{teorema}[Equivalenze tra le quattro forme]
Per ogni $p$, $q$ valgono le seguenti equivalenze e \emph{non} valgono le altre:
\[
  (p\Rightarrow q) \equiv (\lnot q\Rightarrow\lnot p) \qquad \text{(diretta $\equiv$ contronominale),}
\]
\[
  (q\Rightarrow p) \equiv (\lnot p\Rightarrow\lnot q) \qquad \text{(inversa $\equiv$ contraria).}
\]
In generale, invece, \emph{diretta} e \emph{inversa} (o \emph{contraria}) non sono logicamente equivalenti.
\end{teorema}

\textit{Dimostrazione.} La prima equivalenza è la legge di contrapposizione (capitolo \ref{cap:LD-002}). La seconda si ottiene applicando la stessa legge all'implicazione inversa $q\Rightarrow p$: la sua contrapposta è $\lnot p\Rightarrow\lnot q$, cioè la contraria di $p\Rightarrow q$.

\begin{figure}[H]
\centering
\begin{tikzpicture}[node distance=2.6cm, every node/.style={font=\small}]
  \node[draw, BLU, rounded corners, fill=BLU!10, align=center] (D) at (0,0) {Diretta\\$p\Rightarrow q$};
  \node[draw, ARANCIO, rounded corners, fill=ARANCIO!10, align=center] (I) at (5,0) {Inversa\\$q\Rightarrow p$};
  \node[draw, ARANCIO, rounded corners, fill=ARANCIO!10, align=center] (C) at (0,-2.4) {Contraria\\$\lnot p\Rightarrow\lnot q$};
  \node[draw, BLU, rounded corners, fill=BLU!10, align=center] (N) at (5,-2.4) {Contronominale\\$\lnot q\Rightarrow\lnot p$};

  \draw[<->, BLU, thick] (D) -- (N) node[midway, above, sloped] {\small equivalenti};
  \draw[<->, ARANCIO, thick] (I) -- (C) node[midway, above, sloped] {\small equivalenti};
  \draw[dashed, GRIGIO] (D) -- (I) node[midway, above] {\small non equiv.};
  \draw[dashed, GRIGIO] (C) -- (N) node[midway, above] {\small non equiv.};
\end{tikzpicture}
\caption{Le quattro implicazioni derivate da $p\Rightarrow q$. Sulla diagonale principale (in blu) stanno la diretta e la contronominale, sempre logicamente equivalenti. Sull'altra diagonale (in arancio) stanno inversa e contraria, anch'esse equivalenti tra loro ma non con la diretta.}
\label{fig:ld-004-quadrato-implicazioni}
\end{figure}

\begin{attenzione}[L'errore più frequente]
Confondere un'implicazione con la sua inversa è uno degli errori più comuni nei ragionamenti. Da ``se piove, la strada è bagnata'' \textbf{non} segue ``se la strada è bagnata, allora piove'': la strada potrebbe essere bagnata per un'autobotte o per la rugiada. Dal punto di vista logico, l'inversa va dimostrata \emph{a parte}; non discende dalla diretta.
\end{attenzione}

\begin{esempio}[Le quattro forme in un esempio concreto]
Considera l'implicazione diretta: \emph{``se $n$ è divisibile per $4$, allora $n$ è pari''} (vera).
\begin{itemize}
  \item Inversa: ``se $n$ è pari, allora $n$ è divisibile per $4$''. \textbf{Falsa}: $n=6$ è pari ma non multiplo di $4$.
  \item Contraria: ``se $n$ non è divisibile per $4$, allora $n$ è dispari''. \textbf{Falsa}: $n=6$.
  \item Contronominale: ``se $n$ è dispari, allora $n$ non è divisibile per $4$''. \textbf{Vera}, e infatti è equivalente alla diretta.
\end{itemize}
Diretta e contronominale hanno lo stesso valore di verità; inversa e contraria lo stesso valore di verità (qui entrambe false).
\end{esempio}

% ============================================================
\section{Esempi svolti}\label{sec:ld-004-07-esempi-svolti}
% ============================================================

\begin{esempio}[Riformulare con ``necessario'' e ``sufficiente'']
Esprimere la frase ``ogni triangolo equilatero è isoscele'' usando i termini necessario e sufficiente.

\textit{Soluzione.} Posto $p$: ``il triangolo è equilatero'' e $q$: ``il triangolo è isoscele'', la frase è $p\Rightarrow q$. Possiamo dire:
\begin{itemize}
  \item ``Essere equilatero è condizione sufficiente per essere isoscele.''
  \item ``Essere isoscele è condizione necessaria per essere equilatero.''
\end{itemize}
L'inversa ``ogni triangolo isoscele è equilatero'' è falsa: un triangolo isoscele con angolo al vertice diverso da $\ang{60}$ ha solo due lati uguali. Quindi ``essere isoscele'' non è sufficiente per essere equilatero.
\end{esempio}

\begin{esempio}[Caratterizzare con un ``se e solo se'']
Provare che un numero naturale è divisibile per $9$ se e solo se la somma delle sue cifre è divisibile per $9$.

\textit{Soluzione.} Sia $n=a_k\,10^k+a_{k-1}\,10^{k-1}+\cdots+a_1\,10+a_0$ con $a_i$ cifre. Poiché $10\equiv 1\pmod 9$, si ha $10^i\equiv 1\pmod 9$ per ogni $i\ge 0$. Quindi
\[
  n \equiv a_k+a_{k-1}+\cdots+a_1+a_0 \pmod 9.
\]
Ne segue che $9\mid n$ se e solo se $9$ divide la somma delle cifre. Le due frecce sono provate simultaneamente da una sola equivalenza modulare. È una c.n.s.\ (il celebre criterio di divisibilità per $9$).
\end{esempio}

\begin{esempio}[Smentire un'implicazione con un controesempio]
Confutare la frase ``se un numero è un quadrato perfetto, allora è dispari''.

\textit{Soluzione.} La frase ha la forma $\forall n\in\N : (n\text{ è quadrato}\Rightarrow n\text{ è dispari})$. Per smentirla basta un controesempio: $n=4=2^2$ è un quadrato perfetto, ma è pari. La frase è falsa.
\end{esempio}

\begin{esempio}[Dimostrazione per contronominale]
Dimostrare: ``se $n^2$ è dispari, allora $n$ è dispari'' (con $n\in\N$).

\textit{Soluzione.} È più comodo dimostrare la contronominale: ``se $n$ è pari, allora $n^2$ è pari''. Sia $n=2k$ con $k\in\N$: allora $n^2=4k^2=2(2k^2)$ è pari. Per la legge di contrapposizione (diretta $\equiv$ contronominale), abbiamo dimostrato anche l'implicazione di partenza.
\end{esempio}

\begin{esempio}[Identificare condizioni nelle definizioni]
Considera la definizione: \emph{``un parallelogrammo è un quadrilatero con i lati opposti paralleli''}. Quali sono le condizioni necessarie e sufficienti coinvolte?

\textit{Soluzione.} Una definizione è sempre una c.n.s. Posto $p$: ``il quadrilatero è un parallelogrammo'' e $q$: ``il quadrilatero ha i lati opposti paralleli'', la definizione afferma $p\Leftrightarrow q$:
\begin{itemize}
  \item $p\Rightarrow q$: ogni parallelogrammo ha lati opposti paralleli (definizione);
  \item $q\Rightarrow p$: ogni quadrilatero con lati opposti paralleli è un parallelogrammo (definizione, in senso opposto).
\end{itemize}
È così che funzionano tutte le definizioni: introducono un nome per chi soddisfa una proprietà, e dichiarano simultaneamente le due frecce.
\end{esempio}

% ============================================================
\section{Esercizi proposti}\label{sec:ld-004-08-esercizi-proposti}
% ============================================================

\begin{eserciziobox}
\begin{enumerate}
  \item Identifica ipotesi e tesi nelle seguenti proposizioni:\quad
        (a) ``ogni numero primo maggiore di $2$ è dispari'';\quad
        (b) ``se due rette sono parallele, hanno lo stesso coefficiente angolare'';\quad
        (c) ``i triangoli equilateri hanno tutti gli angoli congruenti'';\quad
        (d) ``se $a^2+b^2=0$ con $a,b\in\R$, allora $a=b=0$''.
  \item Per ciascuna delle seguenti implicazioni, scrivi inversa, contraria e contronominale, e stabilisci quali sono vere e quali false:\quad
        (a) ``se $n$ è pari, allora $n+2$ è pari'';\quad
        (b) ``se $x>0$, allora $x^2>0$'';\quad
        (c) ``se un quadrilatero ha quattro angoli retti, allora è un rettangolo''.
  \item Per ciascuna proposizione, riformula usando ``\emph{necessario}'' e ``\emph{sufficiente}'':\quad
        (a) ``ogni rettangolo ha gli angoli retti'';\quad
        (b) ``se $\Delta>0$, l'equazione $ax^2+bx+c=0$ ($a\neq 0$) ha due soluzioni reali distinte'';\quad
        (c) ``se un numero è multiplo di $12$, è multiplo di $4$''.
  \item Stabilisci, motivando, quali tra le seguenti coppie di condizioni sono c.n.s.\ tra loro:\quad
        (a) ``$n$ è multiplo di $5$'' / ``l'ultima cifra di $n$ è $0$ o $5$'';\quad
        (b) ``un quadrilatero è un quadrato'' / ``ha tutti i lati uguali'';\quad
        (c) ``$x^2=4$'' / ``$x=2$'' (con $x\in\R$);\quad
        (d) ``$x^2=4$'' / ``$x=\pm 2$''.
  \item Dimostra per contronominale: ``se $3n+1$ è pari, allora $n$ è dispari'' (con $n\in\N$).
  \item Trova un controesempio per la frase ``se $n$ è dispari, allora $n$ è primo'' (con $n\in\N$).
  \item Scrivi una formula del tipo $p\Rightarrow q$ il cui senso comune sembra suggerire l'equivalenza con la propria inversa, ma che in realtà non vale. (Suggerimento: pensa a frasi del linguaggio quotidiano del tipo ``se la macchina parte, allora c'è benzina''.)
  \item (Discussione.) Un compagno dice: ``per dimostrare $p\Leftrightarrow q$ basta dimostrare $p\Rightarrow q$, poi negare le proposizioni e ottenere automaticamente $q\Rightarrow p$''. È corretto? Giustifica e, se necessario, indica quale è il passo logico mancante.
\end{enumerate}
\end{eserciziobox}

% ============================================================
\section{Riepilogo del capitolo}\label{sec:ld-004-09-riepilogo-del-capitolo}
% ============================================================

\begin{riepilogo}
\begin{itemize}
  \item Ogni teorema ha la struttura $p\Rightarrow q$, dove $p$ è l'\emph{ipotesi} e $q$ è la \emph{tesi}.
  \item Dall'implicazione $p\Rightarrow q$ si dice:
        \emph{$p$ è condizione sufficiente per $q$} (basta $p$ per concludere $q$);
        \emph{$q$ è condizione necessaria per $p$} (senza $q$, $p$ non può essere vera).
  \item L'interpretazione insiemistica è $A\subseteq B$, dove $A$ è l'insieme degli oggetti che soddisfano $p$, $B$ quelli che soddisfano $q$.
  \item Se valgono entrambe $p\Rightarrow q$ e $q\Rightarrow p$, si scrive $p\Leftrightarrow q$ e si dice che $p$ è \emph{condizione necessaria e sufficiente} (c.n.s.) per $q$. In insiemi: $A=B$.
  \item Per dimostrare un ``se e solo se'' si dimostrano le due frecce separatamente.
  \item Da $p\Rightarrow q$ si costruiscono:
        \emph{inversa} $q\Rightarrow p$,
        \emph{contraria} $\lnot p\Rightarrow\lnot q$,
        \emph{contronominale} $\lnot q\Rightarrow\lnot p$.
  \item Equivalenze: diretta $\equiv$ contronominale; inversa $\equiv$ contraria. In generale diretta e inversa \textbf{non} sono equivalenti — confonderle è un errore tipico.
  \item Per smentire un'implicazione basta un \emph{controesempio}: un caso in cui l'ipotesi è verificata ma la tesi no.
\end{itemize}
\end{riepilogo}