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

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

Булевой алгеброй^[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$	дополнительность

В нотации · + ¯

$\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}$

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

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

Из аксиом видно, что наименьшим элементом является 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 г. Вильям МакКьюн, используя некоторые полученные до него результаты, дал утвердительный ответ на этот вопрос. Таким образом, любая алгебра Роббинса является булевой алгеброй.

[править] См. также

[править] Примечания

в‘ D. A. Vladimirov Springer Online Reference Works - Boolean algebra (англ.). Springer-Verlag (2002). Архивировано из первоисточника 9 февраля 2012. Проверено 4 августа 2010.
в‘ Владимиров Д. А. Булевы алгебры. в М.: «Наука», 1969. в С. 19.
в‘ Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. в М.: Энергоатомиздат, 1988. в С. 58.

[править] Литература

Владимиров Д. А. Булевы алгебры. в М.: «Наука», 1969. в 320 с.
Иванов Б. Н. Дискретная математика. Алгоритмы и программы. Расширенный курс. в М.: «Известия», 2011. в 512 с. в ISBN 978-5-206-00824-1
Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. в М.: Энергоатомиздат, 1988. в 480 с.

[0] в‘ D. A. Vladimirov Springer Online Reference Works - Boolean algebra (англ.). Springer-Verlag (2002). Архивировано из первоисточника 9 февраля 2012. Проверено 4 августа 2010.

[1] в‘ Владимиров Д. А. Булевы алгебры. в М.: «Наука», 1969. в С. 19.

[2] в‘ Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. в М.: Энергоатомиздат, 1988. в С. 58.

[1]

[2]

[3]

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

Содержание

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

[править] Основные тождества

[править] Примеры

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

[править] Представления булевых алгебр

[править] Аксиоматизация

[править] См. также

[править] Примечания

[править] Литература

Личные инструменты

Пространства имён

Варианты

Просмотры

Действия

Поиск

Навигация

Участие

Печать/экспорт

Инструменты

На других языках