Vai al contenuto
← Algebra booleana · Lezione 2
Algebra Booleana · Lezione 2

Le regole
del gioco

Due espressioni diverse possono dire la stessa cosa? E come lo dimostri senza provare tutte le combinazioni? In questa lezione le leggi dell'algebra di Boole (ciascuna con la sua intuizione «da interruttore»), De Morgan e la dualità, la semplificazione passo per passo, e gli operatori derivati. Vedremo anche come costruire qualsiasi funzione booleana usando soltanto porte NAND.

1
Capitolo 1

Due strade per l'equivalenza

Nella lezione 1 l'equivalenza aveva una sola prova: la stessa tabella di verità. Funziona sempre, ma con nn variabili costa 2n2^n righe, e soprattutto non spiega perché due espressioni coincidono.

La seconda strada è algebrica: si trasforma un'espressione nell'altra applicando leggi, un passo alla volta, come si fa coi numeri. Ogni passo cita la sua legge, e la catena di passi è la dimostrazione. Le due strade si controllano a vicenda: la tabella dice se è vero, l'algebra dice perché. Con molte variabili, le trasformazioni algebriche evitano di enumerare tutte le righe della tabella.

2
Capitolo 2

Le leggi, con l'intuizione da interruttore

Poche regole permettono di manipolare e semplificare le espressioni, come si fa in algebra con i numeri. Eccole, tutte dimostrabili con una tabella di verità.

LeggeCon AND (·)Con OR (+)
IdentitàA⋅1=AA\cdot 1=AA+0=AA+0=A
Elemento nulloA⋅0=0A\cdot 0=0A+1=1A+1=1
IdempotenzaA⋅A=AA\cdot A=AA+A=AA+A=A
ComplementoA⋅A‾=0A\cdot\overline{A}=0A+A‾=1A+\overline{A}=1
CommutativaA⋅B=B⋅AA\cdot B=B\cdot AA+B=B+AA+B=B+A
Associativa(AB)C=A(BC)(A B)C=A(B C)(A+B)+C=A+(B+C)(A+B)+C=A+(B+C)
DistributivaA(B+C)=AB+ACA(B+C)=AB+ACA+BC=(A+B)(A+C)A+BC=(A+B)(A+C)
AssorbimentoA(A+B)=AA(A+B)=AA+AB=AA+AB=A
ConsensoAB+A‾C+BC=AB+A‾CAB+\overline{A}C+BC = AB+\overline{A}C

Le più usate hanno un'intuizione «da interruttore» che aiuta a interpretare la formula:

  • Elemento nullo: un interruttore in serie sempre aperto (A⋅0A\cdot 0) spegne tutto; uno in parallelo sempre chiuso (A+1A+1) accende tutto, qualunque cosa faccia AA.
  • Complemento: AA e A‾\overline{A} in serie non conducono mai (uno dei due è sempre aperto); in parallelo conducono sempre.
  • Assorbimento: se il ramo AA da solo accende la luce, aggiungergli in parallelo il ramo A⋅BA\cdot B non cambia niente, perché quel ramo conduce solo quando AA già conduceva. A+AB=AA+AB=A.
  • Consenso: il termine BCBC è ridondante perché nei casi in cui scatta (B=C=1B=C=1), uno tra ABAB e A‾C\overline{A}C è già scattato, qualunque sia AA.
💡 Doppia negazione

A‾‾=A\overline{\overline{A}}=A: negare due volte riporta al valore di partenza.

⚠️ La distributiva dell'OR rispetto all'AND

La prima distributiva, A(B+C)=AB+ACA(B+C)=AB+AC, è quella dell'aritmetica. La seconda, A+BC=(A+B)(A+C)A+BC=(A+B)(A+C), a chi viene dai numeri sembra un errore: con l'aritmetica non funziona (2+3⋅4≠(2+3)(2+4)2+3\cdot4 \ne (2+3)(2+4)). In Boole vale in entrambi i versi, e la dimostrazione per tabella è nel laboratorio del prossimo capitolo: scegli «Distributiva (OR)» e guardala reggere su tutte le righe.

3
Capitolo 3

De Morgan e la dualità

Due identità permettono di applicare la negazione a espressioni con AND e OR. Le useremo per semplificare le espressioni e progettare i circuiti.

📘 De Morgan

A⋅B‾=A‾+B‾\overline{A\cdot B}=\overline{A}+\overline{B}, A+B‾=A‾⋅B‾\overline{A+B}=\overline{A}\cdot\overline{B}. A parole: la negazione di un AND è l'OR delle negazioni, e viceversa. Negando, l'operatore si «ribalta» (AND↔OR) e ogni pezzo si nega.

La lettura intuitiva: «non è vero che piove e fa freddo» significa «non piove oppure non fa freddo». Basta che una delle due manchi. E «non è vero che piove o fa freddo» significa «non piove e non fa freddo»: devono mancare entrambe. La regola si estende a quante variabili vuoi: A⋅B⋅C‾=A‾+B‾+C‾\overline{A\cdot B\cdot C}=\overline{A}+\overline{B}+\overline{C}.

