Канонически определенные булевы алгебры - Boolean algebras canonically defined

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

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

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

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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основа

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

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

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

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

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

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

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

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

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

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

Этот макет и связанное с ним наименование операций полностью проиллюстрированы здесь для арностей от 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}}$	${displaystyle {} ^ {2}! е_ {9}}$	${displaystyle {} ^ {2}! е_ {10}}$	${displaystyle {} ^ {2}! е_ {11}}$	${displaystyle {} ^ {2}! е_ {12}}$	${displaystyle {} ^ {2}! е_ {13}}$	${displaystyle {} ^ {2}! е_ {14}}$	${displaystyle {} ^ {2}! е_ {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^п ряды по арности п, каждая строка дает оценку или привязку п переменные Икс₀,...Икс_п−1 и каждая колонка озаглавлена ^пж_я придавая значение ^пж_я(Икс₀,...,Икс_п−1) из я-й п-арная операция при такой оценке. Операции включают переменные, например ¹ж₂ является Икс₀ пока ²ж₁₀ является Икс₀ (как две копии его унарного аналога) и ²ж₁₂ является Икс₁ (без унарного аналога). Отрицание или дополнение ¬Икс₀ выглядит как ¹ж₁ и снова как ²ж₅, вместе с ²ж₃ (¬Икс₁, которые не появлялись при арности 1), дизъюнкции или объединении Икс₀∨Икс₁ в качестве ²ж₁₄, соединение или пересечение Икс₀∧Икс₁ в качестве ²ж₈, значение Икс₀→Икс₁ в качестве ²ж₁₃, исключительная или симметричная разность Икс₀⊕Икс₁ в качестве ²ж₆, установить разницу Икс₀−Икс₁ в качестве ²ж₂, и так далее.

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

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

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

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

Примеры

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

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

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

Алгебра набора мощности

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

Примеры 2 и 3 являются частными случаями общей конструкции алгебры, называемой прямой продукт, применимые не только к булевым алгебрам, но и ко всем видам алгебр, включая группы, кольца и т. д. Прямое произведение любого семейства B_я булевых алгебр, где я колеблется в пределах некоторого набора индексов я (не обязательно конечная или даже счетная) - это булева алгебра, состоящая из всех я-кортежи (...Икс_я,...) чей я-й элемент взят из B_я. Операции прямого произведения - это соответствующие операции составляющих алгебр, действующих в пределах их соответствующих координат; в частности операция ^пж_j продукта действует на п я-кортежи путем применения операции ^пж_j из B_я к п элементы в я-я координата п кортежи, для всех я в я.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(Икс∧у)∨(у∧z)∨(z∧Икс)

и

(Икс∨у)∧(у∨z)∧(z∨Икс)

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

(Икс∧у)∨(у∧z)∨(z∧Икс) = (Икс∨у)∧(у∨z)∧(z∨Икс),

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

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

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

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

Булевы тождества - это утверждения вида s = т куда s и т находятся п-арные термины, под которыми мы будем понимать термины, переменные которых ограничены Икс₀ через Икс_п-1. An п-ари срок это либо атом, либо приложение. Приложение ^мж_я(т₀,...,т_м-1) - пара, состоящая из м-арная операция ^мж_я и список или м-температура (т₀,...,т_м-1) из м п-ризованные термины операнды.

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

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

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

A1. ^мж_я(^пж_j₀,...,^пж_{j_м-1}) = ^пж_яоĵ куда (яоĵ)_v = я_{ĵ_v}, с ĵ существование j транспонировать, определяемый (ĵ_v)_ты = (j_ты)_v.

R1. Без предпосылок сделать вывод т = т.

R2. Из s = ты и т = ты сделать вывод s = т куда s, т, и ты находятся п-арочные условия.

R3. Из s₀ = т₀,...,s_м-1 = т_м-1 сделать вывод ^мж_я(s₀,...,s_м-1) = ^мж_я(т₀,...,т_м-1), где все термины s_я, т_я находятся п-ари.

Значение побочного условия на A1 в том, что яоĵ это 2^п-битовое число, чье v-й бит - это ĵ_v-й бит я, где диапазоны каждой величины ты: м, v: 2^п, j_ты: 2^{2^п}, и ĵ_v: 2^м. (Так j является м-набор из 2^п-битовые числа, а ĵ как транспонирование j это 2^п-набор м-битовые числа. Обе j и ĵ поэтому содержат м2^п бит.)

A1 является схемой аксиом, а не аксиомой в силу того, что содержит метапеременные, а именно м, я, п, и j₀ через j_м-1. Фактические аксиомы аксиоматизации получаются путем установки метапеременных на определенные значения. Например, если взять м = п = я = j₀ = 1, мы можем вычислить два бита яоĵ из я₁ = 0 и я₀ = 1, поэтому яоĵ = 2 (или 10, если записано как двухбитное число). Получившийся экземпляр, а именно ¹ж₁(¹ж₁) = ¹ж₂, выражает известную аксиому ¬¬Икс = Икс двойного отрицания. Правило R3 затем позволяет нам сделать вывод о ¬¬¬Икс = ¬Икс принимая s₀ быть ¹ж₁(¹ж₁) или ¬¬Икс₀, т₀ быть ¹ж₂ или же Икс₀, и ^мж_я быть ¹ж₁ или ¬.

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

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

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

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

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

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

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

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

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

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

Булевы гомоморфизмы

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

час(^мж_я(Икс₀,...,Икс_м−1)) = ^мж_я(час(Икс₀),...,час(Икс_м−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 ограничены мощность, в отличие от ситуации с полные булевы алгебры, результат Гайфмана-Хейлза неприменим и свободный сигма-алгебры существуют. Однако, в отличие от ситуации с CABA, свободная счетно порожденная сигма-алгебра не является алгеброй степенных множеств.

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

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

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

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

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

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

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