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 di variabili booleane vale l'uguaglianza:
Le due funzioni sommate al secondo membro sono dette residui della funzione al primo membro rispetto alla variabile
Dimostrazione Si consideri una funzione da espandere rispetto alla variabile . Questa variabile può assumere valore oppure
Caso , cioè :
Caso , cioè :
Proprietà Per espandere rispetto a più variabili si reitera la precedente. Si consideri un'espansione rispetto a e :
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 , si ottiene che: se allora se allora
Infatti
che fornisce proprio oppure a seconda che rispettivamente.
Nel caso di si ha che: se allora se allora
Quindi
che fornisce proprio oppure a seconda che rispettivamente.
Applicazione alle porte logiche 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:
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.
Note
Voci correlate Algebra booleana Leggi di De Morgan Teorema dell'assorbimento
Categoria:Elettronica digitale Shannon Categoria:Algebra di Boole