ElectroYou - la comunità dei professionisti del mondo elettrico

Indice

1 La riduzione, o minimizzazione, delle funzioni booleane (terza parte)

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

Dopo aver visto la riduzione di una funzione booleana mediante il metodo algebrico (LogicBignami (VI)) e mediante il metodo "grafico" delle mappe di Karnaugh (LogicBignami (VII)) analizziamo, adesso, un metodo, cosiddetto "tabellare", il Quine-McCluskey.

PREMESSA Questo metodo non rientrava nel mio percorso di studi da Istituto Tecnico Industriale, per cui, prima di riassumerlo l'ho dovuto studiare io stesso. Se trovate qualche lacuna o mancanza siete invitati a segnalarlo, tenendo presente che il target di questi miei articoli sono, comunque, studenti delle superiori e appassionati. Grazie.

Questo metodo si presta ad essere tradotto in una routine da far svolgere ad un elaboratore dati, questo permette la riduzione di una funzione booleana con un numero qualsiasi (*) di variabili booleane, a differenza del metodo utilizzante le mappe di Karnaug che, come abbiamo detto nel precedente articolo LogicBignami (VII), oltre le 5 variabili booleane si complica eccessivamente.

(*) In realtà le tempistiche per la soluzione del problema di riduzione della funzione booleana con il metodo Quine-McCluskey cresce in maniera esponenziale all'aumentare del numero di variabili booleane da trattare, tant'è che, al di spora della decina di variabili booleane, convengono altri sistemi di riduzione di tipo euristico, la cui descrizione, però, esula l'impostazione data a questa serie di articoli divulgativi.

Il metodo di Quine - McCluskey si applica a funzioni booleane sottoforma di somma logica di prodotti logici e consta, essenzialmente, di due passaggi principali:

1) Eliminare più variabili booleane possibili dai singoli termini prodotto logico applicando ripetutamente la regola:

$K \cdot Y + K \cdot \overline {Y} = K$

dove

$K \cdot Y \;$ e $K \cdot \overline Y \;$ rappresentano due termini prodotto logico che differiscono unicamente per una variabile booleana, $Y \;$ , che, in un termine sarà normale e nell'altro risulterà complementata.

Ad esempio, considerando i due termini

$I_0 \; \overline {I_1} \; I_2 \; \overline {I_3}$

$I_0 \; \overline {I_1} \; I_2 \; I_3$

notiamo che i due differiscono solo per la variabile booleana $I_3 \;$ che, in un termine è normale e nell'altro è negata, per tanto, applicando la suddetta regola otterremo:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Da notare che il risultato a cui porta questa regola non cì è nuovo, in quanto l'avevamo già visto in LogicBignami VI con la riduzione algebrica delle funzioni booleane, con l'applicazione della proprietà distributiva, della regola della complementarietà e della regola dell'elemento neutro.

Il termine $K \;$ , risultato della semplificazione reiterata, quando non risulta più riducibile con nessun altro termine prodotto logico, prende il nome di implicante primo.

2) Usare una grafico che ci permette di selezionare il minimo numero di implicanti primi che, sottoposti a somma logica, forniscono la stessa funzione logica booleana di partenza con un numero ridotto di termini e variabili booleane.

La ricerca degli implicanti primi

Come abbiamo detto il metodo Quinde - McCluskey si applica a funzioni booleane somma logica di prodotti logici, e, nello specifico, in formato canonico (nel caso la funzione booleana non sia in tale formato, la si può ricavare secondo quanto visto in LogicBignami VI).

Il formato canonico ci permette di analizzare tutte le possibili copie di mintermini alle quali sia possibile applicare la regola appena citata:

$K \cdot Y + K \cdot \overline {Y} = K$

Vediamo allora come trovare tutti gli implicanti primi, ossia tutti i termini prodotto logico ridotti al minimo numero di variabili booleane possibile.

Innanzi tutto si costruisce una tabella suddividendo i mintermini, della funzione booleana da ridurre, in gruppi in base al numero di variabili booleane in stato logico $1 \;$ .
In pratica avremo:

