Булевы алгебры канонически определены

Булевы алгебры являются моделями эквациональной теории двух значений; это определение эквивалентно определениям решетки и кольца.

Булева алгебра — математически богатая ветвь абстрактной алгебры . Стэнфордская энциклопедия философии определяет булеву алгебру как «алгебру двузначной логики только с сентенциальными связками или, что то же самое, как алгебры множеств при объединении и дополнении». Точно так же, как теория групп имеет дело с группами , а линейная алгебра — с векторными пространствами , булевы алгебры являются моделями эквациональной теории двух значений 0 и 1 (чья интерпретация не обязательно должна быть числовой). Общим для булевых алгебр, групп и векторных пространств является понятие алгебраической структуры , — множества замкнутого относительно некоторых операций , удовлетворяющих определенным уравнениям.

Точно так же, как существуют основные примеры групп, такие как группа $\mathbb {Z}$ целых чисел и симметрической группы Sn _{основные примеры булевых алгебр ,} перестановок , существуют также n объектов такие как следующие.

• Алгебра двоичных цифр или битов 0 и 1 при выполнении логических операций, включая дизъюнкцию, конъюнкцию и отрицание. Приложения включают исчисление высказываний и теорию цифровых схем.
• Алгебра множеств при выполнении операций над множествами, включая объединение , пересечение и дополнение . Приложения имеют далеко идущие последствия, поскольку теория множеств является стандартной основой математики .

Таким образом, булева алгебра позволяет применять методы абстрактной алгебры к математической логике и цифровой логике .

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

Определение

Булева алгебра рассматривает эквациональную теорию максимальной двухэлементной финитной алгебры, называемую булевым прототипом , и модели этой теории, называемые булевыми алгебрами . Эти термины определяются следующим образом.

Алгебра — это семейство операций над множеством, называемым основным множеством алгебры. Мы принимаем базовый набор логического прототипа равным {0,1}.

Алгебра является финитарной, если каждая ее операция принимает лишь конечное число аргументов. В прототипе каждый аргумент операции имеет значение 0 или 1 в зависимости от результата операции. Максимальная такая алгебра состоит из всех финитарных операций над {0,1}.

Количество аргументов, принимаемых каждой операцией, называется арностью операции. Операция над {0,1} арности n или n -арная операция может быть применена к любому из 2 ^н возможные значения для его n аргументов. Для каждого выбора аргументов операция может возвращать 0 или 1 , откуда их 2. ^{2 н} n -арные операции.

Таким образом, прототип имеет две операции без аргументов, называемые нулевыми или нулевыми операциями, а именно ноль и единицу. Он имеет четыре унарные операции , две из которых — операции с константами, другая — с идентичностью, а наиболее часто используемая, называемая отрицанием , возвращает противоположность своего аргумента: 1 , если 0 , 0 , если 1 . Он имеет шестнадцать двоичных операций ; снова два из них являются константами, другой возвращает свой первый аргумент, еще один возвращает второй, один называется конъюнкцией и возвращает 1, если оба аргумента равны 1, а в противном случае 0, другой называется дизъюнкцией и возвращает 0, если оба аргумента равны 0, и в противном случае 1 , и так далее. Количество ( n +1) -арных операций в прототипе равно квадрату количества n -арных операций, поэтому их 16. ² = 256 троичных операций, 256 ² = 65 536 четверичных операций и так далее.

Семейство . индексируется индексов набором В случае семейства операций, образующих алгебру, индексы называются символами операций и составляют язык этой алгебры. Операция, индексируемая каждым символом, называется обозначением или интерпретацией этого символа. Каждый символ операции определяет арность своей интерпретации, поэтому все возможные интерпретации символа имеют одинаковую арность. В общем, алгебра может интерпретировать разные символы с помощью одной и той же операции, но это не относится к прототипу, символы которого находятся во взаимном соответствии с ее операциями. Таким образом, прототип имеет 2 ^{2 н} n -арные символы операций, называемые символами булевых операций и образующие язык булевой алгебры. Лишь немногие операции имеют общепринятые символы, такие как ¬ для отрицания, ∧ для соединения и ∨ для дизъюнкции. Удобно считать i -й n -арный символ ^н f _{, как это} сделано ниже в разделе, посвященном таблицам истинности .

Эквациональная теория на данном языке состоит из уравнений между терминами, составленными из переменных с использованием символов этого языка. Типичными уравнениями языка булевой алгебры являются x ∧ y = y ∧ x , x ∧ x = x , x ∧¬ x = y ∧¬ y и x ∧ y = x .

Алгебра удовлетворяет уравнению, когда уравнение выполняется для всех возможных значений ее переменных в этой алгебре, когда символы операций интерпретируются так, как указано в этой алгебре. Законы булевой алгебры — это уравнения языка булевой алгебры, которым удовлетворяет прототип. Первые три из приведенных выше примеров являются булевыми законами, но не четвёртым, поскольку 1∧0 ≠ 1 .

Эквациональная теория алгебры — это совокупность всех уравнений, которым удовлетворяет алгебра. Таким образом, законы булевой алгебры составляют эквациональную теорию булевого прототипа.

Модель теории — это алгебра, интерпретирующая символы операций на языке теории и удовлетворяющая уравнениям теории.

Булева алгебра — это любая модель законов булевой алгебры.

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

Если мы определим гомолог алгебры как модель эквациональной теории этой алгебры, то булева алгебра может быть определена как любой гомолог прототипа.

Пример 1 . Булев прототип — это булева алгебра, поскольку она тривиально удовлетворяет своим собственным законам. Таким образом, это прототип булевой алгебры. Первоначально мы не называли его так, чтобы избежать появления зацикленности в определении.

Основа

Не обязательно все операции указывать явно. Базисом является любое множество , из которого можно получить остальные операции композицией. «Булева алгебра» может быть определена на основе любого из нескольких различных оснований. Обычно используются три основы булевой алгебры: базис решетки, базис колец и штрих Шеффера или базис NAND. Эти основы придают предмету соответственно логический, арифметический и экономный характер.

