ElectroYou - la comunità dei professionisti del mondo elettrico

La riduzione, o minimizzazione, delle funzioni booleane (prima parte)

In LogicBignami (IV) abbiamo visto, dall'analisi dei mintermini o dei maxtermini, come sia possibile ricavare la funzione booleana della variabile d'uscita $O \;$ realtiva ad una qualsiasi tabella della verità.

Le funzioni così ottenute vengono definite in formato canonico in quanto ogni termine prodotto logico (nel caso dei mintermini) o somma logica (nel caso dei maxtermini) contiene sempre tutte le variabili d'ingresso da $I_0 \;$ a $I{n} \;$ .

Così, ad esempio, le funzioni:

$O = I_0 \; I_1 \; \overline {I_2} + I_0 \; \overline {I_1} \; I_2 + \overline {I_0} \; I_1 \; I_2$

e

$O = (I_0 + I_1 + I_2) \cdot (\overline {I_0} + I_1 + I_2) \cdot (I_0 + \overline {I_1} + I_2) \cdot (I_0 + I_1 + \overline {I_2}) \cdot$
$\cdot (\overline {I_0} + \overline {I_1} + \overline {I_2})$

sono entrambe in formato canonico in quanto in tutti i termini sono sempre presenti tutte e tre le variabili $I_0 \;$ , $I_1 \;$ , e $I_2 \;$ seppur diversamente complementate.

Da queste funzioni logiche in formato canonico abbiamo visto, nell'articolo precedente riguardanti le porte logiche EX-OR e EX-NOR (LogicBignami (V)), come sia possibile ricavarne il circuito digitale (in logica AOI, NAND o NOR) che la realizzi.

Non sempre, però, la funzione logica in formato canonico trovata è quella che permetterebbe di realizzare un circuito digitale con il minor numero di componenti, e variabili booleane, possibile perchè, come andremo a vedere, spesso, tali funzioni possono essere ridotte o minimizzate.

Per riduzione o minimizzazione di una funzione logica si intendono tutta una serie di processi che permettono, alla fine, di trovarne una equivalente, ossia che "copra" i medesimi stati logici di quella originale, operando, però, su un numero ridotto di variabili booleane d'ingresso per singolo prodotto logico (nel caso di funzioni booleane in formato somma logica di prodotti logici) o per singola somma logica (nel caso di funzioni booleane in formato prodotto logico di somme logiche), ed, eventualmente, anche su un numero ridotto di termini stessi.

I termini che compaiono nelle formule booleane ridotte vengono definiti come:
- Implicanti per le funzioni booleane formate da somme logiche di prodotti logici, ossia per denominare i mintermini ridotti
- Implicati per le funzioni booleane formate da prodotti logici di somme logiche, ossia per denominare i maxtermini ridotti.

Più specificatamente gli implicanti rappresentano il prodotto logico con il minimo numero possibile di varibili booleane che determinano, nella funzione booleana a cui appartengono tali variabili, uno stato logico 1.

Viceversa gli implicati rappresentano la somma logica con il minimo numero possibile di variabili booleane che determina, nella funzione booleana a cui appartengono tali variabili, uno stato logico 0.

Di seguito esamineremo tre sistemi di riduzione di una funzione booleana: il metodo algebrico, il metodo delle mappe o di Karnaugh e il metodo della tabulazione o di Quine-McCluskey.

La riduzione algebrica

La riduzione per via algebrica si avvale delle proprietà e teoremi dell'algebra booleana viste in LogicBignami (II).

Questo sistema è sempre applicabile ma, in alcuni casi, potrebbe risultare difficoltoso trovare il procedimento necessario alla riduzione della funzione booleana data e dire se quella ottenuta sia effettivamente la minima possibile.

Le proprietà e i teoremi dell'algebra booleana, generalmente più utilizzati sono:

Idempotenza
$f_A(x) \cdot f_A(x) = f_A(x)$

$f A (x) + f A (x) = f A (x)$

Proprietà distributiva
$f_A(x) \cdot (f_B(x) + f_C(x)) = (f_A(x) \cdot f_B(x)) + (f_A(x) \cdot f_C(x))$

$f_A(x) + (f_B(x) \cdot f_C(x)) = (f_A(x) + f_B(x)) \cdot (f_A(x) + f_C(x))$

Legge dell'assorbimento
$f_A(x) \cdot (f_A(x) + f_B(x)) = f_A(x)$

$f_A(x) + (f_A(x) \cdot f_B(x)) = f_A(x)$

Elemento neutro
$f_A(x) \cdot 1 = f_A(x)$

$f A (x) + 0 = f A (x)$

Elemento assorbente
$f_A(x) \cdot 0 = 0$

