Algebra booleana e circuiti logici

Algebra e circuiti elettronici

I computer operano con segnali elettrici con valori di potenziale discreti. Sono considerati significativi soltanto due potenziali (high/low), mentre i potenziali intermedi, che si verificano durante le transizioni di potenziale, non vengono considerati. L’aritmetica binaria è stata adottata proprio perché i bit sono rappresentabili naturalmente tramite elementi elettronici in cui siamo in grado di distinguere i due stati del potenziale elettrico (high/low).

Il funzionamento dei circuiti elettronici

Il funzionamento dei circuiti elettronici può essere modellato tramite l'algebra di Boole, che prevede solo due valori:

• Valore logico True (1 o asserted) → livello di potenziale alto
• Valore logico Falso (0 o deasserted) → livello di potenziale basso

Le operazioni logiche booleane vengono utilizzate per combinare i valori. Un blocco logico è un circuito elettronico con linee (fili) in input e output, e possiamo associare variabili logiche con le varie linee in input/output. I valori che le variabili possono assumere sono quelli dell’algebra di Boole. Il circuito calcola una o più funzioni logiche, ciascuna esprimibile tramite la combinazione di operazioni dell’algebra di Boole sulle variabili in input.

Tipi di circuiti

• Circuito combinatorio: senza elementi di memoria - produce output che dipende funzionalmente solo dall’input.
• Circuito sequenziale: con elementi di memoria - produce output che dipende non solo dall’input ma anche dallo stato della memoria.

All'inizio ci concentreremo sui circuiti combinatori.

Algebra booleana

Funzione logica

Una funzione logica è completamente specificata tramite un'equazione logica, con bit in input e output rappresentati tramite variabili logiche (con valori 0 o 1). Gli input sono combinati tramite le operazioni di somma (OR), prodotto (AND) e inversione (NOT) logica dell’algebra di Boole:

• OR (A+B): risultato uguale a 1 (true) se almeno un input è 1 (true).
• AND (A·B): risultato uguale a 1 (true) solo se tutti gli input sono 1 (true).
• NOT (¬A): risultato uguale all’inverso dell’input (0→1 oppure 1→0).

Tabelle di verità

Tabelle di verità delle operazioni di NOT, AND, OR:

X = ¬A

X = A · B

X = A + B

Proprietà dell'algebra di Boole

• Identità: A+0=A
• Nullo: A+1=1
• Idempotente: A+A=A
• Inverso: A+(¬A)=1
• Commutativa: A+B=B+A
• Associativa: A+(B+C)=(A+B)+C
• Distributiva: A·(B+C)=(A·B)+(A·C)
• DeMorgan: ¬(A+B)=(¬A)·(¬B)

Ad esempio, gli output D ed E della precedente tabella di verità possono essere espressi come equazioni logiche, semplificate applicando le proprietà di sopra:

D = ¬(¬A + B·C) + (¬A + ¬B·C) + (A + B · ¬C) = E = (¬A + ¬B·C) + (A + ¬B·C)

Dalle equazioni logiche ai circuiti combinatori

Porte logiche:

• AND: A · B
• OR: A + B
• NOT: ¬A

Esempio di equazione e corrispondente circuito: ¬((AB) + (¬BC))

Operazioni NAND o NOR

NAND: porta e tabella di verità

NAND (inverso dell’operazione AND): ¬(A · B) = A NAND B

NOR: porta e tabella di verità

NOR (inverso operazione OR): ¬(A + B) = A NOR B

Si può dimostrare che le operazioni NAND o NOR (e le corrispondenti porte) sono sufficienti per implementare qualsiasi funzione logica.

NAND

• ¬A = A + 0 = ¬(A · 1) = A NAND 1
• A+B = ¬(¬A · ¬B) = ¬((A · B) · ¬ ¬(A · B)) = ((A NAND B), (A NAND B))
• A · B = (A · B) · 0 = ¬((A · B)+0) = ¬((A NAND B), (A NAND B))

NOR

• ¬A = A + 1 = ¬(A + 1) = A NOR 1
• A+B = (A+B) · ¬(A + B) · 1) = ((A NOR B) (A NOR B))
• A · B = ¬ (¬A + ¬B) = ¬((A + B) = (A NOR B) (A NOR B))