Leggi dell’Algebra di Boole e Semplificazione Algebrica

L’algebra di Boole è il linguaggio formale con cui si descrivono, analizzano e progettano sia i circuiti digitali sia le condizioni logiche nei programmi. A differenza dell’algebra ordinaria, in cui le variabili assumono valori numerici continui, nell’algebra booleana ogni variabile può assumere solo due valori: 0 (falso) e 1 (vero).

Comprendere le leggi di quest’algebra non è un esercizio teorico fine a se stesso. Nel contesto della programmazione, ogni semplificazione algebrica corrisponde a una condizione scritta in modo più chiaro, più corto e meno soggetta a errori. Le leggi di De Morgan in particolare sono uno strumento che ogni programmatore usa — spesso senza saperlo — ogni volta che deve riscrivere una condizione negata o ristrutturare un blocco condizionale complesso.

Questa lezione presenta le famiglie di leggi in modo sistematico, corredando ciascuna di dimostrazione tramite tabella di verità, formulazione algebrica ed esempi applicati sia alla logica formale sia al codice PHP e JavaScript.

Le Proprietà Fondamentali: Commutativa, Associativa e Distributiva

Proprietà commutativa

L’operatore AND e l’operatore OR sono entrambi commutativi: l’ordine degli operandi non influenza il risultato.

Formulazione algebrica:

A AND B = B AND A
A OR B  = B OR A

A	B	A AND B	B AND A	A OR B	B OR A
0	0	0	0	0	0
0	1	0	0	1	1
1	0	0	0	1	1
1	1	1	1	1	1

Nel codice: la commutativa significa che $A && $B e $B && $A producono sempre lo stesso risultato. Tuttavia, in presenza di corto circuito, l’ordine degli operandi influenza le prestazioni: conviene mettere per prima la condizione più probabile che determini il risultato, in modo da evitare la valutazione della seconda.

<?php
// Logicamente equivalenti, ma la seconda è più efficiente
// se $connessione_attiva è spesso false:
// versione meno efficiente
$ok = eseguiQueryCostosa() && $connessione_attiva;

// versione più efficiente: se la connessione è inattiva,
// la query costosa non viene mai eseguita
$ok = $connessione_attiva && eseguiQueryCostosa();
?>

Proprietà associativa

Quando si concatenano più operazioni dello stesso tipo, le parentesi non influenzano il risultato.

Formulazione algebrica:

(A AND B) AND C = A AND (B AND C)
(A OR B)  OR C  = A OR  (B OR C)

A	B	C	(A AND B) AND C	A AND (B AND C)
0	0	0	0	0
0	0	1	0	0
0	1	0	0	0
0	1	1	0	0
1	0	0	0	0
1	0	1	0	0
1	1	0	0	0
1	1	1	1	1

Nel codice: la proprietà associativa garantisce che possiamo raggruppare le condizioni liberamente senza alterare la logica. Questo è utile quando si vuole organizzare una condizione complessa in gruppi semanticamente significativi.

<?php
// Le due forme sono equivalenti
$accesso1 = ($utente_attivo && $email_verificata) && $non_bannato;
$accesso2 = $utente_attivo && ($email_verificata && $non_bannato);
// $accesso1 === $accesso2 sempre
?>

Proprietà distributiva

Qui emerge la prima differenza rispetto all’algebra ordinaria: in aritmetica solo la moltiplicazione distribuisce sulla somma. In algebra booleana vale anche la distributività di OR rispetto ad AND.

Formulazione algebrica:

A AND (B OR C)  = (A AND B) OR  (A AND C)   ← distributiva standard
A OR  (B AND C) = (A OR B)  AND (A OR C)    ← distributiva duale

A	B	C	B AND C	A OR (B AND C)	A OR B	A OR C	(A OR B) AND (A OR C)
0	0	0	0	0	0	0	0
0	0	1	0	0	0	1	0
0	1	0	0	0	1	0	0
0	1	1	1	1	1	1	1
1	0	0	0	1	1	1	1
1	0	1	0	1	1	1	1
1	1	0	0	1	1	1	1
1	1	1	1	1	1	1	1

Leggi di Identità e di Annullamento

Queste quattro leggi sono strumenti di semplificazione immediata: quando un’espressione contiene una costante (0 o 1) in AND o OR con una variabile, il risultato è prevedibile senza dover costruire alcuna tabella.

Formulazione algebrica:

