title: Teorema di Shannon (elettronica)
text: # 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.
  
  