Algebra Booleana
Assistant Prof. Irina RAICU
INTRODUCERE
In electronica digitala, semnalele electrice pot lua numai valori
discrete, aceste valori fiind asociate conventional lui 0 logic si 1
logic. (bit)
Calculatoarele electronice digitale efectuaza operatii logice.
Acestea stau la baza procesorului calculatorului.
STRUCTURA SEMINAR 9
Axiomele algebrei bool
Functii logice forme canonice, tabel de adevar
Simplificarea functiilor logice
Circuite logice
AXIOMELE ALGEBREI
BOOL
Seminar/Suport de curs/ Carte
http://zota.ase.ro/bti/index.html
http://carment.ase.ro/bti/curs/
http://nastasef.ase.ro/
Parola bti
FUNCTII LOGICE
Orice functie logica se reprezinta printr-un tabel de
adevar.
In functie de nr de variabile, o functie poate fi definita
astfel:
1 variabila f:B->B, B={0,1}
2 variabile f:B x B ->B, B={0,1}
3 variabile f:B x B x B->B, B={0,1}
4 variabile f:B x B x B x B->B, B={0,1}
FUNCTII LOGICE
Forme canonice
Pentru orice functie logica f, exista 2 forme canonice:
Forma canonice conjunctiva = produs de Maxterms, unde
functia ia valoarea 0.
Forma canonice disjunctiva = suma de minterms, unde functia
ia valoarea 1.
OBS! Cand FCC=FCD (vezi ex1. seminar 9), se iau in
considerare minterms si maxterms cand functia ia val 1,
alftel pentru FCC se iau maxterms cand f=0.
SIMPLIFICAREA/MINIMI
ZAREA FUNCTIILOR
LOGICE
Minimizarea unei functii logice se poate realiza prin:
Metoda analitica (axiomele alg bool)
Metoda diagramelor Veitch sau Karnaugh
Diagrame Karnaugh
Functie logica cu 3 variabile (a, b, c)
Diagrame Karnaugh
Functie logica cu 4 variabile (a, b, c, d)
EXEMPLE DE
MINIMIZARI
Pentru ca o functie sa poate fi minimizata, mai intai
trebuie determinata forma canonica conjunctiva
(FCC) si/sau forma canonica disjunctiva (FCD).
EXEMPLE DE
MINIMIZARI
1. Minimizare prin FCD
FCD= suma de mintermeni, cand f=1.
In diagrama Karnaugh se completeaza cu 1
valoriile functiei in care aceasta a luat
valoarea 1.
EXEMPLE DE
MINIMIZARI
Exemplu: Fie f(a, b, c) =abc+ abc + abc + abc
1. Sa se realizeze circuitul logic
Vezi figura 1.
2. Sa se minimizeze f prin diagrama
Karnaugh., stiind ca f(a, b, c) reprezinta
FCD a functiei f (este suma de produs
Suma de minterms)
Fig. 1
EXEMPLE DE
MINIMIZARI
Algoritm de minimizare prin Karnaugh:
Pas 1: Se deseneaza diagrama Karnaugh pentru f(a,b,c)
EXEMPLE DE
MINIMIZARI
Pas 2: Avand FCD a functiei f functia a luat valoarea 1, se completeaza in
diagrama valorile 1 corespunzator pozitiei fiecarui produs al sumei functiei f. (Cum
in functia f sunt 4 termeni, in diagrama se completeaza cu 4 de 1).
Pas 3: Se identifica grupuri de celule alaturate ce contin valoarea 1(se pot forma
grupuri/cercuri de 2, 4, 8 elemente)
OBS!
1. Fiecare grup trebuie sa contina 2, 4, 8 celule adiacente ( in functie de variabilele
functiei f)
2. Celulele adiacente au o latura comuna pe verticala sau pe orizontala si difera
printr-o singura variabila
3. Se considera adiacente si celulele de la capetele opuse ale unei linii sau coloane.
EXEMPLE DE
MINIMIZARI
Algoritm de minimizare prin Karnaugh:
Pentru functia f(a, b, c) s-au identificat 3 grupuri.
EXEMPLE DE
MINIMIZARI
Pas 4. Dupa identificarea grupurilor, se cauta variabilele comune pentru fiecare grup
si scriem pentru fiecare grup in parte variabila (produs de variabile, daca sunt mai
multe) ca rezultat bool.
Rezultatul final este suma rezultatelor fiecarui grup.
Astfel pentru f(a, b, c) in diagrama Karnaugh:
Pentru grupul 1 sunt comune variabilele A si C => rezultat logic A * C
Pentru grupul 2 sunt comune variabilele A si C => rezultat logic B * C
Pentru grupul 3 sunt comune variabilele A si C => rezultat logic A * B
Functia minimizata este: A * C + B * C + A * B
EXEMPLE DE GRUPARI
1 1
1 1
3 grupari
EXEMPLE DE
MINIMIZARI
2. Minimizare prin FCC
FCC=produs de maxtermeni, cand f=0.
In diagrama Karnaugh se completeaza cu 0
valoriile functiei in care aceasta a luat
valoarea 0.
EXEMPLE DE
MINIMIZARI
Algoritmul este identic ca cel aplicat pe o FCD,
cu diferenta ca in diagrama se completeaza cu 0
in celulele unde f=0, deoarece FCC se formeaza
atunci cand f=0.
EXEMPLE DE
MINIMIZARI
Exemplu: Fie f(a, b, c) =abc+ abc + abc + abc
1. Sa se minimizeze f prin diagrama Karnaugh., stiind ca f(a, b,
c) reprezinta FCC a functiei f (este produs de suma produs
de maxterms)
2. Diagrama Karnaugh ptr exemplu se va realiza astfel: (3
grupuri)
0 0 0
0
EXEMPLE DE
MINIMIZARI
Fie f(a, b, c, d), sa se minimizeze prin
FCD si FCC.
Ex. 1 - FCD
1 1 1 1
1 1
1 1
1 1 1 1
=> 2 grupuri
EXEMPLE DE
MINIMIZARI
Fie f(a, b, c, d), sa se minimizeze prin
FCD si FCC.
Ex. 1 - FCC
0 0
0 0
=> 2 grupuri
EXEMPLE DE
MINIMIZARI
Fie f(a, b, c, d), sa se minimizeze prin
FCD si FCC.
Ex. 2 - FCD
1 1
1 1
1 1
=> 2 grupuri
EXEMPLE DE
MINIMIZARI
Fie f(a, b, c, d), sa se minimizeze prin
FCD si FCC.
Ex. 2 - FCC
0 0
0 0
0 0
0 0 0 0
=> 4 grupuri
EXEMPLE DE
MINIMIZARI
Fie f(a, b, c, d), sa se minimizeze prin
FCD si FCC.
Ex. 3 - FCD
1 1
1 1 1 1
1 1 1
=> 5 grupuri
EXEMPLE DE
MINIMIZARI
Fie f(a, b, c, d), sa se minimizeze prin
FCD si FCC.
Ex. 3 - FCC
0 0 0 0
0 0
=> 4 grupuri
