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

редактировать
Алгебраическая структура, моделирующая логические операции

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

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

булевой решеткой подмножеств

Содержание

  • 1 История
  • 2 Определение
  • 3 Примеры
  • 4 Гомоморфизмы и изоморфизмы
  • 5 Булевы кольца
  • 6 Идеалы и фильтры
  • 7 Представления
  • 8 Аксиоматика
  • 9 Обобщения
  • 10 См. Также
  • 11 Примечания
  • 12 Ссылки
  • 13 Внешние ссылки

История

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

Определение

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

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

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

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

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

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

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

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

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

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

Примеры

01
000
101
01
001
111
a01
¬a10
  • Он имеет приложения в логике, интерпретируя 0 как ложь, 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.
  • После двухэлементной булевой алгебры простейшая булева алгебра определяется набором степеней из двух атомов:
0ab1
00000
a0a0a
b00bb
10ab1
0ab1
00ab1
aaa11
bb1b1
11111
x0ab1
¬x1ba0
  • Множество всех подмножеств S, которые либо конечны, либо cofinite, является булевой алгеброй, алгеброй множеств.
  • Начальная с исчислением высказываний с κ-символами предложений, образуют алгебру Линденбаума (то есть набор предложений в исчислении высказываний по модулю логической эквивалентности ). Эта конструкция дает булеву алгебру. Фактически это свободная булева алгебра на образующих κ. Присвоение истинности в исчислении высказываний является гомоморфизмом булевой алгебры из этой алгебры в двухэлементную булеву алгебру.
  • Для любого линейно упорядоченного множества L с наименьшим элементом алгебра интервалов является наименьшая алгебра подмножеств L, содержащая все полуоткрытые интервалы [a, b) такие, что a находится в L, а b либо в L, либо равно ∞. Алгебры интервалов полезны при изучении алгебр Линденбаума – Тарского ; каждая счетная булева алгебра изоморфна интервальной алгебре.
диаграмма Хассе булевой алгебры делителей 30.
  • Для любого натурального числа n множество всех положительных делители числа n, определяющие a≤b, если a делит b, образуют распределительную решетку. Эта решетка является булевой алгеброй тогда и только тогда, когда 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 гомоморфизм между двумя булевыми алгебрами A и B - это функция f: A → B такая, что для всех a, b в A:

f (a ∨ b) = f (a) ∨ f (b),
f (a ∧ b) = f (a) ∧ f (b),
f (0) = 0,
f (1) = 1.

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

Изоморфизм между двумя булевыми алгебрами A и B - это гомоморфизм f: A → B с обратным гомоморфизмом, то есть гомоморфизм g: B → A такой, что композиция g ∘ f: A → A - это тождественная функция на 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 ∧ у: = х · у. Поскольку эти две конструкции являются обратными друг другу, мы можем сказать, что каждое булево кольцо возникает из булевой алгебры, и наоборот. Более того, отображение f: A → B является гомоморфизмом булевых алгебр тогда и только тогда, когда оно является гомоморфизмом булевых колец. Категории логических колец и булевых алгебр эквивалентны.

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

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

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

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

Представления

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

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

Аксиоматика

Проверенные свойства
UId 2[dual] If x ∧ i = x для всех x, тогда i = 1
Idm 2[dual] x ∧ x = x
Bnd 2[двойной] x ∧ 0 = 0
Abs 2[dual] x ∧ (x ∨ y) = x
A2[двойственный] x ∧ (¬x ∧ y) = 0
B2[двойной] (x ∧ y) ∧ (¬x ∨ ¬y) = 0
C2[dual] (x ∧ y) ∨ (¬x ∨ ¬y) = 1
DMg 2[двойное] ¬ (x ∧ y) = ¬x ∨ ¬y
D2[двойной] (x∧ (y∧z)) ∧ ¬x = 0
E2[двойное] y ∨ (x∧ (y∧z)) = y
F2[двойственный] (x∧ (y∧z)) ∧ ¬y = 0
G2[двойной] (x∧ ( y∧z)) ∧ ¬z = 0
H2[dual] ¬ ((x∧y) ∧z) ∨ x = 1
I2[dual ] ¬ ((x∧y) ∧z) ∨ y = 1
J2[двойной] ¬ ((x∧y) ∧z) ∨ z = 1
K2[dual] (x ∧ (y ∧ z)) ∧ ¬ ((x ∧ y) ∧ z) = 0
L2[dual] (x ∧ (y ∧ z)) ∨ ¬ ((x ∧ y) ∧ z) = 1
Ass 2[двойное] x ∧ (y ∧ z) = (x ∧ y) ∧ z
Сокращения
UIdУникальная идентичность
IdmIdempotence
BndГраницы
AbsПоглощение закон
UNgУникальное отрицание
DNgДвойное отрицание
DMgЗакон Де Моргана
AssАссоциативность
Аксиомы булевой алгебры Хантингтона 1904 г.
Idn 1x ∨ 0 = xIdn 2x ∧ 1 = x
Cmm 1x ∨ y = y ∨ xCmm 2x ∧ y = y ∧ x
Dst 1x ∨ (y∧z) = (x∨y) ∧ (x∨z)Dst 2x ∧ (y∨z) = (x∧y) ∨ (x∧z)
Cpl 1x ∨ ¬x = 1Cpl 2x ∧ ¬x = 0
Аббревиатуры
IdnИдентичность
CmmКоммутативность
DstДистрибутивность
CplДополнения

Первая аксиоматизация булевых решеток / алгебр в общее было дано английским философом и математиком Альфредом Норт Уайтхедом в 1898 году. Оно включало вышеуказанные аксиомы и дополнительно x∨1 = 1 и x∧0 = 0. В 1904 году американский математик Эдвард В. Хантингтон (1874–1952) дал, вероятно, самую экономную аксиоматизацию, основанную на, ∨, ¬, даже доказав законы ассоциативности (см. Вставку). Он также доказал, что эти аксиомы независимы друг от друга. В 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 = b. Определяя a ∖ b как единственный x такой, что (a ∧ b) ∨ x = a и (a ∧ b) ∧ x = 0, мы говорим, что структура (B, ∧, ∨, ∖, 0) является обобщенной булевой алгебры, а (B, ∨, 0) - обобщенная булева полурешетка. Обобщенные булевы решетки - это в точности идеалы булевых решеток.

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

См. Также

Примечания

Ссылки

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

Последняя правка сделана 2021-05-13 14:35:34
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте