Algebra di Boole - assiomi, teoremi e complemento di una funzione

Un circuito digitale realizza una funzione booleana; per scegliere il circuito più semplice si manipola l'espressione con le regole dell'algebra di Boole. Questa nota raccoglie le regole, mostra come si dimostrano e come si usano per semplificare e per complementare una funzione.

Che cos'è un'algebra di Boole

Un'algebra di Boole è un insieme con due operazioni, somma logica (OR, $+$) e prodotto logico (AND, $\cdot$), più il complemento (NOT), in cui valgono la proprietà distributiva, l'esistenza di un minimo ($0$) e di un massimo ($1$) e l'esistenza del complemento. George Boole la propose a metà Ottocento per la logica; Claude Shannon (tesi di master, MIT, 1938) mostrò che i segnali in una rete di interruttori a due stati (aperto/chiuso) seguono le sue regole: da lì deriva il metodo di analisi e progetto dei circuiti digitali.

Per il nostro scopo le variabili assumono i valori $0$ e $1$ (logica binaria). Una funzione booleana è un'espressione formata da variabili, costanti $0,1$ e dalle operazioni AND, OR, NOT. Un'espressione si semplifica per usare meno porte (circuito più piccolo, veloce e che consuma meno).

Le identità fondamentali

Proprietà (identità fondamentali dell'algebra di Boole). Le identità vengono a coppie duali: la seconda si ottiene dalla prima scambiando AND con OR e $0$ con $1$.

nome	forma OR	forma AND (duale)
elemento neutro	$X+0=X$	$X\cdot1=X$
minimo e massimo	$X+1=1$	$X\cdot0=0$
idempotenza	$X+X=X$	$X\cdot X=X$
complemento	$X+\overline X=1$	$X\cdot\overline X=0$
doppia negazione	$\overline{\overline X}=X$
commutativa	$X+Y=Y+X$	$XY=YX$
associativa	$X+(Y+Z)=(X+Y)+Z$	$X(YZ)=(XY)Z$
distributiva	$X(Y+Z)=XY+XZ$	$X+YZ=(X+Y)(X+Z)$

Esempio. $(A+B)(A+\overline B)=A+B\overline B=A+0=A$ (seconda distributiva e complemento).

Legge di dualità: se un'identità è vera, lo è anche la sua duale. Attenzione: la seconda distributiva ($X+YZ=(X+Y)(X+Z)$) non vale nell'algebra ordinaria, ma vale in quella booleana. Anche $X+X=X$ e $X+1=1$ non valgono nell'aritmetica comune.

Queste regole sono gli assiomi: tutto il resto si deduce da esse (o si controlla con la tabella di verità). L'espressione $X+Y=Y+X$ è quindi un assioma (la proprietà commutativa), non un teorema da dimostrare.

Teorema di De Morgan

Teorema (De Morgan)

$$\overline{X+Y}=\overline X\cdot\overline Y,\qquad\overline{X\cdot Y}=\overline X+\overline Y .$$

Esempio. $\overline{A+\overline B\,C}=\overline A\cdot(B+\overline C)$: si scambiano AND e OR e si negano i letterali.

Si estende a più variabili: $\overline{X+Y+Z}=\overline X\,\overline Y\,\overline Z$ (e non $\overline X\,\overline Y+\overline Z$, un errore frequente). Forma generalizzata: per complementare un'espressione si scambiano AND e OR e si negano tutte le variabili e le costanti.

Dimostrazione per induzione perfetta (si provano tutte le combinazioni dei valori delle variabili): per $\overline{X+Y}=\overline X\,\overline Y$

Le colonne $\overline{X+Y}$ e $\overline X\,\overline Y$ coincidono in tutte le righe. De Morgan rende la NAND e la NOR universali (Porte logiche, ritardi e porte universaliLe porte AND, OR, NOT realizzano le operazioni dell'algebra di Boole; NAND, NOR, XOR e XNOR ne derivano. Ogni funzione si descrive con la tabella di verità ($2^n$ righe). XOR a più ingressi = funzione di disparità (1 se gli 1 sono in numero dispari). Una porta reale ha ritardo di propagazione $t_G$ (diverso per 0→1 e 1→0): in un diagramma temporale l'uscita cambia $t_G$ dopo l'ingresso. NAND e NOR sono universali: bastano da sole a realizzare qualunque funzione. In VHDL: and, or, not, nand, nor, xor, xnor.Porte logiche, ritardi e porte universali →): $X+Y=\overline{\overline X\,\overline Y}$.

Teoremi di semplificazione

Teorema (semplificazione: assorbimento, adiacenza e consenso)

nome	forma	dimostrazione
assorbimento	$X+XY=X$	$X+XY=X(1+Y)=X\cdot1=X$
assorbimento (dual)	$X(X+Y)=X$	duale
	$X+\overline XY=X+Y$	$X+\overline XY=(X+\overline X)(X+Y)=1\cdot(X+Y)$
adiacenza (unificazione)	$XY+X\overline Y=X$	$X(Y+\overline Y)=X\cdot1=X$
consenso	$XY+\overline XZ+YZ=XY+\overline XZ$	vedi sotto

Esempio. $X+\overline XY=X+Y$: per $X=0,Y=1$ entrambi i membri valgono $1$, per $X=0,Y=0$ valgono $0$.

Assorbimento ($X+XY=X$): il secondo termine si può omettere perché ridondante. Si dimostra anche con la tabella: la colonna $X+XY$ coincide con la colonna $X$ ($0,0,1,1$).

Consenso. Nel primo termine compare $Y$ insieme a $X$, nel secondo $Z$ insieme a $\overline X$, e il terzo ($YZ$) è sempre coperto da uno dei due: se $X=1$ e $Y=Z=1$ è già coperto da $XY$; se $X=0$ è coperto da $\overline XZ$. Dimostrazione algebrica: si moltiplica il terzo termine per $(X+\overline X)=1$: $$XY+\overline XZ+YZ=XY+\overline XZ+YZ(X+\overline X)=XY+\overline XZ+XYZ+\overline XYZ=XY(1+Z)+\overline XZ(1+Y)=XY+\overline XZ,$$ perché $1+Z=1$ e $1+Y=1$. Il teorema vale anche nella forma duale $(X+Y)(\overline X+Z)(Y+Z)=(X+Y)(\overline X+Z)$.

Esempi di semplificazione

Esempio 1. $F=A+\overline AB+\overline A\,\overline BC$. Si raccoglie $\overline A$ negli ultimi due termini: $F=A+\overline A(B+\overline BC)$. Per $X+\overline XY=X+Y$ con $X=B$, $Y=C$: $B+\overline BC=B+C$. Quindi $F=A+\overline A(B+C)$ e, applicando ancora la stessa regola con $X=A$: $F=A+B+C$. Controllo: l'unica combinazione che dà $0$ è $A=B=C=0$; nella forma originale $A=0,B=0,C=0$ dà $0+0+0=0$ ✓, e ogni altra combinazione dà $1$.

Esempio 2. $XY+\overline XZ+YZ=XY+\overline XZ$ (consenso): da tre prodotti a due. Se i tre termini sono realizzati con porte, si risparmia una AND e un ingresso della OR.

Complemento di una funzione

Proprietà (complemento di una funzione). Il complemento $\overline F$ ha la tabella di verità con $0$ e $1$ scambiati nella colonna dell'uscita. Per ottenerne l'espressione si hanno due vie.

(a) De Morgan. Esempio: $F_1=\overline AB+A\overline B$ (XOR). $\overline{F_1}=\overline{\overline AB}\cdot\overline{A\overline B}=(A+\overline B)(\overline A+B)=A\overline A+AB+\overline B\,\overline A+\overline BB=AB+\overline A\,\overline B$ (XNOR) ✓.

(b) Duale e negazione dei letterali. Si scrive l'espressione duale (scambio di AND/OR e di $0/1$) e poi si nega ogni letterale. Stesso esempio: il duale di $\overline AB+A\overline B$ è $(\overline A+B)(A+\overline B)$; negando i letterali si ottiene $(A+\overline B)(\overline A+B)$, uguale al risultato di (a) ✓.

Esempio. $F=A+B\overline C$ ha $\overline F=\overline A\cdot(\overline B+C)$ (De Morgan); per $A=0,B=1,C=0$ si ha $F=1$ e $\overline F=0$.

Esempio più ricco. $F_2=\overline AB+C(\overline A+D)$. Per (b): duale $(\overline A+B)\cdot(C+\overline AD)$, negando i letterali $\overline{F_2}=(A+\overline B)(\overline C+A\overline D)$. Sviluppando il prodotto: $\overline{F_2}=A\overline C+A\cdot A\overline D+\overline B\,\overline C+\overline B A\overline D=A\overline C+A\overline D+\overline B\,\overline C+A\overline B\,\overline D$; l'ultimo termine contiene $A\overline D$, quindi è assorbito ($A\overline D+A\overline B\,\overline D=A\overline D$) e resta $\overline{F_2}=A\overline C+A\overline D+\overline B\,\overline C$. Si può controllare con la tabella di verità (16 righe, quattro variabili) che $F_2+\overline{F_2}=1$ e $F_2\cdot\overline{F_2}=0$ per ogni combinazione.

Letterali e costo

Un letterale è ogni occorrenza di una variabile, diretta o negata. $AB+\overline AC$ ha 2 termini e 4 letterali. Due criteri di costo di una forma a due livelli:

• numero di letterali (si ricava dall'espressione, ma non sempre rappresenta bene il circuito);
• numero di ingressi delle porte (gate input cost): si somma il numero di ingressi di tutte le porte del diagramma; è proporzionale al numero di transistor e connessioni, quindi più accurato. In una somma di prodotti: ingressi di ogni AND (con almeno 2 letterali) più ingressi della OR finale.

Esempio. $F=AB+\overline AC$: 2 AND a 2 ingressi $+$ OR a 2 ingressi $\Rightarrow$ $2+2+2=6$ ingressi (4 letterali); gli inverter, se contati, aggiungono un ingresso ciascuno. La forma di costo minimo non è necessariamente unica.

Errori comuni

• De Morgan sbagliato: $\overline{X+Y+Z}\ne\overline X\,\overline Y+\overline Z$; vanno complementati tutti i letterali e scambiati tutti i connettivi.
• Applicare l'assorbimento a termini non contenuti l'uno nell'altro ($X+YZ\ne X$).
• Credere che $X+X'Y=X$ (è $X+Y$).
• Dimenticare di verificare il risultato con la tabella di verità (o sostituendo valori) quando il passaggio algebrico è lungo.