Bulova algebra

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.

Vrednosti

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}.

Operacije

Osnovne operacije

• 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:

Tablice 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

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)

Izvedene operacije

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.

Zakoni i svojstva

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 identiteti Bulove algebre

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

Definicija 1.

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;

Definicija 2.

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;

Princip dualnosti

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.

Dijagramske reprezentacije

Venovi dijagrami

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:

Figure 2. Venovi dijagrami za 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 logička kola

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.

Bulove algebre

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.

Literatura

• 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 .

Spoljašnje veze

Bulova algebra na Wikimedijinoj ostavi

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