Logica Booleana

Logica booleana: operatori, proprietà ed esempi

La logica dei calcolatori è intrinsecamente binaria: ogni informazione è codificata
mediante due soli valori, 0 e 1.
Il valore 0 rappresenta in genere il falso, lo spento o l’assenza di corrente,
mentre il valore 1 indica il vero, l’acceso o la presenza di corrente.

Questa rappresentazione ha radici storiche importanti: a metà Ottocento, il matematico inglese George Boole elaborò un sistema formale di calcolo logico, oggi chiamato algebra di Boole.
Le sue idee, nate in un contesto puramente matematico, si sono rivelate perfette per la progettazione dei calcolatori elettronici moderni.

—

Variabili booleane e valori di verità

Una variabile booleana è un simbolo che può assumere uno dei due valori:

  • 0 → falso, spento, interruttore aperto, condizione non verificata
  • 1 → vero, acceso, interruttore chiuso, condizione verificata

Questa corrispondenza tra logica e realtà fisica è fondamentale: in un circuito, un interruttore chiuso corrisponde al valore “vero” (1), mentre un interruttore aperto corrisponde al valore “falso” (0).

—

Operatori fondamentali

Gli operatori logici stabiliscono come combinare variabili booleane per ottenere nuovi risultati. Sono tre quelli fondamentali: AND, OR e NOT.

Congiunzione (AND)

L’operatore AND restituisce 1 solo se entrambe le variabili sono 1.

Esempio quotidiano: “Posso guardare la TV se ho la corrente AND il televisore è acceso”.
Entrambe le condizioni devono essere vere contemporaneamente.

Forma simbolica: x \land y

x y x \land y
0 0 0
0 1 0
1 0 0
1 1 1
Porta AND
Simbolo della porta AND e circuito equivalente: due interruttori in serie, che fanno passare la corrente solo se entrambi sono chiusi.

—

Disgiunzione (OR inclusivo)

L’operatore OR restituisce 1 se almeno una delle due variabili vale 1.
Il risultato è 0 solo se entrambe valgono 0.

Esempio quotidiano: “La luce si accende se premiamo l’interruttore in cucina OR quello in salotto”.
Basta che uno solo degli interruttori sia azionato.

Forma simbolica: x \lor y

x y x\lor y
0 0 0
0 1 1
1 0 1
1 1 1

 

Porta OR
Simbolo della porta OR e circuito equivalente: due interruttori in parallelo, basta che uno sia chiuso per permettere il passaggio della corrente.

—

Negazione (NOT)

L’operatore NOT inverte il valore della variabile: se la variabile vale 0,
l’uscita è 1; se vale 1, l’uscita diventa 0.

Esempio quotidiano: “La spia della riserva si accende se NON c’è carburante nel serbatoio”.

Forma simbolica: \lnot x \quad\text{oppure}\quad \overline{x}

x \lnot x
0 1
1 0

 

 

Porta NOT
Simbolo della porta NOT: inverte il segnale logico. L’ingresso 0 diventa uscita 1, e viceversa.

Operatori derivati

Oltre agli operatori fondamentali (AND, OR, NOT), in elettronica digitale si utilizzano
spesso degli operatori derivati, ottenuti combinando i primi tre.
Questi operatori sono molto importanti perché permettono di costruire circuiti logici
più complessi in modo compatto. Vediamoli uno per uno.

—

NAND (NOT-AND)

Il NAND è l’operatore logico che corrisponde alla negazione dell’AND.
Restituisce 0 solo quando entrambe le variabili sono 1; in tutti gli altri casi l’uscita è 1.

Forma simbolica: \overline{A \cdot B}

NOR (NOT-OR)

Il NOR è l’operatore logico che corrisponde alla negazione dell’OR.
Restituisce 1 solo quando entrambe le variabili sono 0; in tutti gli altri casi l’uscita è 0.

Forma simbolica: \overline{A + B}

x y \lnot(x \land y) \lnot(x \lor y)
0 0 1 1
0 1 1 0
1 0 1 0
1 1 0 0

 

Simboli della porta NAND e della porta NOR . In elettronica è fondamentale perché, insieme alla NOR, sono considerate funzioni universali: da sole possono realizzare qualsiasi altro operatore logico.

—

XOR (Exclusive OR)

L’operatore XOR (OR esclusivo) restituisce 1 solo se esattamente una delle due variabili è vera.
Se entrambe sono uguali (entrambe 0 o entrambe 1), l’uscita è 0.

