Valutare con 1 e 0

Valuta $A \land \neg B$ per $A = 1$ e $B = 0$.

Sostituire i valori: Sostituisci $A$ con $1$ e $B$ con $0$ = $1 \land \neg 0$

Prima NOT: $\neg 0 = 1$ = $1 \land 1$

Poi AND: Entrambi i valori sono $1$, quindi AND dà $1$ = $1$

Answer: $A \land \neg B = 1$ (vero) per $A = 1$, $B = 0$.

AND prima di OR

Valuta $A \lor B \land C$ per $A = 1$, $B = 0$, $C = 0$.

Sostituire i valori: Sostituisci ogni lettera con il suo valore = $1 \lor 0 \land 0$

AND prima di OR: $0 \land 0 = 0$ = $1 \lor 0$

Poi OR: Almeno un valore è $1$ = $1$

Confronto con il calcolo da sinistra a destra: Da sinistra a destra si otterrebbe $(1 \lor 0) \land 0 = 1 \land 0 = 0$ = Un risultato diverso e sbagliato

Answer: $A \lor B \land C = 1$. Calcolando da sinistra a destra si ottiene $0$, che è sbagliato perché AND viene prima di OR.

Le parentesi cambiano il risultato

Valuta $\neg(A \land B)$ e $\neg A \land B$ per $A = 0$ e $B = 0$.

Prima espressione: prima la parentesi: $A \land B = 0 \land 0 = 0$ = $\neg(0)$

Poi NOT: $\neg 0 = 1$ = $\neg(A \land B) = 1$

Seconda espressione: NOT si applica solo ad $A$: $\neg A = \neg 0 = 1$ = $1 \land B$

Poi AND: $1 \land 0 = 0$ = $\neg A \land B = 0$

Answer: $\neg(A \land B) = 1$ ma $\neg A \land B = 0$. Sono le parentesi a decidere a che cosa si applica NOT.

Una tavola di verità completa e l'equivalenza

Costruisci la tavola di verità di $A \lor \neg A \land B$ e confrontala con $A \lor B$.

Contare le righe: 2 variabili, quindi $2^2 = 4$ righe = $AB$: 00, 01, 10, 11

Colonna ausiliaria $\neg A$: Inverti $A$: 0, 0, 1, 1 = $\neg A$: 1, 1, 0, 0

Colonna ausiliaria $\neg A \land B$ (AND prima di OR): $\neg A$: 1, 1, 0, 0 AND $B$: 0, 1, 0, 1 = 0, 1, 0, 0

Colonna finale $A \lor (\neg A \land B)$: $A$: 0, 0, 1, 1 OR 0, 1, 0, 0 = 0, 1, 1, 1

Colonna di $A \lor B$ e confronto: $A \lor B$: 0, 1, 1, 1 = Uguali in tutte e 4 le righe

Answer: Entrambe le colonne finali sono 0, 1, 1, 1, quindi $A \lor \neg A \land B$ e $A \lor B$ sono equivalenti: l'espressione più corta fa lo stesso lavoro.

Tre variabili: dove vanno le parentesi

Costruisci le tavole di verità di $A \land (B \lor C)$ e di $A \land B \lor C$. Sono equivalenti?

Contare le righe: 3 variabili, quindi $2^3 = 8$ righe: 000, 001, 010, 011, 100, 101, 110, 111 = 8 righe

Colonna ausiliaria $B \lor C$: $B \lor C$ vale $0$ solo quando $B = C = 0$ = 0, 1, 1, 1, 0, 1, 1, 1

Colonna finale $A \land (B \lor C)$: $A$ vale $1$ solo nelle ultime 4 righe = 0, 0, 0, 0, 0, 1, 1, 1

Colonna finale $A \land B \lor C = (A \land B) \lor C$: $A \land B$: 0, 0, 0, 0, 0, 0, 1, 1. OR con $C$: 0, 1, 0, 1, 0, 1, 0, 1 = 0, 1, 0, 1, 0, 1, 1, 1