A AND 1 = A      ← identità dell'AND
A AND 0 = 0      ← annullamento dell'AND
A OR  0 = A      ← identità dell'OR
A OR  1 = 1      ← annullamento dell'OR

A	A AND 1	A AND 0	A OR 0	A OR 1
0	0	0	0	1
1	1	0	1	1

Nel codice: queste leggi aiutano a identificare condizioni ridondanti o sempre vere/false nel codice.

<?php
// A AND 0 = 0: questa condizione è sempre falsa, il blocco non viene mai eseguito
if ($utente_attivo && false) {
    // codice irraggiungibile
}

// A OR 1 = 1: questa condizione è sempre vera, la condizione è inutile
if ($utente_attivo || true) {
    // viene sempre eseguito
}

// A AND 1 = A: la seconda condizione è ridondante
if ($utente_attivo && true) {
    // equivale semplicemente a: if ($utente_attivo)
}
?>

Un buon editor di codice o un analizzatore statico (come PHPStan o ESLint) segnala questi pattern come potenziali errori logici, perché spesso indicano una condizione dimenticata o un copia-incolla errato.

Leggi di Complementazione

Queste leggi formalizzano due principi della logica classica: il principio di contraddizione e il principio del terzo escluso.

Formulazione algebrica:

A AND NOT A = 0    ← legge di contraddizione
A OR  NOT A = 1    ← legge del terzo escluso

A	NOT A	A AND NOT A	A OR NOT A
0	1	0	1
1	0	0	1

Nel codice: queste leggi aiutano a riconoscere condizioni contraddittorie o tautologiche.

<?php
// A AND NOT A = 0: impossibile che $attivo sia true e false contemporaneamente
if ($attivo && !$attivo) {
    // blocco irraggiungibile: segnale di un errore logico nel codice
}

// A OR NOT A = 1: sempre vero, la condizione non serve a nulla
if ($attivo || !$attivo) {
    // viene sempre eseguito: la condizione è superflua
}
?>

// Stesso concetto in JavaScript
let modalitaNotturna = true;

// Questa condizione è sempre false: bug logico evidente
if (modalitaNotturna && !modalitaNotturna) {
    console.log("Impossibile arrivare qui");
}

Leggi di Idempotenza

Applicare un’operazione due volte sullo stesso operando produce lo stesso risultato di applicarla una volta sola.

Formulazione algebrica:

A AND A = A
A OR  A = A

A	A AND A	A OR A
0	0	0
1	1	1

Nel codice: la presenza di una stessa condizione ripetuta in un’espressione è quasi sempre il sintomo di un copia-incolla errato o di una ristrutturazione incompleta del codice.

<?php
// A AND A = A: la condizione è ripetuta inutilmente
if ($utente_attivo && $utente_attivo) {
    // equivale a: if ($utente_attivo)
}

// Caso più sottile con variabili diverse ma stesso significato:
$is_admin = $ruolo === "admin";
$ha_privilegi = $ruolo === "admin";  // identica a $is_admin

// $is_admin && $ha_privilegi equivale a $is_admin
if ($is_admin && $ha_privilegi) {
    // ridondante
}
?>

Legge di Doppia Negazione

Formulazione algebrica:

NOT (NOT A) = A

A	NOT A	NOT (NOT A)
0	1	0
1	0	1

Negare due volte un segnale riporta al segnale originale. È come dire «non è vero che non piove»: la doppia negazione restituisce l’affermazione originale «piove».

Nel codice: la doppia negazione appare frequentemente quando si converte un valore qualsiasi in booleano esplicito, oppure quando si ristruttura un’espressione senza semplificarla.

<?php
$valore = "ciao";

// Doppia negazione usata per forzare la conversione a booleano
$booleano = !!$valore;   // equivale a (bool) $valore → true

// Doppia negazione da semplificare:
$attivo = true;
$risultato = !!$attivo;  // inutile: equivale semplicemente a $attivo
?>

let valore = "ciao";

// In JavaScript !! è l'idioma più comune per convertire in booleano
let booleano = !!valore;   // true

// Doppia negazione che si annulla:
let attivo = true;
let risultato = !!attivo;  // true: equivale ad attivo

Nota

In JavaScript l’operatore !! (doppia negazione) è un idioma comunemente usato dai programmatori per convertire qualsiasi valore in un booleano esplicito. Non è un errore quando usato intenzionalmente per la conversione: è equivalente a Boolean(valore) ma più conciso. Diventa invece ridondante quando applicato a una variabile già booleana.

Leggi di Assorbimento

