Булева алгебра
- Эта статья об алгебраической системе. О разделе математической логики, изучающем высказывания и операции над ними, см. Алгебра логики.
Булевой алгеброй[1][2][3] называется непустое множество A с двумя бинарными операциями [math]\displaystyle{ \land }[/math] (аналог конъюнкции), [math]\displaystyle{ \lor }[/math] (аналог дизъюнкции), одной унарной операцией [math]\displaystyle{ \lnot }[/math] (аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для любых a, b и c из множества A верны следующие аксиомы:
| [math]\displaystyle{ a \lor (b \lor c) = (a \lor b) \lor c }[/math] | [math]\displaystyle{ a \land (b \land c) = (a \land b) \land c }[/math] | ассоциативность |
| [math]\displaystyle{ a \lor b = b \lor a }[/math] | [math]\displaystyle{ a \land b = b \land a }[/math] | коммутативность |
| [math]\displaystyle{ a \lor (a \land b) = a }[/math] | [math]\displaystyle{ a \land (a \lor b) = a }[/math] | законы поглощения |
| [math]\displaystyle{ a \lor (b \land c) = (a \lor b) \land (a \lor c) }[/math] | [math]\displaystyle{ a \land (b \lor c) = (a \land b) \lor (a \land c) }[/math] | дистрибутивность |
| [math]\displaystyle{ a \lor \lnot a = 1 }[/math] | [math]\displaystyle{ a \land \lnot a = 0 }[/math] | дополнительность |
[math]\displaystyle{ \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} }[/math]
Первые три аксиомы означают, что (A, [math]\displaystyle{ \land }[/math], [math]\displaystyle{ \lor }[/math]) является решёткой. Таким образом, булева алгебра может быть определена как дистрибутивная решётка, в которой выполнены две последние аксиомы. Структура, в которой выполняются все аксиомы, кроме предпоследней, называется псевдобулевой алгеброй. Названа в честь Джорджа Буля.
Некоторые свойства
Из аксиом видно, что наименьшим элементом является 0, наибольшим является 1, а дополнение ¬a любого элемента a однозначно определено. Для всех a и b из A верны также следующие равенства:
| [math]\displaystyle{ a \lor a = a }[/math] | [math]\displaystyle{ a \land a = a }[/math] | |
| [math]\displaystyle{ a \lor 0 = a }[/math] | [math]\displaystyle{ a \land 1 = a }[/math] | |
| [math]\displaystyle{ a \lor 1 = 1 }[/math] | [math]\displaystyle{ a \land 0 = 0 }[/math] | |
| [math]\displaystyle{ \lnot 0 = 1 }[/math] | [math]\displaystyle{ \lnot 1 = 0 }[/math] | дополнение 0 есть 1 и наоборот |
| [math]\displaystyle{ \lnot (a \lor b) = \lnot a \land \lnot b }[/math] | [math]\displaystyle{ \lnot (a \land b) = \lnot a \lor \lnot b }[/math] | законы де Моргана |
| [math]\displaystyle{ \lnot \lnot a = a }[/math]. | инволютивность отрицания, закон снятия двойного отрицания. |
Основные тождества
В данном разделе повторяются свойства и аксиомы, описанные выше с добавлением ещё нескольких.
Сводная таблица свойств и аксиом, описанных выше:
| [math]\displaystyle{ a \lor b = b \lor a }[/math] | [math]\displaystyle{ a \land b = b \land a }[/math] | 1 коммутативность, переместительность |
| [math]\displaystyle{ a \lor (b \lor c) = (a \lor b) \lor c }[/math] | [math]\displaystyle{ a \land (b \land c) = (a \land b) \land c }[/math] | 2 ассоциативность, сочетательность |
| 3.1 конъюнкция относительно дизъюнкции [math]\displaystyle{ a \lor (b \land c) = (a \lor b) \land (a \lor c) }[/math] | 3.2 дизъюнкция относительно конъюнкции [math]\displaystyle{ a \land (b \lor c) = (a \land b) \lor (a \land c) }[/math] | 3 дистрибутивность, распределительность |
| [math]\displaystyle{ a \lor \lnot a = 1 }[/math] | [math]\displaystyle{ a \land \lnot a = 0 }[/math] | 4 комплементность, дополнительность (свойства отрицаний) |
| [math]\displaystyle{ \lnot (a \lor b) = \lnot a \land \lnot b }[/math] | [math]\displaystyle{ \lnot (a \land b) = \lnot a \lor \lnot b }[/math] | 5 законы де Моргана |
| [math]\displaystyle{ a \lor (a \land b) = a }[/math] | [math]\displaystyle{ a \land (a \lor b) = a }[/math] | 6 законы поглощения |
| [math]\displaystyle{ a \lor(\lnot a \land b) = a \lor b }[/math] | [math]\displaystyle{ a \land(\lnot a \lor b) = a \land b }[/math] | 7 Блейка-Порецкого |
| [math]\displaystyle{ a \lor a = a }[/math] | [math]\displaystyle{ a \land a = a }[/math] | 8 Идемпотентность |
| [math]\displaystyle{ \lnot \lnot a = a }[/math] | 9 инволютивность отрицания, закон снятия двойного отрицания | |
| [math]\displaystyle{ a \lor 0 = a }[/math] | [math]\displaystyle{ a \land 1 = a }[/math] | 10 свойства констант |
| [math]\displaystyle{ a \lor 1 = 1 }[/math] | [math]\displaystyle{ a \land 0 = 0 }[/math] | |
| дополнение 0 есть 1 [math]\displaystyle{ \lnot 0 = 1 }[/math] | дополнение 1 есть 0 [math]\displaystyle{ \lnot 1 = 0 }[/math] | |
| [math]\displaystyle{ (a \lor b)\land(\lnot a \lor b)=b }[/math] | [math]\displaystyle{ (a \land b) \lor (\lnot a \land b)=b }[/math] | 11 Склеивание |
Примеры
- Самая простая нетривиальная булева алгебра содержит всего два элемента, 0 и 1, а действия в ней определяются следующей таблицей:
|
|
|
- Эта булева алгебра наиболее часто используется в логике, так как является точной моделью классического исчисления высказываний. В этом случае 0 называют ложью, 1 — истиной. Выражения, содержащие булевы операции и переменные, представляют собой высказывательные формы.
- Множество всех подмножеств данного множества S образует булеву алгебру относительно операций ∨ := ∪ (объединение), ∧ := ∩ (пересечение) и унарной операции дополнения. Наименьший элемент здесь — пустое множество, а наибольший — всё S.
- Рассмотрим множество [math]\displaystyle{ U }[/math] всех натуральных делителей заданного натурального числа [math]\displaystyle{ m, }[/math] свободного от квадратов. Определим на [math]\displaystyle{ U }[/math] две бинарные операции: нахождение наибольшего общего делителя (аналог конъюнкции) и наименьшего общего кратного (аналог дизъюнкции); роль отрицания играет одноместная операция, сопоставляющая делителю [math]\displaystyle{ d }[/math] делитель [math]\displaystyle{ m/d. }[/math] Полученная структура является булевой алгеброй; в ней аналогами булевских нуля и единицы выступают соответственно числа 1 и [math]\displaystyle{ m. }[/math] Переложение приведенных выше общих аксиом и свойств булевой алгебры для множества [math]\displaystyle{ U }[/math] даёт ряд полезных и не очевидных теоретико-числовых тождеств[4].
- Алгебра Линденбаума — Тарского (фактормножество всех утверждений по отношению равносильности в данном исчислении с соответствующими операциями) какого-либо исчисления высказываний является булевой алгеброй. В этом случае истинностная оценка формул исчисления является гомоморфизмом алгебры Линденбаума — Тарского в двухэлементную булеву алгебру.
- Если 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.
Этот вопрос оставался открытым с 1930-х годов и был любимым вопросом Тарского и его учеников.
В 1996 году Вильям МакКьюн, используя некоторые полученные до него результаты, дал утвердительный ответ на этот вопрос. Таким образом, любая алгебра Роббинса является булевой алгеброй.
См. также
Примечания
- ↑ D. A. Vladimirov. Springer Online Reference Works – Boolean algebra (англ.). Springer-Verlag (2002). Дата обращения: 4 августа 2010. Архивировано 9 февраля 2012 года.
- ↑ Владимиров, 1969, с. 19.
- ↑ Кузнецов, 2007.
- ↑ Виленкин Н. Я., Шибасов Л. П. Шибасова 3. Ф. За страницами учебника математики : Арифметика. Алгебра. Геометрия : Кн. для учащихся 10-11-х кл. общеобразоват. учреждений. — М.: Просвещение : АО "Учеб. лит.", 1996. — С. 197. — 319 с.
Литература
- Владимиров Д. А. Булевы алгебры. — М.: «Наука», 1969. — 320 с.
- Кузнецов О. П. Дискретная математика для инженера. — СПб.: Лань, 2007. — 394 с.
- Иванов Б. Н. Дискретная математика. Алгоритмы и программы. Расширенный курс. — М.: «Известия», 2011. — 512 с. (недоступная ссылка)
- Гуров С.И. Булевы алгебры, упорядоченные множества, решетки: Определения, свойства, примеры. — М.: Либроком, 2013. — 352 с.
