Due formule logiche sono equivalenti quando assumono lo stesso valore di verità per ogni combinazione delle variabili. Conoscere un piccolo repertorio di equivalenze permette di trasformare una condizione complicata in una più semplice, con la certezza di non averne cambiato il comportamento. Tra tutte, le leggi di De Morgan sono quelle che si usano più spesso, soprattutto quando bisogna negare una condizione.
Le leggi di De Morgan
Le due leggi dicono come si nega una congiunzione e una disgiunzione:
- ¬(p ∧ q) ≡ ¬p ∨ ¬q
- ¬(p ∨ q) ≡ ¬p ∧ ¬q
In parole: la negazione «entra» nella parentesi, nega ciascun termine e scambia ∧ con ∨. «Non è vero che il file è leggibile e scrivibile» equivale a «il file non è leggibile oppure non è scrivibile». «Non è vero che piove o nevica» equivale a «non piove e non nevica».
Le leggi si estendono a qualunque numero di termini: ¬(p ∧ q ∧ r) ≡ ¬p ∨ ¬q ∨ ¬r. Valgono anche per gli insiemi, dove il complemento dell'intersezione è l'unione dei complementi, e per i circuiti, dove una porta NAND equivale a un OR con gli ingressi negati.
Il repertorio delle equivalenze
| Nome | Equivalenza |
|---|---|
| Doppia negazione | ¬¬p ≡ p |
| Commutativa | p ∧ q ≡ q ∧ p; p ∨ q ≡ q ∨ p |
| Associativa | (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) |
| Distributiva | p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) |
| Distributiva duale | p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) |
| Idempotenza | p ∧ p ≡ p; p ∨ p ≡ p |
| Assorbimento | p ∨ (p ∧ q) ≡ p; p ∧ (p ∨ q) ≡ p |
| Elemento neutro | p ∧ V ≡ p; p ∨ F ≡ p |
| Dominanza | p ∨ V ≡ V; p ∧ F ≡ F |
| Complemento | p ∨ ¬p ≡ V; p ∧ ¬p ≡ F |
| Implicazione | p → q ≡ ¬p ∨ q |
Ognuna si può verificare con una tavola di verità. Notate la simmetria: ogni legge ha una versione «duale» che si ottiene scambiando ∧ con ∨ e V con F. È una proprietà generale dell'algebra di Boole.
Un esempio di semplificazione passo per passo
Supponiamo di trovare nel codice questa condizione:
not (utente_attivo and not abbonamento_scaduto) or not utente_attivo
Chiamiamo a = utente_attivo e s = abbonamento_scaduto. La formula è ¬(a ∧ ¬s) ∨ ¬a.
- De Morgan sulla prima parte: ¬a ∨ ¬¬s ∨ ¬a.
- Doppia negazione: ¬a ∨ s ∨ ¬a.
- Commutativa e idempotenza: ¬a ∨ s.
Il risultato, not utente_attivo or abbonamento_scaduto, è molto più leggibile. Si può anche rileggere come implicazione: a → s, cioè «se l'utente è attivo, allora l'abbonamento è scaduto». Questo tipo di rilettura aiuta spesso a capire se la condizione originale esprimeva davvero l'intenzione di chi l'ha scritta, oppure nascondeva un errore.
L'errore più comune: negare a metà
Quando si deve invertire una condizione, per esempio per trasformare un if in un'uscita anticipata, l'errore tipico è negare i termini senza scambiare l'operatore:
# condizione originale: procedere se età >= 18 e documento valido
if eta >= 18 and documento_valido:
procedi()
# uscita anticipata SBAGLIATA
if eta < 18 and not documento_valido:
return
# uscita anticipata CORRETTA (De Morgan)
if eta < 18 or not documento_valido:
return
La versione sbagliata lascia passare un minorenne con documento valido. Errori di questo tipo sono insidiosi perché il codice sembra ragionevole a una lettura veloce. Nel mio lavoro di revisione del codice, i controlli di accesso negati sono tra i punti che ricontrollo sempre con De Morgan alla mano.
Equivalenze e SQL
Le stesse leggi valgono nelle clausole WHERE, con una cautela: in SQL esiste il valore NULL, che introduce una logica a tre valori (vero, falso, sconosciuto). Le leggi di De Morgan continuano a valere anche lì, ma NOT (colonna = 5) non restituisce le righe in cui la colonna è NULL, perché il confronto con NULL dà «sconosciuto» e la sua negazione resta «sconosciuto». Chi semplifica una query deve quindi tenere conto dei valori mancanti, aggiungendo se necessario OR colonna IS NULL.
Perché semplificare
Una condizione più corta non è solo più elegante:
- è più facile da leggere e da revisionare;
- riduce il rischio di errori quando qualcuno la modifica in futuro;
- in hardware si traduce in meno porte logiche;
- nei test, rende più chiaro quali casi vanno coperti.
Attenzione però a non esagerare: a volte la forma più corta è meno espressiva di una leggermente più lunga che rispecchia la regola di business. L'obiettivo è la chiarezza, non il minimo numero di simboli.
In sintesi
- Le leggi di De Morgan negano congiunzioni e disgiunzioni scambiando ∧ e ∨ e negando ogni termine.
- Un repertorio di una decina di equivalenze basta per semplificare quasi ogni condizione reale.
- Ogni legge ha una duale, ottenuta scambiando ∧ con ∨ e vero con falso.
- L'errore tipico è negare i termini senza cambiare l'operatore, soprattutto nelle uscite anticipate.
- In SQL ricordate che NULL introduce un terzo valore di verità.