- il gruppo 0 conterrà il mintermine con tutte le variabili booleane in stato logico $0$
- il gruppo 1 conterrà tutti i mintermini con una variabile booleana in stato logico $1$
- il gruppo 2 conterrà tutti i mintermini con due variabili booleane in stato logico $1$
- il gruppo 3 conterrà tutti i mintermini con tre variabili booleane in stato logico $1$
- ... e così via fino al gruppo n, dove "n" è il numero delle variabili booleane presenti nei mintrmini della funzione booleana da ridurre, che conterrà il mintermine con tutte le variabili booleane in stato logico $1$

Come si è detto questa tabella conterrà solo i mintermini di cui è composta la nostra funzione booleana da ridurre, quindi, non è detto che tutti i gruppi sopra indicati contengano dei termini.

Facciamo un esempio, consideriamo la seguente tabella della verità è ricabimone la funzione booleana in formato canonico:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Dalla sommatoria dei mintermini in stato logico $1 \;$ , evidenziati in rosso, deriva la seguente funzione booleana in formato canonico:

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

Raggruppiamo, allora, questi mintermini, in gruppi come li abbiamo poc'anzi definiti:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Con questa tabella possiamo notare che i termini prodotto logico da comparare devono appartenere per forza a due gruppi adiacenti (0 e 1, 1 e 2, 2 e 3) perchè solo in questo frangente si può riscontrare che, tra quello appartenente ad un gruppo e quello del gruppo immediatamente successivo, sussiste la variazione di stato logico di un'unica variabile booleana.

Iniziamo, quindi a comparare il mintermine $m_0 \;$ , del gruppo 0, con i mintermini $m_1 \;$ , $m_2 \;$ e $m_8 \;$ del gruppo 1.

Come possiamo notare tutte le coppie $[m_0 \; m_1] \;$ , $[m_0 \; m_2] \;$ e $[m_0 \; m_8] \;$ differiscono tutte per lo stato logico di un'unica variabile booleana (rispettivamente $I_0 \;$ , $I_1 \;$ e $I_3 \;$ ).

Applicando, allora, a queste coppie di mintermini, la regola $K \cdot Y + K \cdot \overline {Y} = K \;$ , possiamo ricavare la seguente tabella, dove le variabili booleane eliminate dai mintermini sono state marcate con un $- \;$ :

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

In questa tabella, con i termini $K_{[a,b]} \;$ si intendono gli implicanti derivanti dal confronto dei mintermini $m_a \;$ e $m_b \;$ .

A questo punto passiamo al gruppo 1 e confrontiamo ogni suo mintermine con quelli presenti nel gruppo 2 in modo da trovare tutte le possibili coppie che differiscono per lo stato logico di un'unica variabile booleana, operando come abbiamo appena visto nel confornto tra il gruppo 0 e il gruppo 1, e lo stesso facciamo confrontando ogni mintermine del gruppo 2 con quelli appartenenti al gruppo 3.

Alla fine otterremo una seconda tabella così composta:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

E' utile evidenziare i mintermini che sono stati accoppiati almeno una volta (qui sono stati segnati con un asterisco) perchè quelli che non possono essere accoppiati, quindi quelli che non possono essere ridotti, saranno degli implicanti primi e finiranno, così come sono, nella formula della funzione booleana che sarà poi analizzata tramite il grafico degli implicanti primi.

Prendiamo, allora, questo secondo gruppo di tabelle di implicanti e ripetiamo i passaggi appena visti confrontando, questa volta, gli implicanti appartenenti a gruppi adiacenti, sempre al fine di trovare le coppie che differiscono per lo stato logico di un'unica variabile booleana.

Il confronto tra le diverse coppie di implicanti può risultare più semplice se si considera anche il simbolo $- \;$ come elelmento dell'implicante stesso:

Ad esempio, se confrontiamo la coppia $K_{[0, \; 1]} \;$ e $K_{[8, \; 9]}$ risulta subito evidente che l'unica variabile che differisce di stato logico è $I 3$

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Quindi, come detto, ripetendo i passaggi di confronto e riduzione, anche sui gruppi della tabella di implicanti appena ottenuta, ricaviamo questa ulteriore tabella formata da due soli gruppi, dove con $K_{[a,b] \;[c,d]} \;$ evidenziamo le coppie di implicanti $K_{[a,b]} \;$ e $K_{[c,d]} \;$ ridotte:

