Algebra BOOLE. Tabela de adevar. Functii logice.

Algebra BOOLE. Tabela de adevar. Functii logice.

MINIMIZAREA FUNCTIILOR LOGICE

Noiuni despre algebra BOOLE.

Fiind data o multime de elemente M in care s-au definit simbolurile '0' si '1' carora li se asociaza valorile 'fals', respectiv 'adevarat' si operatiile:

- sumare booleana (disjunctie, functia 'SAU','OR') - notata '+' sau ' '

- produs boolean (conjunctie, functia 'SI', 'AND') - notata '*' sau ' ' (sau fara nici o notare prin analogie cu multiplicarea aritmetica)

- negare booleana (functia 'NOT') - notata ''

Putem spune ca sunt satisfacute legile (axiomele):

multimea M= este inchisa in raport cu operatorii '+','*' sau '' adica:

a,bM atunci abM, a+bM, not(a) M

- comutativitate: x+y=y+x ;

xy=yx

- asociativitate: x+(y+z)=(x+y)+z ;

x(yz)=(xy)z

- distributivitate: x(y+z)=xy+xz ;

x+(yz)=(x+y)(x+z)

- exista in M un element neutru fata de adunare: x+0=x

- exista in M element neutru fata de inmultire:

pentru orice nM, exista complementarul sau, notat M (sau not(n)) care

satisface relatiile:

n+=1

Mai avem si un grup de teoreme:

- idempotenta: x + x=x ;

xx=x

x0=0

x+1=1

- dubla negatie: not(not(x))=x

- legile lui De Morgan: not(x+y)=not(x)not(y) ()

not(xy)=not(x)+not(y) ()

- dualitatea: daca intr-o expresie booleana se inlocuiesc simbolurile '+' si '' intre ele, iar 0 cu 1 (si invers) se obtine tot o expresie adevarata.

Exemplu: ; ;

- absorbtia: x(x+y)=x si expresia duala: x+xy=x

- x+=x+y si expresia duala x* (not(x)+y)=xx

FUNCTII LOGICE. TABELA DE ADEVAR

Fiind date variabilele logice x₀,x₁..x_n-1 din multimea M si o alta variabila yM daca realizam o corespondenta intre toate combinatiile variabilelor x si, respectiv valorile variabilei y, putem spune ca am definit o functie logica:

y=y(x_n-1,x_n-2..x₁x₀) in care variabilele x_i se numesc variabile independente, iar variabila y -> variabila dependenta

Functia logica y are cel mult 2ⁿ valori corespunzatoare celor 2ⁿ combinatii posibile ale valorilor variabilei independente x (valorile binare posibile).

Tabelul de adevar al unei functii logice reprezinta un tabel cu n+1 coloane (corespunzatoare numarului total de variabile independente 'x'+variabila dep. 'y') si 2ⁿ linii corespunzatoare tuturor valorilor pe care le poate lua functia y.

Vom considera tabelul de adevar corespunzator unei situatii reale. Am 3 motoare care deservesc o anumita instalatie. Conditia ca instalatia sa functioneze este ca cel putin 2 motoare sa functioneze la un moment dat. Vom nota cu n_i=1 un motor functional si n_i=0 (sau '') in caz contrar. Va rezulta urmatorul tabel de adevar.

x₂ x₁ x₀ y

---|----|----|----||----

0 | 0 | 0 | 0 || 0

1 | 0 | 0 | 1 || 0

2 | 0 | 1 | 0 || 0

3 | 0 | 1 | 1 || 1

4 | 1 | 0 | 0 || 0

5 | 1 | 0 | 1 || 1

6 | 1 | 1 | 0 || 1

7 | 1 | 1 | 1 || 1

----- ----- -------------

Expresii analitice ale functiilor logice

Definitie: Numim conjunctie elementara produsul unor variabile sau ale inverselor lor.

Exemplu:

unde, am notat:

- coeficientul superior imi da numarul de variabile independente

- coeficientul inferior imi da valoarea echivalentului zecimal al conjunctiei

Avem relatia:

(k_n-1k_n-2k₀)₂ este echivalentul binar al conjunctiei, cu k_i, iar j₁₀ este echivalentul zecimal

