Algebra di Boole e porte logiche

---

---

1) Due interruttori e una lampadina: a che serve l'algebra di Boole
2) Attenzione: qui 1 + 1 fa 1 (e non 10)
3) NOT, AND, OR e come si scrivono in un compito italiano
4) Il tabellone delle sette porte: tutte le tavole di verità
5) Le proprietà dell'algebra di Boole e come si dimostrano in due minuti
6) De Morgan: spezzi la barra, cambi il segno (e perché la NAND può fare tutto)
7) Dal problema al circuito: il protocollo in 5 passi
8) Mappe di Karnaugh a 2, 3 e 4 variabili
9) Otto esercizi svolti passo passo
10) Gli errori che ti costano il voto
11) Domande frequenti
12) Conclusioni

---

Due interruttori e una lampadina: a che serve l'algebra di Boole

Prendi una pila, una lampadina e due interruttori. Montali in serie, uno dietro l'altro sullo stesso filo: la lampadina si accende solo quando sono chiusi tutti e due. Basta che uno sia aperto e la corrente non passa.

Scriviamo 1 per "interruttore chiuso" e 0 per "aperto", 1 per "lampadina accesa" e 0 per "spenta":


Ora montali in parallelo, ognuno sul suo filo. Adesso la lampadina si accende quando è chiuso almeno uno dei due:


Hai appena scritto le due tabelle più importanti dell'informatica. La prima si chiama AND, la seconda si chiama OR. Sono tavole di verità, e sono la cosa che questa guida ti insegna a costruire, a leggere e a trasformare in un circuito.

Il salto successivo lo ha fatto la tecnologia: un transistor è un interruttore senza parti mobili, aperto e chiuso da un'altra corrente invece che da un dito. Quattro o sei transistor fanno una porta logica, qualche miliardo di porte fa un processore. Il computer su cui stai leggendo non sa fare nient'altro che quello che c'è in queste due tabelle: lo fa solo miliardi di volte al secondo.

Cinque righe di storia, che spiegano perché la materia sembra astratta

George Boole era figlio di un calzolaio, non aveva nessuna laurea e nel 1849 diventò comunque primo professore di matematica al Queen's College di Cork. Nel 1854 pubblicò An Investigation of the Laws of Thought (Walton & Maberly, Londra), dichiarando fin dalla prima riga di voler studiare "le leggi fondamentali di quelle operazioni della mente con cui si compie il ragionamento". Nel libro non c'è una sola parola su elettricità, circuiti o macchine: stava facendo filosofia della mente con l'algebra.