Gli implicanti possono anche essere rappresentati solo includendo all'interno delle parentesi l'elenco dei mintermini che essi riducono: [a, b, c, d]. Questo è sicuramente vantaggioso quando il numero delle semplificazioni aumenta.

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Vediamo che tre implicanti (indicati dalla freccia blu), $K_{[1, \;5]} \;$ equivalente a $I_0 \; \overline I_1 \; \overline I_3 \;$ , $K_{[5, \;7]} \;$ equivalente a $I_0 \; I_2 \; \overline I_3 \;$ e $K_{[6, \;7]} \;$ equivalente a $I_1 \; I_2 \; \overline I_3 \;$ non fanno coppia con nessun altro implicante appartenente ad un gruppo adiacente, per cui, non potendo più essere ridotti, sono degli implicanti primi e finiranno direttamente nella formula della funzione booleana con questo "livello" di riduzione.

Nell'ultima tabella, formata da due soli gruppi di implicanti, vediamo che non è possibile trovare delle coppie confrontabili che differiscano solamente per lo stato logico di un'unica variabile booleana, quindi ognuno di essi è un implicante primo.

In pratica quando non è più possibile trovare coppie di implicanti riducibili, il processo di confronto si arresta e tutti gli implicanti rimasti saranno considerati implicanti primi.

Notiamo, inoltre, la presenza, nel primo gruppo, di due coppie di implicanti uguali e, nel secondo gruppo di una coppia di implicanti uguali (indicati con le lettere a-a, b-b e c-c): nella funzione booleana ne verrà inserito uno solo di ognuna, in virtù della regola dell'idempotenza vista in LogicBignami II.

Quindi la nostra funzione booleana ridotta equivarrà alla somma logica di tutti gli implicanti primi risultanti dalle suddette tabelle:

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

Rispetto alla funzione booleana di partenza, questa potrebbe sembrare già ridotta, in realtà si può notare, che diversi termini contengono variabili booleane con il medesimo stato logico e quindi potrebbero essere, in parte, ulteriormente ridotti.

Infatti la sola ricerca degli implicanti primi porta ad una funzione booleana che contiene termini che hanno il minor numero di variabili booleane possibile, per singolo termine, ma non il minor numero di termini possibile.

Per ottenere la funzione booleana ridotta finale, sia come variabili booleane manipolate che come numero di termini che la compongono, si deve procedere con il secondo passo del metodo Quine-McCluskey, ossia utilizzare il grafico degli implicanti primi.

Utilizzo del grafico degli implicanti primi

Dopo aver visto come trovare tutti gli implicanti primi, mostriamo adesso il metodo per estrarre da questi il minimo numero di termini che ci permetteranno di esprimere la medesima funzione logica di partenza.

Per far ciò dobbiamo costruire un grafico dove metteremo in relazione gli implicanti primi, a cui assegneremo le righe del grafico, con i relativi mintermini della funzione booleana di partenza, a cui assegneremo le colonne.

Riprendiamo allora la nostra funzione booleana, in formato canonico, utilizzata all'inizio dell'esempio:
$O = \overline {I_0} \; \overline {I_1} \; \overline {I_2} \; \overline {I_3} + I_0 \; \overline {I_1} \; \overline {I_2} \; \overline {I_3} + \overline {I_0} \; I_1 \; \overline {I_2} \; \overline {I_3} + I_0 \; \overline {I_1} \; I_2 \; \overline {I_3} + \overline {I_0} \; I_1 \; I_2 \; \overline {I_3} +$
$+ I_0 \; I_1 \; I_2 \; \overline {I_3} + \overline {I_0} \; \overline {I_1} \; \overline {I_2} \; I_3 + I_0 \; \overline {I_1} \; \overline {I_2} \; I_3 + \overline {I_0} \; I_1 \; \overline {I_2} \; I_3 + \overline {I_0} \; I_1 \; I_2 \; I_3$

che corrisponde alla sommatoria dei seguenti mintermini che, come detto, rappresenteranno gli indici delle colonne del nostro grafico:

