Введение

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

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

История

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

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

Каждая булева алгебра 1=(A, ∧, ∨) порождает кольцо (A, +, ·) путем определения 1=a + b := (a ∧ ¬b) ∨ (b ∧ ¬a) = (a ∨ b) ∧ ¬(a ∧ b) (эта операция называется симметрической разностью в случае множеств и XOR в случае логики) и 1=a · b := a ∧ b. Нулевой элемент этого кольца совпадает с 0 булевой алгебры; единичный элемент кольца – 1 булевой алгебры. Это кольцо обладает свойством, что 1=a · a = a для всех a из A; кольца с этим свойством называются булевыми кольцами. Обратно, если задано булево кольцо A, мы можем преобразовать его в булеву алгебру, определив 1=x ∨ y := x + y + (x · y) и 1=x ∧ y := x · y. Поскольку эти две конструкции являются обратными друг другу, мы можем утверждать, что каждое булево кольцо происходит из булевой алгебры, и наоборот. Более того, отображение f : A → B является гомоморфизмом булевых алгебр тогда и только тогда, когда оно является гомоморфизмом булевых колец. Категории булевых колец и булевых алгебр эквивалентны; фактически, эти категории изоморфны. Хсианг (1985) предложил алгоритм, основанный на правилах, для проверки того, обозначают ли два произвольных выражения одно и то же значение в каждом булевом кольце. В более общем случае, Буде, Жуанно и Шмидт-Шаусс (1989) предложили алгоритм для решения уравнений между произвольными выражениями булевых колец. Используя сходство булевых колец и булевых алгебр, оба алгоритма находят применение в автоматическом доказательстве теорем.

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

Идеал булевой алгебры A – это непустое подмножество I, такое, что для всех x, y из I выполняется x ∧ y ∈ I и для всех a из A выполняется a ∧ I ∈ I. Это понятие идеала совпадает с понятием кольцевого идеала в булевом кольце A. Идеал I алгебры A называется простым, если x ∧ y ∈ I влечет за собой x ∈ I или y ∈ I. Кроме того, для каждого a ∈ A выполняется a ∨ I = 1, и если I является простым, то для каждого a ∈ A выполняется a ∈ I или ¬a ∈ I. Идеал I алгебры A называется максимальным, если I ≠ A и единственный идеал, строго содержащий I, – это само A. Для идеала I, если x ∈ I и y ∈ I, то либо x ∨ y содержится в другом собственном идеале J. Следовательно, такой I не является максимальным, и поэтому понятия простого идеала и максимального идеала эквивалентны в булевой алгебре. Более того, эти понятия совпадают с кольцево-теоретическими понятиями простого и максимального идеалов в булевом кольце A. Дуалом идеала является фильтр. Фильтр булевой алгебры A – это непустое подмножество p, такое, что для всех x, y из p выполняется x ∨ y ∈ p и для всех a из A выполняется a ∨ p = 1. Дуалом максимального (или простого) идеала в булевой алгебре является ультрафильтр. Ультрафильтры можно описать как 2-значные морфизмы из A в двухэлементную булеву алгебру. Утверждение о том, что каждый фильтр в булевой алгебре может быть расширен до ультрафильтра, называется леммой ультрафильтра и не может быть доказано в теории множеств Цермело — Френкеля (ZF), если ZF непротиворечива. В рамках ZF лемма ультрафильтра строго слабее аксиомы выбора. Лемма ультрафильтра имеет множество эквивалентных формулировок: каждая булева алгебра имеет ультрафильтр, каждый идеал в булевой алгебре может быть расширен до простого идеала и т.д.

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

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

Обобщения

Удаление требования о существовании единицы из аксиом булевой алгебры приводит к "обобщённым булевым алгебрам". Формально, распределительная решётка 1=B является обобщённой булевой решёткой, если она имеет наименьший элемент 1=0 и для любых элементов 1=a и 1=b в 1=B, таких что 1=a ≤ b, существует элемент 1=x, такой что 1=a ∧ x = 0 и 1=a ∨ x = b. Определяя 1=a \ b как единственный 1=x, удовлетворяющий условиям 1=(a ∧ b) ∨ x = a и 1=(a ∧ b) ∧ x = 0, мы говорим, что структура (B, ∧, ∨, \, 0) является обобщённой булевой алгеброй, а (B, ∨, 0) – обобщённой булевой полурешёткой. Обобщённые булевы решётки являются идеалами булевых решёток. Структура, удовлетворяющая всем аксиомам булевой алгебры, за исключением двух аксиом дистрибутивности, называется ортокомплементированной решёткой. Ортокомплементированные решётки возникают естественным образом в квантовой логике как решётки замкнутых линейных подпространств для сепарабельных пространств Гильберта.

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

Да. Да. Да. Да.

Общие ссылки

Да. Да. См. раздел 2.5. См. главу 2. В 3 томах (Т. 1, Т. 2, Т. 3). Переиздано Dover Publications, 1979.