Creeaza.com - informatii profesionale despre


Cunostinta va deschide lumea intelepciunii - Referate profesionale unice
Acasa » referate » matematica
Algebra booleana - Pasii de definire ai algebrei booleene

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

1

1

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 :

A B

C

0

1

0

1





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 :

A B

C

0

1

0

1





Poarta logica ce indeplineste operatia NOT este reprezentata simbolic prin :

Relatia de intrare - iesire pentru un inversor este :

A

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

a

b

0 1 1

0 0 1



a.b




a

b

0 1 1

1 0 1



a+b




Ultimele doua randuri sunt identice , deci si

Teorema de consens

a

b

c

0 0 0 1 1 1 1

0 1 1 0 0 1 1

1 0 1 0 1 0 1

a.b

b.c

0 0 0 0 0 1 1

1 0 1 0 0 0 0


1 0 1 0 0 1 1

1 0 1 0 0 1 1

a

b

c

0 0 0 1 1 1 1

0 1 1 0 0 1 1

1 0 1 0 1 0 1

a+b

b+c

0 1 1 1 01 1 1


1 1 1 0 1 1 1

0 1 1 0 0 1 1

0 1 1 0 0 1 1

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 :

S

S

S

S S

S



S

S

C

S

S

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

1

1

1

1

0

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 :

a b 1

a

b

0 0 0

a 0 a

0 b b

a b 1

a b 1

a

b

a b 1

a a 1 1

b 1 b 1


a b 1

1 b a 0

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

A B I

A

B

I

A B I

A A I I

B I B I

I I I I

A B I

A

B

I

A A

B B

A B I

C

A B I

I B A

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 :

 

Algebra booleana cu 8 elemente este izomorfica cu

Conform cu definitia :

Produsul cartezian este :

Functia bijectiva se obtine astfel incat :

In , operatiile de baza AND, OR ,NOT sunt definite de urmatoarele tabele de adevar :

a

b

c

d

e

f

a

a

a

a

a

b

b

b

b

b

c

c

c

c

c

d

a

b

d

a

b

d

e

a

c

a

e

c

e

f

b

c

b

c

f

f

a

b

c

d

e

f

a

b

c

d

e

f

a

b



c

d

e

f

a

a

a

d

e

d

e

b

b

d

b

f

f

c

c

e

f

c

e

f

d

d

d

d

d

e

e

e

e

e

f

f

f

f

f

a b c d e f 1

1 f e d c b a 0

Izomorfismul dintre si poate fi exprimat in mod grafic in felul urmator :

 


10. Calculul propozitiilor

O propozitie este o expresie declarativa care poate fi ,'adevarata'' sau ,'falsa'', dar niciodata ambele.

Exemple de propozitii :

"Temperatura este de 20 de grade" sau

"Suma lui 2 cu 3 face 4"

Fiecarei propozitii ii asociem o variabila notata cu o litera ( P,Q,R ) care are valoarea T daca propozitia este adevarata si are valoarea F daca este falsa.

Exista multe modalitati de a lucra cu propozitii pentru a forma propozitii noi . Aceste operatii atribuie propozitiei rezultat o valoare determinata de valorile de adevar ale propozitiilor din care a fost construita. Aceasta investigare poarta numele de calculul propozitiilor .

Negarea este cel mai simplu exemplu de operatie.

Noi propozitii pot fi obtinute din cele existente.

Sa consideram propozitiile : "Soarele straluceste" si "Soarele nu straluceste". Este evident ca daca prima propozitie este adevarata atunci cea de-a doua este falsa si viceversa .

O propozitie este considerata a fi negatia alteia daca atunci cand una este falsa cealalta este adevarata (sau viceversa) , deci negarea unei propozitii , notate sau este denumita simplu negare. Daca P este T atunci este F, sau daca P este F atunci este T .

Doua propozitii si pot fi combinate pentru a forma noi propozitii.

De exemplu , daca reprezinta propozitia :

= "Temperatura este mai mare de 10 grade"

iar = "Umiditatea este mai mare de 50 % " , atunci putem forma o noua propozitie :

" Temperatura este mai mare de 10 grade si umiditatea este mai mare de 50 % " legand cele doua propozitii prin conectorul AND .

In general , conjunctia lui si , notata este propozitia P and Q ; aceasta propozitie este adevarata daca atat cat si sunt adevarate si este falsa daca una dintre ele este falsa. Propozitiile pot fi combinate prin conectorul OR .

De exemplu, propozitiile anterioare combinate conduc la urmatoarea propozitie noua : "Temperatura este mai mare de 10 grade sau umiditatea este mai mare de 50 %".

In general , disjunctia lui si se noteaza cu si reprezinta propozitia ,' P sau Q sau amandoua in care formularea ,' sau amandoua ,' este omisa de obicei iar conectorul OR este definit ca un OR inclusiv.

Din aceasta definitie putem spune ca propozitia este adevarata daca sau sau amandoua sunt adevarate si este falsa daca oricare dintre si sunt false.

Conjunctia si disjunctia lui si sunt prezentate in tabelul urmator. In loc de simbolurile "0" si "1" folosim simbolurile T si F ( true si false ) .

P Q

F F

F

F

F T

T

F

T F

T

F

T T

T

T

Pentru negare,folosim tabelul urmator :

P

T F

F T

Exista doua tipuri de propozitii pe care trebuie sa le mentionam : propozitiile totdeauna false sau propozitiile ZERO si propozitiile totdeauna adevarate sau propozitiile UNU .