Le leggi di assorbimento sono tra i più potenti strumenti di riduzione algebrica, perché permettono di eliminare un intero sottogruppo di variabili in un solo passaggio.

Formulazione algebrica:

A OR  (A AND B) = A    ← assorbimento OR
A AND (A OR  B) = A    ← assorbimento AND

A	B	A AND B	A OR (A AND B)
0	0	0	0
0	1	0	0
1	0	0	1
1	1	1	1

A	B	A OR B	A AND (A OR B)
0	0	0	0
0	1	1	0
1	0	1	1
1	1	1	1

Nel codice: la legge di assorbimento aiuta a identificare condizioni composte che sono più semplici di quanto appaiano.

<?php
$utente_admin = true;
$utente_admin_con_log = $utente_admin && true; // qualsiasi condizione aggiuntiva

// A OR (A AND B) = A
// Se l'utente è admin, non serve anche verificare admin_con_log:
// la seconda condizione è assorbita dalla prima
$accesso = $utente_admin || ($utente_admin && $utente_admin_con_log);
// Equivale semplicemente a:
$accesso = $utente_admin;
?>

let isPremium = true;
let isPremiumWithDiscount = isPremium && hasDiscount;

// A OR (A AND B) = A
// Se l'utente è premium, non serve controllare anche isPremiumWithDiscount
let mostraContenuto = isPremium || (isPremium && isPremiumWithDiscount);
// Equivale a:
let mostraContenuto2 = isPremium;

Leggi di De Morgan

Le leggi di De Morgan sono le più rilevanti per la programmazione quotidiana. Stabiliscono come la negazione si distribuisce rispetto ad AND e OR, e sono lo strumento principale per riscrivere condizioni negate in forma più leggibile o più gestibile.

Formulazione algebrica:

NOT (A AND B) = NOT A OR  NOT B    ← prima legge di De Morgan
NOT (A OR  B) = NOT A AND NOT B    ← seconda legge di De Morgan

La regola mnemonica è: si nega il risultato globale, si invertono gli operatori interni (AND diventa OR e viceversa), si negano i singoli operandi.

Dimostrazione della prima legge

A	B	A AND B	NOT (A AND B)	NOT A	NOT B	NOT A OR NOT B
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

Dimostrazione della seconda legge

A	B	A OR B	NOT (A OR B)	NOT A	NOT B	NOT A AND NOT B
0	0	0	1	1	1	1
0	1	1	0	1	0	0
1	0	1	0	0	1	0
1	1	1	0	0	0	0

De Morgan nel codice: applicazione pratica

Le leggi di De Morgan sono indispensabili nella programmazione ogni volta che si deve negare una condizione composta. Vediamo i casi più comuni.

Caso 1: negare un AND. «L’accesso non è consentito se password e badge sono entrambi corretti» diventa «l’accesso è negato se la password è sbagliata oppure il badge è sbagliato».

<?php
$password_ok = true;
$badge_ok = false;

// Forma originale con NOT su AND
$accesso_negato = !($password_ok && $badge_ok);
var_dump($accesso_negato);  // bool(true)

// Forma equivalente per De Morgan: NOT(A AND B) = NOT A OR NOT B
$accesso_negato_dm = !$password_ok || !$badge_ok;
var_dump($accesso_negato_dm);  // bool(true) — stesso risultato
?>

Caso 2: negare un OR. «Non è né il giorno libero né una festività» corrisponde a «non è il giorno libero AND non è una festività».

<?php
$giorno_libero = false;
$festività = false;

// Forma originale con NOT su OR
$deve_lavorare = !($giorno_libero || $festività);
var_dump($deve_lavorare);  // bool(true)

// Forma equivalente per De Morgan: NOT(A OR B) = NOT A AND NOT B
$deve_lavorare_dm = !$giorno_libero && !$festività;
var_dump($deve_lavorare_dm);  // bool(true) — stesso risultato
?>

Caso 3: semplificare un if/else usando De Morgan. Un pattern molto comune è trasformare un blocco con condizione negata in uno con condizione positiva, rendendo il codice più leggibile.

<?php
$utente_loggato = true;
$sessione_valida = true;

// Versione con condizione negata (meno leggibile)
if (!($utente_loggato && $sessione_valida)) {
    header("Location: /login");
    exit;
}
echo "Benvenuto!";

// Versione con De Morgan applicato (più leggibile)
if (!$utente_loggato || !$sessione_valida) {
    header("Location: /login");
    exit;
}
echo "Benvenuto!";
?>

