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

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

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

Булева решетка подмножеств

История [ править ]

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

Определение [ править ]

Булева алгебра является шести- кортеж , состоящий из множества A , оснащен двумя бинарными операциями ∧ ( так называемые «концами» или «и»), ∨ ( так называемый «присоединиться» или «или»), А унарная операция ¬ ( так называемый " дополнять или не дополнять) и два элемента 0 и 1 в A (называемые «нижний» и «верхний» или «наименьший» и «наибольший» элементы, также обозначаемые символами ⊥ и ⊤ соответственно), такие, что для всех элементов a , b и c из A верны следующие аксиомы : ^[2]

a ∨ ( b ∨ c ) = ( a ∨ b ) ∨ c	a ∧ ( b ∧ c ) = ( a ∧ b ) ∧ c	ассоциативность
а ∨ б = б ∨ а	а ∧ б = б ∧ а	коммутативность
а ∨ ( а ∧ б ) = а	а ∧ ( а ∨ б ) = а	поглощение
а ∨ 0 = а	а ∧ 1 = а	личность
a ∨ ( b ∧ c ) = ( a ∨ b ) ∧ ( a ∨ c )	a ∧ ( b ∨ c ) = ( a ∧ b ) ∨ ( a ∧ c )	распределенность
а ∨ ¬ а = 1	а ∧ ¬ а = 0	дополняет

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

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

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

a = b ∧ a     тогда и только тогда, когда     a ∨ b = b .

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

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

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

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

Примеры [ править ]

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

• Он имеет применение в логике , интерпретируя 0 как ложь , 1 как истину , ∧ как и , ∨ как или и ¬ как нет . Выражения, включающие переменные и логические операции, представляют формы операторов, и можно показать, что два таких выражения равны, используя приведенные выше аксиомы, тогда и только тогда, когда соответствующие формы операторов логически эквивалентны .

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

• Двухэлементная булева алгебра также важна в общей теории булевых алгебр, поскольку уравнение, включающее несколько переменных, обычно истинно во всех булевых алгебрах тогда и только тогда, когда оно истинно в двухэлементной булевой алгебре (что можно проверить с помощью тривиальный алгоритм грубой силы для небольшого числа переменных). Это может, например, использоваться, чтобы показать, что следующие законы ( теоремы консенсуса ) в целом справедливы во всех булевых алгебрах:
  • ( a ∨ b ) ∧ (¬ a ∨ c ) ∧ ( b ∨ c ) ≡ ( a ∨ b ) ∧ (¬ a ∨ c )
  • ( a ∧ b ) ∨ (¬ a ∧ c ) ∨ ( b ∧ c ) ≡ ( a ∧ b ) ∨ (¬ a ∧ c )

• Набор мощности (множество всех подмножеств) из любого заданного непустого множества S образует булеву алгебру, в алгебре множеств , причем две операций ∨: = ∪ (союз) и ∧: = ∩ (пересечение). Наименьший элемент 0 является пустое множество , а наибольший элемент 1 является множество S себя.

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

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

• Для любого натурального числа п , множество всех положительных делителей из п , определяющее а ≤ Ь , если а делит Ь , образует распределительную решетку . Эта решетка является булевой алгеброй тогда и только тогда, когда n не содержит квадратов . Нижний и верхний элементы этой булевой алгебры - это натуральные числа 1 и n соответственно. Дополнение к a дается n / a . Встреча и соединение a и b задаются наибольшим общим делителем(gcd) и наименьшее общее кратное (lcm) для a и b соответственно. Сложение кольца a + b дается соотношением lcm ( a , b ) / gcd ( a , b ). На рисунке показан пример для n = 30. В качестве контрпримера, учитывая неквадратное n = 60, наибольший общий делитель 30 и его дополнение 2 будет 2, тогда как он должен быть нижним элементом 1.
• Другие примеры булевых алгебр возникают из топологических пространств : если X - топологическое пространство, то совокупность всех подмножеств X, которые являются как открытыми, так и замкнутыми, образует булеву алгебру с операциями ∨: = ∪ (объединение) и ∧: = ∩ (перекресток).
• Если R - произвольное кольцо и мы определим множество центральных идемпотентов как
  A = { e ∈ R  : e ² = e , ex = xe , ∀ x ∈ R },
  то множество A становится булевой алгеброй с операциями e ∨ f  : = e + f - ef и e ∧ f  : = ef .

Гомоморфизмы и изоморфизмы [ править ]

Гомоморфизм между двумя булевыми алгебрами A и B является функцией F  : → B , что для всех а , б , в A :

f ( a ∨ b ) = f ( a ) ∨ f ( b ),

f ( a ∧ b ) = f ( a ) ∧ f ( b ),

f (0) = 0,

f (1) = 1.

Из этого следует , что п (¬ ) = ¬ е ( ) для всех а в А . Класс всех булевых алгебр, вместе с этим понятием морфизма, образует полную подкатегорию в категории решеток.

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

Логические кольца [ править ]

Каждая булева алгебра ( A , ∧,) порождает кольцо ( A , +, ·), определяя a + b  : = ( a ∧ ¬ b ) ∨ ( b ∧ ¬ a ) = ( a ∨ b ) ∧ ¬ ( a ∧ b ) (эта операция называется симметричной разностью в случае множеств и XOR в случае логики) и a · b  : = a ∧ b. Нулевой элемент этого кольца совпадает с нулем булевой алгебры; мультипликативный единичный элемент кольца - это 1 булевой алгебры. Это кольцо обладает тем свойством, что a · a = a для всех a из A ; кольца с этим свойством называются булевыми кольцами .

Наоборот, если дано булево кольцо A , мы можем превратить его в булеву алгебру, определив x ∨ y  : = x + y + ( x · y ) и x ∧ y  : = x · y . ^{[4] [5]} Поскольку эти две конструкции противоположны друг другу, мы можем сказать, что каждое булево кольцо возникает из булевой алгебры, и наоборот. Более того, отображение f  : A → B является гомоморфизмом булевых алгебр тогда и только тогда, когда оно является гомоморфизмом булевых колец. В категориибулевых колец и булевых алгебр эквивалентны. ^[6]

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

Идеалы и фильтры [ править ]

Идеал булевой алгебры A есть подмножество I , что для всех х , у в I мы имеем х ∨ у в I и для всех а в А мы имеем ∧ х в I . Это понятие идеального совпадает с понятием кольца идеал в булевой кольце A . Идеал I кольца A называется простым, если I ≠ A и если a ∧б в I всегда подразумевает в I или б в I . Кроме того, для любого a ∈ A имеем a ∧ -a = 0 ∈ I и тогда a ∈ I или -a ∈ I для любого a ∈ A , если I простое число. Идеал I кольца A называется максимальным, если I ≠ A и если единственный идеал, должным образом содержащий Iэто сам. Для идеального I , если ∉ я и -a ∉ я , то я ∪ { } или я ∪ { -a } должным образом содержится в другом идеала J . Следовательно, I не является максимальным и, следовательно, понятия простого идеала и максимального идеала эквивалентны в булевых алгебрах. Кроме того, эти понятия совпадают с кольцевыми теоретико - одними из простого идеала и максимального идеала в булево кольцо А .

Двойник идеала - это фильтр . Фильтр булевой алгебры А является подмножеством р такое , что для всех х , у в р мы имеем х ∧ у в р и для всех а в А мы имеем ∨ х в р . Двойственный к максимальному (или простому ) идеалу в булевой алгебре является ультрафильтром . Альтернативно ультрафильтры можно описать как двузначные морфизмыот A к двухэлементной булевой алгебре. Оператор каждый фильтр в булевой алгебре может быть продолжен до ультрафильтра называется Ультрафильтр теорема и не могут быть доказаны в ZF , если ZF является последовательным . В ZF это строго слабее, чем выбранная аксиома . Теорема об ультрафильтре имеет много эквивалентных формулировок: каждая булева алгебра имеет ультрафильтр , каждый идеал в булевой алгебре может быть расширен до простого идеала и т. Д.

Представления [ править ]

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

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

Аксиоматика [ править ]

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

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

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

4. Уравнение Роббинса : 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 ≤ b , существует элемент x такой, что a ∧ x = 0 и a ∨ x = б. Определяя a ∖ b как единственный x такой, что (a ∧ b) ∨ x = a и (a ∧ b) ∧ x = 0, мы говорим, что структура (B, ∧, ∨, ∖, 0) является обобщенной булевой алгебры , а (B, ∨, 0) - обобщенная булева полурешетка. Обобщенные булевы решетки - это в точности идеалы булевых решеток.

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

См. Также [ править ]

Примечания [ править ]

Ссылки [ править ]

Цитированные работы [ править ]

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

Общие ссылки [ править ]

Эта статья включает в себя список общих ссылок , но он остается в основном непроверенным, поскольку в нем отсутствуют соответствующие встроенные ссылки . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Июль 2013 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

• Браун, Стивен; Вранешич, Звонко (2002), Основы цифровой логики с дизайном VHDL (2-е изд.), McGraw – Hill , ISBN 978-0-07-249938-4. См. Раздел 2.5.
• Boudet, A .; Jouannaud, JP; Шмидт-Шаус, М. (1989). «Объединение в булевых кольцах и абелевых группах». Журнал символических вычислений . 8 (5): 449–477. DOI : 10.1016 / s0747-7171 (89) 80054-9 .
• Кори, Рене; Ласкар, Дэниел (2000), Математическая логика: курс с упражнениями , Oxford University Press , ISBN 978-0-19-850048-3. См. Главу 2.
• Dahn, BI (1998), "Robbins Алгебра булевы: A Пересмотр сгенерированного компьютера Решения McCune о Robbins в проблеме", журнал алгебра , 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.
• Хантингтон, Е. В. (1933), "Новые наборы независимых постулатов для алгебры логики" (PDF) , Труды Американского математического общества , Американского математического общества, 35 (1): 274-304, DOI : 10,2307 / 1989325 , JSTOR  1989325.
• Хантингтон, Е. В. (1933), "Булева алгебра: коррекция", Труды Американского математического общества , 35 (2): 557-558, DOI : 10,2307 / 1989783 , JSTOR  1989783
• Сян, Цзе (2007). "Доказательство опровергающей теоремы с помощью систем переписывания терминов" . AI . 25 (3): 255–300. arXiv : cond-mat / 0606434 . DOI : 10.1016 / 0004-3702 (85) 90074-8 .
• Мендельсон, Эллиотт (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 и ихрер Гренцгебиете, Springer Verlag.
• Столл, Р. Р. (1963), Теория множеств и логика , WH Freeman, ISBN 978-0-486-63829-4. Перепечатано Dover Publications , 1979.

Внешние ссылки [ править ]

Использование внешних ссылок в этой статье может не соответствовать политикам или рекомендациям Википедии . Пожалуйста, улучшите эту статью , удалив лишние или неприемлемые внешние ссылки и преобразовав полезные ссылки, где это необходимо, в сноски . ( Ноябрь 2020 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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