Булева алгебра (структура)

В абстрактной алгебре булева алгебра или булева решетка является дополняемой дистрибутивной решеткой . Этот тип алгебраической структуры отражает основные свойства как операций над множествами , так и логических операций. Булеву алгебру можно рассматривать как обобщение степенной алгебры множеств или поля множеств , или ее элементы можно рассматривать как обобщенные значения истинности . Это также частный случай алгебры Де Моргана и алгебры Клини (с инволюцией) .

Каждая булева алгебра порождает булево кольцо и наоборот, при этом умножение колец соответствует конъюнкции или встрече ∧, а добавление колец — исключительной дизъюнкции или симметричной разности (не дизъюнкции ∨). Однако теории булевых колец присуща асимметрия между двумя операторами, в то время как аксиомы и теоремы булевой алгебры выражают симметрию теории, описываемую принципом двойственности . ^[1]

История

Термин «булева алгебра» назван в честь Джорджа Буля (1815–1864), английского математика-самоучки. Он представил алгебраическую систему первоначально в небольшой брошюре « Математический анализ логики» , опубликованной в 1847 году в ответ на продолжающуюся общественную полемику между Огастесом Де Морганом и Уильямом Гамильтоном , а затем в виде более существенной книги «Законы мышления », опубликованной в 1847 году. 1854. Формулировка Буля отличается от описанной выше в некоторых важных отношениях. Например, конъюнкция и дизъюнкция в булевском языке не были двойной парой операций. Булева алгебра возникла в 1860-х годах в статьях Уильяма Джевонса и Чарльза Сандерса Пирса . Первое систематическое представление булевой алгебры и дистрибутивных решеток принадлежит Vorlesungen 1890 года Эрнста Шредера . Первым обширным исследованием булевой алгебры на английском языке является « Универсальная алгебра» А.Н. Уайтхеда 1898 года . Булева алгебра как аксиоматическая алгебраическая структура в современном аксиоматическом смысле начинается со статьи Эдварда В. Хантингтона 1904 года . Булева алгебра достигла зрелости как серьезная математика благодаря работам Маршалла Стоуна в 1930-х годах и благодаря «Теории решеток » Гаррета Биркгофа 1940 года . В 1960-х годах Пол Коэн , Дана Скотт и другие нашли глубокие новые результаты в математической логике и аксиоматической теории множеств , используя ответвления булевой алгебры, а именно модели принуждения и булевозначные модели .

Определение

Булева алгебра — это множество $A$ , снабженное двумя бинарными операциями $\land$ (называемыми «встретиться» или «и»), $\lor$ (называемыми «присоединиться» или «или»), унарной операцией $\neg$ (называемой «дополнением» или «не»). ) и два элемента $0$ и $1$ из $A$ (называемые «нижним» и «верхним» или «наименьшим» и «наибольшим» элементом, также обозначаемые символами $⊥$ и $⊤$ соответственно), такие, что для всех элементов $a$ , $b$ и $c$ из $A$ справедливы следующие аксиомы : ^[2]

Однако заметим, что закон поглощения и даже закон ассоциативности можно исключить из набора аксиом, поскольку они могут быть выведены из других аксиом (см. Доказанные свойства).