Definitie: Doua conjunctii se numesc vecine daca difera printr-un singur rang.

Ex.:

Daca notam cu:         

putem scrie:

si si in continuare:

Definitie: Numim disjunctie elementara suma logica a unor variabile sau ale

inverselor lor.

Definitie: Doua disjunctii sunt vecine daca difera printr-un singur rang.

Consideram doua disjunctii:

Notam cu:

si facem produsul disjunctiilor:

Forma canonica disjunctiva a unei functii logice

O funtie de o singura variabila poate fi scrisa:

O functie de 2 variabile poate fi scrisa:

sau

Deci y se poate scrie sub forma:

adica:

pentru care f(k₁,k₀)=1

Prin generalizare (inductie) ajungem la forma canonica disjunctiva (f.n.d-numita si o disjunctie de conjunctii sau de mintermeni):

pentru care f(k_n-1.k₁k₀)=1

Daca ne referim la tabelul de adevar definit anterior, expresia functiei logice y se scrie astfel in f.n.d (alegem numai combinatiile pentru care y=1):

Putem spune ca expresia functiei logice y in f.n.d este o suma de conjunctii (mintermeni), in care fiecare conjunctie contine toate variabilele independente. Conjunctiile care apar in expresia functiei corespund valorilor de 1 din tabelul de adevar. Valorile independente apar in forma directa sau negata, functie de valorile corespunzatoare din tabel (1 respectiv 0).

Forma canonica conjunctiva a unei functii logice

Pentru a ajunge la forma canonica conjunctiva (f.n.c) plecam de la f.n.d careia ii aplicam legile lui De Morgan (negatul sumei= produsul negatelor, iar negatul produsului este suma negatelor).

Ca urmare vom considera expresia lui not(y) in f.n.d:

Inversind (complementind) aceasta relatie si aplicind legile lui De morgan ajungem la f.n.c:

pentru care not(f(k_n-1k₁k₀)=1)) adica f(k_n-1k₁k₀)=0

Vom scrie expresia functiei logice y in f.n.c pentru tabelul de adevar anterior (alegem numai combinatiile pentru care y=0)

sau

Deci, in f.n.c expresia unei functii logice este formata din produsul disjunctiilor (maxtermenilor) corespunzatoare valorilor 0 ale functiei. Fiecare disjunctie contine toate variabilele independente in forma directa sau negata functie de valorile corespunzatoare din tabel (0 respectiv 1, deci invers fata de f.n.d)

Functii incomplet definite

Exista situatii in care pentru anumite valori ale valorilor variabilelor independente, nu este precizata valoarea functiei logice sau, practic vorbind, aceste combinatii nu apar niciodata in sistemul fizic ce materializeaza functia data.

Vom spune in acest caz ca funtia este incomplet definita si prezinta valori indiferente (pe care le vom nota cu caracterul )

Consideram, ca exemplu, din nou tabelul de adevar anterior in care vom inlocui, aleator, niste combinatii, cu .

x₂ x₁ x₀ y

---|----|----|----||----

0 | 0 | 0 | 0 || 0

1 | 0 | 0 | 1 ||

2 | 0 | 1 | 0 || 0

3 | 0 | 1 | 1 || 1

4 | 1 | 0 | 0 ||

5 | 1 | 0 | 1 || 1

6 | 1 | 1 | 0 || 1

7 | 1 | 1 | 1 || 1

----- ----- -------------

Un alt mod de a exprima o functie logica consta in indicarea echivalentilor zecimali pentru care functia ia valoarea 1 sau valoarea 0, cum este mai convenabil.

Ex:       y=R₁(3,5,6,7)+R_(1,4) sau y=R₀(0,2)

IMPLEMENTAREA FUNCTIILOR LOGICE

Pentru implementarea unei functii logice se folosesc circuitele elementare numite porti care sunt asociate operatorilor booleni anterior mentionati. Astfel avem porti 'SI', 'SAU', 'NU', dar si porti care implementeaza cobinatii ale operatorilor: 'SI-NU' (not(xy)), 'SAU-NU' (not(x+y)), 'SAU-EXCLUSIV' (xnot(y)+not(x)y=xy)

