Cos'è ElectroYou | Login Iscriviti

ElectroYou - la comunità dei professionisti del mondo elettrico

6
voti

Forma cum laude: algebra di commutazione

Indice

PRESENTAZIONE

Benvenuto, affezionato lettore! Quello che hai davanti è il secondo articolo del ciclo relativo ai metodi formali (se non hai ancora letto il primo, puoi farlo qui); precisamente, con questo e con il prossimo articolo ci occuperemo di una trattazione essenziale della logica proposizionale, la quale vedremo prima come sistema algebrico e poi come linguaggio formale. Si tratta di un argomento fondamentale nel nostro percorso sui metodi formali, perché ci permette di vedere un primo esempio di linguaggio adatto alla modellazione dei sistemi e alla scrittura delle condizioni che si desidera essi rispettino; nello specifico, vedremo direttamente come utilizzare la formulazione algebrica della logica proposizionale per modellare semplici circuiti digitali, e indirettamente valuteremo come scrivere delle condizioni mentre tratteremo la definizione "linguistica" della logica.

Questo articolo non presuppone che il lettore abbia competenze specifiche se non quelle minime acquisite nell'ambito delle scuole superiori o equipollenti, per cui in linea di principio dovrebbe essere fruibile da chiunque; in ogni caso, chi ne avesse bisogno è caldamente invitato ad avvalersi di un qualsiasi testo di analisi matematica di base (faccio un po' di campanilismo e consiglio [CanutoTabacco14], ma qualsiasi testo va bene) per un breve ripasso degli elementi fondamentali sulle funzioni.

Bene, cominciamo.

INTRODUZIONE

Prima di iniziare: strutture algebriche

Prima di addentrarci nell'analisi dell'algebra di commutazione, una breve spiegazione informale: quando definiamo delle cosiddette strutture algebriche, in realtà ciò che stiamo facendo è più o meno prendere un insieme di valori (un dominio, in termini tecnici) e delle operazioni su quei valori, un po' come si fa alle scuole elementari quando impariamo i numeri naturali e le quattro operazioni fondamentali. Precisamente, ai fini di questo articolo ci occupiamo di strutture algebriche chiuse, ovvero tali che l'esecuzione delle operazioni tra elementi del dominio risulti in altri elementi del dominio; non sempre, però, le strutture algebriche sono chiuse: basti pensare che, per esempio, l'insieme dei numeri naturali non può definirsi chiuso rispetto alla sottrazione, perché l'operazione 2 − 3 non produce un numero naturale.
L'approfondimento teoretico delle strutture e delle loro proprietà esula dagli scopi di questo articolo: si rimanda, per approfondimenti (consigliati, comunque, solo a chi sia già forte di solide basi matematico-logiche), a testi come[Hodges97]; noi seguiremo un approccio molto più elementare, così da poter comprendere i concetti fondamentali senza dover ricorrere a strumenti particolarmente avanzati.

Le proprietà fondamentali

