A hie adeg

4 - Reti Combinatorie e Algebra di Boole

Ugo DalLago

DipartimentodiS ienzedell'Informazione

UniversitàdegliStudidiBologna

Anno A ademi o2007/2008

◮

Il i lo dilezioni heandiamo adiniziareriguardaillivello

logi o-digitale.

◮

Comeabbiamo giàdetto inpre edenza, in questo livelloi

programmisono ostitutitida ir uitidigitali(o reti

logi he),i ui omponentifondamentali sonodettiporte

logi he.

◮

Esistonodue lassi di retilogi he:

◮

Lereti ombinatorie, henonhannounostatointernoe he

verrannostudiateinquesta partedel orso. Esempio: ALU.

◮

Leretisequenziali, hehannounostatointernoe he

verrannostudiatenellaprossimapartedel orso. Esempio:

registri.

◮

Il livellologi o-digitalesta alla basedellegerar hiadi ma hine virtuali he abbiamointrodottoall'inizio del orso.

◮

I ir uitisonoentità on rete etangibili,per uinonvanno

tradottiointerpretati.

◮

D'altraparte,ilfunzionamentointernodelleportelogi hesi

può omprenderesoloadunlivelloinferiore,dettolivellodei

◮

Un ir uitodigitaleè un'inter onnessione diportelogi he.

◮

Neili heinter onnettono le portelogi hein un ir uitosono

presenti solo duevalorilogi i:

◮

Ilvalore0,rappresentatodaunsegnale ompresotra0e1

volt.

◮

Ilvalore1,rappresentatodaunsegnale ompresotra3e5

volt.

◮

Esistonoalmeno inque tipidiversidiportelogi he: NOT,

NAND, NOR,AND, OR.

◮

Ogni porta logi a haunoo piùingressie un'us ita.

◮

Ogni ir uitoha unoo piùingressie una opiùus ite.

◮

Gliingressidi un ir uitopossono essere onnessi:

◮

Adunodegliingressidiunaportalogi a.

◮

Adunadelleus itedel ir uito.

◮

Inun ir uito,l'us itadiuna portalogi apuòessere onnessa:

◮

Adunodegliingressidiun'altraportalogi a.

◮

Porte Logi he

Cir uito diEsempio

◮

Lereti ombinatoriesono ir uitidigitali henon ontengono i li.

◮

Inaltreparole,nonpossonoesistere ammini i li iall'interno

del ir uito.

◮

Un input peril ir uito onsistein una sequenza divalori

binari,uno per ogniingresso del ir uito.

◮

Un outputperun ir uito onsistein una sequenza di valori

binari,uno per ognius ita del ir uito.

◮

L'output di unarete ombinatoriain orrispondenza adun

erto inputsipuò al olare ome segue:

◮

Perogniportalogi a,sesononotiivaloribinariin

orrispondenzadeisuoiingressi,allorasarànotoan heilvalore

binarioin orrispondenzadellasuaus ita.

◮

Leregole hepermettonodi determinare,perogniporta

logi a,qualesiailvaloredellasuaus itain orrispondenzadi

ias unvaloreperle entratedipendonosolodaltipodiporta.

◮

Si puòsupporre, aquestopunto, he iltempo ne essario alla

(b) A NAND

B

X

A B X 0 0 1 0 1 1 1 0 1 1 1 0

(c) A NOR

B

X

A B X 0 0 1 0 1 0 1 0 0 1 1 0

A AND

B

X

(d) A B X 0 0 0 0 1 0 1 0 0 1 1 1

A OR

B

X

(e) A B X

0 0 0

0 1 1

1 0 1

1 1 1

(a) NOT

A

A X

X

0 1

1 0

◮

Idettaglisulfunzionamento internodelleportelogi he

esulano daglis opidi questo orso.

◮

Una pi ola digressionerisultaperòutile,a questopunto.

◮

Il transistor è undispositivoelettroni o hepuòfunzionare

ome unvelo issimointerruttorebinario.

◮

Itransistorhannotre onnessioniversoilmondo esterno: il

ollettore,labasee l'emettitore.

◮

Quando latensionesulla bases ende sotto ilvalore riti o,il

transistorsi omporta ome una resistenza innita.

◮

Quando latensionesuperaunvalore riti o,il transistorsi

omporta omeun onduttore ideale.

◮

Inquesto modoè fa ilmente realizzabileuna porta NOT.Due

transistorsonoinve e su ientia ostruire una porta NAND

oppure una porta NOR.

◮

Esistonoduete nologie prin ipalinella ostruzione delleporte

logi he:

◮

Late nologiabipolare(TTL,ECL,...).

◮

Collector

Base +V _CC

V out

V _in

Emitter

(a)

V _out +V _CC

+V _CC

V _out

V ₂

(b) V ₁

V ₁

(c)

V ₂

◮

Studieremol'Algebra di Boole per hé quest'ultimarappresenta

unutile strumentoperl'analisie lasintesidellereti

ombinatoriee sequenziali.

◮

Le Algebre di Boolesonostrutture algebri he hesoddisfano

