# 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

Si consideri una funzione $f(x_{1},x_{2},\ldots ,x_{n})$ da espandere rispetto alla variabile $x_{1}$. Questa variabile può assumere valore $0$ oppure $1.$
Caso $x_{1}=0$, cioè $f(0,x_{2},\ldots ,x_{n})$:
    $0\cdot f(1,x_{2},\ldots ,x_{n})+{\overline {0}}\cdot f(0,x_{2},\ldots ,x_{n})=0\cdot f(1,x_{2},\ldots ,x_{n})+1\cdot f(0,x_{2},\ldots ,x_{n})=f(0,x_{2},\ldots ,x_{n}).$
Caso $x_{1}=1$, cioè $f(1,x_{2},\ldots ,x_{n})$:
    $1\cdot f(1,x_{2},\ldots ,x_{n})+{\overline {1}}\cdot f(0,x_{2},\ldots ,x_{n})=1\cdot f(1,x_{2},\ldots ,x_{n})+0\cdot f(0,x_{2},\ldots ,x_{n})=f(1,x_{2},\ldots ,x_{n}).$

## Proprietà

Per espandere rispetto a più variabili si reitera la precedente. Si consideri un'espansione rispetto a $x_{1}$ e $x_{2}$:
    $f(x_{1},x_{2},\ldots ,x_{n})=x_{2}\cdot [x_{1}\cdot f(1,1,\ldots ,x_{n})+{\overline {x_{1}}}\cdot f(0,1,\dots ,x_{n})]+{\overline {x_{2}}}\cdot [x_{1}\cdot f(1,0,\ldots ,x_{n})+{\overline {x_{1}}}\cdot f(0,0,\ldots ,x_{n})].$
Le operazioni di somma logica, prodotto logico o complementazione non annullano le proprietà di Shannon delle funzioni booleane. Infatti, se sommiamo logicamente $k$ alla funzione di una variabile $g(x_{1})=x_{1}$, si ottiene $f(x_{1})=x_{1}+k$ che:
* se $k=0,$ allora $f(x_{1})=x_{1},$
* se $k=1,$ allora $f(x_{1})=1.$
Infatti
    $f(x_{1})=f(1)\cdot x_{1}+f(0)\cdot {\overline {x_{1}}}=1\cdot x_{1}+k\cdot {\overline {x_{1}}}=x_{1}+k\cdot {\overline {x_{1}}},$
che fornisce proprio $f(x_{1})=x_{1}$ oppure $f(x_{1})=1$ a seconda che $k=0,1$ rispettivamente.
Nel caso di $f(x_{1})=x_{1}\cdot k$ si ha che:
* se $k=0,$ allora $f(x_{1})=0,$
* se $k=1,$ allora $f(x_{1})=x_{1}.$
Quindi
    $f(x_{1})=f(1)\cdot x_{1}+f(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},\ldots ,x_{n})=[x_{1}+f(0,x_{2},\dots ,x_{n})]\cdot [{\overline {x_{1}}}+f(1,x_{2},\ldots ,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.