Definirea axiomatica a algebrei booleene, Functii boleene, Reprezentarea

Definirea axiomatica a algebrei booleene

Algebra booleana este o algebra formata din:

elementele

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 = 1

0 0 + 1 = 1 1 = 0

1 1 + 0 = 1

1 1 + 1 = 1

Axiomele algebrei booleene sunt urmatoarele:

Fie o multime M compusa din elementele x₁, x₂,.x_n, impreuna cu operatiile si +. Aceasta multime formeaza o algebra daca:

Multimea M contine cel putin 2 elemente distincte x₁ x₂ (x₁,x₂I M);

Pentru x₁ I M, x₂ I M avem:

x₁ + x₂ I M si x₁ x₂ I M

Operatiile si + au urmatoarele proprietati:

a.     sunt comutative

x₁ x₂ = x₂ x₁

x₁ + x₂ = x₂ + x₁

b.    sunt asociative

x₁ (x₂ x₃) = (x₁ x₂) x₃

x₁ + (x₂ + x₃) = (x₁ + x₂) + x₃

c.     sunt distributive una fata de cealalta

x₁ (x₂ + x₃) = x₁ x₂ + x₁ x₃

x₁ + (x₂ x₃) = (x₁ + x₂) (x₁ + x₃)

Ambele operatii admit cate un element neutru cu proprietatea:

x₁ + 0 = 0 + x₁ = x₁

x₁ x₁ = x₁

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:

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

x₁ (x₁ + x₂) = x₁

x₁ + (x₁ x₂) = x₁

Proprietatile elementelor neutre

x x 1 = x

x + 0 = x           x + 1 = 1

Formulele lui De Morgan

x₁ x₂ = x₁ + x₂

x₁ + x₂ = x₁ x₂

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:

x₁ x₂ x_n = x₁ + x₂ + . + x_n

x₁ + x₂ + . + x_n = x₁ x₂ x_n

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: Bⁿ B, unde B = se numeste functie booleana. Aceasta functie booleana y = f(x₁, x₂,.,x_n) 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 x_i).

1.4.1. Functii booleene elementare

Revenim la forma generala a unei functii booleene de n variabile:

y = f(x₁, x₂,.,x_n)

Domeniul de definitie este format din m = 2ⁿ 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 = 2^m.

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:

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.

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 2ⁿ 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 2^m 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 2ⁿ 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(x₁, x₂) = x₁ x₂ + x₁ x₂

x₁

sau

x₁

x₂

Obs. Numerotarea liniilor si coloanelor se face in cod Gray (cod binar reflectat)

Diagrama Karnaugh pentru functia de 3 variabile:

y = f(x₁,x₂,x₃)

Domeniul de definitie este format din 2³ = 8 puncte si reprezinta varfurile unui cub cu latura 1:

x₁

001 101

011 111

000 100 x₃

010 110

x₂

Diagramele Karnaugh corespunzatoare pot fi reprezentate astfel:

x₂

x₃

sau

Diagrama Karnaugh pentru functia de 4 variabile:

y = f(x₁,x₂,x₃,x₄)

x₃

Prin sageti am marcat vecinatatile punctului de coordonate 0010.

4) Diagramele Karnaugh pentru functii de mai mult de 4 variabile se construiesc din diagrame de 4 variabile considerate ca diagrame elementare.

Schema logica - reprezentare cu ajutorul simbolurilor circuitelor logice.

Diagrama de timp - reprezentare utila pentru studiul unor forme tranzitorii de hazard in circuitele logice. Se reprezinta functii logice in a caror evolutie intervine timpul.

Exemplu f = x₁ x₂