Cos'è ElectroYou | Login Iscriviti

ElectroYou - la comunità dei professionisti del mondo elettrico

5
voti

LogicBignami (VI)

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)

fA(x) + fA(x) = fA(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)

fA(x) + 0 = fA(x)

Elemento assorbente
f_A(x) \cdot 0 = 0

fA(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

I0
I1
I2
I3
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:

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>

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 I2) 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.

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.

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:

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

2

Commenti e note

Inserisci un commento

di ,

Grazie di cuore...

Rispondi

di ,

LogicBignami .. un lavorone .. Bravo Max!!

Rispondi

Inserisci un commento

Per inserire commenti è necessario iscriversi ad ElectroYou. Se sei già iscritto, effettua il login.