Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf ·...

transcript

FondamentidiInformaticaAlgebradi Boole eCircuit i Logic i

Prof. Chr i st ian Espos i toCorso d i Laurea in Ingegner ia Meccanica e Gest iona le (C lasse I )A .A . 2016/17

AlgebradiBoole eCircuitiLogici

L’AlgebradiBoole – 1/4• Unpo’distoria• IlmatematicoingleseGeorgeBoole nel1847fondòuncampodellamatematicaedellafilosofiachiamatologicasimbolica

• Shannon perprimoapplicòlalogicasimbolicaaicircuitinel1939

• L’algebradiBoole ècaratterizzatada• Variabilibooleane(obinarie): variabiliicuivaloripossonoessere0oppure1• Maanche:vero/falso,on/off,si/no

• Operazioni(ofunzioni)booleane: funzioniicuiinputedoutputsonovariabilibooleane

• Relazioneconicircuitilogici• Sistudial’algebrabooleanapoichélesuefunzionisonoisomorfeaicircuitidigitali:uncircuitodigitalepuòessereespressotramiteun’espressionebooleanaeviceversa• Levariabilibooleanecorrispondonoasegnali• Lefunzionibooleanecorrispondonoacircuiti

AlgebradiBoole eCircuitiLogici 02/52

L’AlgebradiBoole – 2/4• Comevariabilicontemplasoloduecostanti:0 e1 (falso evero)• Corrispondonoaduestatichesiescludonoavicenda• Possonodescriverelostatodiaperturaochiusuradiungenericocontattoodiuncircuitoapiùcontatti

• Sullevariabilibooleanesidefinisconolefunzioni(odoperazioni)AND,OR,NOT• Edaltredefiniteapartiredaesse

L’AlgebradiBoole – 3/4• LeoperazioniAND eOR sonooperazionibinarie (agisconosudueoperandi),l’operazioneNOT èunaria

• Nellavalutazionedelleespressionibooleaneesisteunarelazionediprecedenzafraglioperatori NOT,ANDeOR,nell’ordineincuisonostatielencati

• Peralteraretalerelazionebisognausareleparentesi• Talvoltausatesolopermaggiorechiarezza

L’AlgebradiBoole – 4/4• Glioperatori dell’algebrabooleanapossonoessererappresentatiedescrittiinvarimodi• SpessosonodescrittisemplicementecomeAND,OReNOT• Tavolediverità• Nelladescrizionedeicircuitiappaionosottoformadiportelogiche

Operatore(ofunzione)OR• Sommalogica(OR): ilvaloredellasommalogicaèilsimbolo1 seilvaloredialmenounodeglioperandièilsimbolo1

• Ingenerale,daten variabilibinarie,lalorosommalogica(OR)èdatada

x1+ x2+ …+ xn =1 se almeno una xi vale 1, 𝑐𝑜𝑛1 ≤ 𝑖 ≤ 𝑛

0 se x1= x2= …= xn = 0

x1 x2 F(x1,x2)=x1+x20 0 00 1 11 0 11 1 1

Tavoladiverità

OperatoreOR:PossibiliRappresentazioni• x|y<- UsatoinMATLAB

• or(x,y)<- UsatoinMATLAB

• x#y

• xory

• x+y

• x∪ 𝒚

• x∨ 𝒚

Operatore(ofunzione)AND• Prodottologico(AND): ilvaloredelprodottologicoèilsimbolo1seilvaloredituttiglioperandièilsimbolo1

• Ingenerale,daten variabilibinarieindipendenti,illoroprodottologico(AND)èdatoda

x1´ x2´ …´ xn =0 se almeno una xi vale 0, 𝑐𝑜𝑛1 ≤ 𝑖 ≤ 𝑛

1 se x1= x2= …= xn = 1

x1 x2 F(x1,x2)=x1× x20 0 00 1 01 0 01 1 1

OperatoreAND:PossibiliRappresentazioni• x&y <- UsatoinMATLAB

