Tavole di verità

Una **tavola di verità** elenca **tutte le combinazioni possibili** di valori di verità delle variabili di un'espressione e mostra, in ogni riga, il valore dell'intera espressione. **Quante righe?** Ogni variabile può essere V (vero) o F (falso), quindi ogni nuova variabile raddoppia il numero di righe: $$\text{righe} = 2^n \quad (n = \text{numero di variabili})$$ Quindi 2 variabili richiedono $2^2 = 4$ righe e 3 variabili richiedono $2^3 = 8$ righe. **Costruire una tavola in 4 passi:** 1. Conta le variabili e scrivi $2^n$ righe vuote. 2. Riempi le colonne delle variabili in un ordine fisso: la prima colonna è per metà V e poi per metà F; ogni colonna successiva cambia il doppio delle volte; l'ultima colonna alterna V, F, V, F. 3. Aggiungi una **colonna ausiliaria** per ogni parte dell'espressione, partendo da quella più interna (un NOT su una sola variabile, poi le parentesi). 4. Combina le colonne ausiliarie per ottenere la colonna finale. **Esempio:** $P \land \neg Q$ | $P$ | $Q$ | $\neg Q$ | $P \land \neg Q$ | |:---:|:---:|:---:|:---:| | V | V | F | F | | V | F | V | **V** | | F | V | F | F | | F | F | V | F | La colonna finale dice tutto: questa espressione è vera in una sola riga, quando $P$ è vero e $Q$ è falso. **Come leggere la colonna finale:** - Solo V: l'espressione è una **tautologia** (sempre vera). - Solo F: è una **contraddizione** (sempre falsa). - Due espressioni con **la stessa colonna finale in ogni riga** sono **logicamente equivalenti**.

Una tavola con due variabili

Costruisci la tavola di verità di $P \lor \neg Q$.

Contare le righe: Ci sono 2 variabili, $P$ e $Q$, quindi servono $2^2 = 4$ righe = 4 righe

Riempire le colonne delle variabili: $P$: V, V, F, F (metà V, metà F). $Q$: V, F, V, F (alternate) = Tutte e 4 le combinazioni compaiono una volta

Aggiungere la colonna ausiliaria $\neg Q$: Inverti ogni valore di $Q$: V, F, V, F diventa F, V, F, V = $\neg Q$: F, V, F, V

Combinare con OR: Riga per riga: V OR F = V, V OR V = V, F OR F = F, F OR V = V = $P \lor \neg Q$: V, V, F, V

Answer: La colonna finale è V, V, F, V. L'espressione è falsa solo nella riga 3, dove $P$ è falso e $Q$ è vero.

Preparare tre variabili

Riempi le colonne delle variabili di una tavola di verità per $P$, $Q$ e $R$.

Contare le righe: 3 variabili, quindi $2^3 = 2 \times 2 \times 2 = 8$ righe = 8 righe

Riempire la colonna $P$: La metà di 8 è 4: quattro V, poi quattro F = $P$: V, V, V, V, F, F, F, F

Riempire la colonna $Q$: Cambia il doppio delle volte, a blocchi di 2 = $Q$: V, V, F, F, V, V, F, F

Riempire la colonna $R$: L'ultima colonna alterna a blocchi di 1 = $R$: V, F, V, F, V, F, V, F

Answer: Le 8 righe sono VVV, VVF, VFV, VFF, FVV, FVF, FFV, FFF. Ogni combinazione compare esattamente una volta e non ne manca nessuna.

Un'espressione con tre variabili

Costruisci la tavola di verità di $(P \land Q) \lor \neg R$. In quante righe è vera?

Preparare 8 righe: Usa l'ordine dell'esempio precedente: $P$ a blocchi di 4, $Q$ a blocchi di 2, $R$ alternata = 8 righe

Colonna ausiliaria $P \land Q$: AND è vero solo quando $P$ e $Q$ sono entrambi veri: righe 1 e 2 = $P \land Q$: V, V, F, F, F, F, F, F

