Architettura dei Calcolatori: Algebra di Boole - Introduzione

Definizione di Algebra di Boole

L’algebra di Boole, sviluppata da George Boole a metà del XIX secolo, è un sistema algebrico che descrive le operazioni logiche e il comportamento dei circuiti digitali. Essa si basa su un insieme, detto supporto e rappresentato con il simbolo $A$, costituito da due elementi¹, tipicamente rappresentati come 0 e 1, e su due operazioni fondamentali: l’AND (congiunzione logica rappresentato dal simbolo $\land$ o dal simbolo $\cdot$) e l’OR (disgiunzione logica rappresentato dal simbolo $\lor$ o dal simbolo $+$), insieme all’operazione NOT (negazione logica rappresentato dal simbolo $\lnot$ o dal simbolo $'$). L’algebra di Boole trova applicazioni soprattutto nei circuiti digitali, nei linguaggi di programmazione e nella teoria della computazione.

Nell’algebra di Boole, le espressioni logiche possono essere combinate per costruire sistemi complessi, ma la loro struttura è basata su regole precise e ben definite che aiutano a semplificare le operazioni e a verificare la correttezza dei sistemi.

Varibile booleana

Definiamo variabile booleana un simbolo che indica un qualsiasi elemento del supporto (nel contesto del seguente articolo le variabili sono indicate con le lettere minuscole dell’alfabeto latino).

Gli operatori nell’algebra di commutazione

Operatore AND

Operatore OR

Operatore NOT

Proprietà degli operatori

1. Proprietà commutativa

• $a \land b = b \land a$
• $a \lor b = b \lor a$

2. Proprietà distributiva

• $a \lor (b \land c) = (a \lor b)\land(a \lor c)$
• $a \land (b \lor c) = (a \land b)\lor(a \land c)$

3. Proprietà elemento neutro

• $a \land 1 = a$
• $a \lor 0 = a$

4. Proprietà del complemento

• $a \lor \lnot a = 1$
• $a \land \lnot a = 0$

Proprietà dell’Algebra di Boole

L’algebra di Boole è caratterizzata da una serie di proprietà fondamentali, che permettono di manipolare e semplificare le espressioni booleane. Queste proprietà sono analoghe a quelle dell’algebra ordinaria, ma adattate al contesto logico.

1. Associatività

L’associatività afferma che la disposizione delle parentesi non influisce sul risultato di un’operazione. Questa proprietà vale sia per l’operazione AND che per OR:

• $ a \land (b \land c) = (a \land b) \land c $
• $ a \lor (b \lor c) = (a \lor b) \lor c $

2. Idempotenza

L’idempotenza indica che ripetere un’operazione su uno stesso elemento non cambia il risultato:

• $ a \land a = a $
• $ a \lor a = a $

3. Elemento Nullo

L’elemento nullo rappresenta il comportamento di un valore che non influisce sul risultato in un’operazione booleana:

• $ a \land 1 = a $ (l’elemento neutro per l’AND è 1)
• $ a \lor 0 = a $ (l’elemento neutro per l’OR è 0)

4. Unicità dell’Elemento Nullo

Il complemento di $a$ è $\lnot a$ ed è unico.

5. Assorbimento

La proprietà di assorbimento mostra come una combinazione di AND e OR può essere semplificata:

• $ a \lor (a \land b) = A $
• $ a \land (a \lor b) = A $

6. Semplificazione

La semplificazione aiuta a ridurre la complessità delle espressioni booleane:

• $ a \land \neg a = 0 $
• $ a \lor \neg a = 1 $

7. Involuzione

L’involuzione afferma che la doppia negazione di un valore ritorna al valore iniziale:

• $ \neg(\neg a) = a $

8. Leggi di De Morgan

Le leggi di De Morgan sono due regole che consentono di trasformare una negazione di una congiunzione o di una disgiunzione in un’espressione equivalente:

• $ \neg(a \land b) = \neg a \lor \neg b $
• $ \neg(a \lor b) = \neg a \land \neg b $

Espressioni Booleane

1. Espressioni Booleane

Un’espressione booleana è una combinazione di variabili e operatori logici che restituisce un valore booleano, cioè vero (1) o falso (0).

Consideriamo l’espressione booleana:

$(a \land b) \lor \neg c $

Il risultato di questa espressione dipende dai valori di $ a $, $ b $, e $ c $. Se $ a = 1 $, $ b = 1 $, e $ c = 0 $, allora:

$ (1 \land 1) \lor \neg 0 = 1 \lor 1 = 1 $

Quindi l’espressione complessiva è vera.

2. Funzioni Booleane

Una funzione booleana è una funzione che associa a un insieme di variabili booleane un risultato booleano. Può essere espressa come una tabella di verità o tramite espressioni booleane.

Una funzione booleana ha n variabili di input e restituisce un singolo valore di output (0 o 1). Gli input e l’output sono descritti utilizzando gli operatori logici.

Esempio di Funzione Booleana

Prendiamo una funzione booleana $ f(a, b, c) $ che rappresenta l’espressione booleana:

$ f(a, b, c) = (a \land b) \lor \neg c $

Possiamo costruire la tabella di verità che mostra tutti i possibili valori di $ a $, $ b $, e $ c $, e il corrispondente output di $ f $.

La tabella di verità mostra tutte le possibili combinazioni di input (a, b, c) e i corrispondenti valori della funzione booleana.

Esercizi

Semplifica con le proprietà dell’algebra booleana le seguenti espressioni:

1. A + A’ =

2. A + 0 =

3. A · 1 =

4. A · A’ =

5. A + A =

6. 0 + A =

7. A + AB =

8. A · (B + C) =

9. A · (A + B) =

10. AB + A’B =

11. (A + B)(A + C) =

12. A + A’B + A’C =

13. A + A’B + AC =

14. (A + B)(A’ + B’) =

15. A · B + A · B’ + A’ · C =

16. A + A’B + A’C’ =

17. (A + B’)(A’ + C) =

18. AB + AC + A’B’C =

19. (A + B)(A’ + C)(B’ + C) =

20. A · B + A · C + A’B’C =