L’ algebra di Boole

Settembre 2002 IFTS2002 Acq. Dati Remoti: INFORMATICA 1

L’algebra di Boole

Esiste una definizione generale di algebra in cui, oggi, viene fattarientrare la geniale intuizione del matematico inglese George Boole(1815 - 1864) che, intorno al 1850 si rese conto, molto prima chel'Elettronica muovesse i primi passi, delle potenzialità di una strutturamatematica basata su un sistema minimale (2 soli elementi rappresen-tativi).La riscoperta e l'utilizzazione in Elettronica dell'algebra di Boole si devea von Neumann, colui che propose il modello strutturale su cui si basanoi moderni computer.

L'algebra binaria di Boole, come richiesto dalla definizione di algebra,prevede un insieme di supporto, A e due operatori binari che sichiamano, "somma" (simbolo ) e "prodotto" (simbolo ) cheassociano a coppie di elementi di A un elemento dello stesso insieme.

La scelta di questi simboli è fatta per sottolineare, in questa fase, chequesti sono altra cosa rispetto agli omonimi operatori aritmetici.


Il libro di Boole


Proprietà degli operatori booleani (assiomi)

Le operazioni di somma e prodotto sono commutative. Per ogni coppia di elementi x ed y appartenenti all’insieme A, si ha:

(x y) = (y x); (x y) = (y x) La somma è distributiva rispetto al prodotto e questo è

distributivo rispetto alla somma. Per ogni coppia di elementi x ed y appartenenti all’insieme A, si ha:

(x (y z)) = (x y) (x z); (x (y z)) = (x y) (x z);


Proprietà degli operatori booleani (assiomi) (2)

O è l'elemento neutro per la somma ed I è l'elemento neutro per il prodotto. Esistono due elementi O, I tali che: per ogni elemento x appartenente all’insieme A,

x O = x; x I = x Ogni elemento x dell'insieme A ammette un complemento x' che è unico e si indica con x. Per ogni elemento x appartenente all’insieme A, esiste un elemento x' tale che:

x x' = I; x x' = 0

Simboli usati per il complemento sono: x' , x, x


Un modello: algebra delle classi

S è un insieme finito. 2S è l'insieme delle parti di S (l’insieme di tutti i possibili sottoinsiemi costituiti da elementi di S), Esistono 2S sottoinsiemi distinti (vanno dall'insieme vuoto ad S), avendo indicato con S la cardinalità di S. Si può verificare che nell'algebra delle classi sono verificati tutti gli assiomi dell'algebra di Boole


Diagrammi di VennVisualizzazione grafica delle operazioni nel modello di Algebra di Boole consistente nell'algebra degli insiemi. T è l'universo della nostra struttura di insiemi, cioè è l'insieme contenente tutti gli elementi possibili. A e B sono due insiemi di punti

A

B

TABA

B

T

AB

A

B

T ~ AA

B

T ~ B


Verifica grafica di teoremi (1)

A

B

T

~A~B

dal confronto con la figura relativa a AB si ricava

~A~B= ~ (AB)

A

B

T~ A~ B dal confronto con la

figura relativa a AB si ricava

~A~B= ~ (AB)


Verifica grafica di teoremi (2)

X

Y

T

XY =

Graficamente poi sono ovvie le relazioni

~ = T~ T =

X ~X= T X ~X=

X T= TX T= X


Il nostro modello di Algebra di BooleL’algebra di Boole con cui lavoriamo ha un supporto A costituito da due soli elementi 0 ed 1: A = {0,1}.Le operazioni interne di questa algebra sono definite dalle seguenti tabelle delle operazioni che corrispondono alle operazioni logiche di OR ed AND e NOT a b ab

0 0 00 1 01 0 01 1 1

a b ab 0 0 0 0 1 1 1 0 1 1 1 1

Esse soddisfano i 4 postulati dell’algebra di Boole, come si può verificare per induzione perfetta cioè semplicemente verificando per tutti i possibili valori delle variabili, operazione macchinosa ma semplice concettualmente.

a ā0 11 0

