Definizione di Algebra Booleana

Il costo dei circuiti che implementano la logica binaria in tutti i dispositivi digitali e computer di oggi è un fattore importante affrontato dai progettisti, siano essi ingegneri informatici, ingegneri elettronici o informatici.

Trovare realizzazioni più semplici ed economiche, ma equivalenti, di un circuito può produrre enormi benefici nel ridurre il costo complessivo del progetto.

I metodi matematici che semplificano i circuiti si basano principalmente sull'algebra booleana. Pertanto, a partire da questa lezione, studieremo questa algebra. Apprenderemo un vocabolario di base e una breve fondazione nell'algebra booleana che ci permetterà di ottimizzare circuiti semplici e di comprendere lo scopo degli algoritmi utilizzati dagli strumenti software per ottimizzare circuiti complessi che coinvolgono milioni di porte logiche.

Concetti Chiave
  • L'algebra booleana è una struttura algebrica fondamentale per la logica digitale, che definisce operazioni su variabili binarie.
  • Questa lezione introduce i concetti base dell'algebra booleana, le sue operazioni e le proprietà fondamentali.
  • L'algebra booleana è essenziale per la progettazione e l'ottimizzazione dei circuiti logici digitali.
  • Comprendere l'algebra booleana permette di semplificare circuiti complessi e di migliorare l'efficienza dei sistemi digitali.
  • I concetti di chiusura, associatività, commutatività, esistenza dell'elemento identità e inverso sono gli assiomi fondamentali che definiscono l'algebra booleana.

Alcune Definizioni Preliminari

L'algebra booleana, come qualsiasi altro sistema matematico deduttivo, può essere definita come un insieme di elementi, un insieme di operatori e un numero di assiomi o postulati non dimostrati.

Un insieme di elementi è qualsiasi collezione di oggetti, che solitamente hanno una proprietà comune.

Se S è un insieme, e x e y sono certi oggetti, allora la notazione:

x \in S

significa che x è un membro dell'insieme S. Se invece scriviamo:

y \notin S

significa che y non è un elemento di S.

Un insieme con un numero numerabile di elementi è specificato da parentesi graffe:

A = \left\{1, 2, 3, 4\right\}

indica che gli elementi dell'insieme A sono i numeri 1, 2, 3 e 4.

Un operatore binario definito su un insieme S di elementi è una regola che assegna, a ogni coppia di elementi da S, un elemento unico di S.

Come esempio, consideriamo la relazione:

a \star b = c

Diciamo che \star è un operatore binario se si rispettano due condizioni:

  1. a, b, c \in S: ossia a, b e c sono elementi di S;
  2. L'operatore \star specifica una regola per trovare c dalla coppia (a, b).

Spesso, un operatore di questo tipo prende anche il nome di legge di composizione interna.

Tuttavia, \star non è un operatore binario c \notin S, ossia se l'elemento risultante c non appartiene all'insieme S.

