Teorema di espansione di Shannon

Prendiamo $f:B^n\mapsto B$, per tutti gli elementi in $B^n$ si ha:

$$f(x_0,x_1,\dots ,x_n)=x_0^{\prime }\cdot f(0,x_1,\dots ,x_n)+x_0\cdot f(1,x_1,\dots ,x_n)$$

Il teorema di espansione di Shannon si può scrivere anche nella sua forma duale, cioè la seguente:

$$f(x_0,x_1,\dots ,x_n)=(x_0^{\prime }+f(1,x_1,\dots ,x_n))\cdot (x_0+f(0,x_1,\dots ,x_n))$$

I fattori $f(0,x_1,\dots ,x_n)$ e $f(1,x_1,\dots ,x_n)$ sono detti cofattori e si dicono rispettivamente $f_{x_0^{\prime }}$ e $f_{x_0}$.

Esempio del teorema di espansione di Shannon

Prendiamo la funzione booleana a 2 variabili $f(x,y)$ e usiamo il teorema di espansione di Shannon:

$$\begin{array}{rl}f(x,y)& =x^{\prime }\cdot f(0,y)+x\cdot f(1,y)=\\ & =x^{\prime }\cdot (y^{\prime }\cdot f(0,0)+y\cdot f(0,1))+x\cdot (y^{\prime }\cdot f(1,0)+y\cdot f(1,1))=\\ & =x^{\prime }{y}^{\prime }\cdot f(0,0)+x^{\prime }y\cdot f(0,1)+x{y}^{\prime }\cdot f(1,0)+xy\cdot f(1,1)\end{array}$$

Esempio del teorema di espansione di Shannon nella sua forma duale

Se prendiamo la forma duale del teorema di espansione di Shannon con una funzione a 2 variabili $f(x,y)$ otterremmo questo:

$$\begin{array}{rl}f(x,y)& =(x^{\prime }+f(1,y))\cdot (x+f(0,y))=\\ & =(x^{\prime }+(y^{\prime }+f(1,1))\cdot (y+f(1,0)))\cdot (x+(y^{\prime }+f(0,1))\cdot (y+f(0,0)))=\\ & =(x^{\prime }+y^{\prime }+f(1,1))\cdot (x^{\prime }+y+f(1,0))\cdot (x+y^{\prime }+f(0,1))\cdot (x+y+f(0,0))\end{array}$$

Il teorema di Shannon si può iterare più volte, come visto negli esempi soprastanti. La formula generale per scrivere tutte le iterazioni di una funzione a $n$ variabili si utilizza questa forma:

$$\begin{array}{rl}& x_1^{\prime }\cdot x_2^{\prime }\cdot \dots \cdot x_{n-1}^{\prime }\cdot x_n^{\prime }\cdot f(0,0,\dots ,0,0)+\\ +& x_1^{\prime }\cdot x_2^{\prime }\cdot \dots \cdot x_{n-1}^{\prime }\cdot x_n\cdot f(0,0,\dots ,0,1)+\\ +& \dots +\\ +& x_1\cdot x_2\cdot \dots \cdot x_{n-1}\cdot x_n\cdot f(1,1,\dots ,1,1)\end{array}$$

Mentre la forma generale delle iterazioni per la forma duale del teorema di espansione si rappresenta nella seguentet maniera:

$$\begin{array}{rl}& (x_1+x_2+++x_{n-1}+x_n+f(0,0,\dots ,0,0))\cdot \\ \cdot & (x_1+x_2+\dots +x_{n-1}+x_n^{\prime }+f(0,0,\dots ,0,1))\cdot \\ \cdot & (\dots )\cdot \\ \cdot & (x_1^{\prime }+x_2^{\prime }+\dots +x_{n-1}^{\prime }+x_n^{\prime }+f(1,1,\dots ,1,1))\end{array}$$

Perché il teorema funziona?

Facciamo un’esempio, se prendiamo la funzione a 1 variabile $f(x)$ e proviamo ad espanderla:

$$f(x)=x^{\prime }\cdot f(0)+x\cdot f(1)$$

Dopo aver fatto l’espansione, proviamo a sostituire alla $x$ un valore:

$$\begin{array}{rl}f(0)& =1\cdot f(0)+0\cdot f(1)\\ & =f(0)\\ & \\ & \\ f(1)& =0\cdot f(0)+1\cdot f(1)\\ & =f(1)\end{array}$$

Come visto dai risultati, le due equazioni sono soddisfatte.