Analogia dintre calculul propozitiilor si algebra booleana este in acest moment aparenta. De fapt, acestea sunt sisteme algebrice izomorfe.

Legatura dintre algebra booleana, calculul propozitiilor , teoria multimilor si teoria retelelor de porti electronice

Algebra booleana apare din concepte care tin de alte domenii ale algebrei : teoria multimilor, calculul propozitiilor, teoria multimilor partial ordonate, etc.

In tabelul urmator sunt prezentate analogiile intre notiunile primitive specifice algebrei booleene , teoria multimilor, calculul propozitiilor, si teoria comutationala .

Algebra booleana

Teoria multimilor

Calculul propozitiilor

Teoria combinationala

Reprezentare

Element

Multime

Propozitie

Terminal

Operatia SAU

Reuniune

Conectorul SAU

Poarta logica

SAU

Operatia SI

Intersectie

Conectorul

SI

Poarta logica

SI

Operatia NOT

Complementul

multimii

Conectorul

NOT

Poarta inversoare

Elementul 0

Multimea

vida

Propozitie falsa

Simbol logic atribuit uneia dintre cele doua valori ale semnalului

 

Elementul 1

Universul

Propozitie adevarata

Simbol logic atribuit uneia dintre cele doua valori ale semnalului

Postulatele lui Huntington

Studiul sistemelor axiomatice legate de proiectarea logica au determinat crearea unei multimi de postulate cunoscute sub numele de Postulatele lui Huntington .

Aceste postulate pot fi folosite pentru evaluarea altor sisteme; aceste sisteme care indeplinesc criteriile stabilite de aceste postulate poarta numele de sisteme Huntington .

In momentul in care un sistem respecta criteriile stabilite prin postulatele lui Huntington, in mod automat toate teoremele referitoare la sistemele Huntington pot fi aplicate noului sistem. Astfel, se propune o algebra booleana care se testeaza cu postulatele lui Huntington. Astfel, se pot folosi teoreme si proprietatile altor sisteme Huntington pentru noul nostru sistem. Algebra booleana , ca si alte sisteme axiomatice se bazeaza pe cativa operatori definiti pe o multime nedefinita de elemente. O MULTIME este o colectie de elemente care au proprietati comune, elementele sale fiind nevoie sa fie definite.

Asa cum s-a folosit pana acum , avem de-a face cu multimile , etc. 0 si 1 sunt simboluri speciale si nu au nici o conotatie numerica.

Operatorii sunt definiti ca reguli ce exprima rezultatul unei operatii pe doua elemente din multime.

In continuare prezentam postulatele lui Huntington :

O multime E este inchisa in raport cu un operator daca pentru toate perechile de elemente din E operatia specifica un rezultat unic (element) , care este de asemenea din E. In particular , operatorul '' + '' obtine rezultatul care este tot din E. Acelasi lucru se intampla si pentru operatorul '' . '' .

Existenta elementelor identitate :

2.1. Exista elementul in astfel incat pentru fiecare avem

2.2. Exista elementul in astfel incat pentru fiecare avem

Proprietatea de comutativitate.

3.1. Pentru orice pereche avem

3.2. Pentru orice pereche avem

Proprietatea de distributivitate :

4.1. Pentru orice triplet avem :

- legea distributiei lui '' + '' asupra lui '' . '' .

4.2. Pentru orice triplet avem :

- legea distributiei lui '' . '' asupra lui '' + '' .

Existenta elementului simetric :

Pentru orice exista un element , numit invers sau element simetric , ce corespunde lui , astfel incat si .

6) Exista cel putin doua elemente in astfel incat

nu este echivalent cu .

Se poate verifica simplu ca algebrele booleene prezentate verifica postulatele lui Huntington . Toate teoremele se pot demonstra matematic folosind postulatele. Astfel, dandu-se un nou sistem algebric se testeaza multimea postulatelor lui Huntington si daca sunt verificate atunci toate teoremele si proprietatile adevarate pot fi aplicate in noul sistem definit.







Politica de confidentialitate







creeaza logo.com Copyright © 2024 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Comentarii literare

ALEXANDRU LAPUSNEANUL COMENTARIUL NUVELEI
Amintiri din copilarie de Ion Creanga comentariu
Baltagul - Mihail Sadoveanu - comentariu
BASMUL POPULAR PRASLEA CEL VOINIC SI MERELE DE AUR - comentariu

Personaje din literatura

Baltagul – caracterizarea personajelor
Caracterizare Alexandru Lapusneanul
Caracterizarea lui Gavilescu
Caracterizarea personajelor negative din basmul

Tehnica si mecanica

Cuplaje - definitii. notatii. exemple. repere istorice.
Actionare macara
Reprezentarea si cotarea filetelor

Economie

Criza financiara forteaza grupurile din industria siderurgica sa-si reduca productia si sa amane investitii
Metode de evaluare bazate pe venituri (metode de evaluare financiare)
Indicatori Macroeconomici

Geografie

Turismul pe terra
Vulcanii Și mediul
Padurile pe terra si industrializarea lemnului



PROBLEME DE EXTREM IN GEOMETRIE SI FIZICA
Derivabilitate
Algoritm pentru aflarea coeficientilor unui polinom atunci cand se cunosc radacinile polinomului
NUMERE COMPLEXE SUB FORMA TRIGONOMETRICA
Ecuatiile lui Maxwell
Identitati trigonometrice
APLICATII DIN GEOMETRIA PONDERILOR COMPLEXE
Modelul Kaldor - Cadrul teoretic



Termeni si conditii
Contact
Creeaza si tu