Colonna ausiliaria $\neg R$: Inverti $R$: V, F, V, F, V, F, V, F diventa F, V, F, V, F, V, F, V = $\neg R$: F, V, F, V, F, V, F, V

Combinare con OR: Una riga è vera se almeno una colonna ausiliaria ha V: righe 1, 2, 4, 6, 8 = Finale: V, V, F, V, F, V, F, V

Contare le righe vere: Conta le V nella colonna finale = 5 righe

Answer: L'espressione è vera in 5 delle 8 righe e falsa nelle righe 3, 5 e 7.

Tautologia, contraddizione o nessuna delle due?

Classifica $P \lor \neg P$, $P \land \neg P$ e $(P \land Q) \lor \neg P$.

Trovare $\neg P$: Con una sola variabile ci sono $2^1 = 2$ righe. $P$: V, F, quindi $\neg P$: F, V = $\neg P$: F, V

Controllare $P \lor \neg P$: V OR F = V e F OR V = V = Solo V: tautologia

Controllare $P \land \neg P$: V AND F = F e F AND V = F = Solo F: contraddizione

Controllare $(P \land Q) \lor \neg P$: 4 righe. $P \land Q$: V, F, F, F. $\neg P$: F, F, V, V. OR: V, F, V, V = Misto: nessuna delle due

Answer: $P \lor \neg P$ è una tautologia, $P \land \neg P$ è una contraddizione e $(P \land Q) \lor \neg P$ non è nessuna delle due, perché è falsa nella riga 2.

Verificare l'equivalenza (De Morgan)

$\neg(P \land Q)$ e $\neg P \lor \neg Q$ sono equivalenti? E $\neg(P \land Q)$ e $\neg P \land \neg Q$?

Colonna finale di $\neg(P \land Q)$: $P \land Q$: V, F, F, F. La si inverte = F, V, V, V

Colonna finale di $\neg P \lor \neg Q$: $\neg P$: F, F, V, V. $\neg Q$: F, V, F, V. OR riga per riga = F, V, V, V

Confrontare ogni riga: F = F, V = V, V = V, V = V = Uguali in tutte e 4 le righe: equivalenti

Colonna finale di $\neg P \land \neg Q$: $\neg P$: F, F, V, V AND $\neg Q$: F, V, F, V = F, F, F, V: diversa nelle righe 2 e 3

Answer: $\neg(P \land Q) \equiv \neg P \lor \neg Q$ (una delle leggi di De Morgan). Ma $\neg(P \land Q)$ e $\neg P \land \neg Q$ non sono equivalenti: basta una sola riga diversa.

Una tavola di verità è il modo più affidabile per controllare un enunciato logico, perché non tralascia nessun caso: - **Programmazione**: prima di pubblicare una condizione come (socio OR coupon) AND NOT bloccato, i tester controllano ogni combinazione di input - **Elettronica**: gli ingegneri progettano circuiti con le tavole di verità e sostituiscono un circuito complicato con uno più semplice ed economico che fa la stessa cosa - **Sicurezza e allarmi**: un allarme con 4 sensori ha $2^4 = 16$ stati possibili, e in ognuno deve reagire correttamente - **Argomentazioni e dibattiti**: una tavola di verità mostra se due frasi dicono davvero la stessa cosa o si somigliano soltanto - **Enigmi e giochi**: gli enigmi logici si risolvono escludendo le righe che non possono essere vere Sai già come funzionano AND, OR e NOT da soli. Le tavole di verità ti permettono di combinarli in qualsiasi espressione restando sicuro del risultato.

Mistake: Scrivere troppo poche righe, per esempio 6 righe per 3 variabili

Why: Il numero di righe non è $2 \times n$. Ogni variabile raddoppia il numero di combinazioni, quindi 3 variabili danno $2 \times 2 \times 2 = 8$ righe.

Correct: Usa sempre $2^n$ righe: 4 per 2 variabili, 8 per 3 variabili, 16 per 4 variabili.

Mistake: Riempire le colonne delle variabili in ordine casuale

Why: Senza un metodo è facile scrivere due volte la stessa combinazione e dimenticarne un'altra. Così la tavola dà un verdetto sbagliato.

