Definirea axiomatica a algebrei booleene, Functii boleene, Reprezentarea referat






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 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:

a.     sunt comutative

x1 x2 = x2 x1

x1 + x2 = x2 + x1

b.    sunt asociative

x1 (x2 x3) = (x1 x2) x3

x1 + (x2 + x3) = (x1 + x2) + x3

c.     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 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 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 = 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



Reprezentare

Denumire

f0




Constanta 0

f1



x

Variabila x

f2



x

Negatia lui x

f3




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

1 0

0 0

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

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

1 0

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

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 1

1 0

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




x2      x1




x1x2

x1x2





x2


x1x2

x1x2





x1

sau

x1









x2

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





Cod binar direct

Cod Gray





































Diagrama Karnaugh pentru functia de 3 variabile:

y = f(x1,x2,x3)

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

x1


001 101

011 111


000 100 x3

010 110

x2



Diagramele Karnaugh corespunzatoare pot fi reprezentate astfel:

x2


x1 x2x3











x1






x3

sau






x3



x1x2 x3












x2

x1










Diagrama Karnaugh pentru functia de 4 variabile:

y = f(x1,x2,x3,x4)



x4




x1x2 x3x4

















x2

x1














x3

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 = x1 x2


x1




















x2




















f






















loading...









Copyright © Contact | Trimite referat


Ultimele referate adaugate
Mihai Beniuc
   - Mihai beniuc - „poezii"
Mihai Eminescu Mihai Eminescu
   - Mihai eminescu - student la berlin
Mircea Eliade Mircea Eliade
   - Mircea Eliade - Mioara Nazdravana (mioriţa)
Vasile Alecsandri Vasile Alecsandri
   - Chirita in provintie de Vasile Alecsandri -expunerea subiectului
Emil Girlenu Emil Girlenu
   - Dragoste de viata de Jack London
Ion Luca Caragiale Ion Luca Caragiale
   - Triumful talentului… (reproducere) de Ion Luca Caragiale
Mircea Eliade Mircea Eliade
   - Fantasticul in proza lui Mircea Eliade - La tiganci
Mihai Eminescu Mihai Eminescu
   - „Personalitate creatoare” si „figura a spiritului creator” eminescian
George Calinescu George Calinescu
   - Enigma Otiliei de George Calinescu - geneza, subiectul si tema romanului
Liviu Rebreanu Liviu Rebreanu
   - Arta literara in romanul Ion, - Liviu Rebreanu














loading...



Scriitori romani