Leggi di identità e di annullamento

Semplifica $(A \land 1) \lor (B \land 0)$.

Applica la legge di identità alla prima parentesi: $A \land 1 = A$, perché AND con vero non cambia niente = $A \lor (B \land 0)$

Applica la legge di annullamento alla seconda parentesi: $B \land 0 = 0$, perché AND con falso è sempre falso = $A \lor 0$

Applica di nuovo la legge di identità: $A \lor 0 = A$, perché OR con falso non cambia niente = $A$

Answer: $(A \land 1) \lor (B \land 0) = A$. Il valore di $B$ non conta per niente.

Dimostrare la legge di assorbimento

Dimostra con altre leggi che $A \lor (A \land B) = A$.

Scrivi $A$ come $A \land 1$ (legge di identità): $A \lor (A \land B) = (A \land 1) \lor (A \land B)$ = Entrambe le parentesi iniziano con $A$

Raccogli $A$ (proprietà distributiva, letta da destra a sinistra): $(A \land 1) \lor (A \land B) = A \land (1 \lor B)$ = $A \land (1 \lor B)$

Applica la proprietà commutativa e la legge di annullamento: $1 \lor B = B \lor 1 = 1$ = $A \land 1$

Applica la legge di identità: $A \land 1 = A$ = $A$

Answer: $A \lor (A \land B) = A$. A parole: se $A$ è vera, tutto l'OR è vero, e se $A$ è falsa, anche $A \land B$ è falsa. In entrambi i casi il risultato è uguale ad $A$.

De Morgan e doppia negazione

Semplifica $\neg(\neg A \land B)$ e controlla il risultato con una tavola di verità.

Applica la legge di De Morgan: Il NOT di un AND diventa un OR delle negazioni: $\neg(\neg A \land B) = \neg\neg A \lor \neg B$ = $\neg\neg A \lor \neg B$

Applica la doppia negazione: $\neg\neg A = A$ = $A \lor \neg B$

Costruisci la colonna dell'espressione iniziale: Righe $(A, B)$ = 00, 01, 10, 11: $\neg A \land B$ vale 0, 1, 0, 0, quindi $\neg(\neg A \land B)$ vale 1, 0, 1, 1 = 1, 0, 1, 1

Costruisci la colonna del risultato: $\neg B$ vale 1, 0, 1, 0, quindi $A \lor \neg B$ vale 1, 0, 1, 1 = Stessa colonna in ogni riga

Answer: $\neg(\neg A \land B) = A \lor \neg B$. Le due colonne coincidono in tutte e 4 le righe, quindi la semplificazione è corretta.

Raccogliere e legge del complemento

Semplifica $(A \land B) \lor (A \land \neg B)$ e controlla con una tavola di verità.

Raccogli $A$ (proprietà distributiva): $(A \land B) \lor (A \land \neg B) = A \land (B \lor \neg B)$ = $A \land (B \lor \neg B)$

Applica la legge del complemento: $B \lor \neg B = 1$, perché $B$ è vera oppure falsa = $A \land 1$

Applica la legge di identità: $A \land 1 = A$ = $A$

Controlla con una tavola di verità: Righe $(A, B)$ = 00, 01, 10, 11: $A \land B$ vale 0, 0, 0, 1 e $A \land \neg B$ vale 0, 0, 1, 0, quindi l'OR vale 0, 0, 1, 1 = Come la colonna $A$: 0, 0, 1, 1

Answer: $(A \land B) \lor (A \land \neg B) = A$. Un circuito con 4 porte (due AND, un NOT, un OR) diventa un semplice filo.

Meno porte in un circuito

Un circuito calcola $\neg(A \lor B) \lor (\neg A \land B)$. Semplificalo e conta le porte risparmiate (una porta per ogni $\land$, $\lor$ e $\neg$).

Conta le porte dell'espressione iniziale: Operatori: $\neg$ e $\lor$ nella prima parte, $\neg$ e $\land$ nella seconda, e l'$\lor$ al centro = 5 porte

Applica la legge di De Morgan alla prima parte: $\neg(A \lor B) = \neg A \land \neg B$ = $(\neg A \land \neg B) \lor (\neg A \land B)$

Raccogli $\neg A$ (proprietà distributiva): $(\neg A \land \neg B) \lor (\neg A \land B) = \neg A \land (\neg B \lor B)$ = $\neg A \land (\neg B \lor B)$

Applica le leggi del complemento e di identità: $\neg B \lor B = 1$ e $\neg A \land 1 = \neg A$ = $\neg A$

Conta di nuovo le porte: $\neg A$ richiede una sola porta NOT: $5 - 1 = 4$ = 4 porte risparmiate