Andando a noi, l'algebra di commutazione è identificata dal suo dominio e da tre operazioni di base; formalmente, si scrive che l'algebra di commutazione \mathcal{A} è definita dalla tupla (S, \, \cdot , \, +, \, \neg), dove S = {0,1} è il dominio dell'algebra e i tre simboli successivi sono le tre operazioni, ovvero l'operazione binaria di congiunzione \cdot, l'operazione binaria di disgiunzione + e l'operazione unaria di negazione \neg. Per indicare le tre operazioni, esistono delle scritture alternative che è importante conoscere:

  • Visto che il simbolo della congiunzione è analogo a quello del prodotto, può essere omesso: x\cdot y è spesso scritto come xy. Un'altra simbologia, molto usata nell'ambito della logica, è x \wedge y.
  • Per indicare la negazione, spesso si scrive non \neg x, bensì \overline{x} (e noi faremo proprio così); alternativamente, certuni preferiscono indicare \neg x come x'.
  • Per indicare la disgiunzione, si usa (soprattutto nell'ambito della logica) anche il simbolo \vee.

Le operazioni fondamentali godono di importanti proprietà:

  • La congiunzione è un'operazione commutativa, ovvero x\cdot y = y \cdot x, e il suo elemento neutro è il valore 1, ovvero x \cdot 1 = x. Ogni elemento x ammette un complementare rispetto alla congiunzione, ovvero un elemento indicato con \overline{x} (si, esatto: è proprio la negazione dell'elemento di partenza!) e tale che x\cdot\overline{x} = 0.
  • La disgiunzione è un'operazione commutativa, ovvero x + y = y + x e il suo elemento neutro è il valore 0, ovvero x + 0 = x. Ogni elemento x amette un complementare rispetto alla disgiunzione, ovvero l'elemento \overline{x} (anche qui, ci riferiamo proprio alla negazione dell'elemento di partenza) e tale che x+\overline{x} = 1.

La congiunzione e la disgiunzione sono legate da un principio importantissimo, detto principio di dualità, il quale stabilisce che qualsiasi proprietà derivata da quelle fondamentali (ovvero, quelle che abbiamo appena elencato) per una delle due operazioni vale anche per l'altra sostituendo un'operazione con l'altra e gli 1 con gli 0 (o viceversa, gli 0 con gli 1); alcune proprietà che rispettano il principio di dualità sono:

  • La proprietà di idempotenza x + x = x, la cui duale è x\cdot x = x.
  • La proprietà di assorbimento x + (x\cdot y) = x, la cui duale è x\cdot(x+y) = x.
  • La proprietà di associatività x + (y + z) = (x + y) + z, la cui duale è x \cdot (y \cdot z) = (x \cdot y) \cdot z.
  • Le due leggi di De Morgan, che sono una la duale dell'altra: \overline{(x+y)} = \overline{x}\cdot\overline{y} e \overline{(x\cdot y)} = \overline{x}+\overline{y}.

Introduciamo ora un piccolo supplemento di notazione, così da poter semplificare la scrittura di certe formule avvalendoci di sintassi molto usate:

  • La formula \overline{x} + y è comunemente scritta come x \rightarrow y, e si dice che x implica y.
  • La formula (\overline{x}\cdot y) + (x \cdot \overline{y}) è comunemente scritta come x \oplus y, e si parla di disgiunzione esclusiva tra le due variabili. Nota a margine: avremmo potuto evitare le parentesi, perché la congiunzione ha la precedenza sulla disgiunzione (e la negazione ha la precedenza sulla congiunzione, per la cronaca), ma le abbiamo scritte lo stesso per miglior leggibilità.
  • La formula (\overline{x} + y) \cdot (x + \overline{y}), ovvero la formula (x \rightarrow y) \cdot (y \rightarrow x), è indicata anche come x \leftrightarrow y, e si dice che le variabili sono coimplicate.

Queste che abbiamo appena visto vengono comunemente annoverate come "operazioni derivate", e noi le tratteremo come tali; non si dimentichi mai, però, che esse non sono a rigore operazioni dell'algebra di commutazione: si tratta semplicemente di notazioni abbreviate per espressioni basate sulle tre "vere" operazioni dell'algebra.

Una precisazione terminologica

Leggendo fin qui, il lettore "informato" si sarà chiesto "algebra di commutazione? Ma non si chiamava algebra booleana?". A questo lettore è importante dare risposta, perché egli non sia confuso dalla nostra trattazione: l'algebra che stiamo trattando si chiama davvero algebra di commutazione... ed è un'algebra booleana!
Il punto fondamentale della questione è il seguente: si definisce algebra booleana una tupla (S, \, \cdot , \, +, \, \neg, 0, 1), dove S è il dominio dell'algebra, i tre simboli successivi sono tre operazioni fondamentali (binarie le prime due, unaria la terza) e gli ultimi due simboli sono degli elementi notevoli del dominio; le tre operazioni citate godono di tutte le proprietà che abbiamo già visto per l'algebra di commutazione. Ma dove sta, quindi, il trucco? È presto detto: l'algebra di commutazione è la particolare algebra booleana in cui S = {0,1}, le tre operazioni assumono i nomi che abbiamo visto prima e i due simboli notevoli sono di fatto gli unici elementi del dominio (per questo, nella definizione data all'inizio, li abbiamo omessi); si noti però che l'algebra di commutazione non è ovviamente l'unica algebra booleana possibile: se prendiamo un qualche insieme X, per esempio, e poniamo che:

  • S = \mathcal{P}(X), dove \mathcal{P}(X) è l'insieme delle parti di X.
  • L'operazione \cdot è l'operazione di intersezione insiemistica, l'operazione + è l'operazione di unione insiemistica e l'operazione \neg è l'operazione di complementazione insiemistica.
  • Il simbolo 0 indica l'insieme vuoto, mentre il simbolo 1 indica l'intero insieme X.

Otteniamo un'altra algebra booleana, la quale lavora sui sottoinsiemi dell'insieme-universo X. Potrebbe essere un interessante esercizio per il lettore riflettere sul significato delle proprietà già discusse se inserite in una simile algebra.
Dopo aver risposto al lettore curioso che come un novello Diogene cercava l'algebra booleana, ci permettiamo un'ultima precisazione, dopo la quale riprenderemo la trattazione: in questo articolo, useremo tranquillamente termini "booleani" per parlare della sola algebra di commutazione, ovvero parleremo, ad esempio, di "variabili booleane" invece che di "variabili dell'algebra di commutazione": dato quanto abbiamo appena discusso, senz'altro il lettore non avrà difficoltà a capire che, per ciò che ci interessa, non c'è differenza.

