A.S.E.A.S.E. 88..11

ARCHITETTURA DEI SISTEMI ARCHITETTURA DEI SISTEMI ELETTRONICIELETTRONICI

LEZIONE N° LEZIONE N° 88

ALGEBRA BOOLEANAALGEBRA BOOLEANA

• PostulatiPostulati• Principio di dualitàPrincipio di dualità• Teoremi fondamentaliTeoremi fondamentali

A.S.E.A.S.E. 88..22

RichiamiRichiami

• Insieme di elementiInsieme di elementi• Variabili, costantiVariabili, costanti• Insieme di operazioniInsieme di operazioni• Insieme di postulatiInsieme di postulati• Espressioni algebricheEspressioni algebriche• Tabella di veritàTabella di verità• Espressione algebrica Espressione algebrica vs.vs. Tabella di Tabella di

veritàverità• Tabella di verità Tabella di verità vs.vs. Espressione Espressione

algebricaalgebrica

A.S.E.A.S.E. 88..33

Postulati di HUNTINGTON (1)Postulati di HUNTINGTON (1)

• Esistono un dominio”B” costituito almeno Esistono un dominio”B” costituito almeno da due elementi e due operatori binari (cioè da due elementi e due operatori binari (cioè che operano su due elementi) (+) e (che operano su due elementi) (+) e ())tali tali che:che:

a.a. Se Se xx e e y y sono elementi di “B”, allora sono elementi di “B”, allora xx + +yy è un elemento di “B”. L’operazione è un elemento di “B”. L’operazione eseguita da (+) prende il nome di eseguita da (+) prende il nome di SOMMA LOGICA.SOMMA LOGICA.

b.b. Se Se xx e e y y sono elementi di “B”, allora sono elementi di “B”, allora xx yy è un elemento di “B”. L’operazione è un elemento di “B”. L’operazione eseguita da (eseguita da () prende il nome di ) prende il nome di PRODOTTO LOGICO.PRODOTTO LOGICO.

A.S.E.A.S.E. 88..44

Postulati di HUNTINGTON (2)Postulati di HUNTINGTON (2)

ELEMENTI IDENTITÀELEMENTI IDENTITÀ

• Sia Sia xx un elemento di “B” un elemento di “B”a.a. Esiste in “B” un elemento “0”, Esiste in “B” un elemento “0”,

chiamato chiamato ELEMENTO IDENTITÀELEMENTO IDENTITÀ rispetto rispetto aa (+) (+) tale chetale che risulti risulti xx + 0 = + 0 = x .x .

b.b. Esiste in “B” un elemento “1”, Esiste in “B” un elemento “1”, chiamato chiamato ELEMENTO IDENTITÀELEMENTO IDENTITÀ rispetto rispetto aa ( () ) tale chetale che risulti risulti xx 1 = 1 = x .x .

A.S.E.A.S.E. 88..55

Postulati di HUNTINGTON (3)Postulati di HUNTINGTON (3)

Proprietà COMMUTATIVAProprietà COMMUTATIVA

a.a. Esiste la proprietà commutativa Esiste la proprietà commutativa rispetto alla somma logica: rispetto alla somma logica: x x ++ y y = = y y ++ x x

b.b. Esiste la proprietà commutativa Esiste la proprietà commutativa rispetto al prodotto logico: rispetto al prodotto logico: x x y y = = y y x x

A.S.E.A.S.E. 88..66

Postulati di HUNTINGTON (4)Postulati di HUNTINGTON (4)

Proprietà DISTRIBUTIVAProprietà DISTRIBUTIVA

a.a. Il prodotto logico è distributivo Il prodotto logico è distributivo rispetto all’addizione :rispetto all’addizione :xx ((yy + + z z ) = ) = ((xx y y ) + () + (xx z z ) )

b.b. La somma logica è distributiva La somma logica è distributiva rispetto al prodotto:rispetto al prodotto: xx + ( + (yy z z ) = () = (xx + + y y ) ) ( (xx + + z z ))

A.S.E.A.S.E. 88..77

Postulati di HUNTINGTON (5)Postulati di HUNTINGTON (5)