Ad es. la commutatività di : ab = ba va verificata nei 4 casi possibili a=b=0, a=0 b=1, a=1 b=0 , a=b=1.Per a=b=0 si ha ab = 0 ba=0 e quindi ab = ba Per a=b=1 si ha ab = 1 ba=1 e quindi ab = ba Per a=1 b=0 si ha ab = 1 ba=1 e quindi ab = ba e così via.


L’algebra degli interruttori“Somma”:Il collegamento tra ingressi ed uscita è stabilito quando almenouno degli interruttori è“chiuso”.

“Prodotto”:Il collegamento è stabilito quando entrambigli interruttori sono “chiusi”

“Negazione”:Un interruttore “chiuso”va nello stato “aperto”,uno “aperto” passa allo stato “chiuso”.

O

I

A


Algebra delle porte

OR:Uscita ad “1” se almenouno degli ingressi è ad “1”

AND:Uscita ad “1” se entrambi gli ingressi sono ad “1”

NOT:Uscita a “0” se l’ingresso è ad “1”, uscita ad “1” se l’ingresso è a “0”


Variabili e costanti booleane

Tutti i simboli matematici consueti, possono essere usati per indicare uno dei due valori booleani, (O, I); es. : A, B, C, oppure x, y, z, ....., oppure, ancora, x0, x1, x2,....... Se un simbolo è associato sempre allo stesso valore booleano, esso rappresenta una costante. Se, invece esso può assumere volta per volta l'uno o l'altro dei due possibili valori, esso rappresenta una variabile booleana.


Espressioni booleaneUna espressione booleana è composta esclusivamente da costanti e variabili booleane, legate fra loro da operatori booleani. Esempi: (A B); (X Y) (C D); ( Z) (x0 x1) Le parentesi eliminano qualsiasi ambiguità sul significato degli operatori. Poiché un'espressione booleana può essere indicata con un unico simbolo, si possono scrivere relazioni in cui gli operatori booleani si applicano, non solo a costanti o variabili, ma ad intere espressioni.

Un'operazione tra due o più espressioni booleane è ancora un'espressione booleana. Si può dare una definizione precisa di una espressione booleana ben formata, facendo ricorso ad un modello di definizione ricorsiva o induttiva che incontreremo spesso in Informatica.


Semplificazione della scrittura delle espressioni

Una opportuna priorità assegnata agli operatori permette una prima semplificazione della scrittura delle espressioni booleane. La massima priorità va all'operatore di negazione "", quella intermedia va all'operatore prodotto "" la più bassa a quello di somma "". Queste regole consentono spesso di eliminare le parentesi senza introdurre ambiguità. Si può ad esempio scrivere A B C D Z senza che possano nascere equivoci sulla successione di operazioni da effettuare.


Semplificazioni dei simboli

Ulteriore semplificazione della scrittura:

NOT si indica, quando è possibile, con una linea sul simbolodella variabile:"Ā" invece di "A", altrimenti si scrive A*.

AND si indica con "" o si omette del tutto: A B si scrive,AB o A B

OR si indica con "+": A B si scrive più semplicemente, A +B.

In Elettronica "" è associato ad una operazione diversadall'OR.


Scheda riassuntivarelazioni e teoremi dell'algebra di Boole

postulati dualiP1 x y = y x x y = y x commutativitàP2 (x y) z = (x y) z = distributività

(x z) (y z) (x z) (y z) P3 x 0 = x x 1 = x elementi neutriP4 x ~x = 1 x ~x = 0 complemento

teoremi teoremi dualix 1 = 1 x 0 = 0x x = x x x = x idempotenzax y x z = x (y z) (x y) (x z)=x y z associativax y x ~y = x (x y) (x ~y) = xx x y = x x (x y) = x assorbimento(x y) (x ~y) = x (x y) (x ~y) = x


Analogie tra operatori aritmetici e logici (1)

Nel seguito sono sottolineate e riportate in rosso le leggi che non valgono perentrambi.

Commutatività ed associatività degli operatori + e AND OR ovvero o & |(completa analogia)

aritmeticaelementare

algebra diBoole

algebra diBoole

xy = yx xy = yx x&y = y&xx+y = y+x xy = yx x|y = y|x

(xy) z = x(yz)

