domenica 4 luglio 2010

Algebra di Boole e riduzione di una funzione logica ai minimi termini


Questo tutorial è stato creato da solidkind, ai tempi della partecipazione su forumfree e forumcommunity e ora che l'ho ritrovato lo rimetto a disposizione per voi nuovi utenti.


In questa lezione verranno elencate le propietà dell'algebra di Boole e successivamente procederemo a ridurre ai minimi termini una funzione logica effettuando la riduzione a mano e utilizzando le mappe di Karnaugh con l'ausilio di un software.

Ecco le regole dell'algebra di Boole:

Somma logica

A + A = A
_
A + A = 1

A + 1 = 1

A + 0 = A

Prodotto logico

A * A = A

_
A * A = 0

A * 1 = A

A * 0 = 0

Proprietà associativa

A + B + C = (A + B) +C = A + (B + C)

A * B * C = (A * B) * C = A * (B * C)

Proprietà commutativa

A + B = B + A

A * B = B * A

Proprietà distributiva

A(B + C) = AB + AC

(A+ B)C = AC + BC

Teorema di De Morgan
________ _ _ _
A + B + C = A * B * C
________ _ _ _
A * B * C = A + B + C

Dopo aver introdotto l'algebra di Boole passiamo ad un esempio pratico.

ESEMPIO

In questo esempio partiremo da una descrizione verbale e arriveremo al circuito logico che descrive quanto noi abbiamo espresso a parole.

Ecco l'esercizio.

Io dormo quando ho sonno, se sono a letto o in poltrona, purchè vi sia buio

Come prima cosa dobbiamo riconoscere quali sono le variabili indipendenti e quelle dipendenti.
Le variabili indipendenti sono:

A = avere sonno
B = essere a letto
C = essere in poltrona
D = presenza del buio

inoltre queste variabili costituiranno gli ingressi della nostra rete logica che andremo a creare, mentre l'uscita della rete è costituita dalla variabile dipendente che è:

U = dormire

Dopo aver identificato le variabili dobbiamo costruire la tabella di verità. Questa tabella sarà costituita da 16 combinazioni, perchè gli ingressi sono 4, infatti 24 = 16, dopo dopodichè nella colonna di sinistra scriverò otto volte 0 e otto volte 1, nella colonna a fianco scriverò quattro 0 e quattro 1, nella colonna a fianco scriverò due volte 0 e due volte 1 e nella colonna della variabile D scriverò una volta 0 e una volta 1, mentre per il momento lascio vuota la colonna dell'uscita. Se non avete capito ecco come deve apparire la tabella di verità:




Rileggendo la frase possiamo compilare la colonna dell'uscita, infatti l'uscita varrà 1 (cioè io dormo) se avrò sonno (quindi A =1) se sono a letto (B = 1) o in poltrona (C = 1) e se c'è buio (D = 1), quindi l'uscita varrà 1 con le combinazioni della riga 12 , 14 e 16.
Per ottenere l'espressione algebrica dobbiamo scegliere se utilizzare la 1° o 2° forma canonica. La differenza tra una e l'altra è che nella 1° guardo le uscite che valgono 1 e moltiplico i termini tra di loro badando però a ne gare le variabili che valgono 0, questa forma è anche detta somma di prodotti, mentre nella seconda forma considero le uscite che valgono zero e sommo le variabili ricordandomi di negare quelle che valgono 1, questa forma è anche detta prodotti di somme.
Nel nostro caso scegliamo la prima forma ed otteniamo la seguente espressione:
_ _
U = ABCD + ABCD + ABCD

Ottenuta l'espressione vediamo se possiamo ridurla.
Infatti si può notare che i termini A e D sono comuni a entrambi, quindi li raccogliamo ed otteniamo questa espressione
_ _
U = AD(BC + BC + BC)

A questo punto raccogliamo la B ed otteniamo
_ _
U = AD[BC + B(C + C)]
_
Sapendo che C + C = 1 otteniamo
_
U = AD(BC + B)
_
Applicando una proprietà (questa non l'ho spiegata perchè non le ho mai capite) B + BC = B+ C ottengo

U = AD(B + C)

A questo punto possiamo disegnare il nostro circuito logico che è il seguente



A breve posterò come minimizzare la funzione utilizzando le mappe di Karnaugh

visto che ho avuto un pò di tempo porto a conclusione l'argomento.

Nel post precedente eravamo arrivati a costruire un crcuito logico partendo da una frase, passando prima in alcune tappe intermedie.
Infatti partendo dalla frase abbiamo ricavato le variabili dipendenti e indipendenti, e sccessivamente abbiamo ricavato la tab. di verità dalla quale è stata ricavata la funzione logica, che opportunamente minimizzata ci ha permesso di ricavare il circuito logico.
Bene ora utilizzeremo un altro metodo per arrivare al circuito. Questo metodo prevede l'utilizzo delle mappe di Karnaugh. Per utilizzare queste mappe sfrutteremo un software apposito.

La parte fino alla tab di verità rimane inalterata, infatti per costruire la mappa ci servirà proprio la tab. di verità. La mappa di karnaugh va compilata nel seguente modo



come si può notare nella mappa sono stati inseriti gli uno nelle combinazioni corrispondenti la tab. di verità.
Fatto questo dobbiamo scegliere se raggruppare gli 0 o gli 1, in questo caso sceglieremo gli 0 perchè ho notato che se dico al software di prendere gli 1 non mi trova il risultato a cui siamo arrivati manualmente (va sapere perchè), comunque utilizzare le mappe di Karnaugh ci permette di trovare già una funzione logica più semplificata, e nulla vieta di semplificarla ulteriormente se è possibile. Infatti semplificare la funzione ci permette di ottenere un circuito logico con pochi componenti, ma cosa più importante non tanto complesso.

Spero di essere stato chiaro e se ci sono dubbi chiedete pure.