Impara › Argomento 2

Algebra di Boole: leggi, De Morgan e semplificazione

7 min di lettura · Team bitGateLab

L'algebra di Boole è il linguaggio con cui si descrivono e si trasformano i circuiti digitali. Ogni espressione corrisponde a una rete di porte, e ogni legge che applichi per semplificarla si traduce in porte risparmiate. Qui ripasserai i postulati, le leggi più utili, i teoremi di De Morgan e il modo di semplificare un'espressione passo dopo passo, giustificando ogni mossa.

Variabili e operazioni

Una variabile booleana assume soltanto i valori 0 e 1. Le operazioni fondamentali sono tre: il complemento (A, porta NOT), il prodotto logico (A·B o AB, porta AND) e la somma logica (A + B, porta OR). In assenza di parentesi, l'ordine di precedenza è: prima il complemento, poi il prodotto e infine la somma. Così A + BC significa A + (B·C), come nell'algebra ordinaria.

Postulati

Tutta l'algebra poggia su pochi postulati. Nota che si presentano a coppie: uno per la somma e uno per il prodotto.

Postulato	Forma con la somma	Forma con il prodotto
Elemento neutro	A + 0 = A	A · 1 = A
Commutativo	A + B = B + A	AB = BA
Distributivo	A + BC = (A + B)(A + C)	A(B + C) = AB + AC
Complemento	A + A = 1	A · A = 0

Principio di dualità: se un'uguaglianza è vera, lo è anche quella che ottieni scambiando + con ·, e 0 con 1 (senza toccare le variabili né le loro barre). Per questo ogni legge ha una versione "gemella". Osserva la distributiva della somma, A + BC = (A + B)(A + C): non esiste nell'algebra dei numeri reali, ma qui è perfettamente valida.

Leggi e teoremi utili

Dai postulati si deducono queste regole, che sono quelle che userai di più nel semplificare:

Legge	Forma con la somma	Forma con il prodotto
Idempotenza	A + A = A	AA = A
Elemento nullo	A + 1 = 1	A · 0 = 0
Involuzione	A = A
Associativa	A + (B + C) = (A + B) + C	A(BC) = (AB)C
Assorbimento	A + AB = A	A(A + B) = A
Assorbimento del complemento	A + AB = A + B	A(A + B) = AB
Adiacenza	AB + AB = A	(A + B)(A + B) = A
Consenso	AB + AC + BC = AB + AC	(A + B)(A + C)(B + C) = (A + B)(A + C)

Ognuna di queste leggi si può verificare con una tabella di verità: se le due colonne coincidono in tutte le righe, l'uguaglianza è vera. Per esempio, per A + AB = A: con A = 0 entrambi i membri valgono 0 qualunque sia B; con A = 1 entrambi valgono 1. L'assorbimento del complemento si dimostra così: A + AB = (A + A)(A + B) = 1·(A + B) = A + B, usando la distributiva della somma.

Teoremi di De Morgan

Questi due teoremi ti dicono come "spezzare" una barra lunga:

A · B = A + B (il complemento di un prodotto è la somma dei complementi).
A + B = A · B (il complemento di una somma è il prodotto dei complementi).

La regola pratica: quando spezzi la barra, cambia l'operazione che stava sotto (· con + oppure + con ·) e nega ogni termine. Funziona con qualsiasi numero di variabili: ABC = A + B + C.

A	B	AB	A + B	A + B	AB
0	0	1	1	1	1
0	1	1	1	0	0
1	0	1	1	0	0
1	1	0	0	0	0

Nei circuiti, De Morgan dice che una NAND equivale a una OR con i pallini sugli ingressi, e una NOR equivale a una AND con i pallini sugli ingressi. È la base per convertire qualsiasi progetto in sole NAND o sole NOR, come si spiega in porte logiche.

Esempio 1: applicare De Morgan. Semplifica F = AB + C.

La barra lunga copre una somma: AB + C = AB · C.
Spezza la barra del prodotto: AB = A + B.
Risultato: F = (A + B)C = AC + BC.

