Teorema di Shannon (elettronica)

Teorema importante dell'informatica digitale. Riguarda le funzioni booleane

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 teoremaModifica

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  

DimostrazioneModifica

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.

Applicazione alle porte logicheModifica

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.

NoteModifica

  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 correlateModifica