Algebra booleana - Pasii de definire ai algebrei booleene

Algebra booleana

Introducere

Cunostintele matematice de baza necesare pentru studiul proiectarii logice a sistemelor digitale este algebra booleana. Fondatorul algebrei booleene a fost George Bool, un matematician care a trait in secolul XIX in Anglia (1815 - 1864). In 1854 a publicat cartea ,,Investigarea legilor gandirii,, (An investigation into the laws of thought), in care a introdus un concept nou si anume al logicii cu doua valori , in care se presupune ca oricarui obiect i se poate atribui un atribut caracterizat de numai doua valori: adevarat sau fals . Desi a fost contemporan cu Charles Babbage si cu faimosul matematician De Morgan , aspectele practice ale algebrei propuse nu au fost inca observate. Dupa aproape un secol, mai precis in 1938 , Claude Shannon a facut legatura intre algebra propusa de Bool si dispozitivele folosite in practica , adica releele. Ideea de baza a fost dezvoltata de Shannon prin constructia unui sistem matematic care permite reprezentarea si analiza circuitelor logice. Un dispozitiv logic este un tip special de sistem caracterizat de faptul ca fiecare cantitate a activitatii sale este luata in considerare la intervale discrete de timp si poate lua valori ce apartin uneia dintre doua multimi disjuncte de valori. In principiu, valorile efective nu au importanta, relevant fiind doar in care dintre cele doua multimi se afla. Teza de doctorat a lui Shannon, scrisa la MIT (Massachusetts Institute of Technology) a fost fundamentata in domeniul proiectarii logice. Ideea principala a tezei a fost publicata in 1938 in ,,Transactions of American Institute of Electrical Engineers,, volumul 57. Titlul articolului a fost : '' Analiza simbolica a releelor si a circuitelor logice ''. Trebuie de asemenea mentionat ca in fosta USSR doi cercetatori tratau in acelasi an 1938 acelasi subiect . Acestia sunt Shestakoff si Gavriloff . Scoala romaneasca a avut o contributie majora in domeniu prin activitatea profesorului Grigore C. Moisil.

Pentru a descrie, analiza si proiecta circuite digitale trebuie mai intai sa ne familiarizam cu suportul matematic necesar domeniului. Dezvoltarea unui sistem algebric care implementeaza ideile propuse de George Bool apartine lui Shannon, Shestakoff si Gavriloff care au descris in 1938 suportul matematic necesar operarii circuitelor logice. Folosirea din ce in ce mai frecventa a circuitelor digitale are la baza imbunatatirea tehnicilor de fabricare dar si existenta unor metode teoretice care sa permita proiectarea circuitelor. In acest capitol este prezentat suportul matematic legat de algebra booleana, astfel incat orice inginer il poate folosi pentru proiectarea sistemelor digitale. Algebra booleana are multe alte domenii in care este folosita, cum ar fi teoria multimilor sau logica matematica.

Pasii de definire ai algebrei booleene

Pentru definirea algebrei booleene trebuie parcursi urmatorii pasi :

definirea unei multimi de notiuni primitive .

definirea unei multimi de postulate (axiome) bazate pe notiunile primitive.

In general, toate sistemele axiomatice au la baza expresii fundamentale denumite postulate sau axiome. Multimea de postulate trebuie sa indeplineasca trei conditii :

a)      consistenta ( postulatele nu trebuie sa se auto-contrazica )

b)      independenta (postulatele nu trebuie sa fie dependente unele de altele )

c)      simplitate ( postulatele nu trebuie sa fie complexe )

Postulatele specifice algebrei booleene au fost studiate de E.V. Huntington.

Definirea unei multimi de teoreme care reprezinta relatii simple intre elementele algebrei. Toate demonstratiile trebuie facute pe baza postulatelor.

Observatie : In mod evident multimea teoremelor depinde de multimea postulatelor; este posibil ca pentru o algebra un anumit postulat sa fie teorema in timp ce in alta algebra teorema respectiva sa fie postulat.

Numarul minim de postulate folosit pentru definirea algebrei booleene este patru, dar din punct de vedere practic este preferata folosirea unui numar mai mare de postulate pentru a permite folosirea lor mai usoara in algebra definita. In cle ce urmeaza vor fi prezentate doua versiuni ale algebrei booleene :

Algebra booleana de tip Harrison

Algebra booleana de tip Mowle.

Aceste doua versiuni ale algebrei booleene au la baza doua multimi apropiate de postulate.

