Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Эта статья содержит информацию об алгебраической системе. Информация об основных операциях и понятиях булевой логики находится в статье Алгебра логики.

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

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

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

Некоторые свойства Править

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

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

Основные тождества Править

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

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

 a \lor b = b \lor a  a \land b = b \land a 1 коммутативность
 a \lor (b \lor c) = (a \lor b) \lor c  a \land (b \land c) = (a \land b) \land c 2 ассоциативность
3.1 конъюнкция относительно дизъюнкции  a \lor (b \land c) = (a \lor b) \land (a \lor c) 3.2 дизъюнкция относительно конъюнкции  a \land (b \lor c) = (a \land b) \lor (a \land c) 3 дистрибутивность
 a \lor \lnot a = 1  a \land \lnot a = 0 4 дополнительность (свойства отрицаний)
 \lnot (a \lor b) = \lnot a \land \lnot b  \lnot (a \land b) = \lnot a \lor \lnot b 5 законы де Моргана
 a \lor (a \land b) = a  a \land (a \lor b) = a 6 законы поглощения
a \lor(\lnot a \land b) = a \lor b a \land(\lnot a \lor b) = a \land b 7 Блейка-Порецкого
 a \lor a = a  a \land a = a 8 Идемпотентность
 \lnot \lnot a = a 9 инволютивность отрицания
 a \lor 0 = a  a \land 1 = a 10 свойства констант
 a \lor 1 = 1  a \land 0 = 0
дополнение 0 есть 1  \lnot 0 = 1 дополнение 1 есть 0 \lnot 1 = 0
 (a \lor b)\land(\lnot a \lor b)=b   (a \land b) \lor (\lnot a \land 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.
  • Если R — произвольное кольцо, то на нём можно определить множество центральных идемпотентов так:
    A = { eR : e2 = e, ex = xe, ∀xR },
    тогда множество A будет булевой алгеброй с операциями ef := e + fef и ef := ef.

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

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

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

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

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

Аксиоматизация Править

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

  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.

Этот вопрос оставался открытым с 30-х годов и был любимым вопросом Тарского и его учеников.

В 1996 г. Вильям МакКьюн, используя некоторые полученные до него результаты, дал утвердительный ответ на этот вопрос. Таким образом, любая алгебра Роббинса является булевой алгеброй.

См. такжеПравить

bg:Булева алгебра bn:বুলিয়ান বীজগণিত ca:Àlgebra de Boole cs:Booleova algebraeo:Bulea algebrofa:جبر بولیgl:Álxebra de Boole he:אלגברה בוליאנית hr:Booleova algebra hu:Boole-algebra id:Aljabar Boolean io:Booleana algebrolt:Būlio algebra nl:Booleaanse algebra no:Boolsk algebra pl:Algebra Boole'asimple:Boolean algebra sl:Booleova algebra sr:Булова алгебра sv:Boolesk algebra th:พีชคณิตแบบบูล tl:Aldyebrang Booleanuk:Булева алгебра

Викия-сеть

Случайная вики