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.

Il teorema[modifica | modifica sorgente]

Data una funzione booleana f \ di x_0, x_1, \dots, x_n variabili booleane, vale l'uguaglianza:

f(x_0, x_1, \dots, x_n) = x_0 \cdot f(1, x_1, \dots, x_n) + \overline{x_0} \cdot f(0, x_1, \dots, x_n)

Le due funzioni sommate al secondo membro sono dette residui della funzione al primo membro rispetto alla variabile x_0 \ .

Dimostrazione[modifica | modifica sorgente]

Iniziamo a dimostrare questo teorema per una funzione ad una sola variabile booleana x_0. In tal caso:

f(x_0) = x_0 \cdot f(1) + \overline{x_0} \cdot f(0)
  • Se f(x_0) = k \ allora f(x_0) = x_0 \cdot k + \overline{x_0} \cdot k = k (x_0 + \overline{x_0}) = k;
  • Se f(x_0) = x_0 \ allora f(x_0) = x_0 \cdot 1 + \overline{x_0} \cdot 0 = x_0;
  • Se f(x_0) = \overline{x_0} allora f(x_0) = x_0 \cdot 0 + \overline{x_0} \cdot 1 = \overline{x_0}.

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 f(x_0) = x_0 + k, risulta che per

k=0 \rightarrow f(x_0)=x_0 \quad ; \quad k=1 \rightarrow f(x_0) = 1

infatti

f(x_0) = f(x_0 = 1) \cdot x_0 + f(x_0 = 0) \cdot \overline{x_0} = 1 \cdot x_0 + k \cdot \overline{x_0} = x_0 + k \cdot \overline{x_0}

Nel caso di f(x_0) = x_0 \cdot k si ha che per k = 0 \rightarrow f(x_0) = 0 e per k=1 \rightarrow f(x_0) = x_0, allora:

f(x_0) = f(x_0 = 1) \cdot x_0 + f(x_0 = 0) \cdot \overline{x_0} = k \cdot x_0 + 0 \cdot \overline{x_0} = k \cdot x_0

che fornisce proprio f(x_0) = 0 oppure f(x_0) = x_0 a seconda che k=0, 1 rispettivamente.

Applicazione alle porte logiche[modifica | modifica sorgente]

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

f(x_0, x_1, \dots, x_n) = x_0 x_1 \cdot f(1, 1, \dots, x_n) + \overline{x_0}x_1 \cdot f(0, 1, \dots, x_n) + x_0 \overline{x_1} \cdot f(1, 0, \dots, x_n) + \overline{x_0 x_1} \cdot f(0, 0, \dots, x_n)

iterando il procedimento a tutte le n variabili si ottiene l'espressione di f \ in forma canonica AND-OR.

Per il principio di dualità si ottiene inoltre:

f(x_0, x_1, \dots, x_n) = [x_0 +  f(0, x_1, \dots, x_n)]\cdot[\overline{x_0} + f(1, x_1, \dots, x_n)

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.

Voci correlate[modifica | modifica sorgente]