Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  


AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Elemente de algebra booleana

c

+ Font mai mare | - Font mai mic





DOCUMENTE SIMILARE

Trimite pe Messenger
Tipuri abstracte de date
Manual de referinta C
Uniuni
IMPLEMENTAREA STIVELOR PRIN TIPUL TABLOU
Siruri de caractere
Explorari in grafuri
Implementarea cozilor prin tipul tablou
STRUCURA DE DATE DE TIP GRAF
Operatori de incrementare si decrementare
Memoria partajata

TERMENI importanti pentru acest document

Elemente de algebra booleana

Generalitati

Transferul, prelucrarea si pastrarea datelor numerice sau nenumerice in interiorul unui calculator se realizeaza prin intermediul circuitelor de comutare. Aceste circuite se caracterizeaza prin faptul ca prezinta doua stari stabile care se deosebesc calitativ intre ele. Starile sunt puse in corespondenta cu valorile binare “0” si “1” sau cu valorile logice “adevarat” si “fals” (din acest motiv se mai numesc si circuite logice). Pornind de la aceste considerente, un domeniul al logicii matematice, (stiinta care utilizeaza metode matematice in solutionarea problemelor de logica) numit “algebra logicii” si-a gasit o larga aplicare in analiza si sinteza circuitelor logice. Algebra logicii opereaza cu propozitii care pot fi adevarate sau false. Unei propozitii adevarate i se atribuie valoarea “1”, iar unei propozitii false i se atribuie valoarea “0”. O propozitie nu poate fi simultan adevarata sau falsa, iar doua propozitii sunt echivalente din punct de vedere al algebrei logice, daca simultan ele sunt adevarate sau false. Propozitiile pot fi simple sau compuse, cele compuse obtinandu-se din cele simple prin legaturi logice de tipul conjunctiei Ù, disjunctiei sau negatiei Ø




Bazele algebrei logice au fost puse de matematicianul englez George Boole (1815-1864) si ca urmare ea se mai numeste si algebra booleana. Ea a fost conceputa ca o metoda simbolica pentru tratarea functiilor logicii formale, dar a fost apoi dezvoltata si aplicata si in alte domenii ale matematicii. In 1938 Claude Shannon a folosit-o pentru prima data in analiza circuitelor de comutatie.

Definirea axiomatica a algebrei booleene

Algebra booleana este o algebra formata din:

elementele

Obs. Acestea se mai pot numi Adevarat (engl. True) respectiv Fals (engl. False), Pornit (engl. On) respectiv Oprit (engl. Off)

doua operatii binare numite SAU (OR engl.) notata simbolic + sau respectiv SI (AND engl.) notate simbolic prin sau Ù

operatie unara numita NU negatie, notata simbolic printr-o bara deasupra a ceea ce se neaga sau cu simbolul Ø

Operatiile se definesc astfel:

Si

Sau

Nu

Sau excusiv

Ø

Ø

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:

principiul contradictiei

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

Negare

Øx

NU

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

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

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:

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.

Tabele de adevar

Unei functii booleene cu n variabile ii putem asocia un tabel care are 2n + 1linii care corespund celor 2n combinatii posibile ale variabilelor, precum a n+1 coloane care reprezinta cele n variabile plus una care reprezinta valorile corespunzatoare ale functiei.

De exemplu pentru functia F(x,y)=x+y avem 2 vaiabile deci vom vrea un tabel cu 5 linii si 3 coloane

x

y

F(x,y)=x+y



In cazul care functia booleana este exprimata sub forma de expresie, pentru a ajunge la tabelul de adevar trebuie realizate mai multe calcule prin care sa ne dam seama care este tabelul de adevar corespunzator funtiiei date. De exempu functia: pentru a ajunge la tabelul de adevar trebuie sa realizam mai multe calcule intr-un mod asemanator unor calcule algebrice obisnuite numai ca folosind regulile si principiile algebrei booleene. Pentru ca in formularea functiei apare nagatul pentru z si pentru z in primul rand vom calcula acele valori apoi succesiv vom construi tabelul de adevar pentru funtia data. Pentru aceasta

x

y

z

F

a

b

c

d

e






Politica de confidentialitate



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 997
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2021 . All rights reserved

Distribuie URL

Adauga cod HTML in site