[ITA] Algebra Booleana e applicazione in elettronica digitale

Oggi parleremo di matematica, nello specifico dell'algebra di Boole, vi invito a leggere comunque il post nonostante l'argomento "particolare" in quanto a fine del post, avrete imparato anche come applicarla in un campo reale e saprete disegnare anche un circuito elettronico digitale di base!

L'algebra Booleana

L'algebra di Boole è una particolare branca dell'algebra dove i valori posso assumere solo due valori il vero e il falso o come generalmente con il metodo più conosciuto 0 (usato per il falso) e 1 (usato per il vero), le operazioni fondamentali quindi non so più l'addizione e moltiplicazione, ma diventano invece somma logica (indicata con OR ) , il prodotto logico (indicato con AND ) ed il complemento logico (indicato con NOT ) la combinazione di questi tre operatori AND, OR e NOT permette di rappresentare qualsiasi funzione booleana si definisce quindi un insieme funzionalmente completo

Proprietà matematiche nell'algebra Booleana

Commutativa
A + B = B + A
A * B = B * A
Associativa
A + ( B + C ) = ( A + B ) + C
A * ( B * C ) = ( A * B ) * C
Assorbimento
A + ( A * B ) = A
A * ( A + B ) = A
Distributiva
A * ( B + C ) = ( A * B ) + ( A * C )
A + ( B * C ) = ( A + B ) * ( A + C )
Idempotenza
A + A = A
A * A = A
Esistenza del minimo e del massimo
A * 0 = 0
A + 1 = 1
Esistenza del complemento
A * !A = 0
A + !A = 1

Le operazioni booleane

Come abbiamo definito le operazioni booleane fondamentali sono AND OR e NOT, parlando di variabili che possono assumere solo il valore 0 e 1 possiamo realizzare una vera e propria tabella con tutte le combinazioni possibili e i possibili risultati, queste tabelle sono chiamate Tavole di verità e prendono questo nome perché il loro scopo è ricercare la verità, quindi il vero quindi il valore 1.
Le tavole di verità sono anche il fondamento per la realizzazione di funzione logiche e della sua applicazione nell'elettronica digitale, ma andiamo con ordine

A OR B ( A + B )

L'operazione logica OR può essere vista come la somma logica in algebra booleana, quindi andando a vedere tutte le possibili combinazioni che si possono avere, A può assumere valore 0 e 1 e B analogamente può assumere solo valore 0 e 1 quindi il totale delle combinazioni possibili è 2² = 4 che andremo a rappresentare

A B Y
0 0 0
0 1 1
1 0 1
1 1 1

E' pacifico notare che secondo le proprietà sopra elencate la somma logica di variabili booleane è vera quando almeno uno dei due è vero

A AND B ( A * B )

L'operazione logica AND può essere vista come la somma logica in algebra booleana, quindi andando a vedere tutte le possibili combinazioni che si possono avere, A può assumere valore 0 e 1 e B analogamente può assumere solo valore 0 e 1 quindi il totale delle combinazioni possibili è 2² = 4 che andremo a rappresentare

A B Y
0 0 0
0 1 0
1 0 0
1 1 1

Sempre secondo le proprietà dell'algebra booleana il prodotto logico è vero solo quando entrambe le variabili logiche sono vere

NOT A (!A) _{(la notazione corretta sarebbe A con un trattino sopra, non è presente nella tastiera, viene quindi usata la notazione dei linguaggi di programmazione come il C)}

L'operazione logica NOT è il complemento in algebra booleana e semplicemente ha il compito di "invertire" lo stato attuale della variabile booleana.

A Y
0 1
1 0

Come detto in precedenza l'uso combinato di queste 3 funzioni logiche può rappresentare qualsiasi funzione booleana.

Le applicazioni in Elettronica digitale

Come vi avevo promesso a inizio lettura vi insegno come applicare l'algebra booleana all'elettronica digitale e come realizzare dei circuiti, utilizzando solo queste 3 porte logiche, supponiamo quindi di dover progettare il circuito per un compattatore di rifiuti, il compattatore di rifiuti è pensato per funzionare così, è presente un interruttore di sicurezza (A) che se premuto spegne immediatamente il compattattore in modo manuale, sono previsti inoltre un pulsante (B) per far partire il compattatore di rifiuti dalla gru e il pulsante (C) per far partire il compattatore di rifiuti da un'altra postazione di comando, oltre al sistema di sicurezza manuale è prevista anche un fotocellula (D) che in caso di ostacoli imprevisti ferma il macchinario in automatico

Ora passiamo quindi a realizzare questa funzione in 4 variabili booleane (quindi 2⁴ = 16 combinazioni) facendo la tavola di verità