• Базис решетки возник в 19 веке благодаря работам Буля , Пирса и других, стремившихся к алгебраической формализации процессов логического мышления.
• Кольцевой абстрактной базис появился в 20 веке благодаря работам Жегалкина и Стоуна и стал основой выбора для алгебраистов, пришедших к этому предмету с опытом работы в алгебре . Большинство трактовок булевой алгебры предполагают решеточный базис, заметным исключением является Халмош [1963], чей опыт линейной алгебры, очевидно, привлек к нему внимание к кольцевому базису.
• Поскольку все финитные операции над {0,1} могут быть определены в терминах штриха Шеффера И-НЕ (или его двойного ИЛИ-НЕ), полученная экономическая основа стала основой выбора для анализа цифровых схем , в частности вентильных матриц в цифровой электронике .

Общими элементами решетчатых и кольцевых базисов являются константы 0 и 1, а также ассоциативная коммутативная бинарная операция , называемая встреча x ∧ y в решеточном базисе, и умножение xy в кольцевом базисе. Различие носит лишь терминологический характер. дополнительные соединения x . ∨ y и дополнения ¬ x Базис решетки имеет операции Вместо этого в кольцевом базисе используется арифметическая операция x ⊕ y сложения поскольку (символ ⊕ используется вместо +, последнему иногда присваивается логическое прочтение соединения).

Быть базисом — значит производить все остальные операции по композиции, поэтому любые два базиса должны быть взаимопереводимы. Базис решетки переводит x ∨ y в базис кольца как x ⊕ y ⊕ xy , и ¬ x как x ⊕1 . И наоборот, кольцевой базис переводит x ⊕ y в решеточный базис как ( x ∨ y )∧¬( x ∧ y ) .

Обе эти основы позволяют определять булевы алгебры через подмножество эквациональных свойств булевых операций. Для базиса решетки достаточно определить булеву алгебру как дистрибутивную решетку, удовлетворяющую условиям x ∧¬ x = 0 и x ∨¬ x = 1 , называемую дополняемой дистрибутивной решеткой. Кольцевой базис превращает булеву алгебру в булево кольцо , а именно в кольцо, удовлетворяющее x ² = х .

Эмиль Пост дал необходимое и достаточное условие для того, чтобы набор операций стал основой для ненулевых булевых операций. Нетривиальное свойство — это свойство , которое разделяется некоторыми, но не всеми операциями, составляющими базис. Пост перечислил пять нетривиальных свойств операций, отождествляемых с пятью классами Поста , каждый из которых сохраняется посредством композиции, и показал, что набор операций образует основу, если для каждого свойства набор содержит операцию, лишенную этого свойства. (Обратной теоремой Поста, расширяющей «если» до «тогда и только тогда », является легкое наблюдение, заключающееся в том, что свойство из этих пяти, содержащее каждую операцию в базисе-кандидате, будет также сохраняться для каждой операции, образованной композицией из этого кандидата. , откуда из-за нетривиальности этого свойства кандидат не может быть базисом.) Пять свойств Поста таковы:

• монотонный , никакой входной переход 0-1 не может вызвать выходной переход 1-0;
• affine , представимый полиномами Жегалкина , в которых отсутствуют билинейные или более высокие члены, например x ⊕ y ⊕1 , но не xy ;
• самодвойственный , так что дополнение всех входных данных дополняет выходной, как в случае с x или медианным оператором xy ⊕ yz ⊕ zx или их отрицаниями;
• строгий (отображение всех нулей на входе в ноль);
• costrict (отображение всех единиц в одну).

Операция NAND (двойное NOR) лишена всего этого, поэтому сама по себе образует основу.

Таблицы истинности

Финитарные операции над {0,1} могут быть представлены в виде таблиц истинности , считая 0 и 1 значениями истинности false и true . Их можно расположить единообразно и независимо от приложения, что позволяет нам называть их или, по крайней мере, нумеровать их индивидуально. Эти имена представляют собой удобное сокращение для логических операций. Имена n -арных операций представляют собой двоичные числа 2. ^н биты. Там есть 2 ^{2 н} таких операций, нельзя требовать более краткой номенклатуры. Обратите внимание, что каждую финитную операцию можно назвать функцией переключения .

Эта схема и связанные с ней наименования операций полностью проиллюстрированы здесь для значений от 0 до 2.

Таблицы истинности для логических операций арности до 2

Константы ${}^{0}\!f_{0}$ ${}^{0}\!f_{1}$ 0 1

Унарные операции $x_{0}$ ${}^{1}\!f_{0}$ ${}^{1}\!f_{1}$ ${}^{1}\!f_{2}$ ${}^{1}\!f_{3}$ 0 0 1 0 1 1 0 0 1 1

Бинарные операции $x_{0}$ $x_{1}$ ${}^{2}\!f_{0}$ ${}^{2}\!f_{1}$ ${}^{2}\!f_{2}$ ${}^{2}\!f_{3}$ ${}^{2}\!f_{4}$ ${}^{2}\!f_{5}$ ${}^{2}\!f_{6}$ ${}^{2}\!f_{7}$ ${}^{2}\!f_{8}$ ${}^{2}\!f_{9}$ ${}^{2}\!f_{10}$ ${}^{2}\!f_{11}$ ${}^{2}\!f_{12}$ ${}^{2}\!f_{13}$ ${}^{2}\!f_{14}$ ${}^{2}\!f_{15}$ 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

Эти таблицы продолжаются с более высокой арностью, с 2 ^н строки с арностью n , каждая строка дает оценку или привязку n переменных x ₀ ,... x _{n −1} , а заголовок каждого столбца ^н если _я даю значение ^н f _i ( x ₀ ,..., x _{n −1} ) i -й -арной n операции при этом значении. Операции включают переменные, например ¹ f ₂ равно x ₀ , а ² f ₁₀ — это x ₀ (как две копии своего унарного аналога) и ² f ₁₂ равно x ₁ (без унарного аналога). Отрицание или дополнение ¬ x ₀ выглядит как ¹ f ₁ и снова как ² f ₅ вместе с ² f ₃ ( ¬ x ₁ , которого не было в арности 1), дизъюнкция или объединение x ₀ ∨ x ₁ как ² f ₁₄ , соединение или пересечение x ₀ ∧ x ₁ как ² f ₈ , импликация x ₀ → x ₁ как ² f ₁₃ , исключительная или симметричная разность x ₀ ⊕ x ₁ как ² f ₆ , установите разность x ₀ − x ₁ как ² f2 _. и так далее