(xy)z =x(yz)

(x&y)&z =x&(y&z)

(x+y)+z =x+(y+z)=x+y+|

z

(xy)z =x(yz)

(x|y)|z = x|(y|z)


Analogie tra operatori aritmetici e logici (2)Proprietà distributiva di rispetto a + (di AND rispetto adOR) (di rispetto a ) (di & rispetto a |). Completa analogia

x (y+z) =(xy)+(xz)

x(yz) =(xy)(xz)

x&(y|z) =(x&y)|(x&z)

Proprietà distributiva di OR rispetto ad AND (di rispetto a) o (di | rispetto a &) non vale per le corrispondentioperazioni aritmetiche (+ rispetto a ).

x+ (yz) (x+y) (x+z)

x (yz) =(xy) (xz)

x|(y&z) =(x|y)&(x|z)



Elemento neutro per l'operatore è 1. Per analogia il neutro perAND si designa con 1.Elemento neutro per l'operatore + è 0 per OR è 0. Si ottiene cosil'analogia completa

x1 = x x1 = xx+0 = x x0 = x

Gli elementi neutri sono uno il complemento dell'altro.

-1 0 1 = 0-0 1 0 = 1


Analogie tra operatori aritmetici e logici (4)Legge di annullamento L'analogia c'è solo per , e nonper +,

x+1 1 x1 = 1x0 = 0 x0 = 0

Legge della doppia negazione (completa analogia)

-(-x) = x x = x ~ ~x = x

La legge di idempotenza (o assorbimento) che caratterizza lealgebre di Boole non ha invece l'analogo nell'aritmeticaordinaria

xx x xx = x x&x = xx+x x xx = x x|x = x



Le seguenti formule, utili per la riduzione di espressioninell'algebra di Boole, non valgono per l'aritmetica elementare:

aritmeticaelementare

algebra diBoole

algebra diBoole

x +(xy) x x(xy) = x x|(x&y) = xx(x+y) x x(xy) = x x&(x|y) = xx +(xy) x x(x*y) = xy x|( ~x&y) = x|yx(x*+y) x x(x*y) =

xyx&( ~x|y) =

x&y


Teoremi di De Morgan

S i p o s s o n o v e r i f i c a r e l e r e l a z i o n i :

n o t e c o m e t e o r e m i d i D e M o r g a n . N e g a n d o e n t r a m b i i m e m b r i d e l l ed u e e g u a g l i a n z e s i o t t i e n e :

Q u e s t e d u e r e l a z i o n i m e t t o n o i n e v i d e n z a u n a c a r a t t e r i s t i c ad e l l ' a l g e b r a d i B o o l e : U n o d e i d u e o p e r a t o r i f o n d a m e n t a l i ( O R eA N D ) n o n è i n d i s p e n s a b i l e s e e s i s t e i l N O T .

L ' O R p u ò e s s e r e c o s t r u i t o c o n N O T e d A N D . L ' A N D p u ò e s s e r e o t t e n u t o d a N O T e O R .

yxyx

yxyx

yxyx

yxyx


Teoremi di De Morgan (2)

X

Y

XY

X Y

X Y = X + YXY

X Y = X + Y

X

Y

XY

X Y+

XY

X Y+ = X Y

X Y+ = X Y

XY X + Y

XY

X Y


Tabella di veritàO R , A N D e N O T , d e fin ite in m an ie ra s in te tica , p o sso n o e sse re m e sse in u n a fo rm a e sp lic ita co n la tecn ica d e lle " ta b e lle d i v e r ità " . L 'e sp re ss io n e d e riv a d a u n m o d e llo d i a lg e b ra b in a ria eq u iv a len te a q u e lla d e lle p o rte lo g ic h e in cu i i d u e v a lo ri b o o lean i so n o "vero " ("1 ") e " fa lso " ("0 ").

E ' im p o r ta n te r ilev a re ch e la d e fin iz io n e s in te tic a d e lla d u e fu n z io n i e lem e n ta r i co rr isp o n d e p e r l'A N D a ll'u ltim o r ig o e p er l'O R a l p r im o d e lle r isp e ttiv e ta b e lle d i v er ità

x y x y0

