Porte logiche e algebra booleana: esercizi svolti

Le porte logiche realizzano le operazioni dell’algebra booleana, il fondamento dei circuiti digitali. Con poche regole (De Morgan, identità booleane, mappe di Karnaugh) si semplificano le espressioni e si minimizza l’hardware. Questa scheda allena tabelle di verità, semplificazione e sintesi.

Operatori base: AND ( $\cdot$ ), OR ( $+$ ), NOT ( $\overline{\phantom{x}}$ ).

1. Tabella di verità di un’espressione

Esercizio. Costruire la tabella di verità di $F=A\cdot B+\overline{A}\cdot C$ per i casi $A,B,C$ .

Valutando per le 8 combinazioni (estratto significativo):

\begin{array}{ccc|c} A & B & C & F\\\hline 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 1\\ 0 & 1 & 1 & 1\\ 1 & 1 & 0 & 1\\ 1 & 0 & 1 & 0 \end{array}

$F=1$ quando ( $A$ e $B$ ) oppure (non- $A$ e $C$ ). La tabella di verità elenca l’uscita per ogni combinazione d’ingresso.

2. Leggi di De Morgan

Esercizio. Applicare De Morgan a $\overline{A+B}$ e $\overline{A\cdot B}$ .

$\overline{A+B}=\overline{A}\cdot\overline{B},\qquad \overline{A\cdot B}=\overline{A}+\overline{B}.$

De Morgan scambia AND e OR sotto negazione: la negazione di una somma è il prodotto delle negazioni e viceversa. È la regola più usata nella manipolazione booleana.

3. Semplificazione con identità booleane

Esercizio. Semplificare $F=A\cdot B+A\cdot\overline{B}$ .

Raccogliendo $A$ e usando $B+\overline{B}=1$ :

$F=A(B+\overline{B})=A\cdot1=A.$

L’uscita dipende solo da $A$ : $B$ è irrilevante. Le identità booleane ( $A+\overline A=1$ , $A\cdot A=A$ , $A+A\cdot B=A$ ) eliminano i termini ridondanti.

4. Assorbimento

Esercizio. Semplificare $F=A+A\cdot B$ .

Per la legge di assorbimento:

$F=A+A\cdot B=A(1+B)=A\cdot1=A.$

Il termine $A\cdot B$ è “assorbito” da $A$ : se $A=1$ , $F=1$ comunque; se $A=0$ , anche $A\cdot B=0$ . Semplificazione molto comune.

5. Forma somma di prodotti (SOP)

Esercizio. Scrivere la forma SOP di una funzione che vale 1 nei mintermini $A\overline{B}$ e $AB$ .

La SOP somma i mintermini in cui $F=1$ :

$F=A\overline{B}+AB.$

Semplificando (raccolta $A$ ): $F=A(\overline{B}+B)=A$ . La forma SOP si ottiene direttamente dalla tabella di verità, prendendo le righe con uscita 1.

6. Mappa di Karnaugh

Esercizio. Minimizzare con Karnaugh $F=\overline{A}\,\overline{B}+\overline{A}B+A\overline{B}$ (3 mintermini su 2 variabili).

Mappa $2\times2$ (i tre mintermini valgono 1, solo $AB$ vale 0):

\begin{array}{c|cc} & B=0 & B=1\\\hline A=0 & 1 & 1\\ A=1 & 1 & 0 \end{array}

Raggruppando: la riga $A=0$ (entrambe 1) dà $\overline{A}$ ; la colonna $B=0$ (entrambe 1) dà $\overline{B}$ :

$F=\overline{A}+\overline{B}=\overline{A\cdot B}\ \text{(De Morgan)}.$

La mappa di Karnaugh raggruppa le celle adiacenti a 1 in blocchi di potenze di 2, ottenendo l’espressione minima. $F$ è semplicemente un NAND.

7. Completezza funzionale del NAND

