In questa lezione considereremo unicamente espressioni logiche contenenti proposizioni chiuse. Di tali proposizioni sarà dunque possibile determinare in modo immediato il valore di verità.
Se già conoscete la teoria e vi occorrono esercizi, sono disponibili due esercitazioni:
- esercizi sulle espressioni logiche (livello base);
- esercizi sulle espressioni logiche (livello avanzato).
Vedremo inoltre delle particolari espressioni logiche: le tautologie e le contraddizioni. Infine, mostreremo la condizione per la quale due espressioni logiche possono dirsi logicamente equivalenti.
Espressioni logiche e tavola di verità
Consideriamo ad esempio l’espressione logica:
\[ a \wedge (b \vee c) \]
Il nostro obiettivo è determinare il valore di verità della proposizione che si ottiene da tutte le operazioni logiche indicate.
Ad esempio, ipotizziamo che \( a \) è vera, \( b \) è falsa e \( c \) è vera. Sotto queste ipotesi, vogliamo determinare il valore di verità dell’espressione assegnata.
Ora, le parentesi ci dicono l’ordine con il quale procedere, analogamente ad un’espressione algebrica. La prima operazione che dobbiamo fare è la disgiunzione inclusiva tra le proposizioni \( b \) e \( c \). Poiché la disgiunzione inclusiva è vera se almeno una delle due proposizioni è vera, si ha:
\[ r= b \vee c\qquad \text{VERA} \]
Il risultato della disgiunzione inclusiva tra \( b \) e \( c \) è una proposizione vera poiché \( b \) è falsa ma \( c \) è vera. Abbiamo indicato questa proposizione con \( r \) per comodità.
Ora, ci rimane da eseguire l’operazione di congiunzione logica tra la proposizione \( a \) e la proposizione \( r \):
\[ a \wedge (b \vee c)=a \wedge r \qquad \text{VERA} \]
Il risultato della congiunzione logica è una proposizione vera poiché \( a \) e \( r \) sono entrambe vere.
Possiamo dunque concludere che l’espressione logica assegnata è vera.
E’ sempre bene utilizzare le parentesi nelle espressioni logiche allo scopo di evitare interpretazioni errate. In ogni caso, l’ordine di precedenza tra le varie operazioni logiche è il seguente:
- negazione logica (NOT);
- congiunzione logica (AND);
- disgiunzione inclusiva o esclusiva (OR o XOR);
- implicazione materiale (es: \( a \rightarrow b \));
- coimplicazione materiale (es: \( a \leftrightarrow b \)).
NOTA: poiché qui facciamo uso delle tavole di verità, consideriamo implicazioni e coimplicazioni materiali e non logiche.
Tavola della verità di un’espressione logica
Supponiamo ora di non conoscere il valore di verità delle proposizioni \( a \), \( b \) e \( c \) e quindi di voler determinare il valore di verità della proposizione risultato dell’espressione logica nei vari casi possibili. In altre parole, vogliamo costruire una tavola di verità che ci indichi il valore di verità dell’espressione logica assegnata in funzione di tutti i possibili valori di verità delle proposizioni presenti nell’espressione stessa.
Indichiamo con \( n \) il numero di proposizioni presenti nell’espressione logica assegnata.
Per costruire la tabella abbiamo le seguenti regole.
- numero di colonne della tabella pari al numero delle proposizioni presenti nell’espressione logica, più un’altra colonna per i valori di verità dell’espressione logica. In tutto, \( n+1 \) colonne;
- numero di righe pari a \( 2^n \), più una riga in alto per indicare le proposizioni nell’espressione logica e la stessa espressione logica assegnata. In tutto, \( 2^n+1 \) righe;
- per assegnare tutti i possibili valori di verità alle singole proposizioni, si scrivono i valori di verità \( V \) e \( F \) lungo ciascuna colonna di ogni proposizione. Nella prima colonna scriveremo \( \dfrac{2^n}{2} \) volte il valore di verità \( V \), altrettante volte il valore di verità \( F \). Nella seconda colonna, scriveremo \( \dfrac{2^n}{4} \) volte il valore di verità \( V \), altrettante volte il valore di verità \( F \), ripetendo poi questa stessa sequenza fino a riempire la colonna. E così via per le altre colonne, dimezzando ogni volta il numero di valori di verità uguali consecutivi lungo la colonna.
ESEMPIO
Proviamo a scrivere la tavola di verità per la precedente espressione logica:
\[ a \wedge (b \vee c) \]
Osserviamo che abbiamo \( 3 \) differenti proposizioni. Quindi, la tabella dovrà essere formata da \( 3+1=4 \) colonne e \( 2^3+1=9 \) righe.
Per comodità, si può anche inserire una colonna aggiuntiva per il risultato della proposizione \( b \vee c \), in modo da rendere più agevole la valutazione dell’espressione logica.
Cominciamo dunque a scrivere la tabella:
Ora inseriamo tutti i possibili valori di verità per le proposizioni 🙂 Ricordiamo che abbiamo \( 3 \) differenti proposizioni, per cui \( \dfrac{2^n}{2}=\dfrac{2^3}{2}=4 \). Quindi, dovremo scrivere, nella prima colonna, quattro volte di fila \( V \) e quattro volte di fila \( F \):
Veniamo alla seconda colonna. Stavolta, dovremo scrivere due volte di fila \( V \) e due volte di fila \( F \), ripetendo questa esatta sequenza (\( VVFF \)) fino a riempire la colonna. Quindi:
Infine, inseriamo i valori di verità nella terza colonna, semplicemente alternando i due valori di verità \( V \) e \( F \) fino a riempire l’intera colonna:
Ora dobbiamo valutare la disgiunzione logica inclusiva (OR) tra le proposizioni \( b \) e \( c \), in ciascuna riga.
Ci rimane ora soltanto da valutare i valori di verità dell’espressione logica assegnata, per ciascuna riga. Ciò consiste nel valutare il risultato della congiunzione logica tra \( a \) e \( b \vee c \):
Abbiamo così costruito la tavola di verità dell’espressione assegnata.
Con le regole seguite, è possibile dimostrare che abbiamo previsto tutte le possibili combinazioni di vero e falso per le proposizioni date. 😉
Tautologie e contraddizioni
Una tautologia è un’espressione logica che è sempre vera a prescindere dai valori di verità delle singole proposizioni che la compongono.
Una contraddizione è invece un’espressione logica che è sempre falsa a prescindere dai valori di verità delle singole proposizioni che la compongono.
Mediante la costruzione della tavola di verità di un’espressione logica, è possibile verificare se essa è una tautologia oppure una contraddizione.
Ad esempio, consideriamo l’espressione:
\[ (a \rightarrow b) \vee (a \rightarrow \overline{b}) \]
Costruendo la tavola della verità (ad esempio con questo tool), notiamo che tale espressione è soddisfatta per qualsiasi valore di verità delle proposizioni che la compongono:
NOTA: ricordiamo che il simbolo \( \neg \) indica la negazione.
I valori di verità vengono qui indicati con \( 1 \) per vero, e \( 0 \) per falso. Il valore di verità dell’espressione è indicato in neretto. Come si può osservare, vengono anche indicati i valori di verità delle espressioni intermedie.
Dunque, poiché l’espressione è sempre vera, questa è una tautologia.
Consideriamo ora l’espressione:
\[ (\overline{a} \wedge \overline{b} ) \wedge a \]
Costruiamo la tavola di verità:
Poiché l’espressione è sempre falsa, questa costituisce una contraddizione.
Espressioni logiche equivalenti
Due espressioni logiche si dicono equivalenti se assumono uno stesso valore di verità per gli stessi valori di verità delle proposizioni che le compongono.
Ad esempio, proviamo a verificare se le seguenti espressioni logiche sono equivalenti:
\[ a \vee b; \qquad \overline{\overline{a} \wedge \overline{b}} \]
Per fare questo, possiamo costruire le tavole di verità di ciascuna espressione e confrontarne i valori di verità.
NOTA: ricordiamo che il simbolo \( \neg \) indica la negazione.
Dal confronto delle due tavole di verità vediamo che le due espressioni logiche sono equivalenti. Infatti, assegnati dei valori di verità delle proposizioni di partenza comuni ad entrambe le espressioni, quest’ultime forniscono come risultato lo stesso valore di verità.
Concludiamo questa lezione con una regola molto utile per gli esercizi.
regola (EQUIVALENZA LOGICA TRA PROPOSIZIONI)
Due proposizioni \( a \) e \( b \) si dicono logicamente equivalenti se e solo se la coimplicazione materiale \( a \leftrightarrow b \) è una tautologia (cioè, è sempre vera). In tal caso, si ha:
\[ a \iff b \]
ovvero \( a \) coimplica logicamente \( b \).
Così ad esempio, se riusciamo a dimostrare che almeno per una combinazione di possibili valori di verità per le proposizioni \( a,b \) la coimplicazione materiale \( a \leftrightarrow b \) è falsa, allora le due proposizioni non sono logicamente equivalenti.
Questa prima introduzione alle espressioni logiche è così conclusa. Nella prossima lezione vedremo le proprietà delle operazioni logiche. Queste sono molto utili per lavorare con le espressioni logiche. Ciao a tutti! 🙂