Il collegamento con i circuiti arriva 83 anni dopo. Nel 1937 Claude Shannon, ventunenne, consegna al MIT la tesi di master A Symbolic Analysis of Relay and Switching Circuits (pubblicata l'anno dopo nelle Transactions of the American Institute of Electrical Engineers, vol. 57, 1938, pp. 713-723). L'idea è quella che hai visto sopra: relè in serie = AND, relè in parallelo = OR, contatto normalmente chiuso = NOT. Quando quella tesi esce, Boole era morto da 73 anni.

Ecco perché il libro di testo ti sembra formalismo puro: la matematica è nata prima dell'oggetto che descrive. Qui la rimettiamo nell'ordine giusto, cioè partendo dall'oggetto.

Come leggere questa guida

Le sezioni da 1 a 5 sono alla portata del biennio e del liceo scientifico con opzione scienze applicate. Le sezioni da 6 a 9 sono livello verifica di terza all'istituto tecnico: De Morgan applicato, forme canoniche, Karnaugh, sintesi con sole NAND. Le sezioni 10, 11 e 12 servono la sera prima del compito.

L'unico prerequisito è sapere cos'è un bit e come si conta in binario. Se hai dei dubbi, parti dalla guida su sistemi di numerazione: binario, decimale, esadecimale e poi torna qui: le due guide si incastrano, e alla fine di questa vedrai il circuito che esegue le somme binarie di quella.

---

Attenzione: qui 1 + 1 fa 1 (e non 10)

Te lo dico subito, prima che succeda, perché è l'inciampo numero uno e perché contraddice in apparenza quello che hai appena studiato sul binario.


Non è un errore di stampa e non è un cambio di regola a metà partita. Sono due algebre diverse che usano gli stessi simboli. Ecco come riconoscere in quale delle due sei, con una sola domanda.

La domanda che risolve tutto: "c'è un riporto?"

• Se c'è un riporto, è aritmetica binaria. Gli 1 e gli 0 sono cifre di un numero, hanno un peso posizionale (1, 2, 4, 8, 16...), e sommandone due il risultato può allungarsi: 1 + 1 = 10 occupa due bit.
• Se non c'è nessun riporto, è algebra di Boole. Gli 1 e gli 0 non sono quantità, sono stati: falso/vero, spento/acceso, 0 V / 5 V. Non hanno posizione e non hanno peso. Il risultato di un'operazione è sempre un bit solo, non si allunga mai.

Da qui discende tutto il resto. In Boole + non vuol dire "più": vuol dire "almeno uno". E "almeno uno fra 1 e 1" è ovviamente vero, cioè 1. Allo stesso modo · non vuol dire "per": vuol dire "tutti e due".

Il box da ricordare. L'unica riga in cui l'algebra di Boole non assomiglia all'aritmetica è 1 + 1. Tutte le altre coincidono: 0+0=0, 0+1=1, 1+0=1, e il prodotto coincide su tutte e quattro le righe. Ecco perché l'errore sopravvive: il modello aritmetico passa 7 controlli su 8. Se di questa pagina ti ricordi una cosa sola, ricordati questa riga.

Una precisazione sui nomi

I libri italiani chiamano + somma logica e · prodotto logico. Sono i termini che troverai nella verifica, quindi devi conoscerli, ma lavorano contro di te: installano proprio l'analogia sbagliata. Si chiamano così per ragioni storiche di notazione — Boole scriveva con i simboli dell'algebra che conosceva — non perché si sommi o si moltiplichi qualcosa.

E adesso la ricucitura, che è la parte bella

I due mondi non sono in guerra: uno è fatto dell'altro. La somma binaria 1 + 1 = 10 viene fuori proprio da due porte logiche. Il bit di somma è A XOR B (che con 1 e 1 dà 0) e il bit di riporto è A AND B (che con 1 e 1 dà 1). Messi insieme: 0 con riporto 1, cioè 10.

Cioè: l'aritmetica binaria non contraddice Boole, è costruita con Boole. Quel circuito si chiama half adder, è fatto di due sole porte, e lo costruiamo insieme nell'esercizio 7 della sezione 9. È il momento in cui questa materia smette di sembrare un gioco di simboli.

---

NOT, AND, OR e come si scrivono in un compito italiano

Le operazioni fondamentali sono tre. Imparale con queste parole, non con altre.

• AND — vero quando sono veri tutti e due. Si scrive A · B, oppure semplicemente AB.
• OR — vero quando è vero almeno uno dei due. Si scrive A + B.
• NOT — dà il contrario: se A vale 1 il risultato è 0, se A vale 0 il risultato è 1.

Nota che per l'OR ho evitato la parola "o". È voluto.

Perché l'OR ti sembrerà sbagliato (e perché la tua intuizione non è stupida)

In italiano parlato "o" ha quasi sempre senso esclusivo: "o vieni o resti", "prendi il primo o il secondo". Con quel significato in testa arrivi alla riga 1 1 della tavola dell'OR e ci scrivi 0. Hai disegnato una XOR credendo di aver disegnato una OR.

Non è un difetto di ragionamento: il latino aveva due parole diverse, vel (inclusivo) e aut (esclusivo), e l'italiano ne ha lasciata una sola a fare due lavori. In più chi sente "o" deduce da solo "non entrambi", perché altrimenti l'altro avrebbe detto "e".

Due frasi per sentire la differenza:

• "Sconto se sei studente o hai meno di 26 anni." Inclusivo: nessuno perde lo sconto perché è tutte e due le cose. Questo è l'OR.
• "Il menù comprende dolce o caffè." Esclusivo: uno dei due, non tutti e due. Questo è lo XOR.

Quindi: quello che tu chiami "o" esiste davvero, ha un nome ed è la XOR. La incontri fra due paragrafi. Ma A + B significa almeno uno, e sulla riga 1 1 vale 1.

La tabella delle notazioni: stessa materia, tre alfabeti

Questa è la tabella che quasi nessun sito italiano mette, e che risolve un equivoco enorme: il prof di matematica scrive ∧ e il prof di sistemi scrive ·, e tu credi che siano due materie diverse. Sono la stessa cosa.


E in programmazione cambia una terza volta: in C, C++ e Java l'AND è &&, l'OR è la doppia barra verticale e il NOT è !; in Python si scrivono and, or, not. Tre alfabeti, una materia sola.

Nel compito in classe di sistemi o di TPSIT si usa la colonna centrale: A · B, A + B, Ā.

Convenzione di questa guida. La soprallineatura non si può digitare, quindi qui la negazione la scrivo con l'apice: A' significa esattamente Ā. Sul quaderno tu continua a tracciare la barra, e se nel compito vuoi usare l'apice dichiaralo in alto al foglio con una riga: "uso A′ per Ā". Nessun professore te lo conta come errore, e nei simulatori la barra non esiste comunque.

Box 1 — Precedenza: NOT, poi AND, poi OR

L'ordine è: NOT → AND → OR. Il NOT è appiccicato alla sua variabile, l'AND si esegue prima dell'OR.

A + B · C significa A + (B · C), non (A + B) · C.

Qui, e solo qui, l'analogia con l'aritmetica è un buon consiglio: A + B·C si legge esattamente come leggeresti 2 + 3·4, cioè prima il prodotto. Sui valori l'aritmetica è un falso amico (vedi la sezione 2), sulla precedenza è un amico vero.

Che le due letture siano diverse si vede con una riga sola. Prendi A = 1, B = 1, C = 0:

• A + B·C = 1 + (1·0) = 1 + 0 = 1
• (A + B)·C = (1+1)·0 = 1·0 = 0

E un'autorizzazione esplicita: nel dubbio metti le parentesi, anche se sono ridondanti. Non è un segno di debolezza, i progettisti veri lo fanno tutti i giorni.

Box 2 — La barra è una parentesi (l'errore che costa più punti di tutti)

Una soprallineatura corta sopra la sola A significa "nego A". Una soprallineatura lunga sopra A·B significa "nego tutto il prodotto", cioè (A·B)'. Non sono la stessa cosa.


Le due colonne sono diverse su due righe su quattro. Regola operativa: prima di togliere una barra lunga, mettici le parentesi. Se riscrivi (A+B)' come A' + B hai già perso il compito, e lo hai perso prima ancora di applicare De Morgan.

---

Il tabellone delle sette porte: tutte le tavole di verità

Questa sezione è il cuore operativo della guida. Le porte da sapere sono sette, più il buffer. Tre sono fondamentali (NOT, AND, OR) e da sole bastano a costruire qualsiasi funzione; quattro sono derivate (NAND, NOR, XOR, XNOR), cioè si ottengono combinando le prime tre — ma NAND e NOR, come vedrai nella sezione 6, bastano ciascuna da sola.

Tutte le tavole di verità in una tabella

Il NOT ha un ingresso solo:


Il buffer è la porta che non fa niente: l'uscita è uguale all'ingresso. Serve a rigenerare il segnale, e nei simulatori è il triangolo senza pallino.

Le altre sei hanno due ingressi, e queste sono le loro uscite messe a confronto:


Guarda le colonne NAND e NOR: sono esattamente le colonne AND e OR rovesciate, uno per uno. NAND vuol dire Not AND, NOR vuol dire Not OR. E la colonna XNOR è la XOR rovesciata.

L'identikit di ogni porta

Gli integrati TTL della serie 74xx sono quelli che monterai in laboratorio. Il 7400 contiene quattro NAND a due ingressi in un solo chip a 14 piedini: tienilo a mente, torna utile nella sezione 6.

I simboli grafici, e cosa fare se il tuo libro usa i rettangoli

Nei libri italiani prevale la forma distintiva americana (nata come MIL-STD-806B e poi confluita nello standard ANSI/IEEE 91-1984), che è anche quella dei simulatori come Logisim e Logic.ly:


Il pallino (o bolla) davanti all'uscita significa sempre e solo una cosa: negazione. Se lo vedi, ribalta l'uscita. Il simbolo ≥1 dell'OR nella notazione IEC è, se ci pensi, la definizione stessa che ti ho dato: "almeno uno".

Come si costruisce una tavola di verità qualunque

Questa è la procedura, e va fatta sempre nello stesso ordine.

1) Conta le variabili. Se sono n, la tabella ha esattamente 2ⁿ righe. Due variabili → 4 righe, tre → 8, quattro → 16, cinque → 32. Se hai dubbi su come funzionano le potenze, dai un'occhiata alla guida sulle potenze, dalle basi agli esercizi avanzati: qui la potenza di 2 conta il numero di combinazioni possibili degli ingressi.
2) Disegna tutte le righe vuote prima di riempirle. Se decidi il numero di righe dopo aver ragionato sui valori, ti mancherà una combinazione e non te ne accorgerai mai.
3) Metti le righe in ordine di conteggio binario. Le righe di una tabella a n variabili sono semplicemente i numeri da 0 a 2ⁿ−1 scritti in binario: 000, 001, 010, 011, 100, 101, 110, 111. Non è una convenzione da rispettare per pignoleria: è lo stesso binario dell'altra guida della sezione, riusato.
4) Controlla con la regola delle colonne a metà. Nella prima colonna la metà superiore è tutta 0 e la metà inferiore tutta 1 (0000/1111 con tre variabili); la seconda va a blocchi di due (0011/0011); l'ultima si alterna (01010101). Se il disegno non viene così, c'è un buco.
5) Scrivi le colonne intermedie, sempre. Per F = A'·B + C non passare direttamente all'uscita: fai una colonna per A', una per A'·B, e solo alla fine F. Il carico mentale crolla e, se sbagli, l'errore è localizzabile in una casella invece che in tutta la riga.

Il controllo da due secondi: conta gli 1

Ogni porta ha una firma, cioè quanti 1 ci sono nella sua colonna d'uscita:


Se hai compilato una tavola e la conta non torna, hai scambiato una porta con un'altra. Due secondi di controllo, mezzo voto salvato.

E la riga da guardare per prima: fra OR e XOR l'unica differenza sta sulla riga 1 1. Compila quella per prima, non per ultima. (Per De Morgan e per i problemi di precedenza, invece, la riga che discrimina è una riga mista, tipo 1 0: lo vedi fra poco.)

---

Le proprietà dell'algebra di Boole e come si dimostrano in due minuti

Le proprietà vanno a coppie, e questo dimezza il lavoro di memoria. Il motivo lo trovi nel box alla fine della sezione.


Sono queste, non ce ne sono altre da sapere per una verifica di terza. La riga di De Morgan ha una sezione tutta sua, la prossima.

Come si dimostrano: induzione perfetta

Il metodo è uno solo e si chiama induzione perfetta: costruisci la tavola di verità dei due membri e guardi se le colonne vengono identiche. Siccome le combinazioni possibili sono un numero finito (2ⁿ), controllarle tutte è una dimostrazione completa. Non serve altro.