Esempio: “Accendo la lampadina se premo esattamente uno dei due pulsanti”.
Se li premo entrambi o nessuno, la lampadina resta spenta.

Forma simbolica: A \oplus B

x y x\oplus y
0 0 0
0 1 1
1 0 1
1 1 0
Porta XOR
Simbolo della porta XOR. È usata ad esempio nei circuiti sommatore,
dove serve a distinguere tra “pari” e “dispari”.

—

XNOR (Exclusive NOR)

L’operatore XNOR (NOT-XOR) restituisce 1 quando le due variabili hanno lo stesso valore (entrambe 0 o entrambe 1).
È l’operatore della uguaglianza logica.

Esempio: “Due lampadine si accendono se entrambi gli interruttori sono nella stessa posizione
(aperti o chiusi)”.

Forma simbolica: \overline{A \oplus B}

 

x y \overline{x \oplus y}
0 0 1
0 1 0
1 0 0
1 1 1

 

Porta XNOR
Simbolo della porta XNOR. È spesso utilizzata come comparatore logico:
verifica se due ingressi sono uguali.

Proprietà e leggi dell’algebra di Boole

Come nell’algebra tradizionale dei numeri, anche l’algebra di Boole è governata da una serie di leggi.
Queste regole ci permettono di semplificare espressioni logiche, ridurre circuiti complessi e riconoscere equivalenze
tra diverse rappresentazioni.
Ogni legge ha un’interpretazione immediata sia a livello logico (vero/falso) sia a livello di circuito elettrico (interruttori in serie o in parallelo).

—

Legge di identità

Ogni variabile combinata con i valori “neutri” lascia la variabile invariata:

A + 0 = A \qquad A \cdot 1 = A

Interpretazione: aggiungere un falso a una disgiunzione non cambia nulla;
moltiplicare per vero in una congiunzione mantiene invariato il risultato.

—

Legge di annullamento

In alcuni casi il risultato è fissato indipendentemente dal valore della variabile:

A + 1 = 1 \qquad A \cdot 0 = 0

Interpretazione: in un OR, se almeno una condizione è sempre vera (1), l’uscita è sempre 1;
in un AND, se una condizione è sempre falsa (0), l’uscita è sempre 0.

In figura è illustrata la legge di identità per mezzo delle reti logiche, considerando una porta AND e una porta OR a due ingressi e visualizzandone il risultato in uscita.

—

Legge del complemento

Una variabile e la sua negazione si annullano o si saturano:

A + \overline{A} = 1 \qquad A \cdot \overline{A} = 0

Significato: “A o non-A” è sempre vero; “A e non-A” è sempre falso.
È la base del principio di non contraddizione.

—

Legge dell’involuzione

La negazione della negazione di una variabile restituisce la variabile stessa:

\overline{\overline{A}} = A

Interpretazione: il doppio NOT equivale a non fare nulla.
Se in un circuito applichiamo due inverter consecutivi, il segnale logico torna al valore originale.

\overline{\overline{(x+y)}} = x+y
La doppia negazione equivale a un filo diretto: l’uscita è identica all’ingresso.

—

Legge di idempotenza

Una variabile combinata con se stessa non cambia:

A + A = A \qquad A \cdot A = A

Se premiamo lo stesso interruttore due volte in parallelo o in serie, il risultato non cambia:
la ridondanza non ha effetto.

—

Legge di assorbimento

Una variabile “assorbe” combinazioni che contengono sé stessa:

A + (A \cdot B) = A \qquad A \cdot (A + B) = A

Questa legge permette di eliminare parti inutili di un’espressione logica.
Ad esempio, se “A è vera”, non serve aggiungere la condizione “A e B”.

—

Leggi commutativa e associativa

Come nei numeri, l’ordine degli elementi o dei raggruppamenti non cambia il risultato:

A + B = B + A \qquad A \cdot B = B \cdot A

(A + B) + C = A + (B + C) \qquad (A \cdot B) \cdot C = A \cdot (B \cdot C)

Interpretazione: in un circuito, l’ordine con cui colleghiamo interruttori in serie o in parallelo non cambia il comportamento complessivo.

Considerando il significato che tale proprietà riveste riguardo ai circuiti logici, utilizziamo una porta AND a tre ingressi.
Ad essa, tramite la proprietà associativa, possiamo sostituire due porte AND a due ingressi ed ottenere lo stesso valore in uscita: le due reti logiche sono equivalenti fra loro.

