Algebra di Boole

Algebra di Boole

• Per affrontare in modo sistematico lo studio deisistemi di calcolo, abbiamo bisogno di unformalismo matematico definito su grandezzebinarie

• “Algebra di Boole”– Introdotta nel 1874 da George Boole per fornire una

rappresentazione algebrica della logica• Per questo motivo i circuiti elettronici che lavoro su valori

binari assumono il nome di circuti “logici” o porte “logiche”

– Applicata nel 1937 da Claude Shannon allo studio dellereti di interruttori

Semplice applicazione

• Variabile di controllo: X– due stati:

• X=0 -> non c’e’ pressione sull’interruttore• X=1 -> pressione sull’interruttore

• Uscita Y– Due stati:

• Lampadina spenta (Y=0)• Lampadina accesa (Y=1)

X=0 Y=0

Y = X

X=1Y=1

Operazioni elementari…

AND

OR

Y ≡ X1 and X2X1 X2

X1

X2

Y ≡ X1 or X2

Y

Y

Interruttori: relè

RELE’: interruttorecomandato da un segnaleelettricoDUE STATI• Quando la corrente fluiscenel circuito, l’elettromagneteattira una lamella del contattol’interruttore rimane aperto

• Se non circola corrente,l’interruttore rimane chiuso

elettromagnete

interruttore

Interruttori CMOS

• La tecnologia MOS permette di utilizzaretransistori unipolari come interruttori

• Le funzionalità sono simili a quelle del relè:– Funzione di trasmissione controllata mendiante

un ingresso di controllo (gate)

drain

source

gate

drain

source

gate

Modello per l’interruttore

• La variabile di controllo X controlla la funzione ditrasmissione, che – per convenzione - può valere 0(interruttore aperto) oppure 1 (interruttore chiuso)

xVariabile di controllo

Funzione di trasmissionet

a bx0

t0

statoaperto

1 1 chiuso

t

x

Interruttore negativo

a b

x0

t1

statochiuso

1 0 aperto

Porte logiche: modello

• Sono circuti digitali base nei quali viene individuatauna uscita (Y) ed uno o più ingressi (x1,..,xn)

• L’uscita dipende dal valore degli ingressi• Si possono realizzare mediante interruttori,

propagando la funzione di trasmissione in uscita

x1

xn

y

Esempio invertitore

X=0Y = 1

aperto

chiuso

X=1 Y = 0

chiuso

aperto

2.5V

0V

2.5V

XY

x0

y1

1 0

X Y

V =2.5 Volt

V =0 Volt

Invertitore:- output Y=0 se x=1- outpu y=1 se x=0

Postulati dell’Algebra di Boole

Un insieme I e due operatori binari + e · formanoun’algebra di Boole se soddisfano i seguenti assiomi(x,y,z sono elementi di I):

• " x,y Œ I x+y Œ I e x·y Œ I (chiusura delle operazioni)• $ 0 Œ I | " xŒI, x+0=x (elemento neutro per +)• $ 1 Œ I | " xŒI, x·1=x (elemento neutro per ·)• " x,yŒI x+y=y+x e x·y = y·x (proprietà commutativa)

• " x,y,z Œ I x+(y+z)=(y+x)+z e x·(y·z) = (y·x)·z) (prop.associativa)

• " x,y,z Œ I x·(y +z) = (x·y) + (x·z); x+(y·z)=(x+y)·(x+z)(proprietà distributiva)

• " xŒI $ ÿxŒI | x + ÿx = 1 e x·ÿx=0 (esistenza dell’inverso)

Proprietà di un’algebra booleana

• Gli elementi 0,1 sono unici• Per ogni xŒI , l’elemento ¬x (inverso di x) è unico

• x+x =x, xx= x idempotenza• x+xy = x, x(x+y)=x assorbimento• x+(¬x)y = x+y, x((¬x)+y)=xy• ¬(x+y) = (¬x)(¬y) De Morgan• ¬(xy) = (¬x)+(¬y)• ¬(¬x) = x involuzione