10

1

0 0

0010

1 1

x y x + y0

10

1

0 0

0111

1 1

A N D O Rx x01

10

N O T


Assegnazione di una funzione booleana

x 2 x 1 f0000

0 00 11 01 1

x 0

0101

1 0 001 0 011 1 001 1 11

g10010110

La tabella di verità è la tecnica standard per assegnare una funzione booleana di n variabili. Poiché 2n sono le disposizioni dei due valori booleani sugli n posti, se la funzione assegna un valore a tutte le combinazioni binarie, la tabella conterrà 2n righe e la funzione si dice, completa. Si possono definire contemporaneamente più funzioni di n variabili con tante colonne di assegnazione quante sono le funzioni.


Numero di righe di una tabella di verità

m

n

m

n

000

00

111

11

Il numero di righe di una tabella di verità evidentemente si ricava elencando tutte le possibili combinazioni delle variabili d’ingresso. Poichè i valori che le variabili possono assumere sono 0 o 1, occorre calcolare il numero di combinazioni di 0 ed 1 su n posti. Se ne può dare una dimostrazione induttiva che risulta anche costruttiva, cioè ci fornisce un algoritmo per costruire la tabella di verità completa, mediante raddoppio iterato della stessa.• nel caso n = 1, il numero di combinazioni di 0 ed 1 su un posto è 2• se il numero di combinazioni nel caso n è m, nel caso n+1 è 2m

Il numero combinazioni cercato è quindi

2•2•2•........ 2 = 2n

n volte


Numero di funzioni ad n variabili

Di questo risultato possiamo renderci conto mediante il seguente schema grafico, che è anche una dimostrazione ‘costruttiva’. Nel caso n = 2 graficamente si ha

Le possibili funzioni booleane distinte di n variabili sono:n22

elementinm 2

nm 222 x y f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

colonne


Numero di funzioni ad n variabili

Di questo risultato possiamo renderci conto mediante il seguente schema grafico, che è anche una dimostrazione ‘costruttiva’. Nel caso n = 2 graficamente si ha:

colonne

x y f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Le possibili funzioni booleane distinte di n variabili sono:n22

elementinm 2

nm 222


Le 16 funzioni di 2 variabili (operatori binari)e loro proprietà

[0 0 0 0] 0 costante [0 1 1 1] (b)|(a) OR [0 0 0 1] (a&b) AND [1 0 0 0] (~a&~b) NOR [0 0 1 0] (a&~b) variaz. and [1 0 0 1] (~a&~b)|(a&b) XNOR [0 0 1 1] (a) identità [1 0 1 0] (~b) not identità [0 1 0 0] (~a&b) variaz. and [1 0 1 1] (~b)|(a) Implicazione ba [0 1 0 1] (b) identità [1 1 0 0] (~a) not identità [0 1 1 0] (~a&b)|(a&~b) XOR [1 1 0 1] (~a)|(b) ab [1 1 1 0] (~a)|(~b) NAND [1 1 1 1] 1 costante

Sono commutativi gli operatori per cui f(x,y)=f(y,x).Sono associativi se f(f(x,y),z)=f(x,f(y,z)). Solo nel caso di associatività ha senso la definizione di porte a più ingressi, come per gli operatori and, or, xor, nand, or, xnor.


Teoremi e formule utili (1)

teoremi teoremi duali• x + 1 = 1 x 0 = 0• x + x = x x x = x idempotenza• x y + x z = x (y + z) (x + y) (x + z)=x + y z distributiva• x y + x ~y = x (x + y) (x + ~y) = x consenso• x + x y = x x (x + y) = x assorbimento• (x + y*) y = x y x y* + y = x + y• (x + y)(x*+ z)(y + z) = (x + y)(x*+ z)

x y + x*z + y z = x y +x*z consensoin formato Mat: (x&y)|(~x&z)|(y&z) = (~x&z)|(x&y);

• x + x*y = x + y e più in generale (x + y)(x*+ z) = x z + x*y


Prodotti e somme di variabilinelle tabelle di verità

Un modo per mettere la funzione da una forma tabellare in una formaalgebrica è, in linea di principio, quella di interpretare la tabella intermini di operatori elementari. Pi sono i 2n "prodotti" (si chiamano anche, clausole) delle n

