Меню Главная Случайная статья Настройки Булева алгебра Материал из https://ru.wikipedia.org Эта статья об алгебраической системе. О разделе математической логики, изучающем высказывания и операции над ними, см. Алгебра логики. Булевой алгеброй[1][2][3] называется непустое множество A с двумя бинарными операциями ${\displaystyle \land }$ (аналог конъюнкции), ${\displaystyle \lor }$ (аналог дизъюнкции), одной унарной операцией ${\displaystyle \lnot }$ (аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для любых a, b и c из множества A верны следующие аксиомы: ${\displaystyle a\lor (b\lor c)=(a\lor b)\lor c}$ ${\displaystyle a\land (b\land c)=(a\land b)\land c}$ ассоциативность ${\displaystyle a\lor b=b\lor a}$ ${\displaystyle a\land b=b\land a}$ коммутативность ${\displaystyle a\lor (a\land b)=a}$ ${\displaystyle a\land (a\lor b)=a}$ законы поглощения ${\displaystyle a\lor (b\land c)=(a\lor b)\land (a\lor c)}$ ${\displaystyle a\land (b\lor c)=(a\land b)\lor (a\land c)}$ дистрибутивность ${\displaystyle a\lor \lnot a=1}$ ${\displaystyle a\land \lnot a=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}}=0\end{aligned}}}$ Первые три аксиомы означают, что (A, ${\displaystyle \land }$, ${\displaystyle \lor }$) является решёткой. Таким образом, булева алгебра может быть определена как дистрибутивная решётка, в которой выполнены две последние аксиомы. Структура, в которой выполняются все аксиомы, кроме предпоследней, называется псевдобулевой алгеброй. Названа в честь Джорджа Буля. Содержание 1 Некоторые свойства 2 Основные тождества 3 Примеры 4 Принцип двойственности 5 Представления булевых алгебр 6 Аксиоматизация 7 См. также 8 Примечания 9 Литература Некоторые свойства Из аксиом видно, что наименьшим элементом является 0, наибольшим является 1, а дополнение ¬a любого элемента a однозначно определено. Для всех a и b из A верны также следующие равенства: ${\displaystyle a\lor a=a}$ ${\displaystyle a\land a=a}$ ${\displaystyle a\lor 0=a}$ ${\displaystyle a\land 1=a}$ ${\displaystyle a\lor 1=1}$ ${\displaystyle a\land 0=0}$ ${\displaystyle \lnot 0=1}$ ${\displaystyle \lnot 1=0}$ дополнение 0 есть 1 и наоборот ${\displaystyle \lnot (a\lor b)=\lnot a\land \lnot b}$ ${\displaystyle \lnot (a\land b)=\lnot a\lor \lnot b}$ законы де Моргана ${\displaystyle \lnot \lnot a=a}$. инволютивность отрицания, закон снятия двойного отрицания. Основные тождества В данном разделе повторяются свойства и аксиомы, описанные выше с добавлением ещё нескольких. Сводная таблица свойств и аксиом, описанных выше: ${\displaystyle a\lor b=b\lor a}$ ${\displaystyle a\land b=b\land a}$ 1 коммутативность, переместительность ${\displaystyle a\lor (b\lor c)=(a\lor b)\lor c}$ ${\displaystyle a\land (b\land c)=(a\land b)\land c}$ 2 ассоциативность, сочетательность 3.1 конъюнкция относительно дизъюнкции ${\displaystyle a\lor (b\land c)=(a\lor b)\land (a\lor c)}$ 3.2 дизъюнкция относительно конъюнкции ${\displaystyle a\land (b\lor c)=(a\land b)\lor (a\land c)}$ 3 дистрибутивность, распределительность ${\displaystyle a\lor \lnot a=1}$ ${\displaystyle a\land \lnot a=0}$ 4 комплементность, дополнительность (свойства отрицаний) ${\displaystyle \lnot (a\lor b)=\lnot a\land \lnot b}$ ${\displaystyle \lnot (a\land b)=\lnot a\lor \lnot b}$ 5 законы де Моргана ${\displaystyle a\lor (a\land b)=a}$ ${\displaystyle a\land (a\lor b)=a}$ 6 законы поглощения ${\displaystyle a\lor (\lnot a\land b)=a\lor b}$ ${\displaystyle a\land (\lnot a\lor b)=a\land b}$ 7 Блейка-Порецкого ${\displaystyle a\lor a=a}$ ${\displaystyle a\land a=a}$ 8 Идемпотентность ${\displaystyle \lnot \lnot a=a}$ 9 инволютивность отрицания, закон снятия двойного отрицания ${\displaystyle a\lor 0=a}$ ${\displaystyle a\land 1=a}$ 10 свойства констант ${\displaystyle a\lor 1=1}$ ${\displaystyle a\land 0=0}$ дополнение 0 есть 1 ${\displaystyle \lnot 0=1}$ дополнение 1 есть 0 ${\displaystyle \lnot 1=0}$ ${\displaystyle (a\lor b)\land (\lnot a\lor b)=b}$ ${\displaystyle (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. Рассмотрим множество ${\displaystyle U}$ всех натуральных делителей заданного натурального числа ${\displaystyle m,}$ свободного от квадратов. Определим на ${\displaystyle U}$ две бинарные операции: нахождение наибольшего общего делителя (аналог конъюнкции) и наименьшего общего кратного (аналог дизъюнкции); роль отрицания играет одноместная операция, сопоставляющая делителю ${\displaystyle d}$ делитель ${\displaystyle m/d.}$ Полученная структура является булевой алгеброй; в ней аналогами булевских нуля и единицы выступают соответственно числа 1 и ${\displaystyle m.}$ Переложение приведенных выше общих аксиом и свойств булевой алгебры для множества ${\displaystyle U}$ даёт ряд полезных и не очевидных теоретико-числовых тождеств[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 с. Архивировано 6 мая 2018 года. Литература