(Esistono anche le dimostrazioni assiomatiche a partire dai postulati di Huntington: sono roba da università e non ti verranno mai chieste alle superiori. Lasciale perdere.)

Esempio: dimostriamo l'assorbimento A + A·B = A.


Le ultime due colonne sono uguali riga per riga. Dimostrato. In parole: se A è già vero, aggiungere "A e B insieme" non aggiunge niente di nuovo; e se A è falso, anche A·B è falso. B non conta.

E adesso il secondo assorbimento, quello che sembra un trucco

A + A'·B = A + B: una negazione sparisce dal nulla. Quando una cosa sembra un trucco la si controlla, e sono sempre quattro righe.


Le ultime due colonne coincidono riga per riga. Non è un trucco.

In parole: A + A'·B si accende quando è vero A, oppure quando è vero B in una riga in cui A è falso. Ma quelle righe sono già dentro "A oppure B", e dove A è vero non serve guardare altro. Le due scritture accendono le stesse righe, quindi tanto vale usare la più corta.

Il modo per riconoscerla quando serve: se in una semplificazione ti ritrovi una variabile sommata a un prodotto che contiene la stessa variabile negata, è lei. La ritrovi tre volte in questa guida — chiude l'esempio della sezione 7, l'esercizio 4 e la prima domanda dell'autoverifica.

Le due leggi che l'aritmetica non ha (usale come prova)

Se qualcuno ancora dubita che Boole e aritmetica siano sistemi diversi, ci sono due leggi che lo dimostrano meglio di qualsiasi discorso.

La distributiva "al contrario": in Boole vale A + B·C = (A + B)·(A + C). In aritmetica è falsa e basta un conto: 2 + 3·4 = 14, mentre (2+3)·(2+4) = 5·6 = 30. Quattordici non è trenta.

L'annullamento: in Boole A + 1 = 1. Cioè: se una delle due cose è già certamente vera, "almeno una delle due" è vera comunque, qualunque cosa valga A. In aritmetica A + 1 non fa mai 1, tranne quando A vale 0.

Attenzione: chi "verifica a intuito aritmetico" non sbaglia solo scrivendo cose false, rifiuta anche leggi vere. Se ti trovi a pensare "questa formula non può essere giusta, i conti non tornano", quasi sempre stai facendo aritmetica dove non serve.

Principio di dualità. Prendi una qualsiasi identità valida, scambia tutti i + con i · e tutti gli 0 con gli 1: quello che ottieni è ancora un'identità valida. È il motivo per cui la tabella qui sopra ha due colonne e non una. Praticamente ti dimezza le cose da imparare. Non usarlo però come strumento di dimostrazione in un compito: se il prof chiede di dimostrare, lui vuole la tavola di verità.

---

De Morgan: spezzi la barra, cambi il segno (e perché la NAND può fare tutto)

Sezione di livello verifica di terza.

Augustus De Morgan pubblica Formal Logic nel 1847, lo stesso anno di The Mathematical Analysis of Logic, il primo libro di Boole — non la Laws of Thought del 1854 che hai visto nella sezione 1, ma il libretto da cui quella nascerà sette anni dopo. E nella prefazione Boole cita proprio la disputa fra De Morgan e Sir William Hamilton come l'occasione che lo spinse a scriverlo: i due si conoscevano.

I teoremi, però, non nascono lì. Le due equivalenze erano note ai logici medievali molto prima — Guglielmo di Ockham le enuncia a parole nel Trecento — e il merito di De Morgan è di averle formulate in modo esplicito dentro la logica simbolica, nello stesso anno in cui Boole metteva giù l'algebra in cui oggi le applichiamo. Per questo portano il suo nome.

Prima l'italiano, poi la formula

Tu De Morgan lo sai già. Guarda:

• "Non è vero che ho fatto entrambi i compiti" significa "me ne manca almeno uno". In simboli: (A·B)' = A' + B'.
• "Non è vero che ne ho fatto almeno uno" significa "non ho fatto né l'uno né l'altro". In simboli: (A+B)' = A' · B'.

La formula non è un'informazione nuova: è l'etichetta di una cosa che hai appena riconosciuto. Verifichiamola per induzione perfetta, colonne affiancate.


Le colonne che contano sono due. Confronta (A+B)' con A'·B': sono identiche su tutte e quattro le righe, e siccome altre righe non esistono, la legge è dimostrata. È l'induzione perfetta della sezione 5, applicata a De Morgan.

Ora guarda l'ultima colonna, quella dell'errore tipico A'+B'. Coincide con la colonna giusta sulla prima riga e sull'ultima, e sbaglia sulle due centrali, cioè proprio sulle righe miste. Tienila d'occhio: fra poco vedrai perché è quell'errore, fra tutti, a riuscire ad arrivare vivo fino al compito.

E la seconda forma:

La procedura in tre mosse

Non imparare De Morgan come un'identità da ricordare. Imparalo come procedura:

1) Spezzi la barra lunga in un solo punto.
2) Scambi + con · (o viceversa).
3) Le barre corte sulle singole variabili non si toccano.

E soprattutto: i punti 1 e 2 vanno sempre insieme. Chi ne fa uno solo sta sbagliando. Il mnemonico inglese standard è break the line, change the sign; in italiano: spezzi la barra, cambi il segno.

Esempio 1. Nega F = A·B + C. La barra lunga copre tutta la somma, quindi la spezzo lì: F' = (A·B)' · C'. Ora c'è ancora una barra lunga su A·B, la spezzo di nuovo: F' = (A' + B') · C'.

Esempio 2. Nega F = (A+B)·(C+D). Barra sull'intero prodotto → diventa somma: F' = (A+B)' + (C+D)'. Poi ciascuna: F' = A'·B' + C'·D'.

Esempio 3 (con negazione annidata). Semplifica F = (A' + B·C')'. Qui la barra lunga ne copre altre due corte, quindi vado un pezzo alla volta e non salto niente.