В качестве незначительной детали, важной больше по форме, чем по содержанию, операции алгебры традиционно организуются в виде списка. Хотя здесь мы индексируем операции булевой алгебры с помощью финитарных операций над {0,1}, представленная выше таблица истинности по счастливой случайности упорядочивает операции сначала по арности, а затем по расположению таблиц для каждой арности. Это позволяет организовать набор всех логических операций в традиционном формате списка. Порядок списка операций заданной арности определяется следующими двумя правилами.

(i) i -я строка в левой половине таблицы представляет собой двоичное представление i с младшим значащим или 0 -м битом слева (порядок с прямым порядком байтов, первоначально предложенный Аланом Тьюрингом , поэтому он будет не было бы неразумно называть это порядком Тьюринга).

(ii) j -й столбец в правой половине таблицы представляет собой двоичное представление j , опять же в прямом порядке. По сути, индекс операции является таблицей истинности этой операции. По аналогии с гёделевой нумерацией вычислимых функций такую ​​нумерацию булевых операций можно было бы назвать булевой нумерацией.

При программировании на C или Java побитовая дизъюнкция обозначается х | и , соединение х и у и отрицание ~ х . Таким образом, программа может представлять, например, операцию x ∧( y ∨ z ) на этих языках как х &( у | z ) , предварительно установив х = 0хаа , у = 0xcc , и г = 0xf0 (" 0x " указывает, что следующая константа должна считываться в шестнадцатеричном формате или в системе счисления 16), либо путем присвоения переменным, либо путем определения в виде макроса. Эти однобайтовые (восьмибитные) константы соответствуют столбцам для входных переменных в расширении Приведенные выше таблицы к трем переменным. Этот метод почти повсеместно используется в аппаратном обеспечении растровой графики для обеспечения гибкого разнообразия способов объединения и маскировки изображений, при этом типичные операции являются троичными и действуют одновременно с битами источника, назначения и маски.

Примеры

Битовые векторы

Пример 2 . Все битовые векторы заданной длины образуют булеву алгебру «поточечно», что означает, что любая n -арная булева операция может быть применена к n ​​битовым векторам по одной битовой позиции за раз. Например, троичное ИЛИ трех битовых векторов, каждый из которых имеет длину 4, представляет собой битовый вектор длиной 4, сформированный путем комбинирования трех битов в каждой из четырех битовых позиций, таким образом, 0100∨1000∨1001 = 1101 . Другим примером являются приведенные выше таблицы истинности для n -арных операций, столбцы которых представляют собой битовые векторы длины 2. ^н и которые, следовательно, могут быть объединены поточечно, поэтому n -арные операции образуют булеву алгебру. Это работает одинаково хорошо для битовых векторов конечной и бесконечной длины, единственное правило состоит в том, что все позиции битов должны быть проиндексированы одним и тем же набором, чтобы «соответствующая позиция» была четко определена.

Атомы такой алгебры — это битовые векторы, содержащие ровно одну единицу. В общем, атомы булевой алгебры — это те элементы x , что x ∧ y имеет только два возможных значения: x или 0 .

Алгебра степенных наборов

Пример 3 . Алгебра степенного множества , множество 2 ^В всех подмножеств данного множества W . Это всего лишь замаскированный пример 2, где W служит для индексации битовых позиций. Любое подмножество X из W можно рассматривать как битовый вектор, имеющий 1 только в тех битовых позициях, которые индексируются X. элементами Таким образом, вектор, состоящий из всех нулей, представляет собой пустое подмножество W, тогда как вектор, состоящий из всех единиц, представляет собой сам W , причем это константы 0 и 1 соответственно алгебры степенного множества. Аналогом дизъюнкции x ∨ y является объединение X ∪ Y , а конъюнкции x ∧ y является пересечение X ∩ Y . Отрицание ¬x становится ~ X , относительно W. дополнением Существует также разность множеств X \ Y = X ∩~ Y , симметричная разность ( X \ Y ) ∪ ( Y \ X ) , тройное объединение X ∪ Y ∪ Z и так далее. Атомы здесь — это одиночки, подмножества, состоящие ровно из одного элемента.

Примеры 2 и 3 представляют собой частные случаи общей конструкции алгебры, называемой прямым произведением , применимой не только к булевым алгебрам, но и ко всем видам алгебр, включая группы, кольца и т. д. Прямое произведение любого семейства B _i булевых алгебр, где i пробегает некоторое множество индексов I (не обязательно конечное или даже счетное) представляет собой булеву алгебру, состоящую из всех I -кортежей (... x _i ,...) -й элемент которых , i взят из B _i . Операции прямого произведения — это соответствующие операции составляющих алгебр, действующие в пределах их соответствующих координат; в частности операция ^н f _j произведения оперирует n I -кортежами, применяя операцию ^н f _j of B _i к n элементам в i -й координате n кортежей для всех i в I .

Когда все алгебры, перемноженные таким образом, представляют собой одну и ту же алгебру A, называем прямое произведение прямой степенью A. мы Булева алгебра всех 32-битных битовых векторов представляет собой двухэлементную булеву алгебру, возведенную в 32-ю степень, или степенную алгебру набора из 32 элементов, обозначаемую 2. ³² . Булева алгебра всех наборов целых чисел равна 2. ^С . Все булевы алгебры, которые мы продемонстрировали до сих пор, были прямыми степенями двухэлементной булевой алгебры, что оправдывает название «алгебра степенного множества».

Теоремы

Можно показать, что каждая конечная булева алгебра изоморфна некоторой степенной алгебре множеств. Следовательно, мощность (число элементов) конечной булевой алгебры является степенью 2 , а именно одной из 1,2,4,8,...,2. ^н ,... Это называется теоремой о представлении , поскольку она дает представление о природе конечных булевых алгебр, давая представление их как алгебры степенных множеств.

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

Чтобы выйти за рамки алгебры степенных множеств, нам нужна другая конструкция. Подалгеброй , алгебры A подмножество A замкнутое относительно операций A. называется любое Каждая подалгебра булевой алгебры A по-прежнему должна удовлетворять уравнениям, содержащимся в A , поскольку любое нарушение будет представлять собой нарушение A. самой Следовательно, каждая подалгебра булевой алгебры является булевой алгеброй.

