1 referat.ro

download referat

ELEMENTE DE ALGEBRĂ BOOLEANĂ 1.1. Generalităţi Transferul, prelucrarea şi păstrarea datelor numerice sau nenumerice în interiorul unui calculator se realizează prin intermediul circuitelor de comutare. Aceste circuite se caracterizează prin faptul că prezintă două stări stabile care se deosebesc calitativ între ele. Stările sunt puse în corespondenţă cu valorile binare “0” şi “1” sau cu valorile logice “adevărat” şi “fals” (din acest motiv se mai numesc şi circuite logice). Pornind de la aceste considerente, un domeniul al logicii matematice, (ştiinţa care utilizează metode matematice în soluţionarea problemelor de logică) numit “algebra logicii” şi-a găsit o largă aplicare în analiza şi sinteza circuitelor logice. Algebra logicii operează cu propoziţii care pot fi adevărate sau false. Unei propoziţii adevărate i se atribuie valoarea “1”, iar unei propoziţii false i se atribuie valoarea “0”. O propoziţie nu poate fi simultan adevărată sau falsă, iar două propoziţii sunt echivalente d.p.d.v. al algebrei logice, dacă simultan ele sunt adevărate sau false. Propoziţiile pot fi simple sau compuse, cele compuse obţinându-se din cele simple prin legături logice de tipul conjuncţiei , disjuncţiei  sau negaţiei . Bazele algebrei logice au fost puse de matematicianul englez George Boole (1815-1864) şi ca urmare ea se mai numeşte şi algebră booleană. Ea a fost concepută ca o metodă simbolică pentru tratarea funcţiilor logicii formale, dar a fost apoi dezvoltată şi aplicată şi în alte domenii ale matematicii. În 1938 Claude Shannon a folosit-o pentru prima dată în analiza circuitelor de comutaţie. 1.2. Definirea axiomatică a algebrei booleene Algebra booleană este o algebră formată din: - elementele 0,1; - 2 operaţii binare numite SAU şi SI, notate simbolic + sau  şi  sau ; - 1 operaţie unară numită NU negaţie, notată simbolic sau . Operaţiile se definesc astfel: SI SAU NU 0  0 = 0 0 + 0 = 0 0 = 1 0  1 = 0 0 + 1 = 1 1 = 0 1  0 = 0 1 + 0 = 1 1  1 = 1 1 + 1 = 1 Axiomele algebrei booleene sunt următoarele: Fie o mulţime M compusă din elementele x1, x2,…xn, împreună cu operaţiile  şi +. Această mulţime formează o algebră dacă: 1) Mulţimea M conţine cel puţin 2 elemente distincte x1  x2 (x1,x2 M); 2) Pentru  x1  M, x2  M avem: x1 + x2  M şi x1  x2  M 3) Operaţiile  şi + au următoarele proprietăţi: 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 faţă de cealaltă x1  (x2 + x3) = x1  x2 + x1  x3 x1 + (x2  x3) = (x1 + x2)  (x1 + x3) 4) Ambele operaţii admit câte un element neutru cu proprietatea: x1 + 0 = 0 + x1 = x1 x1  1 = 1  x1 = x1 unde 0 este elementul nul al mulţimii, iar 1 este elementul unitate al mulţimii. 5) Dacă mulţimea M nu conţine decât două elemente, acestea trebuie să fie obligatoriu elementul nul 0 şi elementul unitate 1; atunci pentru  x  M există un element unic notat cu x cu proprietăţile: x  x = 0 principiul contradicţiei x + x = 1 principiul terţului exclus x este inversul elementului x. În definirea axiomatică a algebrei s-au folosit diferite notaţii. În tabelul următor se dau denumirile şi notaţiile specifice folosite pentru diverse domenii: Matematică Logică Tehnică Prima lege de compoziţie x1 + x2 Disjuncţie x1  x2 SAU x1 + x2 A doua lege de compoziţie x1  x2 Conjuncţie x1  x2 SI x1  x2 Elementul invers x Negare x NU x