1) La barra esterna copre tutta la somma A' + B·C': la spezzo fra i due addendi e il + diventa · → F = (A')' · (B·C')'.
2) (A')' è A negato due volte, e due negazioni si annullano (involuzione) → F = A · (B·C')'.
3) Resta una barra lunga su B·C': la spezzo fra i due fattori, il · diventa +, e ciascuno si porta dietro la barra che aveva già → (B·C')' = B' + (C')'.
4) Ancora involuzione: (C')' torna C → F = A · (B' + C).
5) Se ti serve la forma somma di prodotti, distribuisci la A dentro la parentesi → F = A·B' + A·C.

Occhio al passaggio 3, perché è lì che quasi tutti si fermano: la barra corta di C' non l'ho toccata, è la barra lunga che le è finita sopra. Due barre sulla stessa lettera, ed ecco (C')'.

Controlla tu con A=1, B=1, C=0: dentro la parentesi originale A' + B·C' vale 0 + 1·1 = 1, quindi F = 0. E A·B' + A·C = 1·0 + 1·0 = 0. Torna.

Attenzione: la verifica su 1 1 non serve a niente

Questo è il motivo per cui l'errore di De Morgan sopravvive fino al compito. Prendi lo sbaglio classico, (A+B)' → A' + B', e provalo con A = 1, B = 1:

• corretto: (1+1)' = 1' = 0
• sbagliato: 1' + 1' = 0 + 0 = 0

Coincidono. Lo studente "verifica", vede che torna, e porta l'errore in verifica. Prova invece con A = 1, B = 0:

• corretto: (1+0)' = 1' = 0
• sbagliato: 1' + 0' = 0 + 1 = 1

Ecco la regola: per De Morgan e per la precedenza si verifica su una riga mista (1 0), non su 1 1. E se hai tempo, verifica tutte e quattro le righe.

De Morgan fuori dalla scuola: il cicalino delle cinture

Il safety-belt reminder non è un'invenzione dei costruttori: è definito dal Regolamento UNECE n. 16, obbligatorio per l'omologazione dei veicoli nell'Unione Europea. Il regolamento dice che l'avviso si attiva quando il sedile è occupato e il quadro è inserito e la cintura non è allacciata; e che per i posti posteriori l'avviso di primo livello — quello visivo, che parte all'inizio del viaggio — deve durare almeno 60 secondi, o finché la cintura non viene allacciata. L'avviso di secondo livello, che al visivo aggiunge il suono, per i posti posteriori scatta invece quando una cintura già allacciata viene slacciata a veicolo in marcia.

Tradotto:

AVVISO = QUADRO · SEDILE_OCCUPATO · CINTURA'

Due AND e un NOT: le variabili sono tre, quindi le operazioni che le legano sono due (oppure, se in laboratorio ce l'hai, una sola porta AND a tre ingressi, come nell'esercizio 5). Il NOT è quello dell'apice su CINTURA. Adesso nega tutto con De Morgan:

AVVISO' = QUADRO' + SEDILE_OCCUPATO' + CINTURA

Che letto in italiano fa: "il cicalino tace se il quadro è spento oppure il sedile è vuoto oppure la cintura è allacciata". È la stessa identica condizione, letta al contrario, ed è una frase di puro buon senso. De Morgan è questo.

Stessa cosa in programmazione: !(a && b) è equivalente a !a || !b. Se in un if neghi una condizione composta senza scambiare l'operatore, ottieni una condizione sempre vera o sempre falsa — è uno dei bug più comuni in assoluto, e ha esattamente la stessa radice.

Le bolle: una NAND è anche una OR con gli ingressi negati

Riprendi la seconda forma: (A·B)' = A' + B'. A sinistra c'è una NAND. A destra c'è una OR i cui due ingressi sono negati. Sono lo stesso identico circuito. Sullo schema si vede benissimo: il pallino lo puoi spostare dall'uscita agli ingressi, purché nel farlo cambi la forma della porta (proiettile ↔ scudo). Da qui si arriva alle porte universali.

Porta universale: con sole NAND si fa tutto

Una porta è universale (in logica: funzionalmente completa) se con quella sola, ripetuta, puoi costruire qualsiasi funzione booleana. NAND e NOR lo sono. AND da sola no: con sole AND non riesci mai a produrre una negazione.

Le tre costruzioni da sapere a memoria:

• NOT: collega insieme i due ingressi della NAND. (A·A)' = A', per idempotenza.
• AND: una NAND seguita da un'altra NAND usata come NOT. ((A·B)')' = A·B.
• OR: una NAND che riceve i due ingressi già negati (cioè preceduta da due NAND-NOT). (A'·B')' = A + B — ed è De Morgan che si materializza in rame.

La regoletta per convertire una rete AND-OR in sole NAND. Prendi la funzione in forma somma di prodotti, per esempio F = A·B + C·D, e applica una doppia negazione, che non cambia niente:

F = ((A·B + C·D)')' → spezzo la barra interna → F = ((A·B)' · (C·D)')'

Leggilo: (A·B)' è una NAND, (C·D)' è una NAND, e il tutto negato è una terza NAND. Tre NAND, un solo integrato 7400, e non ti serve nient'altro. In pratica: metti una bolla all'uscita di ogni AND e una bolla su ogni ingresso della OR finale; le bolle si cancellano a coppie e tutte le porte diventano NAND.

I due fatti che ti convincono che la NAND è la porta vera

Primo: costa meno silicio. In logica CMOS statica una NAND a due ingressi si fa con 4 transistor, una NOR a due ingressi con 4, un inverter con 2. E la AND? 6, perché in CMOS le porte elementari sono nativamente invertenti: la AND non esiste come struttura di base, è una NAND con un inverter attaccato dietro. Stessa storia per la OR (6 transistor, cioè NOR + inverter). Se hai sempre pensato all'AND come "la porta base", hai il modello mentale rovesciato rispetto a come è fatto davvero il silicio.

Per darti la scala: l'Apple M3 Max, annunciato nell'ottobre 2023, dichiara 92 miliardi di transistor. Diviso 4 fa circa 23 miliardi di NAND-equivalenti (è una divisione mia, non un dato ufficiale: non tutti i transistor di un chip sono porte logiche, gran parte è memoria cache). Non a caso l'industria misura la complessità dei chip in gate equivalent, e quell'unità è definita proprio come l'area di una NAND a due ingressi.

Secondo: c'è chi ci è andato sulla Luna. L'Apollo Guidance Computer era costruito con un solo tipo di porta. Il Block I usava 4.100 circuiti integrati, ciascuno con una singola NOR a 3 ingressi; il Block II, quello che è volato sulla Luna, circa 2.800 integrati in maggioranza NOR doppie a 3 ingressi, cioè circa 5.600 porte NOR e nient'altro. ALU, logica di controllo, multiplexer: tutto NOR. Un solo componente da qualificare, stoccare e testare, in una missione dove non puoi riparare niente.

---

Dal problema al circuito: il protocollo in 5 passi

Sezione di livello verifica di terza.

Prima due definizioni che ti verranno chieste all'interrogazione.

• Rete combinatoria: l'uscita dipende solo dagli ingressi in questo istante. Tutto quello che c'è in questa guida è combinatorio.
• Rete sequenziale: l'uscita dipende dagli ingressi e dallo stato precedente, cioè il circuito ha memoria. Flip-flop, registri e contatori sono di questa famiglia, e sono un'altra guida.

E i due verbi:

• Analisi: parti dal circuito e ricavi l'espressione (e poi la tavola).
• Sintesi: parti dalla specifica o dall'espressione e costruisci il circuito.

Una funzione logica, del resto, è una funzione a tutti gli effetti: a ogni combinazione di ingressi associa esattamente un'uscita. Se vuoi ripassare cosa vuol dire funzione in generale c'è la guida sulle funzioni in matematica: qui l'unica differenza è che il dominio è finito, 2ⁿ combinazioni tutte scrivibili in tabella.

Il protocollo, sempre uguale

1) Specifica in italiano → elenca le variabili di ingresso e l'uscita, e decidi cosa vuol dire 1 per ognuna.
2) Tavola di verità → 2ⁿ righe in ordine binario, colonne intermedie.
3) Prima forma canonica → somma di prodotti, dalle righe con uscita 1.
4) Semplificazione → con i teoremi o con Karnaugh.
5) Schema del circuito → e poi verifica, ricostruendo la tavola dell'espressione semplificata.

Passo 3: la prima forma canonica, con la regola operativa

Per ogni riga in cui l'uscita vale 1, scrivi un AND di tutte le variabili, negando quelle che in quella riga valgono 0. Poi metti tutti questi termini in OR. Ogni termine si chiama mintermine.

Esempio, tre variabili, la riga A=1, B=0, C=1 con uscita 1 dà il mintermine A·B'·C.

E adesso il perché, così non la impari a memoria. Chiediti quando vale 1 quel A·B'·C. È un AND, quindi devono essere veri tutti e tre i pezzi insieme: serve A = 1, serve B' = 1 cioè B = 0, serve C = 1. Vale 1 solo in quella riga lì, e 0 in tutte e sette le altre. Un mintermine è una spia che si accende su una riga sola.

Da qui la ricetta si spiega da sé: accendi una spia per ogni riga che deve dare 1, le metti tutte in OR (che vuol dire "basta che se ne accenda una"), e l'uscita risulta 1 esattamente sulle righe che volevi e su nessun'altra. Ed ecco anche perché le variabili che in quella riga valgono 0 vanno negate: senza la negazione la spia si accende sulla riga sbagliata. Prova a scrivere A·B·C invece di A·B'·C: quel termine non riconosce la riga 101, riconosce la 111.

