一分钟内预知市场走势的方向，闪电出手，把握战机！
Bulova algebra je deo matemati?ke logike - algebarska struktura koja sa?ima osnovu operacija I, ILI i NE kao i skup teorijskih operacija kao ?to su unija, presek i komplement. Za razliku od elementarne algebre, gde promenljive za vrednosti imaju brojeve, u Bulovoj algebri vrednosti promenljivih mogu biti samo ta?no i neta?no (istina i la?), ?to se obi?no ozna?ava sa 1 i 0, gde 1 predstavlja ta?no a 0 neta?no.
Bulova algebra je dobila naziv po tvorcu, D?ord?u Bulu, engleskom matemati?aru iz 19. veka.
Bulova algebra je, osim kao deo apstraktne algebre, izuzetno uticajna kao matemati?ki temelj ra?unarskih nauka. Tako?e se koristi u teoriji skupova i statistici.
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:
x y x∧y x∨y 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1 x ?x 0 1 1 0 Tablice 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:
x y x NOR y x NAND y x ⊕ y 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0
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.
Osnovni postulati:
- Komutativnost
- x V y = y V x
- x Λ y = y Λ x
- Distributivnost
- x V (y Λ z) = (x V y) Λ (x V z)
- x Λ (y V z) = (x Λ y) V (x Λ z)
- Neutralni elementi
- 0 V x = x
- 1 Λ x = x
- Komplementacija
- x V ?x = 1
- x Λ ?x = 0
Ostali identiteti:
- Asocijativnost
- (x V y) V z = x V (y V z)
- (x Λ y) Λ z = x Λ (y Λ z)
- De Morganove teoreme
- ?(x V y) = ?x Λ ?y
- ?(x Λ y) = ?x V ?y
- Zakon nule
- x V 1 = 1
- x Λ 0 = 0
- Zakon idempotencije
- x V x = x
- x Λ x = x
- Zakon apsorpcije
- x V (x Λ y) = x
- x Λ (x V y) = x
Neprazan skup B na kome su definisane dve binarne operacije "∨" (zbir, disjunkcija, ili) i "∧" (proizvod, konjunkcija, i) je Bulova algebra ako va?e slede?e aksiome:
- A1. Komutativnost: Za bilo koja dva elementa a,b ∈ B va?i:
- (a) a V b = b V a,
- (b) a Λ b = b Λ a;
- A2. Asocijativnost: Za bilo koja tri elementa a,b,c ∈ B va?i:
- (a) (a V b) V c = a V (b V c),
- (b) (a Λ b) Λ c = a Λ (b Λ c);
- A3. Distributivnost: Za bilo koja tri elementa a,b,c ∈ B va?i:
- (a) a V (b Λ c) = (a V b) Λ (a V c),
- (b) a Λ (b V c) = (a Λ b) V (a Λ c);
- A4. Postojanje neutralnih elemenata: U skupu B postoje dva elementa 0 i 1 (0 <> 1) takva da za svako a ∈ B va?i:
- (a) a V 0 = a,
- (b) a Λ 1 = a;
- A5. Egzistencija komplementa: Za svaki element a ∈ B postoji element ?a (komplement) tako da je:
- (a) a V ?a = 1,
- (b) a Λ ?a = 0;
Neprazan skup B na kome su definisane dve binarne operacije "V" (zbir, disjunkcija, ili), "Λ" (proizvod, konjunkcija, i) i jedna unarna operacija "?" (negacija, komplement, ne) je Bulova algebra ako va?e slede?e aksiome:
- A1. Komutativnost: Za bilo koja dva elementa a,b ∈ B va?i:
- (a) a V b = b V a,
- (b) a Λ b = b Λ a;
- A2. Asocijativnost: Za bilo koja tri elementa a,b,c ∈ B va?i:
- (a) (a V b) V c = a V (b V c),
- (b) (a Λ b) Λ c = a Λ (b Λ c);
- A3. Distributivnost: Za bilo koja tri elementa a,b,c ∈ B va?i:
- (a) a V (b Λ c) = (a V b) Λ (a V c),
- (b) a Λ (b V c) = (a Λ b) V (a Λ c);
- A4’. Apsortivnost: Za bilo koja dva elementa a,b ∈ B va?i:
- (a) a Λ (a V b) = a,
- (b) a V (a Λ b) = a;
- A5’. Za bilo koja dva elementa a,b ∈ B va?i:
- (a) (a Λ ?a) V b = b,
- (b) (a V ?a) Λ b = b;
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, 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.
- Brown Stephen, Vranesic Zvonko (2002), Fundamentals of Digital Logic with VHDL Design (2nd izd.), McGraw-Hill, ISBN 978-0-07-249938-4. See Section 2.5.
- Cori Rene, Lascar Daniel (2000), Mathematical Logic: A Course with Exercises, Oxford University Press, ISBN 978-0-19-850048-3. See Chapter 2.
- Dahn B. I. (1998), ?Robbins Algebras are Boolean: A Revision of McCune's Computer-Generated Solution of the Robbins Problem”, Journal of Algebra 208 (2): 526-532, DOI:10.1006/jabr.1998.7467.
- Givant Steven, Paul Halmos (2009), Introduction to Boolean Algebras, Undergraduate Texts in Mathematics, Springer Science Business Media, ISBN 978-0-387-40293-2.
- Halmos Paul (1963), Lectures on Boolean Algebras, Van Nostrand, ISBN 978-0-387-90094-0.
- Halmos Paul, Steven Givant (1998), Logic as Algebra, Dolciani Mathematical Expositions, 21, Mathematical Association of America, ISBN 978-0-88385-327-6.
- Huntington E. V. (1933), ?New sets of independent postulates for the algebra of logic”, Transactions of the American Mathematical Society (American Mathematical Society) 35 (1): 274-304, DOI:10.2307/1989325, JSTOR 1989325.
- Huntington E. V. (1933), ?Boolean algebra: A correction”, Transactions of the American Mathematical Society (American Mathematical Society) 35 (2): 557-558, DOI:10.2307/1989783, JSTOR 1989783.
- Mendelson Elliott (1970), Boolean Algebra and Switching Circuits, Schaum's Outline Series in Mathematics, McGraw-Hill, ISBN 978-0-07-041460-0.
- Monk J. Donald, R. Bonnet, ur. (1989), Handbook of Boolean Algebras, Elsevier, ISBN 978-0-444-87291-3. In 3 volumes. (Vol.1:. ISBN 978-0-444-70261-6., Vol.2:. ISBN 978-0-444-87152-7., Vol.3:. ISBN 978-0-444-87153-4.)
- Padmanabhan Ranganathan, Rudeanu Sergiu (2008), Axioms for lattices and boolean algebras, World Scientific, ISBN 978-981-283-454-6.
- Sikorski Roman (1966), Boolean Algebras, Ergebnisse der Mathematik und ihrer Grenzgebiete, Springer Verlag.
- Stoll R. R. (1963), Set Theory and Logic, W. H. Freeman, Reprinted by Dover Publications, 1979., ISBN 978-0-486-63829-4.
- James A. Anderson (2005), Diskretna matematika, CET, ISBN 86-7991-269-7.
