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.

AksiomiUredi

Asocijativnost

 

 

'Komutativnost'

Binarni operator   i   na skupu B je komutativan

 

  (   )

Neutralni elementi

0 i 1 su neutralni element skupa B u odnosu na binarnu operaciju   i  

 

 

Inverzni element

 

 

Ako 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 algebraUredi

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 0 0
0 1 0
1 0 0
1 1 1
x y x+y
0 0 0
0 1 1
1 0 1
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 dualnostiUredi

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 algebreUredi

Teorema 1

1.  

2.  

Dokaz

1.  

2.  

Teorema 2

 

 

Dokaz

1. 

2. po principu dualnosti

Teorema 3

 

Dokaz

Iz aksime

 

 

zamjenom   sa   imamo

 

 

primjenom komutativnosti dobijamo  

 

dobijamo

 

Teorema 4

1.  

2.  

Teorema 5(De Morganova teorema)

 

 

Teorema 6

1. 

2.  

Dokaz

1.  

2. princip dualnosti Teorema 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  

IzvorUredi

MATEMATIČKA LOGIKA