algebra di boolee circuiti logici - intranet ...cesposito/materiale/lezioni/lezione_3.pdf ·...
TRANSCRIPT
![Page 1: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/1.jpg)
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
![Page 2: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/2.jpg)
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
![Page 3: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/3.jpg)
L’AlgebradiBoole – 2/4• Comevariabilicontemplasoloduecostanti:0 e1 (falso evero)• Corrispondonoaduestatichesiescludonoavicenda• Possonodescriverelostatodiaperturaochiusuradiungenericocontattoodiuncircuitoapiùcontatti
• Sullevariabilibooleanesidefinisconolefunzioni(odoperazioni)AND,OR,NOT• Edaltredefiniteapartiredaesse
0 1
AlgebradiBoole eCircuitiLogici 03/52
![Page 4: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/4.jpg)
L’AlgebradiBoole – 3/4• LeoperazioniAND eOR sonooperazionibinarie (agisconosudueoperandi),l’operazioneNOT èunaria
• Nellavalutazionedelleespressionibooleaneesisteunarelazionediprecedenzafraglioperatori NOT,ANDeOR,nell’ordineincuisonostatielencati
• Peralteraretalerelazionebisognausareleparentesi• Talvoltausatesolopermaggiorechiarezza
AlgebradiBoole eCircuitiLogici 04/52
![Page 5: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/5.jpg)
L’AlgebradiBoole – 4/4• Glioperatori dell’algebrabooleanapossonoessererappresentatiedescrittiinvarimodi• SpessosonodescrittisemplicementecomeAND,OReNOT• Tavolediverità• Nelladescrizionedeicircuitiappaionosottoformadiportelogiche
AlgebradiBoole eCircuitiLogici 05/52
![Page 6: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/6.jpg)
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à
AlgebradiBoole eCircuitiLogici 06/52
![Page 7: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/7.jpg)
OperatoreOR:PossibiliRappresentazioni• x|y<- UsatoinMATLAB
• or(x,y)<- UsatoinMATLAB
• x#y
• xory
• x+y
• x∪ 𝒚
• x∨ 𝒚
AlgebradiBoole eCircuitiLogici 07/52
![Page 8: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/8.jpg)
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
AlgebradiBoole eCircuitiLogici 08/52
![Page 9: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/9.jpg)
OperatoreAND:PossibiliRappresentazioni• x&y <- UsatoinMATLAB
• and(x,y) <- UsatoinMATLAB
• xandy
• x∧ 𝒚
• x∩ 𝒚
• x×𝒚
• x*y
• xy
AlgebradiBoole eCircuitiLogici 09/52
![Page 10: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/10.jpg)
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
AlgebradiBoole eCircuitiLogici 10/52
![Page 11: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/11.jpg)
OperatoreNOT:PossibiliRappresentazioni• y=~x<- UsatoinMATLAB
• y=not(x)<- UsatoinMATLAB
• y=!x
• y=not x
• y=x’
• y=¬𝒙
• y=𝒙1
AlgebradiBoole eCircuitiLogici 11/52
![Page 12: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/12.jpg)
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 eCircuitiLogici 12/52
![Page 13: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/13.jpg)
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
AlgebradiBoole eCircuitiLogici 13/52
![Page 14: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/14.jpg)
Leggi di De Morgan
LeggidiDeMorgan– 1/4
𝑥1 + 𝑥2 = 𝑥11×𝑥21𝑥1×𝑥2 = 𝑥11 + 𝑥21
• Ilcomplementodiunasommadivariabilièugualealprodottodeicomplimentidellevariabili• Ilcomplementodidueopiùvariabili
posteinORèugualeall’ANDdeicomplimentidellesingolevariabili
AlgebradiBoole eCircuitiLogici 14/52
![Page 15: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/15.jpg)
Leggi di De Morgan
LeggidiDeMorgan– 2/4
𝑥1 + 𝑥2 = 𝑥11×𝑥21𝑥1×𝑥2 = 𝑥11 + 𝑥21
• Ilcomplementodiunprodottodivariabilièugualeallasommadeicomplimentidellevariabili• Ilcomplementodidueopiùvariabili
posteinANDèequivalenteall’ORdeicomplimentidellesingolevariabili
AlgebradiBoole eCircuitiLogici 15/52
![Page 16: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/16.jpg)
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
AlgebradiBoole eCircuitiLogici 16/52
![Page 17: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/17.jpg)
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
AlgebradiBoole eCircuitiLogici 17/52
![Page 18: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/18.jpg)
AlcuneOsservazioni• Identità,proprietàeleggivistefinoadorasonogeneralmenteapplicatenelletrasformazionidifunzionibooleaneinaltreequivalenti,madipiùfacilerealizzazionecircuitale
• DalleleggidiDeMorgansievincechelasceltadellefunzioniOR,ANDeNOT,comefunzioniprimitive,èridondante
AlgebradiBoole eCircuitiLogici 18/52
![Page 19: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/19.jpg)
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
AlgebradiBoole eCircuitiLogici 19/52
![Page 20: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/20.jpg)
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
AlgebradiBoole eCircuitiLogici 20/52
![Page 21: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/21.jpg)
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
AlgebradiBoole eCircuitiLogici 21/52
![Page 22: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/22.jpg)
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
AlgebradiBoole eCircuitiLogici 22/52
![Page 23: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/23.jpg)
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
AlgebradiBoole eCircuitiLogici 23/52
![Page 24: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/24.jpg)
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• 𝑭 = 𝒙𝟏 + 𝒙𝟐 ×(𝒙𝟏𝒙𝟐)
AlgebradiBoole eCircuitiLogici 24/52
![Page 25: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/25.jpg)
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
AlgebradiBoole eCircuitiLogici 25/52
![Page 26: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/26.jpg)
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
Si può scrivere la funzione come somma logica (OR) delle configurazioni corrispondenti agli 1
AlgebradiBoole eCircuitiLogici 26/52
![Page 27: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/27.jpg)
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
Si può scrivere la funzione come somma logica (OR) delle configurazioni corrispondenti agli 1
AlgebradiBoole eCircuitiLogici 27/52
![Page 28: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/28.jpg)
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
AlgebradiBoole eCircuitiLogici 28/52
![Page 29: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/29.jpg)
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
x1x2
xm
Inpu
ts
z1z2
zn
Outputs
AlgebradiBoole eCircuitiLogici 29/52
![Page 30: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/30.jpg)
PorteLogiche• Buildingblock utilizzatipercrearecircuitidigitali
• Qualsiasicircuitopuòessereimplementatousandosoloportelogicheelementari(AND,OReNOT)• Lecosesifannocomplicatequandosihannonumerosiinputedoutput
• Dispositivielettronicicheimplementanosemplicifunzionibooleane
• Ciascunaportahailpropriosimbolologicochepermetteafunzionicomplessediessererappresentatemedianteundiagrammalogico
• Lafunzionediciascunaportapuòessererappresentatadaunatabelladiveritàoutilizzandolanotazionebooleana
AlgebradiBoole eCircuitiLogici 30/52
![Page 31: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/31.jpg)
FunzioneOR:TavoladiVeritàePortaLogica
x1 x2 x1 ORx20 0 00 1 11 0 11 1 1
CS126 11-7 Randy Wang
An OR-Gate and a NOT-Gate
00 0
01 1
10 1
11 1
0 1
1 0CS126 11-7 Randy Wang
An OR-Gate and a NOT-Gate
00 0
01 1
10 1
11 1
0 1
1 0
AlgebradiBoole eCircuitiLogici 31/52
![Page 32: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/32.jpg)
FunzioneAND:TavoladiVeritàePortaLogica
x1 x2 x1 ANDx20 0 00 1 01 0 01 1 1
CS126 11-6 Randy Wang
An AND-Gate
•A smallest useful circuit is a logic gate•We will connect these small gates into larger circuits
00 0 0
1 0
10 0 1
1 1
AlgebradiBoole eCircuitiLogici 32/52
![Page 33: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/33.jpg)
FunzioneNOT:TavoladiVeritàePortaLogica
x NOTx0 11 1
CS126 11-7 Randy Wang
An OR-Gate and a NOT-Gate
00 0
01 1
10 1
11 1
0 1
1 0
AlgebradiBoole eCircuitiLogici 33/52
![Page 34: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/34.jpg)
PortaNAND
AlgebradiBoole eCircuitiLogici 34/52
![Page 35: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/35.jpg)
PortaNOR
AlgebradiBoole eCircuitiLogici 35/52
![Page 36: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/36.jpg)
PortaXOR
AlgebradiBoole eCircuitiLogici 36/52
![Page 37: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/37.jpg)
PortaExclusive NOR
AlgebradiBoole eCircuitiLogici 37/52
![Page 38: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/38.jpg)
Esempio5:dallaFunzionealCircuito
CBAX +=
AlgebradiBoole eCircuitiLogici 38/52
![Page 39: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/39.jpg)
Esempio6:dallaFunzionealCircuito
C= (𝐴 + 𝐵) O (𝐴𝐵)
PortaNAND
AlgebradiBoole eCircuitiLogici 39/52
![Page 40: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/40.jpg)
Esempio7:dallaFunzionealCircuito
CBACBACBAX ++=
AlgebradiBoole eCircuitiLogici 40/52
![Page 41: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/41.jpg)
Esempio8:dallaFunzionealCircuito
DCBAY +=
PortaNOR
AlgebradiBoole eCircuitiLogici 41/52
![Page 42: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/42.jpg)
Esempio9:dalCircuitoallaFunzione– 1/2
AlgebradiBoole eCircuitiLogici 42/52
![Page 43: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/43.jpg)
Esempio9:dalCircuitoallaFunzione– 2/2• Procedereprogressivamentedagliinputversol’outputaggiungendoaturnoleespressionilogicheall’outputdiciascunaportalogica
AlgebradiBoole eCircuitiLogici 43/52
![Page 44: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/44.jpg)
Esempio10:Funzione=>TavoladiVerità=>Circuito• Siconsiderilaseguentefunzione:A(B + C)
AlgebradiBoole eCircuitiLogici 44/52
![Page 45: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/45.jpg)
Ricapitolando…• Abbiamovistocheunafunzionelogica (maancheuncircuitologico)puòessereespressainduemodi• TavoladiVerità• PorteLogiche
• Perchéabbiamobisognodituttequestediverserappresentazioni?• Alcunesonopiùfacilidialtrepercominciareaprogettareuncircuito• Disolitosicominciaconlatavoladiverità• Siderivaun’espressionebooleanadaessa(magariesemplificata)• Sitrasformal’espressionebooleanainuncircuito
AlgebradiBoole eCircuitiLogici 45/52
![Page 46: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/46.jpg)
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
AlgebradiBoole eCircuitiLogici 46/52
![Page 47: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/47.jpg)
Esercizio2:trovarel’outputdelseguentecircuito(tavoladiveritàefunzione)
xyxyy
AlgebradiBoole eCircuitiLogici 47/52
![Page 48: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/48.jpg)
Esercizio3:trovarel’outputdelseguentecircuito(tavoladiveritàefunzione)
x
y
AlgebradiBoole eCircuitiLogici 48/52
![Page 49: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/49.jpg)
Esercizio4:trovarel’outputdelseguentecircuito(tavoladiveritàefunzione)
AlgebradiBoole eCircuitiLogici 49/52
![Page 50: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/50.jpg)
Esercizio5:trovarel’outputdelseguentecircuito(tavoladiveritàefunzione)
AlgebradiBoole eCircuitiLogici 50/52
![Page 51: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/51.jpg)
Esercizio6:progettareilcircuitoperciascunadelleseguentiespressioni• �̅� + 𝑦
•(𝑥 + 𝑦)𝑥
• ScriverelafunzioneXORusandoAND,OReNOT
AlgebradiBoole eCircuitiLogici 51/52
![Page 52: Algebra di Boolee Circuiti Logici - INTRANET ...cesposito/materiale/lezioni/Lezione_3.pdf · Fondamenti di Informatica Algebra di Boolee Circuiti Logici Prof. Christian Esposito Corso](https://reader031.vdocumenti.com/reader031/viewer/2022022723/5c69d9d209d3f27a7e8bc768/html5/thumbnails/52.jpg)
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
AlgebradiBoole eCircuitiLogici 52/52