—

Legge distributiva

Nell’algebra booleana la distribuzione funziona in entrambi i sensi:

A \cdot (B + C) = A \cdot B + A \cdot C

A + (B \cdot C) = (A + B) \cdot (A + C)

Significato: collegare un interruttore in serie/parallelo può essere rappresentato con più forme equivalenti.
Questa legge è molto utile per la semplificazione delle reti logiche.

Possiamo notare che ogni uguaglianza possiede la sua duale. Consideriamo, per esempio, la proprietà associativa e la proprietà commutativa per la somma. Scambiando il simbolo di addizione con quello di moltiplicazione otteniamo le due uguaglianze per il prodotto. Possiamo quindi passare da una relazione, ad esempio per la funzione OR, a quella duale per la funzione AND ottenendo altre leggi e proprietà. Il concetto di dualità, definito dal cambiamento della funzione AND in OR, e viceversa, e dal cambiamento di “1” in “0” (e viceversa), è un concetto fondamentale dell’algebra di Boole, e può essere definito nel seguente modo: se una equazione è vera, allora anche l’equazione duale è vera. Questa regola si rivela di grande importanza nel progetto logico dei circuiti.

Tornando alla proprietà distributiva che è tipica dell’algebra ordinaria e applicando il principio di dualità valido nell’algebra di Boole, operiamo lo scambio dei simboli:

 

La seconda uguaglianza è valida solo nell’algebra di Boole; si potrebbe dimostrare la sua validità utilizzando le proprietà che stiamo descrivendo.

—

Principio di dualità

Ogni legge dell’algebra di Boole resta vera se scambiamo simultaneamente:

  • il simbolo + (OR) con · (AND)
  • il valore 0 con 1

Esempio: dalla legge di identità A + 0 = A otteniamo la legge duale A \cdot 1 = A .

I teoremi di De Morgan

Due delle trasformazioni più importanti dell’algebra di Boole sono note come
Teoremi di De Morgan.
Essi permettono di trasformare un’operazione logica con NOT esterno in un’altra
espressione equivalente con NOT interni.
Sono strumenti fondamentali per semplificare espressioni logiche e per
progettare circuiti digitali equivalenti.

1° teorema: \overline{A + B} = \overline{A} \cdot \overline{B}
2° teorema: \overline{A \cdot B} = \overline{A} + \overline{B}

Interpretazione:

  • “Il NON di una somma (OR) equivale al prodotto (AND) dei NON”.
  • “Il NON di un prodotto (AND) equivale alla somma (OR) dei NON”.

—

1° Teorema: \overline{A + B} = \overline{A} \cdot \overline{B}

Prendiamo due variabili A e B e calcoliamo i valori della funzione
\overline{A + B} .
Li confrontiamo con quelli della funzione \overline{A} \cdot \overline{B} .
Come mostra la tabella seguente, i risultati coincidono perfettamente riga per riga.

\begin{array}{|c|c|c|>{\columncolor{yellow}}c|c|c|>{\columncolor{yellow}}c|} \hline A & B & A+B & \overline{A+B} & \overline{A} & \overline{B} & \overline{A}\cdot\overline{B} \\ \hline\hline 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \hline \end{array}

Dimostrazione del 1° teorema di De Morgan tramite tabella di verità: le colonne gialle
mostrano che \overline{A+B} e \overline{A}\cdot\overline{B} coincidono.

—

2° Teorema: \overline{A \cdot B} = \overline{A} + \overline{B}

Ora prendiamo le stesse variabili e calcoliamo i valori di
\overline{A \cdot B} .
Li confrontiamo con quelli di \overline{A} + \overline{B} .
Anche in questo caso, i risultati delle due colonne coincidono perfettamente.

\begin{array}{|c|c|c|>{\columncolor{yellow}}c|c|c|>{\columncolor{yellow}}c|} \hline A & B & A \cdot B & \overline{A \cdot B} & \overline{A} & \overline{B} & \overline{A} + \overline{B} \\ \hline\hline 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \hline \end{array}

Dimostrazione del 2° teorema di De Morgan: anche qui le colonne gialle evidenziano
l’identità tra \overline{A\cdot B} e \overline{A}+\overline{B}.

—

Applicazioni pratiche

