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
di
variabili booleane
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}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d938bc6c34d215ccefc60cef9023d7e616667084)
Le due funzioni sommate al secondo membro sono dette residui della funzione al primo membro rispetto alla variabile
Iniziamo a dimostrare questo teorema per una funzione a una sola variabile booleana
. In tal caso:
![{\displaystyle f(x_{1})=x_{1}\cdot f(1)+{\overline {x_{1}}}\cdot f(0)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/da918a829bb2405e5390d2cd64abdfaf72900a14)
- Se
allora
;
- Se
allora
;
- Se
allora
.
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
, risulta che per
![{\displaystyle k=0\rightarrow f(x_{1})=x_{1}\quad ;\quad k=1\rightarrow f(x_{1})=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/75b0c9cdf408143662fbe07f33b8a346906ab4c3)
infatti
![{\displaystyle 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}}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b57404429f8cb71e0af236aab493999b8f9c7cba)
Nel caso di
si ha che per
e per
, allora:
![{\displaystyle 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},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/439a9811e209737c53838e0408165be7374d310f)
che fornisce proprio
oppure
a seconda che
rispettivamente.
Applicando il teorema una seconda volta su ognuno dei residui rispetto alla variabile
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}),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/86aa0161c2758779ea8ab7c55f48ac8c46714476)
iterando il procedimento a tutte le
variabili si ottiene l'espressione di
in forma canonica AND-OR.
Per il principio di dualità si ottiene inoltre:
![{\displaystyle 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})],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4ca02f44a72df374fd2387ed7a17f5e1f22e43ac)
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.
- ^ (EN) George Boole, Proposition II, in An Investigation of the Laws of Thought: On which are Founded the Mathematical Theories of Logic and Probabilities, 1854, p. 73.