IL LINGUAGGIO DELL'ALGEBRA

Espressioni e formule

Torniamo a noi, e definiamo ciò che più ci interessa: come esprimere i concetti utilizzando il linguaggio dell'algebra di commutazione. Il punto di partenza è costituito dalle variabili, che possiamo identificare con i simboli che vogliamo (x o y, ad esempio), e dalle costanti, che dato il nostro dominio possono essere solo 0 o 1. Questi elementi, benchè elementari, sono in realtà tutto ciò che ci serve, perché possiamo concatenarli con le operazioni fondamentali per ottenere le formule booleane, che sono in pratica le nostre "frasi" nel linguaggio dell'algebra di commutazione. Formalmente, definiamo le formule booleane per induzione, in questo modo:

  • Un elemento del dominio dell'algebra costituisce un'espressione booleana.
  • Una variabile booleana costituisce un'espressione booleana.
  • La congiunzione di espressioni booleane è un'espressione booleana.
  • La disgiunzione di espressioni booleane è un'espressione booleana.
  • La negazione di un'espressione booleana è ancora un'espressione booleana.

Questa modalità di definizione è molto potente, perché ci permette non solo di capire quali sequenze di simboli rispettano la definizione e quali no, ma anche di intendere come costruire le formule booleane.
Ora, poniamoci una domanda: possiamo tradurre delle espressioni booleane in una nuova espressione booleana? In altri termini, possiamo dire in qualche modo che un'espressione booleana è funzione di altre espressioni booleane? Banalmente, la risposta è si: possiamo infatti definire le funzioni booleane f: S^n \rightarrow S, le quali prendono come parametri n variabili booleane e forniscono in uscita un valore del dominio dell'algebra (ovviamente, nulla ci impedisce di definire funzioni a più uscite f: S^n \rightarrow S^m; noi ci limitiamo a quelle con una sola uscita per semplicità); come le formule, anche le funzioni sono definite per induzione:

  • La funzione f(x1,...,xn) = k con k \in S è una funzione booleana.
  • La funzione f(x1,...,xn) = xi con i \in [1, n] è una funzione booleana.
  • La congiunzione, la disgiunzione e la negazione di funzioni booleane è a sua volta una funzione booleana.


Tabelle di verità: arriva la logica

