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

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

Бу́левой а́лгебройШаблон:SfnШаблон:Sfn называется непустое множество A с двумя бинарными операциями $\wedge$ (аналог конъюнкции), $\vee$ (аналог дизъюнкции), одной унарной операцией $\mathrm{\neg }$ (аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для любых a, b и c из множества A верны следующие аксиомы:

$a\vee (b\vee c)=(a\vee b)\vee c$	$a\wedge (b\wedge c)=(a\wedge b)\wedge c$	ассоциативность
$a\vee b=b\vee a$	$a\wedge b=b\wedge a$	коммутативность
$a\vee (a\wedge b)=a$	$a\wedge (a\vee b)=a$	законы поглощения
$a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)$	$a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c)$	дистрибутивность
$a\vee \mathrm{\neg }a=1$	$a\wedge \mathrm{\neg }a=0$	дополнительность

Шаблон:Hider

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

Некоторые свойства

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

$a\vee a=a$	$a\wedge a=a$
$a\vee 0=a$	$a\wedge 1=a$
$a\vee 1=1$	$a\wedge 0=0$
$\mathrm{\neg }0=1$	$\mathrm{\neg }1=0$	дополнение 0 есть 1 и наоборот
$\mathrm{\neg }(a\vee b)=\mathrm{\neg }a\wedge \mathrm{\neg }b$	$\mathrm{\neg }(a\wedge b)=\mathrm{\neg }a\vee \mathrm{\neg }b$	законы де Моргана
$\mathrm{\neg }\mathrm{\neg }a=a$.		инволютивность отрицания, закон снятия двойного отрицания.

Основные тождества

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

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

$a\vee b=b\vee a$	$a\wedge b=b\wedge a$	1 коммутативность, переместительность
$a\vee (b\vee c)=(a\vee b)\vee c$	$a\wedge (b\wedge c)=(a\wedge b)\wedge c$	2 ассоциативность, сочетательность
3.1 конъюнкция относительно дизъюнкции $a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)$	3.2 дизъюнкция относительно конъюнкции $a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c)$	3 дистрибутивность, распределительность
$a\vee \mathrm{\neg }a=1$	$a\wedge \mathrm{\neg }a=0$	4 комплементность, дополнительность (свойства отрицаний)
$\mathrm{\neg }(a\vee b)=\mathrm{\neg }a\wedge \mathrm{\neg }b$	$\mathrm{\neg }(a\wedge b)=\mathrm{\neg }a\vee \mathrm{\neg }b$	5 законы де Моргана
$a\vee (a\wedge b)=a$	$a\wedge (a\vee b)=a$	6 законы поглощения
$a\vee (\mathrm{\neg }a\wedge b)=a\vee b$	$a\wedge (\mathrm{\neg }a\vee b)=a\wedge b$	7 Блейка-Порецкого
$a\vee a=a$	$a\wedge a=a$	8 Идемпотентность
$\mathrm{\neg }\mathrm{\neg }a=a$		9 инволютивность отрицания, закон снятия двойного отрицания
$a\vee 0=a$	$a\wedge 1=a$	10 свойства констант
$a\vee 1=1$	$a\wedge 0=0$
дополнение 0 есть 1 $\mathrm{\neg }0=1$	дополнение 1 есть 0 $\mathrm{\neg }1=0$
$(a\vee b)\wedge (\mathrm{\neg }a\vee b)=b$	$(a\wedge b)\vee (\mathrm{\neg }a\wedge 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.
• Рассмотрим множество $U$ всех натуральных делителей заданного натурального числа $m,$ свободного от квадратов. Определим на $U$ две бинарные операции: нахождение наибольшего общего делителя (аналог конъюнкции) и наименьшего общего кратного (аналог дизъюнкции); роль отрицания играет одноместная операция, сопоставляющая делителю $d$ делитель $m/d.$ Полученная структура является булевой алгеброй; в ней аналогами булевских нуля и единицы выступают соответственно числа 1 и $m.$ Переложение приведенных выше общих аксиом и свойств булевой алгебры для множества $U$ даёт ряд полезных и не очевидных теоретико-числовых тождеств.
• Алгебра Линденбаума — Тарского (фактормножество всех утверждений по отношению равносильности в данном исчислении с соответствующими операциями) какого-либо исчисления высказываний является булевой алгеброй. В этом случае истинностная оценка формул исчисления является гомоморфизмом алгебры Линденбаума — Тарского в двухэлементную булеву алгебру.
• Если R — произвольное кольцо, то на нём можно определить множество центральных идемпотентов так:
  A = { e ∈ R : e² = e, ex = xe, ∀x ∈ R },
  тогда множество A будет булевой алгеброй с операциями e ∨ f := e + f − ef и e ∧ f := ef.

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

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

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

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

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

Аксиоматизация

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

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:КнигаШаблон:Недоступная ссылка
• Шаблон:Книга