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

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

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

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

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

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

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

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

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

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

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

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

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

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

Семьи индексируется с помощью множества индексов . В случае семейства операций, образующих алгебру, индексы называются символами операций , составляя язык этой алгебры. Операция, индексируемая каждым символом, называется обозначением или интерпретацией этого символа. Каждый символ операции определяет арность его интерпретации, поэтому все возможные интерпретации символа имеют одинаковую арность. В общем, алгебра может интерпретировать различные символы с помощью одной и той же операции, но это не относится к прототипу, символы которого находятся в однозначном соответствии с его операциями. Таким образом, прототип имеет $2 2 n n$ -арные символы операций, называемые символами булевых операций и образующие язык булевой алгебры. Только некоторые операции имеют обычные символы, такие как $\neg$ для отрицания, $\land$ для соединения и $\lor$ для дизъюнкции. Удобно рассматривать $я$ -м $п$ -ичный символ будет $п е I$ , как это сделано ниже в разделе таблицы истинности .

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

Алгебра удовлетворяет уравнению, когда уравнение выполняется для всех возможных значений его переменных в этой алгебре, когда символы операций интерпретируются как заданные этой алгеброй. Законы булевой алгебры - это уравнения на языке булевой алгебры, которым удовлетворяет прототип. Первые три из приведенных выше примеров являются булевыми законами, но не четвертым, поскольку $1\land0 \neq 1$ .

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

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

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

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

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

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

Основа [ править ]

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

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

Общими элементами решетки и базиса кольца являются константы 0 и 1, а также ассоциативная коммутативная бинарная операция , называемая соответствием $x \land y$ в базисе решетки, и умножение $xy$ в базисе кольца. Различие только терминологическое. Базис решетки имеет дальнейшие операции соединения , $x \lor y$ , и дополнения , $\neg x$ . Кольцо базис имеет вместо арифметической операции $х \oplus у$ из дополнения (символ $\oplus$ используются в предпочтении $+$ потому что последнему иногда дается логическое чтение соединения).

Быть базисом - значит давать все остальные операции по композиции, откуда любые две основы должны быть взаимопереводимыми. Базис решетки переводит $x \lor y$ в базис кольца как $x \oplus y \oplus xy$ , а $\neg x$ как $x \oplus1$ . Наоборот, базис кольца переводит $x \oplus y$ в базис решетки как $(x \lor y) \land\neg (x \land y)$ .

Обе эти базы позволяют определять булевы алгебры через подмножество эквациональных свойств булевых операций. Для базиса решетки достаточно определить булеву алгебру как дистрибутивную решетку, удовлетворяющую $x \land\neg x = 0$ и $x \lor\neg x = 1$ , называемую дополняемой дистрибутивной решеткой. Базис колец превращает булеву алгебру в булево кольцо , а именно в кольцо, для которого $x 2 = x$ .

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

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

В операции И-НЕ (двойное ИЛИ-ИЛИ) всего этого нет, поэтому она сама по себе составляет основу.

Таблицы истинности [ править ]

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

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

Таблицы истинности для булевых операций арности до 2

Константы
${\ Displaystyle {} ^ {0} \! е_ {0}}$	${\ Displaystyle {} ^ {0} \! е_ {1}}$
0	1

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

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

Эти таблицы продолжаются с более высокой арностью, с $2 n$ строками с арностью $n$ , каждая строка дает оценку или привязку $n$ переменных $x 0, ... x n -1,$ а каждый столбец с заголовком $n f i$ дает значение $n f i (х 0, ..., х п -1)$ из $я$ -го $п$ -ичной операции в этой оценке. Операции включают переменные, например $1 f 2$ - $x 0,$ а $2 f 10$ - это $x 0$ (как две копии его унарного аналога), а $2 f 12$ - это $x 1$ (без унарного аналога). Отрицание или дополнение $\neg x 0$ отображается как $1 f 1$ и снова как $2 f 5$ вместе с $2 f 3$ ( $\neg x 1$ , которое не появилось в арности 1), дизъюнкцией или объединением $x 0 \lor x 1$ как $2 f 14$ , соединение или пересечение $x 0 \land x 1$ как $2 f 8$ , импликация $x 0 \to x 1 как 2 f 13$ , исключительная или симметричная разность $x 0 \oplus x 1$ как $2 f 6$ , установить разность $x 0 - x 1$ как $2 f 2$ , и поэтому на.

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

(i)

i

-я строка в левой половине таблицы - это двоичное представление

i

с его младшим значащим или

0-м

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

(ii)

j

-й столбец в правой половине таблицы является двоичным представлением

j

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

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

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

Битовые векторы [ править ]

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

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

Алгебра степенных множеств [ править ]

