Impara › Argomento 3

Tabelle di verità e forme canoniche: Σm e ΠM

8 min di lettura · Team bitGateLab

Quasi tutti i problemi di progetto digitale cominciano con un enunciato a parole ("l'allarme suona se...") che si trasforma in una tabella di verità. Il passo successivo è ricavare da quella tabella un'equazione che tu possa realizzare con le porte. Qui imparerai il metodo sistematico per farlo: i mintermini e i maxtermini, le forme canoniche somma di prodotti e prodotto di somme, e la notazione compatta Σm e ΠM usata dai libri, dai simulatori e dalle mappe di Karnaugh.

Come si ordina una tabella di verità

Con n variabili ci sono 2ⁿ righe. Si scrivono in ordine binario crescente, con la prima variabile come bit più significativo. In questo modo ogni riga è identificata da un numero decimale: in una tabella di A, B e C, la riga A = 1, B = 0, C = 1 è la 101₂ = 5. Quel numero è quello che userai come indice del mintermine o del maxtermine, perciò l'ordine delle variabili conta: se cambi l'ordine, cambiano i numeri.

Mintermini e somma di prodotti

Un mintermine è un prodotto (AND) che contiene tutte le variabili, ciascuna una sola volta, negata o non negata. Si costruisce così: la variabile che vale 1 in quella riga va senza barra e quella che vale 0 va con la barra. Il mintermine vale 1 unicamente nella sua riga e 0 in tutte le altre. Si indica con m_i, dove i è il numero della riga.

Riga	A	B	C	Mintermine	Maxtermine
0	0	0	0	m₀ = ABC	M₀ = A + B + C
1	0	0	1	m₁ = ABC	M₁ = A + B + C
2	0	1	0	m₂ = ABC	M₂ = A + B + C
3	0	1	1	m₃ = ABC	M₃ = A + B + C
4	1	0	0	m₄ = ABC	M₄ = A + B + C
5	1	0	1	m₅ = ABC	M₅ = A + B + C
6	1	1	0	m₆ = ABC	M₆ = A + B + C
7	1	1	1	m₇ = ABC	M₇ = A + B + C

Se sommi (OR) i mintermini di tutte le righe in cui la funzione vale 1, ottieni un'equazione che vale 1 esattamente in quelle righe. Questa è la somma di prodotti canonica (SOP, dall'inglese sum of products) o prima forma canonica. In notazione compatta si scrive F = Σm(elenco delle righe con 1).

Maxtermini e prodotto di somme

Un maxtermine è una somma (OR) che contiene tutte le variabili. La regola è quella opposta: la variabile che vale 0 nella riga va senza barra e quella che vale 1 va con la barra. Un maxtermine vale 0 unicamente nella sua riga. Si indica con M_i (con la M maiuscola).

Se moltiplichi (AND) i maxtermini di tutte le righe in cui la funzione vale 0, ottieni un'equazione che vale 0 proprio lì e 1 altrove: il prodotto di somme canonico (POS) o seconda forma canonica. Si scrive F = ΠM(elenco delle righe con 0).

Il mintermine e il maxtermine della stessa riga sono complementari: m_i = M_i. Per questo, se conosci l'elenco Σm di una funzione, l'elenco ΠM è formato da tutti i numeri che non vi compaiono.

Esempio 1: dalla tabella alle due forme. Una funzione di tre variabili vale 1 nelle righe 1, 3, 6 e 7.

#	A	B	C	F
0	0	0	0	0
1	0	0	1	1
2	0	1	0	0
3	0	1	1	1
4	1	0	0	0
5	1	0	1	0
6	1	1	0	1
7	1	1	1	1

Notazione compatta: F = Σm(1, 3, 6, 7) = ΠM(0, 2, 4, 5).
Somma di prodotti canonica: F = ABC + ABC + ABC + ABC.
Prodotto di somme canonico: F = (A + B + C)(A + B + C)(A + B + C)(A + B + C).
Semplifica la SOP: ABC + ABC = AC e ABC + ABC = AB. Quindi F = AC + AB.

Verifica nella riga 5 (A = 1, B = 0, C = 1): AC = 0 e AB = 0, quindi F = 0, come nella tabella.

Quale forma conviene?

Le due forme descrivono la stessa funzione, ma non hanno la stessa dimensione. Usa quella con meno termini: se la funzione ha pochi uni, la Σm è più corta; se ha pochi zeri, è più corta la ΠM. Con 8 righe, una funzione con 2 uni ha una SOP di 2 termini e una POS di 6.

