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.^[1]

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

${\displaystyle 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 ${\displaystyle x_{1}.}$

Si consideri una funzione ${\displaystyle f(x_{1},x_{2},\ldots ,x_{n})}$ da espandere rispetto alla variabile ${\displaystyle x_{1}}$. Questa variabile può assumere valore ${\displaystyle 0}$ oppure ${\displaystyle 1.}$

Caso ${\displaystyle x_{1}=0}$, cioè ${\displaystyle f(0,x_{2},\ldots ,x_{n})}$:

${\displaystyle 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 ${\displaystyle x_{1}=1}$, cioè ${\displaystyle f(1,x_{2},\ldots ,x_{n})}$:

${\displaystyle 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}).}$

Per espandere rispetto a più variabili si reitera la precedente. Si consideri un'espansione rispetto a ${\displaystyle x_{1}}$ e ${\displaystyle x_{2}}$:

${\displaystyle 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 ${\displaystyle k}$ alla funzione di una variabile ${\displaystyle g(x_{1})=x_{1}}$, si ottiene ${\displaystyle f(x_{1})=x_{1}+k}$ che:

• se ${\displaystyle k=0,}$ allora ${\displaystyle f(x_{1})=x_{1},}$
• se ${\displaystyle k=1,}$ allora ${\displaystyle f(x_{1})=1.}$

Infatti

${\displaystyle 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 ${\displaystyle f(x_{1})=x_{1}}$ oppure ${\displaystyle f(x_{1})=1}$ a seconda che ${\displaystyle k=0,1}$ rispettivamente.

Nel caso di ${\displaystyle f(x_{1})=x_{1}\cdot k}$ si ha che:

• se ${\displaystyle k=0,}$ allora ${\displaystyle f(x_{1})=0,}$
• se ${\displaystyle k=1,}$ allora ${\displaystyle f(x_{1})=x_{1}.}$

Quindi

${\displaystyle 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 ${\displaystyle f(x_{1})=0}$ oppure ${\displaystyle f(x_{1})=x_{1}}$ a seconda che ${\displaystyle k=0,1}$ rispettivamente.

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

${\displaystyle 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 ${\displaystyle n}$ variabili si ottiene l'espressione di ${\displaystyle f}$ in forma canonica AND-OR.

Per il principio di dualità si ottiene inoltre:

${\displaystyle 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.

• Algebra booleana
• Leggi di De Morgan
• Teorema dell'assorbimento