let utenteLoggato = true;
let sessioneValida = false;

// Con NOT su OR: meno immediato
if (!(utenteLoggato || sessioneValida)) {
    window.location.href = "/login";
}

// Con De Morgan: NOT(A OR B) = NOT A AND NOT B
if (!utenteLoggato && !sessioneValida) {
    window.location.href = "/login";
}

Caso 4: De Morgan con più di due variabili. Le leggi si estendono a qualsiasi numero di operandi.

<?php
// NOT(A AND B AND C) = NOT A OR NOT B OR NOT C
$form_valido = !($nome_vuoto || $email_vuota || $messaggio_vuoto);
// Equivale a:
$form_valido = !$nome_vuoto && !$email_vuota && !$messaggio_vuoto;

// Le due forme sono identiche: scegliere quella più leggibile nel contesto
?>

Quando usare quale forma

Non esiste una forma sempre migliore dell’altra: dipende da cosa si vuole rendere evidente al lettore del codice. Se si vuole enfatizzare che la condizione è un’eccezione a una regola positiva, il NOT esterno è più espressivo. Se si vuole elencare esplicitamente le singole condizioni di fallimento, la forma con De Morgan distribuito è più chiara. La capacità di passare da una all’altra è la competenza che questa lezione vuole costruire.

Riepilogo delle Leggi in forma di Tavola di riferimento

Famiglia	Legge AND	Legge OR
Commutativa	A·B = B·A	A+B = B+A
Associativa	(A·B)·C = A·(B·C)	(A+B)+C = A+(B+C)
Distributiva	A·(B+C) = A·B+A·C	A+(B·C) = (A+B)·(A+C)
Identità	A·1 = A	A+0 = A
Annullamento	A·0 = 0	A+1 = 1
Idempotenza	A·A = A	A+A = A
Complementazione	A·NOT A = 0	A+NOT A = 1
Assorbimento	A·(A+B) = A	A+(A·B) = A
Doppia negazione	NOT(NOT A) = A	—
De Morgan	NOT(A·B) = NOT A+NOT B	NOT(A+B) = NOT A·NOT B

Semplificazione Algebrica: Applicazione Sequenziale delle Leggi

Semplificare un’espressione booleana significa riscriverla in una forma equivalente che contenga meno variabili, meno operatori o meno livelli logici. Nel codice questo corrisponde a condizioni più corte, più leggibili e meno soggette a errori.

La strategia generale segue questi criteri orientativi:

1. cercare termini complementari (A AND NOT A) da azzerare o (A OR NOT A) da portare a 1;
2. applicare identità e annullamento per eliminare costanti;
3. applicare idempotenza per eliminare duplicati;
4. applicare assorbimento per eliminare sottogruppi ridondanti;
5. applicare De Morgan per uniformare la struttura o eliminare NOT distribuiti.

Esempio 1 — Semplificazione con Assorbimento e Complementazione

Espressione di partenza:

F = A OR (A AND B) OR (A AND NOT A)

Passo 1: applicare la legge di complementazione al terzo termine: A AND NOT A = 0

F = A OR (A AND B) OR 0

Passo 2: applicare l’identità dell’OR con 0:

F = A OR (A AND B)

Passo 3: applicare la legge di assorbimento A OR (A AND B) = A:

F = A

In codice PHP — prima e dopo la semplificazione:

<?php
$A = true;
$B = false;

// Espressione originale (5 operazioni logiche)
$F_originale = $A || ($A && $B) || ($A && !$A);
var_dump($F_originale);  // bool(true)

// Espressione semplificata (0 operazioni logiche)
$F_semplificata = $A;
var_dump($F_semplificata);  // bool(true) — stesso risultato
?>

Esempio 2 — Semplificazione con De Morgan e Assorbimento

Espressione di partenza:

F = NOT (NOT A AND NOT B) OR (A AND B)

Passo 1: applicare la seconda legge di De Morgan al primo termine:

NOT (NOT A AND NOT B) = NOT(NOT A) OR NOT(NOT B) = A OR B
F = (A OR B) OR (A AND B)

Passo 2: applicare la proprietà associativa:

F = A OR B OR (A AND B)

Passo 3: applicare assorbimento B OR (A AND B) = B:

F = A OR B

In codice PHP — prima e dopo:

<?php
$A = true;
$B = false;

// Espressione originale (6 operazioni)
$F_originale = !(!$A && !$B) || ($A && $B);
var_dump($F_originale);  // bool(true)