$f A (x) + 1 = 1$

Complementarietà
$f_A(x) \cdot \overline {f_A(x)} = 0$

$f_A(x) + \overline {f_A(x)} = 1$

In pratica si dovranno cercare, nella funzione booleana da ridurre, se esistono dei mintermini (o maxtermini) che contengano variabili booleane che siano tra loro complementari e se, a questi mintermini (o maxtermini), sia possibile applicare la proprietà distributiva in modo da raccogliere tali variabili rendendole, così, elementi neutri e quindi eliminabili dalla composizione del mintermine (o maxtermine) stesso: anche la presenza di elementi assorbenti ci permetterebbe di eliminare completamente un mintermine (o maxtermine) dalla funzione stessa.

Per meglio comprendere il procedimento da attuare, facciamo un paio di esempi, prendendo in esame i due casi più comuni, e cioè quando si parte da una tabella della verità, oppure quando si ha a disposizione, direttamente, la funzione booleana da ridurre, anche se, in questo caso, potremmo risalire, comunque, alla tabella della verità che l'ha generata e da lì procedere come il primo caso.

Riduzione algebrica di una funzione booleana data la sua tabella della verità

Consideriamo la seguente tabella della verità a quattro variabili

$I 0$	$I 1$	$I 2$	$I 3$	$O$
0	0	0	0	0
1	0	0	0	0
0	1	0	0	0
1	1	0	0	0
0	0	1	0	1
1	0	1	0	1
0	1	1	0	0
1	1	1	0	0
0	0	0	1	0
1	0	0	1	0
0	1	0	1	1
1	1	0	1	1
0	0	1	1	1
1	0	1	1	1
0	1	1	1	1
1	1	1	1	1

Da questa, considerando i mintermini relativi allo stato logico 1, della variabile d'uscita $O \;$ , ricaviamo la seguente funzione booleana in formato canonico, come somma logica di 8 prodotti logici ognuno composto da quattro variabili booleane:

$O = \overline {I_0} \; \overline {I_1} \; I_2 \; \overline {I_3} + I_0 \; \overline {I_1} \; I_2 \; \overline {I_3} + \overline {I_0} \; I_1 \; \overline {I_2} \; I_3 + I_0 \; I_1 \; \overline {I_2} \; I_3 + \overline {I_0} \; \overline {I_1} \; I_2 \; I_3 + I_0 \; \overline {I_1} \; I_2 \; I_3 +$
$+ \overline {I_0} \; I_1 \; I_2 \; I_3 + I_0 \; I_1 \; I_2 \; I_3$

Se volessimo realizzarla come circuito in logica AOI avremmo bisogno di una porta logica OR ad 8 ingressi, ai quali andranno collegate 8 porte logiche AND a 4 ingressi che manipoleranno, ognuna, le quattro variabili booleane d'ingresso $I_0\;$ , $I_1 \;$ , $I_2 \;$ e $I_3 \;$ variamente complementate, ottenendo il seguente schema di collegamento:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Analizziamo, allora, la funzione booleana in formato canonico, per vedere se può essere ridotta e, conseguentemente, se è possibile ottenere un circuito più semplice.

Notiamo che le seguenti coppie di mintermini presentano parte delle variabili booleane d'ingresso comuni e una variabile, una volta "normale" e una volta complementata:

coppia 1	coppia 2	coppia 3	coppia 4
$\overline {I_0} \; \overline {I_1} \; I_2 \; \overline {I_3}$	$\overline {I_0} \; I_1 \; \overline {I_2} \; I_3$	$\overline {I_0} \; \overline {I_1} \; I_2 \; I_3$	$\overline {I_0} \; I_1 \; I_2 \; I_3$
$I_0 \; \overline {I_1} \; I_2 \; \overline {I_3}$	$I_0 \; I_1 \; \overline {I_2} \; I_3$	$I_0 \; \overline {I_1} \; I_2 \; I_3$	$I_0 \; I_1 \; I_2 \; I_3$

Dalla prima coppia applicando, in sequenza, la proprietà distributiva, la regola della complementarietà e la regola dell'elemento neutro otteniamo:

$\overline {I_1} \; I_2 \; \overline {I_3} \cdot (\overline {I_0} + I_0) = \overline {I_1} \; I_2 \; \overline {I_3} \cdot 1 = \overline {I_1} \; I_2 \; \overline {I_3}$

analogamente per le restanti tre coppie:

$I_1 \; \overline {I_2} \; I_3 \cdot (\overline {I_0} + I_0) = I_1 \; \overline {I_2} \; I_3 \cdot 1 = I_1 \; \overline {I_2} \; I_3$