Esercizio. Realizzare la funzione NOT usando solo porte NAND.

Il NAND è $\overline{A\cdot B}$ . Collegando entrambi gli ingressi insieme ( $B=A$ ):

$\overline{A\cdot A}=\overline{A}.$

Il NAND con ingressi uniti realizza il NOT. Poiché con NAND si costruiscono anche AND ( $\overline{\overline{A\cdot B}}$ ) e OR (via De Morgan), il NAND è funzionalmente completo: qualunque circuito logico si realizza con soli NAND. È la ragione della sua diffusione nei circuiti integrati.

8. Porta XOR

Esercizio. Scrivere la funzione booleana della porta XOR e la sua tabella di verità.

La XOR vale $1$ quando gli ingressi sono diversi:

F=A\oplus B=\overline{A}B+A\overline{B}.

Tabella:

\begin{array}{cc|c} A&B&F\\\hline 0&0&0\\ 0&1&1\\ 1&0&1\\ 1&1&0 \end{array}

La XOR è fondamentale in sommatori, controlli di parità e comparatori. Non va confusa con OR: per $A=B=1$ , OR vale $1$ , XOR vale $0$ .

9. Forma prodotto di somme (POS)

Esercizio. Scrivere la forma POS di una funzione a due variabili che vale $0$ per $A=0,B=0$ e per $A=1,B=1$ .

La forma POS usa i maxtermini corrispondenti alle righe in cui $F=0$ .

Per la riga $A=0,B=0$ , il maxtermine è:

(A+B).

Per la riga $A=1,B=1$ , il maxtermine è:

(\overline{A}+\overline{B}).

Quindi:

F=(A+B)(\overline{A}+\overline{B}).

Sviluppando:

F=A\overline{B}+\overline{A}B,

che è proprio la XOR. SOP e POS sono due forme canoniche diverse della stessa funzione.

10. OR realizzato solo con NAND

Esercizio. Realizzare $F=A+B$ usando solo porte NAND.

Per De Morgan:

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

Con NAND si ottengono prima le negazioni:

\overline{A}=A\ \text{NAND}\ A, \qquad \overline{B}=B\ \text{NAND}\ B.

Poi:

F=(\overline{A})\ \text{NAND}\ (\overline{B}).

Esplicitamente:

\boxed{ A+B=(A\ \text{NAND}\ A)\ \text{NAND}\ (B\ \text{NAND}\ B) }.

Questo esercizio completa la prova pratica della completezza funzionale del NAND: con NAND si realizzano NOT, AND e OR.

11. Karnaugh a tre variabili

Esercizio. Minimizzare la funzione:

F(A,B,C)=\Sigma m(1,3,5,7).

Con la convenzione dei mintermini $ABC$ , i mintermini $1,3,5,7$ sono:

001,\quad 011,\quad 101,\quad 111.

In tutte queste combinazioni vale:

C=1.

La funzione è quindi indipendente da $A$ e $B$ :

\boxed{F=C}.

La mappa di Karnaugh raggrupperebbe quattro celle adiacenti corrispondenti a tutta la colonna $C=1$ . Quando una variabile cambia dentro un gruppo, viene eliminata dal termine finale.

Errori comuni

Sbagliare De Morgan. La negazione distribuisce scambiando AND e OR: $\overline{A+B}=\overline A\cdot\overline B$ , non $\overline A+\overline B$ .
Dimenticare le adiacenze nella mappa di Karnaugh. I raggruppamenti devono essere blocchi di $1,2,4,8\dots$ celle adiacenti (anche ai bordi opposti).
Non semplificare la SOP. La forma SOP diretta dalla tabella è corretta ma spesso ridondante: va minimizzata con identità o Karnaugh.
Credere che servano porte diverse. NAND (o NOR) da soli bastano per qualsiasi funzione: sono funzionalmente completi.
Confondere XOR e OR. La XOR vale $1$ solo quando gli ingressi sono diversi.