Come capisco quale legge usare dopo?

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.

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

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.

Posso controllare una legge con l'aritmetica normale?

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.

Risorse per insegnanti

Algebra di Boole

Impara le leggi dell'algebra di Boole, comprese le leggi di De Morgan, usale per semplificare le espressioni passo dopo passo e controlla il risultato con una tavola di verità.

Avanzato30 minLezione

Scheda da stampare

Definizione

L'algebra di Boole è un insieme di leggi per riscrivere le espressioni booleane. Ogni legge dice che due espressioni sono equivalenti: hanno lo stesso valore di verità per ogni ingresso, quindi puoi sempre sostituire l'una con l'altra. Con le leggi puoi semplificare un'espressione senza costruire ogni volta una nuova tavola di verità.

Scriviamo 1 per vero e 0 per falso (anche le tavole di verità interattive usano 1 e 0). Gli ingegneri scrivono spesso

A \cdot B

per

A \land B

A + B

per

A \lor B

\overline{A}

per

\neg A

: significano esattamente la stessa cosa. In questa lezione usiamo

\land

\lor

\neg

Le leggi (

A

B

C

sono variabili booleane):

Legge	Forma AND	Forma OR
Identità (elemento neutro)	$A \land 1 = A$	$A \lor 0 = A$
Annullamento (dominanza)	$A \land 0 = 0$	$A \lor 1 = 1$
Idempotenza	$A \land A = A$	$A \lor A = A$
Complemento	$A \land \neg A = 0$	$A \lor \neg A = 1$
Doppia negazione	$\neg\neg A = A$	(una sola forma)
Proprietà commutativa	$A \land B = B \land A$	$A \lor B = B \lor A$
Proprietà associativa	$(A \land B) \land C = A \land (B \land C)$	$(A \lor B) \lor C = A \lor (B \lor C)$
Proprietà distributiva	$A \land (B \lor C) = (A \land B) \lor (A \land C)$	$A \lor (B \land C) = (A \lor B) \land (A \lor C)$
Legge di assorbimento	$A \land (A \lor B) = A$	$A \lor (A \land B) = A$
De Morgan	$\neg(A \land B) = \neg A \lor \neg B$	$\neg(A \lor B) = \neg A \land \neg B$

Nota lo schema: se in una colonna scambi

\land

con

\lor

e 0 con 1, ottieni l'altra colonna. Questo si chiama dualità.

Semplificare passo dopo passo: usa una sola legge per ogni passo e dichiara quale. Poi controlla il risultato con una tavola di verità: se le colonne finali coincidono in ogni riga, la semplificazione è corretta.

Prova subito

Quale legge dice che

A \land \neg A = 0

Esempi svolti

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$

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

Errori comuni

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

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

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

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

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

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

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

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

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

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

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

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

Visuale interattivo

Tabella di verità

EspressioneA ∧ B ∨ A ∧ ¬B

A	B	A ∧ B	¬B	A ∧ ¬B	A ∧ B ∨ A ∧ ¬B
0	0	0	1	0	0
0	1	0	0	0	0
1	0	0	1	1	1
1	1	1	0	0	1

1= Vero0= Falso

Tabella di verità

Seleziona operatore

A ∧ B

A	B	A ∧ B
0	0	0
0	1	0
1	0	0
1	1	1

1= Vero0= Falso

Sandbox interattivo

Calcolatrice di espressioni

Prova questi:

Cronologia

Ancora nessun calcolo

Esercizi pratici

18 esercizi

Problema 1 di 18

Facile

Quale legge dice che $A \land \neg A = 0$ ?

Perché è importante

Ogni

\land

\lor

\neg

di un'espressione diventa una porta logica in un circuito. Un'espressione più corta significa meno porte, e meno porte significano un chip più economico, più piccolo, più veloce e che consuma meno energia.

Elettronica: un processore contiene miliardi di porte, quindi risparmiare una porta in un circuito copiato un milione di volte fa risparmiare un milione di porte
Programmazione: una condizione come NOT (weekend OR festivo) si può riscrivere come (NOT weekend) AND (NOT festivo), che spesso è più facile da leggere e da testare
Ricerca e database: un filtro come matematica OR (matematica AND logica) dà esattamente gli stessi risultati di matematica da solo
Dimostrazioni: le leggi permettono di dimostrare che due circuiti o due condizioni fanno la stessa cosa senza provare tutti gli ingressi