I postulati di un sistema matematico formale formano le assunzioni di base dalle quali è possibile dedurre le regole, i teoremi e le proprietà del sistema. I postulati più comuni utilizzati per formulare varie strutture algebriche sono i seguenti:

  • Chiusura: Un insieme S è chiuso rispetto a un operatore binario se, per ogni coppia di elementi di S, l'operatore binario specifica una regola per ottenere un elemento unico di S.

    Per esempio, l'insieme dei numeri naturali \mathbb{N} è chiuso rispetto all'operatore binario + (ossia rispetto all'addizione) dalle regole dell'addizione aritmetica, poiché, per qualsiasi a, b \in \mathbb{N}, esiste un unico c \in \mathbb{N} tale che a + b = c.

    L'insieme dei numeri naturali non è chiuso rispetto all'operatore binario - (ossia rispetto alla sottrazione) dalle regole della sottrazione aritmetica, perché, ad esempio:

    2 - 3 = -1

    e

    2, 3 \in \mathbb{N} \quad \text{ma} \quad (-1) \notin \mathbb{N}

  • Associatività: Un operatore binario \star su un insieme S si dice associativo ogni volta che

    (x \star y) \star z = x \star (y \star z) \text{ per tutti } x, y, z \in S

  • Commutatività: Un operatore binario \star su un insieme S si dice commutativo ogni volta che

    x \star y = y \star x \quad \forall x, y \in S

  • Esistenza dell'elemento Identità: Si dice che un insieme S ha un elemento identità rispetto a un'operazione binaria \star su S se esiste un elemento e ∈ S con la proprietà che

    e \star x = x \star e = x \quad \forall x \in S

    Ad esempio, l'elemento 0 è un elemento identità rispetto all'operatore binario + sull'insieme degli interi \mathbb{Z} poiché

    x + 0 = 0 + x = x \quad \forall x \in \mathbb{Z}

  • Esistenza dell'Elemento Inverso: Si dice che un insieme S che ha l'elemento identità e rispetto a un operatore binario \star ha un inverso ogni volta che:

    \forall x \in S \quad \exists y \in S: \quad x \star y = e

    Ad esempio, nell'insieme degli interi, \mathbb{Z}, e l'operatore +, con e = 0, l'inverso di un elemento a è (-a), poiché a + (-a) = 0.

  • Legge Distributiva: Se \star e \circ sono due operatori binari su un insieme S, \star si dice distributivo su \circ ogni volta che

    x \star (y \circ z) = (x \star y) \circ (x \star z)

Un campo è un esempio di struttura algebrica. Un campo è un insieme di elementi, corredato di due operatori binari, ognuno avente le proprietà da 1 a 5 e entrambi gli operatori che si combinano per dare la proprietà 6. L'insieme dei numeri reali, insieme agli operatori binari + e \cdot (somma e moltiplicazione), forma il campo dei numeri reali. Il campo dei numeri reali è la base per l'aritmetica e l'algebra ordinaria. Gli operatori e i postulati hanno i seguenti significati:

  1. L'operatore binario + definisce l'addizione.
  2. L'identità additiva è 0.
  3. L'inverso additivo definisce la sottrazione.
  4. L'operatore binario \cdot definisce la moltiplicazione.
  5. L'identità moltiplicativa è 1.

Per a \neq 0, l'inverso moltiplicativo di a è 1/a e definisce la divisione (cioè, a \cdot 1/a = 1).

L'unica legge distributiva applicabile è quella di \cdot su +:

a \cdot (b + c) = (a \cdot b) + (a \cdot c)

Definizione Assiomatica dell'Algebra Booleana

Nel 1854, George Boole sviluppò un sistema algebrico ora chiamato algebra booleana.

Nel 1938, Claude E. Shannon introdusse un'algebra booleana a due valori chiamata algebra di commutazione che rappresentava le proprietà dei circuiti elettrici di commutazione bistabile. Per la definizione formale dell'algebra booleana, impiegheremo i postulati formulati da E. V. Huntington nel 1904.

L'algebra booleana è una struttura algebrica definita da un insieme di elementi, B, corredato di due operatori binari, + e \cdot, purché i seguenti postulati (di Huntington) siano soddisfatti:

  1. Chiusura di entrambe le operazioni:

    • La struttura è chiusa rispetto all'operatore +.
    • La struttura è chiusa rispetto all'operatore \cdot.

  2. Identità per le due operazioni:

    • L'elemento 0 è un elemento identità rispetto a +; cioè:

      x + 0 = 0 + x = x

    • L'elemento 1 è un elemento identità rispetto a \cdot; cioè:

      x \cdot 1 = 1 \cdot x = x

  3. Commutatività delle due operazioni:

    • La struttura è commutativa rispetto a +; cioè:

      x + y = y + x

    • La struttura è commutativa rispetto a \cdot; cioè:

      x \cdot y = y \cdot x

  4. Distributività delle singole operazioni sulle altre:

    • L'operatore \cdot è distributivo su +; cioè:

      x \cdot (y + z) = (x \cdot y) + (x \cdot z)

    • L'operatore + è distributivo su \cdot; cioè:

      x + (y \cdot z) = (x + y) \cdot (x + z)

  5. Esistenza del complemento:

    Per ogni elemento x \in B, esiste un elemento x' \in B (chiamato il complemento di x) tale che:

    • x + x' = 1
    • x \cdot x' = 0

  6. Esistono almeno due elementi x, y \in B tali che x \neq y.

Confrontando l'algebra booleana con l'aritmetica e l'algebra ordinaria (il campo dei numeri reali), notiamo le seguenti differenze:

  1. I postulati di Huntington non includono la legge associativa. Tuttavia, questa legge vale per l'algebra booleana e può essere derivata (per entrambi gli operatori) dagli altri postulati.
  2. La legge distributiva di + su \cdot (cioè, x + (y \cdot z) = (x + y) \cdot (x + z)) è valida per l'algebra booleana, ma non per l'algebra ordinaria.
  3. L'algebra booleana non ha inversi additivi o moltiplicativi; pertanto, non ci sono operazioni di sottrazione o divisione.
  4. Il postulato 5 definisce un operatore chiamato complemento che non è disponibile nell'algebra ordinaria.
  5. L'algebra ordinaria si occupa dei numeri reali, che costituiscono un insieme infinito di elementi. L'algebra booleana si occupa dell'insieme di elementi B ancora non definito, ma nell'algebra booleana a due valori definita di seguito (e di interesse nel nostro uso successivo), B è definito come un insieme con solo due elementi, 0 e 1.

L'algebra booleana assomiglia all'algebra ordinaria in alcuni aspetti. La scelta dei simboli + e \cdot è intenzionale, per facilitare le manipolazioni algebriche booleane da parte di persone già familiari con l'algebra ordinaria. Sebbene si possa usare qualche conoscenza dall'algebra ordinaria per trattare l'algebra booleana, il principiante deve stare attento a non sostituire le regole dell'algebra ordinaria dove non sono applicabili.

È importante distinguere tra gli elementi dell'insieme di una struttura algebrica e le variabili di un sistema algebrico. Per esempio, gli elementi del campo dei numeri reali sono numeri, mentre le variabili come a, b, c, ecc., usate nell'algebra ordinaria, sono simboli che rappresentano numeri reali. Allo stesso modo, nell'algebra booleana, si definiscono gli elementi dell'insieme B, e le variabili come x, y, e z sono meramente simboli che rappresentano gli elementi. A questo punto, è importante rendersi conto che, per avere un'algebra booleana, si deve mostrare che

  1. gli elementi dell'insieme B,
  2. le regole di operazione per i due operatori binari, e
  3. l'insieme di elementi, B$, insieme ai due operatori, soddisfano i sei postulati di Huntington.

Si possono formulare molte algebre booleane, a seconda della scelta degli elementi di B e delle regole di operazione. In questo corso, trattiamo solo un'algebra booleana a due valori (cioè, un'algebra booleana con solo due elementi). L'algebra booleana a due valori ha applicazioni nella teoria degli insiemi (l'algebra delle classi) e nella logica proposizionale. Il nostro interesse qui è nell'applicazione dell'algebra booleana ai circuiti (come le porte logiche) comunemente usati nei dispositivi digitali e nei computer.