Algebra di commutazione

Con B={0,1} sono definiti i tre operatori di• somma logica (+), chiamato OR• prodotto logico (·), chiamato AND• Negazione (-) oppure (¬), chiamato NOT

• Applicata da C. Shannon nel 1936 per lo studio e laprogettazione di sistemi a relè

• Detta anche algebra logica, da cui reti o circuitilogici

Alcuni teoremi

• Teorema di De Morgan(x+y)= x · y

(x · y)= x + y• Teorema dell’involuzione

x=x• Legge di dualità

Ogni identità e ogni proprietà booleana resta valida sesi scambiano tra di loro gli operatori AND ed OR e glielementi 0 ed 1

Porta NOT

01

10

x y

Proprietà:

X=X

XY

Porta AND

x1x2

y

00 0

01 0

0 01

11 1

Proprietà:

ABC=(AB)C=A(BC)AB=BAAA=AA1=AA0=0

AA=0

111

001

010

000

x1 x2 y

Temporizzazioni porta AND

Porta OR

111

101

110

000

x1 x2 y

x1

x2

y

00 0

01 1

0 11

11 1

Proprietà:

A+B+C=(A+B)+C=A+(B+C)A+B=B+AA+A=AA+1=1A+0=A

A+A=1

Temporizzazioni porta OR

Variabili di commutazione

Grandezza che può assumere i valori 0 oppure 1Se x,y,z sono variabili di commutazione allora:• x+y = y + x (commutatività)• xy=yx• x+(y+z)=(x+y)+z=x+y+z (associatività)• x (yz)=(xy) z=xyz• x(y+z)=(xy)+(xz) (distributività)• x+(yz)=(x+y)(x+z)

Funzioni di commutazione

Sia xi una variabile di commutazione ed x vettore din variabili: xi Π{0,1}, x Π{0,1}n

• Consideriamo le funzioni y=f(x)f: {0,1}n Æ {0,1}

Il dominio di f è costituito da tutte e sole le n-ple(x1,x2,…,xn) e il codominio è l’insieme {0,1}

NOTA: Il numero di n-ple diverse è 2n Quindif può essere definita mediante una tabella diverità (con 2n righe)

(il termine verità deriva dai valori TRUE/FALSE)

Tabelle di veritàtabella di verità di una funzione dicommutazione

2n configurazioni

n variabili valori funzione

111

101

110

000

Esempio: due var.x1 x2 y

.

.

.

Funzioni unarie

1

0

y2

0

1

y1

0

0

y0

11

10

y3x

y0 : funzione 0y1 : negazione (NOT)y2 : funzione identitày3 : funzione 1

Funzioni binarie (due variabili)

0

0

0

0

y0

0

0

0

1

y1

0

0

1

0

y2

0

0

1

1

y3

0

1

0

0

y4

0

1

0

1

y5

0

1

1

0

y6

0

1

1

1

y7

1

0

0

0

y8

1

0

0

1

y9

1

0

1

0

y10

1

0

1

1

y11

1

1

0

0

Y12

1

1

0

1

y13

1

1

1

0

y14

1

1

1

1

y15

01

10

11

00

x1 x0

Tutte le funzioni possono essere ricavate a partire dagli operatori{NOT,AND} oppure{NOT,OR} Esistono operatori universali?

AND ORNOT x1 NOT x0

Teorema di Shannon

Teorema di Shannonf(x1,..,xn) = xi f(x1,..,xi-1,1,xi+1...,xn) + ÿxi f(x1,..,xi-1,0,xi+1...,xn) 1£ i£n

Dimostrazione (per induzione):• Se xi = 0 allora il primo termine vale 0. Poiché ÿ0=1, si ha

f(x1,..,xn) = f(x1,.., xi-1,0, xi+1...,xn), che è identicamente veraperché, per ipotesi, xi = 0.