Confrontare le colonne: Sono diverse nella riga 2 (001) e nella riga 4 (011) = Non equivalenti

Answer: Le espressioni non sono equivalenti: per $A = 0$, $B = 0$, $C = 1$ la prima dà $0$ e la seconda dà $1$. Basta una sola riga diversa.

Mistake: Calcolare da sinistra a destra: $1 \lor 0 \land 0 = (1 \lor 0) \land 0 = 0$

Why: AND viene prima di OR, così come la moltiplicazione viene prima dell'addizione. Senza parentesi, la parte AND si calcola per prima.

Correct: $1 \lor 0 \land 0 = 1 \lor (0 \land 0) = 1 \lor 0 = 1$

Mistake: Applicare NOT a tutto ciò che segue: leggere $\neg A \land B$ come $\neg(A \land B)$

Why: Senza parentesi, NOT si applica solo alla variabile che lo segue direttamente.

Correct: $\neg A \land B = (\neg A) \land B$. Per negare tutto l'AND, scrivi $\neg(A \land B)$.

Mistake: Sommare come se fossero numeri: $1 \lor 1 = 2$

Why: Un'espressione booleana può valere solo $1$ o $0$. OR chiede se almeno un valore è $1$, non li conta.

Correct: $1 \lor 1 = 1$, $1 \land 1 = 1$ e $\neg 1 = 0$. Il risultato è sempre $1$ o $0$.

Mistake: Dichiarare equivalenti due espressioni dopo aver provato solo uno o due ingressi

Why: $A \land (B \lor C)$ e $A \land B \lor C$ hanno lo stesso valore in 6 righe su 8, eppure sono diverse.

Correct: Costruisci la tavola completa con $2^n$ righe e confronta ogni riga. Una riga diversa significa: non equivalenti.

Regole in un programma

I programmatori scrivono le regole come espressioni booleane e provano ogni combinazione di ingressi prima di mettere online il programma.

Un'attrazione del luna park ti fa salire se $T \land (H \lor P)$: $T$ = hai il biglietto, $H$ = sei abbastanza alto, $P$ = sale con te un genitore.

Filtri antispam

Un programma di posta decide con un'espressione booleana se un messaggio finisce nella cartella spam.

Un filtro segna un'e-mail come spam se $L \lor S \land \neg K$: $L$ = il mittente è in una lista nera, $S$ = parole sospette, $K$ = il mittente è nei tuoi contatti.

Regole della casa intelligente

Due espressioni diverse possono comandare un dispositivo esattamente allo stesso modo. Una tavola di verità mostra quando una regola lunga si può sostituire con una corta.

Una luce da giardino usa la regola $M \lor M \land N$: $M$ = movimento rilevato, $N$ = è notte.

Q: Perché AND viene prima di OR?

A: È una convenzione, come la moltiplicazione prima dell'addizione. Con 0 e 1, AND si comporta come la moltiplicazione ($1 \times 0 = 0$), e OR viene spesso paragonato all'addizione, quindi lo stesso ordine sembra naturale.

Q: Posso semplicemente mettere parentesi dappertutto?

A: Sì. Parentesi che seguono la precedenza degli operatori non cambiano mai il valore e rendono l'espressione più facile da leggere. $A \lor (B \land C)$ è uguale a $A \lor B \land C$, ma la prima scrittura mostra l'ordine a colpo d'occhio.

Q: 1 e 0 sono la stessa cosa di vero e falso?

A: Sì. 1 sta per vero e 0 per falso. I computer usano 1 e 0 perché memorizzano tutto come bit. Anche le tavole interattive di questa lezione usano 1 e 0.

Q: Esiste un modo più rapido della tavola di verità per mostrare che due espressioni sono equivalenti?

A: Sì. L'algebra di Boole ha delle leggi (come le leggi di De Morgan) che trasformano un'espressione in un'altra passo dopo passo. Le studierai nella lezione Algebra di Boole. Una tavola di verità è più lenta, ma funziona sempre.