Mostreremo in particolare due metodi risolutivi per questi esercizi sulle tautologie e contraddizioni. Nel primo metodo, costruiremo la tavola di verità dell’espressione logica e controlleremo se è sempre vera (tautologia), sempre falsa (contraddizione), oppure è una generica espressione logica (a volte vera, a volte falsa). Nel secondo metodo, utilizzeremo una tecnica di dimostrazione per assurdo. In particolare, volendo dimostrare che un’espressione logica è una tautologia, proveremo ad ipotizzare che è falsa. Se così facendo incontreremo un assurdo (cioè una proposizione che deve essere allo stesso tempo vera e falsa), allora diremo che la proposizione non può essere mai falsa e quindi è sempre vera, cioè una tautologia.
Ricordiamo come ultima precisazione che con i termini “sempre vera” e “sempre falsa” intendiamo che l’espressione logica data assume lo stesso valore di verità a prescindere dalla combinazione di valori di verità per la proposizione di partenza. Ad esempio, un’espressione logica è una tautologia se risulta sempre vera comunque si attribuiscano i valori di vero e falso alle proposizioni logiche di partenza.
Precisiamo che le proposizioni presenti nelle espressioni sono chiuse. Ed ora, cominciamo 🙂
Esercizio 1
Dimostrare che la seguente espressione logica è una tautologia.
\[ (a \wedge a ) \rightarrow a \]
SOLUZIONE
Qui già sappiamo che l’espressione logica è una tautologia. Il nostro compito è solo dimostrarlo.
PRIMO METODO
Il primo metodo risolutivo consiste nello scrivere la tavola di verità dell’espressione logica e controllare che quest’ultima sia sempre vera.
Poiché abbiamo una sola proposizione, avremo bisogno di \( 2^1=2 \) righe per i valori di verità. Quanto alle colonne, conviene usare tre colonne. In particolare, una colonna per il valore di verità di \( a \), una per il valore di verità dell’operazione intermedia \( (a \wedge a) \)) e infine una per il valore di verità dell’espressione logica data.
Abbiamo:
Come possiamo vedere, l’espressione logica è sempre vera per cui è una tautologia.
SECONDO METODO
NOTA: questo secondo metodo in genere non viene utilizzato al primo anno delle scuole superiori. Può essere di interesse per gli studenti della terza superiore in poi ma più che altro è destinato agli studenti universitari. Tuttavia, questa è solo una linea guida – regolatevi in base al vostro programma scolastico. A mio parere comunque, imparare questo metodo non potrà che essere utile per tutti 😉
Cominciamo con lo svolgimento. Proviamo ad ipotizzare che l’espressione logica data sia falsa. Ciò è ovviamente impossibile se l’espressione data è una tautologia. Ma allora, ipotizzando che l’espressione sia falsa dovremo ottenere un qualcosa di impossibile, cioè un assurdo. In particolare, se così facendo arriveremo alla conclusione assurda che una delle proposizioni di partenza debba essere contemporaneamente vera e falsa, allora vorrà dire che l’espressione logica data non potrà mai essere falsa. Di conseguenza, l’espressione logica dovrà essere sempre vera e sarà quindi una tautologia.
Cominciamo allora ipotizzando che l’espressione data è falsa, cioè che l’implicazione materiale è falsa. Ciò ha senso poiché l’implicazione materiale è l’ultima operazione logica in ordine di precedenza nell’espressione. Dal suo valore di verità dipende quindi il valore di verità di tutta l’espressione logica.
\[ \begin{array}{ccccc} (&a &\wedge & a) & \rightarrow &a \\ &&&&F\end{array} \]
Ora, se è falsa l’implicazione materiale, la congiunzione logica dovrà per forza essere vera e la proposizione \( a \) dovrà essere per forza falsa. Ricordiamo infatti che l’implicazione materiale è falsa soltanto quando la premessa è vera e la conseguenza è falsa.
Scriviamo quindi i rispettivi valori di verità:
\[ \begin{array}{ccccc} (&a &\wedge & a) & \rightarrow &a \\ &&&&F \\ &&V&&&F\end{array} \]
Ora, osserviamo che affinché la congiunzione \( a \wedge a \) sia vera, la proposizione \( a \) non può che essere vera:
\[ \begin{array}{ccccc} (&a &\wedge & a) & \rightarrow &a \\ &&&&F \\ &&V&&&\boxed{F}\\ &\boxed{V}&&\boxed{V}\end{array} \]
Ma, come evidenziato, abbiamo un assurdo! La proposizione \( a \) non può essere contemporaneamente vera e falsa! Ciò significa che non possiamo ipotizzare che l’espressione logica data sia falsa, perché ciò ci porta ad una cosa impossibile, un assurdo. Quindi, l’espressione logica data non può essere mai falsa. Allora, deve essere sempre vera. In conclusione, è una tautologia.
Osserviamo che abbiamo dimostrato per assurdo che l’espressione logica data è una tautologia. Mettiamo da parte nel nostro bagaglio di informazioni questo modo di procedere, perché poi in Analisi capiterà più di una volta di dover dimostrare un teorema per assurdo. Ma avremo già un bonus poiché il meccanismo sarà praticamente questo 😉
Esercizio 2
Verificare che la seguente espressione logica è una tautologia:
\[ (a \rightarrow b) \vee (b \rightarrow a) \]
SOLUZIONE
Procediamo con i soliti due metodi. Nel primo metodo, costruiremo la tavola di verità e verificheremo se l’espressione logica è sempre vera. Nel secondo metodo, proveremo ad ipotizzare che l’espressione data è falsa e controlleremo se otterremo un assurdo.
PRIMO METODO – TAVOLA DI VERITA’
Costruiamo la tavola di verità dell’espressione logica data:
Come possiamo vedere, l’espressione logica data è vera per qualunque combinazione di valori di verità delle proposizioni di partenza \( a,b \). Quindi, l’espressione logica è una tautologia.
SECONDO METODO – DIMOSTRAZIONE PER ASSURDO
Ipotizziamo che l’espressione logica sia falsa. Ciò corrisponde ad ipotizzare che l’ultima operazione in ordine di precedenza (cioè la disgiunzione) sia falsa.
Otteniamo:
\[ \begin{array}{cccccccc} (&a &\rightarrow &b) & \vee ( & b & \rightarrow &a) \\ &&&&F \\ &&F&&&&F \\ &\boxed{V}&&\boxed{F}&&\boxed{V}&&\boxed{F}\end{array} \]
Abbiamo un assurdo: \(a, b \) contemporaneamente false e vere Ciò è ovviamente impossibile per cui l’espressione logica assegnata non può mai essere falsa. Allora, è una tautologia.
Esercizio 3
Dire se la seguente espressione logica è una tautologia, una contraddizione o nessuna delle due.
\[ (a \wedge b) \wedge (\neg a \vee \neg b) \]
SOLUZIONE
La differenza rispetto agli altri esercizi su tautologie e contraddizioni svolti finora è che adesso non abbiamo nessun indizio. Quindi, come vedremo, nell’applicazione del secondo metodo potremmo aver bisogno di fare due diverse ipotesi.
METODO 1 – TAVOLA DI VERITA’
L’espressione data è una contraddizione poiché è sempre falsa.
METODO 2 – DIMOSTRAZIONE PER ASSURDO
Proviamo a vedere se l’espressione è una tautologia. Ipotizziamo per essa una valore di verità falso:
\[ \begin{array}{ccccccccc}(&a &\wedge &b) &\wedge (&\neg &a &\vee &\neg &b) \\ &&&&F\\ &&F&&&&&V \\ &F&&F&&V&&&V \\ &&&&&&F&&&F \end{array} \]
Vediamo che non otteniamo alcun assurdo. L’espressione logica assegnata è falsa per valori certi delle proposizioni logiche di partenza. In particolare, l’espressione è falsa per \( a, b \) false. Quindi, essendo almeno in un caso falsa, l’espressione data non è certamente una tautologia.
Proviamo allora a vedere se questa è una contraddizione. Il meccanismo sarà simile, ma stavolta dovremo ipotizzare che l’espressione logica assegnata è vera. Se otterremo un assurdo, allora avremo dimostrato che l’espressione data non può mai essere vera e quindi è una contraddizione (sempre falsa).
\[ \begin{array}{ccccccccc}(&a &\wedge &b) &\wedge (&\neg &a &\vee &\neg &b) \\ &&&&V\\ &&V&&&&&V \\ &\boxed{V}&&\boxed{V}&&V&&&V \\ &&&&&&\boxed{F}&&&\boxed{F} \end{array} \]
Come possiamo vedere, abbiamo ottenuto un assurdo. Allora l’espressione logica data non può mai essere vera. Di conseguenza è una contraddizione (cioè sempre falsa).
Se non avessimo ottenuto un assurdo in nessuno dei due casi, allora avremmo concluso che l’espressione data non sarebbe stata né una tautologia, né una contraddizione. Quindi, se ci capita una tale situazione questa è la conclusione da trarre.
E’ importante osservare che avremmo potuto svolgere molto rapidamente questo esercizio utilizzando una delle leggi di De Morgan. Abbiamo dunque anche un terzo possibile svolgimento in realtà.
TERZO METODO – LEGGI DI DE MORGAN
Osserviamo l’espressione:
\[ (a \wedge b) \wedge (\neg a \vee \neg b) \]
Il termine a destra può essere riscritto utilizzando una delle leggi di De Morgan. In particolare. poiché per la legge di De Morgan della congiunzione:
\[ \neg (a \wedge b) = \neg a \vee \neg b \]
abbiamo ovviamente, “rovesciando” l’uguaglianza:
\[ \neg a \vee \neg b=\neg (a \wedge b) \]
Quindi, possiamo riscrivere l’espressione logica data come:
\[ (a \wedge b) \wedge \neg(a \wedge b) \]
Ma a questo punto è evidente che abbiamo una congiunzione logica tra una proposizione \( (a \wedge b) \) e la sua negata (\( \neg(a \wedge b) \)). Ed è ovviamente impossibile che entrambe siano vere. Per cui la proposizione data è per forza una contraddizione.
Qui concludiamo questa lezione relativa agli esercizi su tautologie e contraddizioni. Per chi vuole approfondire, sono anche disponibili degli esercizi su tautologie e contraddizioni di livello avanzato. Buono studio a tutti, ciao! 🙂