Walter Ruggeri (wruggeri)

FORMA CUM LAUDE: ALGEBRA DI COMMUTAZIONE

16 June 2018

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

ELECTROYOU.IT

FORMA CUM LAUDE: ALGEBRA DI COMMUTAZIONE 1

articolo: si rimanda, per approfondimenti (consigliati, comunque, solo a chi sia già forte di solide

basi matematico-logiche), a testi come[Hodges97] o (da un punto di vista più "matematico" e

meno "logico") [Bourbaki89]; 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 è definita dalla tupla

, dove S = {0,1} è il dominio dell'algebra e i tre simboli successivi sono le tre operazioni, ovvero

l'operazione binaria di congiunzione , l'operazione binaria di disgiunzione + e l'operazione

unaria di negazione . 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: è spesso scritto come xy. Un'altra simbologia, molto usata nell'ambito della

logica, è .

• Per indicare la negazione, spesso si scrive non , bensì (e noi faremo proprio così);

alternativamente, certuni preferiscono indicare come x'.• Per indicare la disgiunzione, si usa (soprattutto nell'ambito della logica) anche il simbolo

.

Le operazioni fondamentali godono di importanti proprietà:

• La congiunzione è un'operazione commutativa, ovvero , e il suo elemento

neutro è il valore 1, ovvero . Ogni elemento x ammette un complementare

rispetto alla congiunzione, ovvero un elemento indicato con (si, esatto: è proprio la

negazione dell'elemento di partenza!) e tale che .

• 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 (anche qui, ci riferiamo proprio alla negazione

dell'elemento di partenza) e tale che .

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 è .

• La proprietà di assorbimento , la cui duale è .

• La proprietà di associatività x + (y + z) = (x + y) + z, la cui duale è

.

ELECTROYOU.IT WALTER RUGGERI (WRUGGERI)

FORMA CUM LAUDE: ALGEBRA DI COMMUTAZIONE 2

• Le due leggi di De Morgan, che sono una la duale dell'altra: e

.

Introduciamo ora un piccolo supplemento di notazione, così da poter semplificare la scrittura di

certe formule avvalendoci di sintassi molto usate:

• La formula è comunemente scritta come , e si dice che x implica y.• La formula è comunemente scritta come , 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 , ovvero la formula , è indicata anche

come , 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

, 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:

• , dove è l'insieme delle parti di X.

• L'operazione è l'operazione di intersezione insiemistica, l'operazione + è l'operazione di

unione insiemistica e l'operazione è 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à

ELECTROYOU.IT WALTER RUGGERI (WRUGGERI)

FORMA CUM LAUDE: ALGEBRA DI COMMUTAZIONE 3

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 , 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 ; 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 è una funzione booleana.

• La funzione f(x1,...,xn) = xi con è una funzione booleana.

• La congiunzione, la disgiunzione e la negazione di funzioni booleane è a sua volta una

funzione booleana.

ELECTROYOU.IT WALTER RUGGERI (WRUGGERI)

FORMA CUM LAUDE: ALGEBRA DI COMMUTAZIONE 4

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 1e 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:

ELECTROYOU.IT WALTER RUGGERI (WRUGGERI)

FORMA CUM LAUDE: ALGEBRA DI COMMUTAZIONE 5

• La congiunzione 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 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 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 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 indica la frase "x equivale a y", ovvero "dire che xequivale a dire che y", e la sua tabella di verità è la seguente:

ELECTROYOU.IT WALTER RUGGERI (WRUGGERI)

FORMA CUM LAUDE: ALGEBRA DI COMMUTAZIONE 6

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

: anzitutto, ci occorre calcolare la disgiunzione di x e y:

ELECTROYOU.IT WALTER RUGGERI (WRUGGERI)

FORMA CUM LAUDE: ALGEBRA DI COMMUTAZIONE 7

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

Infine, dobbiamo calcolare la disgiunzione tra quanto ottenuto e :

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, quindiQ = 0.

ELECTROYOU.IT WALTER RUGGERI (WRUGGERI)

FORMA CUM LAUDE: ALGEBRA DI COMMUTAZIONE 8

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 nuovoQ = 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 produrreQ = 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, è la

funzione di transizione tra gli stati, λ è la funzione che determina il valore dell'uscita del circuito

e è 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 , la macchina a stati finiti è una macchina di Moore;

se invece λ dipende anche dall'ingresso, ovvero , 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).

ELECTROYOU.IT WALTER RUGGERI (WRUGGERI)

FORMA CUM LAUDE: ALGEBRA DI COMMUTAZIONE 9

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 . 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 (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 un implicante sarebbe . 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 . 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:

ELECTROYOU.IT WALTER RUGGERI (WRUGGERI)

FORMA CUM LAUDE: ALGEBRA DI COMMUTAZIONE 10

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

del tipo:

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:

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

, 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, 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 , i cui due termini hanno distanza di Hamming

unitaria, possiamo scrivere:

ELECTROYOU.IT WALTER RUGGERI (WRUGGERI)

FORMA CUM LAUDE: ALGEBRA DI COMMUTAZIONE 11

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à):

ELECTROYOU.IT WALTER RUGGERI (WRUGGERI)

FORMA CUM LAUDE: ALGEBRA DI COMMUTAZIONE 12

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

, 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 , , e , 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:

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 e avessimo avuto degli 0, perché

avremmo potuto comunque semplificare .

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ì:

ELECTROYOU.IT WALTER RUGGERI (WRUGGERI)

FORMA CUM LAUDE: ALGEBRA DI COMMUTAZIONE 13

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 è assolutamente equivalente alla funzione

.

Detto questo, torniamo alla nostra mappa: effettuando la copertura, abbiamo ottenuto che i

termini essenziali per la funzione sono (gruppo rosa), y (gruppo verde) e x (gruppo azzurro),

ovvero la nostra funzione di partenza è equivalente a .

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.

ELECTROYOU.IT WALTER RUGGERI (WRUGGERI)

FORMA CUM LAUDE: ALGEBRA DI COMMUTAZIONE 14

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

[Bourbaki89] N. Bourbaki, Algebra I, Springer, 1989 [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

Estratto da "https://www.electroyou.it/mediawiki/index.php?title=UsersPages:Wruggeri:forma-

cum-laude-logica-proposizionale"

ELECTROYOU.IT WALTER RUGGERI (WRUGGERI)

FORMA CUM LAUDE: ALGEBRA DI COMMUTAZIONE 15