Algebra di Boole e porte logiche

Una variabile booleana vale 0 (falso) o 1 (vero). Una funzione booleana di $n$ variabili associa 0 o 1 a ciascuna delle $2^n$ combinazioni di ingresso ed è descritta completamente dalla sua tabella di verità.

Operatori e porte

Definizione (porte AND, OR, NAND, NOR, XOR e XNOR)

$A$	$B$	AND $AB$	OR $A+B$	NAND $\overline{AB}$	NOR $\overline{A+B}$	XOR $A \oplus B$	XNOR $\overline{A\oplus B}$
0	0	0	0	1	1	0	1
0	1	0	1	1	0	1	0
1	0	0	1	1	0	1	0
1	1	1	1	0	0	0	1

Esempio. Con $A=1$ e $B=0$: AND $=0$, OR $=1$, NAND $=1$, NOR $=0$, XOR $=1$, XNOR $=0$.

NOT: $\overline{0} = 1$, $\overline{1} = 0$.

• AND vale 1 solo se tutti gli ingressi sono 1; OR vale 1 se almeno uno è 1.
• XOR vale 1 se gli ingressi sono diversi (con più ingressi: se il numero di 1 è dispari, cioè calcola la parità; vedi Codifiche binarie e informazione non numericaBit, byte e multipli (potenze di 2 e di 10); codici BCD e Gray; caratteri ASCII, Unicode e UTF-8; ordine dei byte (little e big endian); bit di parità e codice di Hamming per rilevare e correggere errori.Codifiche binarie e informazione non numerica →). $A \oplus B = A\overline{B} + \overline{A}B$.
• Una porta logica è il circuito che realizza un operatore; il ritardo di propagazione di una porta è dell'ordine dei picosecondi.

Proprietà

Proprietà (algebra di Boole e De Morgan)

Proprietà	Forma AND	Forma OR
identità	$A \cdot 1 = A$	$A + 0 = A$
elemento nullo	$A \cdot 0 = 0$	$A + 1 = 1$
idempotenza	$AA = A$	$A + A = A$
complemento	$A\overline{A} = 0$	$A + \overline{A} = 1$
commutativa	$AB = BA$	$A + B = B + A$
associativa	$(AB)C = A(BC)$	$(A+B)+C = A+(B+C)$
distributiva	$A(B + C) = AB + AC$	$A + BC = (A+B)(A+C)$
assorbimento	$A(A + B) = A$	$A + AB = A$
De Morgan	$\overline{AB} = \overline{A} + \overline{B}$	$\overline{A+B} = \overline{A}\,\overline{B}$

Esempio. $\overline{A+B}=\overline A\,\overline B$: per $A=0$ e $B=1$ entrambi i membri valgono $0$.

Doppia negazione: $\overline{\overline{A}} = A$. Ogni proprietà ha la sua duale, ottenuta scambiando AND con OR e 0 con 1. La seconda distributiva ($A + BC = (A+B)(A+C)$) non vale nell'aritmetica ordinaria.

Utile anche: $A + \overline{A}B = A + B$.

Completezza

Proprietà (completezza della NAND). {AND, OR, NOT} basta per scrivere qualsiasi funzione (vedi le forme canoniche in Reti combinatorie e mappe di KarnaughRete combinatoria (uscite funzione dei soli ingressi attuali); mintermini e maxtermini, forme canoniche SOP e POS; mappe di Karnaugh a 3 e 4 variabili con esempi svolti; condizioni di indifferenza; costo e ritardo di una rete a due livelli.Reti combinatorie e mappe di Karnaugh →). Anche la sola NAND basta, e così la sola NOR:

• NOT: $\overline{A} = \overline{AA}$ (NAND con gli ingressi uniti);
• AND: $AB = \overline{\overline{AB}}$ (NAND seguita da un NOT fatto con NAND);
• OR: $A + B = \overline{\overline{A}\,\overline{B}}$ (De Morgan: NAND degli ingressi negati).

Esempio. $A+B=\overline{\overline A\,\overline B}$: per $A=1$ e $B=0$ si ha $\overline{0\cdot1}=1$.

Per questo i circuiti integrati si costruiscono spesso con un solo tipo di porta.

Esempio di semplificazione

$$F = \overline{A}BC + A\overline{B}C + ABC + AB\overline{C}$$

• Raccolgo $C$ dai termini 1 e 3: $\overline{A}BC + ABC = BC(\overline{A} + A) = BC$.
• Duplico $ABC$ (idempotenza) e lo uso anche con il termine 2 e con il 4: $A\overline{B}C + ABC = AC$, $ABC + AB\overline{C} = AB$.

$$F = BC + AC + AB$$

È la funzione maggioranza (vale 1 se almeno due ingressi su tre sono 1): è il riporto in uscita di un sommatore completo (vedi Circuiti combinatori notevoliMultiplexer, decodificatore e codificatore; semisommatore e sommatore completo; sommatore a propagazione del riporto e suo ritardo, idea dell'anticipo del riporto; sommatore-sottrattore in complemento a 2 con rilevazione dell'overflow; comparatore.Circuiti combinatori notevoli →).

Errori tipici

• Applicare De Morgan senza cambiare l'operatore: $\overline{AB} \neq \overline{A}\,\overline{B}$.
• Dimenticare che $A + 1 = 1$ (non $A + 1 = A$).