ru.wikipedia.org

Булева алгебра — Википедия

Эта статья об алгебраической системе. О разделе математической логики, изучающем высказывания и операции над ними, см. Алгебра логики.

Бу́левой а́лгеброй[1][2][3] называется непустое множество A с двумя бинарными операциями {\displaystyle \land } (аналог конъюнкции), {\displaystyle \lor } (аналог дизъюнкции), одной унарной операцией {\displaystyle \lnot } (аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для любых a, b и c из множества A верны следующие аксиомы:

{\displaystyle a\lor (b\lor c)=(a\lor b)\lor c} {\displaystyle a\land (b\land c)=(a\land b)\land c} ассоциативность
{\displaystyle a\lor b=b\lor a} {\displaystyle a\land b=b\land a} коммутативность
{\displaystyle a\lor (a\land b)=a} {\displaystyle a\land (a\lor b)=a} законы поглощения
{\displaystyle a\lor (b\land c)=(a\lor b)\land (a\lor c)} {\displaystyle a\land (b\lor c)=(a\land b)\lor (a\land c)} дистрибутивность
{\displaystyle a\lor \lnot a=1} {\displaystyle a\land \lnot a=0} дополнительность

{\displaystyle {\begin{aligned}&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{aligned}}}

Первые три аксиомы означают, что (A, {\displaystyle \land }, {\displaystyle \lor }) является решёткой. Таким образом, булева алгебра может быть определена как дистрибутивная решётка, в которой выполнены две последние аксиомы. Структура, в которой выполняются все аксиомы, кроме предпоследней, называется псевдобулевой алгеброй. Названа в честь Джорджа Буля.

Из аксиом видно, что наименьшим элементом является 0, наибольшим является 1, а дополнение ¬a любого элемента a однозначно определено. Для всех a и b из A верны также следующие равенства:

{\displaystyle a\lor a=a} {\displaystyle a\land a=a}
{\displaystyle a\lor 0=a} {\displaystyle a\land 1=a}
{\displaystyle a\lor 1=1} {\displaystyle a\land 0=0}
{\displaystyle \lnot 0=1} {\displaystyle \lnot 1=0} дополнение 0 есть 1 и наоборот
{\displaystyle \lnot (a\lor b)=\lnot a\land \lnot b} {\displaystyle \lnot (a\land b)=\lnot a\lor \lnot b} законы де Моргана
{\displaystyle \lnot \lnot a=a}. инволютивность отрицания, закон снятия двойного отрицания.

В данном разделе повторяются свойства и аксиомы, описанные выше с добавлением ещё нескольких.

Сводная таблица свойств и аксиом, описанных выше:

{\displaystyle a\lor b=b\lor a} {\displaystyle a\land b=b\land a} 1 коммутативность, переместительность
{\displaystyle a\lor (b\lor c)=(a\lor b)\lor c} {\displaystyle a\land (b\land c)=(a\land b)\land c} 2 ассоциативность, сочетательность
3.1 конъюнкция относительно дизъюнкции {\displaystyle a\lor (b\land c)=(a\lor b)\land (a\lor c)} 3.2 дизъюнкция относительно конъюнкции {\displaystyle a\land (b\lor c)=(a\land b)\lor (a\land c)} 3 дистрибутивность, распределительность
{\displaystyle a\lor \lnot a=1} {\displaystyle a\land \lnot a=0} 4 комплементность, дополнительность (свойства отрицаний)
{\displaystyle \lnot (a\lor b)=\lnot a\land \lnot b} {\displaystyle \lnot (a\land b)=\lnot a\lor \lnot b} 5 законы де Моргана
{\displaystyle a\lor (a\land b)=a} {\displaystyle a\land (a\lor b)=a} 6 законы поглощения
{\displaystyle a\lor (\lnot a\land b)=a\lor b} {\displaystyle a\land (\lnot a\lor b)=a\land b} 7 Блейка-Порецкого
{\displaystyle a\lor a=a} {\displaystyle a\land a=a} 8 Идемпотентность
{\displaystyle \lnot \lnot a=a} 9 инволютивность отрицания, закон снятия двойного отрицания
{\displaystyle a\lor 0=a} {\displaystyle a\land 1=a} 10 свойства констант
{\displaystyle a\lor 1=1} {\displaystyle a\land 0=0}
дополнение 0 есть 1 {\displaystyle \lnot 0=1} дополнение 1 есть 0 {\displaystyle \lnot 1=0}
{\displaystyle (a\lor b)\land (\lnot a\lor b)=b} {\displaystyle (a\land b)\lor (\lnot a\land b)=b} 11 Склеивание
  • Самая простая нетривиальная булева алгебра содержит всего два элемента, 0 и 1, а действия в ней определяются следующей таблицей:
∧ 0 1
0 0 0
1 0 1
∨ 0 1
0 0 1
1 1 1
a 0 1
¬a 1 0
Эта булева алгебра наиболее часто используется в логике, так как является точной моделью классического исчисления высказываний. В этом случае 0 называют ложью, 1 — истиной. Выражения, содержащие булевы операции и переменные, представляют собой высказывательные формы.

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

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

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

В 1933 году американский математик Хантингтон[англ.] предложил следующую аксиоматизацию для булевых алгебр:

  1. Аксиома коммутативности: x + y = y + x.
  2. Аксиома ассоциативности: (x + y) + z = x + (y + z).
  3. Уравнение Хантингтона: n(n(x) + y) + n(n(x) + n(y)) = x.

Здесь использованы обозначения Хантингтона: + означает дизъюнкцию, n — отрицание.

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

Аксиоматизация алгебры Роббинса:

  1. Аксиома коммутативности: x + y = y + x.
  2. Аксиома ассоциативности: (x + y) + z = x + (y + z).
  3. Уравнение Роббинса: n(n(x + y) + n(x + n(y))) = x.

Этот вопрос оставался открытым с 1930-х годов и был любимым вопросом Тарского и его учеников.

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

  1. ↑ D. A. Vladimirov. Springer Online Reference Works – Boolean algebra (англ.). Springer-Verlag (2002). Дата обращения: 4 августа 2010. Архивировано 9 февраля 2012 года.
  2. ↑ Владимиров, 1969, с. 19.
  3. ↑ Кузнецов, 2007.
  4. ↑ Виленкин Н. Я., Шибасов Л. П. Шибасова 3. Ф. За страницами учебника математики : Арифметика. Алгебра. Геометрия : Кн. для учащихся 10-11-х кл. общеобразоват. учреждений. — М.: Просвещение : АО "Учеб. лит.", 1996. — С. 197. — 319 с. Архивировано 6 мая 2018 года.