Подалгебра степенной алгебры множеств называется полем множеств ; эквивалентно, поле множеств — это множество подмножеств некоторого множества W, включая пустое множество и W и замкнутое относительно конечного объединения и дополнения относительно W (и, следовательно, также относительно конечного пересечения). Теорема Биркгофа [1935] о представлении булевых алгебр утверждает, что каждая булева алгебра изоморфна полю множеств. Теперь теорему Биркгофа о HSP для многообразий можно сформулировать следующим образом: каждый класс моделей эквациональной теории класса C алгебр является гомоморфным образом подалгебры произведения прямого алгебр C . Обычно необходимы все три из H, S и P; Первая из этих двух теорем Биркгофа показывает, что в частном случае многообразия булевых алгебр гомоморфизм можно заменить изоморфизмом . Таким образом, теорема Биркгофа HSP для многообразий вообще становится теоремой Биркгофа ISP для многообразия булевых алгебр.

Другие примеры

, удобно Когда речь идет о множестве натуральных чисел X рассматривать его как последовательность x ₀ , x ₁ , x ₂ ,... битов с x _i = 1 тогда и только тогда, когда i ∈ X . Эта точка зрения облегчит разговор о подалгебрах степенной алгебры 2. ^Н , которую с этой точки зрения делает булевой алгеброй всех последовательностей битов. Он также хорошо сочетается со столбцами таблицы истинности: когда столбец читается сверху вниз, он представляет собой последовательность битов, но в то же время его можно рассматривать как набор этих оценок (присвоений переменным в левой части таблицы). половина таблицы), при которой функция, представленная этим столбцом, принимает значение 1.

Пример 4 . В конечном итоге постоянные последовательности . Любая булева комбинация в конечном итоге константных последовательностей в конечном итоге является константой; следовательно, они образуют булеву алгебру. Мы можем идентифицировать их с целыми числами, рассматривая последовательности с нулевым значением как неотрицательные двоичные числа (бит 0 последовательности является младшим битом), а последовательности с нулевым значением как отрицательные двоичные числа (представьте себе арифметику с дополнением до двух со всеми числами) . последовательность единиц равна −1 ). Это делает целые числа булевой алгеброй, где объединение представляет собой побитовое ИЛИ, а дополнение равно −x−1 . Целых чисел только счетное количество, поэтому эта бесконечная булева алгебра счетна. Атомы представляют собой степени двойки, а именно 1,2,4,.... Другой способ описания этой алгебры - это набор всех конечных и коконечных наборов натуральных чисел, с последовательностями, состоящими из всех единиц, соответствующими коконечным числам. множества, причем эти множества пропускают только конечное число натуральных чисел.

Пример 5 . Периодическая последовательность . Последовательность называется периодической, если существует некоторое число n > 0 , называемое свидетелем периодичности, такое, что x _i = x _{i + n} для всех i ≥ 0 . Период периодической последовательности является ее наименьшим свидетелем. Отрицание оставляет период неизменным, в то время как дизъюнкция двух периодических последовательностей является периодической, причем период не превышает наименьшее общее кратное периодов двух аргументов (период может быть всего лишь 1 , как это происходит при объединении любой последовательности и ее дополнение). Следовательно, периодические последовательности образуют булевую алгебру.

Пример 5 похож на пример 4 тем, что он счетен, но отличается тем, что он безатомен. Последнее связано с тем, что соединение любой ненулевой периодической последовательности x с последовательностью взаимно простого периода (больше 1) не равно ни 0 , ни x . Можно показать, что все счетные безатомные булевы алгебры изоморфны, т. е. с точностью до изоморфизма существует только одна такая алгебра.

Пример 6 . Периодическая последовательность с периодом, равным степени двойки . Это собственная подалгебра из примера 5 (собственная подалгебра равна пересечению самой себя со своей алгеброй). Их можно понимать как финитные операции, причем первый период такой последовательности дает таблицу истинности операции, которую она представляет. Например, таблица истинности x ₀ в таблице бинарных операций, а именно ² f ₁₀ имеет период 2 (и поэтому может быть распознан как использующий только первую переменную), хотя 12 бинарных операций имеют период 4 . Когда период равен 2 ^н операция зависит только от первых n переменных, в том смысле, что операция является финитной. Этот пример также представляет собой счетную бесконечную безатомную булеву алгебру. Следовательно, пример 5 изоморфен собственной подалгебре самой себе! Пример 6 и, следовательно, пример 5 представляют собой свободную булеву алгебру со счетным числом образующих, то есть булеву алгебру всех финитарных операций над счетным бесконечным набором образующих или переменных.

Пример 7 . В конечном счете, периодические последовательности , последовательности, которые становятся периодическими после первоначального конечного приступа беззакония. Они представляют собой собственное расширение примера 5 (это означает, что пример 5 является собственной подалгеброй примера 7), а также примера 4, поскольку постоянные последовательности периодические с периодом один. Последовательности могут различаться в зависимости от того, когда они стабилизируются, но любой конечный набор последовательностей в конечном итоге стабилизируется не позднее, чем их член, который медленнее всего стабилизируется, поэтому в конечном итоге периодические последовательности замыкаются при выполнении всех булевых операций и, таким образом, образуют булеву алгебру. Этот пример имеет те же атомы и коатомы, что и пример 4, следовательно, он не является безатомным и, следовательно, не изоморфен примеру 5/6. Однако она содержит бесконечную безатомную подалгебру , а именно пример 5, и поэтому не изоморфна примеру 4, каждая подалгебра которого должна быть булевой алгеброй конечных множеств и их дополнений и, следовательно, атомарной. Этот пример изоморфен прямому произведению примеров 4 и 5, что дает ему другое описание.

Пример 8 . Прямое произведение периодической последовательности (пример 5) с любой конечной, но нетривиальной булевой алгеброй. (Тривиальная одноэлементная булева алгебра — это уникальная конечная безатомная булева алгебра.) Это напоминает пример 7 тем, что содержит как атомы, так и безатомную подалгебру , но отличается наличием лишь конечного числа атомов. Пример 8 на самом деле представляет собой бесконечное семейство примеров, по одному на каждое возможное конечное число атомов.

Этими примерами ни в коем случае не исчерпываются возможные булевы алгебры, даже счетные. Действительно, существует несчетное множество неизоморфных счетных булевых алгебр, которые Юсси Кетонен [1978] полностью классифицировал в терминах инвариантов, представимых некоторыми наследственно счетными множествами.

Булевы алгебры булевых операций

Сами n -арные логические операции составляют степенную алгебру 2 ^В , а именно, когда W принимается за множество из 2 ^н оценки n входов. С точки зрения системы наименования операций ^н Если _i таблице . в двоичном формате — это столбец таблицы истинности, столбцы можно комбинировать с логическими операциями любой арности для создания других столбцов, присутствующих в То есть мы можем применить любую булеву операцию арности m к m логическим операциям арности n, чтобы получить булеву операцию арности n для любых m и n .

Практическое значение этого соглашения как для программного, так и для аппаратного обеспечения состоит в том, что n -арные логические операции могут быть представлены как слова соответствующей длины. Например, каждая из 256 троичных логических операций может быть представлена ​​как беззнаковый байт. Доступные логические операции, такие как И и ИЛИ, затем можно использовать для формирования новых операций. Если мы возьмем x , y и z (на данный момент без индексных переменных) равными 10101010 , 11001100 и 11110000 соответственно (170, 204 и 240 в десятичном формате, 0xaa , 0xcc и 0xf0 в шестнадцатеричном формате), их парные соединения будут x ∧ y = 10001000 , y ∧ z = 11000000 и z ∧ x = 10100000 , в то время как их парные дизъюнкции - x ∨ y = 11101110 , y ∨ z = 11111100 и z ∨ x = 1111101010 . Дизъюнкция трёх дизъюнкций равна 11101000 , что также является конъюнкцией трёх дизъюнкций. Таким образом, с помощью примерно дюжины логических операций над байтами мы подсчитали, что две троичные операции

$(x\land y)\lor (y\land z)\lor (z\land x)$

и

$(x\lor y)\land (y\lor z)\land (z\lor x)$

на самом деле это одна и та же операция. То есть мы доказали эквациональное тождество

$(x\land y)\lor (y\land z)\lor (z\land x)=(x\lor y)\land (y\lor z)\land (z\lor x)$,

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

Эта тернарная операция случайно легла в основу троичных булевых алгебр Грау [1947], которые он аксиоматизировал в терминах этой операции и отрицания. Операция симметрична, что означает, что ее значение не зависит ни от одного из 3! = 6 перестановок его аргументов. Две половины его таблицы истинности 11101000 являются таблицами истинности для ∨ , 1110 и ∧ , 1000 , поэтому операцию можно сформулировать так, как если бы z then x ∨ y else x ∧ y . Поскольку он симметричен, его с равным успехом можно сформулировать следующим образом: если x , то y ∨ z else y ∧ z , или если y то z ∨ x else z ∧ x . Если рассматривать это как маркировку 3-куба с 8 вершинами, верхняя половина помечается 1, а нижняя половина 0; по этой причине его назвали медианным оператором с очевидным обобщением на любое нечетное число переменных (нечетное, чтобы избежать связи, когда ровно половина переменных равна 0).

Аксиоматизация булевых алгебр

Технику, которую мы только что использовали для доказательства тождества булевой алгебры, можно обобщить на все тождества систематическим образом, что можно рассматривать как здравую и полную аксиоматизацию или аксиоматическую систему для эквациональных законов булевой логики . Обычная формулировка системы аксиом состоит из набора аксиом, которые «заполняют насос» некоторыми исходными тождествами, а также набора правил вывода для вывода остальных тождеств из аксиом и ранее доказанных тождеств. В принципе желательно иметь конечное число аксиом; однако с практической точки зрения в этом нет необходимости, поскольку столь же эффективно иметь конечную схему аксиом , имеющую бесконечное количество экземпляров, каждый из которых при использовании в доказательстве может быть легко проверен как законный экземпляр - подход, которому мы следуем здесь.

Булевы тождества — это утверждения вида s = t, где s и t — n -арные термины, под которыми мы будем понимать здесь термины, переменные которых ограничены значениями от до _x0 xn - ₁ . N -арный терм — это либо атом, либо приложение. Приложение ^м f _i ( t ₀ ,..., t _{m ​​-1} ) — пара, состоящая из m -арной операции ^м f _i и список или m -кортеж ( t ₀ ,..., t _{m -1} ) из m n -арных терминов, называемых операндами .

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

Что же такое атом? Обычно атом — это либо константа (0 или 1), либо переменная x _i , где 0 ≤ i < n . Для техники доказательства здесь удобно определить атомы как n -арные операции. ^н f _i , которые, хотя и рассматриваются здесь как атомы, тем не менее означают то же самое, что и обычные термины точной формы ^н f _i ( x ₀ ,..., x _{n -1} ) (точно, переменные должны быть перечислены в указанном порядке без повторений и пропусков). Это не является ограничением, поскольку атомы такого вида включают в себя все обычные атомы, а именно константы 0 и 1, которые возникают здесь как n -арные операции ^н f ₀ и ^н f ₋₁ для каждого n (сокращенно 2 ^{2 н} от −1 до −1 ), а также переменные x ₀ ,..., x _{n -1} , как видно из таблиц истинности, где x ₀ появляется как унарная операция ¹ f ₂ и бинарная операция ² f _10, а x ₁ отображается как ² ж ₁₂ .

Следующая схема аксиом и три правила вывода аксиоматизируют булеву алгебру n -арных термов.

А1 . ^м ж _я ( ^н ж _{0 ,} ..., ^н ж _{м м -1} ) = ^н f _{i o ĵ} где ( i o ĵ ) _v = i _{ĵ v} , где ĵ означает j транспонирование, определяемое формулой ( ĵ _v ) _u = ( j _u ) _v .

Р1 . Без каких-либо предпосылок сделайте вывод t = t .

Р2 . Из s = u и t = u выведите s = t , где s , t и u — n -арные члены.

Р3 . Из s ₀ = t ₀ , ... , s _{m -1} = t _{m -1} сделайте вывод ^м ж _я ( s ₀ ,..., s _{м -1} ) = ^м f _i ( t ₀ ,..., t _{m ​​-1} ) , где все члены s _i , t _i n -арные .

Смысл дополнительного условия на A1 состоит в том, что i o ĵ заключается в том, что 2 ^н -битное число, v -й бит которого является ĵ _v -м битом i , где диапазоны каждой величины равны u : m , v : 2 ^н , ты _: 2 ^{2 н} , и ĵ _v : 2 ^м . (Итак, j — это m -кортеж из 2 ^н -битные числа, в то время как ĵ, поскольку транспонирование j равно 2 ^н -кортеж из m -битных чисел. Поэтому и j , и ĵ содержат m 2 ^н биты.)