al uneproprietà.

◮

LostudiodelleAlgebrediBooleingeneraleri hiederebbe

troppotempo.

◮

Anoi interessauna parti olare Algebra di Boole, he onsiste

nell'insiemeB

= {

⁰

,

¹

}

^{e in treoperazionisuquestoinsieme:}

◮

L'operazionebinariadi addizione,indi ata on

+

^{oppure on}

OR.Valgonoleseguentiidentità: 0

+

⁰

=

^0,0

+

¹

=

^1,

1

+

⁰

=

^1e1

+

¹

=

^1.

◮

L'operazionebinariadi moltipli azione,indi ata on

·

^{, on}

ANDoppure tramitelasempli egiustapposizionedegli

operandi. Valgonoleseguentiidentità: 0

·

⁰

=

^0,0

·

¹

=

^0,

1

·

⁰

=

^0e1

·

¹

=

^1.

◮

L'operazioneunariadinegazione,indi ata onilsimbolo

NOToppure onunalineasoprailrelativooperando. Valgono

leseguentiidentità: 0

=

^1e1

=

^0.

Elementoneutro 1A

=

^{A 0}

+

^A

=

^A

Assorbimento 0A

=

^{0 1}

+

^A

=

¹

Idempotenza AA

=

^{A A}

+

^A

=

^A

Complementazione AA

=

^{0 A}

+

^A

=

¹

Commutativa AB

=

^{BA A}

+

^B

=

^B

+

^A

Asso iativa

(

^AB

)

^C

= (

^A

+

^B

) +

^C

=

A

(

^BC

)

^A

+ (

^B

+

^C

)

Distributiva A

+

^BC

=

^A

(

^B

+

^C

) =

(

^A

+

^B

)(

^A

+

^C

)

^AB

+

^AC

Assorbimento A

(

^A

+

^B

) =

^{A A}

+

^AB

=

^A

De Morgan AB

=

^A

+

^{B A}

+

^B

=

^AB

Doppia Negazione A

=

^A

◮

Le variabili booleanesono X

,

^Y

,

^Z

,

^A

,

^B

,

^C

, . . .

^{. Sisuppone}

hele variabili booleane prendano unvalore inB.

◮

Abbiamoappenautilizzatolevariabilibooleaneneldarele

proprietàdell'AlgebradiBoole, hevalgonoqualunquesiail

valoresostituitoaA,B oC.

◮

Apartire dalle ostanti 0e 1 edalle variabili booleane, possiamo ostruireespressioni booleaneutilizzandole

operazionidi addizione, moltipli azionee negazione.

◮

Esempidi espressionibooleanesonoA

+

^BC,A

+

^B

+

^C

+

^C,

et .

◮

Una voltaassegnato unvalore diveritàin B adognuna delle

variabiliin unespressione booleana,è possibilevalutare

l'espressionein orrispondenzadi taleassegnamento.

◮

Il valoredi un'espressionein orrispondenzadi tuttii possibili

assegnamenti èriassunto nellasua tabella diverità.

◮

Due espressionibooleane( ontenenti lestesse variabili

booleane)sidi ono equivalenti quandoilvaloredelle

AB

+

^AC

A B C AB AC AB

+

^AC

0 0 0 0 0 0

0 0 1 0 0 0

0 1 0 0 0 0

0 1 1 0 0 0

1 0 0 0 0 0

1 0 1 0 1 1

1 1 0 1 0 1

1 1 1 1 1 1

A

(

^B

+

^C

)

A B C B

+

^{C A}

(

^B

+

^C

)

0 0 0 0 0

0 0 1 1 0

0 1 0 1 0

0 1 1 1 0

1 0 0 0 0

1 0 1 1 1

1 1 0 1 1

1 1 1 1 1

◮

Un modomolto sempli epertrasformareun'espressione

booleanain un'altraespressioneespressionead essa

equivalente onsiste nell'impiegodelleproprietà algebri he

dell'algebra booleana.

◮