Пример 3 . Булеана алгебра , множество $2 W$ всех подмножеств данного множества $W$ . Это всего лишь замаскированный пример 2, где $W$ служит для индексации битовых позиций. Любое подмножество $X$ из $W$ можно рассматривать как битовый вектор , имеющий 1 - х раз в тех позициях битов , индексированных элементов $X$ . Таким образом, вектор всех нулей - это пустое подмножество $W,$ тогда как вектор всех единиц - это сам $W$ , которые являются константами 0 и 1 соответственно алгебры степенных множеств. Аналог дизъюнкции $x \lor y$ - это объединение $X \cup Y$ , В то время как совместно $х \land у$ является пересечением $X \cap Y$ . Отрицание $\neg х$ становится $~ X$ , дополнение по отношению к $W$ . Также существует разность множеств $X ∖ Y = X \cap ~ Y$ , симметричная разность $(X ∖ Y) \cup (Y ∖ X)$ , тройное объединение $X \cup Y \cup Z$ и так далее. Атомы здесь - синглтоны, те подмножества, которые содержат ровно один элемент.

Примеры 2 и 3 являются частными случаями общей конструкции алгебры, называемой прямым произведением , применимой не только к булевым алгебрам, но и ко всем видам алгебры, включая группы, кольца и т. Д. Прямое произведение любого семейства булевых алгебр $B i,$ где $i$ пробегает некоторое индексное множество $I$ (не обязательно конечное или даже счетное) является булевой алгеброй, состоящей из всех $I$ -наборов $(... x i, ...)$ , $i$ -й элемент которых взят из $B i$ . Операции прямого произведения - это соответствующие операции составляющих алгебр, действующих в пределах их соответствующих координат; в частности , операции $п е J$ продукта действует на $п$ $я$ -наборов, применяя операцию $п ф J$ о $B я$ к $п$ элементов в $я$ -я координата $п$ кортежей, для всех $я$ в $I$ .

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

Теоремы представления [ править ]

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

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

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

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

Другие примеры [ править ]

Это удобно , когда речь идет о множестве X натуральных чисел , чтобы просмотреть его в виде последовательности $х 0, х 1, х 2, ...$ бит, с $й я = 1$ тогда и только тогда , когда $я \in X$ . Эта точка зрения облегчит разговор о подалгебрах алгебры степенных множеств $2 N$ , что с этой точки зрения делает булеву алгебру всех последовательностей битов. Он также хорошо сочетается со столбцами таблицы истинности: когда столбец читается сверху вниз, он представляет собой последовательность битов, но в то же время его можно рассматривать как набор этих оценок (присвоения переменным слева половина таблицы), в котором функция, представленная этим столбцом, оценивается как 1.

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

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

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

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

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

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

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

Булевы алгебры логических операций [ править ]

Сами $n$ -арные булевы операции составляют алгебру набора степеней $2 W$ , а именно, когда $W$ берется как набор из $2 n$ оценок $n$ входов. С точки зрения системы именования операций $n f i,$ где $i$ в двоичном формате представляет собой столбец таблицы истинности, столбцы могут быть объединены с логическими операциями любой арности для создания других столбцов, присутствующих в таблице. То есть мы можем применить любую булеву операцию арности $m$ к $m$ логическим операциям арности $n,$ чтобы получить булеву операцию арности $n$ для любого $m$ и $п$ .

Практическое значение этого соглашения как для программного, так и для аппаратного обеспечения состоит в том, что $n-$ мерные логические операции могут быть представлены в виде слов соответствующей длины. Например, каждая из 256 тернарных логических операций может быть представлена как беззнаковый байт. Доступные логические операции, такие как И и ИЛИ, могут затем использоваться для создания новых операций. Если мы возьмем $х$ , $у$ и $г$ (дозирования с индексами переменных на данный момент) , чтобы быть $10101010$ , $11001100$ и $11110000$ соответственно (170, 204 и 240 в десятичной, $0хАА$ , $0xCC$ и $0xf0$ в шестнадцатеричном формате), их попарные конъюнкции являются $x \land y = 10001000$ , $y \land z = 11000000$ и $z \land x = 10100000$ , а их попарные дизъюнкции равны $x \lor y = 11101110$ , $y \lor z = 11111100$ и $z \lor x = 11111010$ . $Дизъюнкция$ трех союзов составляет $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$ являются таблицами истинности для $\lor$ , $1110$ и $\land$ , $1000$ , поэтому операцию можно сформулировать так, как если бы $z,$ затем $x \lor y,$ иначе $x \land y$ . Поскольку он симметричен, его можно с равным успехом сформулировать как если $x,$ то $y \lor z$ else $y \land z$ , или если $y,$ то $z \lor x,$ иначе $z \land x$ . Если рассматривать как метку 8-вершинного 3-куба, верхняя половина помечена цифрой 1, а нижняя половина - 0; по этой причине он был назван медианным оператором с очевидным обобщением на любое нечетное число переменных (нечетное, чтобы избежать связи, когда ровно половина переменных равна 0).