A1 является схемой аксиом, а не аксиомой, поскольку содержит метапеременные , а именно m , i , n и j ₀ – j _m-1 . Фактические аксиомы аксиоматизации получаются путем присвоения метапеременным определенных значений. Например, если мы возьмем m = n = i = j ₀ = 1 , мы сможем вычислить два бита i o ĵ из i ₁ = 0 и i ₀ = 1 , поэтому i o ĵ = 2 (или 10 , если записать как двухбитное число). Полученный экземпляр, а именно ¹ ф ₁ ( ¹ ж ₁ ) = ¹ f ₂ выражает знакомую аксиому ¬¬ x = x двойного отрицания. Правило R3 позволяет нам сделать вывод, что ¬¬¬ x = ¬ x , приняв s ₀ за ¹ ф ₁ ( ¹ f ₁ ) или ¬¬ x ₀ , t ₀ быть ¹ f ₂ или x ₀ и ^м если _{бы я} был ¹ f ₁ или ¬ .

Для каждых m и n существует только конечное число аксиом, реализующих A1 , а именно 2 ^{2 м} × (2 ^{2 н} ) ^м . Каждый экземпляр определяется 2 ^м + м2 ^н биты.

Мы рассматриваем R1 как правило вывода, даже несмотря на то, что оно похоже на аксиому, не имеющую посылок, поскольку это правило, независимое от предметной области, наряду с R2 и R3 , общее для всех эквациональных аксиоматизаций, будь то групп, колец или любой другой разновидности. Единственная сущность, специфичная для булевых алгебр, — это схема аксиом A1 . Таким образом, говоря о различных эквациональных теориях, мы можем отодвинуть правила в сторону как независимые от конкретных теорий и ограничить внимание аксиомами как единственной частью системы аксиом, характеризующей конкретную эквациональную теорию.

Эта аксиоматизация является полной, а это означает, что каждый булев закон s = t доказуем в этой системе. Сначала индукцией по высоте s доказывается , что каждый булев закон, для которого t является атомарным, доказуем, используя R1 для базового случая (поскольку отдельные атомы никогда не бывают равными) и A1 и R3 для шага индукции ( это приложение). Эта стратегия доказательства представляет собой рекурсивную процедуру вычисления s для получения атома. Затем, чтобы доказать s = t в общем случае, когда t может быть приложением, используйте тот факт, что если s = t является тождеством, то s и t должны оцениваться как один и тот же атом, назовем его u . Итак, сначала докажите s = u и t = u, как указано выше, то есть оцените s и t , используя A1 , R1 и R3 , а затем вызовите R2 , чтобы сделать вывод s = t .

В A1 , если мы просмотрим число n ^м поскольку тип функции m → n и m _n как приложение m ( n ) , мы можем переинтерпретировать числа i , j , ĵ и i o ĵ как функции типа i : ( m →2)→2 , j : m →(( n →2)→2) , ĵ : ( n →2)→( m →2) и i o ĵ : ( n →2)→2 . Определение ( i o ĵ ) _v = i _{ĵ v} в A1 затем переводится в ( i o ĵ )( v ) = i ( ĵ ( v )) , то есть i o ĵ определяется как композиция i и ĵ понимается как функции. Таким образом, содержание A1 сводится к определению применения термина как по сути композиции, по модулю необходимости транспонировать m -кортеж j , чтобы типы совпадали подходящим для композиции. Эта композиция входит в ранее упомянутую категорию Ловера о наборах власти и их функциях. Таким образом, мы перевели коммутирующие диаграммы этой категории, как эквациональную теорию булевых алгебр, в эквациональные следствия A1 как логическое представление этого конкретного закона композиции.

Основная решетчатая структура

В основе каждой булевой алгебры B лежит частично упорядоченное множество или частично упорядоченное множество ( B ,≤) . Отношение частичного порядка определяется соотношением x ≤ y только тогда, когда x = x ∧ y или, что то же самое, когда y = x ∨ y . Учитывая множество X элементов булевой алгебры, верхняя граница X — это элемент y такой, что для каждого элемента x из X x , ⩽ y а нижняя граница X — это элемент y такой, что для каждого элемента x из X Икс , у ≤ Икс .

Суп , X — это наименьшая верхняя граница X , а именно верхняя граница X меньше или равна каждой верхней границе X. которая Двойственным образом X является X максимальной нижней границей инф . Суп x и y всегда существует в базовом частично упорядоченном множестве булевой алгебры, будучи x ∨ y , и аналогично существует их inf, а именно x ∧ y . Пустой элемент sup равен 0 (нижний элемент), а пустой элемент inf равен 1 (верхний). Отсюда следует, что каждое конечное множество имеет как sup, так и inf. Бесконечные подмножества булевой алгебры могут иметь или не иметь sup и/или inf; в алгебре степенных множеств они всегда так делают.

Любое частично упорядоченное множество ( B ,≤) такое, что каждая пара элементов x , y имеет как sup, так и inf, называется решеткой . Мы пишем x ∨ y для sup и x ∧ y для inf. Базовое ЧУМ булевой алгебры всегда образует решетку. Решетка называется дистрибутивной, когда x ∧ ( y ∨ z ) = ( x ∧ y ) ∨ ( x ∧ z ) или, что то же самое, когда x ∨( y ∧ z ) = ( x ∨ y ) ∧ ( x ∨ z ) , поскольку любой закон подразумевает другой в решетке. Это законы булевой алгебры, согласно которым базовое ЧУ множество булевой алгебры образует дистрибутивную решетку.

Учитывая решетку с нижним элементом 0 и верхним элементом 1, пара элементов x , y называется дополнительной, когда x ∧ y = 0 и x ∨ y = 1 , и тогда мы говорим, что y является дополнением x и наоборот. наоборот. Любой элемент x распределительной решетки с верхом и низом может иметь не более одного дополнения. Когда каждый элемент решетки имеет дополнение, решетка называется дополненной. Отсюда следует, что в дополненной дистрибутивной решетке дополнение к элементу всегда существует и уникально, что делает дополнение унарной операцией. Более того, каждая дополняемая дистрибутивная решетка образует булеву алгебру, и наоборот, каждая булева алгебра образует дополняемую дистрибутивную решетку. Это дает альтернативное определение булевой алгебры, а именно как любой дополняемой дистрибутивной решетки. Каждое из этих трех свойств может быть аксиоматизировано с помощью конечного числа уравнений, следовательно, эти уравнения, взятые вместе, составляют конечную аксиоматизацию эквациональной теории булевых алгебр.

