È impossibile che uno stesso predicato appartenga e insieme non appartenga al medesimo soggetto, e sotto lo
stesso rispetto.” — Aristotele, Metafisica, libro IV
Nel capitolo precedente abbiamo imparato a parlare di insiemi: a dire “\(x\) appartiene” oppure “\(x\)
non appartiene”. Una volta che abbiamo un vocabolario per gli oggetti matematici, ci serve anche
un vocabolario per le frasi che li riguardano: come si combinano, come si negano, quando una frase
è conseguenza di un’altra.
Dire “\(\sqrt {2}\) non è razionale”, “se \(n\) è pari allora \(n^2\) è pari”, “\(x>0\) e \(y>0\) implica \(xy>0\)” significa usare delle particelle
precise — non, se…allora, e, o — che in matematica hanno un significato fissato una volta per tutte.
Capire questo linguaggio è il primo passo verso la dimostrazione: senza connettivi univoci non c’è
ragionamento univoco.
In questo capitolo introduciamo i cinque connettivi fondamentali (negazione, congiunzione,
disgiunzione, implicazione, doppia implicazione) e lo strumento delle tavole di verità, che permette
di ridurre il significato di qualsiasi enunciato composto a una semplice tabella di simboli. È uno
strumento meccanico ma potentissimo: ci consentirà di riconoscere quando due frasi dicono la stessa
cosa e quando una è conseguenza dell’altra.
Una proposizione (o enunciato) è una frase dichiarativa che può essere classificata come
vera oppure falsa, in modo univoco e indipendentemente da chi la pronuncia.
Indicheremo le proposizioni con lettere minuscole (\(p\), \(q\), \(r\), \(\ldots \)) e useremo i simboli V e F (oppure \(1\) e \(0\))
per indicare i due possibili valori di verità.
Esempio 3.1 — Frasi che sono proposizioni
Sono proposizioni:
\(p\): “\(7\) è un numero primo” (vera);
\(q\): “\(2+2=5\)” (falsa);
\(r\): “ogni numero pari è divisibile per \(3\)” (falsa);
\(s\): “\(\sqrt {2}\) è irrazionale” (vera).
Esempio 3.2 — Frasi che NON sono
proposizioni
Non sono proposizioni:
“Che ora è?” (è una domanda, non afferma nulla);
“Chiudi la porta!” (è un comando);
“Buongiorno!” (è un’esclamazione);
“Questa frase è falsa” (paradosso: non può essere né V né F);
“\(x+1=3\)” (dipende dal valore di \(x\): è un predicato, non una proposizione vera o propria —
lo riprenderemo nel capitolo sui quantificatori).
Attenzione!
Una proposizione è vera o falsa indipendentemente dal fatto che noi sappiamo quale dei
due valori abbia. La frase “esistono infinite coppie di primi gemelli” è una proposizione:
o è vera o è falsa, anche se a oggi nessuno sa quale delle due cose.
Nota — Due principi cardine
La logica classica si fonda su due principi che useremo implicitamente in tutto il
libro:
1.
principio di non contraddizione: nessuna proposizione può essere insieme vera e falsa;
2.
principio del terzo escluso: ogni proposizione è vera oppure falsa (non c’è un terzo
caso possibile).
Sono i due principi richiamati da Aristotele nella citazione di apertura.
Le proposizioni \(p\), \(q\), \(\ldots \) scritte “così come sono” si dicono atomiche o semplici. Combinandole con i
connettivi che introdurremo nelle prossime sezioni si ottengono proposizioni composte.
Il primo e più semplice connettivo è la negazione: opera su una sola proposizione e ne inverte il
valore di verità.
Definizione 3.2 — Negazione
La negazione di una proposizione \(p\) è la proposizione \(\lnot p\) (si legge “non \(p\)”), che è vera quando
\(p\) è falsa e falsa quando \(p\) è vera.
La regola si riassume in una tabella, detta tavola di verità del connettivo:
Se \(p\): “\(7\) è primo” (vera), allora \(\lnot p\): “\(7\) non è primo” (falsa). Se \(q\): “\(\pi \) è razionale” (falsa), allora
\(\lnot q\): “\(\pi \) non è razionale” (vera).
Attenzione!
Negare una proposizione non significa dire il contrario nel linguaggio comune. La
negazione di “tutti gli studenti sono presenti” non è “tutti gli studenti sono assenti”: è
“esiste almeno uno studente assente” (lo vedremo a fondo nel capitolo sui quantificatori).
Teorema 3.1 — Doppia negazione
Per ogni proposizione \(p\) vale \(\lnot (\lnot p) = p\).
Dimostrazione. Confrontiamo le colonne nella tavola di verità:
Le colonne di \(p\) e di \(\lnot (\lnot p)\) coincidono riga per riga: le due proposizioni hanno lo stesso valore di verità
in ogni caso, dunque coincidono.
I due connettivi binari più semplici corrispondono al nostro “e” e al nostro “o”.
Definizione 3.3 — Congiunzione
La congiunzione di \(p\) e \(q\) è la proposizione \(p\land q\) (si legge “\(p\) e \(q\)”), che è vera quando entrambe \(p\)
e \(q\) sono vere, e falsa in tutti gli altri casi.
Definizione 3.4 — Disgiunzione
La disgiunzione (inclusiva) di \(p\) e \(q\) è la proposizione \(p\lor q\) (si legge “\(p\) o \(q\)”), che è vera quando
almeno una fra \(p\) e \(q\) è vera, e falsa solo quando entrambe sono false.
La disgiunzione logica \(\lor \) è inclusiva: “\(p\) o \(q\)” è vera anche quando lo sono entrambe. Nel
linguaggio comune “o” è talvolta esclusiva (“prendi il caffè o il tè” di solito significa “uno
solo dei due”). In matematica si usa \(\lor \) in senso inclusivo; il caso esclusivo, indicato \(p\veebar q\) o
XOR, è vero solo se esattamente una delle due è vera.
Esempio 3.4 — Lettura concreta
Siano \(p\): “\(6\) è pari” (V) e \(q\): “\(6\) è primo” (F). Allora:
\(p\land q\): “\(6\) è pari e \(6\) è primo” F;
\(p\lor q\): “\(6\) è pari o \(6\) è primo” V;
\(\lnot p \land q\): “\(6\) non è pari e \(6\) è primo” F.
Il legame con la teoria degli insiemi (capitolo 2) è diretto: se interpretiamo \(p\) come “\(x\in A\)” e \(q\) come “\(x\in B\)”,
allora \(p\land q\) corrisponde a \(x\in A\cap B\) e \(p\lor q\) a \(x\in A\cup B\). La figura 3.1 lo visualizza.
Figura 3.1: Lettura insiemistica di congiunzione e disgiunzione. A sinistra, la regione colorata
è l’intersezione \(A\cap B\) (gli \(x\) per cui \(p\) e \(q\) sono vere). A destra, l’unione \(A\cup B\) (gli \(x\) per cui \(p\) o \(q\) è vera).
L’implicazione è il connettivo del ragionamento: corrisponde al “se…allora…”.
Definizione 3.5 — Implicazione
L’implicazione “se \(p\) allora \(q\)” è la proposizione \(p\Rightarrow q\), che è falsa soltanto nel caso in cui \(p\) sia
vera e \(q\) sia falsa, e vera in tutti gli altri casi. \(p\) si dice ipotesi (o antecedente), \(q\) si dice tesi
(o conseguente).
Le ultime due righe sono il punto più delicato per chi inizia. Se l’ipotesi \(p\) è falsa,
l’implicazione \(p\Rightarrow q\) si considera vera qualunque sia \(q\). È la cosiddetta implicazione vacua: “se
sono sulla Luna, allora \(2+2=4\)” è una implicazione vera, perché la premessa è falsa e dunque
l’implicazione non è mai messa alla prova.
Nota — Perché questa convenzione
L’idea è che \(p\Rightarrow q\) esprime una promessa: “se si verifica \(p\), allora si verificherà \(q\)”. La promessa è
violata solo se \(p\) accade ma \(q\) non accade. Se \(p\) non accade affatto, la promessa non è stata
messa alla prova e quindi non è stata infranta: la consideriamo vera.
Esempio 3.5 — Quattro casi
Sia \(p\): “\(n\) è multiplo di \(4\)”; \(q\): “\(n\) è pari”. Verifichiamo \(p\Rightarrow q\) per quattro scelte di \(n\):
\(n=8\): \(p\) V, \(q\) V. \(p\Rightarrow q\): V.
\(n=12\): \(p\) V, \(q\) V. \(p\Rightarrow q\): V.
\(n=6\): \(p\) F, \(q\) V. \(p\Rightarrow q\): V (caso “vacuo”).
\(n=7\): \(p\) F, \(q\) F. \(p\Rightarrow q\): V (caso “vacuo”).
Per nessun \(n\) multiplo di \(4\) accade \(q\) falso: l’implicazione resta sempre vera. Se trovassimo anche un
solo \(n\) multiplo di \(4\) ma dispari, avremmo \(p\) V e \(q\) F, e l’implicazione diventerebbe falsa (è il
controesempio).
Se \(p\Rightarrow q\), si dice che \(p\) è condizione sufficiente per \(q\), e che \(q\) è condizione necessaria per \(p\).
Cioè: per avere \(q\) basta avere \(p\); e per poter avere \(p\) è indispensabile che valga \(q\).
Esempio 3.6
“Se piove allora la strada è bagnata” (\(p\Rightarrow q\)): la pioggia è sufficiente a bagnare la strada
(basta che piova); la strada bagnata è necessaria se piove (non si dà pioggia senza strada
bagnata). Ma la strada bagnata può avere altre cause (un’autobotte), quindi non è
sufficiente a concludere che piova.
Le colonne di \(p\Rightarrow q\) e \(\lnot q\Rightarrow \lnot p\) coincidono riga per riga.
Nota
La legge di contrapposizione è alla base della dimostrazione per assurdo: per provare \(p\Rightarrow q\) si
può equivalentemente provare \(\lnot q\Rightarrow \lnot p\). La affronteremo nel dettaglio nel capitolo sulle tecniche
di dimostrazione.
Attenzione!
L’inversa \(q\Rightarrow p\) e la contraria \(\lnot p\Rightarrow \lnot q\), invece, non sono in generale equivalenti a \(p\Rightarrow q\). Se “piove \(\Rightarrow \)
strada bagnata” è vera, “strada bagnata \(\Rightarrow \) piove” può essere falsa (autobotte). Confondere
implicazione e inversa è uno degli errori logici più frequenti.
La doppia implicazione (o biimplicazione, “se e solo se”) è la proposizione \(p\Leftrightarrow q\), vera quando
\(p\) e \(q\) hanno lo stesso valore di verità (entrambe V oppure entrambe F), falsa altrimenti.
Per dimostrare “\(p\) se e solo se \(q\)” è quasi sempre conveniente provare separatamente le due
implicazioni: prima “se \(p\) allora \(q\)”, poi “se \(q\) allora \(p\)”. È la stessa idea della doppia inclusione
tra insiemi vista nel capitolo precedente.
Esempio 3.7
“Un numero intero è pari se e solo se il suo quadrato è pari”. È un teorema: dovremo
dimostrare entrambe le frecce, \(\Rightarrow \) (se \(n\) è pari, \(n^2\) è pari) e \(\Leftarrow \) (se \(n^2\) è pari, \(n\) è pari, la parte più
sottile).
Costruire la tavola di verità di una proposizione composta significa elencare tutti i possibili
valori delle proposizioni atomiche che la compongono e calcolare passo passo il valore di verità del
tutto.
Procedura — Costruzione di una tavola di
verità
1.
Si elencano le proposizioni atomiche \(p_1,\,p_2,\,\ldots ,\,p_n\) contenute nella formula.
2.
Si scrivono nelle prime \(n\) colonne tutte le \(2^n\) combinazioni di valori di verità (V/F) di \(p_1,\ldots ,p_n\).
3.
Si aggiungono colonne intermedie per le sotto-formule, calcolate seguendo l’ordine di
precedenza dei connettivi.
4.
L’ultima colonna è il valore della formula completa per ciascuna combinazione.
L’ordine di precedenza usuale (dal più stretto al più largo) è:
La formula è falsa solo nella seconda riga, in cui \(p\) e \(q\) sono entrambe vere ma \(r\) è falsa: in
quel caso la promessa “se \(p\) e \(q\), allora \(r\)” è infranta.
Figura 3.2: Albero di valutazione della formula \((p\lor q)\land \lnot r\) nel caso \(p=\text {V}\), \(q=\text {F}\), \(r=\text {F}\). Si parte dai valori atomici alle
foglie e si applicano i connettivi risalendo fino alla radice.
Definizione 3.9 — Tautologia, contraddizione
Una proposizione composta si dice:
tautologia se è vera per ogni possibile combinazione dei valori di verità degli atomi
che la compongono (tutta la colonna finale è V);
contraddizione se è falsa per ogni possibile combinazione (tutta la colonna finale è
F);
contingente negli altri casi.
Esempio 3.9 — Tautologie classiche
Sono tautologie:
il terzo escluso: \(p\lor \lnot p\);
la non contraddizione: \(\lnot (p\land \lnot p)\);
il modus ponens: \(\bigl ((p\Rightarrow q)\land p\bigr )\Rightarrow q\).
Si verifica costruendone la tavola di verità: la colonna finale è tutta V.
Definizione 3.10 — Equivalenza logica
Due proposizioni \(\varphi \) e \(\psi \) si dicono logicamente equivalenti, e si scrive \(\varphi \equiv \psi \), se hanno la stessa
tavola di verità (cioè se \(\varphi \Leftrightarrow \psi \) è una tautologia).
Teorema 3.4 — Leggi di De Morgan per i
connettivi
Per ogni \(p\), \(q\) valgono:
\[ \lnot (p\land q) \equiv \lnot p \lor \lnot q, \qquad \lnot (p\lor q) \equiv \lnot p \land \lnot q. \]
Dimostrazione (della prima). Si confrontano le colonne:
Le due colonne corrispondono riga per riga, quindi le due proposizioni sono logicamente
equivalenti. La seconda legge si dimostra in modo analogo.
Nota
Le leggi di De Morgan per i connettivi sono il duale logico delle leggi di De Morgan
per gli insiemi (capitolo 2): scambiare \(\land \) con \(\lor \) corrisponde, sul versante insiemistico, a
scambiare \(\cap \) con \(\cup \), e la negazione corrisponde al complemento.
“Non è vero che se \(p\) allora \(q\)” equivale a “\(p\) e non \(q\)”: è esattamente il controesempio, cioè
un caso in cui l’ipotesi è verificata ma la tesi no.
Negare la frase: “se un numero naturale è multiplo di \(6\), allora è multiplo di \(4\)”.
Soluzione. Posto \(p\): “\(n\) è multiplo di \(6\)” e \(q\): “\(n\) è multiplo di \(4\)”, la frase è \(p\Rightarrow q\). La negazione è
\[ \lnot (p\Rightarrow q) \equiv p\land \lnot q, \]
cioè: “esiste un numero naturale multiplo di \(6\) ma non multiplo di \(4\)”. Un controesempio: \(n=6\),
multiplo di \(6\) ma non di \(4\). Quindi la frase di partenza è falsa.
Esempio 3.11 — Verifica di una tautologia: modus
ponens
Verificare che \(\bigl ((p\Rightarrow q)\land p\bigr )\Rightarrow q\) è una tautologia.
L’ultima colonna è tutta V: la formula è una tautologia. È il principio di inferenza più
elementare: se sappiamo che \(p\Rightarrow q\) e che \(p\), possiamo concludere \(q\).
Esempio 3.12 — Contrapposta e dimostrazione
indiretta
Sia data l’implicazione: “se \(n^2\) è pari, allora \(n\) è pari”. Riformularla tramite la contrapposta.
Soluzione. Posto \(p\): “\(n^2\) è pari”, \(q\): “\(n\) è pari”, vogliamo dimostrare \(p\Rightarrow q\). La contrapposta è \(\lnot q\Rightarrow \lnot p\), ovvero:
“se \(n\) è dispari, allora \(n^2\) è dispari”. Quest’ultima si verifica direttamente: se \(n=2k+1\), allora
\[ n^2 = (2k+1)^2 = 4k^2+4k+1 = 2(2k^2+2k)+1, \]
quindi \(n^2\) è dispari. Per la legge di contrapposizione, abbiamo provato anche l’implicazione
di partenza.
Le colonne \(\varphi \) e \(\psi \) coincidono: le due proposizioni sono logicamente equivalenti. Si può dunque
“distribuire” l’implicazione rispetto alla congiunzione.
Stabilisci quali delle seguenti frasi sono proposizioni e, per quelle che lo sono, indicane
il valore di verità: (a) “\(3+5=8\)”; (b) “apri la finestra”; (c) “\(\sqrt {9}=\pm 3\)”; (d) “\(x\) è positivo”; (e)
“ogni numero primo maggiore di \(2\) è dispari”; (f) “questa frase non è vera”.
2.
Date \(p\): “\(10\) è divisibile per \(5\)” (V), \(q\): “\(10\) è dispari” (F), \(r\): “\(10>20\)” (F), determina il valore di verità
di: \(p\land q\), \(p\lor q\), \(\lnot q\), \(p\Rightarrow q\), \(q\Rightarrow p\), \((p\lor q)\land \lnot r\), \((p\Rightarrow q)\Leftrightarrow r\).
3.
Scrivi la tavola di verità di \((p\lor q)\land \lnot (p\land q)\) (è la disgiunzione esclusiva XOR). In quali righe la
formula è vera?
4.
Costruisci la tavola di verità di \((p\Rightarrow q)\Rightarrow (\lnot q\Rightarrow \lnot p)\) e verifica che è una tautologia.
5.
Verifica con una tavola di verità la seconda legge di De Morgan: \(\lnot (p\lor q)\equiv \lnot p\land \lnot q\).
6.
Determina la negazione delle seguenti frasi, riformulandola con \(\land \) se possibile: (a) “se
\(n\) è primo allora \(n\) è dispari”; (b) “se piove, esco con l’ombrello”; (c) “se \(x>0\) e \(y>0\), allora
\(x+y>0\)”.
7.
Per la frase “se \(n\) è divisibile per \(4\), allora \(n\) è pari”, scrivi inversa, contraria e
contrapposta. Quali sono vere e quali false? Confrontale tra loro.
8.
Stabilisci, costruendo le tavole, se le seguenti coppie sono logicamente equivalenti:
(a) \(p\Rightarrow (q\lor r)\) e \((p\Rightarrow q)\lor (p\Rightarrow r)\); (b) \(\lnot (p\Leftrightarrow q)\) e \((p\land \lnot q)\lor (\lnot p\land q)\); (c) \((p\land q)\Rightarrow r\) e \(p\Rightarrow (q\Rightarrow r)\).
9.
(Discussione.) Un compagno afferma: “se l’implicazione \(p\Rightarrow q\) è falsa, allora anche la sua
inversa \(q\Rightarrow p\) è falsa”. È vero? Giustifica con una tavola di verità o con un controesempio.
Una proposizione è una frase dichiarativa cui si può attribuire in modo univoco un
valore di verità (V o F). Reggono la logica classica i principi di non contraddizione e
di terzo escluso.
Ciascun connettivo è caratterizzato dalla sua tavola di verità. In particolare \(p\Rightarrow q\) è falsa
solo quando \(p\) è vera e \(q\) è falsa; quando \(p\) è falsa l’implicazione è vera “per vacuità”.
L’implicazione si legge anche: \(p\) sufficiente per \(q\), \(q\) necessaria per \(p\). Inversa \(q\Rightarrow p\) e contraria \(\lnot p\Rightarrow \lnot q\)
non sono equivalenti all’implicazione di partenza; la contrapposta \(\lnot q\Rightarrow \lnot p\) sì.
\(p\Leftrightarrow q\) equivale a \((p\Rightarrow q)\land (q\Rightarrow p)\): per provare un “se e solo se” si dimostrano separatamente le due frecce.
Una formula sempre vera è una tautologia, sempre falsa una contraddizione. Due
formule sono logicamente equivalenti (\(\equiv \)) se hanno la stessa tavola di verità.
![[Picture]](immagini_matematica/libro_matematica_a_capitoli12x.svg)
![[Picture]](immagini_matematica/libro_matematica_a_capitoli13x.svg)