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,\dots ,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,\dots ,x_n)$:

$0\cdot f(1,x_2,\dots ,x_n)+\bar{0}\cdot f(0,x_2,\dots ,x_n)=0\cdot f(1,x_2,\dots ,x_n)+1\cdot f(0,x_2,\dots ,x_n)=f(0,x_2,\dots ,x_n).$

Caso $x_1=1$, cioè $f(1,x_2,\dots ,x_n)$:

$1\cdot f(1,x_2,\dots ,x_n)+\bar{1}\cdot f(0,x_2,\dots ,x_n)=1\cdot f(1,x_2,\dots ,x_n)+0\cdot f(0,x_2,\dots ,x_n)=f(1,x_2,\dots ,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,\dots ,x_n)=x_2\cdot [x_1\cdot f(1,1,\dots ,x_n)+\overline{x_1}\cdot f(0,1,\dots ,x_n)]+\overline{x_2}\cdot [x_1\cdot f(1,0,\dots ,x_n)+\overline{x_1}\cdot f(0,0,\dots ,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,\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.

Voci correlate

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