Verifica con A = 1, B = 1, C = 0: l'originale dà 1 + 0 = 0; il risultato dà (0 + 0)·1 = 0. Con A = 0, B = 1, C = 0: originale 0 + 0 = 1; risultato (1 + 0)·1 = 1.

Semplificazione algebrica passo dopo passo

Semplificare significa ridurre il numero di termini e di letterali (ogni occorrenza di una variabile, negata o no). Meno letterali significa meno ingressi di porta. Con la sola algebra non esiste un algoritmo unico; queste tattiche funzionano quasi sempre:

Cerca coppie di termini che differiscono per una sola variabile e applica l'adiacenza.
Raccogli a fattor comune e cerca un A + A = 1 nascosto.
Se un termine è contenuto in un altro, eliminalo per assorbimento.
Puoi duplicare un termine (idempotenza) per combinarlo con due vicini diversi.

Esempio 2. Semplifica F = AB + AB + AB.

Raccogli nei primi due: AB + AB = A(B + B) = A·1 = A.
Resta F = A + AB.
Assorbimento del complemento: A + AB = A + B.

F = A + B. Sei passato da tre porte AND, una OR a tre ingressi e due invertitori a una sola OR.

Esempio 3: funzione di maggioranza. Semplifica F = ABC + ABC + ABC + ABC.

Per idempotenza, ABC = ABC + ABC + ABC. Scrivi tre copie per combinarne ciascuna con un vicino.
ABC + ABC = BC(A + A) = BC.
ABC + ABC = AC(B + B) = AC.
ABC + ABC = AB(C + C) = AB.

F = AB + AC + BC. Vale 1 quando almeno due dei tre ingressi valgono 1: è un circuito di votazione. Vedrai che è anche l'uscita di riporto del sommatore completo.

Esempio 4: distributiva della somma. Semplifica F = (A + B)(A + C).

Moltiplica: AA + AC + AB + BC = A + AC + AB + BC.
Raccogli A: A(1 + C + B) + BC.
Elemento nullo: 1 + C + B = 1, quindi resta A + BC.

È proprio il postulato distributivo della somma letto al contrario.

Errori comuni

Applicare De Morgan senza cambiare l'operazione: AB non è AB, è A + B.
"Semplificare" i termini come nell'algebra ordinaria. In Boole non esistono né la sottrazione né la divisione: da A + B = A + C non si deduce che B = C.
Dimenticare la precedenza: A + BC non è (A + B)C.
Spezzare solo una parte di una barra lunga. La barra di AB + C agisce su tutta la somma; lavora dalla barra più esterna verso l'interno.
Fermarsi troppo presto. Dopo ogni passo controlla se è rimasto qualcosa da assorbire o un termine di consenso ridondante.

Provalo nel simulatore

Una semplificazione corretta produce un circuito con esattamente la stessa tabella di verità dell'originale. Il simulatore ti permette di verificarlo senza compilare la tabella a mano.

Costruisci nell'editor il circuito originale di un esempio, come AB + AB + AB, con i suoi ingressi e la sua uscita.
Genera la sua tabella di verità e annotala.
Su un'altra uscita della stessa area di lavoro, costruisci la versione semplificata (A + B) con gli stessi ingressi.
Porta gli ingressi in tutte le combinazioni e osserva che le due uscite coincidono sempre.
Richiedi l'espressione semplificata a partire dalla tabella e confrontala con quella che hai ottenuto a mano.

Esercizi

Semplifica F = AB + AB + AB.
Risposta
AB + AB = A. Poi A + AB = A + B (assorbimento del complemento). F = A + B = AB: è una NAND.
Semplifica F = A + B.
Risposta
De Morgan: A · B = AB.
Semplifica F = A(A + B) + B(B + C).
Risposta
Per assorbimento, A(A + B) = A e B(B + C) = B. F = A + B.
Dimostra il teorema del consenso: AB + AC + BC = AB + AC.
Risposta
Scrivi BC = BC(A + A) = ABC + ABC. Allora AB + ABC = AB (assorbimento) e AC + ABC = AC (assorbimento). Resta AB + AC.