Alle funzioni booleane è connesso un concetto fondamentale: quello di tabella di verità. Data una funzione booleana, la sua tabella di verità (il cui nome ha un'origine che sarà intuitivamente chiara tra poco) descrive sostanzialmente quali valori dei suoi parametri producano in uscita un 1 e quali uno 0. Possiamo utilizzare le tabelle di verità per dare un senso alle operazioni dell'algebra, ovvero per dare una semantica al linguaggio la cui sintassi è data dall'algebra di commutazione; vedremo per esteso il caso della disgiunzione, mentre per le altre operazioni daremo solo le tabelle di verità e l'interpretazione.
Prendiamo la funzione f(x,y) = x + y, della quale sappiamo, dalle proprietà fondamentali, che, se y = x allora x + y = x, mentre se y = 0 allora x + y = x, ed egualmente se x = 0 allora x + y = y. Compiliamo la tabella di verità:

x y f(x,y)
0 0 0
1 0 1
0 1 1
1 1 1

Notiamo ora un dettaglio: se poniamo che x e y indichino frasi minime ("la pianta è secca", ad esempio), che il valore 1 voglia dire che la frase è vera e che il valore 0 voglia dire che la frase è falsa, la nostra tabella di verità ci dice quando è vera la frase "x o anche y"!
Vediamo un esempio, così ci rendiamo conto:

x = "la pianta è secca"
y = "c'è il sole"
f(x,y) = "la pianta è secca o anche c'è il sole" (orribile da leggere, ma rende l'idea)

Se la pianta è in fiore e piove, ovviamente ci aspettiamo che f(x,y) = 0; ponendo x = y = 0 (com'è giusto che sia, visto che le due frasi indicate dalle variabili sono false) e guardando la tavola di verità per la funzione, ci rendiamo conto che effettivamente f(x,y) = 0! Se invece la pianta è secca e piove, ci aspettiamo che f(x,y) = 1, e ponendo x = 1 e y = 0 notiamo che questo succede; egualmente, se la pianta è in fiore e c'è il sole, oltre a essere tutti contenti e dotati di pollice verde ci aspettiamo che f(x,y) = 1, e ponendo x = 0 e y = 1 la tabella di verità ci dice che è così. Ultimo caso: la pianta è secca e c'è il sole, quindi poniamo x = y = 1 e ci aspettiamo che f(x,y) = 1, come in effetti la tabella di verità ci dice.
In sostanza, cosa abbiamo ottenuto? Per farla breve, abbiamo visto che la disgiunzione booleana è un modo formale per esprimere in termini matematici la disgiunzione non esclusiva tra due frasi minime (o, più esattamente, due proposizioni); in altri termini ed "esagerando" un po' (ma neanche tanto), abbiamo appena ricavato gli strumenti per ragionare rigorosamente sul senso di frasi nella forma "x o anche y". Non è poco, soprattutto in tempi come questi in cui tutti si sentono autorizzati a dire le peggiori cretinate e capire cosa ha senso e cosa no diventa sempre più difficile.
Passiamo alle altre operazioni:

  • La congiunzione f(x, y) = x\cdot y esprime la frase "x e y", e la sua tabella di verità (che i più volenterosi potrebbero cercare di derivare: è un esercizio semplice ma istruttivo) è ovviamente la seguente:
x y f(x,y)
0 0 0
1 0 0
0 1 0
1 1 1
  • La negazione f(x) = \overline{x} esprime (probabilmente l'avevate già capito) la frase "non è vero che x", e la sua tabella di verità è banale:
x f(x,y)
0 1
1 0
  • L'implicazione f(x, y) = x \rightarrow y esprime la frase "se x allora y". Prima di presentare la tabella di verità, riflettiamo un attimo sul valore dell'implicazione nel linguaggio naturale: se la premessa di un'implicazione è vera, ci aspettiamo che lo sia anche la conseguenza, dunque un'implicazione è vera se lo sono sia la premessa che la conseguenza, mentre è falsa se la premessa è vera e la conseguenza non lo è; se la premessa è falsa, invece, ci aspettiamo che anche la conseguenza lo sia, dunque un'implicazione in cui siano entrambe false è perfettamente verificata; tuttavia, non possiamo dire che un'implicazione in cui la premessa sia falsa e la conseguenza vera risulti falsa a sua volta, perché non sappiamo se la nostra conseguenza possa derivare anche da premesse diverse dalla nostra, quindi la nostra implicazione rimane perfettamente valida. Il risultato della nostra riflessione è ben espresso dalla tabella di verità:


x y f(x,y)
0 0 1
1 0 0
0 1 1
1 1 1
  • La disgiunzione esclusiva f(x, y) = x \oplus y esprime la frase "x oppure y, ma non entrambe", e la sua tabella di verità è:
x y f(x,y)
0 0 0
1 0 1
0 1 1
1 1 0
  • La coimplicazione f(x, y) = x \leftrightarrow y indica la frase "x equivale a y", ovvero "dire che x equivale a dire che y", e la sua tabella di verità è la seguente:
x y f(x,y)
0 0 1
1 0 0
0 1 0
1 1 1

Dopo questi ragionamenti, non può non apparirci ovvio un fatto fondamentale: l'algebra di commutazione ci da la possibilità di esprimere formalmente una certa parte del nostro linguaggio e di ragionare su di essa. Non serve conoscere il greco antico per capire che questa è sostanzialmente la definizione di "λογική", che in italiano rendiamo con "logica": il linguaggio che ha per sintassi l'algebra di commutazione e per semantica le tabelle di verità è una logica, e precisamente la cosiddetta logica proposizionale, che sarà oggetto del prossimo articolo.

Andiamo all'elettronica

Oltre che per discutere parte del nostro linguaggio naturale, l'algebra di commutazione può essere usata per rappresentare i circuiti digitali. Essi, infatti, sono composti da blocchi elementari, detti porte logiche (a loro volta costituite da transistor... ma non divaghiamo: per i nostri scopi, cosa c'è dentro le porte logiche non è importante), i quali implementano (lo dice il nome!) esattamente le operazioni logiche, ovvero le operazioni dell'algebra di commutazione. La corrispondenza operazione-porta è così definita:

Proviamo a costruire noi un circuito logico partendo dalla funzione f(x, y, z) = (x + y) \cdot z + \overline{x}: anzitutto, ci occorre calcolare la disgiunzione di x e y:

Poi, dobbiamo congiungere il risultato di questo calcolo a z:

Infine, dobbiamo calcolare la disgiunzione tra quanto ottenuto e \overline{x}:

Fatto: abbiamo ricavato il circuito descritto da f(x,y,z).

Un'altra riflessione, questa volta sui circuiti

A questo punto, dobbiamo precisare un dettaglio molto importante: le funzioni booleane descrivono opportunamente solo i circuiti combinatori, ovvero quelli che implementano funzioni in cui l'uscita dipende solo dall'ingresso corrente; per i circuiti sequenziali, i quali implementano funzioni "con memoria", il formalismo è un altro, e ne parleremo qui brevemente.
Prendiamo uno dei più semplici circuiti sequenziali: il latch SR. Esso è così composto:

Vediamo un attimo come funziona dandogli una sequenza di input:

  1. Se poniamo R = S = 1, entrambe le porte hanno l'uscita a 0, quindi Q = 0.
  2. Se a questo punto poniamo R = 0, otteniamo Q = 1 (ricordiamo la tabella di verità della porta NOR!).
  3. Se torniamo a R = S = 1, abbiamo di nuovo Q = 0.
  4. Se a questo punto poniamo S = 0, l'uscita non cambia: la porta in basso ha due 0 in ingresso e dunque produce un 1, ovvero la porta in alto si trova in ingresso due 1 e continua a produrre Q = 0.

Questi quattro passi ci fanno notare una cosa fondamentale: partendo dallo stesso stato iniziale, ovvero R = S = 1, azioni diverse portano il circuito in stati diversi. Per descrivere il circuito, noi dobbiamo essere in grado di descrivere questi stati e come sono collegati tra loro.
Come fare? Ci viene in aiuto una branca dell'informatica teorica (e della matematica discreta), la cosiddetta "teoria degli automi", la quale ci permette di derivare il modello che ci serve, chiamato macchina a stati finiti. Questo modello è descritto dalla tupla (I,O,S,δ,λ,S0), dove I è detto alfabeto d'ingresso, O è l'alfabeto d'uscita, S è l'insieme degli stati, \delta: S \times I \rightarrow S è la funzione di transizione tra gli stati, λ è la funzione che determina il valore dell'uscita del circuito e S_0 \in S è lo stato iniziale della macchina (in realtà possono essercene molteplici, ma nei circuiti digitali di solito ne abbiamo uno, quindi accontentiamoci di un modello siffatto). Se λ dipende solo dallo stato corrente, ovvero \lambda: S \rightarrow O, la macchina a stati finiti è una macchina di Moore; se invece λ dipende anche dall'ingresso, ovvero \lambda: S \times I \rightarrow O, la macchina a stati finiti è una macchina di Mealy.
Per il momento, questo è tutto ciò che abbiamo da dire sulle macchine a stati finiti: oggi dobbiamo parlare dell'algebra di commutazione, e conviene che non si divaghi troppo. Torneremo sui modelli per circuiti sequenziali in seguito.

MINIMIZZAZIONE

Di cosa parliamo?

Abbiamo analizzato espressioni e funzioni booleane, e abbiamo dato loro un senso; a questo punto, ci chiediamo: queste entità, le funzioni e le espressioni, sono uniche? In altri termini, possiamo rappresentare la stessa funzione in più modi? E soprattutto, se possiamo, come scegliamo il modo migliore?
Non perdiamo tempo, e rispondiamoci subito: si, è possibile rappresentare la stessa funzione (o espressione; per semplicità, nel seguito parleremo solo di funzioni, ma l'applicabilità alle espressioni è oltre la banalità) in più modi diversi, e ovviamente è possibile identificare una rappresentazione migliore delle altre, posto che definiamo un'opportuna metrica per valutare la qualità di ciascuna. Visto che nessuno ha voglia di operare con espressioni lunghe, e visto che noi dobbiamo modellare (anche) circuiti digitali, dove diminuire gli ingressi può presentare vantaggi non indifferenti, sceglieremo come metrica la minimizzazione del numero di variabili (più propriamente, di letterali... ma ci arriviamo tra poco).


Un po' di teoria

Iniziamo con una definizione utile per il seguito: data una variabile booleana x, si dicono suoi letterali se stessa e la propria negazione \overline{x}. Formalmente, un letterale è definito come l = < nome,valore > , dove il primo parametro è il nome della variabile cui fa riferimento e il secondo definisce se la variabile è negata o no: i due letterali associati a x sono x = < x,1 > (letterale naturale) e \overline{x} = <x, 0> (letterale negato).
Notiamo ora un dettaglio fondamentale: data una funzione booleana, non sempre è necessario assegnare un valore a tutte le sue variabili: può capitare che basti dare un valore solo ad alcune di esse per sapere quale valore assumerà a sua volta la funzione. Prendiamo, ad esempio, la funzione f(x,y,z) = x + yz: se poniamo x = 1, possiamo anche disinteressarci dei valori delle altre variabili, perché certamente la nostra funzione varrà 1. A questo comportamento sono legate due definizioni interessanti, che adesso vediamo:

  • Chiamiamo implicante una congiunzione di letterali il cui stato sia sufficiente a far valere 1 la funzione, e in particolare implicante primo un implicante contenente il minor numero possibile di letterali. In altri termini, un implicante è una congiunzione contenente, per ognuna delle variabili "necessarie" al fine di definire il valore della funzione, il suo letterale naturale se tale variabile deve valere 1, il suo letterale negato altrimenti. Per esempio, nella nostra funzione di prima un possibile implicante potrebbe essere x, mentre nella funzione f(x, y, z) = x\overline{y} + z\overline{x} un implicante sarebbe x\overline{y}. Un implicante che coinvolge tutte le variabili della funzione è un mintermine.
  • Chiamiamo implicato una disgiunzione di letterali il cui stato sia sufficiente a far valere 0 la funzione, e in particolare implicato primo un implicato contenente il minor numero possibile di letterali. Per esempio, nella nostra funzione di prima un possibile implicato potrebbe essere \overline{x} + \overline{y}. Un implicato che coinvolge tutte le variabili della funzione è un maxtermine.

Partendo da queste definizioni, valuteremo due possibili metodi di minimizzazione delle funzioni booleane.

Forme canoniche

Il primo metodo che vediamo è puramente meccanico, e si basa sull'applicazione ripetuta delle proprietà delle formule booleane. Per poter applicare profittevolmente questo metodo, però, ci occorre rappresentare la funzione in modo opportuno; ci viene in aiuto il fondamentale teorema di espansione di Shannon (chiamato così anche se in realtà la sua formulazione si deve a Boole), secondo il quale una generica funzione booleana f(x1,x2,...,xn) può essere riscritta in una tra due forme:

f(x_1, x_2, ..., x_n) = \overline{x}_1f_{\overline{x}_1} + x_1f_{x_1} = \overline{x}_1 f(0, x_2, ..., x_n) + x_1 f(1, x_2, ..., x_n)
f(x_1, x_2, ..., x_n) = (\overline{x}_1+f_{\overline{x}_1}) (x_1+f_{x_1}) = [\overline{x}_1 + f(0, x_2, ..., x_n)]  [x_1 + f(1, x_2, ..., x_n)]

L'applicazione iterativa della prima scrittura a una funzione booleana conduce ad un'espressione del tipo:

f(x_1, x_2, ..., x_n) = \overline{x}_1 \overline{x}_2 ... \overline{x}_n f(0, 0, ..., 0) +
 \overline{x}_1 \overline{x}_2 ... x_n f(0, 0, ..., 1) + ... + x_1x_2 ... x_n f(1, 1, ..., 1)

La quale può essere semplificata notando che in alcuni dei prodotti il termine f(...) (detto discriminante della funzione) vale senz'altro 0; il risultato della semplificazione così realizzata è la prima forma canonica della funzione, la quale risulta di fatto una disgiunzione di tutti i suoi mintermini. Partendo da questa espressione e applicando le proprietà che abbiamo già studiato (o altre che possiamo ricavare da esse), è possibile giungere alla semplificazione della funzione.

Applicando iterativamente la seconda scrittura, invece, otteniamo un'espressione del tipo:

f(x_1, x_2, ..., x_n) = [\overline{x}_1 + \overline{x}_2+... + \overline{x}_n + f(0, 0, ..., 0)] [\overline{x}_1 +
\overline{x}_2+...+ x_n  + f(0, 0, ..., 1)]...[x_1+x_2+...+ x_n+ f(1, 1, ..., 1)]

Valutando i discriminanti, possiamo determinare senz'altro che alcuni valgono 1, e dunque possiamo eliminare le relative disgiunzioni; la semplificazione siffatta conduce alla seconda forma canonica della funzione, la quale risulta una congiunzione di tutti i suoi maxtermini. Vale quanto detto prima: partendo da questa forma e applicando le proprietà note, è possibile giungere alla semplificazione della funzione.

A margine, una piccola nota: ovviamente, nulla ci impedisce di provare ad applicare le proprietà algebriche direttamente sulla funzione "non espansa", ma la rappresentazione canonica rende più immediato capire quali proprietà possono essere applicate e dove.

Concludiamo questa sezione proponendo un utile esercizio: partendo dalla funzione f(x, y, z) = x + \overline{y}z, il lettore provi a sviluppare le due forme canoniche e poi, da esse, torni all'espressione originale. La soluzione è disponibile in [BBSS04], ma si consiglia al lettore di controllarla solo dopo aver risolto l'esercizio da sè.

Mappe di Karnaugh

Passiamo ad un approccio totalmente diverso, basato sul concetto di distanza di Hamming tra due sequenze di letterali: è così detto il numero di letterali differenti tra la prima e la seconda sequenza; ad esempio, xy\overline{z} e xyz hanno distanza di Hamming 1. Perché ci interessa la distanza di Hamming? È presto detto: due termini a distanza di Hamming unitaria differiscono per il letterale associato a una sola variabile, che in uno dei termini è negata e nell'altro non lo è, quindi potrebbe essere possibile semplificarli applicando le proprietà fondamentali che abbiamo visto. Facciamo un esempio per capirci: data l'espressione xyz + xy\overline{z}, i cui due termini hanno distanza di Hamming unitaria, possiamo scrivere:

xyz + xy\overline{z} = xy(z + \overline{z}) = xy

Torniamo a noi: il metodo che studiamo è quello delle mappe di Karnaugh, del quale diciamo subito che risulta adatto solo per funzioni di al più tre-quattro variabili, perché per funzioni più "grosse" la sua esecuzione diventa macchinosa e si ricorre ad altri metodi (come ad esempio il metodo di Quine-McCluskey, che generalizza le mappe di Karnaugh; noi non vedremo queste tecniche, perché appesantirebbero oltre modo la nostra trattazione, ma il lettore interessato può consultare [BBSS04] o [DeMicheli94]).
Valutiamo graficamente una funzione di tre variabili f(x,y,z) utilizzando i valori delle sue variabili come fossero le coordinate di un punto:

Notiamo subito che questa rappresentazione mostra in modo inequivocabile le combinazioni dei valori delle variabili caratterizzate da una distanza di Hamming unitaria, e dunque ci permette di determinare quali termini (se presenti nella nostra funzione) possiamo "fondere" insieme. Per capire ancora meglio l'importanza della cosa, vediamola un attimo da un altro punto di vista: questa rappresentazione elenca tutte le possibili congiunzioni dei letterali della funzione, ovvero (anche) tutti i possibili mintermini della funzione.
Adesso, "smontiamo" il nostro cubo e riportiamolo sul piano, ottenendo questa struttura (da cui abbiamo tolto alcune facce, perché non aggiungevano combinazioni che non avessimo già):

Ciò che abbiamo ottenuto è una mappa di Karnaugh per una generica funzione booleana in tre variabili. Ma come si usa? Vediamolo cercando di semplificare la funzione f(x, y, z) = x + y + \overline{y}z, la cui mappa di Karnaugh possiamo rappresentare mettendo in ogni cella il valore della funzione data la relativa assegnazione di valori alle variabili:

Notiamo un dettaglio importante: tutti i quadratini in cui abbiamo messo un 1 identificano i prodotti di letterali che rendono vera la funzione, ovvero i suoi mintermini. Ciò vuol dire che abbiamo praticamente ottenuto una rappresentazione tabulare della prima forma canonica della funzione. Ma che ci facciamo, con questa rappresentazione?
Chiediamoci: se due celle vicine identificano una coppia di letterali a distanza di Hamming unitaria, quattro celle vicine cosa identificano? Vediamolo per la nostra funzione: la prima riga ci fornisce nell'ordine i mintermini \overline{x}\cdot\overline{y}\cdot\overline{z}, \overline{x}\cdot y\cdot\overline{z}, x\cdot y\cdot\overline{z} e x\cdot\overline{y}\cdot\overline{z}, e possiamo notare che riducendo insieme i primi due e gli ultimi due otteniamo due letterali aventi distanza di Hamming reciproca unitaria. Questo vuol dire una cosa molto importante: i quattro mintermini possono essere ridotti ad un solo termine, costituito dall'unico letterale comune a tutti:

\overline{x}\cdot\overline{y}\cdot\overline{z} + \overline{x}\cdot y\cdot\overline{z}+x\cdot y\cdot\overline{z}+x\cdot\overline{y}\cdot\overline{z} = \overline{z}

Un risultato eccellente!
A questo punto, però, è importante chiederci: quando possiamo unire più di due termini e semplificarli tutti insieme? La risposta è: possiamo realizzare "gruppi" contenenti un numero di termini pari sempre a una potenza di 2, perché ad ogni "riduzione" dobbiamo poter disporre i termini che abbiamo in coppie con distanza di Hamming unitaria. Questo vuol dire che possiamo avere gruppi di 1, 2, 4, 8, 16 letterali.
Altra precisazione: gli estremi di una stessa riga della mappa di Karnaugh hanno distanza di Hamming unitaria (pensiamo al cubo da cui siamo partiti: quegli estremi erano connessi da uno spigolo!), quindi possiamo considerarli una coppia di mintermini semplificabili. Questo ci sarebbe stato utile, per esempio, se in corrispondenza di \overline{x}\cdot y\cdot\overline{z} e x\cdot y\cdot\overline{z} avessimo avuto degli 0, perché avremmo potuto comunque semplificare \overline{x}\cdot\overline{y}\cdot\overline{z} + x\cdot\overline{y}\cdot\overline{z} = \overline{y}\cdot\overline{z}.
Torniamo alla nostra funzione: determinato come identificare i termini semplificabili, possiamo definire tutti i gruppi, ovvero effettuare la copertura della mappa. Dato che vogliamo il minimo numero di letterali possibile, siamo interessati ad avere gruppi grandi e in numero limitato; possiamo quindi effettuare la copertura così:

Notiamo un attimo una cosa: non è sbagliato che un mintermine appartenga a più gruppi, perché replicare uno stesso mintermine all'interno di una funzione booleana non cambia la funzione stessa: per esempio, la funzione g_1(x, y) = xy + \overline{x}y è assolutamente equivalente alla funzione g_2(x, y) = xy + \overline{x}y + xy.
Detto questo, torniamo alla nostra mappa: effettuando la copertura, abbiamo ottenuto che i termini essenziali per la funzione sono \overline{z} (gruppo rosa), y (gruppo verde) e x (gruppo azzurro), ovvero la nostra funzione di partenza è equivalente a f(x, y, z) = x + y + \overline{z}.

A questo punto, delle mappe di Karnaugh abbiamo detto tutto: vediamo solo, per concludere, che forma assumono in base al numero di variabili:

E forniamo un algoritmo generale per usarle:

  1. Scrivere la funzione booleana in forma sum of products, ovvero come somma di congiunzioni e variabili singole; non è strettamente necessario, ma aiuta nelle fasi successive.
  2. Realizzare la mappa di Karnaugh della funzione.
  3. Effettuare la copertura della mappa.
  4. Per ciascun gruppo ottenuto, prendere i letterali che non cambiano valore all'interno del gruppo e congiungerli.
  5. Effettuare la disgiunzione dei termini ottenuti al passo precedente: essa è la funzione semplificata.

BIBLIOGRAFIA

Consigli per la lettura

Tutto ciò che abbiamo trattato nel corso di quest'articolo è riportato in [BBSS04], i primi cinque capitoli del quale costituiscono una lettura integrativa assolutamente raccomandata se non addirittura obbligatoria: essi non solo trattano e approfondiscono ciò di cui abbiamo discusso in quest'articolo, ma presentano anche un certo numero di esempi di circuiti digitali notevoli che dovrebbero far parte della "libreria" di chiunque abbia a che fare con l'hardware e che tra l'altro useremo per alcuni esempi nei prossimi articoli.
Per lo studio dei circuiti logici anche da un punto di vista più "elettronico", il testo di riferimento è senz'altro [MKM15], di cui al momento i primi tre capitoli sono più che sufficienti, ma il lettore più interessato potrebbe gradire anche il quinto.
Per quanto riguarda il progetto dei circuiti combinatori, un'integrazione decente al contenuto dei testi già citati è costituita dai primi due capitoli di [Vahid05]: non aggiungono granché in termini di contenuti (anche se un paio di spunti da non sottovalutare ci sono), ma propongono un certo numero di esempi interessanti.

Riferimenti bibliografici

[BBSS04] C. Bolchini, C. Brandolese, F. Salice, D. Sciuto, Reti logiche, Apogeo, 2004
[CanutoTabacco14] C. Canuto, A. Tabacco, Analisi matematica 1, Springer, 2014
[DeMicheli94] G. De Micheli, Synthesis and optimization of digital circuits, McGraw-Hill, 1994
[Hodges97] W. Hodges, A shorter model theory, Cambridge University Press, 1997
[MKM15] M.M. Mano, C.R. Kime, T. Martin, Logic and computer design fundamentals, Pearson, 2015
[Vahid05] F. Vahid, Digital design, Wiley, 2005

1

Commenti e note

Inserisci un commento

di ,

articolo ben scritto e ben strutturato complimenti, mi permetto di consigliare un ulteriore testo di approfondimento : F.Centurelli, A.Ferrari, Fondamenti Di Elettronica,Zanichelli. In cui l'argomento è trattato molto bene.

Rispondi

Inserisci un commento

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