Algebra di Boole e semplificazione

Un’espressione logica lunga si traduce in un circuito con tante porte. Se un’espressione più corta produce la stessa tabella di verità, il circuito equivalente costa meno, consuma meno e sbaglia meno. Semplificare non è estetica: è ingegneria.

Le regole con una costante

Con lo 0 e con l’1 le regole discendono dritte dalle definizioni di AND e OR:

X + 0 = X \qquad X + 1 = 1 \qquad X \cdot 1 = X \qquad X \cdot 0 = 0

Le due centrali sono gli elementi assorbenti, e sono quelle che fanno sparire pezzi interi di espressione: un 1 dentro una OR decide da solo l’uscita, uno 0 dentro una AND pure.

Le regole con il complemento

X + \overline{X} = 1 \qquad\qquad X \cdot \overline{X} = 0

La prima si legge: “X o non-X” è sempre vera — una delle due lo è di sicuro. La seconda: “X e non-X” è sempre falsa — non possono esserlo entrambe.

E l’idempotenza, che non ha equivalente nell’algebra ordinaria:

X + X = X \qquad\qquad X \cdot X = X

È qui che l’algebra di Boole smette di somigliare a quella normale:

\underbrace{X + X = X}_{\text{Boole}} \qquad\neq\qquad \underbrace{x + x = 2x}_{\text{algebra ordinaria}}

Non esistono coefficienti né esponenti: ripetere una variabile non la “accumula”. Chi porta dentro i riflessi dell’algebra ordinaria scrive $2X$ o $X^2$ , che non significano niente.

La tecnica: raccogliere e assorbire

La semplificazione tipo funziona quasi sempre in due mosse: raccogliere una variabile comune, poi far collassare la parentesi con le regole del complemento o dell’assorbente.

AB\overline{C} + BC + \overline{A}BC

Guardo gli ultimi due termini: hanno $BC$ in comune.

BC + \overline{A}BC = BC\,(1 + \overline{A}) = BC \cdot 1 = BC

Il $(1 + \overline{A})$ vale 1 per l’elemento assorbente, e il termine $\overline{A}BC$ è sparito gratis: era già contenuto in $BC$ .

Un altro passaggio ricorrente, il collasso col complemento:

A\,(B + \overline{B}) = A \cdot 1 = A

Davanti a un’espressione da semplificare, cerca nell’ordine:

coppie di termini che differiscono solo per una variabile negata → raccogli e usa $X + \overline{X} = 1$ ;
un termine “corto” contenuto in uno “lungo” → il lungo sparisce per assorbimento ( $X + XY = X$ );
un 1 dentro una OR o uno 0 dentro una AND → collasso immediato.

Ogni passaggio deve conservare la tabella di verità: se hai un dubbio, provala su una riga.

Le leggi di De Morgan

Per negare un’espressione composta:

\overline{A + B} = \overline{A} \cdot \overline{B} \qquad\qquad \overline{A \cdot B} = \overline{A} + \overline{B}

La negazione entra sulle variabili e scambia gli operatori: la OR negata diventa AND di negati, e viceversa. Sono le leggi che collegano NAND e NOR alle porte fondamentali, e il motivo per cui le porte universali possono costruire tutto.

Esercizio. Semplifica:

$A + AB$
$AB + A\overline{B}$
$(A + B)\cdot(A + \overline{B})$
$A + AB + BC + \overline{A}BC$

Mostra la soluzione

1. Raccolgo la $A$ :

A + AB = A\,(1 + B) = A \cdot 1 = A

2. Raccolgo e uso il complemento:

AB + A\overline{B} = A\,(B + \overline{B}) = A \cdot 1 = A

3. Svolgo il prodotto:

(A+B)(A+\overline{B}) = AA + A\overline{B} + AB + B\overline{B} = A + A(\overline{B} + B) + 0 = A + A = A

(Idempotenza nell’ultimo passaggio: $A + A = A$ , non $2A$ .)

4. Due raccoglimenti in sequenza:

A + AB = A \qquad\text{e}\qquad BC + \overline{A}BC = BC(1 + \overline{A}) = BC

\Longrightarrow\quad A + BC

Verifica. Controlla su una riga della tabella: con $A=0$ , $B=1$ , $C=1$ l’espressione di partenza del punto 4 vale $0 + 0 + 1 + 1 = 1$ e la semplificata $0 + 1 = 1$ ✓. Una riga non prova tutto, ma smaschera subito una semplificazione sbagliata.