L'ordine delle righe è importante?

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.

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

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

Servono sempre le colonne ausiliarie?

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.

Risorse per insegnanti

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 minLezione

Scheda da stampare

Definizione

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.

Prova subito

Quante righe ha una tavola di verità con 3 variabili?

Esempi svolti

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

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

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

Errori comuni

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

Perché è sbagliato: 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.

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

Riempire le colonne delle variabili in ordine casuale

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

Corretto: 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.

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

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

Corretto: 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.

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

Perché è sbagliato: 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.

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

Visuale interattivo

Tabella di verità

EspressioneP ∧ Q ∨ ¬R

P	Q	R	P ∧ Q	¬R	P ∧ Q ∨ ¬R
V	V	V	V	F	V
V	V	F	V	V	V
V	F	V	F	F	F
V	F	F	F	V	V
F	V	V	F	F	F
F	V	F	F	V	V
F	F	V	F	F	F
F	F	F	F	V	V

V= VeroF= Falso

Tabella di verità

EspressioneP ∨ ¬Q

P	Q	P ∨ ¬Q
V	V
V	F
F	V
F	F

V= VeroF= Falso

Sandbox interattivo

Calcolatrice di espressioni

Prova questi:

Cronologia

Ancora nessun calcolo

Esercizi pratici

18 esercizi

Problema 1 di 18

Facile

Quante righe ha una tavola di verità con 3 variabili?

Perché è importante

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.

Applicazioni nel mondo reale

Sistemi di allarme

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

Esempio:

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

1Provaci tu stesso

L'allarme di una casa ha 4 sensori, e ognuno è acceso (V) o spento (F). L'allarme suona se almeno un sensore è acceso (OR).

Quante righe ha la tavola di verità, e in quante di esse suona l'allarme?

Passo 1: Scrivi l'espressione matematica

Scrivi il numero di righe come potenza di 2:

Testare il software

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

Esempio:

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

2Provaci tu stesso

Un negozio online fa uno sconto se vale $(M \lor C) \land \neg B$ , dove $M$ = è socio, $C$ = ha un coupon, $B$ = l'account è bloccato.

In quante combinazioni di input il cliente ottiene lo sconto?

Passo 1: Scrivi l'espressione matematica

Scrivi il numero di casi di test come potenza di 2:

Semplificare i circuiti

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

Esempio:

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

3Provaci tu stesso

Il circuito A calcola $\neg(P \lor Q)$ . Il circuito B calcola $\neg P \land \neg Q$ .

I due circuiti danno sempre la stessa uscita?

Passo 1: Scrivi l'espressione matematica

Scrivi il numero di righe come potenza di 2:

Punti chiave

1Una tavola di verità elenca ogni combinazione di valori di verità e il valore dell'espressione in ogni riga
2Con $n$ variabili la tavola ha $2^n$ righe: 4 con 2 variabili, 8 con 3 variabili
3Riempi le colonne delle variabili in un ordine fisso: prima blocchi di metà delle righe, l'ultima colonna alternata V, F
4Usa colonne ausiliarie per ogni parte dell'espressione, partendo da quella più interna
5Solo V nella colonna finale significa tautologia, solo F significa contraddizione
6Due espressioni sono equivalenti quando le loro colonne finali coincidono in ogni riga

Domande frequenti

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

Glossario

Tavola di verità: Una tabella che mostra il valore di un'espressione per ogni combinazione delle sue variabili
Espressione composta: Un'espressione formata da variabili e operatori, come $(P \land Q) \lor \neg R$
Colonna ausiliaria: Una colonna in più per una parte dell'espressione, usata per costruire passo dopo passo la colonna finale
Tautologia: Un'espressione vera in ogni riga, come $P \lor \neg P$
Contraddizione: Un'espressione falsa in ogni riga, come $P \land \neg P$
Logicamente equivalenti: Due espressioni con lo stesso valore in ogni riga, si scrive con $\equiv$

Scheda formule

Numero di righe

\text{righe} = 2^n

$n$ è il numero di variabili: $2^2 = 4$, $2^3 = 8$, $2^4 = 16$

Tautologia

P \lor \neg P

Sempre vera: la colonna finale contiene solo V

Contraddizione

P \land \neg P

Sempre falsa: la colonna finale contiene solo F

Leggi di De Morgan

\neg(P \land Q) \equiv \neg P \lor \neg Q, \quad \neg(P \lor Q) \equiv \neg P \land \neg Q

Due equivalenze che puoi dimostrare con una tavola di verità

Altro su questo argomento

Definizione

Esempi svolti

Errori comuni

Visuale interattivo

Tabella di verità

Tabella di verità

Sandbox interattivo

Calcolatrice di espressioni

Cronologia

Esercizi pratici

Perché è importante

Applicazioni nel mondo reale

Sistemi di allarme

Testare il software

Semplificare i circuiti

Punti chiave

Domande frequenti

Glossario

Scheda formule

Numero di righe

Tautologia

Contraddizione

Leggi di De Morgan

Altro su questo argomento

Introduzione alla logica booleana

Enunciati veri e falsi

L'operazione AND

L'operazione OR