Basi di logica e tecniche di dimostrazione¶
Parte 1 · Numeri e logica · Capitolo 2 · dalle dispense di Fabio Furini · PDF del capitolo
1. Simboli logici¶
-
il simbolo “\(\forall\)” si chiama quantificatore universale e si legge “per ogni”, “per tutti” , “per ciascuno”
-
il simbolo “\(\exists\)” si chiama quantificatore esistenziale e si legge “esiste”, “esistono”
-
il simbolo “\(\Rightarrow\)” si chiama implicazione logica e si legge “implica” o “se … allora”
-
il simbolo “\(:\)” si legge “tale che”
-
il simbolo “\(\in\)” si legge “appartiene”
-
il simbolo “\(\notin\)” si legge “non appartiene”
-
il simbolo “\(\vee\)” si chiama disgiunzione logica e si legge “o”, “oppure” , “or”
-
il simbolo “\(\wedge\)” si chiama congiunzione logica e si legge “e”, “and”
-
il simbolo “\(\neg\)” si chiama negazione logica e si legge “non”, “not”.
2. Implicazioni universali e dimostrazioni¶
Predicati (o proprietà) e proposizioni (o enunciati)
-
Consideriamo la seguente affermazione:
\[\begin{equation} \label{TT} ``{\rm il~numero~naturale~} n {\rm ~è~dispari}'' \end{equation}\]e chiediamoci se è vera. Ovviamente la risposta è: “dipende da \(n\)”. Infatti nella \(\eqref{TT}\) il simbolo \(n\) rappresenta una variabile che può assumere valori diversi e rendere l'affermazione vera o falsa.
Una frase di questo tipo si chiama predicato (o proprietà): la sua verità o falsità dipende dai valori della o delle variabili che in essa compaiono.
-
Consideriamo ora la seguente affermazione:
\[\begin{equation} \label{TTT} ``{\rm per~ogni~numero~naturale~} n, {\rm ~se~} n {\rm ~è~dispari~allora~} n^2 {\rm~ è~dispari}'' \end{equation}\]che possiamo scrivere più formalmente nel modo seguente:
\[\begin{equation} \label{TTTT} \forall n \in \N ~~(n {\rm ~~dispari~~} \Rightarrow n^2 {\rm ~~dispari~~}) \end{equation}\]Si dice in questo caso che la variabile \(n\) non è libera, ma vincolata dal quantificatore \(\forall\). Come conseguenza si ha che la \(\eqref{TTTT}\) è vera o falsa “ una volta per tutte” e prende il nome di proposizione (o enunciato).
In particolare, i componenti della \(\eqref{TTTT}\) sono l'insieme \(\N\), due predicati definiti su \(\N\) dati da
\[ p(n) : ``n {\rm~dispari}'' {\rm~~e~~} q(n) : ``n^2 {\rm~dispari}'' \]e l'implicazione
\[ p(n) \Rightarrow q(n). \]
Definizione 1: di implicazione universale
In generale, un enunciato che presenti un insieme \(A\), due predicati \(p(x)\) e \(q(x)\) il cui argomento \(x\) varia in \(A\) e la struttura logica:
prende il nome di implicazione universale.
La maggior parte dei teoremi è costituita da implicazioni universali, nelle quali il predicato \(p(x)\) fa la parte dell'ipotesi e il predicato \(q(x)\) fa la parte della tesi.
-
In particolare la \(\eqref{TTTT}\) è una proposizione (o un enunciato):
Proposizione 1
\[\begin{equation} \label{CC} \forall n \in \N ~~(~n {\rm ~~dispari~~} \Rightarrow n^2 {\rm ~~dispari}~) \end{equation}\]In questo caso ci si convince facilmente che la proposizione sia vera, ma come si fa a dimostrarlo rigorosamente?
-
Per esempio, è sufficiente osservare che \(3\) è dispari e \(3^2=9\) è dispari per affermare che la proposizione sia vera? Certamente no, poiché la proposizione pretende che l'implicazione universale valga per ogni numero naturale. Tuttavia, i numeri dispari sono infiniti: come facciamo a provare un'implicazione universale per infiniti numeri?
-
Il procedimento chiave è questo: si considera il generico \(n\) che soddisfa l'ipotesi (essere dispari) e si dimostra che \(n\) soddisfi la tesi (il suo quadrato è dispari).
Vediamo come si opera per dimostrare la precedente proposizione:
Dimostrazione
Sia \(n\) dispari e proviamo che allora \(n^2\) è dispari.
Qualunque numero dispari si può scrivere nella forma \(2\:k + 1\), con un opportuno \(k \in \N\). Osserviamo inoltre che \(2\:k\) è un numero pari per qualunque \(k \in \N\).
Sia dunque \(n = 2k + 1\) un numero dispari (\(k \in \N\)), occorre quindi poter scrivere \(n^2\) come un numero intero pari più uno. Si ha:
\[ n^2 = (2\:k + 1)^2 = 4\:k^2 + 4\:k +1 = 2\:(2\:k^2 + 2\:k) +1 . \]Poiché \(2\:(2\:k^2 + 2\:k)\) è un intero pari, allora \(n^2\) è dispari. □
Per dimostrare la correttezza di un'implicazione universale come la \(\eqref{JJ}\), si considera il generico \(x\) che soddisfi l'ipotesi \(p(x)\) e si cerca di dimostrare che la tesi \(q(x)\) sia vera.
- Proviamo ora una simile relazione per i numeri pari:
Proposizione 2
Dimostrazione
Sia \(n\) pari e proviamo che allora \(n^2\) è pari.
Sia dunque \(n = 2\:k\) un numero pari (\(k \in \N\)), occorre quindi poter scrivere \(n^2\) come un numero intero pari. Si ha:
Poiché \(2\:(2\:k^2)\) è un intero pari, allora \(n^2\) è pari. □
2.1 Controesempi¶
I controesempi sono una tecnica importante per dimostrare la falsità di un'implicazione universale.
-
Chiediamoci, per esempio, se la seguente implicazione universale sia vera o falsa:
\[\begin{equation} \label{TEST} \forall n \in \N ~~(~n {\rm ~~primo~~} \Rightarrow n {\rm ~~dispari}~) \end{equation}\]Un attimo di riflessione mostra che questa proposizione è falsa. Infatti, il numero 2 è primo ma è pari.
Per poter affermare che un'implicazione universale sia vera è necessaria una dimostrazione (un esempio non è sufficiente), mentre per dimostrare che un'implicazione universale sia falsa basta un esempio contrario.
- L'implicazione universale pretende che ogni \(x\) che soddisfi l'ipotesi soddisfi anche la tesi: perciò, se troviamo anche un solo esempio di \(x\) che soddisfi l'ipotesi ma non la tesi, questo significa che l'implicazione universale sia falsa. Non “falsa in un caso”, ma semplicemente “falsa”, perché l'implicazione universale è vera o falsa una volta per tutte.
Definizione 2: di controesempio
In generale, un esempio che soddisfi l'ipotesi ma non la tesi di una implicazione universale, e che quindi ne dimostri la falsità, si chiama controesempio.
-
La dimostrazione formale che la precedente implicazione universale sia falsa è la seguente:
Dimostrazione
Il numero \(2\) è un controesempio per l'implicazione universale: “Per ogni numero naturale \(n\), se \(n\) è primo allora \(n\) è dispari". □
La negazione della proposizione
è la proposizione
Questo \(x\) particolare costituisce un controesempio.
3. Legge della contronominale¶
- È una tecnica di dimostrazione indiretta
L'implicazione universale
è logicamente equivalente a
La seconda implicazione si dice la contronominale della prima.
-
Ad esempio: poiché sappiamo che vale l'implicazione universale (proposizione ↗)
\[\begin{equation*} \forall n \in \N ~~(~n {\rm ~~dispari~~} \Rightarrow n^2 {\rm ~~dispari}~) \end{equation*}\]vale la seguente proposizione:
Proposizione 3
\[\begin{equation} \label{DD} \forall n \in \N ~~(n^2 {\rm ~~pari~~} \Rightarrow n {\rm ~~pari~~}) \end{equation}\]Dimostrazione
Sia \(n^2\) pari e proviamo che allora \(n\) è pari. Dimostriamo la \(\eqref{DD}\) basandoci sulla veridicità della \(\eqref{CC}\).
Se \(n\) non è pari allora è dispari e quindi \(n^2\) è dispari per la \(\eqref{CC}\). Questo caso contraddice l'ipotesi che \(n^2\) sia pari (quindi non può accadere).
Di conseguenza \(n\) è pari e la \(\eqref{DD}\) è dimostrata. □
-
Il ragionamento fatto nella precedente dimostrazione ha una validità generale, e mostra appunto che se è vera la \(\eqref{AA}\) allora è vera la \(\eqref{BB}\); Inoltre, se è vera la seconda allora è vera la prima (perché “non non \(p(x)\)” è logicamente equivalente a \(p(x)\)), per cui le due sono logicamente equivalenti.
L'equivalenza tra \(\eqref{AA}\) e \(\eqref{BB}\) è detta legge della contronominale. È un metodo di dimostrazione indiretta che consiste nel provare la \(\eqref{BB}\) per mostrare che la \(\eqref{AA}\) sia vera (prevede di dimostrare che la negazione della tesi implica la negazione dell'ipotesi).
Nell'usare la legge della contronominale occorre saper costruire la corretta negazione di una proposizione o proprietà data.
-
Dati \(p(x)\) e \(q(x)\), due predicati o proprietà qualsiasi, riportiamo schematicamente alcune regole con cui si costruisce la negazione di una proposizione o proprietà.
La negazione di
\[ ``{\rm per~ogni~~} x \in A {\rm~~vale~~} p (x)'' \]\[ \forall x \in A ~~\big(~p(x)~ \big) \]è
\[ ``{\rm esiste~~} x \in A {\rm~~per~cui~non~vale~} p (x) '' \]\[ \exists x \in A ~~\big(~\neg p(x) ~\big) \]La negazione di
\[ ``{\rm esiste~~} x \in A {\rm~~per~cui~vale~~} p (x)'' \]\[ \exists x \in A ~~\big(~p(x)~ \big) \]è
\[ ``{\rm per~ogni~~} x \in A {\rm~~non~vale~} p (x) '' \]\[ \forall x \in A ~~\big(~\neg p(x) ~\big) \]La negazione di
\[ ``{\rm vale~~} p (x) {\rm ~~e~~vale~~} q (x)'' \]\[ \big(~p(x) \wedge q(x)~\big) \]è
\[ ``{\rm non~vale~~} p (x) {\rm ~~o~~non~vale~~} q (x)'' \]\[ \big(~\neg p(x) ~\vee~ \neg q(x)~\big) \]La negazione di
\[ ``{\rm vale~~} p (x) {\rm ~~o~~vale~~} q (x)'' \]\[ \big(~p(x) ~\vee~ q(x)~\big) \]è
\[ ``{\rm non~vale~~} p (x) {\rm ~~e~~non~vale~~} q (x)'' \]\[ \big(~\neg p(x) ~\wedge~ \neg q(x)~\big) \]
4. Condizioni sufficienti e condizioni necessarie¶
Definizione 3: di condizione sufficiente
Una condizione sufficiente è quella che, se soddisfatta, garantisce la verità della proposizione.
Definizione 4: di condizione necessaria
Una condizione necessaria è quella che deve essere soddisfatta affinché la proposizione sia vera.
Dati \(p(x)\) e \(q(x)\), due predicati o proprietà qualsiasi. Se \(p(x)\) implica \(q(x)\), formalmente:
allora:
-
\(p(x)\) è condizione sufficiente a \(q(x)\)
-
\(q(x)\) è condizione necessaria a \(p(x)\)
-
Abbiamo visto che la seguente implicazione universale è vera (proposizione \(\eqref{CC}\)):
\[\begin{equation*} \forall n \in \N ~~(~n {\rm ~~dispari~~} \Rightarrow n^2 {\rm ~~dispari}~) \end{equation*}\]Quindi “\(n\) dispari” è condizione sufficiente a “\(n^2\) dispari” e “\(n^2\) dispari” è condizione necessaria per “\(n\) dispari” .
-
Proviamo ora che anche la seguente proposizione sia vera:
Proposizione 4
Dimostrazione
Sia \(n^2\) dispari e proviamo che allora \(n\) sia dispari.
Sia dunque \(n^2 = 2\;(2\;k^2 +2\;k)+1\) un numero dispari (\(k \in \N\)), dato che \(2\;(2\;k^2 +2\;k)\) è un numero pari). Occorre quindi poter scrivere \(n\) come un numero intero pari più uno. Si ha:
Poiché \(2\;k+1\) è un intero dispari, allora \(n\) è dispari. □
In questo modo abbiamo provato che “\(n^2\) dispari” è condizione necessaria e sufficiente per “\(n\) dispari” e anche che “\(n\) dispari” è condizione necessaria e sufficiente per “\(n^2\) dispari”:
Proposizione 5
-
Abbiamo visto che la seguente implicazione universale è vera (proposizione \(\eqref{TEST_tris}\)):
\[\begin{equation*} \forall n \in \N ~~(~n {\rm ~~pari~~} \Rightarrow n^2 {\rm ~~pari}~) \end{equation*}\]Quindi “\(n\) pari” è condizione sufficiente a “\(n^2\) pari” e “\(n^2\) pari” è condizione necessaria per “\(n\) pari”.
-
Proviamo ora che anche la seguente proposizione sia vera (dimostrazione diretta, senza usare la legge della contronominale come visto in precedenza \(\eqref{DD}\)):
Dimostrazione
Sia \(n^2\) pari e proviamo che allora \(n\) è pari.
Sia dunque \(n^2 = 2\;(2\;k^2)\) un numero pari (\(k \in \N\)), occorre quindi poter scrivere \(n\) come un numero intero pari. Si ha:
Poiché \(2\;k\) è un intero pari, allora \(n\) è pari. □
In questo modo abbiamo provato che “\(n^2\) pari” è condizione necessaria e sufficiente per “\(n\) pari” e anche che “\(n\) pari” è condizione necessaria e sufficiente per “\(n^2\) pari”:
Proposizione 6
Esempio 1: condizioni necessarie e sufficienti
Ad esempio, per una matrice quadrata di numeri reali, il fatto che il suo determinante sia diverso da zero è condizione necessaria e sufficiente affinché essa sia invertibile.
Proposizione 7
Dimostrazione
Sia \(n>2\) un numero primo e proviamo che allora \(n\) è dispari.
Se \(n\) non è dispari, è pari. Ma nessun numero pari maggiore di due è primo, fatto che contraddice l'ipotesi che \(n\) sia primo e maggiore di due (quindi questo caso non può accadere).
Di conseguenza \(n\) è dispari. □
-
Quindi “\(n\) dispari” è condizione necessaria per “\(n\) primo > 2” e “\(n\) primo > 2” è condizione sufficiente a “\(n\) dispari”.
-
Però “\(n\) dispari” non implica “\(n\) primo > 2”, dato che per esempio il numero \(9\) non è primo (controesempio). Ovvero:
\[\begin{equation*} \forall n \in \N ~~(~n {\rm ~~ dispari~~} \nRightarrow n {\rm ~~numero~ primo~maggiore~di~} 2~) \end{equation*}\]Quindi “\(n\) dispari” è condizione necessaria ma non sufficiente per “\(n\) primo >2” e “\(n\) primo > 2” è condizione sufficiente ma non necessaria a “\(n\) dispari”.
Proposizione 8
Dimostrazione
Sia \(n\) un numero divisibile per sei e proviamo che allora \(n\) è pari.
Se \(n\) non è pari, è dispari. Ma nessun numero dispari è divisibile per sei, fatto che contraddice l'ipotesi che \(n\) sia divisibile per sei (quindi questo caso non può accadere).
Di conseguenza \(n\) è pari. □
-
Quindi “\(n\) pari” è condizione necessaria per “\(n\) divisibile per 6” e “\(n\) divisibile per 6” è condizione sufficiente a “\(n\) pari”.
-
Però “\(n\) pari” non implica “\(n\) divisibile per 6”, dato che per esempio il numero \(2\) è pari ma non è divisibile per sei (controesempio). Ovvero:
\[\begin{equation*} \forall n \in \N ~~(~n {\rm ~~pari} \nRightarrow ~ n {\rm ~ divisibile~per~~} 6) \end{equation*}\]Quindi “\(n\) pari” è condizione necessaria ma non sufficiente per “\(n\) divisibile per 6” e “\(n\) divisibile per 6” è condizione sufficiente ma non necessaria a “\(n\) pari”.
Esempio 2: condizioni necessarie/sufficienti ma non sufficienti/necessarie
Essere un quadrato implica essere un rettangolo:
dato che tutti i quadrati sono rettangoli.
Quindi “essere un rettangolo” è condizione necessaria per “essere un quadrato” ed “essere un quadrato” è condizione sufficiente ad “essere un rettangolo”.
Ma essere un rettangolo non implica essere un quadrato
perché esistono dei rettangoli che non sono dei quadrati.
Quindi “essere un rettangolo” non è condizione sufficiente (ma è necessaria) per “essere un quadrato” ed “essere un quadrato” non è condizione necessaria (ma è sufficiente) per “essere un rettangolo”.
5. Dimostrazioni per assurdo¶
- È una tecnica di dimostrazione indiretta
Definizione 5: di dimostrazione per assurdo
In generale, la dimostrazione per assurdo consiste nel supporre vera l'ipotesi del teorema e la negazione della tesi, e dedurre da questi fatti una contraddizione di qualsiasi tipo.
- Esemplifichiamo la dimostrazione per assurdo, col seguente teorema.
Teorema 1
Non esiste un numero razionale il cui quadrato è \(2\).
Dimostrazione
Supponiamo per assurdo che esista un numero \(r \in \Q\) tale che \(r^2 = 2\).
Possiamo scrivere \(r = \frac{n}{m}\) con \(n,m \in \Z\), \(m \neq 0\).
Inoltre, possiamo supporre che la frazione \(\frac{n}{m}\) sia già ridotta ai minimi termini, ossia “semplificata” (in altre parole: \(n\), \(m\) non contengono fattori comuni).
Abbiamo dunque la catena di implicazioni:
per cui \(n^2\) è pari; ma allora per la \(\eqref{HHHHHHHHH}\) anche \(n\) è pari e possiamo scrivere \(n = 2k\) per qualche \(k \in \Z\).
Quindi la relazione \(n^2 = 2\:m^2\) si può riscrivere come:
Per cui \(m^2\) è pari. Ma allora per la \(\eqref{HHHHHHHHH}\) anche \(m\) è pari.
Dunque sia \(n\) che \(m\) sono pari, e questo è assurdo, perché avevamo supposto che la frazione \(\frac{n}{m}\) fosse già stata semplificata.
La dimostrazione si trova negli Elementi di Euclide (circa 300 a. C.). □
6. Logica e insiemi¶
Il linguaggio logico e il linguaggio insiemistico sono due facce della stessa medaglia.
6.1 Implicazione logica e inclusione insiemistica¶
-
Esiste un parallelismo tra la relazione di inclusione insiemistica e l'implicazione logica. Per spiegarlo, consideriamo l'implicazione universale:
\[\begin{equation} \label{KK} \forall n \in \N ~~(n {\rm ~~divisibile~per~} 4 \Rightarrow n {\rm ~~divisibile~per~} 2) \end{equation}\]Se indichiamo con:
\[ D_4 =\big\{ ~~ n \in \N: n {\rm~~è~divisibile~per~~} 4 ~~\big\} {\rm ~~e~~} D_2 =\big\{ ~~ n \in \N: n {\rm~~è~divisibile~per~~} 2 ~~\big\} \]possiamo osservare che l'implicazione universale scritta sopra è equivalente all'affermazione:
\[ ``D_4 \subseteq D_2 '' \]Infatti, questa inclusione significa che ogni elemento appartenente a \(D_4\) appartiene anche a \(D_2\), cioè che ogni numero naturale divisibile per \(4\) è anche divisibile per \(2\).
L'implicazione universale:
è equivalente all'inclusione insiemistica:
6.2 Uguaglianza fra insiemi e implicazioni universali¶
-
Dimostrare l'uguaglianza tra due insiemi, i.e., \(A=B\), comporta dimostrare due implicazioni universali. Formalmente:
\[\begin{equation} \label{FFF} \forall x ~~(x \in A \Rightarrow x \in B) {\rm ~~~~~~e~~~~~~} \forall x ~~(x \in B \Rightarrow x \in A). \end{equation}\] -
Affermare che \(A \subsetneqq B\) significa affermare che “Ogni elemento che appartiene ad \(A\) appartiene anche a \(B\) ed esiste un elemento di \(B\) che non appartiene ad \(A\)”. Formalmente:
\[\begin{equation} \label{GGG} \forall x ~~(x \in A \Rightarrow x \in B) {\rm ~~~~~~e~~~~~~} \exists x \in B: x \notin A. \end{equation}\]
6.3 Operazioni tra insiemi e operazioni logiche¶
Esiste una relazione tra operazioni sugli insiemi e operazioni logiche. Precisamente:
-
L'intersezione insiemistica è definita mediante la “e” (congiunzione logica).
-
L'unione insiemistica è definita mediante la “o” (disgiunzione logica).
-
La differenza insiemistica e l'operazione di complementazione sono definite mediante il “non” (negazione logica).
-
Le proprietà distributive dell'unione e dell'intersezione degli insiemi:
Osservazione 1: proprietà distributive (insiemi)
Dati tre insiemi \(\red{A}, \blue{B}\) e \(\orange{C}\) abbiamo:
- Si possono riscrivere in termini di predicati osservando che il simbolo dell'intersezione \(\cap\) equivale alla congiunzione \(\wedge\) (“and”) e che il simbolo dell'unione \(\cup\) equivale alla disgiunzione \(\vee\) (“or”).
Osservazione 2: proprietà distributive (predicati)
Dati tre predicati \(\red{p(x)}, \blue{q(x)}\) e \(\orange{r(x)}\) abbiamo:
- Le leggi di DeMorgan:
Proposizione 9: Leggi di DeMorgan (insiemi)
Dati gli insiemi \(\blue{B}, \orange{C} \subseteq \violet{U}\), abbiamo
- Si possono riscrivere in termini di predicati osservando che l'operazione di complementazione equivale alla negazione \(\neg\) (“not”).
Proposizione 10: leggi di DeMorgan (predicati)
Dati due predicati \(\blue{q(x)}\) e \(\orange{r(x)}\) abbiamo: