Булевой алгеброй[1][2][3] называется непустое множество A с двумя бинарными операциями (аналог конъюнкции), (аналог дизъюнкции), одной унарной операцией (аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для любых a, b и c из множества A верны следующие аксиомы:
ассоциативность | ||
коммутативность | ||
законы поглощения | ||
дистрибутивность | ||
дополнительность |
Первые три аксиомы означают, что (A, , ) является решёткой. Таким образом, булева алгебра может быть определена как дистрибутивная решётка, в которой выполнены две последние аксиомы. Структура, в которой выполняются все аксиомы, кроме предпоследней, называется псевдобулевой алгеброй. Названа в честь Джорджа Буля.
Из аксиом видно, что наименьшим элементом является 0, наибольшим является 1, а дополнение ¬a любого элемента a однозначно определено. Для всех a и b из A верны также следующие равенства:
дополнение 0 есть 1 и наоборот | ||
законы де Моргана | ||
. | инволютивность отрицания, закон снятия двойного отрицания. |
В данном разделе повторяются свойства и аксиомы, описанные выше с добавлением ещё нескольких.
Сводная таблица свойств и аксиом, описанных выше:
1 коммутативность, переместительность | ||
2 ассоциативность, сочетательность | ||
3.1 конъюнкция относительно дизъюнкции | 3.2 дизъюнкция относительно конъюнкции | 3 дистрибутивность, распределительность |
4 комплементность, дополнительность (свойства отрицаний) | ||
5 законы де Моргана | ||
6 законы поглощения | ||
7 Блейка-Порецкого | ||
8 Идемпотентность | ||
9 инволютивность отрицания, закон снятия двойного отрицания | ||
10 свойства констант | ||
дополнение 0 есть 1 | дополнение 1 есть 0 | |
11 Склеивание |
|
|
|
В булевых алгебрах существуют двойственные утверждения, они либо одновременно верны, либо одновременно неверны. Именно, если в формуле, которая верна в некоторой булевой алгебре, поменять все конъюнкции на дизъюнкции, 0 на 1, ≤ на > и наоборот или < на ≥ и наоборот, то получится формула, также истинная в этой булевой алгебре. Это следует из симметричности аксиом относительно таких замен.
Можно доказать, что любая конечная булева алгебра изоморфна булевой алгебре всех подмножеств какого-то множества. Отсюда следует, что количество элементов в любой конечной булевой алгебре будет степенью двойки.
Теорема Стоуна утверждает, что любая булева алгебра изоморфна булевой алгебре всех открыто-замкнутых множеств какого-то компактного вполне несвязного хаусдорфова топологического пространства.
В 1933 году американский математик Хантингтон[en] предложил следующую аксиоматизацию для булевых алгебр:
Здесь использованы обозначения Хантингтона: + означает дизъюнкцию, n — отрицание.
Герберт Роббинс поставил следующий вопрос: можно ли сократить последнюю аксиому так, как написано ниже, то есть будет ли определённая выписанными ниже аксиомами структура булевой алгеброй?
Аксиоматизация алгебры Роббинса:
Этот вопрос оставался открытым с 1930-х годов и был любимым вопросом Тарского и его учеников.
В 1996 году Вильям МакКьюн, используя некоторые полученные до него результаты, дал утвердительный ответ на этот вопрос. Таким образом, любая алгебра Роббинса является булевой алгеброй.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .