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

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

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

История

Термин «Булева алгебра» дан в честь Джорджа Буля (1815–1864), английского математика-самоучки. Он представил алгебраическую систему первоначально в небольшой брошюре «Математический анализ логики» , опубликованной в 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 в) \land (б \lor в) \equiv (а \lor б) \land (\neg а \lor в)$
- $(а \land б) \lor (\neg а \land в) \lor (б \land в) \equiv (а \land б) \lor (\neg а \land в)$

Множество степеней (множество всех подмножеств) любого заданного непустого множества $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$ задаются наибольшим общим делителем ( $НОД$ ) и наименьшим общим кратным ( $НОК$ ) чисел $a$ и $b$ соответственно. Кольцевое сложение $a$ $+$ $b$ задается как $НОД($ $a$ $,$ $b$ $) / НОД($ $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$ :

f (а \lor b) = f (а) \lor f (b)

f (а \land b) = f (а) \land f (b)

ф (0) = 0

ф (1) = 1

Отсюда следует, что f $(\neg a) = \neg f (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 булевой алгебры; мультипликативный единичный элемент кольца является 1 $булевой$ алгебры. Это кольцо обладает тем свойством, что $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] на самом деле категории изоморфны .

Hsiang (1985) дал основанный на правилах алгоритм для проверки того, обозначают ли два произвольных выражения одно и то же значение в каждом булевом кольце. В более общем смысле, Boudet, Jouannaud и Schmidt-Schauss (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$ . Двойственный максимальному (или простому ) идеалу в булевой алгебре — это ультрафильтр . Ультрафильтры можно альтернативно описать как 2-значные морфизмы из $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 = b$ . Определяя $a \ b$ как единственный $x,$ такой что $(a \land b) \lor x = a$ и $(a \land b) \land x = 0$ , мы говорим, что структура $( B , ∧, ∨, \, 0)$ является обобщенной булевой алгеброй , в то время как $(B, \lor, 0)$ является обобщенной булевой полурешеткой . Обобщенные булевы решетки являются в точности идеалами булевых решеток.

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

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

Примечания

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

Ссылки

^ Гивант и Халмос 2009, с. 20.
↑ Дэйви и Пристли 1990, стр. 109, 131, 144.
^ Гудстейн 2012, стр. 21 и далее.
↑ Стоун 1936.
^ Сян 1985, стр. 260.
^ Кон 2003, стр. 81.
^ Падманабхан и Рудеану 2008, с. 73.
↑ Уайтхед 1898, стр. 37.
↑ Хантингтон 1904, стр. 292–293.
↑ Хантингтон 1904, стр. 296.
^ Хантингтон 1933а.

Цитируемые работы

Дэви, BA; Пристли, HA (1990). Введение в решетки и порядок . Cambridge Mathematical Textbooks. Cambridge University Press.
Кон, Пол М. (2003), Основы алгебры: группы, кольца и поля , Springer, стр. 51, 70–81, ISBN 9781852335878
Дживант, Стивен; Халмош, Пол (2009), Введение в булевы алгебры , Бакалаврские тексты по математике , Springer , ISBN 978-0-387-40293-2.
Гудстейн, Р.Л. (2012), «Глава 2: Самодуальная система аксиом», Булева алгебра , Courier Dover Publications, стр. 21 и далее, ISBN 9780486154978
Сян, Цзе (1985). «Доказательство опровержения теорем с использованием систем переписывания терминов». Искусственный интеллект . 25 (3): 255–300. doi :10.1016/0004-3702(85)90074-8.
Хантингтон, Эдвард В. (1904). «Наборы независимых постулатов для алгебры логики». Труды Американского математического общества . 5 (3): 288–309. doi : 10.1090/s0002-9947-1904-1500675-4 . JSTOR 1986459.
Падманабхан, Ранганатан; Рудеану, Серджиу (2008), Аксиомы для решеток и булевых алгебр , World Scientific, ISBN 978-981-283-454-6.
Стоун, Маршалл Х. (1936). «Теория представлений для булевой алгебры». Труды Американского математического общества . 40 : 37–111. doi : 10.1090/s0002-9947-1936-1501865-8 .
Уайтхед, А. Н. (1898). Трактат об универсальной алгебре. Cambridge University Press. ISBN 978-1-4297-0032-0.

Общие ссылки

Браун, Стивен; Вранесич, Звонко (2002), Основы цифровой логики с проектированием VHDL (2-е изд.), McGraw–Hill , ISBN 978-0-07-249938-4, См. раздел 2.5.
Буде, А.; Жуанно, Ж. П.; Шмидт-Шаус, М. (1989). «Унификация в булевых кольцах и абелевых группах». Журнал символических вычислений . 8 (5): 449–477. doi : 10.1016/s0747-7171(89)80054-9 .
Кори, Рене; Ласкар, Дэниел (2000), Математическая логика: курс с упражнениями , Oxford University Press , ISBN 978-0-19-850048-3. См. Главу 2.
Дан, Б.И. (1998), «Алгебры Роббинса являются булевыми: пересмотр компьютерно-генерированного решения МакКьюна проблемы Роббинса», Журнал алгебры , 208 (2): 526–532, doi : 10.1006/jabr.1998.7467.

Халмос, Пол (1963), Лекции по булевой алгебре , Ван Ностранд, ISBN 978-0-387-90094-0.
Халмош, Пол ; Дживант, Стивен (1998), Логика как алгебра , Dolciani Mathematical Expositions, т. 21, Математическая ассоциация Америки , ISBN 978-0-88385-327-6.
Хантингтон, Э.В. (1933a), «Новые наборы независимых постулатов для алгебры логики» (PDF) , Труды Американского математического общества , 35 (1), Американское математическое общество: 274–304, doi :10.2307/1989325, JSTOR 1989325.
Хантингтон, Э.В. (1933б), «Булева алгебра: исправление», Труды Американского математического общества , 35 (2): 557–558, doi :10.2307/1989783, JSTOR 1989783
Мендельсон, Эллиотт (1970), Булева алгебра и коммутационные схемы , серия «Очерк Шаума» по математике, McGraw–Hill , ISBN 978-0-07-041460-0
Монк, Дж. Дональд; Боннет, Р., ред. (1989), Справочник по булевой алгебре , Северная Голландия , ISBN 978-0-444-87291-3. В 3-х томах. (Том 1: ISBN 978-0-444-70261-6 , Том 2: ISBN 978-0-444-87152-7 , Том 3: ISBN 978-0-444-87153-4 )
Сикорский, Роман (1966), Булевы алгебры , Ergebnisse der Mathematik und ihrer Grenzgebiete, Springer Verlag.
Столл, Р. Р. (1963), Теория множеств и логика , WH Freeman, ISBN 978-0-486-63829-4. Перепечатано Dover Publications , 1979.

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

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