Correct: Segui lo schema fisso: prima colonna a blocchi di metà delle righe, ogni colonna successiva a blocchi lunghi la metà, ultima colonna alternata V, F.

Mistake: Trattare $\neg P \land Q$ come se fosse $\neg(P \land Q)$

Why: Senza parentesi, NOT si applica solo alla variabile subito dopo. La versione con le parentesi inverte il risultato dell'intero AND.

Correct: Crea una colonna ausiliaria esattamente per ciò a cui si applica NOT: solo $\neg P$, oppure prima $P \land Q$ e poi la sua negazione.

Mistake: Dire che due espressioni sono equivalenti dopo averne controllato solo alcune righe

Why: Due espressioni possono coincidere in parecchie righe e differire comunque in una. $\neg(P \land Q)$ e $\neg P \land \neg Q$ coincidono nelle righe 1 e 4, ma non nelle righe 2 e 3.

Correct: Confronta le colonne finali in ogni singola riga. Equivalenti significa identiche in tutte le $2^n$ righe.

Sistemi di allarme

Gli ingegneri della sicurezza elencano ogni stato dei sensori per essere sicuri che l'allarme reagisca correttamente in ogni caso.

Un allarme con 3 sensori sulle porte ha $2^3 = 8$ stati, da tutte le porte chiuse a tutte le porte aperte.

Testare il software

I programmatori testano una condizione con ogni combinazione di input, e questa è proprio una tavola di verità.

Una regola di accesso (password corretta AND NOT bloccato) richiede $2^2 = 4$ casi di test per essere verificata del tutto.

Semplificare i circuiti

Se due circuiti hanno la stessa tavola di verità, gli ingegneri possono usare quello con meno componenti o componenti più economici.

Le leggi di De Morgan permettono di sostituire un NOT-AND con un OR di due NOT senza cambiare ciò che fa il circuito.

Una tavola di verità elenca ogni combinazione di valori di verità e il valore dell'espressione in ogni riga

Con $n$ variabili la tavola ha $2^n$ righe: 4 con 2 variabili, 8 con 3 variabili

Riempi le colonne delle variabili in un ordine fisso: prima blocchi di metà delle righe, l'ultima colonna alternata V, F

Usa colonne ausiliarie per ogni parte dell'espressione, partendo da quella più interna

Solo V nella colonna finale significa tautologia, solo F significa contraddizione

Due espressioni sono equivalenti quando le loro colonne finali coincidono in ogni riga

Q: Perché ogni nuova variabile raddoppia le righe?

A: Ogni riga esistente si può continuare con la nuova variabile V oppure F. Così ogni riga si divide in due: 2 righe diventano 4, 4 diventano 8 e così via, il che dà $2^n$.

Q: L'ordine delle righe è importante?

A: Qualsiasi ordine va bene, purché ogni combinazione compaia esattamente una volta. L'ordine standard (che parte da tutte V) rende facile controllare e confrontare le tavole. Alcuni libri partono invece da F; le righe sono le stesse, solo elencate al contrario. Le tavole interattive di questa lezione usano l'ordine standard.

Q: Come si chiama un'espressione che non è né una tautologia né una contraddizione?

A: Si chiama **contingenza**: il suo valore dipende dagli input. La maggior parte delle espressioni di tutti i giorni, come $P \land Q$, sono contingenze.

Q: Servono sempre le colonne ausiliarie?

A: Non sono obbligatorie, ma evitano la maggior parte degli errori. Con l'esercizio puoi unire piccoli passaggi a mente, ma con 3 variabili o parentesi dentro parentesi le colonne ausiliarie sono il modo più sicuro.

Esci dalla presentazione

Tavole di verità

1 / 14

Logica e Insiemi / Logica booleana

Tavole di verità

Impara a costruire passo dopo passo la tavola di verità di un'espressione composta e a usarla per trovare tautologie, contraddizioni ed espressioni equivalenti.

Intermedio25 min

Usa i tasti freccia o la barra spaziatrice per navigare