sintesi

Algebra di Boole (1815-1864 logico e matematico inglese)

• Consente di descrivere in forma algebrica le funzioni dei circuiti

• Fornisce dei metodi per l’analisi e la sintesi (a livello logico) dei circuiti

• Tramite l’algebra di Boole si stabilisce una corrispondenza biunivoca tra – operazioni dell’algebra e componenti elementari

– espressioni algebriche e circuiti Le reti logiche

• Il progetto delle reti logiche si svolge in primo luogo tenendo conto delle funzionalità del circuito, indipendentemente dalla realizzazione fisica (progetto logico)

Ciò consente:

– di prescindere dai particolari realizzativi

– di risolvere a livello logico eventuali problemi implementativi

• Nel progetto delle reti logiche si impiega un sistema algebrico in cui ogni variabile può assumere solo uno tra due valori: 0 e 1

• Sulle variabili si applicano le operazioni: prodotto logico (*) o AND

somma logica (+) o OR negazione (x) o NOT

Proprietà dell’algebra di Boole

Proprietà 0 e 1 x_{ 0} x

1 1_

 x

1 0 1_{ }

x x_1

0 0_

 x

0 0 1_{ } Proprietà del complemento _xx1

0 1_

0

^x x

1 0_ Legge della doppia

negazione ^{x x}

Proprietà Commutativa ^x ^y ^y^{x x}^y^y^x

Proprietà Associativa x_

_

_{ }

_

_{   }

_{  }

_{ }

_

_

_{    }

_{ }

_

_

Leggi di Idempotenza x_x_x x_x_x

Leggi di De Morgan _{x yxy xyx y}

y x y x

x_{   } y x y x

x_{   }

Logica della proposizioni

p _p q p_q p_q p_q p_q p(xor)q

1 0 1 1 1 1 1 0

1 0 0 0 1 0 0 1

0 1 1 0 1 1 0 1

0 1 0 0 0 1 0 0

p_q=

_{   }

_{ }

_

_

Esiste una equivalenza tra le funzioni logiche e le

porte elementari delle reti logiche (Il lavoro di Boole fu ben recepito durante la sua vita, ma fu considerato soltanto "pura matematica" fino al 1938, quando Claude Shannon(1916-2001) pubblicò la sua tesi al MIT.

simbolismo di rappresentazione dei circuiti logici

Minimizzazione delle funzioni logiche

• Ad una funzione descritta tramite tabella di verità possono essere associate più espressioni algebriche. Quale scegliere ?

• Vista l’equivalenza con i circuiti, conviene scegliere l’espressione corrispondente al circuito a minimo costo (minimizzazione)

• Il costo può esprimersi in base a: – numero di porte

– numero di ingressi – eterogeneità delle porte

• I metodi per la minimizzazione si basano sulle proprietà dell’algebra di Boole. Esempio:

xyz z xy z y x z y x z y x z y x

f _{     }

semplificare

xyz_xyz_xy

_{ }

xyz_xyz_ xz(y_y)_xz xyz_xyz_xz(y_y)_xz xyz_xyz_ yz(x_x)_ yz z y x x z y z y x z y

x _{ } ( _ )_ xy_xy_x(y_y)_x

xz_xz_ x(z_z)_x Forma minima: f _x_ yz_ yz

Fasi del progetto di una rete logica 1. Definizione delle specifiche

• Identificazione delle variabili in ingresso e in uscita 2. Definizione della tabella di verità della funzione 3. Minimizzazione

4. Definizione del circuito