В классе алгебр, определяемом как все модели набора уравнений, обычно бывает, что некоторые алгебры этого класса удовлетворяют большему количеству уравнений, чем только те, которые необходимы для квалификации их в класс. Класс булевых алгебр необычен тем, что, за единственным исключением, каждая булева алгебра удовлетворяет именно булевым тождествам и не более. Исключением является одноэлементная булева алгебра, которая обязательно удовлетворяет каждому уравнению, даже x = y , и поэтому иногда называется противоречивой булевой алгеброй.

гомоморфизмы

Булев гомоморфизм — это функция h : A → B между булевыми алгебрами A , B такая, что для каждой булевой операции ^м ф _я :

$$h(^{m}\!f_{i}(x_{0},...,x_{m-1}))={}^{m}\!f_{i}(h(x_{0},...,x_{m-1}))$$

Категория имеет в качестве объектов все булевы алгебры, а в качестве морфизмов — булевых алгебр Bool булевы гомоморфизмы между ними.

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

В другом направлении может существовать множество гомоморфизмов булевой алгебры B в 2 . Любой такой гомоморфизм разделяет B на элементы, отображаемые в 1, и элементы в 0. Подмножество B называется ультрафильтром B , состоящее из первых , . Когда B конечен, его ультрафильтры соединяются с его атомами; один атом отображается в 1, а остальные в 0. Таким образом, каждый ультрафильтр B состоит из атома B и всех элементов над ним; следовательно, ровно половина элементов B находится в ультрафильтре, а ультрафильтров столько же, сколько атомов.

Для бесконечных булевых алгебр понятие ультрафильтра становится значительно более тонким. Элементы, большие или равные атому, всегда образуют ультрафильтр, как и многие другие множества; например, в булевой алгебре конечных и коконитных множеств целых чисел коконечные множества образуют ультрафильтр, даже если ни один из них не является атомом. Аналогично, набор степеней целых чисел имеет среди своих ультрафильтров набор всех подмножеств, содержащих данное целое число; таких «стандартных» ультрафильтров, которые можно отождествить с самими целыми числами, счетно много, но «нестандартных» ультрафильтров еще несчетно. Они формируют основу для нестандартного анализа , предоставляя представления для таких классически противоречивых объектов, как бесконечно малые и дельта-функции.

Бесконечные расширения

Напомним определение sup и inf из раздела выше, посвященного частичному порядку булевой алгебры. Полная булева алгебра — это такая алгебра, каждое подмножество которой имеет как sup, так и inf, даже бесконечные подмножества. Гейфман [1964] и Хейлз [1964] независимо друг от друга показали, что бесконечных свободных полных булевых алгебр не существует. Это предполагает, что логика с бесконечными операциями размера множества может иметь множество термов — точно так же, как логика с финитными операциями может иметь бесконечное количество термов.

Однако существует другой подход к введению бесконечных булевых операций: просто исключить слово «финитный» из определения булевой алгебры. Модель эквациональной теории алгебры всех операций над {0,1} арности вплоть до мощности модели называется полной атомной булевой алгеброй, или CABA . (Вместо этого неудобного ограничения на арность мы могли бы допустить любую арность, что привело бы к другой неловкости: сигнатура тогда была бы больше, чем любой набор, то есть правильный класс. Одним из преимуществ последнего подхода является то, что он упрощает определение гомоморфизма между CABA разной мощности .) Такую алгебру можно эквивалентно определить как полную булевую алгебру , которая является атомарной , что означает, что каждый элемент является разновидностью некоторого набора атомов. Свободные CABA существуют для всех мощностей множества V генераторов . , а именно степенного множества алгебры 2 ^{2 V} , что является очевидным обобщением конечных свободных булевых алгебр. Это аккуратно спасает бесконечную булеву логику от участи, которой ее, казалось, обрек результат Гейфмана-Хейлза.

Несуществование свободных полных булевых алгебр можно объяснить неспособностью расширить уравнения булевой логики подходящим образом на все законы, которые должны выполняться для бесконечной конъюнкции и дизъюнкции, в частности, пренебрежением дистрибутивностью в определении полной булевой алгебры. Полная булева алгебра называется полностью дистрибутивной, если произвольные конъюнкции распределяются по произвольным дизъюнкциям, и наоборот. Булева алгебра является CABA тогда и только тогда, когда она полна и полностью дистрибутивна, что дает третье определение CABA. Четвертое определение — это любая булева алгебра, изоморфная алгебре степенного множества.

Полный гомоморфизм — это гомоморфизм, который сохраняет все существующие суппорты, а не только конечные суппорты, и то же самое касается infs. Категория CABA всех CABA и их полных гомоморфизмов двойственна категории множеств и их функций, а это означает, что она эквивалентна противоположности этой категории (категории, возникающей в результате обращения всех морфизмов). Все не так просто с категорией Bool булевых алгебр и их гомоморфизмов, которую Маршалл Стоун фактически показал (хотя ему не хватало ни языка, ни концептуальной основы, чтобы сделать двойственность явной), двойственной категории полностью несвязного компакта Хаусдорфа. пространства , впоследствии названные пространствами Стоуна .

Другой бесконечный промежуточный класс между булевыми алгебрами и полными булевыми алгебрами — это понятие сигма-алгебры . Это определяется аналогично полным булевым алгебрам, но с ограничениями sups и infs счетной арностью. То есть сигма-алгебра — это булева алгебра со всеми счетными sup и inf. Поскольку sups и infs имеют ограниченную мощность , в отличие от ситуации с полными булевыми алгебрами , результат Гейфмана-Хейлза не применим и свободные сигма-алгебры существуют. Однако, в отличие от ситуации с CABA, свободная счетно порожденная сигма-алгебра не является алгеброй степенного множества.

определения

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

Стоун (1936)

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

Джонстон (1982)

Булева алгебра — это фильтрованный копредел конечных булевых алгебр.

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

