Просмотр кода страницы Булева алгебра

: ''Эта статья об [[Алгебраическая система|алгебраической системе]]. О разделе математической логики, изучающем высказывания и операции над ними, см. [[Алгебра логики]].''
'''Бу́левой а́лгеброй'''<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|archiveurl=https://www.webcitation.org/65JKMgr2a?url=http://www.encyclopediaofmath.org/index.php/Main_Page|archivedate=2012-02-09}}</ref>{{sfn|Владимиров|1969|с=19}}{{sfn|Кузнецов|2007}} называется непустое [[множество]] ''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 = В нотации · + ¯|
  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=15
| <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 Склеивание
|}

{{seealso|Алгебра логики#Свойства логических операций}}

== Примеры ==
* Самая простая нетривиальная булева алгебра содержит всего два элемента, 0 и 1, а действия в ней определяются следующей таблицей:
{|
|-
| width="80" |
|
{| border="1" cellpadding="4" cellspacing="0"
|-
! ∧ || 0 || 1
|-
! 0
| 0 || 0
|-
! 1
| 0 || 1
|}
|
| width="40" |
|
{| border="1" cellpadding="4" cellspacing="0"
|-
! ∨ || 0 || 1
|-
! 0
| 0 || 1
|-
! 1
| 1 || 1
|}
|
| width="40" |
|
{| border="1" cellpadding="4" cellspacing="0"
|-
! a || 0 || 1
|-
! ¬a
| 1 || 0
|}
|}
: Эта булева алгебра наиболее часто используется в [[логика|логике]], так как является [[точная модель|точной моделью]] классического [[исчисление высказываний|исчисления высказываний]]. В этом случае 0 называют ''ложью'', 1 — ''истиной''. Выражения, содержащие булевы операции и переменные, представляют собой высказывательные формы.
* [[Булеан|Множество всех подмножеств]] данного множества ''S'' образует булеву алгебру относительно операций ∨ := ∪ (объединение), ∧ := ∩ (пересечение) и унарной операции дополнения. Наименьший элемент здесь — [[пустое множество]], а наибольший — всё ''S''.
* Рассмотрим множество <math>U</math> всех натуральных делителей заданного натурального числа <math>m,</math> [[Свободное от квадратов число|свободного от квадратов]]. Определим на <math>U</math> две бинарные операции: нахождение [[Наибольший общий делитель|наибольшего общего делителя]] (аналог конъюнкции) и [[Наименьшее общее кратное|наименьшего общего кратного]] (аналог дизъюнкции); роль отрицания играет одноместная операция, сопоставляющая делителю <math>d</math> делитель <math>m/d.</math> Полученная структура является булевой алгеброй; в ней аналогами булевских нуля и единицы выступают соответственно числа 1 и <math>m.</math> Переложение приведенных выше общих аксиом и свойств булевой алгебры для множества <math>U</math> даёт ряд полезных и не очевидных теоретико-числовых тождеств<ref>{{книга |автор=Виленкин Н. Я., Шибасов Л. П. Шибасова 3. Ф. |ref=За страницами учебника математики |заглавие=За страницами учебника математики : Арифметика. Алгебра. Геометрия : Кн. для учащихся 10-11-х кл. общеобразоват. учреждений |ссылка=https://search.rsl.ru/ru/record/01001733870 |место=М. |издательство=Просвещение : АО "Учеб. лит." |год=1996 |страницы=197 |страниц=319 |archivedate=2018-05-06 |archiveurl=https://web.archive.org/web/20180506040228/https://search.rsl.ru/ru/record/01001733870 }}</ref>.
* [[Алгебра Линденбаума — Тарского]] ([[фактормножество]] всех утверждений по отношению равносильности в данном исчислении с соответствующими операциями) какого-либо исчисления высказываний является булевой алгеброй. В этом случае истинностная оценка формул исчисления является [[гомоморфизм]]ом алгебры Линденбаума — Тарского в двухэлементную булеву алгебру.
* Если ''R'' — произвольное [[кольцо (алгебра)|кольцо]], то на нём можно определить множество ''центральных идемпотентов'' так: <br> ''A'' = { ''e'' ∈ ''R'' : ''e''² = ''e'', ''ex'' = ''xe'', ∀''x'' ∈ ''R'' }, <br> тогда множество ''A'' будет булевой алгеброй с операциями ''e'' ∨ ''f'' := ''e'' + ''f'' − ''ef'' и ''e'' ∧ ''f'' := ''ef''.

== Принцип двойственности ==
В булевых алгебрах существуют двойственные утверждения, они либо одновременно верны, либо одновременно неверны. Именно, если в формуле, которая верна в некоторой булевой алгебре, поменять все конъюнкции на дизъюнкции, 0 на 1, ≤ на > и наоборот или < на ≥ и наоборот, то получится формула, также истинная в этой булевой алгебре. Это следует из симметричности аксиом относительно таких замен.

== Представления булевых алгебр ==
Можно доказать, что любая конечная булева алгебра изоморфна булевой алгебре всех подмножеств какого-то множества. Отсюда следует, что количество элементов в любой конечной булевой алгебре будет степенью двойки.

[[Теорема Стоуна о представлении булевых алгебр|Теорема Стоуна]] утверждает, что любая булева алгебра изоморфна булевой алгебре всех открыто-замкнутых множеств какого-то [[компакт]]ного [[вполне несвязное пространство|вполне несвязного]] [[хаусдорфово пространство|хаусдорфова]] [[Топологическое пространство|топологического пространства]].

== Аксиоматизация ==
В [[1933 год]]у американский математик {{не переведено 5|Хантингтон, Эдвард (математик)|Хантингтон||Edward Vermilye Huntington}} предложил следующую аксиоматизацию для булевых алгебр:
# ''Аксиома коммутативности'': ''x'' + ''y'' = ''y'' + ''x''.
# ''Аксиома ассоциативности'': (''x'' + ''y'') + ''z'' = ''x'' + (''y'' + ''z'').
# ''Уравнение Хантингтона'': ''n''(''n''(''x'') + ''y'') + ''n''(''n''(''x'') + ''n''(''y'')) = ''x''.
Здесь использованы обозначения Хантингтона: + означает дизъюнкцию, n — отрицание.

[[Роббинс, Герберт|Герберт Роббинс]] поставил следующий вопрос: можно ли сократить последнюю аксиому так, как написано ниже, то есть будет ли определённая выписанными ниже аксиомами структура булевой алгеброй?

Аксиоматизация алгебры Роббинса:
# ''Аксиома коммутативности'': ''x'' + ''y'' = ''y'' + ''x''.
# ''Аксиома ассоциативности'': (''x'' + ''y'') + ''z'' = ''x'' + (''y'' + ''z'').
# ''Уравнение Роббинса'': ''n''(''n''(''x'' + ''y'') + ''n''(''x'' + ''n''(''y''))) = ''x''.
Этот вопрос оставался открытым с 1930-х годов и был любимым вопросом [[Тарский, Альфред|Тарского]] и его учеников.

В [[1996 год]]у {{нп4|МакКьюн, Вильям|Вильям МакКьюн||William McCune}}, используя некоторые полученные до него результаты, дал утвердительный ответ на этот вопрос. Таким образом, любая алгебра Роббинса является булевой алгеброй.

== См. также ==
* [[Алгебра логики]]
* [[Булева функция]]
* [[Модальная алгебра]]
* [[Битовые операции]]
* [[Аксиома Вольфрама]]

== Примечания ==
{{примечания}}

== Литература ==
* {{книга
 |автор          = Владимиров Д. А.
 |часть          = 
 |заглавие       = Булевы алгебры
 |оригинал       = 
 |ссылка         = http://eqworld.ipmnet.ru/ru/library/books/Vladimirov1969ru.djvu
 |ответственный  = 
 |издание        = 
 |место          = {{М.}}
 |издательство   = «Наука»
 |год            = 1969
 |том            = 
 |страницы       = 
 |страниц        = 320
 |серия          = 
 |isbn           = 
 |тираж          = 
 |ref            = Владимиров
}}
* {{книга|автор=Кузнецов О. П.|заглавие=Дискретная математика для инженера|место={{СПб}}|издательство=Лань|год=2007|страниц=394|ссылка=https://search.rsl.ru/ru/record/01003342716|ref = Кузнецов}}
* {{книга|автор=Иванов Б. Н.|часть=|заглавие=Дискретная математика. Алгоритмы и программы. Расширенный курс|оригинал=|ссылка=http://bnivanov.ru/?p=761|ответственный=|издание=|место={{М.}}|издательство=«Известия»|год=2011|том=|страницы=|страниц=512|серия=|isbn=|тираж=|ref=Кузнецов}}{{Недоступная ссылка|date=Июнь 2018 |bot=InternetArchiveBot }}
* {{книга
 |автор          = Гуров С.И.
 |заглавие       = Булевы алгебры, упорядоченные множества, решетки: Определения, свойства, примеры
 |ссылка         = https://www.researchgate.net/publication/279495665_Bulevy_algebry_uporadocennye_mnozestva_resetki_Opredelenia_svojstva_primery
 |ответственный  = 
 |издание        = 
 |место          = {{М.}}
 |издательство   =  Либроком
 |год            = 2013
 |том            = 
 |страницы       = 
 |страниц        = 352
 |серия          = 
 |isbn           = 
 |тираж          = 
}}

{{вс}}
{{Дискретная математика}}
[[Категория:Теория решёток]]
[[Категория:Математическая логика]]
[[Категория:Булева алгебра|*]]
[[Категория:Дискретная математика]]