Teorema di Shannon (elettronica)

Da Wikipedia, l'enciclopedia libera.

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]

Il teorema[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

Iniziamo a dimostrare questo teorema per una funzione ad 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.

Applicazione alle porte logiche[modifica | modifica wikitesto]

Applicando il teorema una seconda volta su ognuno dei residui rispetto alla variabile si ottiene:

iterando il procedimento a tutte le n 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[modifica | modifica wikitesto]

  1. ^ (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.

Voci correlate[modifica | modifica wikitesto]