Definitie:        Costul unei functii logice este dat de numarul de intrari in circuitele

utilizate pentru implementare

Definitie:        Numar de nivele ale unei implementari este dat de numarul maxim de

circuite strabatut de un semnal (variabila independenta) de la intrare la

iesire.

Definitie:        Minimizarea unei functii logice reprezinta obtinerea unei expresii a

functiei logice pentru un numar de nivele dat cu cost minim.

Altfel spus, minimizarea unei functii trebuie sa conduca la o expresie formata fin citi mai putin termeni, iar fiecare termen sa contina cit mai putine variabile independente.

O modalitate de minimizare a unei functii logice ar fi aplicarea legilor algebrei BOOLE. De exemplu, consideram expresia functiei y pentru tabelul de adevar anterior in f.n.d. si aplicam un artificiu de calcul: ultimul termen il mai scriem de 2 ori si functia isi pastreaza valoarea conform legii idempotentei dupa care facem grupari favorabile de termeni rezultind expresia minimizata a functiei.

sau

Se observa ca metoda este greu de aplicat in mod sistematic si nu se poate stabili cu certitudine cind s-a obtinut solutia minima (mai ales daca am 4 sau 5 variabile independente)

O metoda rapida de minimizare, foarte utilizata, este metoda Veitch-Karnaugh care se aplica functiilor de maxim 5 variabile (pentru mai multe variabile, metoda este greu de aplicat, apelindu-se la alte metode cum ar fi metoda Quine Mc-Cluskey).

Definitie: Prin partitie de variabile se intelege separarea unui sir de variabile in

doua grupe.

De ex. in cazul variabilelor independente x₂,x₁,x₀ putem considera partitia [x₂,x₁] si [x₀] sau [x₂] si [x₁,x₀].

In cazul general, a n variabile independente x_n-2x_n-1..x₁x₀ vom considera partitia [x₀x₀] [x₀x₀], unde p=n/2, pentru n par sau p=[(n-1)/2] ori [(n+1)/2] pentru n impar

Metoda Veitch-Karnaugh consta intr-o ordonare matriciala a conjunctiilor (valorile de 1 ale functiei) sau disjunctiilor (valorile de 0 ale functiei). Matricea respectiva contine un numar de linii si coloane determinat de partitia propusa pentru variabile independente. Pentru n variabile matricea va avea dimensiunea (2^k,2^p) unde:

k = numarul de variabile ale primului termen al partitiei

p = numarul de variabile ale celui de-al doilea termen al partitiei

iar n=k+p si deci 2^k*2^p=2ⁿ elemente ale matricii.

Fiecare element al matricii va indica conjunctia (sau disjunctia) si deci valoarea functiei respective, aferenta valorilor variabilelor independente ce pozitioneaza elementul in matrice.

Pentru ordonarea liniilor si coloanelor matricii se foloseste codul binar reflectat (GRAY) care are particularitatea ca doua valori consecutive difera printr-un singur rang (o singura variabila). Pe acest lucru se bazeaza si metoda Veitch-Karnaugh, in sensul ca adunind (inmultind) doua conjunctii (disjunctii) vecine dispare termenul care difera. In acest sens se pot cupla 2³, 2², 2¹ conjunctii (disjunctii) disparind 1,2,3 variabile corespunzatoare, si astfel se realizeaza minimizarea.

Practic, gruparea celulelor adiacente conduce in f.n.d la expresia:

sau, in f.n.c la expresia:

Vom considera vechiul nostru tabel de adevar si vom realiza pentru el matricea Veitch-Karnaugh.

x₂x₁x₀| 0 | 1 |

00 | | |

01 | | 1 |

11 | 1 | 1 |

10 | | 1 |

Minimizarea functiei y presupune parcurgerea urmatorilor pasi:

- se realizeaza diagrama V-K (vezi sus) in care se trec valorile de '1' (pentru f.n.d) sau '0' (pentru f.n.c) ale functiei in locurile corespunzatoare combinatiilor variabilelor independente x_i

- se realizezaza gruparea celulelor vecine in zone cit mai mari formate dintr-un numar de elemente (valori de '1', sau '0') egal cu o putere a lui 2 (2, 4, 8 etc). De mentionat ca celulele laterale care sunt simetrice fata de o linie mediana imaginara a diagramei sunt de asemenea vecine