• and(x,y) <- UsatoinMATLAB

• xandy

• x∧ 𝒚

• x∩ 𝒚

• x×𝒚

• x*y

• xy

Operatore(ofunzione)NOT• Operatoredinegazione(NOT): inverteilvaloredellacostantesucuiopera• Notoanchecomeinverter

• Ingenerale,lanegazionediunavariabile𝑥 è

• L’elemento�̅� =NOT(x)vienedettocomplemento dix• Ilcomplementoèunico

𝟎1 = 𝟏𝟏1 = 𝟎

𝟎4 =0𝟏4 =1

�̅� = 0 se x = 1�̅� = 1 se x = 0

OperatoreNOT:PossibiliRappresentazioni• y=~x<- UsatoinMATLAB

• y=not(x)<- UsatoinMATLAB

• y=!x

• y=not x

• y=x’

• y=¬𝒙

• y=𝒙1

AlgebradiBoole:AlcuneIdentità

Funzione AND Funzione OR Funzione NOT0 × 0 = 0 0 + 0 = 0 x+�̅� = 10 × 1 = 0 0 + 1 = 1 x×�̅� = 01 × 0 = 0 1 + 0 = 1 �̿� = 𝑥1 × 1 = 1 1 + 1 = 1x × 0 = 0 x + 0 = x0 × x = 0 0 + x = xx × 1 = x x + 1 = 11 × x = x 1 + x = 1x × x = x x + x = x

Legge dell’idempotenza

AlgebradiBoole:ProprietàeLeggi

Proprietà Commutativa Leggi di Assorbimento

Proprietà Distributiva Leggi di De Morgan

Proprietà Associativa Altre Note

𝑥1𝑥2 = 𝑥2𝑥1𝑥1 + 𝑥2 = 𝑥2 + 𝑥1

𝑥1 + 𝑥1𝑥2 = 𝑥1𝑥1(𝑥1 + 𝑥2) = 𝑥1

𝑥1 𝑥2 + 𝑥3 = 𝑥1𝑥2 + 𝑥2𝑥3𝑥1 + 𝑥2𝑥3 = 𝑥1 + 𝑥2 + (𝑥1 + 𝑥3)

𝑥1 𝑥2𝑥3 = (𝑥1𝑥2)𝑥3𝑥1 + 𝑥2 + 𝑥3 = 𝑥1 + 𝑥2 + 𝑥3

𝑥1 + 𝑥2 = 𝑥11×𝑥21𝑥1×𝑥2 = 𝑥11 + 𝑥21

𝑥1 +𝑥11 𝑥2 = 𝑥1 + 𝑥2𝑥1(𝑥11 + 𝑥2) = 𝑥1𝑥2

Leggi di De Morgan

LeggidiDeMorgan– 1/4

𝑥1 + 𝑥2 = 𝑥11×𝑥21𝑥1×𝑥2 = 𝑥11 + 𝑥21

• Ilcomplementodiunasommadivariabilièugualealprodottodeicomplimentidellevariabili• Ilcomplementodidueopiùvariabili

posteinORèugualeall’ANDdeicomplimentidellesingolevariabili

Leggi di De Morgan

LeggidiDeMorgan– 2/4

𝑥1 + 𝑥2 = 𝑥11×𝑥21𝑥1×𝑥2 = 𝑥11 + 𝑥21

• Ilcomplementodiunprodottodivariabilièugualeallasommadeicomplimentidellevariabili• Ilcomplementodidueopiùvariabili

posteinANDèequivalenteall’ORdeicomplimentidellesingolevariabili

LeggidiDeMorgan– 3/4• Osservazione: �̿� = 𝑥(Eq. 1)• Legge1diDeMorgan: 𝑥1 + 𝑥2 = 𝑥11×𝑥21 (Eq.2)