Sesidimostra heesisteuna atenadiuguaglianze(indotte

dalleproprietàdell'algebrabooleana) hepermettonodi

ris rivereun'espressioneinun'altra,alloraledueespressioni

sonoequivalenti.

◮

Inquesto modoè possibile,in parti olare,sempli are

un'espressionebooleana datain un'espressione piùsempli e

(ma equivalente).

◮

Esempi:

AB

+

^AC

=

^A

(

^B

+

^C

)

ABC

+

^ABC

+

^AC

=

^AB

(

^C

+

^C

) +

^AC

=

^AB

·

¹

+

^AC

=

^AB

+

^AC

◮

Daten variabili booleane A

1

, . . . ,

^An

,una funzione booleana

asso iaunassegnamento di veritàperuna variabileC ad ogni

assegnamento diverità allevariabili A

1

, . . . ,

^An .

◮

Un modoespli itoperdenire una funzione booleana onsiste

nel darelasua tavoladi verità, he elen heràilvalore diC per

ogni possibilevaloredi veritàper A

1

, . . . ,

^An .

◮

Esempio:

A B C F

0 0 0 0

0 0 1 0

0 1 0 1

0 1 1 0

1 0 0 0

1 0 1 0

1 1 0 1

1 1 1 1

◮

Data una funzionebooleana,ilsuo omplementoèdenito

ome lafunzione booleana (sullestessevariabili) hevale 0

quando lafunzione dipartenzavale 1 e,vi eversa, vale1

◮

Adogni espressione booleana E puòessereasso iata una

funzione booleana F, he siindi a spesso on

F

=

^E

◮

Il valoredellafunzione F suunassegnamento diveritàalle

variabilibooleane inE sarà sempli ementeilvalore diE in

orrispondenza ditale assegnamento.

◮

Esempi:

F

=

^A

+

^BC

F

=

^A

(

^B

+

^C

) +

^AB

◮

Ingenerale, espressionibooleane diverse possono orrisponderealla stessa funzionebooleana.

◮

Adesempio,letabelladiveritàdiF

=

^AB

+

^{AC edi}

F

=

^A

(

^B

+

^C

)

^sonouguali.

◮

Piùingenerale,tutteleespressioniequivalenti orrispondono

◮

Un letteraleè una variabilebooleana oppurelanegazione di

una variabilebooleana.

◮

Data una funzionebooleana,sipuò sempre ostruireuna

espressione booleana orrispondente (trale tante possibili).

◮

Inparti olare, sipuòpro edere onsiderandoogni rigadella

tabelladiverità relativaalla funzione dipartenza.

◮

Si asso iaadogni riga ilprodotto di letteraliad essa

orrispondente.

◮

L'espressione he er hiamo sarà una somma diprodotti di

letterali. Se lafunzionevale 1 inuna ertariga, allorail

orrispondente prodotto diletterali farà parte dellasomma.

Vi eversa,se lafunzione vale 0in una ertariga,allora il

orrispondenteprodotto diletteralinonfaràpartedellasomma.

◮

Inquesto modosipossono ottenereespressionibooleane molto

omplesse...

◮

... hepossonoperòesseresempli atetramite l'usodelle

◮

Consideriamolafunzione booleana introdotta inpre edenza.

◮

In orrispondenza di ogni rigadella tabelladi verità,s riviamo ilprodotto di letterali:

A B C F

0 0 0 0 ABC

0 0 1 0 ABC

0 1 0 1 ABC

0 1 1 0 ABC

1 0 0 0 ABC

1 0 1 0 ABC

1 1 0 1 ABC

1 1 1 1 ABC

◮

Le righein ui F vale1 sonolaterza, lapenultima e l'ultima.

Possiamo quindi on ludere hel'espressionebooleana he i

interessaè

ABC

+

^ABC

+

^ABC

◮

Utilizzando leproprietà dell'algebra booleana otteniamo:

F

=

^ABC

+

^ABC

+

^ABC

=

^ABC

+

^AB

=

^B

(

^AC

+

^A

)

◮

Adogni us ita di ognirete ombinatoria orrisponde una

funzione booleana.

◮

Primadituttoasso iamonvariabilibooleaneA

1

, . . . ,

^An aglin

ingressieunavariabile C all'us ita he iinteressa

◮

Perogniassegnamentodivaloridi veritàallevariabilibooleane

A

1

, . . . ,

^An

,il orrispondentevalorediC saràquelloottenuto

valutandoil ir uito.

◮

Inquestomodo,sipossonoasso iarefunzionibooleaneadogni

us itadel ir uito. Diremo heil ir uitoinquestione

implementatalifunzionibooleane.

◮

Due ir uitisi di onoequivalenti se implementanolastessa

funzione.

◮

Una volta ostruita una funzione,sipotrà poiri avare

un'espressionebooleana

⇒

A B C D

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 0

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

⇓

ABC

+

^ABC

+

^ABC

◮

Adogni sequenza di espressionibooleane sullestesse variabili orripondeun ir uito.

◮

Dataun'espressionebooleanaE ontenentelevariabili

booleaneA

1

, . . . ,

^An

,un ir uito onnentrateeun'us itasi

può ostruireseguendolastrutturadiE.

◮

Lafunzioneimplementatadal ir uitosaràlafunzione

orrispondenteadE.

◮

Partendodaunasequenzadiespressioni,sipotrà ostruire un

singolo ir uito onpiùus ite.

◮

Perottenere le espressionibooleane di partenza, si può pro edereappli ando adaltrettante funzionibooleane la

pro edura vista inpre edenza.

◮

Inquestomodo, sipuòpassaredanfunzionibooleanesu m

variabiliadun ir uito onmingressiednus ite.

A B C 0 0 0 0 0 1 0 1 0 0 1 1

M 0 0 0 1 1 0 0 1 0 1 1 1 0 1 1 1

0 1 1 1

(a) (b)

ABC A

A

B

C

B C A

A

B C

ABC

ABC

ABC

M 1

4

8 5

6

7 B

2

C 3

⇓ ⇑

ABC

+

^ABC

+

^ABC

+

^ABC