Se va arata ca nu este respectata totdeauna conditia de independenta , ceea ce inseamna ca unele dintre postulate sunt demonstrate cu ajutorul altora.

In general , conditiile de independenta si simplicitate trebuie modificate asatfel incat sa se poata folosi usor .

Algebra booleana de tip Harrison

Definitie : O Algebra booleana este un sistem algebric , notat cu B reprezentat astfel :

B = <E, +, , 0, 1, >

unde:

'' E '' este o multime finita care contine cel putin doua elemente

''+'' este operatorul binar denumit ''suma logica'' , ''or logic'' , ''OR'' sau ''disjunctie'' , ce defineste o operatie pe multimea E , astfel incat pentru toate perechile

''^.'' este operatorul binar denumit ''produs logic'' , ''AND logic'', ''AND'' sau ''conjunctie'' ce defineste o operatie pe multimea E , astfel incat pentru toate perechile

''0'' si ''1'' sunt doua constante ce apartin multimii E ,

Simbolurile 0 si 1 arata ca si numerele binare , dar ele nu au valoare numerica , ele sunt doar doua simboluri din multimea E.

Se defineste o relatie de echivalenta R reprezentata de simbolul ''='' care indeplineste trei proprietati de baza ; daca R este o relatie de echivalenta atunci R este

a)      reflexiva

b)      simetrica , sau daca atunci

c)      tranzitiva , sau daca si atunci

Principiul substitutiei este adevarat; daca doua expresii A si B sunt echivalente , legea substitutiei permite inlocuirea valorii lui B cu A in toate expresiile in care apare A fara a fi afectata validitatea expresiilor rezultate.

Notatia cu paranteze este folosita.

Sunt definite urmatoarele noua postulate, definite :

Asociativitatea lui OR :

Asociativitatea lui AND :

comutativitatea lui OR :

comutativitatea lui AND :

existenta identitatii unice fata de OR :

astfel incat

existenta identitatii unice fata de AND astfel incat

distributivitatea lui OR fata de AND

distributivitatea lui AND fata de OR

existenta complementului ( elementul invers sau simetric ):

astfel incat

Observatie : 1) Notatia uzuala pentru produsul logic este , astfel incat simbolul ''.'' este frecvent omis din expresiile booleene.

2) Multe din postulatele prezentate sunt similare cu cele din algebra dar pot fi observate si diferente ca si

3) Aceasta multime de postulate este folosita pe larg in practica datorita simplitatii ; in continuare se defineste un sistem algebric bazat pe algebra de tip Harrison.

Teoreme ale algebrei booleene

Teoremele care vor fi prezentate sunt etichetate urmat de numele acesteia si de demonstratie . Fiecare pas al demonstratiei este marcat de postulatul folosit sau de o teorema anterior demonstrata.

) Teorema de idempotenta a lui OR :

Demonstratie :

) Teorema de idempotenta a lui AND

Demonstratie :

) Agresivitatea lui 1 asupra lui OR

Demonstratie :

) Agresivitatea lui 0 asupra lui AND :

Demonstratie:

) Prima teorema a absortiei :

Demonstratie :

sau mai simplu

) A doua teorema a absortiei

Demonstratie:

sau mai simplu :

) Complementul ( simetricul ) unui element este unic

Demonstratie:

Conform cu A9 , pentru orice element exista un element , denumit si complementul lui ''a'' astfel incat :

Trebuie sa demonstram ca elementul '' a '' este unic. Pentru a demonstra acest lucru folosim metoda reducerii la absurd ( '' reductio ad absurdum '' ).

Astfel, presupunem ca elementul '' a '' are doua complemente si astfel incat avem simultan :

Atunci :

Deci , cele doua componente presupuse diferite sunt identice ( )

Observatie : Aceasta teorema se mai numeste si legea complementului mic .

) Relatia intre constantele 0 si 1 : Complementul lui 0 este 1 si complementul lui 1 este 0 . Deci : si

Demonstratie :

Pentru inceput demonstram ca . Din A5 avem :

Consideram sI, dupa inlocuire obtinem ; dar din A9 rezulta ca si deci (proprietatea de inlocuire )

Sa demonstram ca . Din A6 avem : . Consideram si, dupa inlocuire obtinem ; dar din A9 rezulta ca si deci (proprietatea de inlocuire ) .

Definitie : O algebra booleana este degenerata daca identitatea de multiplicare este egala cu cea de adunare, adica .

Proprietate : Se poate demonstra ca orice algebra booleana nedegenerata trebuie sa contina un numar par de elemente.

) Teorema de identitate :

