Funzioni booleane

Volendo riprendere alcuni concetti intravisti nelle pagine precedenti possiamo definire:

Variabili booleane : sono variabili che possono assumere solo due valori distinti, 0, 1; vengono indicate con lettere maiuscole; come A, B, C.. .

Funzione booleana : è una funzione che dipende dai valori assunti dalle variabili booleane e quindi può assumere solo i valori 0, 1; possiamo indicare una generica funzione booleana come

Y=f(A,B,C)

Tabella della verità : la tabella della verità di una data funzione booleana esprime i valori assunti dalla stessa per tutte le possibili combinazioni delle sue variabili indipendenti.

La tabella della verità rappresenta una prima sintesi della rete combinatoria, non è detto però che l'espressione logica ottenuta rappresenti la funzione minima che realizza la rete combinatoria. Come per le coniche della geometria analitica, per esprimere una funzione booleana può esserci una forma canonica; per l'esattezza esistono due possibili forme canoniche .

1^a forma canonica : forma canonica della somma (forma AND-OR)

Abbiamo questa forma quando la funzione è costituita dalla somma logica di vari termini, ciascuno dei quali è dato dal prodotto logico di tutte le variabili indipendenti della funzione stessa. Ad es.

             è in forma canonica

                  non è in forma canonica perchè il secondo termine manca della variabile C.

In quest'ultimo caso abbiamo già visto come sia possibile riportare una funzione di questo tipo in forma canonica; basta moltiplicare il termine mancante della variabile per la stessa sommata del suo complemento.

questo possiamo farlo perchè per il teorema del complemento C+C=1; da cui

che è la funzione iniziale posta in forma canonica.

Per realizzare la forma AND-OR si rilevano dalla tabella della verità gli 1 della funzione; la funzione risultante sarà costituita da tanti termini quanti sono gli 1 della stessa, ciascun termine è dato dal prodotto logico di tutte le variabili di ingresso, in forma naturale se la variabile vale 1, in forma complementata se la variabile vale 0.

ciascun termine della funzione f si chiama mintermine ed è associato ad una combinazione dei valori delle variabili indipendenti che verificano (mandano a 1) la funzione logica di uscita Y. Anche se non è ancora stata semplificata, la funzione può in ogni caso essere associata ad un circuito.

gli indici dei mintermini sono in questo caso Y=∑(1, 2, 4).

2^a forma canonica : forma canonica del prodotto (forma OR-AND)

Abbiamo questa forma quando la funzione è costituita dal prodotto logico di vari fattori, ciascuno dei quali è dato dalla somma logica di tutte le variabili indipendenti della funzione stessa. Ad es.

          è in forma canonica

                    non è in forma canonica perchè nel primo fattore manca la variabile B

In questo caso, ciascun termine della funzione viene chiamato maxtermine. Per realizzare la forma canonica del prodotto, si rilevano dalla tabella della verità gli 0 della funzione, la funzione risultante sarà costituita da tanti fattori quanti sono gli 0 della stessa; ciascun fattore è dato dalla somma logica di tutte le variabili di ingresso, in forma naturale se la variabile è vale 0, in forma complementata se vale 1.
Ad es. prendiamo la precedente tabella dove avevamo come forma canonica della somma Y=∑(1, 2, 4); se vogliamo considerare la forma canonica del prodotto sarà Y=Π(0, 2, 3, 6, 7) dunque :

è chiaro che in questo caso la forma canonica della somma risulta la più semplice e conveniente da adottare, proprio perchè la quantità di 1 presenti in tabella per la funzione di uscita Y sono meno degli 0.
L'implementazione circuitale, ha un costo in termini di impiego di porte logiche, ma abbiamo visto che con l'utilizzo del metodo della mappe di karnaugh, la funzione e il circuito conseguente possono essere ulteriormente semplificati.

ottenendo la funzione risultante   

decisamente più semplice.