Nella lezione Tavole di verità hai controllato le equivalenze riga per riga, e nella lezione Porte logiche hai costruito circuiti. L'algebra di Boole collega le due cose: trasforma un circuito grande in uno piccolo, e una tavola di verità conferma che non è cambiato niente.

Applicazioni nel mondo reale

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.

Esempio:

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

1Provaci tu stesso

Un chip contiene 1000 copie di un circuito che calcola $(A \land B) \lor (A \land C)$ . Conta una porta per ogni $\land$ e ogni $\lor$ .

Quante porte risparmia l'intero chip se il circuito viene semplificato in $A \land (B \lor C)$ ?

Passo 1: Scrivi l'espressione matematica

Scrivi il risparmio come calcolo:

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.

Esempio:

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.

2Provaci tu stesso

Un programma apre una sbarra se vale $\neg(\neg P \land \neg G)$ , dove $P$ significa che il visitatore ha un pass e $G$ che è nella lista degli invitati.

Qual è la forma più semplice della condizione e quanti operatori NOT spariscono?

Passo 1: Scrivi l'espressione matematica

Scrivi il numero di operatori NOT prima e dopo come sottrazione:

Filtri di ricerca

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

Esempio:

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

3Provaci tu stesso

Una biblioteca ha 40 libri di matematica, e 15 di questi parlano anche di logica. Un lettore cerca matematica OR (matematica AND logica).

Quanti libri restituisce la ricerca?

Passo 1: Scrivi l'espressione matematica

Somma i libri di matematica e i libri in più che porta (matematica AND logica):

Punti chiave

1L'algebra di Boole usa le leggi per riscrivere un'espressione in una equivalente, senza una nuova tavola di verità ogni volta
2Le leggi di identità, annullamento, idempotenza e complemento eliminano costanti e variabili ripetute: $A \land 1 = A$ , $A \lor 1 = 1$ , $A \lor A = A$ , $A \land \neg A = 0$
3Le proprietà commutativa, associativa e distributiva riordinano, raggruppano e raccolgono; nell'algebra di Boole anche OR è distributivo rispetto ad AND
4Leggi di assorbimento: $A \lor (A \land B) = A$ e $A \land (A \lor B) = A$
5Leggi di De Morgan: 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$
6Semplifica con una legge per passo, nomina ogni legge e controlla il risultato con una tavola di verità; un'espressione più semplice significa meno porte

Domande frequenti

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.

Glossario

Algebra di Boole: L'insieme delle leggi per riscrivere e semplificare le espressioni booleane
Legge: Un'equivalenza che vale per ogni valore delle variabili, come $A \lor 0 = A$
Equivalente: Che ha lo stesso valore di verità in ogni riga della tavola di verità
Semplificare: Riscrivere un'espressione con meno operatori mantenendola equivalente
Leggi di De Morgan: $\neg(A \land B) = \neg A \lor \neg B$ e $\neg(A \lor B) = \neg A \land \neg B$
Legge di assorbimento: $A \lor (A \land B) = A$ e $A \land (A \lor B) = A$

Scheda formule

Identità e annullamento

A \land 1 = A, \quad A \lor 0 = A, \quad A \land 0 = 0, \quad A \lor 1 = 1

AND con 1 e OR con 0 non cambiano niente; AND con 0 e OR con 1 decidono il risultato

Idempotenza e complemento

A \land A = A, \quad A \lor A = A, \quad A \land \neg A = 0, \quad A \lor \neg A = 1

Ripetere una variabile non aggiunge niente; una variabile con la sua stessa negazione dà una costante

Doppia negazione

\neg\neg A = A

Due NOT si annullano a vicenda

Proprietà distributive

A \land (B \lor C) = (A \land B) \lor (A \land C), \quad A \lor (B \land C) = (A \lor B) \land (A \lor C)

Valgono entrambe nell'algebra di Boole; la seconda non funziona con i numeri normali

Leggi di assorbimento

A \lor (A \land B) = A, \quad A \land (A \lor B) = A

La parte più lunga viene assorbita da $A$

Leggi di De Morgan

\neg(A \land B) = \neg A \lor \neg B, \quad \neg(A \lor B) = \neg A \land \neg B

Spezza la barra, cambia il segno

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

Progettare chip più economici

Condizioni leggibili in un programma

Filtri di ricerca

Punti chiave

Domande frequenti

Glossario

Scheda formule

Identità e annullamento

Idempotenza e complemento

Doppia negazione

Proprietà distributive

Leggi di assorbimento

Leggi di De Morgan

Altro su questo argomento

Introduzione alla logica booleana

Enunciati veri e falsi

L'operazione AND

L'operazione OR