Definirea axiomatica a algebrei booleene
Algebra booleana este o algebra formata din:
elementele {0,1};
2 operatii binare numite SAU si SI, notate simbolic + sau Ú si × sau Ù;
1 operatie unara numita NU negatie, notata simbolic sau Ø.
Operatiile se definesc astfel:
SI SAU NU
0 × 0 = 0 0 + 0 = 0 0 = 1 39628ind67tev7k
0 × 1 = 0 0 + 1 = 1 1 = 0
1 × 0 = 0 1 + 0 = 1
1 × 1 = 1 1 + 1 = 1
Axiomele algebrei booleene sunt urmatoarele: ne628i9367teev
Fie o multime M compusa din elementele x1, x2,…xn, impreuna cu operatiile × si +. Aceasta multime formeaza o algebra daca:
Multimea M contine cel putin 2 elemente distincte x1 ¹ x2 (x1,x2I M);
Pentru " x1 I M, x2 I M avem:
x1 + x2 I M si x1 × x2 I M
Operatiile × si + au urmatoarele proprietati:
sunt comutative
x1 × x2 = x2 × x1
x1 + x2 = x2 + x1
sunt asociative
x1 × (x2 × x3) = (x1 × x2) × x3
x1 + (x2 + x3) = (x1 + x2) + x3
sunt distributive una fata de cealalta
x1 × (x2 + x3) = x1 × x2 + x1 × x3
x1 + (x2 × x3) = (x1 + x2) × (x1 + x3)
Ambele operatii admit cate un element neutru cu proprietatea:
x1 + 0 = 0 + x1 = x1
x1 × 1 = 1 × x1 = x1
unde 0 este elementul nul al multimii, iar 1 este elementul unitate al multimii.
Daca multimea M nu contine decat doua elemente, acestea trebuie sa fie obligatoriu elementul nul 0 si elementul unitate 1; atunci pentru " x I M exista un element unic notat cu x cu proprietatile:
x × x = 0 principiul contradictiei
x + x = 1 principiul tertului exclus
x este inversul elementului x.
In definirea axiomatica a algebrei s-au folosit diferite notatii. In tabelul urmator se dau denumirile si notatiile specifice folosite pentru diverse domenii:
Matematica |
Logica |
Tehnica |
Prima lege de compozitie
x1 + x2 |
Disjunctie
x1 Ú x2 |
SAU
x1 + x2 |
A doua lege de compozitie
x1 × x2 |
Conjunctie
x1 Ù x2 |
SI
x1 × x2 |
Elementul invers
x |
Negare
Øx |
NU
x |
1.3. Proprietatile algebrei booleene
Plecand de la axiome se deduc o serie de proprietati care vor forma reguli de calcul in cadrul algebrei booleene. Aceste proprietati sunt:
Principiul dublei negatii
x = x dubla negatie duce la o afirmatie
Idempotenta
x × x = x
x + x = x
Absorbtia
x1 × (x1 + x2) = x1
x1 + (x1× x2) = x1
Proprietatile elementelor neutre
x × 0 = 0 x × 1 = x
x + 0 = x x + 1 = 1
Formulele lui De Morgan
x1 × x2 = x1 + x2
x1 + x2 = x1 × x2
Aceste formule sunt foarte utile datorita posibilitatii de a transforma produsul logic in suma logica si invers.
Formulele pot fi generalizate la un numar arbitrar de termeni:
x1 × x2 × … × xn = x1 + x2 + … + xn
x1 + x2 + … + xn = x1 × x2 × … × xn
Principiul dualitatii – daca in axiomele si proprietatile algebrei booleene se interschimba 0 cu 1 si + cu ×, sistemul de axiome ramane acelasi, in afara unor permutari.
Verificarea proprietatilor se poate face cu ajutorul tabelelor de adevar si cu observatia ca doua functii sunt egale daca iau aceleasi valori in toate punctele domeniului de definitie. Prin tabelul de adevar se stabileste o corespondenta intre valorile de adevar ale variabilelor si valoarea de adevar a functiei.
Obs. Comutativitatea si asociativitatea pot fi extinse la un numar arbitrar, dar finit, de termeni, indiferent de ordinea lor.
1.4. Functii booleene
O functie f: Bn ® B, unde B = {0,1} se numeste functie booleana. Aceasta functie booleana y = f(x1, x2,…,xn) are drept caracteristica faptul ca atat variabilele cat si functia nu pot lua decat doua valori distincte, 0 sau 1. Functia va pune in corespondenta fiecarui element al produsului cartezian n dimensional, valorile 0 sau 1. Astfel de functii sunt utilizate pentru caracterizarea functionarii unor dispozitive (circuite) construite cu elemente de circuit avand doua stari (ex.: un intrerupator inchis sau deschis, un tranzistor blocat sau in conductie; functionarea unui astfel de circuit va fi descrisa de o variabila booleana xi).
1.4.1. Functii booleene elementare
Revenim la forma generala a unei functii booleene de n variabile:
y = f(x1, x2,…,xn)
Domeniul de definitie este format din m = 2n puncte. Deoarece in fiecare din aceste puncte functia poate lua doar valorile 0 si 1 rezulta ca numarul total al functiilor booleene de n variabile este N = 2m.
Vom considera in continuare functiile elementare de 1 variabila. Pentru n = 1 avem m = 2 si N = 4. Functia are forma y = f(x) si cele 4 forme ale ei se gasesc in tabelul urmator:
fi x |
0 |
1 |
Reprezentare |
Denumire |
f0 |
0 |
0 |
0 |
Constanta 0 |
f1 |
0 |
1 |
x |
Variabila x |
f2 |
1 |
0 |
x |
Negatia lui x |
f3 |
1 |
1 |
1 |
Constanta 1 |
La fel se pot realiza toate functiile cu ajutorul unor functii de baza. Acestora le vor corespunde si niste circuite logice elementare, cu ajutorul carora se poate realiza practic orice tip de circuit. Tinand cont de faptul ca circuitele logice de comutatie au 2 stari stabile LOW (L) si HIGH (H), asignand lui L ¬ 0 si lui H ¬ 1 se poate intocmi un tabel al functiilor elementare.
Denumire |
Functie |
Simbol |
Tabel de adevar |
Tabel de definitie |
Inversor – NOT |
f = x |
x
f = x |
x f
0 1
1 0 |
x f
L H
H L |
Poarta SI – AND |
f = x1 × x2 |
x1
x2
f=x1×x2 |
x1 x2 f
0 0 0
0 1 0
1 0 0
1 1 1 |
x1 x2 f
L L L
L H L
H L L
H H H |
Poarta SAU – OR |
f = x1 + x2 |
x1
x2
f=x1+x2 |
x1 x2 f
0 0 0
0 1 1
1 0 1
1 1 1 |
x1 x2 f
L L L
L H H
H L H
H H H |
Poarta SI-NU – NAND |
f = x1 × x2 |
x1
x2
f=x1×x2 |
x1 x2 f
0 0 1
0 1 1
1 0 1
1 1 0 |
x1 x2 f
L L H
L H H
H L H
H H L |
Poarta SAU-NU – NOR |
f = x1 + x2 |
x1
x2
f=x1+x2 |
x1 x2 f
0 0 1
0 1 0
1 0 0
1 1 0 |
x1 x2 f
L L H
L H L
H L L
H H L |
SAU EXCLUSIV – XOR |
f = x1 + x2 |
x1
x2
f=x1 + x2 |
x1 x2 f
0 0 0
0 1 1
1 0 1
1 1 0 |
x1 x2 f
L L L
L H H
H L H
H H L |
COINCIDENTA |
f = x1 × x2 |
x1
x2
f=x1 × x2
=x1 + x2 |
x1 x2 f
0 0 1
0 1 0
1 0 0
1 1 1 |
x1 x2 f
L L H
L H L
H L L
H H H |
1.4.2. Reprezentarea functiilor booleene
Exista doua moduri de reprezentare a functiilor booleene: grafica si analitica.
Modalitati grafice - se caracterizeaza printr-o reprezentare intuitiva, usor de retinut, dar sunt inadecvate pentru functii booleene cu un numar de variabile mai mare decat 4;
2. Modalitati analitice - sunt mai greoaie, dar permit metode automate, deci algoritmi de simplificare a functiei; se folosesc in general pentru functii booleene cu numarul variabilelor mai mare decat 5.
Modalitati de reprezentare grafica
Modalitatile de reprezentare grafica sunt: tabel de adevar, diagrama Karnaugh, schema logica, diagrama de timp.
Tabel de adevar – se marcheaza intr-un tabel corespondenta dintre valorile de adevar ale variabilelor de intrare si valoarea de adevar a functiei, in fiecare punct al domeniului de definitie.
Pentru o functie cu n variabile de intrare vom avea 2n combinatii.
Exista situatii in care, pentru anumite combinatii ale variabilelor de intrare, valoarea functiei nu este specificata. Aceste functii se numesc incomplet definite. In tabel, in locul in care functia nu este specificata, se noteaza cu “X”. Daca o functie booleana este incomplet definita pentru “m” combinatii ale variabilelor de intrare se pot defini 2m functii noi prin alegerea arbitrara a valorilor incomplet definite.
Diagrama Karnaugh
O diagrama Karnaugh pentru o functie booleana de n variabile se deseneaza sub forma unui patrat sau dreptunghi impartit in 2n compartimente. Fiecare compartiment este rezervat unui termen canonic al functiei, respectiv unuia dintre varfurile cubului n dimensional din reprezentarea geometrica a functiei (2n n-uple ale functiei).
Diagrama Karnaugh este organizata astfel incat doua compartimente vecine pe o linie sau pe o coloana corespund la doi termeni canonici care difera numai printr-o singura variabila, care apare in unul adevarata, iar in celalalt negata (la doua n-pluri adiacente). Se considera vecine si compartimentele aflate la capetele opuse ale unei linii, respectiv coloane.
Diagrama Karnaugh se noteaza fie indicand domeniul fiecarei variabile, fie indicand pe linie si coloana n-uple de zerouri si unitati corespondente unui compartiment din diagrama si ordinea variabilelor. Prima notatie se foloseste in cazul in care se reprezinta functia prin forma ei canonica sau normala. A doua notatie se foloseste in cazul in care functia se reprezinta prin tabel de adevar. Pentru a putea reprezenta usor functii exprimate in mod conventional prin indicii termenilor canonici se poate nota fiecare compartiment cu indicele termenului corespondent, tinand cont de o anumita ordine a variabilelor.
Exemple:
Diagrama Karnaugh pentru functia de 2 variabile:
f(x1, x2) = x1×x2 + x1×x2
| |
x2 x1 |
0 |
1 |
|
x2 x1 |
0 |
1 |
|
|
0 |
x1x2 |
x1x2 |
|
0 |
0 |
1 |
x2 |
1 |
x1x2 |
x1x2 |
|
1 |
1 |
0 |
x1
sau
x1
x2
Obs. Numerotarea liniilor si coloanelor se face in cod Gray (cod binar reflectat)
Cod binar direct |
Cod Gray |
0000 |
0000 |
0001 |
0001 |
0010 |
0011 |
|
