Bulova algebra

Za razliku od elementarne algebre, u kojoj u izrazima koristimo najviše brojeve od 0 do 9, u Bulovoj algebri koristimo samo istinite vrednosti, odnosno, tačno i netačno. Ove vrednosti možemo predstaviti preko bitova, tj. preko brojeva 1 i 0. U Bulovoj algebri se ovi bitovi ne ponašaju na način na koji smo navikli, odnosno, 1 + 1 nikada ne može biti 2.

Bulova algebra takođe može da barata i funkcijama. Vrednosti koje koristimo u ovim funkcijama moraju biti iz skupa {0, 1}.

• I (konjunkcija): označava se kao x∧y ili kao x*y ili kao x AND y.
• ILI (disjunkcija): označava se kao x∨y ili kao x+y ili kao x OR y.
• NE (negacija): označava se kao ¬x ili kao `x ili kao NOT x.

Operacije se takođe mogu prikazati preko tablica istinitosti:

Pošto se konjunkcija može izraziti preko disjunkcije i negacije, vidimo da su nam za rad potrebne samo dve operacije:

x ∧ y = ¬(¬x ∨ ¬y)

Naravno, važi i obrnuto:

x ∨ y = ¬(¬x ∧ ¬y)

Do sada smo videli da postoje samo tri Bulove operacije. To su bile osnovne operacije, što znači da nam one mogu poslužiti kao osnova za druge, kompleksnije operacije.

• x NOR y (nili)
• x NAND y (ni)
• x ⊕ y

Tablice istinitosti za ove operacije:

Prva operacija, x NOR y, se zove nili. Kombinacija dve promenljive, ¬(x ∨ y), jednaka je 1 ako i samo ako su obe promenljive jednake 0.

Druga operacija, x NAND y, se zove ni. Kombinacija dve promenljive, ¬(x ∧ y), jednaka je 0 ako i samo ako su obe promenljive jednake 1.

Treća operacija, x ⊕ y, ili x XOR y, se zove eksplicitno ili. Kombinacija dve promenljive, x ⊕ y, je jednaka 1 ako i samo ako je tačno jedna promenljiva jednaka 1.

Definicija Bulove algebre polazi od jednog nepraznog skupa B koji ima najmanje dva elementa i na kome se uvode jedna unarna (NE) operacija i dve binarne (I i ILI) operacije, a za koje važi izvestan broj aksioma.

Svaka aksioma sastoji se iz dva dela (a) i (b). Uočljivo je da se deo (b) može dobiti ako operacije V i Λ zamene mesta i ako elementi 0 i 1 zamene mesta. Stoga, ako imamo neku teoremu u Bulovoj algebri, i ako smo izveli njen dokaz, tada zamenom operacija V i Λ i elemenata 0 i 1 dolazimo do nove, tzv. dualne, teoreme čiji se dokaz dobija iz dokaza polazne teoreme zamenom operacija V i Λ i elemenata 0 i 1. Otuda proizilazi sledeći princip.

Ako je neka jednakost teorema Bulove algebre, tada zamenom operacija V i Λ i elemenata 0 i 1 u toj relaciji dolazimo do tačne jednakosti. Ta jednakost naziva se dualna teorema date teoreme. Može se desiti da ovim postupkom dođemo do polazne teoreme, tj. da se navedenim promenama polazna teorema ne menja. Za takvu teoremu kažemo da je samodualna.

Venovi dijagrami su korisna alatka za predstavljanje skupova i proučavanje njihovih operacija. U njima su skupovi predstavljeni (u ravni) unutrašnjošću krugova, presecima krugova, unijama krugova i tako dalje. Univerzalni skup je predstavljen pravougaonikom. Na slici su prikazana tri Venova dijagrama i prikazuju konjunkciju, disjunkciju i negaciju:

Dijagram 1 predstavlja presek dva elementa, drugi predstavlja uniju istih, a treći komplement jednog elementa.

Za konjunkciju, oblast u oba kruga je osenčena da ukaže da h ∧ u ima vrednost 1 kada obe varijable uzimaju vrednost 1. Ostali regioni su ostali neosenčeni što prikazuje da h ∧ u ima vrednost 0 za ostale tri kombinacije.

Drugi dijagram predstavlja disjunkciju h ∨ u senčenjem onih regija koje leže unutar jednog ili oba kruga. Treći dijagram predstavlja komplement ¬ h, što je demonstrirano senčenjem regiona koji nije unutar kruga.

Iako nismo prikazali Venov dijagram za konstante 0 i 1, koji bi bio trivijalan, budući da su predstavljeni, respektivno, kao svetao i taman kvadrat, od kojih nijedan ne sadrži krug. Međutim, mi bismo mogli da ubacimo krug za h u kvadrate, i u tom slučaju bi svaki kvadrat označavao funkciju jednog argumenta, h, koja vraća istu vrednost nezavisno od promenljive h , što se zove konstantna funkcija. Što se tiče njihovih izlaznih vrednosti, konstante i konstantne se ne mogu razlikovati. Razlika je u tome što konstantne ne uzimaju argumente, i zovu se nularne operacije, dok konstantne funkcije imaju jedan argument, koji se ignoriše, što ih čini unarnim operacijama.

Venovi dijagrami su od pomoći pri vizuelizaciji zakona. Zakon komutativnosti za ∧ i ∨ može se lako videti iz simetrije dijagrama: binarna operacija koja nije komutativna neće imati simetrične dijagrame jer bi smenjivanje h i u imalo efekat odražavanja dijagrama horizontalno i svaki neuspeh komutativnosti bi se onda delovao kao neuspeh simetrije.

Idempotencija ∧ ∨ može se vizualizovati sjedinjavanjem dva kruga i konstatatovanjem da je osenčeno područje tada postaje ceo krug, kako za ∧ tako i za ∨.

Da bismo vizualizovali prvi zakon apsorpcije, h ∧ (h ∨ u) = h, počnimo sa dijagramom u sredini za h ∨ u i primetimo da je deo osenčene površine zajednički za krug h, ceo krug h. Za drugi zakon apsorpcije, h ∨ (h ∧ u) = h, počnimo sa levim dijagramom za h ∧ u i primetimo da senčenje kompletnog h kruga rezultuje time da je samo na h kruga osenčen, jer je prethodno senčenje bilo unutar h kruga.

Zakon duple negacije se može videti dopunjujući senčenje u trećem dijagramu za ¬ h, što osenčava h krug.

Da bismo vizuelno predstavili prvi De Morganov zakon, (¬ h) ∧ (¬ u) = ¬ (h ∨ u) , počnimo sa središnjim dijagramom za h ∨ u i komplementirajmo senčenje, tako da je samo oblast izvan oba kruga osenčena, što je ono što desna strana zakona opisuje. Rezultat je isti kao da smo osenčili oanj region koji je i izvan kruga h i izvan kruga u, odnosno konjunkciju njihovih spoljašnjosti, što je ono što je leva strana zakona opisuje .

Drugi De Morganov zakon, (¬ h) ∨ (¬ u) = ¬ (h ∧ u), funkcioniše na isti način samo sa dva dijagrama koji se smenjuju.

Prvi zakon komplementacije, ¬ h ∧ h = 0, kaže da se unutrašnjost i spoljašnjost h kruga ne preklapaju. Drugi zakon komplementacije, h ∨ ¬ h = 1 , kaže da se sve nalazi ili unutar ili izvan kruga h.

Digitalna logika je primena Bulove algebre od 0 i 1 u elektronskom hardveru koji se sastoji od logičkih kola vezanih tako da formiraju dijagram kola. Svako kolo implementira Bulovu operaciju, i šematski je prikazano kroz oblik koji ukazuje na operaciju. Oblici povezani sa kolima za Konjunkcije (I-kola), Disjunkcije (ILI-kola), i Komplementi (invertori) su sledeći [16].

Komplement se predstavlja pomoću invertorskog kola. Trougao označava operaciju koja jednostavno kopira ulaz na izlaz, mali krug na izlazu označava inverziju koja komplementira ulaz. Po konvenciji stavljanje takvog kruga na bilo kom portu znači da signal koji prolazi kroz ovaj port se komplementira, bilo da ulazni ili izlazni port.

Sa obzirom da postoji osam načina označavanja tri porta I-kola ili ILI-kola sa invertorima, ta konvencija pruža širok spektar mogućih Bulovih operacija koje su realizovane kao kola koja su tako ukrašena. Nisu sve kombinacije su ipak razlikuju : bilo koje obeležavanje I - kola sa invertorima realizuje istu Bulovu operaciju kao i suprotno obeležavanje ILI-kola (dati port I-kola je označen invertorom ako i samo ako odgovarajući port ILI nije tako označen). Ovo sledi iz De Morganovih zakona.

Ako komplementiramo sve portove na svakom kolu, i zamenimo I – kola i ILI - kola, kao na slici ispod 4, dobijamo istu operaciju od koje smo počeli, ilustrujući kako De Morganove zakone tako i princip dualnosti.

Zbog uparujuće identifikacije kola preko principa dualnosti, iako 16 šematskih simbola mogu biti proizvedeni iz dva osnovna binarna kola I i ILI tako što se njihovim portovima dodeli invertor, oni predstavljaju samo osam logičkih operacija , prvenstveno onih sa neparnim brojem jedinica u istinitosnoj tablici. Ukupno postoji 16 binarnih Bulovih operacija, drugih osam su ​​one sa parnim brojem jedinica u njihovim istinitosnim tablicama. Konstanta 0, koju posmatramo kao binarnu operaciju koja igrnoriše oba svoja ulaza, nema jedinica. Šest operacija h, u, ¬ h , ¬ u, h ⊕ u, h ≡ u imaju dve jedinice, i konstanta 1 ima četiri jedinice.

Termin "algebra" označava kako predmet algebre, tako i objekat algebre, odnosno algebarske strukture. Ovaj odeljak se bavi matematičkim objektima koji se nazivaju Bulove algebre, definisane u punoj opštosti, kao bilo koji model Bulovih zakona. Počinjemo sa specijalnim slučajem pojma, koji je definisan bez referenciranja na zakone, a onda dajemo formalnu definiciju za generalni slučaj.

• Bulova algebra (engleski)
• Matematika Bulove algebre (engleski)
• Bulova algebra i binarna logika (srpski) Arhivirano 2015-04-24 na Wayback Machine-u