Чтобы представить это в перспективе, бесконечные множества возникают как отфильтрованные копределы конечных множеств, бесконечные CABA как отфильтрованные пределы алгебр конечных степенных множеств и бесконечные пространства Стоуна как отфильтрованные пределы конечных множеств. Таким образом, если кто-то начнет с конечных множеств и спросит, как они обобщаются на бесконечные объекты, есть два способа: «сложение» их дает обычные или индуктивные множества, а «умножение» их дает пространства Стоуна или проконечные множества . Тот же выбор существует для алгебр с конечной степенью множества как двойственных конечных множеств: сложение дает булевы алгебры как индуктивные объекты, а умножение дает CABA или алгебры степенных множеств как проконечные объекты.

Характерной отличительной особенностью является то, что основная топология построенных таким образом объектов, если она определена как Хаусдорф , дискретна для индуктивных объектов и компактна для проконечных объектов. Топология конечных хаусдорфовых пространств всегда одновременно дискретна и компактна, тогда как для бесконечных пространств «дискретное» и «компактное» исключают друг друга. Таким образом, при обобщении конечных алгебр (любых, не только булевых) на бесконечные «дискретные» и «компактные» части компании, и приходится выбирать, какую из них сохранить. Общее правило как для конечных, так и для бесконечных алгебр состоит в том, что финитарные алгебры дискретны, тогда как их двойственные алгебры компактны и содержат бесконечные операции. Между этими двумя крайностями существует множество промежуточных бесконечных булевых алгебр, топология которых не является ни дискретной, ни компактной.

См. также

• Логический домен
• Булева функция
• Логическая функция
• Логическая модель
• Декартова закрытая категория
• Замкнутая моноидальная категория
• Полная булева алгебра
• Элементарные топосы
• Поле наборов
• Фильтр (математика)
• Финитарная булева функция
• Свободная булева алгебра
• Функциональная полнота
• Идеал (теория порядка)
• Решетка (заказать)
• Алгебра Линденбаума–Тарского
• Список тем по булевой алгебре
• Моноидальная категория
• Пропозициональное исчисление
• Алгебра Роббинса
• Таблица истинности
• Ультрафильтр
• Универсальная алгебра

Ссылки

• Биркгоф, Гаррет (1935). «О строении абстрактных алгебр». Учеб. Кэмб. Фил. Соц . 31 (4): 433–454. Бибкод : 1935PCPS...31..433B . дои : 10.1017/s0305004100013463 . ISSN   0008-1981 . S2CID   121173630 .
• Буль, Джордж (2003) [1854]. Исследование законов мышления . Книги Прометея. ISBN  978-1-59102-089-9 .
• Двингер, Филип (1971). Введение в булевы алгебры . Вюрцбург: Physica Verlag.
• Гайфман, Хаим (1964). «Бесконечные логические полиномы, I» . Основы математики . 54 (3): 229–250. дои : 10.4064/fm-54-3-229-250 . ISSN   0016-2736 .
• Живант, Стивен; Халмос, Пол (2009). Введение в булеву алгебру . Тексты бакалавриата по математике . Спрингер. ISBN  978-0-387-40293-2 .
• Грау, А.А. (1947). «Трнарная булева алгебра» . Бык. Являюсь. Математика. Соц . 33 (6): 567–572. дои : 10.1090/S0002-9904-1947-08834-0 .
• Хейлз, Альфред В. (1964). «О несуществовании свободных полных булевых алгебр» . Основы математики . 54 : 45–66. дои : 10.4064/fm-54-1-45-66 . ISSN   0016-2736 .
• Халмос, Пол (1963). Лекции по булевой алгебре . есть Ностранд. ISBN  0-387-90094-2 .
• Живант, Стивен; Халмос, Пол (1998). Логика как алгебра . Математическая экспозиция Дольчиани. Математическая ассоциация Америки . ISBN  978-0-883-85327-6 .
• Джонстон, Питер Т. (1982). Каменные просторы . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN  978-0-521-33779-3 .
• Кетонен, Юсси (1978). «Строение счетных булевых алгебр». Анналы математики . 108 (1): 41–89. дои : 10.2307/1970929 . JSTOR   1970929 .
• Коппельберг, Сабина (1989) «Общая теория булевых алгебр» в книге Монка Дж. Дональда и Боннета Роберта, ред., Справочник по булевым алгебрам, Vol. 1 . Северная Голландия. ISBN   978-0-444-70261-6 .
• Пирс, CS (1989) Сочинения Чарльза С. Пирса: хронологическое издание: 1879–1884 гг . Клозель, CJW, изд. Индианаполис: Издательство Университета Индианы. ISBN   978-0-253-37204-8 .
• Ловер, Ф. Уильям (1963). «Функториальная семантика алгебраических теорий» . Труды Национальной академии наук . 50 (5): 869–873. Бибкод : 1963PNAS...50..869L . дои : 10.1073/pnas.50.5.869 . ПМК   221940 . ПМИД   16591125 .
• Шредер, Эрнст (1890–1910). Лекции по алгебре логики (точная логика), I–III . Лейпциг: Б. Г. Тойбнер.
• Сикорский, роман (1969). Булевы алгебры (3-е изд.). Берлин: Springer Verlag. ISBN  978-0-387-04469-9 .
• Стоун, Миннесота (1936). «Теория представления булевых алгебр». Труды Американского математического общества . 40 (1): 37–111. дои : 10.2307/1989664 . ISSN   0002-9947 . JSTOR   1989664 .
• Тарский, Альфред (1983). Логика, семантика, метаматематика , Коркоран, Дж., изд. Хакетт. 1956 г., 1-е издание отредактировано и переведено Дж. Х. Вудгером, Оксфордский университет. Нажимать. Включает английские переводы следующих двух статей:
  • Тарский, Альфред (1929). «О закрытых классах применительно к некоторым элементарным операциям». Фундамента Математика . 16 : 195–97. ISSN   0016-2736 .
  • Тарский, Альфред (1935). «Zur Grundlegung der Booleschen Algebra, I» . Основы математики . 24 : 177–98. дои : 10.4064/fm-24-1-177-198 . ISSN   0016-2736 .
• Vladimirov, D.A. (1969). булевы алгебры (Boolean algebras, in Russian, German translation Boolesche Algebren 1974) . Nauka (German translation Akademie-Verlag).