Controllo di conteggio: il numero di termini AND deve essere uguale al numero di 1 nella colonna d'uscita. Se hai 3 uno e 4 termini, hai sbagliato.

Il tutto si abbrevia con la notazione Σm: F = Σm(1,3,6,7) vuol dire "la funzione vale 1 nelle righe numero 1, 3, 6 e 7" (le righe si numerano da 0, leggendo gli ingressi come numero binario).

Esiste anche la seconda forma canonica, prodotto di somme, costruita sulle righe che valgono 0: per ognuna scrivi una somma di tutte le variabili, negando quelle che in quella riga valgono 1, e moltiplichi fra loro tutte le somme. Ogni fattore si chiama maxtermine.

Qui è tutto ribaltato rispetto ai mintermini, e conviene dirselo esplicitamente: si guardano le righe con 0 invece che con 1, si negano le variabili che valgono 1 invece che 0, dentro al termine si fa + invece che · e fuori si fa · invece che +. Stessa riga dell'esempio di prima, A=1, B=0, C=1, ma stavolta con uscita 0: il maxtermine è A' + B + C'. Il perché sta tutto lì: quella somma vale 0 soltanto quando tutti e tre gli addendi sono 0, cioè soltanto su quella riga. Moltiplicando fra loro tutti i maxtermini spegni l'uscita esattamente sulle righe con lo 0 e lasci 1 su tutte le altre.

La notazione è ΠM: F = ΠM(0,2,4) vuol dire "la funzione vale 0 nelle righe 0, 2 e 4". E il controllo di conteggio è lo stesso di prima, rovesciato: i fattori devono essere tanti quanti gli 0 nella colonna d'uscita. Su 8 righe con 3 uno avrai 3 mintermini e 5 maxtermini: due espressioni diverse, la stessa identica funzione.

Le due regole di disegno che valgono metà dei punti

Da espressione a circuito: si parte dall'uscita. L'errore tipico è trascrivere le porte da sinistra a destra nell'ordine in cui l'espressione è scritta. La regola giusta è: l'ultima operazione che eseguiresti a mano è la porta attaccata all'uscita. In A·B + C l'ultima operazione è l'OR, quindi l'OR tocca l'uscita e riceve due cose: il risultato dell'AND e il segnale C.

Da circuito a espressione: si va a ritroso, etichettando. Dai un nome all'uscita di ogni porta (n1, n2, ...), scrivi cosa vale ciascuna in funzione dei suoi ingressi, e sostituisci a ritroso fino ad avere una sola espressione in funzione degli ingressi veri.

Esempio guidato: l'allarme con tre sensori

Passo 1 — specifica. L'allarme suona se il sistema è inserito e è aperta la porta oppure la finestra. Variabili: S (sistema inserito), P (porta aperta), F (finestra aperta). Uscita: U (sirena).

Passo 2 — tavola di verità. Tre variabili, quindi 8 righe, in ordine binario.


Nota le prime quattro righe: se il sistema è disinserito, la sirena tace anche con porta e finestra spalancate. È la parte di specifica che quasi tutti dimenticano di scrivere.

Passo 3 — prima forma canonica. Tre uno, quindi tre mintermini: U = Σm(5,6,7) = S·P'·F + S·P·F' + S·P·F.

Passo 4 — semplificazione, con il nome della proprietà a ogni riga.

Una parola sul verbo raccogliere, che qui sotto compare due volte e poi torna in ogni semplificazione della guida. La distributiva l'hai vista scritta così: A·(B+C) = A·B + A·C. Letta da sinistra a destra sviluppa, cioè apre la parentesi; letta da destra a sinistra raccoglie, cioè mette in evidenza il pezzo che si ripete e la parentesi la chiude. Non sono due proprietà: è la stessa, percorsa nei due versi — lo stesso movimento con cui da 3x + 3y torni a 3·(x+y). Nella semplificazione booleana serve quasi sempre nel verso del raccoglimento, ma il nome da scrivere accanto al passaggio, sul compito, resta distributiva.


Risultato: U = S·(P + F), che è esattamente la frase di partenza. Quando succede questo, è il segno che non hai sbagliato niente.

Passo 5 — circuito e verifica. L'ultima operazione è l'AND, quindi l'AND tocca l'uscita: una OR riceve P e F, la sua uscita entra in una AND insieme a S. Due porte. Ricostruisci la tavola di S·(P+F) e confrontala con quella di partenza: coincidono riga per riga.

---

Mappe di Karnaugh a 2, 3 e 4 variabili

Sezione di livello verifica di terza.

Maurice Karnaugh lavorava ai Bell Telephone Laboratories di Murray Hill, nel New Jersey, e progettava circuiti di commutazione telefonica. È la stessa azienda in cui Shannon aveva passato l'estate del 1937, anche se allora i laboratori stavano ancora a Manhattan, al 463 di West Street: la sede di Murray Hill apre solo nel 1941. Nel 1953 pubblica The Map Method for Synthesis of Combinational Logic Circuits nelle Transactions of the AIEE, part I, vol. 72, pp. 593-598. Non era un esercizio didattico: era un problema di lavoro.

Il metodo funziona benissimo fino a 4 variabili, diventa scomodo a 5 (32 caselle, due mappe sovrapposte) e cede a 6 (64 caselle). Il limite non è matematico: è la capacità dell'occhio umano di vedere pattern. Oltre quel punto si passa ad algoritmi tabellari come Quine-McCluskey, cioè si passa la palla al calcolatore.

Il "perché" che nessuno spiega: il codice Gray

Le colonne di una mappa si numerano 00, 01, 11, 10, e non 00, 01, 10, 11. Sembra un dispetto. Non lo è.

L'ordine 00, 01, 11, 10 è il codice Gray, e ha una proprietà unica: fra una casella e la successiva cambia una sola variabile. Ed è proprio questo che rende la mappa uno strumento e non un disegno: due caselle vicine che valgono entrambe 1 differiscono per una variabile sola, quindi quella variabile si può eliminare per complementazione — è la stessa cosa che facevi a mano quando raccoglievi S·P·(F' + F) = S·P. La mappa serve a farti vedere con gli occhi dove quel raccoglimento è possibile.

Se le colonne fossero in ordine binario normale, le caselle vicine differirebbero anche per due variabili e il raccoglimento non varrebbe.

Le regole, tutte

1) Si raggruppano solo caselle che valgono 1 (o X, vedi sotto), in gruppi di 1, 2, 4, 8, 16 caselle: solo potenze di 2. Un gruppo da 3 o da 6 non esiste.
2) I gruppi devono essere i più grandi possibile: più grande è il gruppo, meno variabili restano nel termine.
3) Le sovrapposizioni sono ammesse: la stessa casella può stare in più gruppi.
4) La mappa si richiude a ciambella. La prima colonna è adiacente all'ultima, la prima riga all'ultima, e nella mappa a 4 variabili i quattro angoli sono adiacenti fra loro e formano un gruppo valido. È l'errore che più spesso fa perdere il raggruppamento migliore.
5) Nel termine di un gruppo si scrivono solo le variabili che non cambiano all'interno del gruppo, negate se valgono 0.
6) Alla fine si sommano (OR) tutti i termini trovati.

Esempio a 3 variabili, risolto due volte

F = A'·B'·C + A'·B·C + A·B·C' + A·B·C, cioè F = Σm(1,3,6,7).

Con i teoremi:


Con la mappa. Prima di raggruppare bisogna riempirla, ed è il passaggio che quasi tutti danno per scontato. La regola è una sola: ogni casella della mappa è una riga della tavola di verità, scritta in un altro posto. La riga della mappa ti dice quanto vale A, la colonna quanto valgono B e C; nella casella scrivi 1 se quella combinazione è fra i mintermini, 0 in tutte le altre.

