ALGEBRA DI BOOLE

L’algebra di Boole  è un’algebra astratta che opera con i soli valori 0 e 1 associati ai valori di verità False e True (Logica Booleana). L’algebra fu sviluppata nel 1854 all’University College di Cork da Boole per scrivere in forma algebrica la logica delle proposizioni. Oggi costituisce la base del mondo digitale. Si studia l’algebra di Boole o algebra booleana perché un circuito digitale può essere espresso tramite un’espressione booleana e viceversa,(logica booleana).  Una funzione booleana ha una o più variabili di input e l’uscita dipende esclusivamente dagli stati che assume l’ingresso, che ricordiamo può assumere solo i valori zero e uno. Se in ingresso abbiamo n variabili di input, allora tutte le possibili combinazioni sono 2ⁿ e possono essere espresse da una tabella detta tabella della verità.

CIRCUITI LOGICI

I circuiti logici sono componenti hardware che manipolano l’informazione binaria. I circuiti di base sono detti PORTE LOGICHE (logical gate). Allo scopo di descrivere i comportamenti dei circuiti digitali si può usare una algebra (notazione matematica) che specifica l’operazione di ogni gate e permette di analizzare e sintetizzare (disegnare) il circuito. Sono stati individuati e costruiti circuiti elettronici che realizzano le operazioni elementari, questi sono detti PORTE LOGICHE Le porte logiche sono circuiti che operano su più segnali di ingresso e producono un segnale di uscita. Rispondono a due valori di range di tensioni che associamo ai valori logico 0 e 1. Le porte logiche che rappresentano le operazioni AND OR e NOT sono di seguito riportate. Le variabili si indicano con le lettere A,B,C,X,Y,W,Z. Le operazioni base sono AND ( • ), OR ( + ) ,NOT ( ¯ ).

Le funzioni booleane sono quelle funzioni di variabile booleana che possono assumere soltanto i valori vero e falso (1,0).

Esempio:

F=X+Y̅Z

Possiamo rappresentare la funzione usando la tabella di verità.

TEOREMI DELL’ALGEBRA DI BOOLE

DUALI

Il principio di dualità afferma che data una eguaglianza se ne ottiene un’altra sostituendo l’operatore AND con l’operatore OR, 1 con 0 e viceversa. Le relazioni 1 e 2 sono duali. I teoremi di De Morgan sono molto importanti per ottenere il complemento di una espressione.

Dimostrazione del Teorema di De Morgan tramite tabella di Verità.

Il vantaggio nell’usare l’algebra di Boole sta nel fatto di permettere la semplificazione dei circuiti digitali. Vediamo un esempio:

F=X̅YZ+X̅YZ̅ +XZ

F=X̅Y(Z+Z̅) + XZ      Per il teorema 7) Z+Z̅ = 1

F= X̅Y+XZ

Le due funzioni sono equivalenti, ma la seconda funzione è realizzabile con un circuito più semplice.

DEFINIZIONE DI RETE COMBINATORIA

Una rete combinatoria è una rete logica con n ingressi e m uscite. Le uscite sono funzione degli ingressi, ma non del tempo: cambiano gli ingressi ed immediatamente cambiano le uscite (ovviamente è un modello). In un circuito logico le porte logiche sono combinate tra loro formando un circuito combinatorio. Le variabili sono combinate tramite le operazioni logiche. Abbiamo visto che è possibile esprimere le funzioni booleane tramite la sua espressione analitica oppure tramite la tabella di verità. Le funzioni booleane possono essere scritte in vari modi ma vi sono delle espressioni che vengono considerate standard. Per far ciò definiamo i mintermini e i maxtermini.

MINTERMINI E MAXTERMINI

Considerando una riga della tabella di verità si definisce mintermine il prodotto delle variabili booleane relative a tal riga prese in forma diretta o complementata a seconda se assumono valore 1 o 0. Si definisca maxtermine la somma delle variabili booleane prese in forma diretta o negata a seconda se assumono valore 0 o 1.Con n variabili abbiamo 2ⁿ mintermini e maxtermini.

PRODOTTO DI SOMME

Possiamo ottenere la forma analitica di una funzione a partire dalla tabella di verità nel seguente modo:

1. Si individuano le righe per cui F ha valore 0;
2. Si scrivono tante somme quante sono le righe individuate
3. Ogni somma è il maxtermine relativo alla riga
4. Si effettua il prodotto delle somme.

Il vantaggio delle forme standard è quello di permettere la realizzazione delle funzioni con circuiti a due livelli: AND-OR oppure OR-AND.

MAPPE DI KARNAUGH