• Utilizzando(Eq.1) possoscrivere(Eq.2) comesegue:𝑥1 + 𝑥2 = 𝑥11×𝑥21• Utilizzandoancora(Eq.1) ottengoche𝑥1 + 𝑥2 = 𝑥11×𝑥21• L’ORfrax1 ex2 puòessereespressointerminidellesoleoperazioniANDeNOT• Ognivoltacheinun’espressionebooleanatroviamounOR,lopossiamosostituireconlaappropriatacombinazionediANDeNOT• OgniespressionepuòessereespressainterminidellesoledueoperazionilogicheANDeNOT

LeggidiDeMorgan– 4/4• Osservazione: �̿� = 𝑥(Eq. 1)• Legge2diDeMorgan: 𝑥1×𝑥2 = 𝑥11 +𝑥21 (Eq.3)

• Utilizzando(Eq.1) possoscrivere(Eq.3) comesegue:𝑥1×𝑥2 = 𝑥11 +𝑥21• Utilizzandoancora(Eq.1) ottengoche𝑥1×𝑥2 = 𝑥11 +𝑥21• L’ANDfrax1 ex2 puòessereespressointerminidellesoleoperazioniOReNOT• Ognivoltacheinun’espressionebooleanatroviamounAND,lopossiamosostituireconlaappropriatacombinazionediOReNOT• OgniespressionepuòessereespressainterminidellesoledueoperazionilogicheOReNOT

AlcuneOsservazioni• Identità,proprietàeleggivistefinoadorasonogeneralmenteapplicatenelletrasformazionidifunzionibooleaneinaltreequivalenti,madipiùfacilerealizzazionecircuitale

• DalleleggidiDeMorgansievincechelasceltadellefunzioniOR,ANDeNOT,comefunzioniprimitive,èridondante

FunzioniLogiche(oBooleane)– 1/5• Daten variabilibooleaneindipendentix1,x2,…,xn,questepossonoassumere2n configurazionidistinte• Adesempiopern =3 sihanno8configurazioni

• Ogniriga(inrosso)mostrailvalorerestituitoapartiredaunaparticolareconfigurazionedell’input• UnaconfigurazionespecificaèindividuataunivocamentedaunANDdituttelevariabili,dovequellecorrispondentiaivalori0compaiononegate• Prodottofondamentaleoprodottominimo(minterm)

x1 x2 x3 F(x1,x2,x3)

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

x1x2x3010

FunzioniLogiche(oBooleane)– 2/5

x1 x2 x3 F(x1,x2,x3)

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

𝑥11 𝑥21 𝑥31𝑥11 𝑥21 𝑥3𝑥11 𝑥2𝑥31𝑥11 𝑥2𝑥3𝑥1𝑥21 𝑥31𝑥1𝑥21 𝑥3𝑥1𝑥2𝑥31𝑥1𝑥2𝑥3

Configurazioni

• 011indicatrale23=8configurazionipossibili,quellaincui𝑥1 vale0,𝑥2vale1e𝑥3 vale1

• Questaconfigurazionesiscrivesemplicementeconilprodotto𝑥11 𝑥2𝑥3

• Seinunaconfigurazioneunavariabilecomparecon1,siassumeilvalorediretto,seinvececompareconuno0,siassumeilvalorenegato

FunzioniLogiche(oBooleane)– 3/5• Unavariabileyèfunzione dellen variabiliindipendentix1,x2,…,xn,quandoesisteuncriteriochefacorrispondereinmodounivocoadognunadelle2n configurazionidix undeterminatovalorey (ovviamente0o1)

• Unarappresentazioneesplicitadiunafunzioneèlatavoladiverità,incuisielencanotuttelepossibilicombinazionidix1, x2,…,xn, conassociatoilvalorediy

y=F(x1,x2,…,xn)

x1 x2 y0 0 00 1 11 0 11 1 1

y = x1+ x2

FunzioniLogiche(oBooleane)– 4/5• Sipuòspecificarel’outputdiognifunzionebooleanaesprimendo,tramiteun’espressionebooleana,qualicombinazionidellevariabilidiinputdeterminanol’output1