COMPLEMENTAZIONECOMPLEMENTAZIONE• Se Se xx è un elemento di ”B”, allora esiste è un elemento di ”B”, allora esiste

un altro elemento un altro elemento x x , detto , detto COMPLEMENTOCOMPLEMENTO di di xx, che soddisfa le , che soddisfa le proprietà:proprietà:

a.a. x x ++ x x = = 11

b.b. x x x x = = 00

• x x realizza l’operazione di realizza l’operazione di complemento di complemento di xx

A.S.E.A.S.E. 88..88

RiassuntoRiassunto• POSTULATIPOSTULATI

0 5b 1 5a

4b 4a

3b 3a

1 2b 0 2a

)( logico Prodotto 1b )( logica Somma 1a

distinti elementi due Almeno

xxxx

zxyxzyxzxyxzyx

xyyxxyyx

xxxx

A.S.E.A.S.E. 88..99

OsservazioniOsservazioni

• Alcune proprietà dell’algebra booleana Alcune proprietà dell’algebra booleana sono vere anche nell’algebra sono vere anche nell’algebra normalmente usata:normalmente usata:– Proprietà commutativaProprietà commutativa– Proprietà distributiva del prodotto logicoProprietà distributiva del prodotto logico

• Altre proprietà non sono vere :Altre proprietà non sono vere :– Proprietà distributiva della somma logicaProprietà distributiva della somma logica

• L’operazione complemento logico esiste L’operazione complemento logico esiste solo nell’algebra booleanasolo nell’algebra booleana

• La sottrazione e la divisione non esistono La sottrazione e la divisione non esistono nell’algebra booleananell’algebra booleana

A.S.E.A.S.E. 88..1010

Principio di DUALITÀPrincipio di DUALITÀ

• Da un’osservazione dei postulati Da un’osservazione dei postulati precedenti si osserva che quelli “b” si precedenti si osserva che quelli “b” si ottengono da “a” ottengono da “a”

– Scambiando i due operatori binari fra Scambiando i due operatori binari fra loro, (+) con (loro, (+) con () e () e () con (+)) con (+)

– Scambiando fra loro i due elementi Scambiando fra loro i due elementi identità, 1 con 0 e 0 con 1identità, 1 con 0 e 0 con 1

A.S.E.A.S.E. 88..1111

TEOREMI FONDAMENTALITEOREMI FONDAMENTALI

• Tecniche di dimostrazione dei teoremiTecniche di dimostrazione dei teoremi– Impiego dei postulati fondamentaliImpiego dei postulati fondamentali– Uso di teoremi precedentemente Uso di teoremi precedentemente

dimostratidimostrati– Dimostrazione per assurdoDimostrazione per assurdo

• (si ipotizza verificata l’ipotesi opposta a (si ipotizza verificata l’ipotesi opposta a quella desiderata e si conclude che non è quella desiderata e si conclude che non è possibile che sia vera)possibile che sia vera)

– Dimostrazione per induzioneDimostrazione per induzione• (se una ipotesi è vera per k variabili e per (se una ipotesi è vera per k variabili e per

k+1 variabili allora è vera per qualunque n)k+1 variabili allora è vera per qualunque n)

A.S.E.A.S.E. 88..1212

Teorema 1Teorema 1

• 1a1a 1b1b

• DimostrazioneDimostrazione DimostrazioneDimostrazione

• Per DualitàPer Dualità

11x 00 x

5b 0

2a

4a 0

5b 0

2a 000

xx

xx

xxx

xx

5b 0

5a 1

4b

4a

3b

3a

2b 1

2a 0

xx

xx

zxyxzyx

zxyxzyx

xyyx

xyyx

xx

xx

A.S.E.A.S.E. 88..1313

Teorema 2Teorema 2(Involuzione)(Involuzione)

Il complemento del complemento è Il complemento del complemento è l’elemento stessol’elemento stesso

DimostrazioneDimostrazione

………………………………

xx

A.S.E.A.S.E. 88..1414

Teorema 3Teorema 3(Idempotenza)(Idempotenza)

• 3a3a 3b3b

• DimostrazioneDimostrazioneDimostrazioneDimostrazione

per dualitàper dualità

xxx xxx

2a

5b 0

4b

5a

2b 1

x

x

xxx

xxxx

xxxx

5b 0

5a 1

4b

4a

3b

3a

2b 1

2a 0

xx

xx

zxyxzyx

zxyxzyx

xyyx

xyyx

xx

xx

A.S.E.A.S.E. 88..1515

Teorema 4Teorema 4(assorbimento)(assorbimento)

• 4a4a 4b4b

• DimostrazioneDimostrazione DimostrazioneDimostrazione

per dualitàper dualità

xyxx xyxx

2b

T1a 3a 1

4a 1

2b 1

x

x

yx

yxxyxx

5b 0

5a 1

4b

4a

3b

3a

2b 1

2a 0

xx

xx

zxyxzyx

zxyxzyx

xyyx

xyyx

xx

xx

A.S.E.A.S.E. 88..1616

Teorema 5 Teorema 5 (semplificazione)(semplificazione)

• 5a5a 5b5b

• DimostrazioneDimostrazione DimostrazioneDimostrazioneyxyxx yxyxx

5b 0

5a 1

4b

4a

3b

3a

2b 1

2a 0

xx

xx

zxyxzyx

zxyxzyx

xyyx

xyyx

xx

xx

2a

5b 0

4a

yx

yx

yxxxyxx

A.S.E.A.S.E. 88..1717

Teorema 6Teorema 6(Legge Associativa)(Legge Associativa)

• 6a6a

• 6b6b

zyxzyxzyx

zyxzyxzyx

A.S.E.A.S.E. 88..1818

Teorema 7Teorema 7(Consenso)(Consenso)

• 7a7a• DimostrazioneDimostrazione

• 7b7b

zxxyyzzxxy

zxyxzyzxyx

5b 0

5a 1

4b

4a

3b

3a

2b 1

2a 0

xx

xx

zxyxzyx

zxyxzyx

xyyx

xyyx

xx

xx

4a

T6a 3a

4a

5a

zxxy

zyxzxxyzxy

xyzyzxzxxy

xxyzzxxyyzzxxy

A.S.E.A.S.E. 88..1919

Teorema 8Teorema 8((Teorema di DE MORGANTeorema di DE MORGAN))

• 8a8a 8b8b yxyx yxyx

A.S.E.A.S.E. 88..2020

OsservazioneOsservazione

• La tabella di verità consente di provare La tabella di verità consente di provare la veridicità di una relazione logica, la veridicità di una relazione logica, poiché verifica se la relazione è vera per poiché verifica se la relazione è vera per TUTTE le possibili combinazioni dei TUTTE le possibili combinazioni dei valori delle variabilivalori delle variabili

• Tale metodo prende il nome di Tale metodo prende il nome di • Metodo dell’INDUZIONE PERFETTEMetodo dell’INDUZIONE PERFETTE

A.S.E.A.S.E. 88..2121

Teorema 8Teorema 8(dimostrazione)(dimostrazione)

• 8a8a 8b8b

yxyx yxyx

xx yy x+x+

yy

( x+( x+

y)y)

xx yy x • x •

yy

00 00 00 11 11 11 11

00 11 11 00 11 00 00

11 00 11 00 00 11 00

11 11 11 00 00 00 00

xx yy x • x •

yy

( x ( x

•y)•y)

xx yy x + x +

yy

00 00 00 11 11 11 11

00 11 00 11 11 00 11

11 00 00 11 00 11 11

11 11 11 00 00 00 00

A.S.E.A.S.E. 88..2222

RiassuntoRiassunto

• TEOREMITEOREMI

8b 8a

7b y y 7a

yz 6b 6a

5b 5a

4b 4a

3b 3a

2a

00 1b 11 1a

yxyxyxyx

zxyxzyzxyxzxxyzzxx

xyzzxyxzyxzyxzyx

xyyxxyxyxx

xyxxxxyx

xxxxxx

xx

xx

A.S.E.A.S.E. 88..2323

ConclusioniConclusioni

• I 5 Postulati dell’algebra BooleanaI 5 Postulati dell’algebra Booleana• Principio di dualitàPrincipio di dualità• Teoremi fondamentaliTeoremi fondamentali• Induzione PerfettaInduzione Perfetta