Skip to main content
Logo
Teorema di Espansione di Shannon
Overview

Teorema di Espansione di Shannon

Valerio Di Tommaso Valerio Di Tommaso
18 February 2026
3 min read

È un teorema che ci è utile ad ottenere in modo iterativo, la formula dell’output di una funzione booleana per ogni combinazione di ingressi (input): f(x,y,z)=f(0,0,0)+f(0,0,1)+f(0,1,0)...f(1,1,1);f(x, y, z) = f(0, 0, 0) + f(0, 0, 1) + f(0, 1, 0)... f(1, 1, 1);È come se ci permettesse di analizzare attraverso espressioni booleane una tabella di verità.

Le Forme del Teorema:

Formula Principale: f(x1​,x2​,...,xn​)=x1′​⋅f(0,x2​,...,xn​)+x1​⋅f(1,x2​,...,xn​)f(x_1​, x_2​, ...,x_n​) = x_1^{\prime}​ \cdot f(0, x_2​, ..., x_n​) + x_1​ \cdot f(1, x_2​, ..., x_n​)

Analizziamo la formula:

Cofattori: Sarebbero espressioni come:

  • f(0,x2​,...,xn​)f(0, x_2​, ..., x_n​) —> Descritto anche come fx0′f_{x_0^{\prime}}

    • Ma perché? Nella formula si vede x1′x_1^{\prime} moltiplicato (AND) con la funzione nel quale è stato assegnato x1=0x_1 = 0, in quanto 00 è una possibile combinazione di quella variabile all’interno della funzione f(x1​,x2​,...,xn​)f(x_1​, x_2​, ...,x_n​).

      È possibile dire che la variabile x1′x_1^{\prime} è utilizzata come “selettore” affinché l’affermazione della combinazione con cui è moltiplicata sia vera. Tant’è che infatti se facciamo l’AND tra x1′x_1^{\prime} e f(0,x2,...,xn)f(0, x_2, ..., x_n), otterremo sempre 00. Quindi nella formula: x1′x_1^{\prime} è una variabile necessaria a fare da “selettore” verificando la veridicità dell’affermazione secondo le regole dell’algebra di commutazione.

  • f(1,x2​,...,xn​)f(1, x_2​, ..., x_n​) —> Descritto anche come fx1f_{x_1}

    • Ma perché? Nella formula si vede x1x_1 moltiplicato (AND) con la funzione nel quale è stato assegnato x1=1x_1 = 1, in quanto 11 è una possibile combinazione di quella variabile all’interno della funzione f(x1​,x2​,...,xn​)f(x_1​, x_2​, ...,x_n​).

      È possibile dire che la variabile x1x_1 è utilizzata come “selettore” affinché l’affermazione della combinazione con cui è moltiplicata sia vera. Tant’è che infatti se facciamo l’AND tra x1x_1 e f(1,x2,...,xn)f(1, x_2, ..., x_n), otterremo sempre 1. Quindi nella formula: x1x_1 è una variabile necessaria a fare da “selettore” verificando la veridicità dell’affermazione secondo le regole dell’algebra di commutazione.

Esempio con funzione booleana a 2 variabili:

$f(x,y)​=x′⋅f(0,y)+x⋅f(1,y)=$
       $=x′⋅(y′⋅f(0,0)+y⋅f(0,1))+x⋅(y′⋅f(1,0)+y⋅f(1,1))=$
       $=x′y′⋅f(0,0)+x′y⋅f(0,1)+xy′⋅f(1,0)+xy⋅f(1,1)​;$

Questa formula effettua la Sum of Products (SOP), ossia l’OR tra AND svolti tra cofattori e i loro “selettori”. La Sum of Products (SOP) è la base su cui è costruita la Prima Forma Canonica.

Formula Duale: f(x1​,x2​,...,xn​)=(x1′+f(1,x2,...,xn​))⋅(x1​+f(0,x2,...,xn​))f(x_1​, x_2​, ..., x_n​) = (x_1^{\prime} + f(1, x_2, ..., x_n​)) \cdot (x_1 ​+ f(0, x_2, ...,x_n​))

Qui nella formula duale a quella principale che abbiamo appena visto, essendo appunto “duale”, vengono invertiti gli operatori e anche i termini 00 e 11, senza però cambiare i “selettori”. Questo è totalmente normale e anzi ci fa notare anche la veridicità della proprietà di Dualità, in quanto questa volta svolgendo ad esempio l’OR tra x1′x_1^{\prime} e l’11 del primo cofattore, vedremmo come il risultato sarebbe 11, che ci conferma come l’espressione rispetti le regole dell’algebra di commutazione e come anche il risultato sia duale come la formula.

Esempio con funzione booleana a 2 variabili:

$f(x,y)​=(x′+f(1,y))⋅(x+f(0,y))=$
       $=(x′+(y′+f(1,1))⋅(y+f(1,0)))⋅(x+(y′+f(0,1))⋅(y+f(0,0)))=$
       $=(x′+y′+f(1,1))⋅(x′+y+f(1,0))⋅(x+y′+f(0,1))⋅(x+y+f(0,0))​;$

Questa forma effettua il Product of Sums (POS), ossia l’AND tra OR svolti tra cofattori e i loro “selettori”. La Product of Sums (POS) è la base su cui è costruita la Seconda Forma Canonica.

Continua con… Le Forme Canoniche.