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

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à

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

{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).

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$).