Teorema di Shannon (elettronica)
# Teorema di Shannon (elettronica)

In elettronica digitale il teorema di Shannon è un importante teorema riguardante le funzioni booleane principalmente usato per scomporre una funzione complessa in funzioni più semplici o per ottenere un'espressione canonica da una tabella della verità o da un'espressione non canonica.

Nonostante sia attribuito a Claude Shannon, il teorema è stato enunciato per primo da George Boole.

## Il teorema

Data una funzione booleana $f$ di $n$ variabili booleane $x_{1},x_{2},\dots ,x_{n},$ vale l'uguaglianza:

    $f(x_{1},x_{2},\dots ,x_{n})=x_{1}\cdot f(1,x_{2},\dots ,x_{n})+{\overline {x_{1}}}\cdot f(0,x_{2},\dots ,x_{n}).$

Le due funzioni sommate al secondo membro sono dette residui della funzione al primo membro rispetto alla variabile $x_{1}.$

### Dimostrazione

Iniziamo a dimostrare questo teorema per una funzione a una sola variabile booleana $x_{1}$. In tal caso:

    $f(x_{1})=x_{1}\cdot f(1)+{\overline {x_{1}}}\cdot f(0)$
* Se $f(x_{1})=k\$ allora $f(x_{1})=x_{1}\cdot k+{\overline {x_{1}}}\cdot k=k(x_{1}+{\overline {x_{1}}})=k$;
* Se $f(x_{1})=x_{1}\$ allora $f(x_{1})=x_{1}\cdot 1+{\overline {x_{1}}}\cdot 0=x_{1}$;
* Se $f(x_{1})={\overline {x_{1}}}$ allora $f(x_{1})=x_{1}\cdot 0+{\overline {x_{1}}}\cdot 1={\overline {x_{1}}}$.

Le operazioni di somma logica, prodotto logico o complementazione non annullano le proprietà di Shannon delle funzioni booleane. Infatti, se sommiamo logicamente alla funzione di una variabile $f(x_{1})=x_{1}+k$, risulta che per

    $k=0\rightarrow f(x_{1})=x_{1}\quad ;\quad k=1\rightarrow f(x_{1})=1$

infatti

    $f(x_{1})=f(x_{1}=1)\cdot x_{1}+f(x_{1}=0)\cdot {\overline {x_{1}}}=1\cdot x_{1}+k\cdot {\overline {x_{1}}}=x_{1}+k\cdot {\overline {x_{1}}}.$

Nel caso di $f(x_{1})=x_{1}\cdot k$ si ha che per $k=0\rightarrow f(x_{1})=0$ e per $k=1\rightarrow f(x_{1})=x_{1}$, allora:

    $f(x_{1})=f(x_{1}=1)\cdot x_{1}+f(x_{1}=0)\cdot {\overline {x_{1}}}=k\cdot x_{1}+0\cdot {\overline {x_{1}}}=k\cdot x_{1},$

che fornisce proprio $f(x_{1})=0$ oppure $f(x_{1})=x_{1}$ a seconda che $k=0,1$ rispettivamente.

## Applicazione alle porte logiche

Applicando il teorema una seconda volta su ognuno dei residui rispetto alla variabile $x_{1}\$ si ottiene:

    $f(x_{1},x_{2},\dots ,x_{n})=x_{1}x_{2}\cdot f(1,1,\dots ,x_{n})+{\overline {x_{1}}}x_{2}\cdot f(0,1,\dots ,x_{n})+x_{1}{\overline {x_{2}}}\cdot f(1,0,\dots ,x_{n})+{\overline {x_{1}x_{2}}}\cdot f(0,0,\dots ,x_{n}),$

iterando il procedimento a tutte le $n$ variabili si ottiene l'espressione di $f\$ in forma canonica AND-OR.

Per il principio di dualità si ottiene inoltre:

    $f(x_{1},x_{2},\dots ,x_{n})=[x_{1}+f(0,x_{2},\dots ,x_{n})]\cdot [{\overline {x_{1}}}+f(1,x_{2},\dots ,x_{n})],$

che è detto teorema duale. Anche sfruttando tale teorema si ottiene l'espressione algebrica della funzione in forma canonica AND-OR.

Il risultato finale è l'implementazione della funzione in una struttura di porte logiche semplici AND, OR e NOT, detta multiplexer.

