Булева алгебра
[править]
Материал из Википедии — свободной энциклопедии

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

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

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

1 Некоторые свойства
2 Основные тождества
3 Примеры
4 Принцип двойственности
5 Представления булевых алгебр
6 Аксиоматизация
7 См. также
8 Примечания
9 Литература

[править] Некоторые свойства

||
Из аксиом видно, что наименьшим элементом является 0, наибольшим является 1, а дополнение ¬a любого элемента a однозначно определено. Для всех a и b из A верны также следующие равенства:
a \lor a = a; a \land a = a ;
a \lor 0 = a ; a \land 1 = a ;
a \lor 1 = 1 ; a \land 0 = 0 ;
\lnot 0 = 1 ; \lnot 1 = 0 ; дополнение 0 есть 1 и наоборот
\lnot (a \lor b) = \lnot a \land \lnot b; \lnot (a \land b) = \lnot a \lor \lnot b; законы де Моргана
\lnot \lnot a = a . инволютивность отрицания
[править] Основные тождества

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

Сводная таблица свойств и аксиом, описанных выше:
a \lor b = b \lor a ; a \land b = b \land a . 1 коммутативность переместительность
a \lor (b \lor c) = (a \lor b) \lor c ; a \land (b \land c) = (a \land b) \land c . 2 ассоциативность сочетательность
3.1 конъюнкция относительно дизъюнкции a \lor (b \land c) = (a \lor b) \land (a \lor c) 3.2 дизъюнкция относительно конъюнкции a \land (b \lor c) = (a \land b) \lor (a \land c) 3 дистрибутивность распределительность
a \lor \lnot a = 1 ; a \land \lnot a = 0 . 4 комплементность дополнительность (свойства отрицаний)
\lnot (a \lor b) = \lnot a \land \lnot b; \lnot (a \land b) = \lnot a \lor \lnot b. 5 законы де Моргана
a \lor (a \land b) = a ; a \land (a \lor b) = a . 6 законы поглощения
a \lor(\lnot a \land b) = a \lor b; a \land(\lnot a \lor b) = a \land b. 7 Блейка-Порецкого
a \lor a = a; a \land a = a . 8 Идемпотентность
\lnot \lnot a = a . 9 инволютивность отрицания
a \lor 0 = a ; a \land 1 = a . 10 свойства констант
a \lor 1 = 1 ; a \land 0 = 0 .
дополнение 0 есть 1 \lnot 0 = 1 ; дополнение 1 есть 0 \lnot 1 = 0 .
(a \lor b)\land(\lnot a \lor b)=b; (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 — истиной. Выражения, содержащие булевы операции и переменные, представляют собой высказывательные формы.

Алгебра Линденбаума — Тарского (фактормножество всех утверждений по отношению равносильности в данном исчислении с соответствующими операциями) какого-либо исчисления высказываний является булевой алгеброй. В этом случае истинностная оценка формул исчисления является гомоморфизмом алгебры Линденбаума — Тарского в двухэлементную булеву алгебру.

Множество всех подмножеств данного множества S образует булеву алгебру относительно операций ∨ := ∪ (объединение), ∧ := ∩ (пересечение) и унарной операции дополнения. Наименьший элемент здесь — пустое множество, а наибольший — всё S.

Если R — произвольное кольцо, то на нём можно определить множество центральных идемпотентов так:
A = { e ∈ R : e² = e, ex = xe, ∀x ∈ R },
тогда множество A будет булевой алгеброй с операциями e ∨ f := e + f − ef и e ∧ f := ef.

[править] Принцип двойственности

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

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

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

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

Аксиома коммутативности: 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.

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

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

Алгебра логики
Булева функция
Битовые операции