$\overline {I_1} \; I_2 \; I_3 \cdot (\overline {I_0} + I_0) = \overline {I_1} \; I_2 \; I_3 \cdot 1 = \overline {I_1} \; I_2 \; I_3$

$I_1 \; I_2 \; I_3 \cdot (\overline {I_0} + I_0) = I_1 \; I_2 \; I_3 \cdot 1 = I_1 \; I_2 \; I_3$

La nostra funzione booleana si è quindi così ridotta alla somma logica di 4 implicanti composti, ognuno, di tre variabili booleane:

$O = \overline {I_1} \; I_2 \; \overline {I_3} + I_1 \; \overline {I_2} \; I_3 + \overline {I_1} \; I_2 \; I_3 + I_1 \; I_2 \; I_3$

Anche in questo caso vediamo che esistono coppie di implicanti a loro volta riducibili:

coppia 1	coppia 2
$\overline {I_1} \; I_2 \; \overline {I_3}$	$I_1 \; \overline {I_2} \; I_3$
$\overline {I_1} \; I_2 \; I_3$	$I_1 \; I_2 \; I_3$

Applicando le proprietà e le regole precedentemente accennate, otteniamo:

$\overline {I_1} \; I_2 \cdot (\overline {I_3} + I_3) = \overline {I_1} \; I_2 \cdot 1 = \overline {I_1} \; I_2$

$I_1 \; I_3 \cdot (\overline {I_2} + I_2) = I_1 \; I_3 \cdot 1 = I_1 \; I_3$

Alla fine la nostra funzione booleana dell'uscita si è notelvolmente ridotta, ed equivale alla somma logica di 2 soli implicanti a 2 varibili booleane:

$O = \overline {I_1} \; I_2 + I_1 \; I_3$

che può essere realizzata con un circuito molto più semplice: una porta logica OR a 2 ingressi, ai quali sono collegate 2 porte logiche AND che manipolano, ognuna, solo 2 variabili.</br>

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Riduzione algebrica di una funzione booleana data la funzione stessa

Consideriamo la seguente funzione booleana: $O = I_0 \; I_1 \; \overline {I_2} + \overline {I_0} \; I_1 \;$ e vediamo se sia possibile ridurla.

Escludiamo il fatto di ricavarne la tabella della verità, perchè si ricadrebbe nel procedimento appena descritto, e vediamo come operare direttamente alla sua riduzione.

La prima cosa da fare, non essendo in formato canonico, è trasformarla in tale forma, e per farlo, in pratica, si devono ripercorrere i passi di riduzione, appena visti, a ritroso.

La funzione booleana considerata "manipola" tre variabili booleane d'ingresso ( $I_0 \;$ , $I_1 \;$ e $I 2$ ) e, come si può notare, abbiamo un implicante che ne utilizza solo due: $\overline {I_0} \; I_1 \;$

Per aggiungere una variabile booleana a questo implicante (e trasformarlo, di fatto, in un mintermine) dobbiamo ricordare come ciò sia possibile senza modificarne la sua funzione booleana: essendo un prodotto logico, l'unico modo è aggiungere un elemento neutro al prodotto logico, e cioè uno stato logico 1:

$\overline {I_0} \; I_1 = \overline {I_0} \; I_1 \cdot 1$

Visto che a questo implicante, per essere trasformato in mintermine, manca la variabile booleana $I_2 \;$ , possiamo ricorrere alla proprietà della complementarietà e trasformare quell'1 logico nella somma logica tra la variabile booleana $I_2 \;$ e il suo complemento:

$\overline {I_0} \; I_1 \cdot 1 = \overline {I_0} \; I_1 \cdot (I_2 + \overline {I_2}) = \overline {I_0} \; I_1 \; I_2 + \overline {I_0} \; I_1 \; \overline {I_2}$

Quindi la nostra formula booleana di partenza, in formato canonico, diventa:

$O = I_0 \; I_1 \; \overline {I_2} + \overline {I_0} \; I_1 \; I_2 + \overline {I_0} \; I_1 \; \overline {I_2}$

In questa funzione booleana si possono notare due coppie di mintermini che presentano un gruppo di variabili comune e una variabile "normale" e complementata:

coppia 1	coppia 2
$I_0 \; I_1 \; \overline {I_2}$	$\overline {I_0} \; I_1 \; I_2$
$\overline {I_0} \; I_1 \; \overline {I_2}$	$\overline {I_0} \; I_1 \; \overline {I_2}$

In pratica abbiamo un mintermine ( $\overline {I_0} \; I_1 \; \overline {I_2} \;$ ) che risulta riducibile con entrambi gli altri due, però, così com'è "costruita" la funzione booleana, si può solo effettuare una delle due riduzioni e si tornerebbe ad un formato simile a quello di partenza: un mintermine e un implicante.