La mappa di Karnaugh è un metodo di rappresentazione esatta di sintesi di reti combinatorie a uno o più livelli. Una tale mappa costituisce una rappresentazione visiva di una funzione booleana in grado di mettere in evidenza le coppie di mintermini o di maxtermini a distanza di Hamming unitaria (ovvero di termini che differiscono per una sola variabile binaria (o booleana)). Poiché derivano da una meno intuitiva visione delle funzioni booleane in spazi {0,1}ⁿ con n numero delle variabili della funzione, le mappe di Karnaugh risultano applicabili efficacemente solo a funzioni con al più 5 – 6 variabili. Una mappa di Karnaugh è un metodo grafico che ha come obiettivo quello di ridurre la complessità delle funzioni booleane espresse in forme canoniche. Essa si costruisce a partire dalla tabella della verità di una funzione booleana, nel processo di sintesi di una rete combinatoria. Le mappe di Karnaugh permettono di costruire semplicemente la forma minima di una funzione come somma di prodotti logici (forma disgiuntiva) o come prodotto di somme logiche (forma congiuntiva) e quindi semplificazioni della funzione booleana spesso più immediate di quelle ottenibili con modifiche algebriche.

SEMPLIFICAZIONE DI UNA FUNZIONE

Essendoci 16 combinazioni delle 4 variabili booleane, anche la mappa di Karnaugh dovrà avere 16 posizioni. Il modo più conveniente per disporle è in una tabella 4×4. I numeri binari nella griglia mostrano il valore d’uscita della funzione per tutte le combinazioni possibili di ingresso. Scriveremo 0 all’estrema sinistra in alto poiché f = 0 quando A = 0, B = 0, C = 0, D = 0, cioè f(0,0,0,0) = 0. Allo stesso modo scriveremo 1 in basso a destra poiché A = 1, B = 0, C = 1, D = 0 restituiscono f = 1, ovvero f (1,0,1,0,) = 1.

PROCEDIMENTO

Dopo aver costruito la mappa di Karnaugh si raggruppano gli 1 in rettangoli più grandi possibile, che però abbiano sempre un’area (in quadretti della tabella) pari ad una potenza di 2 (1, 2, 4, 8, 16, 32, …). I raggruppamenti ottimali, in questo esempio, sono quelli indicati nella mappa con il contorno verde, rosso e blu. Per ciascun raggruppamento troviamo le variabili che non cambiano il loro valore. Per il primo raggruppamento (il rosso) si vede che: La variabile A mantiene lo stesso stato (1) in tutto il gruppo, quindi deve essere inclusa nel prodotto risultante. La variabile B non mantiene il suo valore, passando da 1 ( f(1, 1,0, 0) ) a 0 ( f(1, 0, 0, 0)), e quindi deve essere esclusa. C non cambia, mantiene lo stesso stato (0), quindi viene inclusa. D cambia ed è esclusa. Così il primo prodotto che farà parte dell’espressione booleana finale è AC̅ (si considera la variabile diretta se, per i valori all’interno del rettangolo, essa assume il valore 1, e la sua negata se invece assume il valore 0). Per il rettangolo in verde (formato da quattro 1 disposti in verticale) si vede che A, B mantengono lo stesso stato, mentre C e D cambiano. Essendo B uguale a 0, la variabile deve essere negata prima di venire inclusa nel prodotto. Così si ottiene AB̅. Con lo stesso procedimento, dal rettangolo blu si trova BCD’: l’unica variabile che non va inclusa nel prodotto è la A in quanto all’interno del rettangolo essa cambia di valore. L’espressione finale della funzione f si ottiene sommando i prodotti precedentemente trovati: AC̅ + AB̅ + BCD̅. Se si vuole trovare la funzione duale, ossia la funzione che fa uso dei maxtermini, basta semplicemente raggruppare i valori 0 invece degli 1: ciò corrisponde allo scegliere nella tavola di verità le righe per cui la funzione di uscita vale 0 invece che 1. In tal caso vanno complementate (cioè negate) le variabili che rimangono costanti nel raggruppamento e che hanno valore pari a 1. Nell’esempio mostrato la funzione duale è data da (A+C) (A+B) (B̅+C̅+D̅). In una mappa di Karnaugh con n variabili, un prodotto Booleano di k variabili corrisponde a un rettangolo formato da ^2n-k caselle. Le mappe di Karnaugh sono adatte anche alla semplificazione di funzioni che contengono condizioni di indifferenza (don’t care, cioè valori di input per cui è irrilevante quale sia l’output): queste si rappresentano nella griglia solitamente con i simboli *, – oppure con la lettera greca (delta), e possono essere considerate sia come 1 che come 0, in modo da formare raggruppamenti maggiori. Non è però consentito effettuare raggruppamenti di soli don’t care.

Nota: La griglia è da considerarsi, non come un piano, ma come un toro, quindi i rettangoli possono attraversare i bordi, sia verticalmente che orizzontalmente, passando da un lato a quello opposto. Per esempio anche ABD̅ potrebbe essere un prodotto valido.

APPROFONDIMENTO

ALGEBRA DI BOOLE