Booleova algebra

Booleova algebra je dio matematičke logike - algebarska struktura koja sažima osnovu operacija I, ILI i NE kao i skup teorijskih operacija kao što su unija, presjek i komplement.

Booleova algebra je dobila naziv po autoru, engleskom matematičaru Georgeu Booleu, britanskom matematičaru iz 19. vijeka. Booleova algebra je, osim kao dio apstraktne algebre, izuzetno uticajna kao matematički temelj računarskih nauka.

Za razliku od elementarne algebre, u kojoj u izrazima koristimo najviše brojeve od 0 do 9, u Booleovoj algebri koristimo samo istinite vrijednosti, odnosno, tačno i netačno. Ove vrijednosti možemo predstaviti preko bitova, tj. preko brojeva 1 i 0. U Booleovoj algebri se ovi bitovi ne ponašaju na način na koji smo navikli, odnosno,  nikada ne može biti 2.
Booleova  algebra takođe može da barata i funkcijama. Vrijednosti koje koristimo u ovim funkcijama moraju biti iz skupa {0, 1}.

Definicija

Binarni operator na skupu elemenata B je pravilo po kome se svakom paru elemenata iz B pridružuje jedinstveni element iz
B.

Skup B je zatvoren u odnosu na neki binarni operator.  Taj binarni operator B svakom paru elemenata iz
B pridružuje jedinstven element koji pripada skupu B.

Neka su na skupu  definisane
unarna operacija  i binarne operacije   koje se nazivaju oduzimanje mnnoženje i sabiranje i to tako da za svako  vrijedi , gdje je  i za svako  vrijedi  i , gdje je . Skup B sa operacijama   i  predstavlja Bulovu algebru ako
operacije zadovoljavaju sljedeće aksiome.

Bulova algebra je algebarska struktura koja se sastoji od skupa elemenata B, dva binarna operatora  i  takva da su ispunjeni Hantingtonovi aksiomi iz 1904. god.

 Aksiomi 

Asocijativnost

Komutativnost'''

Binarni operator  i  na skupu B je komutativan

 (  )Neutralni elementi0 i 1 su neutralni element skupa B u odnosu na binarnu operaciju  i Inverzni elementAko su  i  dva binarna operatora na skupu B kaže se da je binarni operator   
distributivan u odnosu na binarni operator 

Postoje bar dva elementa  takva da je .

Ovo nisu jedini aksiomi pomoću kojih se definiše Bulova algebra.
To je moguće i pomoću Birkof-Bartijevih aksioma iz1970. god. Na osnovu izloženog vide se sličnosti Bulove algebre sa običnom algebrom ali su uočljive i razlike kao npr. ispunjenost aksioma u Bulovoj algebri

Potrebno je imati u vidu ove razlike posebno zbog toga što su simboli  i  dva binarna operatora Bulove algebre pozajmljena iz obične algebre. Postoji opasnost da se primjene neka pravila obične algebre koja ne važe u Bulovoj algebri.

Moguće je formirati više Bulovih algebri u zavisnosti od broja elemenata skupa B. Interesantna je dvovrednosna Bulova
algebra koju je uveo Senon 1938. god.
 Dvo-vrijednosna Bulova algebra 

Dvo-vrijednosna Booleova algebra je definisana na skupu od samo dva elementa 
Promjenljive dvo-vrijednosne Booleova algebre u označi
 uzimaju vrijednosti sa skupa B.
Pravila za dva binarna operatora  i  kao i za komplement operator definisana tabelarno

 x y x*y 0 00 0 1 0 1 0 0 1 1 1

 x y x+y 0 00 0 1 1 1 01 1 1 1
 x  0 1 1 0

Na skupu  zadana je Booleova algebra ako operacije zadovoljavaju aksiome Booleove algebre.

To se može dokazati uvrštavanjem svih mogućih kombinacija elemenata skupa  u relacije koje predstavljaju aksiome Booleove algebre i izračunavanjem vrijednosti saglasno datim tablicama za date operacije.

Postupak ćemo pokazati za relaciju

za zakon asocijativnosti za operaciju .
Provjeru treba izvršiti za  kombinacija vrijednosti tih elemenata koristeći tablicu za operaciju 

1. Kombinacija:

, , 

2. Kombinacija:

, , 

3. Kombinacija

, , 

4. Kombinacija:

, , 

5. Kombinacija:

, , 

6. Kombinacija

, , 

7. Kombinacija:

, , 

8. Kombinacija:

, , 

Na isti način bi se moglo dokazati da i ostale realicije u aksiomama Booleove algebre vrijede za navedene operacije.
Ovaj način dokazivanja se naziva metoda iscrpljivanja svih mogućih slučajeva ili perfektna indukcija.

Booleova algebra na skupu od dva elementa često se naziva prekidačka algebra.

Naziv dolazi od praktične primjene Booleove algebre na skupu od dva elementa za predstavljanje prekidačkih funkcija koje se koriste pri projektovanju prekidačkih mreža.

Za navedene operacije se u prekidačkoj algebri često koriste i nazivi negacija, disjunkcija i konjukcija.

 Princip dualnosti 

Princip dualnosti (dvojnosti) Algebarski izraz Booleove algebre ostaje u važnosti poslije promjene binarnih operatora i
neutralnih elemenata u njemu. Pošto su neutralni elementi jednaki sa elementima skupa B, to se ranije navedeni gornji
postupak sprovodi tako što se operatori  i  međusobno zamijene  1 sa 0 ili 0 sa 1

 Osnovne teoreme i osobine Booleove algebre Teorema 11. 

2. 

Dokaz

1. 

2. Teorema 2Dokaz

1.

2. po principu dualnostiTeorema 3Dokaz

Iz aksime

zamjenom  sa  imamo

primjenom komutativnosti dobijamo

dobijamoTeorema 41. 

2. Teorema 5(De Morganova teorema)Teorema 6 1.

2. 

Dokaz

1. 

2. princip dualnostiTeorema 7'''

Dokaz

iz aksiome

zamjenom  imamo

Kako je 0 neutralni elemenat za  to je jedino rješenje za  pa je to jedino rješenje koje zadovoljava 

Zamjenom  u navedenoj aksiomi imamo

Posto je 1 neutralni element za  to je jedino rješenje za 1 koje zadovoljava obe relacije 
Izvor
MATEMATIČKA LOGIKA


Kategorija:Algebarska logika