$O = m 0 + m 1 + m 2 + m 5 + m 6 + m 7 + m 8 + m 9 + m 10 + m 14$

Mentre, come abbiamo visto, gli implicanti primi, di questa funzione logica sono:

$K_{[1,5]} = I_0 \; \overline I_1 \; \overline I_3$
$K_{[5,7]} = I_0 \; I_2 \; \overline I_3$
$K_{[6,7]} = I_1 \; I_2 \; \overline I_3$
$K_{[0,1][8,9]} = \overline I_1 \; \overline I_2$
$K_{[0,2][8,10]} = \overline I_0 \; \overline I_2$
$K_{[2,6][10,14]} = \overline I_0 \; I_1$

che rappresenteranno, invece, gli indici delle righe del grafico, che, a questo punto, avrà il seguente aspetto:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Ricordiamo che l'implicante, qualsiasi, $K_{[a,b][c,d]...} \;$ è derivato dalla semplificazione della somma logica di mintermini indicati dai "pedici", così, ad esempio:

$K [0,1][8,9] = K [0,1] + K [8,9] = (m 0 + m 1) + (m 8 + m 9) =$
$= (\overline {I_0} \; \overline {I_1} \; \overline {I_2} \; \overline {I_3} + I_0 \; \overline {I_1} \; \overline {I_2} \; \overline {I_3}) + (\overline {I_0} \; \overline {I_1} \; \overline {I_2} \; I_3 + I_0 \; \overline {I_1} \; \overline {I_2} \; I_3) = \overline {I_1} \; \overline {I_2}$

Nota: Ho tralasciato i passaggi intermedi della semplificazione in quanto già visti più volte, e quindi dovrebbero già essere assimilati.

Per questo, nel suddetto grafico, aggiungiamo una "x" per segnare, in ogni riga "puntata" da ogni implicante primo, quali mintermini ha ridotto:

ad esempio, nella riga relativa a $K_{[0,1][8,9]} \;$ metteremo una "x" nelle colonne dei mintermini $m_0 \; m_1 \; m_8 \; m_9$

Il nostro grafico risulterà, allora, così compilato e completo:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

A questo punto possiamo iniziare la fase di semplificazione: per prima cosa controlliamo se esistono colonne con un'unica "x", se esistono, l'implicante primo, della riga corrispondente a dove è presente quell'unica "x", diventa essenziale, perchè è l'unico che riduce quel mintermine la cui colonna contiene quell'unica "x".

Gli eventuali implicanti primi essenziali così trovati finiscono direttamente nella formula finale della nostra funzione booleana ridotta.

Nel nostro grafico vediamo che ci sono due colonne che hanno un'unica "x" (evidenziate con una cerchiatura), quella relativa al mintermine $m_9 \;$ e quella relativa al mintermine $m 14$ .

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

In particolare:

- Alla "x" della colonna $m_9 \;$ corrisponde la riga dell'implicante primo $K_{[0,1][8,9]} = \overline I_1 \; \overline I_2$
- Alla "x" della colonna $m_14 \;$ corrisponde la riga dell'implicante primo $K_{[2,6][10,14]} = \overline I_0 \; I_1$

questi diventano, quindi, implicanti primi essenziali e entrano direttamente nella formula della funzione booleana ridotta: $O = \overline I_1 \; \overline I_2 + \overline I_0 \; I_1 + ...$

Selezionati gli eventuali implicanti primi essenziali, dal grafico vanno eliminati tutti gli elementi presenti sulle loro righe, come indicato di seguito:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Inoltre, in corrispondenza di ognuna di queste "x" eliminate nelle righe indirizzate dagli implicanti primi essenziali, elimineremo anche tutti gli elementi presenti nella corrispondente colonna, come evidenziato nella figura con le righe verticali verdi:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Da questo grafico, possiamo osservare che sono rimaste, non eliminate, due coppie di "x" appartenenti ai due mintermini $m_5 \;$ e $m_7 \;$ :

