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

Булевой алгеброй называется непустое множество 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}$	дополнительность

Первые три аксиомы означают, что ( 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 — истиной . Выражения, содержащие булевы операции и переменные, представляют собой высказывательные формы.

• Множество всех подмножеств данного множества S образует булеву алгебру относительно операций ∨ := ∪ (объединение), ∧ := ∩ (пересечение) и унарной операции дополнения. Наименьший элемент здесь — пустое множество , а наибольший — всё S .
• Рассмотрим множество ${\displaystyle U}$ всех натуральных делителей заданного натурального числа ${\displaystyle m,}$ свободного от квадратов . Определим на ${\displaystyle U}$ две бинарные операции: нахождение наибольшего общего делителя (аналог конъюнкции) и наименьшего общего кратного (аналог дизъюнкции); роль отрицания играет одноместная операция, сопоставляющая делителю ${\displaystyle d}$ делитель ${\displaystyle m/d.}$ Полученная структура является булевой алгеброй; в ней аналогами булевских нуля и единицы выступают соответственно числа 1 и ${\displaystyle m.}$ Переложение приведенных выше общих аксиом и свойств булевой алгебры для множества ${\displaystyle U}$ даёт ряд полезных и не очевидных теоретико-числовых тождеств .
• Алгебра Линденбаума — Тарского ( фактормножество всех утверждений по отношению равносильности в данном исчислении с соответствующими операциями) какого-либо исчисления высказываний является булевой алгеброй. В этом случае истинностная оценка формул исчисления является гомоморфизмом алгебры Линденбаума — Тарского в двухэлементную булеву алгебру.
• Если R — произвольное кольцо , то на нём можно определить множество центральных идемпотентов так:
  A = { e ∈ R : e ² = e , ex = xe , ∀ x ∈ R },
  тогда множество A будет булевой алгеброй с операциями e ∨ f := e + f − ef и e ∧ f := ef .

Принцип двойственности

В булевых алгебрах существуют двойственные утверждения, они либо одновременно верны, либо одновременно неверны. Именно, если в формуле, которая верна в некоторой булевой алгебре, поменять все конъюнкции на дизъюнкции, 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 году _en , используя некоторые полученные до него результаты, дал утвердительный ответ на этот вопрос. Таким образом, любая алгебра Роббинса является булевой алгеброй.

См. также

• Алгебра логики
• Булева функция
• Модальная алгебра
• Битовые операции
• Аксиома Вольфрама

Примечания

Литература

• Владимиров Д. А. . — М. : «Наука», 1969. — 320 с.
• Кузнецов О. П. . — СПб. : Лань, 2007. — 394 с.
• Иванов Б. Н. . — М. : «Известия», 2011. — 512 с. (недоступная ссылка)
• Гуров С.И. . — М. : Либроком, 2013. — 352 с.