Аксиоматизирующие булевы алгебры [ править ]

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

Булевы тождества - это утверждения вида $s = t,$ где $s$ и $t$ - $n-$ мерные термины, под которыми мы будем понимать термины, переменные которых ограничены значениями от $x 0$ до $x n-1$ . $П$ -ичный термин является либо атом или приложение. Приложение $m f i (t 0, ..., t m -1)$ представляет собой пару, состоящую из $m$ -арной операции $m f i$ и списка или $m$ -набора $(Т 0, ..., т м -1)$ из $т п$ -ичных терминов , называемых операндами .

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

Что такое атом? Обычно атом - это либо константа (0 или 1), либо переменная $x i,$ где $0 \leq i < n$ . Для техники доказательства здесь удобно определять атомы как $n$ -арные операции $n f i$ , которые, хотя и рассматриваются здесь как атомы, тем не менее означают то же самое, что и обычные члены точной формы $n f i (x 0, ..., х п -1)$ (точно в том, что переменные должны быть перечислены в указанном порядке, без повторений или пропусков). Это не ограничение, потому что атомы этой формы включают в себя все обычные атомы, а именно константы 0 и 1, которые возникают здесь как $n$ -арные операции $n f 0$ и $n f -1$ для каждого $n$ (сокращенно $2 2 n -1$ to $-1$ ), а переменные $x 0, ..., x n -1,$ как видно из таблиц истинности, где $x 0$ появляется как унарная операция $1 f 2$ и двоичная операция $2 f 10, в$ то время как $x 1$ отображается как $2 f 12$ .

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

А1 .

m f i (n f j 0, ..., n f j m -1) = n f i o ĵ,

где

(i o ĵ) v = i ĵ v

, где

ĵ

является

j

транспонированным, определяемым

(ĵ v) u = (j u) v

.

R1 . Без предпосылок вывести

t = t

.

R2 . Из

s = u

и

t = u

выведите

s = t,

где

s

,

t

и

u

-

n-

мерные члены.

R3 . Из

s 0 = t 0, ..., s m -1 = t m -1

вывести

m f i (s 0, ..., s m -1) = m f i (t 0, ..., t m -1)

, где все члены

s i, t i

являются

n

-арными.

Смысл побочного условия на A1 состоит в том, что $i o ĵ$ - это $2 n$ -битное число, $v$ -й бит которого является $ĵ v$ -м битом $i$ , где диапазоны каждой величины равны $u : m$ , $v : 2 n$ , $j u : 2 2 n$ и $ĵ v : 2 m$ . (Таким образом, $j$ - это $m$ -набор из $2 n$ -битных чисел, а $ĵ$ как транспонирование $j$ представляет собой $2 n$ -набор $m$ -битных чисел. Следовательно, оба $j$ и $ĵ$ содержат $m 2 n$ битов.)

A1 является схемой аксиом, а не аксиомой в силу наличия метапеременных , а именно от $m$ , $i$ , $n$ и $j 0$ до $j m-1$ . Фактические аксиомы аксиоматизации получаются путем установки метапеременных на определенные значения. Например, если мы возьмем $m = n = i = j 0 = 1$ , мы можем вычислить два бита $i o ĵ$ из $i 1 = 0$ и $i 0 = 1$ , поэтому $i o ĵ = 2$ (или $10,$ если записано как двухбитное число). Результирующий пример, а именно $1 f 1 (1 f 1) = 1 f 2$ , выражает известную аксиому $\neg\neg x = x$ двойного отрицания. Правило R3 затем позволяет нам вывести $\neg\neg\neg x = \neg x$ , взяв $s 0$ равным $1 f 1 (1 f 1)$ или $\neg\neg x 0$ , $t 0$ быть $1 f 2$ или $x 0$ , а $m f i$ быть $1 f 1$ или $\neg$ .

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

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

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

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

Основная структура решетки [ править ]

В основе каждой булевой алгебре $B$ является частично упорядоченное множество или ч.у.м. $(B, \leq)$ . Отношение частичного порядка определяется как $x \leq y$ только тогда, когда $x = x \land y$ , или, что эквивалентно, когда $y = x \lor y$ . Принимая во внимание множество $X$ элементов булевой алгебры, An верхней границы на $X$ представляет собой элемент $у$ такой , что для любого элемента $х$ из $X$ , $х \leq у$ , В то время как нижняя граница $X$ представляет собой элемент $у$ такой , что для любого элемента $х$ из $X$ , $у \leq х$ .

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

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

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

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