📘 Il principio di dualità

Guarda la tabella delle leggi: ogni identità resta vera scambiando AND ↔ OR e 0 ↔ 1. È il principio di dualità: da un'identità si ricava quella della colonna accanto applicando questi scambi.

⚠️ De Morgan «a metà»

L'errore più comune di tutta la materia: negare i pezzi dimenticando di ribaltare l'operatore (o viceversa). A⋅B‾\overline{A\cdot B} non è A‾⋅B‾\overline{A}\cdot\overline{B}: è A‾+B‾\overline{A}+\overline{B}. Le due mosse (ribalta e nega) si fanno insieme, sempre. Il laboratorio qui sotto le mostra riga per riga.

Laboratorio 1Verifica una legge con la tabella

Scegli una legge: le due espressioni (sinistra e destra) vengono confrontate riga per riga. Colonne identiche ⇒ la legge è vera.

Laboratorio 2Verifica le leggi di De Morgan

Le due forme di De Morgan, verificate riga per riga: la colonna di sinistra (la negazione) e quella di destra coincidono sempre.

Laboratorio 3Prova gli operatori derivati

Modifica gli ingressi e confronta le uscite: XOR (1 se gli ingressi sono diversi), XNOR (il suo contrario), NAND (NOT-AND) e NOR (NOT-OR).

4
Capitolo 4

Semplificare, passo per passo

La tecnica: si guarda l'espressione cercando le sagome delle leggi (un X+X ⁣YX+X\!Y da assorbire, un X+X‾X+\overline{X} che vale 1, un fattore da raccogliere) e si applica una legge alla volta, scrivendo quale. Seguiamo tre esempi con passaggi progressivamente più articolati.

Semplificazione 1

A⋅B+A⋅B‾A\cdot B + A\cdot\overline{B}

Raccogli AA (distributiva): A⋅(B+B‾)A\cdot(B+\overline{B}). Complemento: B+B‾=1B+\overline{B}=1. Identità: A⋅1=AA\cdot 1=A.

Risultato: AA. L'uscita coincide con l'ingresso A: le operazioni intermedie non sono necessarie.

Semplificazione 2

(A+B)⋅(A+B‾)(A+B)\cdot(A+\overline{B})

È la sagoma della distributiva OR letta al contrario: (A+X)(A+Y)=A+XY(A+X)(A+Y)=A+XY. Quindi A+B⋅B‾A+B\cdot\overline{B}. Complemento: B⋅B‾=0B\cdot\overline{B}=0. Identità: A+0=AA+0=A.

Risultato: AA. La distributiva permette di applicare poi la legge del complemento.

Semplificazione 3

A‾⋅B‾‾⋅(A+B)\overline{\overline{A}\cdot\overline{B}}\cdot(A+B)