I teoremi di De Morgan sono utilissimi in diversi contesti:

  • Progettazione di circuiti: permettono di sostituire una porta AND seguita da NOT
    con una porta NAND, oppure una porta OR seguita da NOT con una porta NOR, riducendo i componenti.
  • Semplificazione logica: aiutano a trasformare formule complesse in forme più semplici e realizzabili.
  • Excel e linguaggi di programmazione: in Excel, l’espressione =NOT(OR(A;B))
    è equivalente a =AND(NOT(A);NOT(B)), proprio come afferma il 1° teorema.
  • \begin{array}{ll} Y = \overline{A \cdot B} & \quad \text{operazione logica:} \\ Y = \overline{A \cdot \overline{B} + \overline{A} \cdot B} & \quad \text{operazione logica:} \\ Y = \overline{A \cdot \overline{B}} + \overline{A} \cdot B & \quad \text{operazione logica:} \\ Y = A + B & \quad \text{operazione logica:} \\ \end{array}
Circuiti equivalenti De Morgan
Applicazione pratica: due circuiti diversi (uno con AND+NOT, l’altro con NAND) sono equivalenti
grazie ai teoremi di De Morgan.

Esempi applicativi

Per comprendere meglio l’algebra di Boole, è utile osservare esempi concreti tratti
sia dalla vita quotidiana sia da strumenti che usiamo ogni giorno, come Excel.

—

Esempio 1 – Interruttori in serie e in parallelo

Due interruttori collegati in serie funzionano come un operatore AND:
la lampadina si accende solo se entrambi sono chiusi.
Due interruttori collegati in parallelo realizzano un OR:
la lampadina si accende se almeno uno dei due è chiuso.

Serie e parallelo
Rappresentazione con circuiti elettrici:
– Serie ⇔ AND
– Parallelo ⇔ OR

—

Esempio 2 – Linguaggio naturale

La logica booleana è presente anche nelle frasi quotidiane.

  • AND: “Posso uscire se ho finito i compiti e ho riordinato la stanza”.
  • OR: “Mi preparo un caffè o un tè”. (disgiunzione inclusiva: basta una delle due condizioni).
  • NOT: “Non ho fame” equivale a negare la proposizione “ho fame”.
  • XOR: “O vinci tu o vinco io” (ma non entrambi insieme).

—

Esempio 3 – Excel

Excel mette a disposizione funzioni logiche che corrispondono esattamente agli operatori booleani:

  • =AND(A1>10;B1<5) → restituisce VERO se entrambe le condizioni sono vere.
  • =OR(A1>10;B1<5) → restituisce VERO se almeno una condizione è vera.
  • =NOT(A1>10) → restituisce VERO se A1 non è maggiore di 10.
  • =XOR(A1>10;B1<5) → restituisce VERO se esattamente una delle due condizioni è vera.

Questi strumenti mostrano come l’algebra di Boole non sia solo teoria,
ma uno strumento utilizzato quotidianamente per l’analisi dei dati.

Excel – Formattazione condizionale: evidenziare celle con valore tra 5 e 6 equivale a verificare (x \ge 5) \land (x \le 6).

Formattazione condizionale in Excel
Esempio di evidenziazione mediante AND logico.

Abbiamo costruito un elenco di valori numerici all’interno di Excel. Vogliamo fare in modo che solo alcuni dei valori vengano evidenziati. Si tratta di un’operazione di formattazione condizionali. Selezionando la voce di menu Formato/Formattazione condizionale compare la finestra:

 

In particolare vogliamo indicare che desideriamo che il valore della cella sia compreso tra due valori. Il calcolo effettuato per stabilire se un numero soddisfa tale requisito proprio un AND logico tra due condizioni.
Otteniamo il risultato illustrato in figura in cui i «voti» insufficienti sono evidenziati dal retino (a video si distinguono per il colore rosso).

Consideriamo ancora un’applicazione in Excel. Abbiamo costruito un elenco di dati composto da alcuni nomi e abbiamo inserito l’operazione di filtraggio. Essa consiste nel selezionare solo dei valori dell’elenco secondo alcuni criteri. Dal menu Dati si accede a Filtro automatico. In un secondo tempo si è inserito un’opzione che permette di selezionare i dati secondo dei criteri personalizzati. La personalizzazione consiste, in questo caso nello specificare un criterio per Cognome, tale per cui vengano visualizzati solo i cognomi che iniziano con la lettera D. Per fare ciò abbiamo dovuto indicare due condizioni unendole con una AND: si vede, infatti, dalla figura che si è unito la condizione «è maggiore o uguale a D’Addazio» con la condizione «è minore di Finaldi».

 