- fiecare grupa de celule formeaza un termen (produs pentru '1', suma pentru '0') al expresiei minimizate, termen care nu va contine variabilele care isi schimba valoarea si astfel dispar.

expresia minimizata se obtine din suma (pentru '1'), respectiv produsul

(pentru '0') termenilor obtinuti anterior

Observatii:

- acelasi element poate face parte din oricite grupe de celule

- fiecare grupa TREBUIE sa contina cel putin un element nou fata de celelalte

orice element trebuie sa faca parte din cel putin o grupa (chiar o grupa de

un singur element (grupa cu 2⁰ elemente)

- variabilele care formeaza termenii expresiei se scriu conform regulilor stabilite la f.n.d (pentru '1'), respectiv f.n.c (pentru '0')

In cazul exemplului nostru aplicind pasii de mai sus obtinem urmatoarea expresie minimizata pentru y:

y=x₂x₁+x₂x₀+x₁x₀ (2)

Vom considera matricea Veitch-Karnaugh pentru acelasi tabel de adevar in care vom trece acum disjunctiile functiei (deci valorile 0)

x₂x₁x₀| 0 | 1 |

00 | 0 | 0 |

01 | 0 | |

11 | | |

10 | 0 | |

Expresia minimizata pentru y (in urma realizarii calculelor si aplicarii legilor booleene) va fi:

se observa ca variabilele independente apar in

relatie in forma negata, conform relatiei functiei in f.n.c.

In urma realizarii calculelor si prin aplicarea legilor booleene se obtine expresia lui y care este aceeasi cu relatia (2):

Minimizarea functiilor incomplet definite

In acest caz in diagrama se vor trece si valorile indiferente ('') din tabelul de adevar in pozitiile aferente combinatiilor de valori ale variabilelor independente.

Pentru realizarea minimizarii se vor urma etapele deja aminitite cu precizarea ca valorile indiferente vor fi considerate numai daca contribuie la cresterea numarului de celule dintr-o grupa

Vom considera tabelul de adevar prezentat anterior ca exemplu la functii incomplet definite. Construim diagrama V-K pentru acest exemplu, in care functia y se poate scrie (folosind echivalentii zecimali):

y=R₁(3,5,6,7)+R_f sau y=R₀(0,2)

x₂x₁x₀| 0 | 1 |

00 | | |

01 | | 1 |

11 | 1 | 1 |

10 | | 1 |

In urma gruparii celulelor vecine vom obtine urmatoarea expresie minimizata pentru y in f.n.d: y=x2+x0

Construim diagrama V-K pentru f.n.d:

x₂x₁x₀| 0 | 1 |

00 | 0 | |

01 | 0 | |

11 | | |

10 | | |

Se observa ca nu am decit o singura grupa de celule (cei 2 de '0'), iar valorile indiferente nu are sens sa le mai grupez intrucit ar complica inutil expresia minimizata (nu permit, in acest caz, realizarea de grupe mai mari !!)

Expresie minimizata pentru y in f.n.c va fi: y=x2+x0

Concluzie:

- pentru minimizarea unei functii logice trebuie ales intre cele doua posibilitati de exprimare a valorii functiei (f.n.d/f.n.c), in sensul ca vom alege acea posibilitate care ma conduce la un numar minim de celule completate in diagrama V-K, dar nu este obligatoriu si la o forma mai convenabila a expresiei minimizate. De asemenea, este posibil ca minimizarea folosind legile algebrei BOOLE sa ma conduca la o expresie cu un cost mai mic decit cea obtinuta prin metoda V-K, insa metoda este mai laborioasa.

In cazul nostru era avantajos preferarea f.n.c pentru y, care a condus la aceeasi expresie.

Tema: Sa se minimizeze si sa se implementeze expresia urmatoarelor functii (atit pentru f.n.d cit si pentru f.n.c):

y=R₁(0,2,6,7,8,10,12,13,14,15)

y=R₁(0,2,6,7,8,10,12,13,14,15)+R(3,5,11)

Se vor folosi atit legile algebrei BOOLE cit si metoda V-K.