Булевы гомоморфизмы [ править ]

Булева гомоморфизм - это функция $h : A \to B$ между булевыми алгебрами $A, B$ такая, что для каждой булевой операции $m f i$ :

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

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

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

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

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

Бесконечные расширения [ править ]

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

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

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

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

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

Другие определения булевой алгебры [ править ]

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

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

Джонстон (1982): Булева алгебра - это фильтрованный копредел конечных булевых алгебр.

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

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

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

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

Логический домен
Логическая функция
Булевозначная функция
Булевозначная модель
Декартова закрытая категория
Замкнутая моноидальная категория
Полная булева алгебра
Элементарные топосы

Поле наборов
Фильтр (математика)
Финитарная логическая функция
Свободная булева алгебра
Функциональная полнота
Идеал (теория порядка)
Решетка (заказ)
Алгебра Линденбаума – Тарского

Моноидальная категория
Исчисление высказываний
Алгебра Роббинса
Таблица истинности
Ультрафильтр
Универсальная алгебра

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

Биркгоф, Гарретт (1935). «О строении абстрактных алгебр». Proc. Camb. Фил. Soc . 31 (4): 433–454. Bibcode : 1935PCPS ... 31..433B . DOI : 10.1017 / s0305004100013463 . ISSN 0008-1981 .
Буль, Джордж (2003) [1854]. Исследование законов мысли . Книги Прометея. ISBN 978-1-59102-089-9.
Двинджер, Филипп (1971). Введение в булевы алгебры . Вюрцбург: Physica Verlag.
Гайфман, Хаим (1964). «Бесконечные булевы многочлены, I» . Fundamenta Mathematicae . 54 (3): 229–250. DOI : 10,4064 / фм-54-3-229-250 . ISSN 0016-2736 .
Гивант, Стивен; Халмос, Пол (2009). Введение в булевы алгебры . Тексты для бакалавриата по математике . Springer. ISBN 978-0-387-40293-2.
Грау, AA (1947). «Тернарная булева алгебра» . Бык. Являюсь. Математика. Soc . 33 (6): 567–572. DOI : 10.1090 / S0002-9904-1947-08834-0 .
Хейлз, Альфред В. (1964). «О несуществовании свободных полных булевых алгебр» . Fundamenta Mathematicae . 54 : 45–66. DOI : 10,4064 / фм-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. DOI : 10.2307 / 1970929 . JSTOR 1970929 .
Коппельберг, Сабина (1989) «Общая теория булевых алгебр» в книге Монка, Дж. Дональда и Бонне, Роберта, ред., Справочник по булевым алгебрам, Vol. 1 . Северная Голландия. ISBN 978-0-444-70261-6 .
Пирс, CS (1989) сочинения Чарльза С. Пирса: хронологическое издание: 1879–1884 . Kloesel, CJW, изд. Индианаполис: Издательство Индианского университета. ISBN 978-0-253-37204-8 .
Ловер, Ф. Уильям (1963). «Функториальная семантика алгебраических теорий» . Труды Национальной академии наук . 50 (5): 869–873. Bibcode : 1963PNAS ... 50..869L . DOI : 10.1073 / pnas.50.5.869 . PMC 221940 . PMID 16591125 .
Шредер, Эрнст (1890–1910). Vorlesungen über die Algebra der Logik (exakte Logik), I – III . Лейпциг: BG Teubner.
Сикорский, Роман (1969). Булевы алгебры (3-е изд.). Берлин: Springer-Verlag. ISBN 978-0-387-04469-9.
Стоун, MH (1936). «Теория представлений булевых алгебр». Труды Американского математического общества . 40 (1): 37–111. DOI : 10.2307 / 1989664 . ISSN 0002-9947 . JSTOR 1989664 .
Тарский, Альфред (1983). Логика, семантика, метаматематика , Corcoran, J., ed. Хакетт. 1956 1-е издание, отредактированное и переведенное Дж. Х. Вудгером, Оксфордский университет. Нажмите. Включает английские переводы следующих двух статей:
- Тарский, Альфред (1929). «Sur les classes закрывает par rapport à некоторых élémentaires». Fundamenta Mathematicae . 16 : 195–97. ISSN 0016-2736 .
- Тарский, Альфред (1935). "Zur Grundlegung der Booleschen Algebra, I" . Fundamenta Mathematicae . 24 : 177–98. DOI : 10,4064 / фм-24-1-177-198 . ISSN 0016-2736 .
Владимиров Д.А. (1969). булевы алгебры (Булевы алгебры, на русском языке, немецкий перевод Boolesche Algebren 1974) . Наука (немецкий перевод Akademie-Verlag).