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

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

Булова алгебра је добила назив по творцу, Џорџу Булу, енглеском математичару из 19. века.^[1]

Булова алгебра је, осим као део апстрактне алгебре, изузетно утицајна као математички темељ рачунарских наука. Такође се користи у теорији скупова и статистици.^[2]

Вредности

За разлику од елементарне алгебре, у којој у изразима користимо највише бројеве од 0 до 9, у Буловој алгебри користимо само истините вредности, односно, тачно и нетачно. Ове вредности можемо представити преко битова, тј. преко бројева 1 и 0. У Буловој алгебри се ови битови не понашају на начин на који смо навикли, односно, 1 + 1 никада не може бити 2.^[3]

Булова алгебра такође може да барата и функцијама. Вредности које користимо у овим функцијама морају бити из скупа {0, 1}.

Операције

Основне операције

• И (конјункција): означава се као x∧y или као x*y или као x AND y.
• ИЛИ (дисјункција): означава се као x∨y или као x+y или као x OR y.
• НЕ (негација): означава се као ¬x или као `x или као NOT x.

Операције се такође могу приказати преко таблица истинитости:

Таблице истинитости

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

Пошто се конјункција може изразити преко дисјункције и негације, видимо да су нам за рад потребне само две операције:

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

Наравно, важи и обрнуто:

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

Изведене операције

До сада смо видели да постоје само три Булове операције. То су биле основне операције, што значи да нам оне могу послужити као основа за друге, комплексније операције.

• x NOR y (нили)
• x NAND y (ни)
• x ⊕ y

Таблице истинитости за ове операције:

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

Прва операција, x NOR y, се зове нили. Комбинација две променљиве, ¬(x ∨ y), једнака је 1 ако и само ако су обе променљиве једнаке 0.

Друга операција, x NAND y, се зове ни. Комбинација две променљиве, ¬(x ∧ y), једнака је 0 ако и само ако су обе променљиве једнаке 1.

Трећа операција, x ⊕ y, или x XOR y, се зове експлицитно или. Комбинација две променљиве, x ⊕ y, је једнака 1 ако и само ако је тачно једна променљива једнака 1.^[4]

Закони и својства

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

Основни идентитети Булове алгебре

Основни постулати:

• Комутативност

x V y = y V x

x Λ y = y Λ x

• Дистрибутивност

x V (y Λ z) = (x V y) Λ (x V z)

x Λ (y V z) = (x Λ y) V (x Λ z)

• Неутрални елементи

0 V x = x

1 Λ x = x

• Комплементација

x V ⌐x = 1

x Λ ⌐x = 0

Остали идентитети:

• Асоцијативност

(x V y) V z = x V (y V z)

(x Λ y) Λ z = x Λ (y Λ z)

• Де Морганове теореме

⌐(x V y) = ⌐x Λ ⌐y

⌐(x Λ y) = ⌐x V ⌐y

• Закон нуле

x V 1 = 1

x Λ 0 = 0

• Закон идемпотенције

x V x = x

x Λ x = x

• Закон апсорпције

x V (x Λ y) = x

x Λ (x V y) = x

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

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

• А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 у тој релацији долазимо до тачне једнакости. Та једнакост назива се дуална теорема дате теореме.

Може се десити да овим поступком дођемо до полазне теореме, тј. да се наведеним променама полазна теорема не мења. За такву теорему кажемо да је самодуална.^[5]

Дијаграмске репрезентације

Венови дијаграми

Венови дијаграми су корисна алатка за представљање скупова и проучавање њихових операција. У њима су скупови представљени (у равни) унутрашњошћу кругова, пресецима кругова, унијама кругова и тако даље. Универзални скуп је представљен правоугаоником. На слици су приказана три Венова дијаграма и приказују конјункцију, дисјункцију и негацију:

Figure 2. Венови дијаграми за конјункцију, дисјункцију и негацију

Дијаграм 1 представља пресек два елемента, други представља унију истих, а трећи комплемент једног елемента.

За конјункцију, област у оба круга је осенчена да укаже да х ∧ у има вредност 1 када обе варијабле узимају вредност 1. Остали региони су остали неосенчени што приказује да х ∧ у има вредност 0 за остале три комбинације.

Други дијаграм представља дисјункцију х ∨ у сенчењем оних регија које леже унутар једног или оба круга. Трећи дијаграм представља комплемент ¬ х, што је демонстрирано сенчењем региона који није унутар круга.

Иако нисмо приказали Венов дијаграм за константе 0 и 1, који би био тривијалан, будући да су представљени, као светао и таман квадрат, од којих ниједан не садржи круг. Међутим, ми бисмо могли да убацимо круг за х у квадрате, и у том случају би сваки квадрат означавао функцију једног аргумента, х, која враћа исту вредност независно од променљиве х, што се зове константна функција. Што се тиче њихових излазних вредности, константе и константне се не могу разликовати. Разлика је у томе што константне не узимају аргументе, и зову се нуларне операције, док константне функције имају један аргумент, који се игнорише, што их чини унарним операцијама.

Венови дијаграми су од помоћи при визуелизацији закона. Закон комутативности за ∧ и ∨ може се лако видети из симетрије дијаграма: бинарна операција која није комутативна неће имати симетричне дијаграме јер би смењивање х и у имало ефекат одражавања дијаграма хоризонтално и сваки неуспех комутативности би се онда деловао као неуспех симетрије.

Идемпотенција ∧ ∨ може се визуализовати сједињавањем два круга и констатовањем да је осенчено подручје тада постаје цео круг, како за ∧ тако и за ∨.

Да бисмо визуализовали први закон апсорпције, х ∧ (х ∨ у) = х, почнимо са дијаграмом у средини за х ∨ у и приметимо да је део осенчене површине заједнички за круг х, цео круг х. За други закон апсорпције, х ∨ (х ∧ у) = х, почнимо са левим дијаграмом за х ∧ у и приметимо да сенчење комплетног х круга резултује тиме да је само на х круга осенчен, јер је претходно сенчење било унутар х круга.

Закон дупле негације се може видети допуњујући сенчење у трећем дијаграму за ¬ х, што осенчава х круг.

Да бисмо визуелно представили први Де Морганов закон, (¬ х) ∧ (¬ у) = ¬ (х ∨ у) , почнимо са средишњим дијаграмом за х ∨ у и комплементирајмо сенчење, тако да је само област изван оба круга осенчена, што је оно што десна страна закона описује. Резултат је исти као да смо осенчили оанј регион који је и изван круга х и изван круга у, односно конјункцију њихових спољашњости, што је оно што је лева страна закона описује .

Други Де Морганов закон, (¬ х) ∨ (¬ у) = ¬ (х ∧ у), функционише на исти начин само са два дијаграма који се смењују.

Први закон комплементације, ¬ х ∧ х = 0, каже да се унутрашњост и спољашњост х круга не преклапају. Други закон комплементације, х ∨ ¬ х = 1 , каже да се све налази или унутар или изван круга х.

Дигитална логичка кола

Дигитална логика је примена Булове алгебре од 0 и 1 у електронском хардверу који се састоји од логичких кола везаних тако да формирају дијаграм кола. Свако коло имплементира Булову операцију, и шематски је приказано кроз облик који указује на операцију. Облици повезани са колима за Конјункције (И-кола), дисјункције (ИЛИ-кола), и комплементи (инвертори) су следећи.^[6]

Логичке капије

Комплемент се представља помоћу инверторског кола. Троугао означава операцију која једноставно копира улаз на излаз, мали круг на излазу означава инверзију која комплементира улаз. По конвенцији стављање таквог круга на било ком порту значи да сигнал који пролази кроз овај порт се комплементира, било да улазни или излазни порт.

С обзиром да постоји осам начина означавања три порта И-кола или ИЛИ-кола са инверторима, та конвенција пружа широк спектар могућих Булових операција које су реализоване као кола која су тако украшена. Нису све комбинације су ипак разликују : било које обележавање И - кола са инверторима реализује исту Булову операцију као и супротно обележавање ИЛИ-кола (дати порт И-кола је означен инвертором ако и само ако одговарајући порт ИЛИ није тако означен). Ово следи из Де Морганових закона.

Ако комплементирамо све портове на сваком колу, и заменимо И – кола и ИЛИ - кола, као на слици испод 4, добијамо исту операцију од које смо почели, илуструјући како Де Морганове законе тако и принцип дуалности.

Де Морганове капије

Због упарујуће идентификације кола преко принципа дуалности, иако 16 шематских симбола могу бити произведени из два основна бинарна кола И и ИЛИ тако што се њиховим портовима додели инвертор, они представљају само осам логичких операција, првенствено оних са непарним бројем јединица у истинитосној таблици. Укупно постоји 16 бинарних Булових операција, других осам су ​​оне са парним бројем јединица у њиховим истинитосним таблицама. Константа 0, коју посматрамо као бинарну операцију која игнорише оба своја улаза, нема јединица. Шест операција х, у, ¬ х , ¬ у, х ⊕ у, х ≡ у имају две јединице, и константа 1 има четири јединице.

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

Термин "алгебра" означава како предмет алгебре, тако и објекат алгебре, односно алгебарске структуре.

Овај одељак се бави математичким објектима који се називају Булове алгебре, дефинисане у пуној општости, као било који модел Булових закона. Почињемо са специјалним случајем појма, који је дефинисан без референцирања на законе, а онда дајемо формалну дефиницију за генерални случај.

Референце

1. Boole, George (2003) [1854]. An Investigation of the Laws of Thought. Prometheus Books. ISBN 978-1-59102-089-9.
2. Givant, Steven; Halmos, Paul (2009). Introduction to Boolean Algebras. Undergraduate Texts in Mathematics, Springer. ISBN 978-0-387-40293-2.
3. Halmos, Paul (1963). Lectures on Boolean Algebras. van Nostrand.
4. O'Regan, Gerard (2008). A brief history of computing. Springer. стр. 33. ISBN 978-1-84800-083-4.
5. Steven R. Givant; Paul Richard Halmos (2009). Introduction to Boolean algebras. Springer. стр. 21—22. ISBN 978-0-387-40293-2.
6. Shannon, Claude (1949). „The Synthesis of Two-Terminal Switching Circuits”. Bell System Technical Journal. 28: 59—98. doi:10.1002/j.1538-7305.1949.tb03624.x.

Литература

• Brown Stephen, Vranesic Zvonko (2002), Fundamentals of Digital Logic with VHDL Design (2nd изд.), 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.
• Paul, Halmos (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, JSTOR 1989325, doi:10.2307/1989325.
• Huntington, E. V. (1933), „Boolean algebra: A correction”, Transactions of the American Mathematical Society, American Mathematical Society, 35 (2): 557—558, JSTOR 1989783, doi:10.2307/1989783.
• Elliott, Mendelson (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, ур. (1989), Handbook of Boolean Algebras, Elsevier, ISBN 978-0-444-87291-3. In 3 volumes. (Vol.1. 978-0-444-70261-6.., ., .)
• Padmanabhan Ranganathan, Rudeanu Sergiu (2008), Axioms for lattices and boolean algebras, World Scientific, ISBN 978-981-283-454-6.
• Roman, Sikorski (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.
• Anderson, James A. (2005), Дискретна математика, ЦЕТ, ISBN 978-86-7991-269-5.

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

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