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
0 1
AlgebradiBoole eCircuitiLogici 03/52
L’AlgebradiBoole – 3/4• LeoperazioniAND eOR sonooperazionibinarie (agisconosudueoperandi),l’operazioneNOT èunaria
• Nellavalutazionedelleespressionibooleaneesisteunarelazionediprecedenzafraglioperatori NOT,ANDeOR,nell’ordineincuisonostatielencati
• Peralteraretalerelazionebisognausareleparentesi• Talvoltausatesolopermaggiorechiarezza
AlgebradiBoole eCircuitiLogici 04/52
L’AlgebradiBoole – 4/4• Glioperatori dell’algebrabooleanapossonoessererappresentatiedescrittiinvarimodi• SpessosonodescrittisemplicementecomeAND,OReNOT• Tavolediverità• Nelladescrizionedeicircuitiappaionosottoformadiportelogiche
AlgebradiBoole eCircuitiLogici 05/52
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
OperatoreOR:PossibiliRappresentazioni• x|y<- UsatoinMATLAB
• or(x,y)<- UsatoinMATLAB
• x#y
• xory
• x+y
• x∪ 𝒚
• x∨ 𝒚
AlgebradiBoole eCircuitiLogici 07/52
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
OperatoreAND:PossibiliRappresentazioni• x&y <- UsatoinMATLAB
• and(x,y) <- UsatoinMATLAB
• xandy
• x∧ 𝒚
• x∩ 𝒚
• x×𝒚
• x*y
• xy
AlgebradiBoole eCircuitiLogici 09/52
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
OperatoreNOT:PossibiliRappresentazioni• y=~x<- UsatoinMATLAB
• y=not(x)<- UsatoinMATLAB
• y=!x
• y=not x
• y=x’
• y=¬𝒙
• y=𝒙1
AlgebradiBoole eCircuitiLogici 11/52
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
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
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
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
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
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
AlcuneOsservazioni• Identità,proprietàeleggivistefinoadorasonogeneralmenteapplicatenelletrasformazionidifunzionibooleaneinaltreequivalenti,madipiùfacilerealizzazionecircuitale
• DalleleggidiDeMorgansievincechelasceltadellefunzioniOR,ANDeNOT,comefunzioniprimitive,èridondante
AlgebradiBoole eCircuitiLogici 18/52
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
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
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
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
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
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
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
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
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
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
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
PorteLogiche• Buildingblock utilizzatipercrearecircuitidigitali
• Qualsiasicircuitopuòessereimplementatousandosoloportelogicheelementari(AND,OReNOT)• Lecosesifannocomplicatequandosihannonumerosiinputedoutput
• Dispositivielettronicicheimplementanosemplicifunzionibooleane
• Ciascunaportahailpropriosimbolologicochepermetteafunzionicomplessediessererappresentatemedianteundiagrammalogico
• Lafunzionediciascunaportapuòessererappresentatadaunatabelladiveritàoutilizzandolanotazionebooleana
AlgebradiBoole eCircuitiLogici 30/52
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
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
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
PortaNAND
AlgebradiBoole eCircuitiLogici 34/52
PortaNOR
AlgebradiBoole eCircuitiLogici 35/52
PortaXOR
AlgebradiBoole eCircuitiLogici 36/52
PortaExclusive NOR
AlgebradiBoole eCircuitiLogici 37/52
Esempio5:dallaFunzionealCircuito
CBAX +=
AlgebradiBoole eCircuitiLogici 38/52
Esempio6:dallaFunzionealCircuito
C= (𝐴 + 𝐵) O (𝐴𝐵)
PortaNAND
AlgebradiBoole eCircuitiLogici 39/52
Esempio7:dallaFunzionealCircuito
CBACBACBAX ++=
AlgebradiBoole eCircuitiLogici 40/52
Esempio8:dallaFunzionealCircuito
DCBAY +=
PortaNOR
AlgebradiBoole eCircuitiLogici 41/52
Esempio9:dalCircuitoallaFunzione– 1/2
AlgebradiBoole eCircuitiLogici 42/52
Esempio9:dalCircuitoallaFunzione– 2/2• Procedereprogressivamentedagliinputversol’outputaggiungendoaturnoleespressionilogicheall’outputdiciascunaportalogica
AlgebradiBoole eCircuitiLogici 43/52
Esempio10:Funzione=>TavoladiVerità=>Circuito• Siconsiderilaseguentefunzione:A(B + C)
AlgebradiBoole eCircuitiLogici 44/52
Ricapitolando…• Abbiamovistocheunafunzionelogica (maancheuncircuitologico)puòessereespressainduemodi• TavoladiVerità• PorteLogiche
• Perchéabbiamobisognodituttequestediverserappresentazioni?• Alcunesonopiùfacilidialtrepercominciareaprogettareuncircuito• Disolitosicominciaconlatavoladiverità• Siderivaun’espressionebooleanadaessa(magariesemplificata)• Sitrasformal’espressionebooleanainuncircuito
AlgebradiBoole eCircuitiLogici 45/52
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
Esercizio2:trovarel’outputdelseguentecircuito(tavoladiveritàefunzione)
xyxyy
AlgebradiBoole eCircuitiLogici 47/52
Esercizio3:trovarel’outputdelseguentecircuito(tavoladiveritàefunzione)
x
y
AlgebradiBoole eCircuitiLogici 48/52
Esercizio4:trovarel’outputdelseguentecircuito(tavoladiveritàefunzione)
AlgebradiBoole eCircuitiLogici 49/52
Esercizio5:trovarel’outputdelseguentecircuito(tavoladiveritàefunzione)
AlgebradiBoole eCircuitiLogici 50/52
Esercizio6:progettareilcircuitoperciascunadelleseguentiespressioni• �̅� + 𝑦
•(𝑥 + 𝑦)𝑥
• ScriverelafunzioneXORusandoAND,OReNOT
AlgebradiBoole eCircuitiLogici 51/52
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
