ELEMANIA
Digitale - Sintesi di una tabella di verità
Teorema fondamentale dell'algebra booleana

In base al teorema fondamentale dell'algebra booleana, qualsiasi tabella di verità e qualsiasi espressione logica (non importa quanto essa sia complicata) possono essere espresse usando solo gli operatori elementari AND, OR e NOT. In altre parole non sono necessarie altre operazioni logiche (oltre alle tre fondamentali) per rappresentare l'intera algebra di Boole.

Questo teorema è molto importante poiché ci garantisce che, data una tabella di verità, esiste certamente almeno un'espressione logica che la realizza e che tale espressione logica può essere realizzata mediante le sole tre operazioni logiche fondamentali (AND, OR e NOT).

 

Sintesi: infinite espressioni logiche corrispondenti a una tabella di verità

Per lo studio dei circuiti logici, di cui parleremo più avanti, riveste grande interesse il problema di trovare un'espressione logica corrispondente a una data tabella di verità. La tabella di verità rappresenta la descrizione del funzionamento del circuito logico, mentre l'espressione logica costituisce la realizzazione della tabella per mezzo delle operazioni logiche elementari.

La realizzazione di una tabella di verità mediante un'espressione logica prende il nome di sintesi logica. Occorre però notare fin da subito che in generale data una tabella di verità non esiste una sola espressione logica che la realizza. Facciamo un esempio. Si consideri la seguente tabella di verità:

A B U
0 0 1
0 1 1
1 0 1
1 1 0

Non è difficile verificare che essa corrisponde alla seguente espressione logica:

U = A . B

D'altra parte, in base al teorema di De Morgan, l'espressione precedente può anche essere scritta nel seguente modo che corrisponde sempre alla stessa tabella di verità:

U = A + B

Come si può notare, alla stessa tabella di verità corrispondono due espressioni logiche diverse. Ovvero la tabella di verità può essere sintetizzata in modi diversi.

Questo è vero in generale per qualsiasi tabella di verità.

Anzi, non è difficile dimostrare che le possibili realizzazioni di una data tabella di verità sono addirittura infinite. Infatti, data per ipotesi un'espressione logica corrispondente a una certa tabella di verità, è sufficiente negarla due volte per ottenere un'altra espressione ancora corrispondente alla stessa tabella. Ma negando altre due volte la nuova espressione, se ne ottiene un'altra sempre corrispondente alla tabella iniziale e così via all'infinito.

Sintesi minima

Le espressioni logiche che corrispondono a una tabella di verità non sono tutte equivalenti, in quanto in generale contengono un numero diverso di operazioni logiche. Facendo riferimento all'esempio precedente, l'espressione

U = A . B

contiene un AND e un NOT, mentre l'espressione

U = A + B

contiene un OR e due NOT. La prima espressione, come si vedrà nel seguito, risulta più economica da realizzare circuitalmente, in quanto contiene un numero inferiore di operazioni logiche elementari.

In generale, data una tabella di verità, si dice minima l'espressione logica che la realizza col minor numero possibile di operazioni logiche elementari.

 

precedente - successiva

Sito realizzato in base al template offerto da

http://www.graphixmania.it