Booleova algebra

Izvor: Wikipedia

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

Definicija Bulove algebre[uredi - уреди]

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.

Definicija 1.[uredi - уреди]

Neprazan skup B na kome su definisane dve binarne operacije "V" (zbir, disjunkcija, ili) i "Λ" (proizvod, konjunkcija, i) je Bulova algebra ako važe sledeće aksiome:

(a) a V b = b V a,
(b) a Λ b = b Λ a;
(a) (a V b) V c = a V (b V c),
(b) (a Λ b) Λ c = a Λ (b Λ c);
(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.[uredi - уреди]

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[uredi - уреди]

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.

Princip dualnosti[uredi - уреди]

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.

Literatura[uredi - уреди]

  • 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), DOI:10.1006/jabr.1998.7467 .
  • Givant Steven, Paul Halmos (2009), Introduction to Boolean Algebras, 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, 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), DOI:10.2307/1989325 .
  • Huntington E. V. (1933), "Boolean algebra: A correction", Transactions of the American Mathematical Society (American Mathematical Society) 35 (2), DOI:10.2307/1989783 .
  • Mendelson Elliott (1970), Boolean Algebra and Switching Circuits, 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, Springer Verlag .
  • Stoll R. R. (1963), Set Theory and Logic, W. H. Freeman, Reprinted by Dover Publications, 1979., ISBN 978-0-486-63829-4 .

Vanjske veze[uredi - уреди]