Le righe sono A (0 e 1), le colonne sono BC in codice Gray. Prendiamo F = Σm(1,3,6,7) un mintermine alla volta:

• 1 = 001 → A=0, BC=01 → riga 0, colonna 01
• 3 = 011 → A=0, BC=11 → riga 0, colonna 11
• 6 = 110 → A=1, BC=10 → riga 1, colonna 10
• 7 = 111 → A=1, BC=11 → riga 1, colonna 11

Quattro caselle a 1, tutte le altre a 0. E l'inciampo della prima volta è sempre lo stesso: le colonne stanno in ordine 00, 01, 11, 10, quindi la 11 è la terza e la 10 è la quarta. Se posizioni i mintermini come se l'ordine fosse binario, ti ritrovi le ultime due colonne scambiate e i gruppi non tornano più.

Controllo di conteggio: gli 1 nella mappa devono essere tanti quanti i mintermini. Qui quattro e quattro. Ecco la mappa:


Due gruppi da due caselle:

• riga A = 0, colonne 01 e 11: cambia B, restano A = 0 e C = 1 → termine A'·C
• riga A = 1, colonne 11 e 10: cambia C, restano A = 1 e B = 1 → termine A·B

F = A'·C + A·B. Stesso risultato dei teoremi, e ci hai messo dieci secondi invece di quattro passaggi.

Verifica finale (quella che nessuno insegna): ricostruisci la tavola di A'·C + A·B e confrontala con i mintermini di partenza. Vale 1 in 001, 011 (per A'·C) e in 110, 111 (per A·B), cioè esattamente Σm(1,3,6,7). Torna.

Esempio a 4 variabili, con le adiacenze ai bordi

F = Σm(0,1,2,5,8,9,10) con variabili A, B, C, D (A è il bit più significativo).

Righe AB e colonne CD, entrambe in codice Gray:


Tre gruppi:

• Gruppo da 4 "verticale a ciambella": le caselle CD=00 e CD=01 nelle righe AB=00 e AB=10. Le righe 00 e 10 sono la prima e l'ultima, e sono adiacenti perché differiscono per la sola A. Sono i mintermini 0, 1, 8, 9: cambia A, cambia D, restano B = 0 e C = 0 → B'·C'.
• Gruppo dei quattro angoli: mintermini 0, 2, 8, 10. Restano B = 0 e D = 0 → B'·D'.
• Gruppo da 2: mintermini 1 e 5 (colonna CD=01, righe AB=00 e AB=01). Restano A = 0, C = 0, D = 1 → A'·C'·D.

F = B'·C' + B'·D' + A'·C'·D

Il mintermine 5 è coperto solo dal terzo gruppo, quindi quel termine da tre variabili non si può togliere. Senza le adiacenze ai bordi avresti trovato gruppi da 2 al posto dei gruppi da 4, e un'espressione più lunga: sbagliata no, ma non minima — e in una verifica di sintesi vale meno.

Condizioni di indifferenza e forma PS: due accenni

Quando certe combinazioni di ingresso non possono fisicamente accadere (per esempio da 1010 a 1111 se stai trattando cifre BCD, che arrivano solo fino a 9), nella mappa si scrive X: sono le condizioni di indifferenza, in inglese don't care. La regola è una sola: le X si usano solo se convengono, cioè solo se ti permettono di ingrandire un gruppo. Non c'è nessun obbligo di coprirle.

E se invece degli 1 raggruppi gli zeri, ottieni la funzione negata; negandola con De Morgan trovi la sintesi in forma prodotto di somme, che a volte è più corta. Vale la pena provarle entrambe e tenere la più corta.

Questi due casi, insieme agli implicanti primi essenziali e alle mappe a 5 variabili, meritano una guida a parte.

---

Otto esercizi svolti passo passo

Livello base (biennio e liceo)

Esercizio 1 — Completa la tavola di verità di F = A'·B + C.

Tre variabili → 8 righe, in ordine binario, con le colonne intermedie.


Attenzione alla precedenza: si esegue prima A', poi l'AND con B, e solo alla fine l'OR con C. Chi legge A'·B + C come A'·(B+C) sbaglia le righe 5 e 7, quelle in cui A vale 1 e C vale 1.

Cinque uno → F = Σm(1,2,3,5,7).

Esercizio 2 — Analisi: dal circuito all'espressione.

Il circuito ha due ingressi, A e B. A e B entrano in una NAND, la cui uscita chiamiamo n1. Gli stessi A e B entrano anche in una OR, uscita n2. Infine n1 e n2 entrano in una AND, che dà l'uscita U.

Si etichetta e si va a ritroso:

• n1 = (A·B)'
• n2 = A + B
• U = n1 · n2 = (A·B)' · (A + B)


Guarda la colonna U: 0, 1, 1, 0. Due uno, e sono sulle righe in cui gli ingressi sono diversi. È una XOR. In italiano: "almeno uno, ma non tutti e due" — che è la definizione parlata dell'OR esclusivo.

Esercizio 3 — Dimostra De Morgan per induzione perfetta.

Va dimostrato che (A·B)' = A' + B'. Si costruiscono le due colonne e si confrontano.


Le colonne (A·B)' e A' + B' sono identiche, e siccome le righe possibili sono tutte lì, la dimostrazione è completa. Questa è l'induzione perfetta: se il compito dice "dimostra", questa tabella è la risposta.

Livello verifica di terza

Esercizio 4 — Semplifica F = A·B + A·B' + A'·B, giustificando ogni passaggio.

Senza i nomi delle proprietà questo esercizio vale metà. Con i nomi vale tutto.


Verifica (obbligatoria, e veloce):


Coincidono: la funzione di partenza era una semplice OR travestita da tre termini.

Esercizio 5 — Dal problema in italiano al circuito.

"Il nastro trasportatore parte se il motore è acceso e il pezzo è in posizione e il riparo non è aperto."

Passo 1 — specifica. M = motore acceso, P = pezzo in posizione, R = riparo aperto (attenzione: la variabile è "aperto", quindi nella condizione va negata). Uscita N = il nastro parte.

Passo 2 — tavola di verità. Tre variabili, 8 righe.


Passo 3 — prima forma canonica. Un solo 1, quindi un solo mintermine: N = Σm(6) = M·P·R'.

Passo 4 — semplificazione. Non c'è niente da semplificare: un solo mintermine è già la forma minima.

Passo 5 — circuito. Un NOT su R, poi una AND a tre ingressi che riceve M, P e R'. Fine.

La cosa da portarsi via: la parola "non" della specifica diventa una porta NOT, e la riga 7 deve valere 0 anche se motore e pezzo sono a posto. Se il tuo circuito fa partire il nastro con il riparo aperto, hai progettato un macchinario che ferisce l'operatore. Le variabili negate non sono un dettaglio formale.

Esercizio 6 — Rivelatore di maggioranza a 3 ingressi, con Karnaugh e con sole NAND.

"L'uscita vale 1 quando almeno due dei tre ingressi valgono 1." È il classico circuito di voto a maggioranza usato nei sistemi ridondanti.


M = Σm(3,5,6,7) — quattro uno, quindi quattro mintermini: M = A'·B·C + A·B'·C + A·B·C' + A·B·C.

Mappa:


Tre gruppi da due caselle, tutti che passano per la casella A=1, BC=11:

• colonna BC = 11, righe 0 e 1: restano B = 1, C = 1 → B·C
• riga A = 1, colonne 01 e 11: restano A = 1, C = 1 → A·C
• riga A = 1, colonne 11 e 10: restano A = 1, B = 1 → A·B

M = A·B + A·C + B·C. Da quattro termini di tre variabili a tre termini di due: è il guadagno tipico della mappa.

Con sole NAND. Doppia negazione e De Morgan:

