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, $1+1$ 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 $B=\left\{a,b,c...\right\}$ definisane unarna operacija $-$ i binarne operacije $+$ $*$ koje se nazivaju oduzimanje mnnoženje i sabiranje i to tako da za svako ${\overline {a}}\in B$ vrijedi ${\overline {a}}=b$, gdje je $b\in B$ i za svako $a,b\in B$ vrijedi $a+b=c$ i $a*b=c$, gdje je $c\in B$. 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

$a+(b+c)=(a+b)+c$

$a*(b*c)=(a*b)*c$

'Komutativnost'

Binarni operator $*$ i $+$ na skupu B je komutativan

$a+b=b+a$

$a*b=b*a$ ( $a,b\in B$ )

Neutralni elementi

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

$a+0=0+a=a$

$a*1=1$

Inverzni element

$a+{\overline {a}}=1$

$a*{\overline {a}}=0$

Ako su $*$ i $+$ dva binarna operatora na skupu B kaže se da je binarni operator $*$ distributivan u odnosu na binarni operator $+$

$a*(b+c)=(a*b)+(a*c)$

$a+(b*c)=(a+b)*(a+c)$

Postoje bar dva elementa $x,y\in B$ takva da je $x\neq y$.

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

$a+(b*c)=(a+b)*(a+c)$

$a+{\overline {a}}=1$

$a*{\overline {a}}=0$

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 $B=\left\{0,1\right\}$ Promjenljive dvo-vrijednosne Booleova algebre u označi $x,y,z$ 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	${\overline {x}}$
0	1
1	0

Na skupu $\left\{0,1\right\}$ zadana je Booleova algebra ako operacije zadovoljavaju aksiome Booleove algebre.

To se može dokazati uvrštavanjem svih mogućih kombinacija elemenata skupa $\left\{0,1\right\}$ u relacije koje predstavljaju aksiome Booleove algebre i izračunavanjem vrijednosti saglasno datim tablicama za date operacije.

Postupak ćemo pokazati za relaciju

$a+(b+c)=(a+b)+c$

za zakon asocijativnosti za operaciju $+$. Provjeru treba izvršiti za $2^{3}=8$ kombinacija vrijednosti tih elemenata koristeći tablicu za operaciju $+$

1. Kombinacija:

$a=0$, $b=0$, $c=0$

$a+(b+c)=(a+b)+c$

$0+(0+0)=(0+0)+0$

$0+0=0+0$

$0=0$

2. Kombinacija:

$a=0$, $b=0$, $c=1$

$a+(b+c)=(a+b)+c$

$0+(0+1)=(0+0)+1$

$0+1=0+1$

$1=1$

3. Kombinacija

$a=0$, $b=1$, $c=0$ $a+(b+c)=(a+b)+c$

$0+(1+0)=(0+1)+0$

$0+1=1+0$

$1=1$

4. Kombinacija:

$a=0$, $b=1$, $c=1$

$a+(b+c)=(a+b)+c$

$0+(1+1)=(0+1)+1$

$0+1=1+0$

$1=1$

5. Kombinacija:

$a=1$, $b=0$, $c=0$

$a+(b+c)=(a+b)+c$

$1+(0+0)=(1+0)+0$

$1+0=1+0$

$1=1$

6. Kombinacija

$a=1$, $b=0$, $c=1$

$a+(b+c)=(a+b)+c$

$1+(0+1)=(1+0)+1$

$1+1=1+1$

$1=1$

7. Kombinacija:

$a=1$, $b=1$, $c=0$

$a+(b+c)=(a+b)+c$

$1+(1+0)=(1+1)+0$

$1+1=1+0$

$1=1$

8. Kombinacija:

$a=1$, $b=1$, $c=1$

$a+(b+c)=(a+b)+c$

$1+(1+1)=(1+1)+1$

$1+1=1+1$

$1=1$

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 1

1. $x+x=x$

2. $x*x=x$

Dokaz

1. $x+x=(x+x)*1=(x+x)(x+{\overline {x}})=x+x*{\overline {x}}=x+0=x$

2. $x*x=x*x+0=x*x+x*{\overline {x}}=x(x+{\overline {x}})=x*1=x$

Teorema 2

$x+1=1$

$x*0=0$

Dokaz

1.$x+1=1(x+1)=(x+{\overline {x}})(x+1)=x+{\overline {x}}-1=x+{\overline {x}}=1$

2. po principu dualnosti

Teorema 3

${\overline {\overline {x}}}=x$

Dokaz

Iz aksime

$x+{\overline {x}}=1$

$x*{\overline {x}}=0$

zamjenom $x$ sa ${\overline {x}}$ imamo

${\overline {x}}+{\overline {\overline {x}}}=1$

${\overline {x}}*{\overline {\overline {x}}}=0$

primjenom komutativnosti dobijamo ${\overline {\overline {x}}}+{\overline {x}}=1$

${\overline {\overline {x}}}*{\overline {x}}=0$

dobijamo

${\overline {\overline {x}}}={\overline {x}}$

Teorema 4

1. $x+(y+z)=(x+y)+z$

2. $x*(y*z)=(x*y)*z$

Teorema 5(De Morganova teorema)

${\overline {x+y}}={\overline {x}}*{\overline {y}}$

${\overline {x*y}}={\overline {x}}+{\overline {y}}$

Teorema 6

1.$x+xy=x$

2. $x*(x+y)=x$

Dokaz

1. $x+x*y=x*1+x*y=x*(1+y)=x*(y+1)=x*1=x$

2. princip dualnosti Teorema 7 ${\overline {1}}=0$

${\overline {0}}=1$ Dokaz

iz aksiome

$a+{\overline {a}}=1$

$a*{\overline {a}}=0$

zamjenom $a=0$ imamo

$0+{\overline {0}}=1$

$0*{\overline {0}}=0$

Kako je 0 neutralni elemenat za $+$ to je jedino rješenje za ${\overline {0}}$ pa je to jedino rješenje koje zadovoljava ${\overline {0}}=1$

Zamjenom $a=1$ u navedenoj aksiomi imamo $1+{\overline {1}}=1$

$1*{\overline {1}}=0$

Posto je 1 neutralni element za $*$ to je jedino rješenje za 1 koje zadovoljava obe relacije ${\overline {1}}=0$

Izvor

MATEMATIČKA LOGIKA