Daca pentru toate avem atunci

Demonstratie : Prin substitutia lui b din a prima relatie in prima obtinem :

Din T5 obtinem : , deci

Aceasta proprietate reprezinta un procedeu simplu de testare a faptului ca doua expresii booleene sunt echivalente.

Presupunand ca si sunt doua expresii booleene diferite daca dupa calcularea lui si obtinem expresia atunci putem trage concluzia ca ( este echivalent cu ).

Exemplu : Se dau doua expresii booleene ce depind de trei variabile

Pentru a calcula daca sunt echivalente trebuie sa calculam si :

Deoarece si , putem spune ca este echivalent cu , notat.

) Legea complementelor :

Daca pentru toate perechile avem : atunci

Demonstratie :

Demonstratia este evidenta , ca o reformulare a axiomei A9 . Aceasta proprietate reprezinta un procedeu simplu de testare a faptului ca doua expresii sunt una complementul celeilalte. Fie si cele doua expresii . Se calculeaza si ; Daca egal cu 1 si egal cu 0 atunci .

Exemplu :

Consideram doua expresii booleene :

Pentru a determina daca calculam si

Deci , deoarece si atunci

) Teorema involutiei

Demonstratie : Vom aplica legea identitatii astfel incat trebuie sa demonstram ca :

Astfel,

si

Deci

) Prima teorema a lui De Morgan

Demonstratie : Vom folosi legea complementului si deci va trebui sa demonstram ca :

Astfel :

Deci :

) A doua teorema a lui De Morgan

Demonstratie : Folosim legea complementului, trebuie sa demonstram ca :

Ceea ce inseamna :

Deci :

) Generalizarea primei teoreme a lui De Morgan

Unde:

este folosit ca simbol pentru OR generalizat pentru n operanzi

este folosit ca simbol pentru AND generalizat pentru n operanzi

Demonstratie : Prin inductie avem :

( in concordanta cu T12 )

Prin inductie, presupunem ca relatia este adevarata pentru pasul :

Ce se va intampla pentru n ?

In concordanta cu A1:

Notam suma dintre paranteze cu A :

Astfel, reducem expresia la :

Dar s-a presupus ca relatia este adevarata pentru , atunci :

q.e.d.

) Generalizarea celei de-a doua teoreme a lui De Morgan

Unde:

este folosit ca simbol pentru OR generalizat pentru n operanzi

este folosit ca simbol pentru AND generalizat pentru n operanzi

Demonstratie : Folosim aceeasi procedura de inductie :

( in concordanta cu T13 )

Prin inductie, presupunem ca relatia este adevarata pentru :

Ce se va intampla pentru n ?

In concordanta cu A2 :

Notam :

Atunci expresia se reduce la :

Dar s-a presupus ca relatia este adevarata pentru , atunci :

q.e.d.

) A treia teorema a absorbtiei ( legea absorbtiei )

Demonstratie :

) A patra teorema a absorbtiei ( legea absorbtiei )

Demonstratie:

) Generalizarea celei de-a treia teoreme a absorbtiei

Unde reprezinta operatorul OR generalizat.

Demonstratie:

Prin inductie :

( in concordanta cu T16 )

Ce se va intampla pentru n ?

Grupam primii termeni ( in concordanta cu A1 ) :

Prin inductie , pasul este adevarat, deci putem inlocui expresia din paranteze :

Notam suma :

Daca negam pe A si aplicam teorema lui De Morgan generalizata avem :

Deci in final obtinem :

q.e.d.

) Generalizarea teoremei a patra a absorbtiei :

Unde reprezinta operatorul AND generalizat.

Demonstratie :

Prin inductie :

(in concordanta cu T17)

Ce se intampla pentru n ?

La pasul , putem inlocui termenul dintre parantezele patrate prin si obtinem :

Notam

Prin negarea lui A si aplicarea teoremei lui De Morgan generalizata :

Deci in final obtinem :

, q.e.d.

) Cea de-a 20-a teorema a absorbtiei ( teorema de consens )

Demonstratie :

Termenul a fost absorbit.

Observatie : Termenul produs se numeste termen de consens .

) A sasea teorema de absorbtie

Aceasta teorema se numeste teorema de consens duala . Teorema de consens este utila in procesul de minimizare a functiilor booleene.

Demonstratie :

Termenul a fost absorbit.

) Teorema speciala de complementare :

Demonstratie :

) A saptea teorema de absorbtie

Demonstratie :

) A opta teorema de absorbtie :