M = ((A·B + A·C + B·C)')' = ((A·B)' · (A·C)' · (B·C)')'

Cioè: tre NAND a due ingressi che calcolano (A·B)', (A·C)', (B·C)', e una quarta NAND a tre ingressi che le raccoglie. Quattro NAND, e un 7400 ne contiene quattro (per quella a tre ingressi ti serve un 7410, che ne contiene tre a tre ingressi).

Controllo su una riga: con A=1, B=1, C=0 le tre NAND danno 0, 1, 1; il loro prodotto è 0; negato fa 1. Corretto, la maggioranza c'è.

Sfida: la chiusura del cerchio

Esercizio 7 — Half adder: il circuito che somma due bit.

Riprendiamo la promessa della sezione 2. Vogliamo un circuito che sommi due bit A e B e produca due uscite: la somma S e il riporto C (carry).


Guarda la colonna S: 0, 1, 1, 0. È la XOR. Guarda la colonna C: 0, 0, 0, 1. È la AND.

S = A ⊕ B C = A · B

Due porte, quattro righe, e hai costruito il pezzo che esegue le somme binarie. 1 + 1 = 10 non è una regola calata dall'alto: è quello che succede quando una XOR e una AND ricevono due 1. Adesso 1 + 1 che fa 1 in Boole e 10 in binario non è più una contraddizione, è una conseguenza.

In forma canonica, S = A'·B + A·B', che è la definizione estesa dello XOR.

Esercizio 8 — Full adder: tre ingressi, e la somma vera.

L'half adder somma due bit, ma quando sommi numeri di più cifre ogni colonna riceve anche il riporto della colonna precedente. Servono tre ingressi: A, B e Cin.


Ogni riga si legge così: quanti 1 ci sono fra i tre ingressi? Zero → S=0, Cout=0. Uno → S=1, Cout=0. Due → S=0, Cout=1 (cioè "2 in binario è 10"). Tre → S=1, Cout=1 (cioè "3 in binario è 11").

S = Σm(1,2,4,7) e Cout = Σm(3,5,6,7).

Cout con la mappa (riga = A, colonne = B e Cin in codice Gray):


È la stessa mappa dell'esercizio 6, e non è un caso: il riporto esce quando almeno due dei tre ingressi valgono 1, cioè il riporto è una maggioranza.

Cout = A·B + A·Cin + B·Cin

Una forma equivalente e più economica, quella che si usa quando hai già uno XOR in casa, è Cout = A·B + Cin·(A ⊕ B). Verificala sulla riga 5 (A=1, B=0, Cin=1): A·B = 0, A ⊕ B = 1, quindi Cin·1 = 1 e Cout = 1. Torna.

S con la mappa:


Nessuna casella con l'1 è adiacente a un'altra casella con l'1: è una scacchiera, non si raggruppa niente. Non hai sbagliato: questa è la firma dello XOR, e la mappa di Karnaugh non lo sa riconoscere. La forma corretta è

S = A ⊕ B ⊕ Cin

cioè lo XOR a tre ingressi, che vale 1 quando il numero di 1 in ingresso è dispari.

E il full adder si costruisce davvero con due half adder più una OR. Ecco come si incastrano:

1) il primo half adder somma A e B: ti dà una somma parziale S1 = A ⊕ B e un riporto C1 = A·B;
2) il secondo half adder somma S1 con il riporto in arrivo Cin: la sua uscita di somma è S = S1 ⊕ Cin, cioè A ⊕ B ⊕ Cin, proprio la S che cerchi; il suo riporto è C2 = S1·Cin;
3) il riporto in uscita si prende con una OR: Cout = C1 + C2. In italiano: il riporto esce se lo ha generato la prima somma oppure la seconda.

E se scrivi per esteso quel C1 + C2 ottieni A·B + Cin·(A ⊕ B), cioè esattamente la forma economica di qualche riga più su. Non era una scorciatoia arrivata dal nulla: era il disegno del circuito.

E i numeri più lunghi? Colleghi il Cout di ogni full adder al Cin di quello successivo, come quando riporti l'uno a mano. Si chiama ripple carry adder: 8 full adder in fila sommano due byte. Il difetto è che il riporto deve propagarsi da destra a sinistra e questo costa tempo — esistono schemi più veloci, ed è materia di quarta. Se vuoi rivedere come si somma in binario a mano, prima che diventi rame, è tutto nella guida sui sistemi di numerazione.

Cinque esercizi per l'autoverifica (solo il risultato)

1) Semplifica F = A·B' + B. → A + B
2) Semplifica F = (A + B)·(A + B'). → A
3) Quante righe ha la tavola di verità di una funzione di 5 variabili? → 32
4) Nega G = A·B + C' con De Morgan. → G' = (A' + B')·C
5) Una funzione di 3 variabili vale 1 nelle righe 0, 1, 2 e 3. Qual è la sua forma minima? → A'

Provalo senza breadboard

Per montare questi circuiti e vederli funzionare ci sono simulatori gratuiti: Logisim Evolution, Logic.ly, Deeds (sviluppato in Italia) e Tinkercad Circuits, che nel browser ti dà gli integrati 74xx veri. Sono tutti in notazione americana, quindi le porte le riconosci al volo. Monta il full adder dell'esercizio 8: cinque minuti che valgono un'ora di teoria.

---

Gli errori che ti costano il voto

Sono dieci, e vengono dai compiti corretti. Su due punti c'è anche la ricerca didattica: lo studio di Herman, Loui, Kaczmarczyk e Zilles (ACM Transactions on Computing Education, vol. 12, n. 1, articolo 3, 2012), diciassette universitari intervistati uno per uno appena finito il corso di reti logiche, documenta l'errore 4 — più della metà traduceva «non entrambi» con una XOR invece che con una NAND — e il principio che chiude la sezione. Sull'OR, invece, quello studio non ha trovato fraintendimenti diffusi: nessuno degli intervistati ha sbagliato a tradurre «almeno uno». L'errore 3 è qui perché lo vedo nei compiti, non perché lo dica quel paper, che le difficoltà peggiori le ha misurate altrove, sul «se... allora» e sul «se e solo se» — quest'ultimo tradotto bene da tre studenti soltanto.

1) 1 + 1 = 1, non 2 e non 10. E A · A = A, non A². In Boole non esistono esponenti né coefficienti: A + A = A, non 2A.
2) La barra lunga non si distribuisce. (A+B)' non è A' + B'. Devi spezzare la barra e cambiare il segno, sempre insieme, mai una cosa sola.
3) OR compilata come XOR sulla riga 1 1. La tua intuizione dell'"o" è corretta, ma descrive lo XOR. A + B con due 1 vale 1.
4) NAND scambiata con NOR o XOR, perché "non entrambi" suona restrittivo. La NAND invece è generosa: vale 1 in tre righe su quattro. Conta gli 1 e la smascheri.
5) Tavola con meno di 2ⁿ righe, o con le righe in ordine arbitrario. Se le righe non sono i numeri da 0 a 2ⁿ−1 in binario, non ti accorgerai mai di quella che manca.
6) Variabili negate dimenticate nella traduzione dall'italiano. Distributore di panini con quattro ingredienti: formaggio F, prosciutto P, insalata I, salsa S. Se l'ordinazione dice "solo formaggio", la funzione non è F, è F·P'·I'·S': quel "solo" impone che le altre tre siano false, ed è la parte invisibile della frase. Nell'esercizio 5 succede lo stesso: "il riparo non è aperto" è una variabile negata, e se sparisce, sparisce anche la sicurezza dell'operatore.
7) Precedenza ignorata: A + B·C letto come (A+B)·C. L'ordine è NOT, poi AND, poi OR. Nel dubbio, parentesi.
8) Mintermini scritti per le righe con uscita 0, oppure variabili a 0 lasciate senza negazione. La regola è: righe con uscita 1, e nel termine si negano le variabili che in quella riga valgono 0.
9) Adiacenze ai bordi della mappa non viste, e gruppi che non sono potenze di 2. La mappa si richiude sui quattro lati, gli angoli sono adiacenti, e un gruppo da 3 caselle non esiste.
10) Semplificazione corretta ma senza il nome della proprietà accanto a ogni passaggio. Il risultato giusto senza giustificazioni vale metà punteggio in quasi tutte le griglie di valutazione.