Ad una prima analisi parrebbe, quindi, che la funzione booleana di partenza, sia già ridotta.

In realtà, sfruttando la proprietà dell'idempotenza, possiamo aggiungere, alla funzione booleana in formato canonico un mintermine uguale a $\overline {I_0} \; I_1 \; \overline {I_2} \;$ , in modo da poter effettuare la riduzione su entrambe le coppie precedentmente indicate:

$O = I_0 \; I_1 \; \overline {I_2} + \overline {I_0} \; I_1 \; I_2 + \overline {I_0} \; I_1 \; \overline {I_2} + \overline {I_0} \; I_1 \; \overline {I_2}$

Quindi, come avevamo già visto, applicando in sequenza la proprietà distributiva, la regola della complementarietà e la regola dell'elemento neutro ad entrambe le coppie, otteniamo:

$I_1 \; \overline {I_2} \cdot (I_0 + \overline {I_0}) = I_1 \; \overline {I_2} \cdot 1 = I_1 \; \overline {I_2}$

$\overline {I_0} \; I_1 \cdot (I_2 + \overline {I_2}) = \overline {I_0} \; I_1 \cdot 1 = \overline {I_0} \; I_1$

da cui si ricava la funzione booleana ridotta in somma logica di 2 implicanti a 2 variabili booleane: $O = I_1 \; \overline {I_2} + \overline {I_0} \; I_1$ .

Come si vede, entrambi gli implicanti hanno la variabile $I_1 \;$ in comune, per cui, applicando ancora una volta la proprietà distributiva, otteniamo la funzione booleana ridotta:

$O = I_1 \cdot (\overline {I_2} + \overline {I_0})$ .

In questo modo siamo passati dal realizzare la funzione booleana di partenza, con il circuito A, a quello della stessa, ma ridotta, con il circuito B.

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Ma guardiamo ancora un'attimo la funzione booleana ridotta: $O = I_1 \cdot (\overline {I_2} + \overline {I_0})$ .

Ricordando le Leggi di De Morgan, la somma logica $\overline {I_2} + \overline {I_0}$ la possiamo trasformare nel prodotto logico $\overline {I_2 \; I_0}$ e in questo modo otteniamo la funzione booleana $O = I_1 \; \overline {I_2 \; I_0}$ , che, in pratica ci risparmierebbe una porta NOT.

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

A questo punto, volendo evitare di utilizzare due tipologie di porte logiche differenti, visto che abbiamo solo prodotti logici, e uno di questi è complementato, possiamo pensare di realizzare il tutto in logica NAND utilizzando sempre tre sole porte logiche:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Con quest'ultimo caso concludiamo la presentazione della riduzione algebrica di una funzione booleana, prossimamente analizzeremo come procedere per via "grafica" tramite le mappe di Karnaugh.

LogicBignami - Indice articoli correlati

ElectroYou - la comunità dei professionisti del mondo elettrico

LogicBignami (VI)

La riduzione, o minimizzazione, delle funzioni booleane (prima parte)

La riduzione algebrica

Inserisci un commento

Argomenti correlati

Tag Cloud

Informazioni

Seguici

Pubblicità

Credits

$I 0$	$I 1$	$I 2$	$I 3$	$O$
0	0	0	0	0
1	0	0	0	0
0	1	0	0	0
1	1	0	0	0
0	0	1	0	1
1	0	1	0	1
0	1	1	0	0
1	1	1	0	0
0	0	0	1	0
1	0	0	1	0
0	1	0	1	1
1	1	0	1	1
0	0	1	1	1
1	0	1	1	1
0	1	1	1	1
1	1	1	1	1

$I 0$	$I 1$	$I 2$	$I 3$	$O$
0	0	0	0	0
1	0	0	0	0
0	1	0	0	0
1	1	0	0	0
0	0	1	0	1
1	0	1	0	1
0	1	1	0	0
1	1	1	0	0
0	0	0	1	0
1	0	0	1	0
0	1	0	1	1
1	1	0	1	1
0	0	1	1	1
1	0	1	1	1
0	1	1	1	1
1	1	1	1	1

$I 0$	$I 1$	$I 2$	$I 3$	$O$
0	0	0	0	0
1	0	0	0	0
0	1	0	0	0
1	1	0	0	0
0	0	1	0	1
1	0	1	0	1
0	1	1	0	0
1	1	1	0	0
0	0	0	1	0
1	0	0	1	0
0	1	0	1	1
1	1	0	1	1
0	0	1	1	1
1	0	1	1	1
0	1	1	1	1
1	1	1	1	1