- Le due "x" del mintermine $m_5 \;$ ci indicano che quest'ultimo è ridotto dagli implicanti primi $K_{[1,5]} \;$ e $K_{[5,7]} \;$
- Le due "x" del mintermine $m 7$ , invece, ci indicano che quest'ultimo è ridotto dagli implicanti primi $K_{[5,7]} \;$ e $K_{[6,7]} \;$

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Di questi implicanti primi, vediamo che uno, $K_{[5,7]} \;$ , ha entrambe queste "x" sulla sua riga: in pratica, dei tre citati, è l'unico a ridurre contemporaneamente sia il mintermine $m_5 \;$ che il mintermine $m_7 \;$ (cancellati dalla linea magenta), e, come abbiamo visto in precedenza, a questo punto possiamo eliminare anche gli altri elementi presenti nelle colonne $m_5 \;$ e $m_7 \;$ (linee verdi).

L'implicante primo $K_{[5,7]} = I_0 \; I_2 \; \overline I_3 \;$ diventa l'ultimo termine nella nostra formula ridotta della funzione booleana:

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

Per verificare che, effettivamente, questa funzione booleana ridotta, copra tutti gli stati logici di quella in formato canonico, possiamo ricavarne la tabella della verità confrontandone gli stati logici d'uscita con quelli presenti nella tabella della verità di partenza:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Come si può vedere gli stati logici sono esattamente gli stessi.

Prima di concludere la trattazione del metodo Quine-McCluskey, analizziamo un caso particolare che non porta ad una riduzione unica.

Il grafico degli implicanti primi, ciclico

Supponiamo di avere la seguente tabella della verità:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

La funzione booleana d'uscita, come somma logica di prodotti logici, è, come sappiamo, la somma dei seguenti mintermini: $O = m 0 + m 1 + m 2 + m 5 + m 6 + m 7$ .

Come fatto in precedenza, cerchiamo gli implicanti primi, suddividendo questi mintermini in gruppi e cercando, tra questi, le possibili riduzioni:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Tutti i mintermini riescono ad essere ridotti negli implicanti riportati nella tabella di destra ma, nessuno di questi può essere ulteriormente ridotto, infatti nessun implicante di un gruppo "trova" nel gruppo adiacente un altro che differisca per lo stato logico di un'unica variabile booleana: per tanto tutti questi diventeranno implicanti primi.

Costruiamoci, allora, il grafico degli implicanti primi:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

La prima cosa che salta all'occhio analizzando questo grafico è che, in nessuna colonna, è presente un'unica "x", ciò vuol dire che nessun implicante primo è un implicante primo essenziale.

Per ridurre il numero degli implicanti primi da inserire nella funzione booleana ridotta, a questo punto dovremmo cercare quelli che riducono, contemporaneamente più mintermini, in pratica dobbiamo vedere in quali righe sono presenti più "x".

Come si può vedere ogni riga contiene due "x": quindi non c'è un unico risultato di riduzione.

Potremmo, ad esempio, scegliere gli implicanti primi $K_{[0, 1]} \;$ , $K_{[2, 6]} \;$ e $K_{[5, 7]} \;$ in base alla seguente riduzione grafica:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

e quindi ottenere la funzione booleana ridotta, come somma logica di tali implicanti primi:

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

ma potremmo, ugualmente scegliere gli implicanti primi $K_{[0, 2]} \;$ , $K_{[1, 5]} \;$ e $K_{[6, 7]} \;$ operando quest'altra riduzione grafica:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

e otterremo, comunque, una funzione booleana validamente ridotta, come somma logica di tre termini:

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

Visto quest'ultimo esempio, abbiamo terminato la disamina della riduzione delle funzioni booleane anche con il metodo Quine-McCluskey.

Prima di analizzare alcuni circuiti combinatori d'uso comune e, per questo, realizzati anche come singolo componente elettronico integrato, vedremo, nel prossimo articolo, i sistemi di numerazione binaria e le principali operazioni ad esso collegate.

LogicBignami - Indice articoli correlati

ElectroYou - la comunità dei professionisti del mondo elettrico

LogicBignami (VIII)

Indice

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

La ricerca degli implicanti primi

Utilizzo del grafico degli implicanti primi

Il grafico degli implicanti primi, ciclico

Inserisci un commento

Argomenti correlati

Tag Cloud

Informazioni

Seguici

Pubblicità

Credits