Ultimo esempio di utilizzo dell’AND logico: capita spesso di effettuare ricerche su Internet. Utilizzando un motore di ricerca, si specificano delle parole chiave che il file o documento dovrà contenere. Per indicare la presenza di più di una parola chiave si usa il segno +.

ESEMPIO
Consideriamo un’operazione di filtro e vediamo di impostare una condizione OR con Excel.

Nel campo Città, impostiamo due condizioni, unite dal connettivo OR.

Il risultato è il seguente:

 

Associando logicamente più proposizioni in modo diverso, si ottengono espressioni logiche più complesse. Ad esempio:
A = oggi è giovedì
B = vado al cinema
C = vado al ristorante
A·(B+C) = oggi è giovedì “e” vado al cinema “o” vado al ristorante.

Il valore dell’espressione A·(B+C) si ricava dalla seguente tabella:

A B C B+C A·(B+C)
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 1 0
1 0 0 0 0
1 0 1 1 1
1 1 0 1 1
1 1 1 1 1

Tutte le considerazioni fatte fin qui nel campo delle posizioni logiche si possono trasferire nel campo dei circuiti che trattano segnali a due valori, come sono quelli usati nei calcolatori e nei sistemi digitali in genere. La cosa è comprensibile se supponiamo di avere a che fare con circuiti composti solo da interruttori, che fanno passare o meno la corrente.

—

Esempio 4 – Ricerca su Internet

Anche i motori di ricerca usano la logica booleana:

  • AND: digitando energia AND solare otteniamo risultati che contengono entrambe le parole.
  • OR: digitando energia OR elettricità otteniamo risultati che contengono almeno una delle due parole.
  • NOT: digitando energia NOT nucleare escludiamo i risultati che contengono la parola “nucleare”.

Esercizi

Per consolidare le conoscenze sull’algebra di Boole, proponiamo una serie di esercizi
che vanno dal riconoscimento delle tabelle di verità fino alla traduzione di circuiti
in formule logiche.
Gli studenti sono invitati non solo a trovare le risposte, ma anche a motivarle.

—

Esercizio 1 – Riconosci l’operatore

Osserva la seguente tabella di verità e individua quale operatore rappresenta.

A B Y
0 0 0
0 1 0
1 0 0
1 1 1

Soluzione attesa: Y = A · B (operatore AND).

—

Esercizio 2 – Riconosci l’operatore

Osserva questa seconda tabella di verità.

A B Y
0 0 0
0 1 1
1 0 1
1 1 1

Soluzione attesa: Y = A + B (operatore OR).

—

Esercizio 3 – Dal circuito alla funzione

Osserva il seguente schema logico e scrivi l’espressione booleana corrispondente.

Circuito logico esercizio
Schema logico da tradurre in espressione booleana.

Soluzione guida:
Si identificano le porte logiche, si scrivono le operazioni passo passo,
e si ottiene la funzione completa.

—

Esercizio 4 – Semplificazione

Semplifica la seguente espressione usando le leggi dell’algebra di Boole:

Y = \overline{A}\cdot B + \overline{A}\cdot \overline{B}

Svolgimento atteso: applicando la legge distributiva otteniamo
Y = \overline{A}\cdot (B + \overline{B}) = \overline{A}\cdot 1 = \overline{A} .

—

Esercizio 5 – Applicazioni pratiche

Scrivi in linguaggio Excel le seguenti condizioni:

  • “La cella C1 è vera se A1 è maggiore di 10 e B1 è minore di 5”.
    → =AND(A1>10;B1<5)
  • “La cella C1 è vera se A1 è diverso da 0”.
    → =NOT(A1=0)
  • “La cella C1 è vera se almeno una tra A1 e B1 è positiva”.
    → =OR(A1>0;B1>0)

—

Conclusione

L’algebra di Boole non è solo un insieme di formule astratte,
ma un linguaggio che descrive situazioni reali,
dal funzionamento degli interruttori nelle nostre case
alle logiche dei microprocessori e dei software che usiamo ogni giorno.

Attraverso operatori, leggi, teoremi ed esercizi applicativi,
abbiamo visto come il pensiero logico possa essere tradotto in forma simbolica,
ponendo le basi per l’informatica e l’elettronica digitale.

Articoli correlati

Evoluzione delle Macchine da calcolo

Hardware

Software