variabili di un rigo, prese dirette o negate secondo la tabella Si sono, invece, le "somme" delle variabili prese ciascuna

complementata rispetto alla tabella.

Con riferimento alle rispettive tabelle si vede che: Per l'AND solo P3 = x y = 1; per l'OR solo S0 = x+y = 0Generalizzando, tutta l'informazione è contenuta nei Pi chevalgono "1" oppure negli Si che valgono "0".

x y x y0

10

1

0 0

0010

1 1

P 0

P 1

P 2

P 3

x y x + y0

10

1

0 0

0111

1 1

S 0

S 1

S 2

S 3


Forme canoniche SOP e POSS i c h i a m a f o r m a c a n o n i c a d i s g i u n t i v a d e l l a f u n z i o n e l ' O R d e i m i n t e r m i n i ( c l a u s o l e c h e c o r r i s p o n d o n o a g l i " 1 " d e l l a t a b e l l a d i v e r i t à ) . C o n r i f e r i m e n t o a l l a c o l o n n a f d e l l a t a b e l l a d i e s e m p i o s i h a :

I n q u e s t o c a s o s i d i c e a n c h e c h e l a f u n z i o n e è e s p r e s s a i n f o r m a S O P ( S u m o f P r o d u c t ) , c i o è c o m e s o m m a d i p r o d o t t i .

S i c h i a m a f o r m a c a n o n i c a c o n g i u n t i v a d e l l a f u n z i o n e l ' A N D d e i m a x t e r m i n i ( O R d e l l e c o n f i g u r a z i o n i d e l l e v a r i a b i l i , a d u n a a d u n a n e g a t e , c h e c o r r i s p o n d o n o a g l i " 0 " d e l l a t a b e l l a d i v e r i t à ) .

Q u e s t a f o r m a s i d i c e d i t i p o P O S , c i o è p r o d o t t o d i s o m m e .

210210210210 ),,( xxxxxxxxxxxxf

)()(

)()()(),,(

210210

210210210210

xxxxxx

xxxxxxxxxxxxf


La forma canonica SOPrealizza la funzione da cui è ricavata

Ognuna delle clausole Pi costituisce una funzione logica che, per le proprietà dell’AND vale 1 se e solo se le variabili assumono la configurazione degli ingressi da cui è stato ricavato quel prodotto. Ad es. dalla riga 010110 della funzione con variabili x,y,z,t,v,w si ricava il prodotto:

questo vale 1 se e solo se gli ingressi x,y,z,t,v,w valgono rispettivamente 010110.La funzione logica ottenuta mediante OR di tutte le clausole Pi , per le proprietà dell’OR a più ingressi dunque varrà 1 per quei valori delle variabili e solo per questi, e dunque solo per le righe in cui la funzione da realizzare vale 1.

*** tvwyzxP

111111

010110

1

x*yz*vtw*


La forma canonica SOPrealizza la funzione da cui è ricavata (2)

x y z w …..t f Pi Pj Pk Pl Pi +Pj +Pk +...+Pk =f

1

1

1

1

11

1

1

1

1

1

1

….


Completezza funzionaledi un set di operatori binari

Con lo sviluppo in forma POS o SOP risulta dimostrato che AND - OR - NOT sono un set funzionalmente completo.Si può dimostrare che:gli unici operatori che da soli risultano funzionalmente completi sono gli unici operatori che da soli risultano funzionalmente completi sono

NAND e NORNAND e NOR.Sistemi completi sono

AND - OR - NOTNANDNORAND - NOTOR - NOTAND - XOROR - XOR


Proprietà della porta XORIl connettivo XOR è commutativo ed associativo

x y = x y* + x*y = (x + y)(x*+ y*)

(x y)* = x y* = x* y = x y x*y* = (x*+ y)(x + y*)

x x = 0 x x* = 1

x 1 = x* x 0 = x

x (y z) = x y x z

x +y = x y x y = x x*y

x (x + y) = x*y

x x y = x y*

L’ algebra di Boole

Documents

Transcript of L’ algebra di Boole