x1 x2 x3 F(x1,x2,x3)

0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 1

• Piùprecisamente,perpassaredallarappresentazionemediantetavoladiveritàallanotazionetramiteespressionebooleanaènecessario1. Identificaretuttelerighedellatavoladiverità

chedanno1inoutput2. Perognirigaconun1inoutput,scriverela

configurazionedellevariabilicheladefiniscono

3. CollegaretramiteORtutteleconfigurazioniottenute

𝑥11 𝑥2𝑥3 +𝑥1𝑥21 𝑥3 + 𝑥1𝑥2𝑥31 +𝑥1𝑥2𝑥3

FunzioniLogiche(oBooleane)– 5/5• 𝐹 𝑥1, 𝑥2, 𝑥3 = 𝑥11 𝑥2𝑥3 + 𝑥1𝑥21 𝑥3 + 𝑥1𝑥2𝑥31 + 𝑥1𝑥2𝑥3

x1 x2 x3 F(x1,x2,x3)

0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 1

• Conl’usodeiminterm possiamodeterminarel’espressionealgebricadiunafunzionebooleanaapartiredallatavoladiverità

• L’espressionealgebricatrovatasichiamaformacanonica dellafunzioneesiottieneconunosviluppoinminterm• Unasomma(OR)diprodotti(AND)

• Seunminterm assumevalore1anchelafunzioneF assumeilvalore1

Esempio1:laFunzioneExclusive OR(XOR)– 1/2• Ilcomportamento dellafunzioneExclusive OR puòesseredescrittocomesegue• F =“L’outputdeveessere1(vero)sesolounodeisuoiinputè1,manonseentrambigliinputsono1”

• Questopuòessererifrasato comesegue• F =“L’outputè1se(x1 ORx2)è1,ANDse(x1 ANDx2)sonoNOT1(falso)”

• Chepuòesserescrittocome• 𝑭 = 𝒙𝟏 + 𝒙𝟐 ×(𝒙𝟏𝒙𝟐)

Esempio1:laFunzioneExclusive OR(XOR)– 2/2• LafunzioneXORverificaladisuguaglianzadiduevariabili

• L’espressionecomesommadiprodottièquindi

x1 x2 XOR0 0 00 1 11 0 11 1 0

XOR(x1,x2) = 𝑥11 ×𝑥2 + 𝑥1×𝑥21

Si può scrivere la funzione come somma logica (OR) delle configurazioni corrispondenti agli 1

Forma canonica: somma di prodotti (OR di AND)N.B. tutte le funzioni logiche si possono scrivere in questa forma

Esempio2:dallaTavoladiVeritàallaFunzionex y z F0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 0

𝐹 𝑥, 𝑦, 𝑧 = �̅�yz + x𝑦L𝑧 + 𝑥𝑦𝑧̅Forma canonica: somma di prodotti (OR di AND)N.B. tutte le funzioni logiche si possono scrivere in questa forma

• Problema: datetrevariabilibooleane(𝑥, 𝑦, 𝑧),siscrivalafunzioneF chevale1quandosoloduediessehannovalore1

Esempio3:dallaTavoladiVeritàallaFunzionex y z F0 0 0 00 0 1 10 1 0 10 1 1 01 0 0 11 0 1 01 1 0 01 1 1 1

𝐹 𝑥, 𝑦, 𝑧 = �̅�𝑦Lz + �̅�𝑦𝑧̅ + 𝑥𝑦L𝑧̅ + xyzForma canonica: somma di prodotti (OR di AND)N.B. tutte le funzioni logiche si possono scrivere in questa forma

• Problema: datetrevariabilibooleane(𝑥, 𝑦, 𝑧),siscrivalafunzioneF chevale1quandoilnumerodi1èdispari

Esempio4:dallaFunzioneallaTavoladiVerità• Vediamounesempioperlafunzione• 𝐹 = 𝑥×(𝑦 + 𝑧)

x y z F

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 0

1 0 0 1

