Questi esercizi sulla logica (livello avanzato) sono utili per dimostrare che non è sempre necessario scrivere l’intera tavola di verità per ottenere delle informazioni su di una espressione logica.
In particolare, è possibile dimostrare che un’espressione è una tautologia ipotizzando per assurdo che è falsa e guardando cosa succede di conseguenza ai valori di verità delle proposizioni che la compongono. Allo stesso modo, è possibile dimostrare che un’espressione logica è una contraddizione ipotizzando per assurdo che è vera e di nuovo controllando cosa succede ai valori di verità delle singole proposizioni che compongono l’espressione.
La tecnica è particolarmente comoda per le espressioni logiche complesse poiché ci evita di dover costruire tavole di verità piuttosto grandi.
Esercizio 1
Mostrare che la seguente espressione non è una tautologia.
\[ (a \rightarrow (b \vee c)) \vee (a \rightarrow b) \]
SOLUZIONE
Possiamo sicuramente costruire la tavola di verità e verificare che almeno per una certa combinazione dei valori di verità delle proposizioni \( a, \: b, \: c \) l’espressione logica assegnata è falsa. Tuttavia, esiste un metodo più efficiente.
L’idea è quella di ipotizzare che l’espressione è falsa e, procedendo all’indietro dalle ultime operazioni logiche in ordine di precedenza fino alle prime, ricavare i corrispondenti valori di verità delle proposizioni \( a, \: b, \: c \ \).
Adottiamo quindi la seguente procedura:
- scriviamo sotto il testo della proposizione i valori di verità che via via si determinano prima per la proposizione, poi per le singole operazioni intermedie in essa presenti e per le singole proposizioni \( a, \: b, \: c \).
- scriviamo questi valori di verità in ordine cronologico, andando a capo in ogni passo successivo. Seguire questo ordine in modo preciso aiuta nei ragionamenti.
Il primo passo è ipotizzare il valore di verità falso per l’espressione logica. Scriveremo così una F sotto al simbolo \( \vee \) che corrisponde all’operazione che viene eseguita per ultima nell’espressione logica:
\[ \begin{array}{lllllllll}(a& \rightarrow (&b &\vee &c)) &\vee \quad&(a &\rightarrow &b) \\ &&&&&F \\ \end{array} \]
Ora, le operazioni successive sono le due implicazioni \( a \rightarrow (b \vee c) \) e \( a \rightarrow b \). Poiché abbiamo tra le due un’operazione di disgiunzione inclusiva e siccome abbiamo appena ipotizzato un valore di verità falso per la disgiunzione inclusiva stessa, potremo ad esempio ipotizzare un valore di verità falso per entrambe le implicazioni:
\[ \begin{array}{lllllllll}(a& \rightarrow (&b &\vee &c)) &\vee \quad&(a &\rightarrow &b) \\ &&&&&F \\&F&&&&&&F\end{array} \]
Come si può notare, abbiamo scritto dei valori di verità \( F \) proprio sotto ai simboli di implicazione.
Ora, poiché un’implicazione materiale è falsa solo se la premessa è vera e la conseguenza è falsa, per l’operazione di disgiunzione logica \( (b \vee c) \) e per le proposizioni \( a \) e \( b \) dovremo ipotizzare i valori di verità come segue:
\[ \begin{array}{lllllllll}(a& \rightarrow (&b &\vee &c)) &\vee \quad&(a &\rightarrow &b) \\ &&&&&F \\ &F&&&&&&F \\ V&&&F&&&V&&F\end{array} \]
Ma se l’implicazione \( B \vee C \) deve essere falsa e già sappiamo che \( B \) è falsa, allora anche \( C \) dovrà essere falsa (modus tollens):
\[ \begin{array}{lllllllll}(a& \rightarrow (&b &\vee &c)) &\vee \quad&(a &\rightarrow &b) \\ &&&&&F \\ &F&&&&&&F \\ V&&&F&&&V&&F \\ &&F &&F\end{array} \]
Siamo arrivati! Infatti, abbiamo attribuito ad ogni proposizione di partenza \( a, \: b, \: c \) un valore di verità. In particolare, ipotizzando che l’espressione logica è falsa abbiamo ottenuto che ciò avviene per \( a \) vera, \( b \) falsa e \( c \) falsa. Dunque, poiché in almeno un caso l’espressione logica è falsa, questa non è una tautologia 😉
Si poteva arrivare allo stesso risultato costruendo la tavola di verità, ma in questo modo abbiamo usato una tecnica più rapida ed elegante. In ogni caso, la tavola di verità conferma il risultato:
Il valore di verità dell’espressione logica è indicato in neretto (1 = vero, 0 = falso).
Direi che considerata la lunghezza della tavola di verità, il metodo appena introdotto è piuttosto interessante 😉
Esercizio 2
Mostrare che \( (p \rightarrow q) \vee (p \rightarrow \overline{q}) \) è una tautologia.
SOLUZIONE
Poiché una tautologia è un’espressione logica che è sempre vera, ipotizziamo per assurdo che l’espressione logica data sia falsa. Poiché l’ultima operazione in ordine di precedenza è la disgiunzione inclusiva, poniamo un valore di verità \( F \) sotto al simbolo \( \vee \):
\[ \begin{array}{ccccccc} (&p &\rightarrow &q) &\vee &\:\:(&p &\rightarrow &\overline{q}) \\ &&&&F \end{array} \]
Ora, ricordiamo la tavola di verità della disgiunzione inclusiva. Questa è falsa se ad esempio le singole proposizioni di partenza sono false. Quindi possiamo scrivere:
\[ \begin{array}{ccccccc} (&p &\rightarrow &q) &\vee &\:\:(&p &\rightarrow &\overline{q}) \\ &&&&F \\ &&F&&&&&F\end{array} \]
Ma come sappiamo, l’unico caso in cui un’implicazione materiale è falsa è che la premessa sia vera e la conseguenza sia falsa. Quindi:
\[ \begin{array}{ccccccc} (&p &\rightarrow &q) &\vee &\:\:(&p &\rightarrow &\overline{q}) \\ &&&&F \\ &&F&&&&&F \\ &V&&F&&&V&&F\end{array} \]
Ora attenzione, otteniamo che \( q \) deve essere falsa e la sua negazione \( \overline{q} \) deve essere falsa! Ciò è ovviamente impossibile. Quindi, ipotizzando che l’espressione logica assegnata è falsa abbiamo ottenuto un assurdo. Dunque, l’espressione è una tautologia.
Ancora una volta, perveniamo allo stesso risultato costruendo ed analizzando la tavola di verità dell’espressione logica:
Esercizio 3
Mostrare che la proposizione \( b:p \wedge \neg q \rightarrow p \wedge q \) è una conseguenza logica della proposizione \( a:\neg p \).
SOLUZIONE
Ricordiamo anzitutto che dire che una proposizione è una conseguenza logica dell’altra equivale a dire che le due proposizioni sono legate tra loro da una implicazione logica.
Considerato che la premessa implica la conseguenza, l’esercizio richiede di dimostrare la seguente implicazione logica:
\[ \neg p \Rightarrow (p \wedge \neg q \rightarrow p \wedge q) \]
Dobbiamo quindi dimostrare che dalla verità di \( a \) segue sempre la verità di \( b \) per ogni possibile valore di verità delle proposizioni \( p \) e \( q \).
Notiamo che \( p \) deve essere falsa poiché la proposizione \( \neg p \) deve essere vera. Quindi, possiamo già attribuire i seguenti valori di verità:
\[ \begin{array}&\neg &p &\Rightarrow (&p &\wedge &\neg &q &\rightarrow &p &\wedge &q) \\ V&F&V&F&&&&V&F\end{array} \]
Infatti, poiché vogliamo che \( \neg p \) sia vera, allora \( p \) deve essere falsa. Inoltre, affinché dalla verità di \( a \) discenda la verità di \( b \), l’implicazione materiale (l’ultima operazione in ordine di precedenza nella proposizione \( b \)) dovrà per forza essere vera.
Ora osserviamo che essendo \( p \) falsa, sicuramente le congiunzioni logiche saranno entrambe false:
\[ \begin{array}&\neg &p &\Rightarrow (&p &\wedge &\neg &q &\rightarrow &p &\wedge &q) \\ V&F&V&F&&&&V&F \\ &&&&F&&&&&F\end{array} \]
A questo punto notiamo che le congiunzioni logiche saranno comunque false sia per \( q \) vera, sia per \( q \) falsa. Quindi, per tutte le combinazioni dei valori di verità possibili per \( p \) e \( q \) abbiamo che alla verità della proposizione \( a \) corrisponde la verità della proposizione \( b \).
Per cui \( a \Rightarrow b \) e pertanto concludiamo che \( b \) è una conseguenza logica di \( a \):
\[ a \Rightarrow b \]
Verifichiamo il risultato ottenuto con la tavola di verità:
Come possiamo vedere, ogni volta che la proposizione \( a \) è vera, anche la proposizione \( b \) è vera. Dunque, \( a \Rightarrow b \).
Esercizio 4
Dire se la seguente espressione è una tautologia, una contraddizione o nessuna delle due:
\[ ((a \rightarrow b) \wedge b)\rightarrow a \]
Soluzione
Proviamo a vedere se l’espressione è una tautologia. Ipotizziamo allora che l’espressione sia una contraddizione è vediamo se otteniamo un assurdo.
Si tratta quindi di ipotizzare che l’ultima operazione in ordine di precedenza nell’espressione logica sia falsa:
\[ \begin{array}{} ((&a &\rightarrow &b) &\wedge &b)&\rightarrow &a \\ &&&&&&F \end{array} \]
Ma, affinché l’implicazione materiale \( ((a \rightarrow b) \wedge b)\rightarrow a \) sia falsa, necessariamente la proposizione \( (a \rightarrow b) \wedge b \) dovrà essere vera e la proposizione \( a \) dovrà essere falsa. Quindi:
\[ \begin{array}{} ((&a &\rightarrow &b) &\wedge &b)&\rightarrow &a \\ &&&&&&F \\ &&&&V&&&F&&& \end{array} \]
Ora, la congiunzione logica \( (a \rightarrow b) \wedge b \) sarà vera solo se \( a \rightarrow b \) è vera e \( b \) è vera:
\[ \begin{array}{} ((&a &\rightarrow &b) &\wedge &b)&\rightarrow &a \\ &&&&&&F \\ &&&&V&&&F&&& \\ &&V&&&V\end{array} \]
Ora, il fatto che \( a \rightarrow b \) è vera è compatibile con i valori di verità che già abbiamo attribuito ad \( a \) e a \( b \). Non abbiamo quindi nessun assurdo.
Dunque, poiché l’espressione può essere falsa per valori di verità certi di \( a \) e \( b \), questa non è sicuramente una tautologia.
Proviamo ora a vedere se l’espressione è una contraddizione. Per fare questo, dobbiamo ipotizzare che l’espressione sia vera e vedere se otteniamo un assurdo oppure no.
Cominciamo:
\[ \begin{array}{} ((&a &\rightarrow &b) &\wedge &b)&\rightarrow &a \\ &&&&&&V \end{array} \]
Affinché l’espressione sia vera, la congiunzione logica a sinistra e la proposizione \( a \) dovranno essere ad esempio entrambe vere:
\[ \begin{array}{} ((&a &\rightarrow &b) &\wedge &b)&\rightarrow &a \\ &&&&&&V \\ &&&&V &&& V\end{array} \]
D’altronde, la congiunzione logica è vera solo se \( a \rightarrow b \) è vera e anche \( b \) è vera:
\[ \begin{array}{} ((&a &\rightarrow &b) &\wedge &b)&\rightarrow &a \\ &&&&&&V \\ &&&&V &&& V \\ &&V&&&V \end{array} \]
E poiché sappiamo già che \( a \) è vera e \( b \) sono vere, ci limitiamo ad osservare che questi valori di verità vanno d’accordo con la richiesta che l’implicazione \( a \rightarrow b \) sia vera.
\[ \begin{array}{} ((&a &\rightarrow &b) &\wedge &b)&\rightarrow &a \\ &&&&&&V \\ &&&&V &&& V \\ &&V&&&V \\ &V&&V\end{array} \]
Dunque, poiché l’espressione assegnata risulta vera per valori certi delle proposizioni \( a \) e \( b \), questa non è nemmeno una contraddizione.
Concludiamo quindi che l’espressione di partenza non è né una tautologia, né una contraddizione.
Il risultato viene confermato dalla tavola di verità:
L’espressione non è infatti né sempre vera, né sempre falsa.
Esercizio 5
Concludiamo i nostri esercizi sulla logica (livello avanzato) con questo esercizio.
Verificare se le seguenti espressioni sono logicamente equivalenti:
\[ (\neg a ) \vee b; \qquad (\neg b) \vee a \]
SOLUZIONE
L’esercizio può essere risolto costruendo le tavole di verità per ciascuna espressione e verificando se quando è vera un’espressione è vera anche l’altra.
In alternativa, possiamo risolvere l’esercizio osservando che se due espressioni logiche sono equivalenti, allora la loro coimplicazione materiale costituisce una tautologia (cioè è sempre vera). Quindi, nel nostro caso ci chiediamo se la seguente espressione è una tautologia:
\[ (\neg a ) \vee b \leftrightarrow (\neg b) \vee a \]
Proviamo allora ad ipotizzare che la coimplicazione sia falsa e vediamo cosa succede ai valori di verità delle singole proposizioni \( a, b \).
\[ \begin{array}{ccccccccc}(&\neg &a ) &\vee &b &\leftrightarrow(&\neg &b) &\vee &a \\ &&&&& F\end{array} \]
Osserviamo che affinché la coimplicazione sia falsa, una delle due proposizioni nella coimplicazione dovrà essere falsa e l’altra vera. Ad esempio:
\[ \begin{array}{ccccccccc}(&\neg &a ) &\vee &b &\leftrightarrow(&\neg &b) &\vee &a \\ &&&&& F \\ &&&V&&&&&F\end{array} \]
Affinché si abbiano quei valori di verità per le disgiunzioni logiche, possiamo ipotizzare per le proposizioni \( a \) e \( b \) i seguenti valori di verità:
\[ \begin{array}{ccccccccc}(&\neg &a ) &\vee &b &\leftrightarrow(&\neg &b) &\vee &a \\ &&&&& F \\ &&&V&&&&&F \\ &V&F&&V&&F&V&&F \end{array} \]
Abbiamo trovato che tale coimplicazione non può essere una tautologia, poiché risulta falsa per valori certi delle proposizioni.
Concludiamo quindi che le due proposizioni di partenza non sono logicamente equivalenti e non abbiamo quindi tra loro una coimplicazione logica.
Le tavole di verità delle proposizioni confermano il risultato:
NOTA: supponiamo di aver risolto l’esercizio facendo differenti ipotesi sui valori di verità delle congiunzioni logiche. Ad esempio:
\[ \begin{array}{ccccccccc}(&\neg &a ) &\vee &b &\iff (&\neg &b) &\vee &a \\ &&&&& F \\ &&&V&&&&&\boxed{F }\\ &V&F&&F&&\boxed{V}&F&&F \end{array} \]
Osserviamo che in tal caso non otteniamo un assurdo. Semplicemente, significa che con le ipotesi fatte sui valori di verità delle proposizioni \( a,b \) la disgiunzione a destra non può essere falsa e quindi la coimplicazione risulta in realtà vera. In tal caso, si tratta di provare ad attribuire l’altro valore di verità a \( b \) e vedere se è ammissibile per le ipotesi fatte. Precisiamo che si ha l’assurdo solo quando si ottiene un valore contemporaneo di vero e di falso per una stessa proposizione.
Qui terminano gli esercizi sulla logica (livello avanzato) relativi alle espressioni logiche. Ciao a tutti! 🙂