Algebra Booleana a Due Valori

Un'algebra booleana a due valori è definita su un insieme di due elementi, B = \left\{ 0, 1 \right\}, con regole per i due operatori binari + e \cdot come mostrato nelle seguenti tabelle degli operatori (la regola per l'operatore complemento è per la verifica del postulato 5):

x y x \cdot y x + y
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 1
Tabella 1: Risultato delle operazioni somma e prodotto
x x'
0 1
1 0
Tabella 2: Risultato dell'operazione complemento

Queste regole sono esattamente le stesse delle operazioni AND, OR e NOT, rispettivamente, che abbiamo visto in precedenza.

Dobbiamo ora mostrare che i postulati di Huntington sono validi per l'insieme B = \left\{ 0, 1 \right\} e i due operatori binari + e \cdot.

  • Chiusura:

    che la struttura sia chiusa rispetto ai due operatori è ovvio dalle tabelle, poiché il risultato di ogni operazione è o 1 o 0 e 1, 0 \in B.

  • Esiste l'identità per le due operazioni:

    • L'elemento identità per + è 0, poiché x + 0 = x e 0 + x = x per ogni x \in B.
    • L'elemento identità per \cdot è 1, poiché x \cdot 1 = x e 1 \cdot x = x per ogni x \in B.

    Questo stabilisce i due elementi identità, 0 per + e 1 per \cdot, come definito dal postulato 2.

    Si può verificare facilmente queste identità dalle tabelle degli operatori.

  • Commutatività:

    Le leggi commutative sono ovvie dalla simmetria delle tabelle degli operatori binari.

  • Legge Distributiva:

    La legge distributiva per le due operazioni può essere mostrata dalle tabelle degli operatori formando una tavola di verità di tutti i possibili valori di x, y, e z.

    Per ogni combinazione, deriviamo:

    x \cdot (y + z) = (x \cdot y) + (x \cdot z)
    x y z y + z x \cdot (y + z) x \cdot y x \cdot z (x \cdot y) + (x \cdot z)
    0 0 0 0 0 0 0 0
    0 0 1 1 0 0 0 0
    0 1 0 1 0 0 0 0
    0 1 1 1 0 0 0 0
    1 0 0 0 0 0 0 0
    1 0 1 1 1 0 1 1
    1 1 0 1 1 1 0 1
    1 1 1 1 1 1 1 1
    Tabella 3: Dimostrazione della legge distributiva del prodotto su somma

    Analogamente, La legge distributiva di + su \cdot può essere mostrata valere per mezzo di una tavola di verità simile a quella precedente.

  • Complemento:

    Dalla tabella del complemento, si mostra facilmente che

    • x+x' = 1, poiché 0 + 0' = 0 + 1 = 1 e 1 + 1' = 1 + 0 = 1.
    • x \cdot x' = 0, poiché 0 \cdot 0' = 0 \cdot 1 = 0 e 1 \cdot 1' = 1 \cdot 0 = 0.

    Così, il postulato 5 è verificato.

  • Postulato 6:

    Il postulato 6 è soddisfatto perché l'algebra booleana a due valori ha due elementi, 1 e 0, con 1 \neq 0.

Abbiamo appena stabilito un'algebra booleana a due valori avente un insieme di due elementi, 1 e 0, due operatori binari con regole equivalenti alle operazioni AND e OR, e un operatore complemento equivalente all'operatore NOT.

Così, l'algebra booleana è stata definita in modo matematico formale ed è stata mostrata essere equivalente alla logica binaria presentata euristicamente nella lezione apposita.

La presentazione euristica è utile nel comprendere l'applicazione dell'algebra booleana ai circuiti delle porte logiche. La presentazione formale è necessaria per sviluppare i teoremi e le proprietà del sistema algebrico. L'algebra booleana a due valori definita in questa lezione è anche chiamata "algebra di commutazione" dagli ingegneri. Per enfatizzare le somiglianze tra l'algebra booleana a due valori e altri sistemi binari, quell'algebra è stata chiamata "logica binaria". D'ora in poi, tralasceremo l'aggettivo "a due valori" dall'algebra booleana nelle lezioni successive.