Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli...

66
Fondamenti di Informatica Algebra di Boole e Circuiti Logici Prof. Christian Esposito Corso di Laurea in Ingegneria Meccanica e Gestionale (Classe I) A.A. 2017/18 Algebra di Boole e Circuiti Logici

Transcript of Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli...

Page 1: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

FondamentidiInformaticaAlgebradi Boole eCircuit i Logici

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

AlgebradiBoole eCircuitiLogici

Page 2: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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/66

Page 3: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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

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

0 1

AlgebradiBoole eCircuitiLogici 03/66

Page 4: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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

• Nellavalutazionedelleespressionibooleaneesisteunarelazionediprecedenzafraglioperatori NOT,ANDeOR,nell’ordineincuisonostatielencati

• Peralteraretalerelazionebisognausareleparentesi• Talvoltausatesolopermaggiorechiarezza

AlgebradiBoole eCircuitiLogici 04/66

Page 5: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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

AlgebradiBoole eCircuitiLogici 05/66

Page 6: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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/66

Page 7: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

OperatoreOR:PossibiliRappresentazioni• x|y<- UsatoinMATLAB

• or(x,y)<- UsatoinMATLAB

• x#y

• xory

• x+y

• x∪ 𝒚

• x∨ 𝒚

AlgebradiBoole eCircuitiLogici 07/66

Page 8: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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/66

Page 9: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

OperatoreAND:PossibiliRappresentazioni• x&y <- UsatoinMATLAB

• and(x,y) <- UsatoinMATLAB

• xandy

• x∧ 𝒚

• x∩ 𝒚

• x×𝒚

• x*y

• xy

AlgebradiBoole eCircuitiLogici 09/66

Page 10: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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/66

Page 11: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

OperatoreNOT:PossibiliRappresentazioni• y=~x<- UsatoinMATLAB

• y=not(x)<- UsatoinMATLAB

• y=!x

• y=not x

• y=x’

• y=¬𝒙

• y=𝒙1

AlgebradiBoole eCircuitiLogici 11/66

Page 12: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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/66

Page 13: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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/66

Page 14: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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/66

Page 15: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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/66

Page 16: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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/66

Page 17: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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/66

Page 18: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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

• DalleleggidiDeMorgansievincechelasceltadellefunzioniOR,ANDeNOT,comefunzioniprimitive,èridondante

AlgebradiBoole eCircuitiLogici 18/66

Page 19: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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/66

Page 20: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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/66

Page 21: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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/66

Page 22: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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/66

Page 23: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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/66

Page 24: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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/66

Page 25: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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/66

Page 26: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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/66

Page 27: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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/66

Page 28: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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/66

Page 29: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

LemappediKarnaugh (1/2)• Le mappe di Karnaugh sono un mezzo visivo per poter manipolare esemplificare le forme algebriche di una funzione. Per le funzioni fino a4 variabili, i rispettivi termini P sono disposti su una mappa in formatabellare, e viene posto 1 in corrispondenza del termine in cui lafunzione da rappresentare assume il valore 1, 0 altrimenti.

• Esempio: consideriamo la funzione a due variabili XOR con la seguentetabella di verità,

AlgebradiBoole eCircuitiLogici 29/66

x1 x2 XOR0 0 00 1 11 0 11 1 0

Page 30: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

LemappediKarnaugh (1/2)• Le mappe di Karnaugh sono un mezzo visivo per poter manipolare esemplificare le forme algebriche di una funzione. Per le funzioni fino a4 variabili, i rispettivi termini P sono disposti su una mappa in formatabellare, e viene posto 1 in corrispondenza del termine in cui lafunzione da rappresentare assume il valore 1, 0 altrimenti.

• Esempio: consideriamo la funzione a due variabili XOR con la seguentetabella di verità, la relativa mappa di Karnaugh e la seguente:

AlgebradiBoole eCircuitiLogici 30/66

x1 x2 XOR0 0 00 1 11 0 11 1 0

0 1

0

1

x1

x2

0 1

1 0

Page 31: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

LemappediKarnaugh (2/2)• Esempio: consideriamo una funzione a quattro variabili con la seguentetabella di verità, la relativa mappa di Karnaugh e la seguente:

AlgebradiBoole eCircuitiLogici 31/66

x1 x2 x3 x4 f(x1,x2,x3,x4)0 0 0 0 10 0 0 1 10 0 1 1 00 0 1 0 10 1 0 0 00 1 0 1 10 1 1 1 10 1 1 0 01 1 0 0 01 1 0 1 01 1 1 1 11 1 1 0 11 0 0 0 11 0 0 1 01 0 1 1 11 0 1 0 1

