Proiectarea logică a dispozitivelor numerice

1. Aspecte teoretice

Algebra booleanã

O algebră booleană este un ansamblu ( M ,, ,  format din mulţimea suport M cu un număr finit de elemente, operaţia binară SAU notată cu simbolul +, operaţia binară ŞI notată cu simbolul • şi o relaţie de echivalenţă între elementele mulţimii M, notată cu simbolul = , dacă sunt îndeplinite următoarele 6 postulate:

P1 Operaţiile sunt închise:

P2 Pentru fiecare operaţie existã un element neutru:

P3 Operaţiile sunt comutative:

P4 Operaţiile sunt distributive:

P5 Pentru fiecare element

P6 Existã cel puţin 2 elemente distincte în mulţimea M:

Se observã cã fiecare propoziţie este exprimatã prin douã echivalenţe booleene. Prin interschimbarea operaţiilor binare SAU cu ŞI şi a constantelor 0 cu 1 se obţine o relaţie din cealaltã. Aceastã proprietate se numeşte dualitate. În general, este valabilã pentru orice proprietate booleanã.

Iată care sunt formulele din Algebra Booleană :

X + 1 = 1 X + 0=X X + X=X

X 1 = X X 0 = 0 X X = X

X(a+b) = Xa+Xb a+b = b+a ab=ba

(a+b)(a+c) = aa+ac+ab+bc

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

xy[ (-x)+(-y) ]=0

xy(x+y)=xy

x+xy =x

x((-x)+y)=xy

x + y(-x ) = x+y

La aceste formule se vor adãuga şi cele din legile lui De Morgan.

Iată formulele (legile ) De Morgan

Demonstraţie :

, unde T1 şi T7 reprezintã 2 legi fundamentale :

Iar P2,P4,P5 reprezintã postulatele prezentate mai sus.

Aceste două formule stabilesc relaţiile dintre cele trei operaţii booleene de bază : NOT , AND şi OR la nivelul funcţiilor booleene . Prin generalizare, aceste două formule se pot scrie şi astfel :

O funcţie binară cu n intrări este o aplicaţie a mulţimii în mulţimea formatã din 2 elemente {0,1}. Domeniul de definiţie al funcţiei este mulţimea configuraţiilor binare de n biţi :

. Cardinalul mulţimii este .

Funcţiile binare se reprezintã de obicei prin tabele de adevãr, expresii booleene, forme geometrice sau diagrame Veitch- Karnaugh.

Tabelul de adevăr al unei funcţii logice este o listă a tuturor punctelor mulţimii de definiţie, pentru fiecare dintre acestea precizând valoarea funcţiei. Mulţimea de definiţie D a unei funcţii logice este un produs cartezian de mulţimi booleene D= BxBxBx…xB ,iar fiecare punct al ei ,este o combinaţie de valori logice ale variabilelor funcţiei :

Tabelul de adevãr conţine toate combinaţiile posibile de valori logice. În figura urmatoare este prezentat un tabel de adevãr pentru 4 variabile. Numãrul de puncte va fi .

A B C D

P0 0 0 0 0

P1 0 0 0 1

P2 0 0 1 0

P3 0 0 1 1

P4 0 1 0 0

P5 0 1 0 1

P6 0 1 1 0

P7 0 1 1 1

P8 1 0 0 0

P9 1 0 0 1

P10 1 0 1 0

P11 1 0 1 1

P12 1 1 0 0

P13 1 1 0 1

P14 1 1 1 0

P15 1 1 1 1

Diagramele Veitch-Karnaugh oferã o reprezentare graficã sugestivã a funcţiei binare. O diagrama Veitch-Karnaugh pentru o funcţie de n variabile este un tablou ce conţine compartimente, câte unul pentru fiecare din cele combinaţii posibile ale variabilelor funcţiei. În interiorul acestor compartimente se trec valorile funcţiei 1 sau 0. În urmãtoarele figuri sunt 2 diagrame, prima este o diagramã Veitch, iar a doua o diagramã Karnaugh. Deşi, în general,se preferã lucrul cu diagrama Veitch, care pare mai eficientã, se utilizeazã denumirea de Veitch-Karnaugh pentru aceasta.