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.
Pentru a descărca acest document,
trebuie să te autentifici in contul tău.