Possiamo procede meccanicamente e valutare ognuna delle 16 combinazioni, ma a volte usare la logica ci può aiutare a risolvere il problema in modo più veloce, sappiamo per certo che se è azionato il pulsante di sicurezza manuale (A) il compattatore è spento, quindi tutti i casi da 9 a 16 ovvero quando A ha valore 1 lo stato del compattatore è su spento, quindi 0
Possiamo considerare analogamente 0 anche i casi in cui la fotocellula D è attiva quindi oltre a quelli sopra anche le combinazioni 2 4 6 8 sono sicuramente 0
Rimangono quindi da valutare solo 4 combinazioni, ed è molto semplice da trovare le verità in quando l'1 è presente solo quando almeno uno tra B e C sono vere, quindi tutti i casi tranne il primo dove è tutto spento (probabilmente sono tutti in pausa pranzo)

A B C D Y
0 0 0 0 0
0 0 0 1 0
0 0 1 0 1
0 0 1 1 0
0 1 0 0 1
0 1 0 1 0
0 1 1 0 1
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 0
1 1 0 1 0
1 1 1 0 0
1 1 1 1 0

Quindi le uniche combinazioni in cui si ha un 1 come risultato sono 0010 0100 0110 (rispettivamente ABCD) a questo punto scriviamo la formula dell'espressione booleana facendo si che dove si vede uno "zero" nelle variabili si usa la negazione per averla come 1 ad esempio la combinazione :

• 0010 diventa !A!BC*!D
• 0100 diventa !AB!C*!D
• 0110 diventa !ABC*!D

quindi Y = !A * !B * C * !D + !A * B * !C * !D + !A * B * C * !D

Ora nonostante il problema sia già risolto possiamo la soluzione non è ovviamente ottimizzata in quanto verrebbero usate una ventina di porte logiche il risultato va quindi semplificato, o usando i teoremi dell'algebra di boole oppure usando uno strumento grafico, le mappe di Karnaught che vi aiuteranno ad ottenere la semplificazione massima ottenibile semplicemente utilizzando un grafico.

Creiamo un griglia 4x4 mettendo sull'asse delle x tutti i valori delle variabili AB 00 01 10 11, stessa cosa per CD per l'asse della y e riempiamo con 1 i valori delle celle corrispondenti come da immagine.

A questo punto raggruppiamo gli uno, per effettuare questi raggruppamenti le uniche regole da seguire sono, che siano adiacenti tra di loro in orizzontale o in verticale (il bordo sinistro viene considerato adiacente al bordo destro, quindi un eventuale 1 in posizione 0000 sarebbe adiacente con un un 1 in 1100 e anche con 0011 come se fosse una sfera) e i raggruppamenti devono essere fatti con potenze di 2, quindi o 1 (se non è adiacente a nessun altro 1) di 2 (come nel nostro caso) di 4 (se tipo gli 1 formassero un quadrato), i raggruppamenti devono essere rettangoli o quadrati

Ma torniamo al nostro caso e tracciamo i nostri raggruppamenti

A questo punto si semplifica, si va a guardare quali BIT all'interno di un raggruppamento prendiamo il gruppo arancione:

• A cambia valore da 0 a 1
• B cambia valore da 0 a 1
• C e D mantengono il valore invariato rispettivamente in 1 e 0

Karnought ci insegna che se cambia il valore non si prende il considerazione al fine della semplificazione, me invece
varia si prendono usando i complementi per ottenere gli 1, quindi semplificando il rettangolo arancione otteniamo
C * !D
Procediamo nel solito modo per il gruppo verde:

• A rimane a 0
• B varia da 0 a 1
• C e D rimangono invariati quindi
  !A * C * !D

La formula semplificata è quindi

Y = C * !D + !A * C *!D

Una formula decisamente più compatta e con meno componenti rispetto alla versione precedente, ovviamente non tutto si può semplificare con le mappe di Karnought in quanto se aumentano le variabili di ingresso la rappresentazione grafica risulta essere molto più complicata.

Crediti:
Tutte le immagini sono di mia realizzazione elaborate con Excel 2017 di cui detengo originale licenza.

Bibliografia
[1] Steven Givant e Paul Halmos, Introduction to Boolean Algebras, Undergraduate Texts in Mathematics, Springer, 2009
[2] Sito Matematicamente, appunti di Algebra Booleana(https://www.matematicamente.it/staticfiles/appunti/A.Urso-Logica_booleana.pdf)
[3] Charles Kime, Reti logiche, Pearson, 2002.
[4] Mappe di Karnaught