Булева алгебра
- Эта статья об алгебраической системе. О разделе математической логики, изучающем высказывания и операции над ними, см. Алгебра логики.
Булевой алгеброй[1][2][3] называется непустое множество A с двумя бинарными операциями ∧{displaystyle land }
a∨(b∨c)=(a∨b)∨c{displaystyle alor (blor c)=(alor b)lor c}  | a∧(b∧c)=(a∧b)∧c{displaystyle aland (bland c)=(aland b)land c}  | ассоциативность |
a∨b=b∨a{displaystyle alor b=blor a}  | a∧b=b∧a{displaystyle aland b=bland a}  | коммутативность |
a∨(a∧b)=a{displaystyle alor (aland b)=a}  | a∧(a∨b)=a{displaystyle aland (alor b)=a}  | законы поглощения |
a∨(b∧c)=(a∨b)∧(a∨c){displaystyle alor (bland c)=(alor b)land (alor c)}  | a∧(b∨c)=(a∧b)∨(a∧c){displaystyle aland (blor c)=(aland b)lor (aland c)}  | дистрибутивность |
a∨¬a=1{displaystyle alor lnot a=1}  | a∧¬a=0{displaystyle aland lnot a=0}  | дополнительность |
a+(b+c)=(a+b)+ca(bc)=(ab)ca+b=b+aab=baa+ab=aa(a+b)=aa+bc=(a+b)(a+c)a(b+c)=ab+aca+a¯=1aa¯=0{displaystyle {begin{aligned}&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}}=0end{aligned}}}
Первые три аксиомы означают, что (A, ∧{displaystyle land }
Названа в честь Джорджа Буля.
Содержание
1 Некоторые свойства
2 Основные тождества
3 Примеры
4 Принцип двойственности
5 Представления булевых алгебр
6 Аксиоматизация
7 См. также
8 Примечания
9 Литература
Некоторые свойства |
Из аксиом видно, что наименьшим элементом является 0, наибольшим является 1, а дополнение ¬a любого элемента a однозначно определено. Для всех a и b из A верны также следующие равенства:
a∨a=a{displaystyle alor a=a}  | a∧a=a{displaystyle aland a=a}  | |
a∨0=a{displaystyle alor 0=a}  | a∧1=a{displaystyle aland 1=a}  | |
a∨1=1{displaystyle alor 1=1}  | a∧0=0{displaystyle aland 0=0}  | |
¬0=1{displaystyle lnot 0=1}  | ¬1=0{displaystyle lnot 1=0}  | дополнение 0 есть 1 и наоборот |
¬(a∨b)=¬a∧¬b{displaystyle lnot (alor b)=lnot aland lnot b}  | ¬(a∧b)=¬a∨¬b{displaystyle lnot (aland b)=lnot alor lnot b}  | законы де Моргана |
¬¬a=a{displaystyle lnot lnot a=a}  . | инволютивность отрицания, закон снятия двойного отрицания. |
Основные тождества |
В данном разделе повторяются свойства и аксиомы, описанные выше с добавлением ещё нескольких.
Сводная таблица свойств и аксиом, описанных выше:
a∨b=b∨a{displaystyle alor b=blor a} | a∧b=b∧a{displaystyle aland b=bland a} | 1 коммутативность, переместительность |
a∨(b∨c)=(a∨b)∨c{displaystyle alor (blor c)=(alor b)lor c} | a∧(b∧c)=(a∧b)∧c{displaystyle aland (bland c)=(aland b)land c} | 2 ассоциативность, сочетательность |
| 3.1 конъюнкция относительно дизъюнкции a∨(b∧c)=(a∨b)∧(a∨c){displaystyle alor (bland c)=(alor b)land (alor c)} | 3.2 дизъюнкция относительно конъюнкции a∧(b∨c)=(a∧b)∨(a∧c){displaystyle aland (blor c)=(aland b)lor (aland c)} | 3 дистрибутивность, распределительность |
a∨¬a=1{displaystyle alor lnot a=1} | a∧¬a=0{displaystyle aland lnot a=0} | 4 комплементность, дополнительность (свойства отрицаний) |
¬(a∨b)=¬a∧¬b{displaystyle lnot (alor b)=lnot aland lnot b} | ¬(a∧b)=¬a∨¬b{displaystyle lnot (aland b)=lnot alor lnot b} | 5 законы де Моргана |
a∨(a∧b)=a{displaystyle alor (aland b)=a} | a∧(a∨b)=a{displaystyle aland (alor b)=a} | 6 законы поглощения |
a∨(¬a∧b)=a∨b{displaystyle alor (lnot aland b)=alor b}  | a∧(¬a∨b)=a∧b{displaystyle aland (lnot alor b)=aland b}  | 7 Блейка-Порецкого |
a∨a=a{displaystyle alor a=a} | a∧a=a{displaystyle aland a=a} | 8 Идемпотентность |
¬¬a=a{displaystyle lnot lnot a=a} | 9 инволютивность отрицания, закон снятия двойного отрицания | |
a∨0=a{displaystyle alor 0=a} | a∧1=a{displaystyle aland 1=a} | 10 свойства констант |
a∨1=1{displaystyle alor 1=1} | a∧0=0{displaystyle aland 0=0} | |
| дополнение 0 есть 1 ¬0=1{displaystyle lnot 0=1} | дополнение 1 есть 0 ¬1=0{displaystyle lnot 1=0} | |
(a∨b)∧(¬a∨b)=b{displaystyle (alor b)land (lnot alor b)=b}  | (a∧b)∨(¬a∧b)=b{displaystyle (aland b)lor (lnot aland b)=b}  | 11 Склеивание |
Примеры |
- Самая простая нетривиальная булева алгебра содержит всего два элемента, 0 и 1, а действия в ней определяются следующей таблицей:
|
|
|
- Эта булева алгебра наиболее часто используется в логике, так как является точной моделью классического исчисления высказываний. В этом случае 0 называют ложью, 1 — истиной. Выражения, содержащие булевы операции и переменные, представляют собой высказывательные формы.
- Множество всех подмножеств данного множества S образует булеву алгебру относительно операций ∨ := ∪ (объединение), ∧ := ∩ (пересечение) и унарной операции дополнения. Наименьший элемент здесь — пустое множество, а наибольший — всё S.
- Рассмотрим множество U{displaystyle U}
всех натуральных делителей заданного натурального числа m,{displaystyle m,}
свободного от квадратов. Определим на U{displaystyle U}
делитель m/d.{displaystyle m/d.}
Полученная структура является булевой алгеброй; в ней аналогами булевских нуля и единицы выступают соответственно числа 1 и m.{displaystyle m.}
Переложение приведенных выше общих аксиом и свойств булевой алгебры для множества U{displaystyle U}
Алгебра Линденбаума — Тарского (фактормножество всех утверждений по отношению равносильности в данном исчислении с соответствующими операциями) какого-либо исчисления высказываний является булевой алгеброй. В этом случае истинностная оценка формул исчисления является гомоморфизмом алгебры Линденбаума — Тарского в двухэлементную булеву алгебру.- Если R — произвольное кольцо, то на нём можно определить множество центральных идемпотентов так:
A = { e ∈ R : e² = e, ex = xe, ∀x ∈ R },
тогда множество A будет булевой алгеброй с операциями e ∨ f := e + f − ef и e ∧ f := ef.
Принцип двойственности |
В булевых алгебрах существуют двойственные утверждения, они либо одновременно верны, либо одновременно неверны. Именно, если в формуле, которая верна в некоторой булевой алгебре, поменять все конъюнкции на дизъюнкции, 0 на 1, ≤ на > и наоборот или < на ≥ и наоборот, то получится формула, также истинная в этой булевой алгебре. Это следует из симметричности аксиом относительно таких замен.
Представления булевых алгебр |
Можно доказать, что любая конечная булева алгебра изоморфна булевой алгебре всех подмножеств какого-то множества. Отсюда следует, что количество элементов в любой конечной булевой алгебре будет степенью двойки.
Теорема Стоуна утверждает, что любая булева алгебра изоморфна булевой алгебре всех открыто-замкнутых множеств какого-то компактного вполне несвязного хаусдорфова топологического пространства.
Аксиоматизация |
В 1933 году американский математик Хантингтон[en] предложил следующую аксиоматизацию для булевых алгебр:
Аксиома коммутативности: 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 с.
 Дискретная математика | |
|---|---|
| |
