Logica elementare

Proposizione

Una proposizione è un enunciato per il quale ha senso chiedersi se è vero o falso, e che ha uno solo dei due valori di verità. Le proposizioni si indicano con lettere come $p$, $q$, $r$. Ogni enunciato matematico, come un’uguaglianza o un teorema, è una proposizione.

• ”$7$ è un numero primo”: proposizione vera.
• "$2+2=5$": proposizione falsa.
• "$x+1=3$": enunciato con una variabile, che diventa una proposizione quando si assegna un valore a $x$. Un enunciato di questo tipo si chiama predicato e si indica con $p(x)$; i predicati si trasformano in proposizioni anche con i quantificatori.

Negazione

La negazione di $p$, indicata con $\neg p$ (“non $p$”), è la proposizione vera quando $p$ è falsa e falsa quando $p$ è vera.

La negazione di ”$7$ è primo” è ”$7$ non è primo”. La doppia negazione riporta alla proposizione di partenza: $\neg (\neg p)$ ha la stessa tavola di verità di $p$. La negazione compare nei controesempi e nelle dimostrazioni per assurdo.

Congiunzione e disgiunzione

La congiunzione $p\wedge q$ (”$p$ e $q$”) è vera quando $p$ e $q$ sono entrambe vere. La disgiunzione $p\vee q$ (”$p$ o $q$”) è vera quando almeno una tra $p$ e $q$ è vera, comprese le volte in cui lo sono entrambe.

Per $x=2$: la proposizione "$x>0\wedge x>3$" è falsa, perché la seconda parte è falsa; la proposizione "$x>0\vee x>3$" è vera, perché la prima parte è vera.

Implicazione

L’implicazione $p\Rightarrow q$ (“se $p$ allora $q$”) ha $p$ come ipotesi e $q$ come tesi, ed è falsa in un solo caso: $p$ vera e $q$ falsa.

Quando $p$ è falsa l’implicazione è vera qualunque sia $q$: l’implicazione impegna soltanto nei casi in cui l’ipotesi è vera. Per esempio “se $x>3$ allora $x>1$” è vera per ogni $x$ reale; per $x=0$ l’ipotesi è falsa e l’implicazione resta vera. Ogni teorema ha questa forma, quindi la tavola di verità dell’implicazione regola l’uso dei teoremi.

Inversa e contronominale

Data l’implicazione $p\Rightarrow q$:

• l’inversa è $q\Rightarrow p$ (si scambiano ipotesi e tesi);
• la contronominale è $\neg q\Rightarrow \neg p$ (si scambiano ipotesi e tesi e si negano entrambe).

La contronominale è equivalente all’implicazione di partenza: $p\Rightarrow q\equiv \neg q\Rightarrow \neg p$, perché le due tavole di verità coincidono. L’inversa ha invece una tavola di verità diversa, quindi può essere falsa anche quando l’implicazione è vera. Sull’equivalenza con la contronominale si fonda la dimostrazione per contronominale.

Condizione necessaria e condizione sufficiente

Se l’implicazione $p\Rightarrow q$ è vera:

• $p$ è condizione sufficiente per $q$: basta la verità di $p$ per garantire la verità di $q$;
• $q$ è condizione necessaria per $p$: ogni volta che $p$ è vera, anche $q$ è vera.

Se valgono sia $p\Rightarrow q$ sia $q\Rightarrow p$, si scrive $p\iff q$ (”$p$ se e solo se $q$”) e ciascuna delle due è condizione necessaria e sufficiente per l’altra. Nei teoremi l’ipotesi è una condizione sufficiente per la tesi; riconoscere quale verso dell’implicazione è stato dimostrato permette di usare il teorema nel verso corretto.

Quantificatore universale ed esistenziale

Un predicato $p(x)$ diventa una proposizione quando si quantifica la variabile:

• $\forall x\in A:p(x)$ (“per ogni $x$ in $A$ vale $p(x)$”) è vera quando $p(x)$ è vera per tutti gli elementi di $A$;
• $\exists x\in A:p(x)$ (“esiste almeno un $x$ in $A$ per cui vale $p(x)$”) è vera quando $p(x)$ è vera per almeno un elemento di $A$.

Per dimostrare una proposizione universale serve un argomento valido per ogni elemento, e un solo controesempio basta a confutarla; per dimostrare una proposizione esistenziale basta esibire un elemento che soddisfa il predicato.

Dimostrazione diretta

Si assume vera l’ipotesi $p$ e, con una catena di deduzioni, si arriva alla tesi $q$. È la struttura della maggior parte delle dimostrazioni e di ogni esercizio svolto: ciascun passaggio è una piccola deduzione da quanto già stabilito.

Dimostrazione per contronominale

Per dimostrare $p\Rightarrow q$ si dimostra la contronominale $\neg q\Rightarrow \neg p$, che è una proposizione equivalente. Conviene quando la negazione della tesi è più maneggevole dell’ipotesi, come negli enunciati su pari e dispari.

Dimostrazione per assurdo

Si assume che la tesi sia falsa e, deducendo correttamente, si arriva a una contraddizione, cioè a una proposizione falsa oppure alla negazione dell’ipotesi. Poiché da premesse vere seguono soltanto conclusioni vere, l’assunzione era falsa, quindi la tesi è vera. Per dimostrare $p\Rightarrow q$ per assurdo si assume $p\wedge \neg q$, che è la negazione dell’implicazione.