• Se xi = 1 allora il secondo termine vale 0. Poiché ÿ1=0, si haf(x1,..,xn) = f(x1,.., xi-1,1, xi+1...,xn), che è identicamente veraperché, per ipotesi, xi = 1.

Tutte le funzioni si possono realizzare con {NOT,AND}

Forma canonica Somma di Prodotti (SP)

Applichiamo il teorema più volte …

f(x1,..,xn) =

x1 f(1, x2,..,xn) + ÿx1 f(0,x2,...,xn) =

x1 (x2 f(1,1, x3..,xn) + ÿx2 f(1,0, x3..,xn)) + ÿx1 f(0,x2,...,xn)=

x1 x2 f(1,1, x3..,xn)+ x1 ÿx2 f(1,0, x3..,xn) + ÿx1 f(0,x2,...,xn)=

…..

x1 x2 …xn f(1,1, …,1) + x1 ÿx2 …xn f(1,0,1, …,1)+

x1 x2 … ÿxn f(1,1, …,0) + … + ÿx1 ÿx2 ÿx3 … ÿxn f(0,0,0, …,0)

Forma SP

• 2n termini• Termine generico della somma:

• x1a1

x2a2…. xn

an si chiama mintermine ed è ilprodotto di n variabili dirette o negate

x1a1

x2a2…. xn

an f(a1,a2, …,an)

Dove, ai Œ {0,1} e x1 = x e x0 = ÿx

Forma SP

f(x1,.., xn)= S mkf(k) => f(x1,.., xn)= S mkdove:

mk (mintermine) è una funzione che è sempre 0 tranne per una sola assegnazione di valori incui la funzione assume il valore 1in particolare se S ai 2i-1=k allora f(k) è il valore f(a1,..,an); in particolare• k=0: a1,.., an corrisponde a 000..000• k=1: a1,.., an corrisponde a 000...001,•.....• k= 2n : a1,.., an corrisponde a 111...111

k=0

2n-1

k|f(k)=1

Esempioy=f(x1,x2,x3) è 1 se e solo se il numero di variabili con

valore 1 è pari

y =m0+m3+m5+m6 =

0111

1011

1101

0001

1110

0010

0100

100001234567

m3

m0

m5

m6

x3 x2 x1 y

f(x1,x2,x3) = x3 x2 x1+ x3x2x1 + x3 x2 x1 + x3x2 x1

Forma canonica prodotto di somme (PS)

Sia f(x1,.., xn) = S mk e consideriamo

g(x1,.., xn) = S mk

La definizione implica g= not fInfatti, g vale 0 quando f vale 1 (poiché mancano imintermini) e viceversa

•f=not (not f)= not g= S mk

k|f(k)=1

• maxtermine: funzione sempre 1 tranne unaassegnazione di valori

• f= P mk => f(x1,.., xn) = P Mk

k|f(k)=0

k|f(k)=0 k|f(k)=0

k|f(k)=0

Esempio

• y=f(x1,x2,x3) è 1 se e solo se il numero di variabilicon valore 1 è pari

011110111101000111100010010010000

1234567

M2

M1

M4

M7

y =M1 M2M4M7 =P(1,2,4,7)

f(x1,x2,x3) =(x3+x2+ x1)·(x3 + x2 + x1)·( x3 + x2 + x1 ))·( x3 + x2 + x1)

x3 x2 x1 y

Esempio, n=3 variabili

A B CM0= + +A B CM1= + +

A B CM2= + +

A B CM3= + +

A B CM4= + +

A B CM5= + +

A B CM6= + +

A B CM7= + +A B Cm7=

A B Cm6=

A B Cm5=

A B Cm4=

A B Cm3=

A B Cm2=

A B Cm1=

A B Cm0=

111

011

101

001

110

010

100

000A B C minterm maxterm

Porta NAND

Proprietà:

A/B = B/AA/1= ÿAA/0=1A/ÿA=1Nota NANDnon è associativo

