Русская Википедия:Булева алгебра

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

<math> a \lor (b \lor c) = (a \lor b) \lor c </math> <math> a \land (b \land c) = (a \land b) \land c </math> ассоциативность
<math> a \lor b = b \lor a </math> <math> a \land b = b \land a </math> коммутативность
<math> a \lor (a \land b) = a </math> <math> a \land (a \lor b) = a </math> законы поглощения
<math> a \lor (b \land c) = (a \lor b) \land (a \lor c) </math> <math> a \land (b \lor c) = (a \land b) \lor (a \land c) </math> дистрибутивность
<math> a \lor \lnot a = 1 </math> <math> a \land \lnot a = 0 </math> дополнительность
Шаблон:Hider

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

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

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

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

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

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

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

<math> a \lor b = b \lor a </math> <math> a \land b = b \land a </math> 1 коммутативность, переместительность
<math> a \lor (b \lor c) = (a \lor b) \lor c </math> <math> a \land (b \land c) = (a \land b) \land c </math> 2 ассоциативность, сочетательность
3.1 конъюнкция относительно дизъюнкции <math> a \lor (b \land c) = (a \lor b) \land (a \lor c) </math> 3.2 дизъюнкция относительно конъюнкции <math> a \land (b \lor c) = (a \land b) \lor (a \land c) </math> 3 дистрибутивность, распределительность
<math> a \lor \lnot a = 1 </math> <math> a \land \lnot a = 0 </math> 4 комплементность, дополнительность (свойства отрицаний)
<math> \lnot (a \lor b) = \lnot a \land \lnot b</math> <math> \lnot (a \land b) = \lnot a \lor \lnot b</math> 5 законы де Моргана
<math> a \lor (a \land b) = a </math> <math> a \land (a \lor b) = a </math> 6 законы поглощения
<math>a \lor(\lnot a \land b) = a \lor b</math> <math>a \land(\lnot a \lor b) = a \land b</math> 7 Блейка-Порецкого
<math> a \lor a = a</math> <math> a \land a = a </math> 8 Идемпотентность
<math> \lnot \lnot a = a </math> 9 инволютивность отрицания, закон снятия двойного отрицания
<math> a \lor 0 = a </math> <math> a \land 1 = a </math> 10 свойства констант
<math> a \lor 1 = 1 </math> <math> a \land 0 = 0 </math>
дополнение 0 есть 1 <math> \lnot 0 = 1 </math> дополнение 1 есть 0 <math> \lnot 1 = 0 </math>
<math> (a \lor b)\land(\lnot a \lor b)=b</math> <math> (a \land b) \lor (\lnot a \land b)=b</math> 11 Склеивание

Шаблон:Seealso

Примеры

  • Самая простая нетривиальная булева алгебра содержит всего два элемента, 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.
  • Рассмотрим множество <math>U</math> всех натуральных делителей заданного натурального числа <math>m,</math> свободного от квадратов. Определим на <math>U</math> две бинарные операции: нахождение наибольшего общего делителя (аналог конъюнкции) и наименьшего общего кратного (аналог дизъюнкции); роль отрицания играет одноместная операция, сопоставляющая делителю <math>d</math> делитель <math>m/d.</math> Полученная структура является булевой алгеброй; в ней аналогами булевских нуля и единицы выступают соответственно числа 1 и <math>m.</math> Переложение приведенных выше общих аксиом и свойств булевой алгебры для множества <math>U</math> даёт ряд полезных и не очевидных теоретико-числовых тождеств[2].
  • Алгебра Линденбаума — Тарского (фактормножество всех утверждений по отношению равносильности в данном исчислении с соответствующими операциями) какого-либо исчисления высказываний является булевой алгеброй. В этом случае истинностная оценка формул исчисления является гомоморфизмом алгебры Линденбаума — Тарского в двухэлементную булеву алгебру.
  • Если R — произвольное кольцо, то на нём можно определить множество центральных идемпотентов так:
    A = { eR : e² = e, ex = xe, ∀xR },
    тогда множество A будет булевой алгеброй с операциями ef := e + fef и ef := 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, используя некоторые полученные до него результаты, дал утвердительный ответ на этот вопрос. Таким образом, любая алгебра Роббинса является булевой алгеброй.

См. также

Примечания

Шаблон:Примечания

Литература

Шаблон:Вс Шаблон:Дискретная математика