Demonstratie :

Algebra booleana de tip Mowle

Definitie : O algebra booleana este un sistem algebric B definit de tripletul :

, unde

E este o multime finita de elemente

''+'' este un operator binar definit pe E astfel incat pentru orice este unic si se numeste ''OR'' , ''suma logica'' , ''disjunctie'', ''adunare logica''.

'' . '' este un operator binar definit pe E astfel incat pentru orice este unic si se numeste '' AND '' , '' inmultire logica '', '' disjunctie ''.

O relatie de echivalenta notata prin simbolul '' = '' este definita , in care toate proprietatile oricarei relatii de echivalenta sunt valide.

Principiul inlocuirii este respectat.

Se poate folosi notatia cu paranteze.

Sunt definite urmatoarele postulate :

) Existenta complementului :

Multimea E este formata din cel putin doua elemente diferite ( exista cel putin doua elemente x si y care sunt diferite ).

Teoreme specifice algebrei Mowle

) Elementele 0 si 1 sunt unice .

Demonstratie : In conformitate cu A5 , elementul identitate '' 0 '' este definit pentru orice element din E :

Presupunem prin absurd ca exista doua elemente zero, notate si , ambele apartinand lui E , astfel incat urmatoarele relatii trebuie sa fie adevarate :

pentru orice element din E

In particular, poate fi sau , astfel incat daca vom considera atunci obtinem:

in timp ce daca vom considera , atunci :

In conformitate cu A3 putem scrie prima relatie :

In conformitate cu principiul substitutiei rezulta ca : , deci elementul '' 0 '' trebuie sa fie unic.

Similar , in conformitate cu A6 :

exista un element identitate 1 astfel incat .

Aplicand principiul reducerii la absurd ,presupunem ca exista doua elemente '' 1 '' , notate cu si , astfel incat :

pentru orice element x din E

Aceste relatii sunt adevarate pentru orice x, inclusiv pentru valorile particulare si

Deci : daca

daca

In conformitate cu A4 putem scrie cea de-a doua relatie ca : . In conformitate cu principiul substitutiei rezulta ca , deci elementul '' 1 '' este unic.

) Teorema asociativitatii :

Demonstratie : Notam termenul din stanga cu u si termenul din dreapta cu v :

Calculam produsul logic folosind doua metode de calcul. Rezultatul primei metode va fi u , in timp ce a doua metoda va da rezultatul v . Cu ajutorul principiului substitutiei rezulta ca . In timpul calculului se folosesc teoremele T23 si T24 din paragraful anterior.

Pasul 1 :

Pasul 2 :

Deci conduce la egalitatea q.e.d.

Similar, se poate arata ca operatorul AND este asociativ :

Principiul dualitatii

Examinarea postulatelor de baza si a teoremelor ne arata ca acestea sunt organizate in perechi. Explicatia este data de o proprietate generala numita '' Principiul dualitatii sau '' Dualitate '' .

Se poate arata ca orice algebra booleana B corespunde unei alte algebre booleene denumita algebra booleana astfel incat pentru fiecare postulat si teorema se poate asocia un postulat sau o teorema duala.

Acest principiu spune ca daca se poate demonstra ca doua expresii sunt echivalente folosind o secventa de postulate, atunci expresiile duale sunt echivalente prin aplicarea secventei de postulate duale.

In esenta, pentru fiecare proprietate booleana care a fost demonstrata, proprietatea duala este de asemenea adevarata fara sa fie nevoie de demonstratie.

Exemple simple de postulate duale :

Exemple de teoreme :

Teoremele lui De Morgan

Prima si a doua teorema de absorbtie :

A treia si a patra teorema de absorbtie :

Algebra comutationala

Algebra comutationala reprezinta un caz particular al algebrei booleene, in care multimea E are numai doua elemente distincte . Ea corespunde unui sistem algebric boolean cu doua valori.

Definitie : Algebra comutationala , notata , este urmatorul sistem algebric :

Unde simbolurile '' + '' si '' . '' sunt operatori binari denumiti OR si AND , definiti pe elementele din multimea E si care verifica urmatoarele tabele de adevar:

Operatia OR 

Operatia AND

Simbolul '' ' '' este folosit ca operator unar si reprezinta operatia de complement sau negatie (operatia NOT ) , definita pe E si care verifica urmatoarea tabela de adevar :

Operatia NOT