Il principio che tiene insieme tutta la lista

La tavola di verità è il tribunale d'appello. Ogni volta che hai un dubbio — su una porta, su una barra, su una precedenza, su una semplificazione — non riguardare la formula: costruisci le due colonne e confrontale. È il risultato più solido della ricerca didattica su questo argomento: gli stessi studenti che sbagliano a tradurre una frase in espressione booleana rispondono correttamente quando sono costretti a compilare una tabella.

E quando verifichi, usa la riga che discrimina, non una riga a caso:

• per la famiglia OR / XOR / aritmetica → riga 1 1;
• per De Morgan e per la precedenza → una riga mista, tipo 1 0.

Controllare due casi qualunque e fermarsi è precisamente il modo in cui un errore sopravvive fino al compito in classe.

---

Domande frequenti

Perché in algebra di Boole 1 + 1 fa 1 e non 2?
Perché il segno + non è la somma aritmetica: significa "almeno uno dei due è vero". E "almeno uno fra 1 e 1" è vero, cioè 1. In Boole gli 0 e gli 1 non sono quantità ma stati (falso/vero, spento/acceso), quindi il risultato è sempre un bit solo. Si chiama "somma logica" per ragioni storiche di notazione, non perché si sommi qualcosa.

Che differenza c'è fra algebra di Boole e aritmetica binaria, se usano gli stessi simboli?
Basta una domanda: c'è un riporto? Se sì è aritmetica binaria, dove i bit sono cifre con peso posizionale e il risultato si può allungare (1+1 = 10). Se no è algebra di Boole, dove non c'è posizione né riporto e l'uscita è un bit solo (1+1 = 1). I due mondi però si incastrano: la somma binaria di due bit si costruisce con due porte, somma = XOR e riporto = AND (half adder).

Quante righe deve avere una tavola di verità?
Con n variabili servono esattamente 2 elevato a n righe: 4 con due variabili, 8 con tre, 16 con quattro, 32 con cinque. Disegnale tutte vuote prima di riempirle, e mettile in ordine di conteggio binario (000, 001, 010, 011, 100, 101, 110, 111): così sono i numeri da 0 a 2^n meno 1 e non puoi saltarne nessuna.

Come si passa da una tavola di verità al circuito?
Per ogni riga in cui l'uscita vale 1 scrivi un AND di tutte le variabili, negando quelle che in quella riga valgono 0; poi metti tutti i termini in OR. È la prima forma canonica, o somma di prodotti. Controllo: i termini AND devono essere tanti quanti gli 1 nella colonna d'uscita. Poi semplifichi (con i teoremi o con Karnaugh) e disegni partendo dall'uscita, perché l'ultima operazione dell'espressione è la porta attaccata all'uscita.

Come si applicano i teoremi di De Morgan?
In tre mosse: spezzi la barra lunga in un solo punto, scambi il + con il · (o viceversa), e le barre corte sulle singole variabili non le tocchi. Le prime due mosse vanno sempre insieme. Quindi NOT(A+B) = NOT A · NOT B e NOT(A·B) = NOT A + NOT B. Attenzione: verificare con A=1 e B=1 non serve, perché anche la versione sbagliata dà lo stesso risultato; verifica su una riga mista come A=1, B=0.

Qual è la differenza fra OR e XOR?
L'OR vale 1 quando almeno uno dei due ingressi è 1, quindi anche quando lo sono entrambi; lo XOR vale 1 solo quando gli ingressi sono diversi. L'unica riga in cui differiscono è 1 1: l'OR dà 1, lo XOR dà 0. Il senso esclusivo dell'"o" italiano ("o vieni o resti") è proprio lo XOR, ed è per questo che tanti compilano male la tavola dell'OR.

Perché NAND e NOR si chiamano porte universali e AND no?
Perché con sole NAND (o sole NOR) puoi costruire qualsiasi funzione booleana: A NAND A dà NOT A, due NAND in cascata danno l'AND, e una NAND con gli ingressi già negati dà l'OR, che è De Morgan applicato al rame. Con sole AND invece non ottieni mai una negazione. In più, in tecnologia CMOS una NAND costa 4 transistor e una AND 6, perché la AND è una NAND con un inverter dietro.

Perché le colonne della mappa di Karnaugh sono 00, 01, 11, 10 e non 00, 01, 10, 11?
Perché è il codice Gray, in cui fra una casella e la successiva cambia una sola variabile. Solo così due caselle vicine che valgono entrambe 1 si possono raggruppare eliminando la variabile che cambia. Con l'ordine binario normale le caselle adiacenti differirebbero anche per due variabili e il raggruppamento non sarebbe valido. Ricorda anche che la mappa si richiude sui bordi: prima e ultima colonna sono adiacenti, e i quattro angoli formano un gruppo.

---

Conclusioni

Il percorso, in poche righe: il computer ha due stati, e il modo di scriverli è il binario. Su quei due stati si fanno operazioni, e le regole sono l'algebra di Boole, scritta nel 1854 per studiare il ragionamento umano. Quelle operazioni si possono eseguire con dei circuiti, come ha mostrato Shannon nel 1937. E oggi di quei circuiti ce ne stanno decine di miliardi sotto un'unghia di silicio: dai 2.300 transistor dell'Intel 4004 del 1971 ai 92 miliardi dichiarati da Apple per l'M3 Max nel 2023, circa 40 milioni di volte in poco più di cinquant'anni. Ogni singolo transistor, però, non fa nient'altro che quello che hai letto qui.

La sequenza operativa da portare in verifica è sempre la stessa: specifica → tavola di verità → prima forma canonica → semplificazione → schema → verifica.

Formulario da tenere sotto gli occhi

Proprietà (A' sta per Ā):


Le sei porte a due ingressi, con la firma:


Regole rapide: n variabili → 2ⁿ righe; righe in ordine di conteggio binario; termini AND della forma canonica = numero di 1 nell'uscita; colonne della mappa di Karnaugh in codice Gray 00, 01, 11, 10; gruppi solo di 1, 2, 4, 8 caselle; la mappa si richiude sui bordi.

Glossario italiano-inglese

I simulatori e i datasheet sono in inglese, quindi ti serve.

Dove andare adesso

Indietro, se qualcosa nel binario ti è rimasto in sospeso: sistemi di numerazione: binario, decimale, esadecimale. Adesso sai anche che circuito esegue quelle somme.

Avanti, con due argomenti che partono da dove finisce questa guida: le mappe di Karnaugh avanzate (don't care usate bene, forma prodotto di somme, implicanti primi essenziali, mappe a 5 variabili) e le reti combinatorie notevoli — il multiplexer, che sceglie uno fra più ingressi in base a un indirizzo; il demultiplexer, che fa il contrario; il decoder, che accende una sola uscita fra 2ⁿ; l'encoder, che dice quale ingresso è attivo; il comparatore, che confronta due numeri binari. Sono tutti costruiti con le porte di questa guida.

E poi c'è l'altra metà del mondo digitale: flip-flop, registri, contatori, cioè le reti sequenziali, quelle in cui l'uscita dipende anche da quello che è successo prima. Lì entra in scena il tempo, e serve il clock. Ma senza quello che hai letto qui, quella storia non si può nemmeno cominciare.