Le mappe di Karnaugh sono una tecnica grafica di minimizzazione che permette di passare direttamente dalla forma tabellare della funzione a quella minima. Si devono disegnare dei diagrammi (mappe) con tante caselle N quante sono le possibili configurazioni delle n variabili di ingresso cioè N=2ⁿ.  Negli esercizi eseguiti usiamo funzioni:
● a due variabili con una mappa a 4 caselle
● a tre variabili con una mappa a 8 caselle
●a quattro variabili con una mappa a 16 caselle.
esistono problemi di logica booleana che prevedono la presenza di un numero maggiore di variabili di ingresso, ci aspettiamo, in tal caso una maggiore laboriosità per l'esecuzione della minimizzazione, questo in considerazione del fatto che con
● cinque variabili, si deve avere una mappa a 32 caselle
● sei variabili, si deve avere una mappa a 64 caselle
per problemi che prevedono un numero ancora maggiore di variabili di ingresso l'utilizzo dei metodi grafici è sconsigliato, si consigliano invece metodi algebrici.

Mappe di Karnaugh a 5 variabili

Le mappe di Karnaugh con più di quattro variabili binarie devono essere costruite sempre rispettando la regola che nel passaggio da una casella a quella adiacente (contigua) sulla stessa riga o sulla stessa colonna deve cambiare una sola variabile.
Per quanto riguarda la semplificazione di una funzione a cinque variabili essa può essere fatta mediante una mappa di Karnaugh con 32 caselle oppure con due mappe da 16 caselle. Nel primo caso (come si vede nello schema seguente) sono da considerare adiacenti in aggiunta a quelle conosciute, anche le caselle simmetriche rispetto alla linea mediana verticale (rossa). Per esempio la casella 5 oltre ad essere adiacente alla 4, 1, 7, 13 è adiacente anche alla casella simmetrica 21.

Se vogliamo risolvere il problema con due mappe da 16 celle, oltre a tutte le relazioni di adiacenza già viste , ogni casella della mappa (a) in cui A vale sempre 0 è adiacente alla corrispondente della mappa in (b) in cui A vale sempre 1 e viceversa. Queste ultime adiacenze possono essere ben localizzate pensando di sovrapporre le due mappe e considerando adiacenti le caselle che corrispondono verticalmente.

Mappe di Karnaugh a 6 variabili

La semplificazione di una funzione logica a sei variabili binarie mediante il metodo delle mappe K incomincia a diventare piuttosto laboriosa, in quanto è necessario ricorrere ad una mappa di 64 caselle (2⁶=64) come quella nel disegno seguente in cui si hanno due assi di simmetria (verticale e orizzontale).

In alternativa, la minimizzazione può essere effettuata con quattro mappe da 16 caselle ognuna. In quest'ultimo caso, oltre alle adiacenze valide per una mappa a quattro variabili sono da considerarsi adiacenti anche quelle caselle che si corrispondono orizzontalmente e verticalmente, così ad esempio la casella 13 (A=B=0) .

è adiacente alle caselle 5, 15, 9, 12, verticalmente alle caselle 45 (A=1, B=0) orizzontalmente alla 29 (A=0, B=1) mentre non è adiacente alla casella 61 (A=B=1) in quanto passando dalla 13 alla 61 variano sia A che B. Analogamente la casella 29 (A=0, B=1) è adiacente alle 21, 31, 25, 22 e orizzontalmente alla 13(A=B=0) everticalmente alla 61 (A=B=1) e non alla 45 in cui si ha cambiamento delle due variabili Ae B (A=1, B=0).

Naturalmente all'aumentare del numero di variabili della funzione da minimizzare aumenta il numero delle caselle della mappa di Karnaugh corrispondente e di conseguenza anche la difficoltà dell'operatore nella ricerca di più ampi raggruppamenti possibili in ragione di 2ⁿ. In pratica quando il numero di variabili è maggiore di cinque è preferibile passare ad altri sistemi di minimizzazione come quello di Quine McCluskey.

Esempio: minimizzare la funzione a 5 variabili