1 0 1 0

1 1 0 0

1 1 1 0

CircuitoLogico

• Ilcuore diunsistemadigitale èilcircuitologico digitale• Progettatoapartiredaportelogiche• Collegatetraloroperformarecircuitipiùgrandi• Combinatiperrealizzarecircuitidigrandeimportanzapraticanell’architetturadelcomputer

CS126 11-4 Randy Wang

Digital Logic Circuits

•The heart of a digital system is usually a digital logiccircuit

Circuit

Outputs

PorteLogiche• Buildingblock utilizzatipercrearecircuitidigitali

• Qualsiasicircuitopuòessereimplementatousandosoloportelogicheelementari(AND,OReNOT)• Lecosesifannocomplicatequandosihannonumerosiinputedoutput

• Dispositivielettronicicheimplementanosemplicifunzionibooleane

• Ciascunaportahailpropriosimbolologicochepermetteafunzionicomplessediessererappresentatemedianteundiagrammalogico

• Lafunzionediciascunaportapuòessererappresentatadaunatabelladiveritàoutilizzandolanotazionebooleana

FunzioneOR:TavoladiVeritàePortaLogica

x1 x2 x1 ORx20 0 00 1 11 0 11 1 1

An OR-Gate and a NOT-Gate

1 0CS126 11-7 Randy Wang

FunzioneAND:TavoladiVeritàePortaLogica

x1 x2 x1 ANDx20 0 00 1 01 0 01 1 1

An AND-Gate

•A smallest useful circuit is a logic gate•We will connect these small gates into larger circuits

00 0 0

10 0 1

FunzioneNOT:TavoladiVeritàePortaLogica

x NOTx0 11 1

PortaNAND

PortaNOR

PortaXOR

PortaExclusive NOR

Esempio5:dallaFunzionealCircuito

CBAX +=

C= (𝐴 + 𝐵) O (𝐴𝐵)

PortaNAND

CBACBACBAX ++=

DCBAY +=

PortaNOR

Esempio9:dalCircuitoallaFunzione– 1/2

Esempio9:dalCircuitoallaFunzione– 2/2• Procedereprogressivamentedagliinputversol’outputaggiungendoaturnoleespressionilogicheall’outputdiciascunaportalogica

Esempio10:Funzione=>TavoladiVerità=>Circuito• Siconsiderilaseguentefunzione:A(B + C)

Ricapitolando…• Abbiamovistocheunafunzionelogica (maancheuncircuitologico)puòessereespressainduemodi• TavoladiVerità• PorteLogiche

• Perchéabbiamobisognodituttequestediverserappresentazioni?• Alcunesonopiùfacilidialtrepercominciareaprogettareuncircuito• Disolitosicominciaconlatavoladiverità• Siderivaun’espressionebooleanadaessa(magariesemplificata)• Sitrasformal’espressionebooleanainuncircuito

Esercizio1:determinarelafunzioneespressadallaseguentetavoladiverità

A B C X0 0 0 00 0 1 10 1 0 00 1 1 01 0 0 01 0 1 11 1 0 11 1 1 0

Esercizio2:trovarel’outputdelseguentecircuito(tavoladiveritàefunzione)

Esercizio6:progettareilcircuitoperciascunadelleseguentiespressioni• �̅� + 𝑦

•(𝑥 + 𝑦)𝑥

• ScriverelafunzioneXORusandoAND,OReNOT

Riferimenti• Libroditesto• Capitolo3• Paragrafo4

• Altririferimenti• http://www.di.unito.it/~piccolo/teach/AA1516/Lezioni/Lezione2.pdf• http://liceocuneo.it/basteris/wp-content/uploads/sites/3/CIRCUITI20DIGITALI1.pdf• http://bias.csr.unibo.it/maltoni/arc/Dispense/LogicaDigitale.pdf• http://people.unipmn.it/bobbio/DIDATTICA/ARCH1_00/ALDISP_00/varbol00.pdf

Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf ·...

Documents