1 1 0 1

0 1 1 0

0 0 1 1

1 0 1 1

00 01 11 10

00

01

11

10

x1x2

x3x4

Page 32: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

LemappediKarnaugh (2/2)• Nelle mappe di Karnaugh si considerano adiacenti i quadratini chehanno un lato in comune e quelli posti alle estremità opposte dellamappa.

• Queste mappe consentono di semplificare la rappresentazione informa canonica di una funzione booleana.

AlgebradiBoole eCircuitiLogici 32/66

1 1 0 1

0 1 1 0

0 0 1 1

1 0 1 1

00 01 11 10

00

01

11

10

Page 33: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

LemappediKarnaugh (2/2)• Nelle mappe di Karnaugh si considerano adiacenti i quadratini chehanno un lato in comune e quelli posti alle estremità opposte dellamappa.

• Queste mappe consentono di semplificare la rappresentazione informa canonica di una funzione booleana.

• Identifichiamo le celle adiacenti con valore 1.

AlgebradiBoole eCircuitiLogici 33/66

1 1 0 1

0 1 1 0

0 0 1 1

1 0 1 1

01 11

01

11

00

00

10

10

Page 34: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

LemappediKarnaugh (2/2)• Nelle mappe di Karnaugh si considerano adiacenti i quadratini chehanno un lato in comune e quelli posti alle estremità opposte dellamappa.

• Queste mappe consentono di semplificare la rappresentazione informa canonica di una funzione booleana.

• Identifichiamo le celle adiacenti con valore 1.

• Rappresentare i termini caratterizzanti le cellecosì identificate:

𝑓(𝑥1, 𝑥2, 𝑥3, 𝑥4) =

AlgebradiBoole eCircuitiLogici 34/66

1 1 0 1

0 1 1 0

0 0 1 1

1 0 1 1

01 11

01

11

00

00

10

10

Page 35: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

LemappediKarnaugh (2/2)

AlgebradiBoole eCircuitiLogici 35/66

1 1 0 1

0 1 1 0

0 0 1 1

1 0 1 1

01 11

01

11

00

00

10

10

• Nelle mappe di Karnaugh si considerano adiacenti i quadratini chehanno un lato in comune e quelli posti alle estremità opposte dellamappa.

• Queste mappe consentono di semplificare la rappresentazione informa canonica di una funzione booleana.

• Identifichiamo le celle adiacenti con valore 1.

• Rappresentare i termini caratterizzanti le cellecosì identificate:

𝑓 𝑥1, 𝑥2, 𝑥3, 𝑥4 = 𝑥11 𝑥O𝑥P

Page 36: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

• Nelle mappe di Karnaugh si considerano adiacenti i quadratini chehanno un lato in comune e quelli posti alle estremità opposte dellamappa.

• Queste mappe consentono di semplificare la rappresentazione informa canonica di una funzione booleana.

• Identifichiamo le celle adiacenti con valore 1.

• Rappresentare i termini caratterizzanti le cellecosì identificate:

𝑓 𝑥1, 𝑥2, 𝑥3, 𝑥4 = 𝑥11 𝑥O𝑥P + 𝑥Q𝑥O𝑥P

LemappediKarnaugh (2/2)

AlgebradiBoole eCircuitiLogici 36/66

1 1 0 1

0 1 1 0

0 0 1 1

1 0 1 1

01 11

01

11

00

00

10

10

Page 37: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

• Nelle mappe di Karnaugh si considerano adiacenti i quadratini chehanno un lato in comune e quelli posti alle estremità opposte dellamappa.

• Queste mappe consentono di semplificare la rappresentazione informa canonica di una funzione booleana.

• Identifichiamo le celle adiacenti con valore 1.

• Rappresentare i termini caratterizzanti le cellecosì identificate:

𝑓 𝑥1, 𝑥2, 𝑥3, 𝑥4 = 𝑥11 𝑥O𝑥P + 𝑥Q𝑥O𝑥P + 𝑥R𝑥O

LemappediKarnaugh (2/2)

AlgebradiBoole eCircuitiLogici 37/66

1 1 0 1

0 1 1 0

0 0 1 1

1 0 1 1

01 11

01

11

00

00

10

10

Page 38: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

• Nelle mappe di Karnaugh si considerano adiacenti i quadratini chehanno un lato in comune e quelli posti alle estremità opposte dellamappa.

• Queste mappe consentono di semplificare la rappresentazione informa canonica di una funzione booleana.

• Identifichiamo le celle adiacenti con valore 1.

• Rappresentare i termini caratterizzanti le cellecosì identificate:

𝑓 𝑥1, 𝑥2, 𝑥3, 𝑥4 = 𝑥11 𝑥O𝑥P + 𝑥Q𝑥O𝑥P + 𝑥R𝑥O + 𝑥21 𝑥P

LemappediKarnaugh (2/2)

AlgebradiBoole eCircuitiLogici 38/66

1 1 0 1

0 1 1 0

0 0 1 1

1 0 1 1

01 11

01

11

00

00

10

10

Page 39: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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 39/66

Page 40: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

PorteLogiche• Buildingblock utilizzatipercrearecircuitidigitali

• Qualsiasicircuitopuòessereimplementatousandosoloportelogicheelementari(AND,OReNOT)• Lecosesifannocomplicatequandosihannonumerosiinputedoutput

• Dispositivielettronicicheimplementanosemplicifunzionibooleane

• Ciascunaportahailpropriosimbolologicochepermetteafunzionicomplessediessererappresentatemedianteundiagrammalogico

• Lafunzionediciascunaportapuòessererappresentatadaunatabelladiveritàoutilizzandolanotazionebooleana

AlgebradiBoole eCircuitiLogici 40/66

Page 41: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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 41/66

Page 42: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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 42/66

Page 43: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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 43/66

Page 44: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

PortaNAND

AlgebradiBoole eCircuitiLogici 44/66

Page 45: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

PortaNOR

AlgebradiBoole eCircuitiLogici 45/66

Page 46: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

PortaXOR

AlgebradiBoole eCircuitiLogici 46/66

Page 47: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

PortaExclusive NOR

AlgebradiBoole eCircuitiLogici 47/66

Page 48: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

Esempio5:dallaFunzionealCircuito

CBAX +=

AlgebradiBoole eCircuitiLogici 48/66

Page 49: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

Esempio6:dallaFunzionealCircuito

C= (𝐴 + 𝐵) U (𝐴𝐵)

PortaNAND

AlgebradiBoole eCircuitiLogici 49/66

Page 50: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

Esempio7:dallaFunzionealCircuito

CBACBACBAX ++=

AlgebradiBoole eCircuitiLogici 50/66

Page 51: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

Esempio8:dallaFunzionealCircuito

DCBAY +=

PortaNOR

AlgebradiBoole eCircuitiLogici 51/66

Page 52: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

Esempio9:dalCircuitoallaFunzione– 1/2

AlgebradiBoole eCircuitiLogici 52/66

Page 53: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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

AlgebradiBoole eCircuitiLogici 53/66

Page 54: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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

AlgebradiBoole eCircuitiLogici 54/66

Page 55: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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

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

AlgebradiBoole eCircuitiLogici 55/66

Page 56: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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 56/66

Page 57: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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 57/66

𝑋 = �̅�𝐵L𝐶 + 𝐴𝐵L𝐶 + 𝐴𝐵𝐶̅

Page 58: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

Esercizio2:minimizzarelafunzioneespressadallaseguentetavoladiverità

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 58/66

Page 59: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

Esercizio2:minimizzarelafunzioneespressadallaseguentetavoladiverità

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 59/66

1

1 1

00 01 11 10

0

1

A

BC

Page 60: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

Esercizio2:minimizzarelafunzioneespressadallaseguentetavoladiverità

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 60/66

1

1 1

00 01 11 10

0

1

A

BC

𝑋 = 𝐵L𝐶 + 𝐴𝐵𝐶̅

Page 61: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

Esercizio3:trovarel’outputdelseguentecircuito(tavoladiveritàefunzione)

xyxyy

AlgebradiBoole eCircuitiLogici 61/66

Page 62: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

Esercizio4:trovarel’outputdelseguentecircuito(tavoladiveritàefunzione)

x

y

AlgebradiBoole eCircuitiLogici 62/66

Page 63: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

Esercizio5:trovarel’outputdelseguentecircuito(tavoladiveritàefunzione)

AlgebradiBoole eCircuitiLogici 63/66

Page 64: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

Esercizio6:trovarel’outputdelseguentecircuito(tavoladiveritàefunzione)

AlgebradiBoole eCircuitiLogici 64/66

Page 65: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

Esercizio6:progettareilcircuitoperciascunadelleseguentiespressioni• �̅� + 𝑦

•(𝑥 + 𝑦)𝑥

• ScriverelafunzioneXORusandoAND,OReNOT

AlgebradiBoole eCircuitiLogici 65/66

Page 66: Algebra di Boolee Circuiti Logicicesposito/materiale/lezioni...L’Algebra di Boole–4/4 •Gli operatoridell’algebra booleana possono essere rappresentati e descritti in vari modi

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 66/66