Conta anche la realizzazione. Una somma di prodotti si costruisce con porte AND che pilotano una OR, e questa struttura a due livelli si converte direttamente in NAND-NAND. Un prodotto di somme si costruisce con porte OR che pilotano una AND, e si converte in NOR-NOR.

Esempio 2: dall'enunciato all'equazione. Un serbatoio ha tre sensori di livello: A (basso), B (medio) e C (alto). Ogni sensore dà 1 quando l'acqua lo raggiunge. Una lampada di "livello non valido" deve accendersi quando la combinazione è fisicamente impossibile: un sensore più alto attivo con uno più basso inattivo.

Combinazioni valide (ABC): 000, 100, 110, 111. Cioè le righe 0, 4, 6 e 7.
La lampada si accende nelle altre: F = Σm(1, 2, 3, 5).
In modo equivalente: F = ΠM(0, 4, 6, 7).
Semplifica: m₁ + m₃ = AC, m₁ + m₅ = BC, m₂ + m₃ = AB. Usando m₁ e m₃ due volte (idempotenza), F = BC + AB.

Controlla: la riga 1 (001) dà BC = 1; la riga 2 (010) dà AB = 1; la riga 3 (011) dà AB = 1; la riga 5 (101) dà BC = 1. In 000, 100, 110 e 111 entrambi i termini valgono 0. Si legge "C attivo senza B" oppure "B attivo senza A".

Il complemento di una funzione

Se F = Σm(1, 3, 6, 7), il suo complemento vale 1 dove F vale 0: F = Σm(0, 2, 4, 5). Questo è utile quando vuoi la POS semplificata: semplifichi F come somma di prodotti e poi applichi De Morgan. Per esempio, F = AC + AB (verificalo con le righe 0, 2, 4 e 5), e complementando si ottiene F = (A + C)(A + B). Se moltiplichi: AB + AC + BC, che per consenso è AB + AC, lo stesso risultato dell'esempio 1.

Per approfondire queste manipolazioni ripassa l'algebra di Boole; per semplificare in modo grafico, prosegui con le mappe di Karnaugh.

Errori comuni

Invertire la regola delle barre: nei mintermini è lo 0 ad avere la barra; nei maxtermini è l'1 ad averla.
Mettere in ΠM le righe in cui la funzione vale 1. ΠM elenca gli zeri, Σm elenca gli uni.
Cambiare l'ordine delle variabili tra la tabella e l'equazione. Con l'ordine C, B, A la riga "5" non è più la stessa.
Dimenticare una variabile in un termine canonico. Un mintermine di quattro variabili ha sempre quattro letterali; se ne ha meno, è già semplificato e non è canonico.

Provalo nel simulatore

Il modulo della tabella di verità ti permette di inserire una funzione riga per riga e di vedere subito le sue forme canoniche e l'equazione semplificata, così puoi controllare ogni passo che fai a mano.

Crea una tabella con tre ingressi e un'uscita.
Segna con 1 le righe 1, 3, 6 e 7 dell'esempio 1 e lascia le altre a 0.
Osserva le espressioni Σm e ΠM che vengono generate e confrontale con le tue.
Converti la tabella in circuito e cambia gli ingressi per confermare che l'uscita segue la tabella.
Ripeti con il problema del serbatoio e verifica che la lampada si accenda solo nelle combinazioni impossibili.

Esercizi

Scrivi il mintermine m₉ e il maxtermine M₉ di una funzione di quattro variabili A, B, C, D.
Risposta
9 = 1001. m₉ = ABCD e M₉ = A + B + C + D.
Se F(A, B, C) = Σm(0, 1, 5), scrivi F in notazione ΠM.
Risposta
F = ΠM(2, 3, 4, 6, 7).
Ricava la somma di prodotti canonica di una funzione di due variabili che vale 1 solo quando A e B sono uguali, e semplificala se possibile.
Risposta
F = Σm(0, 3) = AB + AB. Non si riduce: è la XNOR.
Scrivi il prodotto di somme canonico di F(A, B, C) = Σm(1, 2, 3, 4, 5, 6, 7).
Risposta
Vale 0 solo nella riga 0, quindi F = ΠM(0) = A + B + C. Una sola OR a tre ingressi.