Algebra Boole Circuiti Logici

7/21/2019 Algebra Boole Circuiti Logici

1/63

2010 Marco Mezzalama, Elio Piccolo, Capire linformatica 1

Marco Mezzlama, Elio Piccolo

Capire linformatica

Algebra di Boole e Circuiti Logici


2/63



Capire linformatica

Perch importante la logica

alla base del ragionamento umano costituisce il fondamento teorico per

trattare i circuiti digitali che sono alla basedei calcolatori

essenziale per la costruzione deglialgoritmi e quindi per i linguaggi di

programmazione alla base di linguaggi non procedurali

come il Prolog


3/63



Capire linformatica

LAlgebra di oole fu ideata nella prima met! del "#" secolo dal

matematico inglese $eorge oole, con lintentodi ricondurre al rigore matematico il

ragionamento umano fu utilizzata da %& E& 'hannon allinizio del ""secolo per descri(ere il comportamento deicircuiti a commutazione )rela*s+, in uso nella

telefonia, e da qui ai dispositi(i digitali una struttura algebrica, potrebbe essereintrodotta in modo formale& -ui (err! proposta inmodo intuiti(o&


4/63



Capire linformatica

Le basi dellalgebra booleana

.ellalgebra di oole/ 'i mettono in corrispondenza le

proposizioni, o in generale gli e(enti binari,con le variabili logiche)o booleane+

Le (ariabili logiche sono denotate con lelettere dellalfabeto )A,,0a,b,0+

Le (ariabili logiche possono assumeresolo due (alori/ 1ero )2, o anche 3+ o4also )4, o anche 5+


5/63



Capire linformatica

Le basi dellalgebra booleana )6+

Esempi/macchina_parteP )7 2, o 3, se lamacchina parte, 4, o 5, se non parte+semaforo_verde' )7 3 se (erde, 5altrimenti+interruttore# )7 3 se chiuso, 5 se

aperto+.ota/ lassociazione stato (alore di(erit! arbitraria&


6/63



Capire linformatica

Le basi dellalgebra booleana )8+

.ellalgebra di oole/ si possono mettere in relazione n9ple di

(ariabili indipendenti con una particolare(ariabile dipendente

la (ariabile dipendente detta funzionebooleana

le funzioni booleane possono assumeresolo due (alori, 2 o 4, o((ero 3 o 5 Esempio * 7 F):3, :6, 0 :n+&


7/63



Capire linformatica

2a(ola di (erit!

;na funzione descritta in modoesausti(o stabilendo, per ognicombinazione delle (ariabili di ingresso,se (ale 3 oppure 5&

'i crea dunque una tabella, detta tavola diveritdella funzione&

-ui di seguito un esempio di ta(ola di(erit!/


8/63



Capire linformatica

Esempio di ta(ola di (erit!

M M l Eli Pi l


9/63



Capire linformatica

Esempio applicati(o


10/63



Capire linformatica

Esempio applicati(o )6+La tavola di verit della funzione telefonare

M M l Eli Pi l


11/63



Capire linformatica

-uante funzioni di n (ariabili@

#l numero di combinazioni delle (ariabili diingresso 6n& #nfatti la prima (ariabile pu=assumere 6 (alori, per ciascuno di essi laseconda (ariabile pu= assumere 6 (alori,e cos (ia, per un totale di 6 6606 76n&

-uante funzioni si possono costruire con n(ariabili@

M M l Eli Pi l


12/63



Capire linformatica

-uante funzioni di n (ariabili@ )6+n varabili

k

combinazioni

m funzioni

Numero variabili: n

Numero combinazioni:

k = 2n= 2^n

Numero funzioni:

m = 2^k = 2^(2^n)

Esempio: se n = 4

k = 2^4 = !" e

m = 2^!" = "#$#%"

M M l Eli Pi l


13/63



Capire linformatica

Bperatori logici/ lA.C

Bperatore A.CD esprime il concetto di


14/63



Capire linformatica

A.C )6+

D esempio/ mi_compro_il_gelatose fa_caldoA.C ho_i_soldi&

D (iene anche dettoprodotto logico, per

analogia con operatore matematico&D #l simbolo circuitale dellA.C/

Marco Mezzlama Elio Piccolo


15/63



Capire linformatica

A.C )8+

analogo elettrico delloperatore A.C/ dueinterruttori in serie&



16/63



Capire linformatica

B

Loperatore BD Esprime il concetto di disgiunzione logica

)una cosa oppureunaltra oppureentrambe+D indicato nei seguenti modi/ A B , A F

oppure A D opera secondo la seguente ta(ola di (erit!/



17/63



Capire linformatica

B )6+

D esempio/ esco_con_lombrellosepioveBnevica&

D (iene anche detto somma logica )ma quilanalogia con loperatore aritmetico piG

lasca+D #l simbolo circuitale dellB/



18/63


Marco Mezzlama, Elio PiccoloCapire linformatica

B )8+

analogo elettrico in un circuito dellB/due interruttori in parallelo



19/63



.B2

Bperatore .B2/D ha il significato di negazione logica

D indicato nei seguenti modi/ .B2 A, oppureA&

D Bpera secondo la seguente ta(ola di (erit!/



20/63



.B2 )6+

D Esempio/ _serenose nuvoloso&

D #l simbolo circuitale del .B2/



21/63



.B2 )8+D analogo elettrico delloperatore .B2/

.ota/ per realizzare la funzione di .B2 occorre undispositi(o

realizzato di solito con un semplice transistor&



22/63



Altri operatori note(oli

sono deri(abili dagli operatori elementari

sono di uso frequente o sonoconcettualmente rile(anti



23/63



E"9B

Loperatore E"9B )B esclusi(o+/D #ndicato nei seguenti modi/ A E"9B , oppure A

D opera secondo la seguente ta(ola di (erit!/



24/63



E"9B )6+

DA

equi(alente allespressione

D #l simbolo circuitale dellE"9B/

BABA +



25/63



E"9B )8+

Alcune interpretazioni dellE"9B )facendoriferimento alla ta(ola di (erit!+/D indica di(ersit! )(ale 3 se e solo se A e sono

di(ersi+D corrisponde alla somma9modulo96 )in cui si tieneconto solo del risultato e non del riporto+

D condizionamento/ sia il segnale condizionante&

-uando 75, luscita dellE"9B corrisponde alsegnale A& -uando 73, luscita corrisponde alsegnale A in(ertito )in(ertitore pilotato+&



26/63



#mplicazione logica

Loperatore di implicazione logicaD modella il costrutto logico


27/63



#mplicazione logica )6+

D (ale la seguente equi(alenza/

)la formula equi(alente permette le

manipolazioni algebriche+D si noti che se la premessa 4alsa )A 7 5+, la

formula resta 1era indipendentemente da

D esempio/ 'e triangolo_rettangoloalloraun_angolo_novanta_gradi

D il fondamento del ragionamento deduttivo

BABA +



28/63



Espressioni logiche

%ombinazione di (ariabili e operatori logici possono essere (alutate per ogni combinazione

delle (ariabili presenti e possono assumere il(alore 5 o 3

anche le espressioni si rappresentano mediantela ta(ola di (erit!&

.ota/D 'pesso loperatore di prodotto logico (iene omesso/

T7 abF cD (ale la priorit! degli operatori )nellordine, .B2, poi

A.C e infine B+


29/63



30/63



Espressioni equi(alenti )6+

Esempio di equazioni equi(alenti/

ba

b

a

TT

yzxzTyzxxzT

=

+=

+=


31/63



32/63


,Capire linformatica

Espressioni complementari

E3ed E6sono complementari se/D per tutte le combinazioni delle (ariabiliindipendenti per cui E37 3 risulta E67 5

eD per tutte le combinazioni delle (ariabiliindipendenti per cui E37 5 risulta E67 3

.ota/ se due espressioni sono complementari/

E37 E6



33/63



Espressioni complementari )6+

Esempio di funzioni complementari/

ba

b

a

TT

xyyxT

yxyxT

=

+=

+=



34/63



Espressioni complementari )8+



35/63


Capire linformatica

Espressioni duali

E6 dualedi E3 se pu= essere ottenuta da E3/ sostituendo lHoperatore B con lHoperatoreA.C e (ice(ersa )tenendo conto delleprecedenze degli operatori in E3 II+?

sostituendo il (alore 5 con il (alore 3 e(ice(ersa&

egola di complementazione/ lHespressionecomplementare di E3pu= essere ottenuta dallasua duale E6complementando tutte le (ariabili inE6)teorema di De Morgan+ &



36/63


Capire linformatica

Espressioni duale e complementare

F(a,b,c) = a (b + c) Fd = a + (b c) F = a + (b c)

a b c F Fd F

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

0 1 0 0 0 1

0 1 1 0 1 1

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

1 1 0 1 1 0

1 1 1 1 1 0



37/63


Capire linformatica

2eoremi dellalgebra di oole

si possono dimostrare per induzione completa/ sufficiente fare la ta(ola di (erit!&

(ale inoltre una propriet! legata alla dualit!/ stato dimostrato che se vale un teorema vale

anche il teorema duale, senza che di debbaripetere la dimostrazione&

ecco le propriet! e i teoremi piG importanti/



38/63


Capire linformatica

2eoremi dellalgebra di oole )6+

!:

&)

:

)

&:

!)

!!:

&&)

=+

=

=+

=

=+

=

=+

=

XXDuale

XXd

XXXDuale

XXXc

XXDuale

XXb

XDuale

Xa



39/63


Capire linformatica

2eoremi dellalgebra di oole )8+

ZYXZXYXDuale

vadistributiproprZYXZXYXh

ZYXZYXDuale

DeMorganteoremaZYXZYXg

ZYXZYXZYXDuale

assocproprZYXZYXZYXf

XYYXDualeacommutativproprXYYXe

+=++

+=+

=+++

+++=

++=++=++

==

+=+=

)()(:

'$')()

$$$$$$:

''$$$$$$)

)()(:

$'$')()()

:'$')



40/63


Capire linformatica

2eoremi dellalgebra di oole )J+

)()()()(:

)

)(:

)

)()(:

'$')

)(:

'')

YZXZYXZXZDuale

YZXZYXZXZl

YXYXXDuale

YXYXXk

XYXYXDuale

direttafusioneteorXYXYX

XYXXDuale

inclusionedellteoremaXYXXi

++=+++

+=+

=+

+=+

=++

=+

=+

=+

Marco Mezzlama, Elio PiccoloC i li f i


41/63


Capire linformatica

2eoremi dellalgebra di oole )K+

)$$$!&()$$$(:

)$$$&!()$$$()

)()(:

)()()

)()()()()(:

)

ZYfXZYXXfXDuale

ZYfXZYXXfXo

YXZXZXYXDuale

YXZXZXYXn

ZXYXZYZXYXDuale

ZXYXZYZXYXm

+=+

=

+=++

++=+

++=+++

+=++

Marco Mezzlama, Elio PiccoloC i li f ti


42/63


Capire linformatica

2eoremi dellalgebra di oole )+

atogeneralizzdeMorganZYXfZYXf!

ZYfXZYfXZYXXfDuale

ZYfXZYfXZYXXfp

'')$$$()$$$()

)$$$&!(()$$$!&(()$$$(:

)$$$!&()$$$&!()$$$()

+=+

++=

+=

Ca notare che nellalgebra di oole la propriet! distributi(a(ale sia per ilprodotto)logico+ che per la somma)logica+&



43/63


Capire linformatica

Calle funzioni alle espressioni logiche

;na funzione logica si rappresenta mediante lasua ta(ola di (erit!

Esempio/ un comitato di tre persone A, e %

prende le decisioni a maggioranza& 'i (uole lafunzione che esprima che una mozione appro(ata )passa, P+&

%on le stesse lettere A, e % si indicano le

(ariabili logiche che assumono il (alore 3 se lacorrispondente persona ha dato (oto fa(ore(ole,5 altrimenti&



44/63


Capire linformatica

Calle funzioni alle espressioni logiche )6+2a(ola di (erit! della funzione /



45/63


Capire linformatica

Calle funzioni alle espressioni logiche )8+

possibile rappresentare questa funzione medianteuna espressione@

'i ricorre al concetto di equi(alenza/ una funzione pu!essere rappresentata mediante una espressione che

abbia la stessa tavola di verit& ;na delle possibili espressioni si rica(a seguendo il

seguente algoritmo/D si indi(iduano le combinazioni per le quali la funzione (ale 3?D ogni combinazione fornisce un termine, formato dalla

congiunzione )operatore A.C+ di tutte le (ariabili, affermate se le(ariabili in quella combinazione assumono il (alore 3, negate seassumono il (alore 5?

D lespressione la disgiunzione )operatore B+ di tutti i termini



46/63


Capire linformatica

Calle funzioni alle espressioni logiche )J+

Espressione equi(alente del tipo sommadi prodotti)minterm+/

AB""AB"BAB"A# +++=

ABA"B"# ++=

Applicando i teoremi di base )quellodella fusione diretta+, si ottiene la forma

minima/



47/63


Capire linformatica

Esempio applicati(o/lanalisi di un circuito

Cato il circuito in figura, desumerne ilfunzionamento&



48/63


Capire linformatica

Lanalisi di un circuito )6+

'iano A, e % le (ariabili logicheassociate agli interruttori )7 3 se chiuso, 5altrimenti+&

'ia L la (ariabile associata alla lampadina)7 3 se accesa, 5 spenta+&

La ta(ola di (erit! si realizza controllando

se, per ogni combinazione delle (ariabiliindipendenti, la luce accesa o spenta&



49/63


Capire l informatica

Lanalisi di un circuito )8+

AB""BAB"A$ ++=

*onsiderando le combinazioni per cui L = ! si ottiene:



50/63



Lanalisi di un circuito )J+

Applicando i teoremi )propriet! distributi(a e"F"7"+, si minimizza lespressione/

"BAA"B"

A"BBB"AA

AB""BAAB"B"AAB""BAB"A$

+=+

=+++

=+++

=++=

)(

)()(

la luce si accende solo se chiuso linterruttore %e insieme uno dei due interruttori A o &



51/63



'intesi di un circuito

Problema/ in una stanza lilluminazione comandata da due de(iatori A e , situatiin punti di(ersi& Allinizio la luce spenta e

i due de(iatori si tro(ano in una posizioneche chiamiamo "& 'e uno dei duede(iatori, diciamo A, (iene spostato nellaposizione , (ogliamo che la luce si

accenda& 'e anche laltro de(iatore (ienespostato in posizione , (ogliamo che laluce si spenga&



52/63



'intesi di un circuito )6+

'iano A e le (ariabili logiche associate aide(iatori& A ciascuna posizione assuntada un de(iatore associamo un (alore

logico/ ad esempio associamo 5 allaposizione ", 3 alla posizione & 'ia L la (ariabile associata alla luce )7 5

se spenta, 3 se accesa+& La ta(ola di (erit! della funzione L la

seguente/



53/63



'intesi di un circuito )8+

%onsiderando le combinazioni per cui L 7 3, si halespressione/

BABABA$ =+=



54/63



'intesi di un circuito )J+

icordando che lA.C si ottiene con unaconnessione serie e lB con una connessioneparallela, si ottiene il circuito/



55/63



Esempio/ il full9adder

La somma ' di 6 numeri binari A e di n bit pu=essere ricondotta a n somme elementari di 8 bittenendo conto che/

ak, bkono i bit di peo k di A e B

k! il k"eimo bit di #

rk! il riporto generato dalla omma dei bitdi peo k"1, k"$, %%% 0 di A e B%

r"1= 0



56/63



4ull9adder/ tabelle di (erit!'i possono rica(are le tabelle di (erit!

di sNe rNin funzione di aN, bNe rN93

0 0 0 0 0

0 0 1 1 00 1 0 1 0

0 1 1 0 1

1 0 0 1 0

1 0 1 0 1

1 1 0 0 1

1 1 1 1 1

ak bkrk"1 k rk



57/63



4ull9adder/ espessioni booleane

0 0 0 0 0

0 0 1 1 0

0 1 0 1 00 1 1 0 1

1 0 0 1 0

1 0 1 0 1

1 1 0 0 1

1 1 1 1 1

ak bkrk"1 k rk

akbkrk+!

akbkrk+!

akbkrk+!

akbkrk+!

akbkrk+!

ak

bk

rk+!akbkrk+!

akbkrk+!



58/63



4ull adder/ semplificazione delle espressioni

kkkkk

kkkkkk

kkkkkkkkkkkkk

kkk

kkk

kkk

kkkkkkkkkk

kkkkkkkkkkkkk

babarbararb

rbarbarbarbar

bar

barbar

babarbabar

rbarbarbarbas

++=

=++=

=+++=

=

=+=

=+++=

=+++=

)(

)()(

)()(

!

!!

!!!!

!

!!

!!

!!!!

Le espressioni di sNe rNsono date da/



59/63



4ull adder/ schema circuitale

Le funzioni che forniscono sNed rNpossono essererealizzate in un unico circuito elettronico )full adder+/



60/63


Cap e o at ca

'ommatore a n bit

#l full9adder pu= essere usato come circuitobase per un sommatore a n bit/

an bn rn"1 a0 b0 0an"1 bn"1 rn"$

r0rn"1rn 0n"1n

carr&



61/63


p

Esercizio

Problema/'i considerino due (alori A 7 a3a5e 7 b3b5espressi in complemento a 6 su 6 bit&

'cri(ere lespressione di una funzione booleana4 che (era se e solo se A 7 9

'oluzione/

con(iene considerare i bit che costituiscono A e come (ariabili indipendenti e scri(ere lafunzione come 4 )a5,a3,b5,b3+&



62/63


p

Esercizio )6+a1 a0 b1 b0

A B F

0 0 0 0 0 0 1

0 0 0 1 0 1 0

0 0 1 0 0 -2 0

0 0 1 1 0 -1 0

0 1 0 0 1 0 0

0 1 0 1 1 1 0

0 1 1 0 1 -2 00 1 1 1 1 -1 1

1 0 0 0 -2 0 0

1 0 0 1 -2 1 0

1 0 1 0 -2 -2 0

1 0 1 1 -2 -1 0

1 1 0 0 -1 0 0

1 1 0 1 -1 1 1

1 1 1 0 -1 -2 0

1 1 1 1 -1 -1 0



63/63

p

Esercizio )8+

)(

)(

!!&&&!&!

!!!!&&&!&!

&!&!&!&!&!&!

bababbaa

babababbaa

bbaabbaabbaa%

+=

=++=

=++=

Algebra Boole Circuiti Logici

Documents

Transcript of Algebra Boole Circuiti Logici