Answer: Il circuito è equivalente a $\neg A$: una porta NOT invece di 5 porte. Controllo: l'espressione iniziale è vera esattamente nelle righe 00 e 01, cioè nelle righe con $A = 0$.

Mistake: Scrivere $\neg(A \land B) = \neg A \land \neg B$

Why: La legge di De Morgan cambia l'operatore oltre a negare le variabili. Prova con $A = 1$, $B = 0$: il lato sinistro vale $\neg 0 = 1$, il lato destro $0 \land 1 = 0$.

Correct: Spezza la barra e cambia il segno: $\neg(A \land B) = \neg A \lor \neg B$ e $\neg(A \lor B) = \neg A \land \neg B$.

Mistake: Usare le regole dell'algebra ordinaria, come $A \lor A = 2A$ o $A \land A = A^2$

Why: Le variabili booleane valgono solo 0 o 1, e $1 \lor 1$ è 1, non 2. Ripetere una variabile non aggiunge niente di nuovo.

Correct: Usa l'idempotenza: $A \lor A = A$ e $A \land A = A$.

Mistake: Leggere $A \lor B \land C$ come $(A \lor B) \land C$

Why: AND si valuta prima di OR, proprio come la moltiplicazione prima dell'addizione. Con $A = 1$, $B = 0$, $C = 0$ il valore corretto è $1 \lor 0 = 1$, ma la lettura sbagliata dà $1 \land 0 = 0$.

Correct: Metti le parentesi prima di applicare una legge: $A \lor B \land C = A \lor (B \land C)$.

Mistake: Applicare la legge del complemento a due variabili diverse, come $A \land \neg B = 0$

Why: La legge del complemento funziona solo con una variabile e la sua stessa negazione. Con $A = 1$, $B = 0$: $A \land \neg B = 1 \land 1 = 1$, non 0.

Correct: Cerca la stessa lettera: $A \land \neg A = 0$ e $B \lor \neg B = 1$, ma $A \land \neg B$ non si può semplificare.

Progettare chip più economici

Chi progetta chip semplifica ogni circuito con l'algebra di Boole prima di costruirlo, perché ogni porta costa spazio, energia e denaro.

Un circuito per $(A \land B) \lor (A \land C)$ usa 3 porte. Raccogliendo, $A \land (B \lor C)$, ne bastano 2.

Condizioni leggibili in un programma

I programmatori usano le leggi di De Morgan per eliminare le doppie negazioni che confondono dalle condizioni del loro codice.

NOT (weekend OR festivo) equivale a (NOT weekend) AND (NOT festivo): il negozio è aperto nei giorni che non sono né l'uno né l'altro.

Filtri di ricerca

I motori di ricerca e i database semplificano i filtri con la legge di assorbimento prima di eseguirli.

Il filtro matematica OR (matematica AND logica) restituisce esattamente gli stessi libri del filtro matematica.

Q: Perché OR è distributivo rispetto ad AND, se con i numeri $a + b \times c$ non è $(a + b) \times (a + c)$?

A: Perché le variabili booleane valgono solo 0 o 1. Controlla i due casi: se $A = 1$, entrambi i lati di $A \lor (B \land C) = (A \lor B) \land (A \lor C)$ valgono 1; se $A = 0$, entrambi i lati diventano $B \land C$. Con i numeri normali $1 + 2 \times 3 = 7$, ma $(1 + 2) \times (1 + 3) = 12$, quindi questa legge vale solo nell'algebra di Boole.

Q: Come capisco quale legge usare dopo?

A: Cerca degli schemi: un NOT davanti a una parentesi chiede De Morgan, una variabile ripetuta in due parentesi chiede di raccogliere (proprietà distributiva), e una variabile accanto alla sua stessa negazione chiede la legge del complemento. Le costanti 0 e 1 spariscono con le leggi di identità e di annullamento.

Q: Servono ancora le tavole di verità se conosco le leggi?

A: Le leggi trovano la semplificazione, la tavola di verità la conferma. Una tavola con 2 variabili ha solo 4 righe, quindi è un controllo rapido e affidabile, soprattutto quando non sei sicuro di un passo.

Q: Posso controllare una legge con l'aritmetica normale?

A: Sì, con 0 e 1: $A \land B = A \times B$, $\neg A = 1 - A$ e $A \lor B = A + B - A \times B$. Per esempio, con $A = 1$ e $B = 1$: $1 + 1 - 1 \times 1 = 1$, quindi $1 \lor 1 = 1$. La calcolatrice di questa lezione funziona con questi numeri.