// Espressione semplificata (1 operazione)
$F_semplificata = $A || $B;
var_dump($F_semplificata);  // bool(true) — stesso risultato
?>

Esempio 3 — Semplificazione applicata al codice reale

Questo esempio mostra come riconoscere un’opportunità di semplificazione direttamente nel codice, senza partire dall’espressione algebrica.

<?php
// Condizione di accesso originale, scritta senza semplificazione:
// L'utente può accedere se:
// - è admin E ha il badge, OPPURE
// - è admin E ha la sessione attiva, OPPURE
// - è admin E ha entrambi
$accesso = ($is_admin && $ha_badge)
        || ($is_admin && $sessione_attiva)
        || ($is_admin && $ha_badge && $sessione_attiva);

// Raccogliendo $is_admin con la distributiva:
// $is_admin AND ($ha_badge OR $sessione_attiva OR ($ha_badge AND $sessione_attiva))
// Per assorbimento: $ha_badge OR ($ha_badge AND $sessione_attiva) = $ha_badge
// Quindi: $is_admin AND ($ha_badge OR $sessione_attiva)

// Condizione semplificata:
$accesso = $is_admin && ($ha_badge || $sessione_attiva);
?>

Il risultato è logicamente identico all’originale ma molto più leggibile: chiunque legga il codice capisce immediatamente che l’accesso richiede di essere admin e di avere almeno una delle due credenziali.

Esercizi di Verifica

Esercizio 1 — Identifica la Legge

Per ciascuna delle seguenti equivalenze, indica quale legge dell’algebra di Boole viene applicata.

1. A AND B AND C = A AND C AND B
2. NOT (NOT A) = A
3. A OR (A AND B) = A
4. A AND 0 = 0
5. NOT (A OR B) = NOT A AND NOT B
6. A OR A = A
7. A AND NOT A = 0
8. NOT (A AND B) = NOT A OR NOT B

Esercizio 2 — De Morgan nel Codice

Per ciascuna delle seguenti espressioni PHP, applica la legge di De Morgan corrispondente e riscrivi l’espressione in forma equivalente. Poi verifica che le due forme producano lo stesso risultato con i valori indicati.

1. !($utente_attivo && $email_verificata), con entrambe le variabili true.
2. !($carrello_vuoto || $pagamento_fallito), con $carrello_vuoto = false e $pagamento_fallito = false.
3. !($A || $B || $C), con A = false, B = true, C = false.
4. !($form_inviato && $dati_validi && $utente_loggato), con tutte e tre le variabili true.

Esercizio 3 — Semplificazione algebrica

Semplifica ciascuna delle seguenti espressioni applicando le leggi dell’algebra di Boole. Mostra tutti i passaggi indicando per ciascuno quale legge viene applicata. Poi scrivi il codice PHP prima e dopo la semplificazione e verifica che il risultato sia identico.

1. F = A OR (NOT A AND B)
2. F = (A AND B) OR (A AND NOT B)
3. F = NOT (NOT A OR NOT B)

Esercizio 4 — Semplifica il Codice

Ciascuno dei seguenti frammenti di codice PHP contiene una condizione che può essere semplificata applicando una o più leggi dell’algebra di Boole. Per ciascuno: identifica la legge applicabile, scrivi la versione semplificata e verifica che le due versioni producano lo stesso output.

<?php
// Frammento 1
$risultato = $A || ($A && $B && $C);

// Frammento 2
$risultato = ($utente_admin && $sessione_attiva) || ($sessione_attiva && $utente_admin);

// Frammento 3
$risultato = !(!$connessione_ok);

// Frammento 4
$risultato = ($logged_in && $verified) || ($logged_in && !$verified) || (!$logged_in && $verified);

// Frammento 5
$risultato = !(!$A && !$B);
?>

Esercizio 5 — Rispondi con parole tue

Rispondi alle seguenti domande scrivendo almeno tre righe per ciascuna risposta.

1. Spiega con un esempio concreto perché le leggi di De Morgan sono utili nella programmazione quotidiana. In quale situazione ti sembra più conveniente usare !($A && $B) rispetto a !$A || !$B?
2. La legge di assorbimento dice che A OR (A AND B) = A. Inventa un esempio di codice PHP in cui questa legge potrebbe aiutarti a semplificare una condizione complessa in un’applicazione web reale.
3. Perché la proprietà commutativa, pur essendo logicamente irrilevante sul risultato, può avere importanza pratica quando si scrive codice che usa la valutazione a corto circuito?