Булова алгебра

Булова алгебра је део математичке логике - алгебарска структура која сажима основу операција И, ИЛИ и НЕ као и скуп теоријских операција као што су унија, пресек и комплемент. Булова алгебра је добила назив по творцу, Џорџу Булу, енглеском математичару из 19. века. Булова алгебра је, осим као део апстрактне алгебре, изузетно утицајна као математички темељ рачунарских наука.

Дефиниција Булове алгебре

Дефиниција Булове алгебре полази од једног непразног скупа B који има најмање два елемента и на коме се уводе једна унарна (НЕ) операција и две бинарне (И и ИЛИ) операције, а за које важи известан број аксиома.

Дефиниција 1.

Непразан скуп B на коме су дефинисане две бинарне операције "V" (збир, дисјункција, или) и "Λ" (производ, конјункција, и) је Булова алгебра ако важе следеће аксиоме:

• А1. Комутативност: За било која два елемента a,b ∈ B важи:

(а) a V b = b V a,

(b) a Λ b = b Λ a;

• А2. Асоцијативност: За било која три елемента a,b,c ∈ B важи:

(а) (a V b) V c = a V (b V c),

(b) (a Λ b) Λ c = a Λ (b Λ c);

• А3. Дистрибутивност: За било која три елемента a,b,c ∈ B важи:

(а) a V (b Λ c) = (a V b) Λ (a V c),

(b) a Λ (b V c) = (a Λ b) V (a Λ c);

• А4. Постојање неутралних елемената: У скупу B постоје два елемента 0 и 1 (0 <> 1) таква да за свако a ∈ B важи:

(а) a V 0 = a,

(b) a Λ 1 = a;

• А5. Егзистенција комплемента: За сваки елемент a ∈ B постоји елемент ⌐a (комплемент) тако да је:

(а) a V ⌐a = 1,

(b) a Λ ⌐a = 0;

Дефиниција 2.

Непразан скуп B на коме су дефинисане две бинарне операције "V" (збир, дисјункција, или), "Λ" (производ, конјункција, и) и једна унарна операција "⌐" (негација, комплемент, не) је Булова алгебра ако важе следеће аксиоме:

• А1. Комутативност: За било која два елемента a,b ∈ B важи:

(а) a V b = b V a,

(b) a Λ b = b Λ a;

• А2. Асоцијативност: За било која три елемента a,b,c ∈ B важи:

(а) (a V b) V c = a V (b V c),

(b) (a Λ b) Λ c = a Λ (b Λ c);

• А3. Дистрибутивност: За било која три елемента a,b,c ∈ B важи:

(а) a V (b Λ c) = (a V b) Λ (a V c),

(b) a Λ (b V c) = (a Λ b) V (a Λ c);

• А4’. Апсортивност: За било која два елемента a,b ∈ B важи:

(а) a Λ (а V b) = a,

(b) a V (а Λ b) = a;

• А5’. За било која два елемента a,b ∈ B важи:

(а) (a Λ ⌐a) V b = b,

(b) (a V ⌐a) Λ b = b;

Принцип дуалности

Свака аксиома састоји се из два дела (а) и (b). Уочљиво је да се део (b) може добити ако операције V и Λ замене места и ако елементи 0 и 1 замене места. Стога, ако имамо неку теорему у Буловој алгебри, и ако смо извели њен доказ, тада заменом операција V и Λ и елемената 0 и 1 долазимо до нове, тзв. дуалне, теореме чији се доказ добија из доказа полазне теореме заменом операција V и Λ и елемената 0 и 1. Отуда произилази следећи принцип.

Принцип дуалности

Ако је нека једнакост теорема Булове алгебре, тада заменом операција V и Λ и елемената 0 и 1 у тој релацији долазимо до тачне једнакости. Та једнакост назива се дуална теорема дате теореме. Може се десити да овим поступком дођемо до полазне теореме, тј. да се наведеним променама полазна теорема не мења. За такву теорему кажемо да је самодуална.

Литература

• Brown Stephen, Vranesic Zvonko (2002), Fundamentals of Digital Logic with VHDL Design (2nd ed.), 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, ed. (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 .

Спољашње везе

Викимедијина остава има још мултимедијалних датотека везаних за: Булова алгебра

• Булова алгебра (енглески)
• Математика Булове алгебре (енглески)
• Булова алгебра и бинарна логика (српски)