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:
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:
- 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
infatti
Nel caso di 
si ha che per 
e per 
, allora:
che fornisce proprio 
oppure 
a seconda che 
rispettivamente.
Applicando il teorema una seconda volta su ognuno dei residui rispetto alla variabile 
si ottiene:
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.
