Просмотр отдельных изменений

':''Эта статья об [[Алгебраическая система|алгебраической системе]]. О разделе математической логики, изучающем высказывания и операции над ними, см. [[Алгебра логики]].'' '''[[Буль, Джордж|Булевой]] алгеброй'''<ref>{{cite web|author=D. A. Vladimirov|date=2002|url=http://eom.springer.de/B/b016920.htm|title=Springer Online Reference Works - Boolean algebra|publisher=Springer-Verlag|accessdate=2010-08-04|lang=en}}</ref><ref>{{книга |автор = Владимиров Д. А. |часть = |заглавие = Булевы алгебры |оригинал = |ссылка = http://eqworld.ipmnet.ru/ru/library/books/Vladimirov1969ru.djvu |ответственный = |издание = |место = {{М.}} |издательство = «Наука» |год = 1969 |том = |страницы = 19 |страниц = |серия = |isbn = |тираж = }}</ref><ref>{{книга |автор = Кузнецов О. П., Адельсон-Вельский Г. М. |часть = |заглавие = Дискретная математика для инженера |оригинал = |ссылка = |ответственный = |издание = |место = {{М.}} |издательство = Энергоатомиздат |год = 1988 |том = |страницы = 58 |страниц = |серия = |isbn = |тираж = }}</ref> называется непустое [[множество]] ''A'' с двумя [[бинарная операция|бинарными операциями]] <math>\land</math> (аналог [[конъюнкция|конъюнкции]]), <math>\lor</math> (аналог [[дизъюнкция|дизъюнкции]]), [[унарная операция|унарной операцией]] <math>\lnot</math> (аналог [[отрицание|отрицания]]) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для всех ''a'', ''b'' и ''c'' из множества ''A'' верны следующие [[аксиома|аксиомы]]: {| cellpadding=5 |<math> a \lor (b \lor c) = (a \lor b) \lor c </math> |<math> a \land (b \land c) = (a \land b) \land c </math> | [[ассоциативность]] |- |<math> a \lor b = b \lor a </math> |<math> a \land b = b \land a </math> | [[коммутативность]] |- |<math> a \lor (a \land b) = a </math> |<math> a \land (a \lor b) = a </math> | законы поглощения |- |<math> a \lor (b \land c) = (a \lor b) \land (a \lor c) </math> |<math> a \land (b \lor c) = (a \land b) \lor (a \land c) </math> | [[дистрибутивность]] |- |<math> a \lor \lnot a = 1 </math> |<math> a \land \lnot a = 0 </math> | дополнительность |} {{Hider| title = В нотации &middot; + &macr;| hidden = 1 | title-style = text-align: left; | content-style = text-align: left; | content = <math>\begin{align} & a+(b+c)=(a+b)+c & a(bc)=(ab)c \\ & a+b=b+a & ab=ba \\ & a+ab=a & a(a+b)=a \\ & a+bc=(a+b)(a+c) & a(b+c)=ab+ac \\ & a+\bar{a}=1 & a\bar{a} = 0 \end{align}</math> }} Первые три аксиомы означают, что (''A'', <math>\land</math>, <math>\lor</math>) является [[Решётка (теория множеств)|решёткой]]. Таким образом, булева алгебра может быть определена как [[дистрибутивная решётка]], в которой выполнены две последние аксиомы. Структура, в которой выполняются все аксиомы, кроме предпоследней, называется [[псевдобулева алгебра|псевдобулевой алгеброй]]. == Некоторые свойства == Из аксиом видно, что наименьшим элементом является 0, наибольшим является 1, а дополнение ¬''a'' любого элемента ''a'' однозначно определено. Для всех ''a'' и ''b'' из ''A'' верны также следующие равенства: {| cellpadding=5 | <math> a \lor a = a</math>; |<math> a \land a = a </math>; | |- |<math> a \lor 0 = a </math>; |<math> a \land 1 = a </math>; | rowspan=2 | |- |<math> a \lor 1 = 1 </math>; |<math> a \land 0 = 0 </math>; |- |<math> \lnot 0 = 1 </math>; |<math> \lnot 1 = 0 </math>; | дополнение 0 есть 1 и наоборот |- |<math> \lnot (a \lor b) = \lnot a \land \lnot b</math>; |<math> \lnot (a \land b) = \lnot a \lor \lnot b</math>; | [[законы де Моргана]] |- | <math> \lnot \lnot a = a </math>. | | [[инволюция (математика)|инволютивность отрицания]] |} == Основные тождества == В данном разделе повторяются свойства и аксиомы, описанные выше с добавлением ещё нескольких. Сводная таблица свойств и аксиом, описанных выше: {| cellpadding=5 |<math> a \lor b = b \lor a </math>; |<math> a \land b = b \land a </math>. |1 [[коммутативность]] [[переместительность]] |- |<math> a \lor (b \lor c) = (a \lor b) \lor c </math>; |<math> a \land (b \land c) = (a \land b) \land c </math>. |2 [[ассоциативность]] [[сочетательность]] |- |3.1 конъюнкция относительно дизъюнкции <math> a \lor (b \land c) = (a \lor b) \land (a \lor c) </math> |3.2 дизъюнкция относительно конъюнкции <math> a \land (b \lor c) = (a \land b) \lor (a \land c) </math> |3 [[дистрибутивность]] [[распределительность]] |- |<math> a \lor \lnot a = 1 </math>; |<math> a \land \lnot a = 0 </math>. |4 [[комплементность]] [[дополнительность]] (свойства отрицаний) |- |<math> \lnot (a \lor b) = \lnot a \land \lnot b</math>; |<math> \lnot (a \land b) = \lnot a \lor \lnot b</math>. | 5 [[законы де Моргана]] |- |<math> a \lor (a \land b) = a </math>; |<math> a \land (a \lor b) = a </math>. | 6 законы поглощения |- |<math>a \lor(\lnot a \land b) = a \lor b</math>; |<math>a \land(\lnot a \lor b) = a \land b</math>. | 7 Блейка-Порецкого |- | <math> a \lor a = a</math>; |<math> a \land a = a </math>. | 8 [[Идемпотентность]] |- | <math> \lnot \lnot a = a </math>. | | 9 [[инволюция (математика)|инволютивность отрицания]] |- |<math> a \lor 0 = a </math>; |<math> a \land 1 = a </math>. | rowspan=3 | 10 свойства констант |- |<math> a \lor 1 = 1 </math>; |<math> a \land 0 = 0 </math>. |- | дополнение 0 есть 1 <math> \lnot 0 = 1 </math>; | дополнение 1 есть 0 <math> \lnot 1 = 0 </math>. |- | <math> (a \lor b)\land(\lnot a \lor b)=b</math>; |<math> (a \land b) \lor (\lnot a \land b)=b</math>. | 11 Склеивание |} См. также [[Алгебра логики#Свойства логических операций|Алгебра логики]] == Примеры == * Самая простая нетривиальная булева алгебра содержит всего два элемента, 0 и 1, а действия в ней определяются следующей таблицей: {| |- | width="80" | | {| border="1" cellpadding="4" cellspacing="0" |- ! &and; || 0 || 1 |- ! 0 | 0 || 0 |- ! 1 | 0 || 1 |} | | width="40" | | {| border="1" cellpadding="4" cellspacing="0" |- ! &or; || 0 || 1 |- ! 0 | 0 || 1 |- ! 1 | 1 || 1 |} | | width="40" | | {| border="1" cellpadding="4" cellspacing="0" |- ! a || 0 || 1 |- ! &not;a | 1 || 0 |} |} * Эта булева алгебра наиболее часто используется в [[логика|логике]], так как является [[точная модель|точной моделью]] классического [[исчисление высказываний|исчисления высказываний]]. В этом случае 0 называют ''ложью'', 1 — ''истиной''. Выражения, содержащие булевы операции и переменные, представляют собой высказывательные формы. * [[Алгебра Линденбаума — Тарского]] ([[фактормножество]] всех утверждений по отношению равносильности в данном исчислении с соответствующими операциями) какого-либо исчисления высказываний является булевой алгеброй. В этом случае истинностная оценка формул исчисления является [[гомоморфизм]]ом алгебры Линденбаума — Тарского в двухэлементную булеву алгебру. * Множество всех подмножеств данного множества ''S'' образует булеву алгебру относительно операций &or; := &cup; (объединение), &and; := &cap; (пересечение) и унарной операции дополнения. Наименьший элемент здесь — [[пустое множество]], а наибольший — всё ''S''. * Если ''R'' — произвольное [[кольцо (алгебра)|кольцо]], то на нём можно определить множество ''центральных идемпотентов'' так: <br /> ''A'' = { ''e'' &isin; ''R'' : ''e''² = ''e'', ''ex'' = ''xe'', &forall;''x'' &isin; ''R'' }, <br /> тогда множество ''A'' будет булевой алгеброй с операциями ''e'' &or; ''f'' := ''e'' + ''f'' &minus; ''ef'' и ''e'' &and; ''f'' := ''ef''. == Принцип двойственности == В булевых алгебрах существуют двойственные утверждения, они либо одновременно верны, либо одновременно неверны. Именно, если в формуле, которая верна в некоторой булевой алгебре, поменять все конъюнкции на дизъюнкции, 0 на 1, &le; на &ge; и наоборот, то получится формула, также истинная в этой булевой алгебре. Это следует из симметричности аксиом относительно таких замен. == Представления булевых алгебр == Можно доказать, что любая конечная булева алгебра изоморфна булевой алгебре всех подмножеств какого-то множества. Отсюда следует, что количество элементов в любой конечной булевой алгебре будет степенью двойки. Знаменитая [[теорема Стоуна]] утверждает, что любая булева алгебра изоморфна булевой алгебре всех открыто-замкнутых множеств какого-то [[компакт]]ного [[вполне несвязное пространство|вполне несвязного]] [[хаусдорфово пространство|хаусдорфова]] топологического пространства. == Аксиоматизация == В [[1933]] г. американский математик [[Хантингтон, Эдвард|Хантингтон]] предложил следующую аксиоматизацию для булевых алгебр: # ''Аксиома коммутативности'': ''x'' + ''y'' = ''y'' + ''x''. # ''Аксиома ассоциативности'': (''x'' + ''y'') + ''z'' = ''x'' + (''y'' + ''z''). # ''Уравнение Хантингтона'': ''n''(''n''(''x'') + ''y'') + ''n''(''n''(''x'') + ''n''(''y'')) = ''x''. ЗдМакКьюн]], используя некоторые полученные до него результаты, дал утвердительный ответ на этот вопрос. Таким образом, любая алгебра Роббинса является булевой алгеброй. == См. также == * [[Алгебра логики]] * [[Булева функция]] * [[Битовые операции]] == Примечания == {{примечания}} == Литература == * {{книга |автор = Владимиров Д. А. |часть = |заглавие = Булевы алгебры |оригинал = |ссылка = http://eqworld.ipmnet.ru/ru/library/books/Vladimirov1969ru.djvu |ответственный = |издание = |место = {{М.}} |издательство = «Наука» |год = 1969 |том = |страницы = |страниц = 320 |серия = |isbn = |тираж = }} * {{книга |автор = Кузнецов О. П., Адельсон-Вельский Г. М. |часть = |заглавие = Дискретная математика для инженера |оригинал = |ссылка = |ответственный = |издание = |место = {{М.}} |издательство = Энергоатомиздат |год = 1988 |том = |страницы = |страниц = 480 |серия = |isbn = |тираж = }} [[Категория:Теория решёток]] [[Категория:Математическая логика]] [[Категория:Булева алгебра|*]] {{Link GA|pl}} [[ast:Álxebra de Boole]] [[bg:Булева алгебра]] [[bn:বুলিয়ান বীজগণিত]] [[bs:Booleova algebra]] [[ca:Àlgebra de Boole]] [[cs:Booleova algebra]] [[de:Boolesche Algebra]] [[en:Boolean algebra (structure)]] [[eo:Bulea algebro]] [[es:Álgebra de Boole]] [[fa:جبر بولی]] [[fi:Boolen algebra]] [[fr:Algèbre de Boole (structure)]] [[gl:Álxebra de Boole]] [[he:אלגברה בוליאנית]] [[hr:Booleova algebra]] [[hu:Boole-algebra]] [[id:Aljabar Boolean]] [[io:Booleana algebro]] [[it:Algebra di Boole]] [[ja:ブール代数]] [[ko:불 대수]] [[lt:Būlio algebra]] [[nl:Booleaanse algebra]] [[no:Boolsk algebra]] [[pl:Algebra Boole'a]] [[pt:Álgebra booleana]] [[simple:Boolean algebra]] [[sk:Boolova algebra]] [[sl:Booleova algebra]] [[sr:Булова алгебра]] [[sv:Boolesk algebra]] [[th:พีชคณิตแบบบูล]] [[tl:Alhebrang Boolean]] [[tr:Boolean cebiri]] [[uk:Булева алгебра]] [[zh:布尔代数]]'