De Morgan sul primo fattore: A‾⋅B‾‾=A+B\overline{\overline{A}\cdot\overline{B}}=A+B (ribalta l'AND in OR, nega i pezzi già negati: doppia negazione). Resta (A+B)⋅(A+B)(A+B)\cdot(A+B). Idempotenza.

Risultato: A+BA+B. Sotto il travestimento c'era due volte la stessa cosa.

🧪 Esercizio · prova tu

Semplifica, citando la legge a ogni passo: (1) A+A‾⋅BA+\overline{A}\cdot B · (2) A⋅B+A⋅B⋅CA\cdot B+A\cdot B\cdot C · (3) A+B‾‾\overline{A+\overline{B}}. Poi verifica ogni risultato nel laboratorio del capitolo 3 o in Python (capitolo 6).

✅ Soluzione

(1) Distributiva OR: A+A‾B=(A+A‾)(A+B)A+\overline{A}B=(A+\overline{A})(A+B); complemento e identità → A+BA+B. È un'identità utile da ricordare a sé: «AA oppure, se non c'è AA, BB» è semplicemente «AA o BB».

(2) Assorbimento con X=ABX=AB: X+XC=XX+XC=X → A⋅BA\cdot B.

(3) De Morgan: A‾⋅B‾‾\overline{A}\cdot\overline{\overline{B}}; doppia negazione → A‾⋅B\overline{A}\cdot B.

5
Capitolo 5

XOR, NAND, NOR e l'universalità

Dai tre operatori fondamentali se ne derivano altri, così frequenti da avere nome e porta propri. Li hai già visti accesi nel laboratorio 3 del capitolo 3.

📘 XOR (o esclusivo)

A⊕B=AB‾+A‾BA\oplus B = A\overline{B}+\overline{A}B: vale 1 se gli ingressi sono diversi. È il cancello a due telecomandi della lezione 1, diventato un operatore. XNOR è il suo contrario: 1 se uguali.

Tre proprietà di XOR che torneranno (nei sommatori, e nella lezione 5 con i cifrari): è associativo e commutativo; A⊕A=0A\oplus A=0; A⊕0=AA\oplus 0=A. Messe insieme, applicare due volte lo stesso XOR riporta al punto di partenza: (A⊕K)⊕K=A(A\oplus K)\oplus K=A.

📘 NAND e NOR

A⋅B‾\overline{A\cdot B} (NOT-AND: 0 solo se entrambi 1) e A+B‾\overline{A+B} (NOT-OR: 1 solo se entrambi 0).

L'universalità della NAND. Con sole porte NAND si costruiscono NOT, AND e OR, quindi qualunque funzione booleana. Si dice che NAND è funzionalmente completa, o «universale» (e NOR lo è altrettanto):

Da costruireSolo con NANDPerché funziona
NOT AA↑AA\uparrow AA⋅A‾=A‾\overline{A\cdot A}=\overline{A} (idempotenza)
A AND B(A↑B)↑(A↑B)(A\uparrow B)\uparrow(A\uparrow B)NAND seguita dal suo NOT: la doppia negazione restituisce l'AND
A OR B(A↑A)↑(B↑B)(A\uparrow A)\uparrow(B\uparrow B)De Morgan: A‾⋅B‾‾=A+B\overline{\overline{A}\cdot\overline{B}}=A+B

La proprietà permette di realizzare una funzione usando un solo tipo di porta. Le leggi di De Morgan servono a convertire le espressioni nella forma adatta a questa realizzazione. Lo riprenderemo nella lezione sui circuiti.

6
Capitolo 6

La verifica in Python

Ogni semplificazione fatta a mano si controlla in un'esecuzione, con la funzione equivalenti() della lezione 1:

Playground Python Tab indenta · Esc poi Tab per uscire · Ctrl/Cmd+Invio esegue · il primo «Esegui» scarica Python; le librerie vengono scaricate quando servono · arresto automatico dopo 30 s di esecuzione
▶ Premi «Esegui» per lanciare il codice.

E De Morgan, generalizzato a tre variabili, il caso che a mano richiederebbe otto righe di tabella:

Playground Python Tab indenta · Esc poi Tab per uscire · Ctrl/Cmd+Invio esegue · il primo «Esegui» scarica Python; le librerie vengono scaricate quando servono · arresto automatico dopo 30 s di esecuzione
▶ Premi «Esegui» per lanciare il codice.

Abbiamo le regole e sappiamo dimostrare. Nella prossima lezione il problema si ribalta: data la tabella del comportamento che vuoi, come ricavi l'espressione più semplice che lo produce? Risposta: forme canoniche e mappe di Karnaugh.

7
Capitolo 7

Verifica finale

Otto domande sulla lezione. Rispondi a tutte, poi premi «Correggi». Puoi sempre riprovare.

1. Per la legge di assorbimento, A + A·B vale…
Se A è 1 il risultato è 1; se A è 0 anche AB è 0. Dipende solo da A.
2. Quanto vale A·Ā?
Una variabile e la sua negazione non possono essere entrambe 1: l'AND è sempre 0.
3. La negazione di A+B (De Morgan) è…
La negazione di un OR è l'AND delle negazioni: ribalta e nega, insieme.
4. A + BC = (A+B)(A+C) è…
Questa proprietà non vale nell'aritmetica ordinaria. Per i valori booleani puoi verificarla con la tabella o con il laboratorio del capitolo 3.
5. Il principio di dualità dice che ogni identità resta vera scambiando…
Le identità della tabella sono accoppiate secondo questi scambi: da una si ricava la sua duale.
6. A ⊕ A vale…
XOR è 1 solo se gli ingressi sono diversi, e A non è mai diverso da sé. Corollario: (A⊕K)⊕K = A.
7. «NAND è universale» significa che…
NOT, AND e OR si ottengono da sole NAND (idempotenza, doppia negazione, De Morgan), quindi tutto il resto.
8. NOT A, usando solo NAND, si scrive…
A NAND A = NOT(A·A) = NOT A, per idempotenza. (A NAND 0 vale sempre 1, qualunque sia A.)
★
Riepilogo

Tutto su una pagina

Leggi base

  • Identità: A·1=A, A+0=A
  • Nullo: A·0=0, A+1=1
  • Complemento: A·Ā=0, A+Ā=1
  • Assorbimento: A+AB=A · doppia negazione riporta ad A

De Morgan & dualità

  • NOT(A·B) = Ā+B̄
  • NOT(A+B) = Ā·B̄
  • Ribalta l'operatore E nega i pezzi, insieme
  • Dualità: AND↔OR, 0↔1

Derivati

  • XOR: 1 se diversi · A⊕A=0 · (A⊕K)⊕K=A
  • NAND: 0 solo se entrambi 1 · NOR: 1 solo se entrambi 0
  • NAND (e NOR) è universale

Semplificare

  • Cerca le sagome: X+XY, X+X̄, fattori comuni
  • Una legge alla volta, citandola
  • A+ĀB = A+B: da ricordare
  • Verifica: tabella o equivalenti()

Algebra Booleana · Lezione 2 · Le regole del gioco · buono studio!

Tengo corsi di programmazione, analisi dati e intelligenza artificiale per aziende ed enti di formazione, in aula e da remoto. Scopri come insegno e quali materiali uso a lezione.