Operatorul OR ( suma logica ) asupra a doua elemente din E ( care sunt doua variabile ) notat este egal cu 1 daca valoarea lui x sau y sau amandoua este 1. Operatorul AND ( produs logic ) asupra a doua elemente din E ( care sunt doua variabile ) notat este egal cu 1 daca si numai daca valorile lui x si y sunt 1. Desi arata ca o inmultire binara , nu este, deoarece 0 si 1 sunt constante booleene si nu numere binare .

Uneori operatia OR este notata si cu simbolul iar operatia AND este notata cu simbolurile .

Operatia NOT , cunoscuta si ca negare , invers sau complement se poate nota fie prin

'' ' '' sau printr-o bara superioara . Deci , este ( NOT x ) iar este (NOT y ) .

O poarta logica ce indeplineste operatia AND se numeste poarta AND si este reprezentata simbolic prin :

Relatia intrare - iesire pentru poarta AND este data de urmatoarea tabela de adevar :

Poarta logica ce indeplineste operatia OR se numeste poarta OR si este reprezentata simbolic prin :

Relatia de intrare - iesire pentru poarta OR este data de urmatoarea tabela de adevar :

Poarta logica ce indeplineste operatia NOT este reprezentata simbolic prin :

Relatia de intrare - iesire pentru un inversor este :

Observatie : Termenul de ''tabela de adevar '' vine dintr-o tabela similara folosita pentru '' adevarul '' sau '' falsitatea '' unei afirmatii in toate conditiile posibile.

Toate postulatele si teoremele prezentate anterior raman adevarate in .

Demonstratia poate fi facuta prin metode tabelare (cu tabelele de adevar). Aceasta metoda se numeste metoda inductiei perfecte si este foarte simpla deoarece se bazeaza pe tabelele de adevar definite pentru cele trei operatii fundamentale +, , ' , definite anterior si pe un numar finit de combinatii ce reprezinta domeniul pentru orice multime de n variabile binare.

Exemple :

Teoremele lui De Morgan

Ultimele doua randuri sunt identice , deci si

Teorema de consens

Ultimele doua randuri sunt identice , deci expresiile analizate sunt adevarate.

Importanta algebrei comutationale este cruciala deoarece se bazeaza pe faptul ca marea majoritate a circuitelor logice care sunt fabricate in prezent sunt caracterizate de doua stari stabile - una corespunde lui '' 0 '' logic iar cealalta lui '' 1 '' logic. Avand in vedere ca retelele logice sunt obtinute prin interconectarea de porti logice elementare putem spune ca algebra comutationala reprezinta suportul matematic fundamental in analiza si sinteza sistemelor digitale .

Relatia dintre algebra comutationala si algebra booleana

Proprietate : Algebra comutationala este izomorfa fata de o multime putere a unei multimi care este un singleton.

Demonstratie : Fie o multime putere a unei multimi care este un singleton. contine doar doua elemente : . Pe aceasta multime definim cele trei operatii specifice teoriei multimilor , si anume : intersectia , reuniunea si complementul , conform cu urmatoarele tabele :

In algebra comutationala , am definit AND, OR, NOT astfel :

Definim o functie bijectiva care arata functiile : si

In urma compararii tabelelor de adevar putem trage concluzia ca este izimorfic cu , adica

Generalizare : Orice algebra booleana este izomorfica cu o anume algebra pe o multime putere. Se stie ca orice multime putere contine elemente daca multimea initiala contine elemente ; deci , numarul de elemente ale unei algebre booleene este totdeauna o putere a lui 2 . Cu alte cuvinte , pentru o algebra booleana exista un intreg pozitiv astfel incat numarul de elemente din este .

Exemplu : Sa consideram algebra booleana cu 4 elemente :

Aceasta algebra este descrisa de urmatoarele tabele de adevar :

Consideram multimea putere , unde . Membrii lui sunt multimea vida , submultimile si universul. Pe se definesc cele trei operatii de baza specifice teoriei multimilor :

Ca si in cazul anterior , se defineste o functie bijectiva care determina urmatoarele functii :

Prin compararea tabelelor se poate spune ca este izomorfic cu , adica :

Proprietate : Daca si sunt doua algebre booleene cu acelasi numar de elemente ,atunci si sunt izomorfice.

Proprietate : Produsul cartezian al multimilor si sunt algebre booleene.

Corolar : Orice algebra booleana este izomorfa cu un anume produs de algebre comutationale .

Exemple :

1). Algebra este izomorfa cu

Conform cu definitiile :

Produsul cartezian este :

Daca este o functie bijectiva astfel incat :

Atunci :

Grafic :