Булева алгебра, состоящая только из одного элемента, называется тривиальной булевой алгеброй или вырожденной булевой алгеброй . (В более старых работах некоторые авторы требовали, чтобы $0$ и $1$ были разными элементами, чтобы исключить этот ^случай^.⁾

Из последних трех пар аксиом, приведенных выше (тождество, дистрибутивность и дополнение), или из аксиомы поглощения, следует, что

a = b \land a

тогда и только тогда, когда

a \lor b = b

Отношение $\leq,$ определяемое $a \leq b$ , если эти эквивалентные условия выполняются, является частичным порядком с наименьшим элементом 0 и наибольшим элементом 1. Встреча $a \land b$ и соединение $a \lor b$ двух элементов совпадают с их нижней и верхней гранями соответственно, относительно ≤.

Первые четыре пары аксиом составляют определение ограниченной решетки .

Из первых пяти пар аксиом следует, что любое дополнение единственно.

Набор аксиом самодуален в том смысле, что если в аксиоме заменить $\lor$ на $\land$ и $0$ на $1$ , результат снова станет аксиомой. Следовательно, применяя эту операцию к булевой алгебре (или булевой решетке), можно получить другую булеву алгебру с теми же элементами; это называется его двойственным . ^[3]

Примеры

Простейшая нетривиальная булева алгебра, двухэлементная булева алгебра , имеет только два элемента, $0$ и $1$ , и определяется правилами:

Он имеет приложения в логике , интерпретируя $0$ как ложь , $1$ как истину , $\land$ как и , $\lor$ как или и $\neg$ как нет . Выражения, включающие переменные и логические операции, представляют собой формы операторов, и можно показать, что два таких выражения равны, используя приведенные выше аксиомы, тогда и только тогда, когда соответствующие формы операторов логически эквивалентны .

Двухэлементная булева алгебра также используется для проектирования схем в электротехнике ; ^{[примечание 1]} здесь 0 и 1 представляют два разных состояния одного бита в цифровой схеме , обычно высокого и низкого напряжения . Схемы описываются выражениями, содержащими переменные, и два таких выражения равны для всех значений переменных тогда и только тогда, когда соответствующие схемы имеют одинаковое поведение ввода-вывода. Более того, любое возможное поведение ввода-вывода можно смоделировать с помощью подходящего логического выражения.

Двухэлементная булева алгебра также важна в общей теории булевых алгебр, поскольку уравнение с несколькими переменными обычно истинно во всех булевых алгебрах тогда и только тогда, когда оно истинно в двухэлементной булевой алгебре (что можно проверить с помощью тривиальный алгоритм перебора для малого числа переменных). Это можно, например, использовать, чтобы показать, что следующие законы ( теоремы консенсуса ) обычно справедливы во всех булевых алгебрах:
- $(а \lor б) \land (\neg а \lor c) \land (б \lor c) \equiv (а \lor б) \land (\neg а \lor c)$
- $(а \land б) \lor (\neg а \land c) \lor (б \land c) \equiv (а \land б) \lor (\neg а \land c)$

Набор степеней (множество всех подмножеств) любого данного непустого множества $S$ образует булеву алгебру, алгебру множеств с двумя операциями $\lor := \cup$ (объединение) и $\land := \cap$ (пересечение). Наименьший элемент 0 — это пустое множество , а самый большой элемент $1$ — это само множество $S.$

После двухэлементной булевой алгебры простейшей булевой алгеброй является та, которая определяется набором степеней двух атомов:

Множество $A$ всех подмножеств $S$ , которые либо конечны, либо коконечны, является булевой алгеброй и алгеброй множеств , называемой конечно-коконитной алгеброй . Если $S$ бесконечно, то множество всех коконитных подмножеств $S$ , называемое фильтром Фреше , является свободным ультрафильтром на $A.$ Однако фильтр Фреше не является ультрафильтром на наборе мощности $S.$
Начиная с исчисления высказываний с $κ$ символами предложений, сформируйте алгебру Линденбаума (то есть множество предложений в исчислении высказываний по модулю логической эквивалентности ). Эта конструкция дает булеву алгебру. Фактически это свободная булева алгебра на $κ$ образующих. Присваивание истинности в исчислении высказываний представляет собой гомоморфизм булевой алгебры из этой алгебры в двухэлементную булеву алгебру.
Для любого линейно упорядоченного множества $L$ с наименьшим элементом интервальная алгебра — это наименьшая булева алгебра подмножеств $L$ , содержащая все полуоткрытые интервалы $[a, b)$ такие, что $a$ находится в $L$ , а $b$ либо находится в $L$ , либо равен до $\infty$ . Интервальные алгебры полезны при изучении алгебр Линденбаума – Тарского ; каждая счетная булева алгебра изоморфна интервальной алгебре.

Для любого натурального числа $n$ набор всех положительных делителей n , определяющих $a$ $\leq$ $b$ $,$ если $a$ делит $b$ , образует дистрибутивную решетку . Эта решетка является булевой алгеброй тогда и только тогда, когда $n$ свободно от квадратов . Нижний и верхний элементы этой булевой алгебры — натуральные числа $1$ и $n$ соответственно. Дополнение $a$ задается $n$ $/$ $a$ . Встреча и соединение $a$ и $b$ задаются наибольшим общим делителем ( $НОД$ ) и наименьшим общим кратным ( $lcm$ ) $a$ и $b$ соответственно. Кольцевое сложение $a$ $+$ $b$ задается формулой $lcm($ $a$ $,$ $b$ $)/gcd($ $a$ $,$ $b$ $)$ . На рисунке показан пример для $n$ $= 30$ . В качестве контрпримера, учитывая несвободное от квадратов $число n$ $= 60$ , наибольший общий делитель числа 30 и его дополнения 2 будет равен 2, а нижний элемент должен быть равен 1.
Другие примеры булевых алгебр возникают из топологических пространств : если $X$ является топологическим пространством, то совокупность всех подмножеств $X$ , которые являются как открытыми, так и замкнутыми, образует булеву алгебру с операциями $\lor := \cup$ (объединение) и $\land := \cap$ (перекресток).
Если $R$ — произвольное кольцо, то его набор центральных идемпотентов , который представляет собой множество

A=\left\{e\in R:e^{2}=e{\text{ и }}ex=xe\;{\text{для всех }}\;x\in R\right\ },

e \lor f := e + f - ef

e \land f := ef

Гомоморфизмы и изоморфизмы

Гомоморфизм между двумя булевыми алгебрами $A$ и $B$ — это функция $f$ $:$ $A$ $\to$ $B такая,$ что для всех $a$ , $b$ в $A$ :

ж (а \lor б) знак равно ж (а) \lor ж (б)

ж (а \land б) знак равно ж (а) \land ж (б)

ж (0) = 0

ж (1) знак равно 1

Отсюда следует, что f $(\nega) = \negf (a) для$ всех $a$ в $A.$ Класс всех булевых алгебр вместе с этим понятием морфизма образует полную подкатегорию категории решеток .

Изоморфизмом между двумя булевыми алгебрами $A$ и $B$ называется гомоморфизм $f$ $:$ $A$ $\to$ $B$ с обратным гомоморфизмом, то есть гомоморфизм $g$ $:$ $B$ $\to$ $A$ такой , что композиция $g$ $\circ$ $f$ $:$ $A$ $\to$ $A$ является тождественной функцией на $A$ , и композиция $f$ $\circ$ $g$ $:$ $B$ $\to$ $B$ является тождественной функцией на $B$ . Гомоморфизм булевых алгебр является изоморфизмом тогда и только тогда, когда он биективен .

Булевы кольца

Каждая булева алгебра $(A, \land, \lor)$ порождает кольцо ( $A, +, \cdot)$ путем определения $a + b := (a \land \neg b) \lor (b \land \neg a) = (a \lor b) \land \neg (a \land b)$ (эта операция называется симметричной разностью в случае множеств и XOR в случае логики) и $a \cdot b := a \land b$ . Нулевой элемент этого кольца совпадает с 0 булевой алгебры; мультипликативный единичный элемент кольца — это единица $булевой$ алгебры. Это кольцо обладает тем свойством, что $a \cdot a = a$ для всех $a$ из $A$ ; кольца, обладающие этим свойством, называются булевыми кольцами .

И наоборот, если дано булево кольцо $A$ , мы можем превратить его в булевую алгебру, определив $x \lor y := x + y + (x \cdot y)$ и $x \land y := x \cdot y$ . ^[4]^[5] Поскольку эти две конструкции являются обратными друг другу, мы можем сказать, что каждое булево кольцо возникает из булевой алгебры, и наоборот. Более того, отображение $f : A \to B$ является гомоморфизмом булевых алгебр тогда и только тогда, когда оно является гомоморфизмом булевых колец. Категории булевых колец и булевых алгебр эквивалентны ; ^[6] на самом деле категории изоморфны .

Сян (1985) предложил алгоритм, основанный на правилах, для проверки того, обозначают ли два произвольных выражения одно и то же значение в каждом булевом кольце. В более общем плане Буде, Жуанно и Шмидт-Шаус (1989) предложили алгоритм для решения уравнений между произвольными выражениями в виде булевых колец. Оба алгоритма, основанные на сходстве булевых колец и булевых алгебр, находят применение в автоматизированном доказательстве теорем .

Идеалы и фильтры

Идеал булевой алгебры $A$ — это непустое подмножество $I такое$ , что для всех $x$ , $y$ в $I$ имеем $x$ $\lor$ $y$ в $I$ и для всех $a$ в $A$ имеем $a$ $\land$ $x$ в $I.$ Это понятие идеала совпадает с понятием идеала кольца в булевом кольце $A$ . Идеал $I$ из $A$ называется простым, если $I$ $\neq$ $A$ и если $a$ $\land$ $b$ в $I$ всегда влечет за собой $a$ в $I$ или $b$ в $I$ . Более того, для каждого $a$ $\in$ $A$ имеем $a$ $\land -$ $a$ $= 0 \in$ $I$ , и тогда, если $I$ простое число, мы имеем $a$ $\in$ $I$ или $-$ $a$ $\in$ $I$ для каждого $a$ $\in$ $A.$ Идеал $I$ из $A$ называется максимальным , если $I$ $\neq$ $A$ и если единственным идеалом, правильно содержащим $I$ , является сам $A.$ Для идеала $I$ , если $a$ $\notin$ $I$ и $-$ $a$ $\notin$ $I$ , то $I$ $\cup$ $a$ или $I$ $\cup {-$ $a$ $}$ содержится в другом собственном идеале $J.$ Следовательно, такое $I$ не является максимальным, и поэтому понятия простого идеала и максимального идеала эквивалентны в булевых алгебрах. Более того, эти понятия совпадают с теоретико-кольцевыми понятиями простого идеала и максимального идеала в булевом кольце $A$ .

Двойник идеала – это фильтр . Фильтр булевой алгебры $A$ — это непустое подмножество $p такое,$ $что$ для всех $x$ , $y$ в $p$ имеем $x$ $\land$ $y$ в p и для всех $a$ в $A$ имеем $a$ $\lor$ $x$ в $p$ . Двойственным максимальному (или простому ) идеалу в булевой алгебре является ультрафильтр . Альтернативно ультрафильтры можно описать как двузначные морфизмы из $A$ в двухэлементную булеву алгебру. Утверждение, что каждый фильтр в булевой алгебре может быть расширен до ультрафильтра, называется леммой об ультрафильтре и не может быть доказано в теории множеств Цермело – Френкеля (ZF), если ZF непротиворечив . В ZF лемма об ультрафильтре строго слабее аксиомы выбора . Лемма об ультрафильтре имеет множество эквивалентных формулировок: каждая булева алгебра имеет ультрафильтр , каждый идеал в булевой алгебре можно расширить до простого идеала и т. д.

Представительства

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

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

Аксиоматика

Первая аксиоматизация булевых решеток/алгебр в целом была дана английским философом и математиком Альфредом Нортом Уайтхедом в 1898 году . ^[7]^[8] Она включала вышеуказанные аксиомы, а также $x \lor 1 = 1$ и $x \land 0 = 0$ . В 1904 году американский математик Эдвард В. Хантингтон (1874–1952) дал, вероятно, самую экономную аксиоматизацию, основанную на $\land$ , $\lor$ , $\neg$ , и даже доказал законы ассоциативности (см. Вставку). ^[9] Он также доказал, что эти аксиомы независимы друг от друга. ^[10] В 1933 году Хантингтон сформулировал следующую элегантную аксиоматизацию булевой алгебры. ^[11] Для того, чтобы его можно было прочитать как «дополнение», требуется всего одна бинарная операция $+$ и унарный функциональный символ $n$ , которые удовлетворяют следующим законам:

Коммутативность : $x + y = y + x$ .
Ассоциативность : $(x + y) + z знак равно x + (y + z)$ .
Уравнение Хантингтона : $n (n (x) + y) + n (n (x) + n (y)) = x$ .

Герберт Роббинс тут же спросил: Если уравнение Хантингтона заменить двойственным ему, а именно:

Уравнение Роббинса : $n (n (x + y) + n (x + n (y))) = x$ ,

составляют ли (1), (2) и (4) основу булевой алгебры? Называя (1), (2) и (4) алгеброй Роббинса , возникает вопрос: является ли каждая алгебра Роббинса булевой алгеброй? Этот вопрос (который стал известен как гипотеза Роббинса ) оставался открытым на протяжении десятилетий и стал любимым вопросом Альфреда Тарского и его учеников. В 1996 году Уильям МакКьюн из Аргоннской национальной лаборатории , опираясь на более ранние работы Ларри Воса, Стива Уинкера и Боба Вероффа, утвердительно ответил на вопрос Роббинса: каждая алгебра Роббинса является булевой алгеброй. Решающее значение для доказательства МакКьюна имела разработанная им компьютерная программа EQP . Упрощение доказательства МакКьюна см. в Dahn (1998).

Дальнейшая работа была проделана по сокращению количества аксиом; см. Минимальные аксиомы булевой алгебры .

Обобщения

Удаление требования существования единицы из аксиом булевой алгебры дает «обобщенные булевы алгебры». Формально дистрибутивная решетка $B$ является обобщенной булевой решеткой, если она имеет наименьший элемент $0$ и для любых элементов $a$ и $b$ в $B$ таких, что $a \leq b$ , существует элемент $x$ такой, что $a \land x = 0$ и $a \lor x = б$ . Определив $a \ b$ как единственный $x$ такой, что $(a \land b) \lor x = a$ и $(a \land b) \land x = 0$ , мы говорим, что структура $( B , ∧, ∨, \, 0)$ является обобщенной логической величиной. алгебра , а $(B, \lor, 0)$ — обобщенная булева полурешетка . Обобщенные булевы решетки — это в точности идеалы булевых решеток.

Структура, которая удовлетворяет всем аксиомам булевых алгебр, за исключением двух аксиом дистрибутивности, называется решеткой с ортодополнениями . Решетки с ортодополнениями естественным образом возникают в квантовой логике как решетки замкнутых линейных подпространств для сепарабельных гильбертовых пространств .

Смотрите также

Примечания

^ Строго говоря, инженеры-электрики склонны использовать дополнительные состояния для представления других состояний цепи, таких как высокое сопротивление — см. IEEE 1164 или IEEE 1364 .

Внешние ссылки

«Булева алгебра», Математическая энциклопедия , EMS Press , 2001 [1994]
Стэнфордская энциклопедия философии : «Математика булевой алгебры», Дж. Дональд Монк.
МакКьюн В., 1997. Алгебры Роббинса являются логическими JAR 19(3), 263–276.
«Булева алгебра» Эрика В. Вайсштейна , Демонстрационный проект Wolfram , 2007.
Беррис, Стэнли Н.; Санкаппанавар, Х.П., 1981. Курс универсальной алгебры. Спрингер-Верлаг. ISBN 3-540-90578-2 .
Вайсштейн, Эрик В. «Булева алгебра». Математический мир .