x1 x2 y

X0

X1

011

101

110

100

0

0

0

1

01

1

10

1

1

1

Y

x / y = xy = x + yx NAND y= x/y

Operatore NAND (NOT-AND)

NAND è un operatore universaleDimostrazione: con NOT, AND e OR posso

realizzare una qualunque funzioneQuindi è sufficiente mostrare che con NAND riesco

a fare le tre funzioni AND OR e NOT

(x / y) /(x / y) = xy = xy

(x / x) /(y / y) = x / y = x + y

x/x = x

Prodotto logico

Somma logica

Negazione

x/x = 1 Generazione della costante 1

1/1 = 0 Generazione della costante 0

Porta NOR

Proprietà:

AØB = BØA AØ1 = 0AØ0 = ÿA AØÿA = 0Nota: NOR non è associativo

x1 x2 y

011

001

010

100

0

0

0

1

01

1

10

0

0

1

X0

X1

Y

NOR èOperatore universale

x Ø y = x + y = x yx NOR y = x Ø y

Operatore NOR (NOT-OR)

• Operatore universale

( x Ø y )Ø( x Ø y ) = x + y

x Ø x = x

Somma logica

Prodotto logico

Negazione

x Ø x = 0 Generazione della costante 0

0 Ø 0 = 1 Generazione della costante 1

( x Ø x )Ø( y Ø y ) = x y

Operatore XOR

• or esclusivo, detto anche "somma modulo 2" o"anticoincidenza", indicato col simbolo ⊕

• x⊕y=x⊕y (proprietà commutativa)• (x⊕y)⊕z=x⊕(y⊕z) (associativa)• x⊕1=ÿx• x⊕0=x• x⊕x=0• x⊕ÿx =1NOTA: XOR Non è un operatore universale

011

101

110

000

YX2X1

x ⊕ y = xy + xy = (x + y)(x + y)⊕

X0

X1

Y

Temporizzazioni porta XOR

XOR e Funzione di disparità

• L’operatore ⊕ applicato a n variabili definisce la funzione didisparità o somma modulo 2:

P=x1⊕x2 ... ⊕xn

• La funzione P è chiamata di disparità perché vale 1 se e solo se unnumero dispari di variabili vale 1.

!• Il bit di parità che si aggiunge nei codici a rivelazione di errore è

ottenuto proprio con la funzione di disparità P; infatti aggiungendoal vettore X il bit P corrispondente alla funzione di disparità siottiene una stringa di bit che avrà sempre un numero pari di 1.

Operatore Simbolo Proprietà

NOT y=1 se e solo se x=0

AND y=x1x2 y=1 se e solo se x1=x2=1

OR y=x1+x2 y=0 se e solo se x1=x2=0

NAND y=x1/x2 y=0 se e solo se x1=x2 = 1

NOR y= xØx2 y=1 se e solo se x1=x2

XOR y = x1⊕x2 y=1 se e solo se x1≠x2

XNOR y= x1≡x2 y=1 se e solo se x1=x2

y=ÿx

= 0

Interverter Three-state

• L’uscita può assumere uno stato di alta impedenzaelettrica (non e’ uno stato logico), utile perdisconnettere l’uscita dagli altri circuiti ad essacollegati.

X Y

OE

Hi-1

010100

OE x2 y XY

Vdd

Vss

OE

Buffer three-state

• Serve per collegare vari le uscite di vari dispositiviad uno stesso mezzo trasmissivo (bus)

• Un solo segnale di abilitazione deve essereabilitante, gli altri devono mettere le uscite deibuffer three-state in alta impedenza.OE1

OE2

OEn

In1

In2

Inn

Out

Buffer three-state (cont.)

• Schema “elettrico”

Per evitare instabilità elettrica quando tutti i segnali di abilitazione valgono 1 si usa una resistenza di “pull-up” (o pull-down)

R

R

OE1

OE2

OEn

In1

In2

Inn

Out