Le regole
del gioco
Due espressioni diverse possono dire la stessa cosa? E come lo dimostri senza provare tutte le combinazioni? In questa lezione le leggi dell'algebra di Boole (ciascuna con la sua intuizione «da interruttore»), De Morgan e la dualità, la semplificazione passo per passo, e gli operatori derivati. Vedremo anche come costruire qualsiasi funzione booleana usando soltanto porte NAND.
Due strade per l'equivalenza
Nella lezione 1 l'equivalenza aveva una sola prova: la stessa tabella di verità. Funziona sempre, ma con variabili costa righe, e soprattutto non spiega perché due espressioni coincidono.
La seconda strada è algebrica: si trasforma un'espressione nell'altra applicando leggi, un passo alla volta, come si fa coi numeri. Ogni passo cita la sua legge, e la catena di passi è la dimostrazione. Le due strade si controllano a vicenda: la tabella dice se è vero, l'algebra dice perché. Con molte variabili, le trasformazioni algebriche evitano di enumerare tutte le righe della tabella.
Le leggi, con l'intuizione da interruttore
Poche regole permettono di manipolare e semplificare le espressioni, come si fa in algebra con i numeri. Eccole, tutte dimostrabili con una tabella di verità.
| Legge | Con AND (·) | Con OR (+) |
|---|---|---|
| Identità | ||
| Elemento nullo | ||
| Idempotenza | ||
| Complemento | ||
| Commutativa | ||
| Associativa | ||
| Distributiva | ||
| Assorbimento | ||
| Consenso | ||
Le più usate hanno un'intuizione «da interruttore» che aiuta a interpretare la formula:
- Elemento nullo: un interruttore in serie sempre aperto () spegne tutto; uno in parallelo sempre chiuso () accende tutto, qualunque cosa faccia .
- Complemento: e in serie non conducono mai (uno dei due è sempre aperto); in parallelo conducono sempre.
- Assorbimento: se il ramo da solo accende la luce, aggiungergli in parallelo il ramo non cambia niente, perché quel ramo conduce solo quando già conduceva. .
- Consenso: il termine è ridondante perché nei casi in cui scatta (), uno tra e è già scattato, qualunque sia .
: negare due volte riporta al valore di partenza.
La prima distributiva, , è quella dell'aritmetica. La seconda, , a chi viene dai numeri sembra un errore: con l'aritmetica non funziona (). In Boole vale in entrambi i versi, e la dimostrazione per tabella è nel laboratorio del prossimo capitolo: scegli «Distributiva (OR)» e guardala reggere su tutte le righe.
De Morgan e la dualità
Due identità permettono di applicare la negazione a espressioni con AND e OR. Le useremo per semplificare le espressioni e progettare i circuiti.
, . A parole: la negazione di un AND è l'OR delle negazioni, e viceversa. Negando, l'operatore si «ribalta» (AND↔OR) e ogni pezzo si nega.
La lettura intuitiva: «non è vero che piove e fa freddo» significa «non piove oppure non fa freddo». Basta che una delle due manchi. E «non è vero che piove o fa freddo» significa «non piove e non fa freddo»: devono mancare entrambe. La regola si estende a quante variabili vuoi: .
Guarda la tabella delle leggi: ogni identità resta vera scambiando AND ↔ OR e 0 ↔ 1. È il principio di dualità: da un'identità si ricava quella della colonna accanto applicando questi scambi.
L'errore più comune di tutta la materia: negare i pezzi dimenticando di ribaltare l'operatore (o viceversa). non è : è . Le due mosse (ribalta e nega) si fanno insieme, sempre. Il laboratorio qui sotto le mostra riga per riga.
Scegli una legge: le due espressioni (sinistra e destra) vengono confrontate riga per riga. Colonne identiche ⇒ la legge è vera.
Le due forme di De Morgan, verificate riga per riga: la colonna di sinistra (la negazione) e quella di destra coincidono sempre.
Modifica gli ingressi e confronta le uscite: XOR (1 se gli ingressi sono diversi), XNOR (il suo contrario), NAND (NOT-AND) e NOR (NOT-OR).
Semplificare, passo per passo
La tecnica: si guarda l'espressione cercando le sagome delle leggi (un da assorbire, un che vale 1, un fattore da raccogliere) e si applica una legge alla volta, scrivendo quale. Seguiamo tre esempi con passaggi progressivamente più articolati.
Raccogli (distributiva): . Complemento: . Identità: .
Risultato: . L'uscita coincide con l'ingresso A: le operazioni intermedie non sono necessarie.
È la sagoma della distributiva OR letta al contrario: . Quindi . Complemento: . Identità: .
Risultato: . La distributiva permette di applicare poi la legge del complemento.
De Morgan sul primo fattore: (ribalta l'AND in OR, nega i pezzi già negati: doppia negazione). Resta . Idempotenza.
Risultato: . Sotto il travestimento c'era due volte la stessa cosa.
Semplifica, citando la legge a ogni passo: (1) · (2) · (3) . Poi verifica ogni risultato nel laboratorio del capitolo 3 o in Python (capitolo 6).
(1) Distributiva OR: ; complemento e identità → . È un'identità utile da ricordare a sé: « oppure, se non c'è , » è semplicemente « o ».
(2) Assorbimento con : → .
(3) De Morgan: ; doppia negazione → .
XOR, NAND, NOR e l'universalità
Dai tre operatori fondamentali se ne derivano altri, così frequenti da avere nome e porta propri. Li hai già visti accesi nel laboratorio 3 del capitolo 3.
: vale 1 se gli ingressi sono diversi. È il cancello a due telecomandi della lezione 1, diventato un operatore. XNOR è il suo contrario: 1 se uguali.
Tre proprietà di XOR che torneranno (nei sommatori, e nella lezione 5 con i cifrari): è associativo e commutativo; ; . Messe insieme, applicare due volte lo stesso XOR riporta al punto di partenza: .
(NOT-AND: 0 solo se entrambi 1) e (NOT-OR: 1 solo se entrambi 0).
L'universalità della NAND. Con sole porte NAND si costruiscono NOT, AND e OR, quindi qualunque funzione booleana. Si dice che NAND è funzionalmente completa, o «universale» (e NOR lo è altrettanto):
| Da costruire | Solo con NAND | Perché funziona |
|---|---|---|
| NOT A | (idempotenza) | |
| A AND B | NAND seguita dal suo NOT: la doppia negazione restituisce l'AND | |
| A OR B | De Morgan: |
La proprietà permette di realizzare una funzione usando un solo tipo di porta. Le leggi di De Morgan servono a convertire le espressioni nella forma adatta a questa realizzazione. Lo riprenderemo nella lezione sui circuiti.
La verifica in Python
Ogni semplificazione fatta a mano si controlla in un'esecuzione, con la funzione equivalenti() della lezione 1:
E De Morgan, generalizzato a tre variabili, il caso che a mano richiederebbe otto righe di tabella:
Abbiamo le regole e sappiamo dimostrare. Nella prossima lezione il problema si ribalta: data la tabella del comportamento che vuoi, come ricavi l'espressione più semplice che lo produce? Risposta: forme canoniche e mappe di Karnaugh.
Verifica finale
Otto domande sulla lezione. Rispondi a tutte, poi premi «Correggi». Puoi sempre riprovare.
Tutto su una pagina
Leggi base
- Identità: A·1=A, A+0=A
- Nullo: A·0=0, A+1=1
- Complemento: A·Ā=0, A+Ā=1
- Assorbimento: A+AB=A · doppia negazione riporta ad A
De Morgan & dualità
- NOT(A·B) = Ā+B̄
- NOT(A+B) = Ā·B̄
- Ribalta l'operatore E nega i pezzi, insieme
- Dualità: AND↔OR, 0↔1
Derivati
- XOR: 1 se diversi · A⊕A=0 · (A⊕K)⊕K=A
- NAND: 0 solo se entrambi 1 · NOR: 1 solo se entrambi 0
- NAND (e NOR) è universale
Semplificare
- Cerca le sagome: X+XY, X+X̄, fattori comuni
- Una legge alla volta, citandola
- A+ĀB = A+B: da ricordare
- Verifica: tabella o equivalenti()
Algebra Booleana · Lezione 2 · Le regole del gioco · buono studio!
Il tuo riscontro
Com’è andata questa lezione?
Dimmi cosa è chiaro e dove la spiegazione può migliorare.