Булева алгебра — это математически богатая ветвь абстрактной алгебры . Стэнфордская энциклопедия философии определяет булеву алгебру как «алгебру двузначной логики только с сентенциальными связками или, что эквивалентно, алгебр множеств при объединении и дополнении». [1] Так же, как теория групп имеет дело с группами , а линейная алгебра — с векторными пространствами , булевы алгебры являются моделями эквациональной теории двух значений 0 и 1 (интерпретация которых не обязательно должна быть числовой). Общим для булевых алгебр, групп и векторных пространств является понятие алгебраической структуры , множества , замкнутого относительно некоторых операций, удовлетворяющих определенным уравнениям. [2]
Так же , как существуют основные примеры групп, такие как группа целых чисел и симметрическая группа S n перестановок n объектов , существуют и основные примеры булевых алгебр, такие как следующие.
Таким образом, булева алгебра позволяет применять методы абстрактной алгебры к математической логике и цифровой логике .
В отличие от групп конечного порядка , которые демонстрируют сложность и разнообразие и чья теория первого порядка разрешима только в особых случаях, все конечные булевы алгебры разделяют одни и те же теоремы и имеют разрешимую теорию первого порядка. Вместо этого тонкости булевой алгебры разделены между структурой бесконечных алгебр и алгоритмической сложностью их синтаксической структуры.
Булева алгебра рассматривает эквациональную теорию максимальной двухэлементной финитарной алгебры, называемой булевым прототипом , и модели этой теории, называемые булевыми алгебрами . [3] Эти термины определяются следующим образом.
Алгебра — это семейство операций на множестве, называемом базовым множеством алгебры. Мы принимаем базовое множество прототипа Буля за {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 -арных операций, поэтому имеется 16 · 2 = 256 тернарных операций, 256 · 2 = 65 536 четвертичных операций и так далее.
Семейство индексируется набором индексов . В случае семейства операций, образующих алгебру, индексы называются символами операций , составляющими язык этой алгебры. Операция, индексированная каждым символом, называется обозначением или интерпретацией этого символа. Каждый символ операции определяет арность своей интерпретации, откуда все возможные интерпретации символа имеют одну и ту же арность. В общем случае алгебра может интерпретировать различные символы с помощью одной и той же операции, но это не относится к прототипу, символы которого находятся во взаимно однозначном соответствии с его операциями. Поэтому прототип имеет 2 2 n n -арные символы операций, называемые символами булевых операций и образующие язык булевой алгебры. Только несколько операций имеют общепринятые символы, такие как ¬ для отрицания, ∧ для конъюнкции и ∨ для дизъюнкции. [4] Удобно считать i -ый n -арный символ n f i , как это делается ниже в разделе о таблицах истинности.
Эквациональная теория в данном языке состоит из уравнений между терминами, построенными из переменных с использованием символов этого языка. Типичные уравнения в языке булевой алгебры — x ∧ y = y ∧ x , x ∧ x = x , x ∧¬ x = y ∧¬ y и x ∧ y = x .
Алгебра удовлетворяет уравнению, когда уравнение выполняется для всех возможных значений ее переменных в этой алгебре, когда символы операций интерпретируются так, как указано в этой алгебре. Законы булевой алгебры — это уравнения на языке булевой алгебры, которым удовлетворяет прототип. Первые три из приведенных выше примеров являются булевыми законами, но не четвертый, поскольку 1∧0 ≠ 1 .
Эквациональная теория алгебры — это множество всех уравнений, которым удовлетворяет алгебра. Законы булевой алгебры, таким образом, составляют эквациональную теорию булевого прототипа.
Модель теории — это алгебра, интерпретирующая символы операций на языке теории и удовлетворяющая уравнениям теории.
То есть, булева алгебра представляет собой множество и семейство операций над ним, интерпретирующих символы булевых операций и удовлетворяющих тем же законам, что и булев прототип. [5]
Если мы определим гомолог алгебры как модель эквациональной теории этой алгебры, то булеву алгебру можно определить как любой гомолог прототипа.
Пример 1. Булев прототип — это булева алгебра, поскольку тривиально она удовлетворяет своим собственным законам. Таким образом, это прототипическая булева алгебра. Мы не называли ее так изначально, чтобы избежать появления зацикленности в определении.
Операции не обязательно должны быть явно указаны. Базис — это любой набор, из которого остальные операции могут быть получены путем композиции. «Булева алгебра» может быть определена из любого из нескольких различных базисов. Обычно используются три базиса для булевой алгебры: решетчатый базис, кольцевой базис и базис Шеффера или NAND. Эти базисы придают предмету соответственно логический, арифметический и экономный характер.
Общими элементами решетчатого и кольцевого базисов являются константы 0 и 1, а также ассоциативная коммутативная бинарная операция , называемая meet x ∧ y в решетчатом базисе и умножением xy в кольцевом базисе. Различие только терминологическое. Решетчатый базис имеет дополнительные операции join , x ∨ y , и addition , ¬ x . Кольцевой базис вместо этого имеет арифметическую операцию x ⊕ y сложения ( символ ⊕ используется вместо + , потому что последнему иногда дается булево прочтение join).
Быть базисом — значит давать все другие операции посредством композиции, откуда любые два базиса должны быть взаимопереводимыми. Решетчатый базис переводит x ∨ y в кольцевой базис как x ⊕ y ⊕ xy , а ¬ x как x ⊕1 . Обратно, кольцевой базис переводит x ⊕ y в решетчатый базис как ( x ∨ y )∧¬( x ∧ y ) .
Оба эти базиса позволяют определять булевы алгебры через подмножество эквациональных свойств булевых операций. Для решетчатого базиса достаточно определить булеву алгебру как дистрибутивную решетку, удовлетворяющую x ∧¬ x = 0 и x ∨¬ x = 1 , называемую дополненной дистрибутивной решеткой. Кольцевой базис превращает булеву алгебру в булево кольцо , а именно кольцо, удовлетворяющее x 2 = x .
Эмиль Пост дал необходимое и достаточное условие для того, чтобы набор операций был базисом для ненулевых булевых операций. Нетривиальное свойство — это свойство, которым обладают некоторые, но не все операции, составляющие базис. Пост перечислил пять нетривиальных свойств операций, отождествляемых с пятью классами Поста , каждое из которых сохраняется при композиции, и показал, что набор операций образует базис, если для каждого свойства набор содержит операцию, не имеющую этого свойства. (Обратная теорема Поста, расширяющая «если» до « если и только если », — это простое наблюдение, что свойство из этих пяти, содержащееся в каждой операции в кандидате на базис, будет также содержаться в каждой операции, образованной композицией из этого кандидата, откуда в силу нетривиальности этого свойства кандидат не сможет быть базисом.) Пять свойств Поста:
Операция NAND (двойная NOR) лишена всего этого и, таким образом, сама по себе является базисом.
Финитные операции над {0,1} могут быть представлены в виде таблиц истинности , думая о 0 и 1 как об истинностных значениях false и true . [7] Их можно расположить унифицированным и независимым от приложения способом, который позволяет нам называть или, по крайней мере, нумеровать их по отдельности. [8] Эти имена обеспечивают удобное сокращение для булевых операций. Имена n -арных операций являются двоичными числами из 2 n бит. Поскольку таких операций 2 2 n , нельзя и мечтать о более краткой номенклатуре. Обратите внимание, что каждую финитную операцию можно назвать функцией переключения .
Эта схема и связанное с ней наименование операций проиллюстрированы здесь полностью для арностей от 0 до 2.
Эти таблицы продолжаются на более высоких арностях, с 2 n строками на арности n , каждая строка дает оценку или связывание n переменных x 0 ,... x n −1 и каждый столбец, озаглавленный n f i , дает значение n f i ( x 0 ,..., x n −1 ) i -й n -арной операции при этой оценке. Операции включают переменные, например 1 f 2 есть x 0 , в то время как 2 f 10 есть x 0 (как две копии своего унарного аналога) и 2 f 12 есть x 1 (без унарного аналога). Отрицание или дополнение ¬ x 0 появляется как 1 f 1 и снова как 2 f 5 , вместе с 2 f 3 ( ¬ x 1 , который не появился при арности 1), дизъюнкция или объединение x 0 ∨ x 1 как 2 f 14 , конъюнкция или пересечение x 0 ∧ x 1 как 2 f 8 , импликация x 0 → x 1 как 2 f 13 , исключающая или симметричная разность x 0 ⊕ x 1 как 2 f 6 , разность множеств x 0 − x 1 как 2 f 2 и так далее.
Как незначительная деталь, важная скорее для ее формы, чем для ее содержания, операции алгебры традиционно организованы в виде списка. Хотя мы здесь индексируем операции булевой алгебры по финитным операциям на {0,1}, представление таблицы истинности выше по счастливой случайности упорядочивает операции сначала по арности, а затем по расположению таблиц для каждой арности. Это позволяет организовать набор всех булевых операций в традиционном формате списка. Порядок списка для операций заданной арности определяется следующими двумя правилами.
При программировании на C или Java побитовая дизъюнкция обозначаетсях | у, соединениех и у, и отрицание~ х. Таким образом, программа может представить, например, операцию x ∧( y ∨ z ) в этих языках какх &( у | z ), предварительно установивх = 0xaa,у = 0xcc, иz = 0xf0("0x" указывает, что следующая константа должна быть прочитана в шестнадцатеричном формате или в системе счисления с основанием 16), либо путем назначения переменным, либо путем определения в виде макросов. Эти однобайтовые (восьмибитные) константы соответствуют столбцам для входных переменных в расширении приведенных выше таблиц до трех переменных. Этот метод почти повсеместно используется в растровом графическом оборудовании для предоставления гибкого разнообразия способов комбинирования и маскирования изображений, причем типичные операции являются троичными и действуют одновременно на исходные, целевые и маскирующие биты.
Пример 2. Все битовые векторы заданной длины образуют булеву алгебру «поточечно», что означает, что любая n -арная булева операция может быть применена к n битовым векторам по одной битовой позиции за раз. Например, троичное ИЛИ трех битовых векторов, каждый из которых имеет длину 4, является битовым вектором длины 4, образованным путем ИЛИ трех битов в каждой из четырех битовых позиций, таким образом, 0100∨1000∨1001 = 1101. Другим примером являются таблицы истинности выше для n -арных операций, столбцы которых являются всеми битовыми векторами длины 2 n и которые, следовательно, могут быть объединены поточечно, откуда n -арные операции образуют булеву алгебру. [9] Это работает одинаково хорошо для битовых векторов конечной и бесконечной длины, единственное правило состоит в том, что все битовые позиции должны быть индексированы одним и тем же набором, чтобы «соответствующая позиция» была хорошо определена.
Атомами такой алгебры являются битовые векторы , содержащие ровно одну 1. В общем случае атомами булевой алгебры являются такие элементы x , что x ∧ y имеет только два возможных значения: x или 0 .
Пример 3. Алгебра множеств степеней , множество 2 W всех подмножеств заданного множества W . [10] Это просто замаскированный пример 2, где W служит для индексации позиций битов. Любое подмножество X из W можно рассматривать как битовый вектор, имеющий 1 только в тех позициях битов, которые индексированы элементами X . Таким образом, вектор из всех нулей является пустым подмножеством W , в то время как вектор из всех единиц является самим W , которые являются константами 0 и 1 соответственно алгебры множеств степеней. Аналогом дизъюнкции x ∨ y является объединение X ∪ Y , в то время как аналогом конъюнкции x ∧ y является пересечение X ∩ Y . Отрицание ¬ x становится ~ X , дополнением относительно W . Существует также разность множеств X \ Y = X ∩~ Y , симметричная разность ( X \ Y )∪( Y \ X ) , тернарное объединение X ∪ Y ∪ Z и т. д. Атомы здесь — это синглтоны, те подмножества, которые содержат ровно один элемент.
Примеры 2 и 3 являются частными случаями общей конструкции алгебры, называемой прямым произведением , применимой не только к булевым алгебрам, но и ко всем видам алгебр, включая группы, кольца и т. д. Прямое произведение любого семейства B i булевых алгебр, где i пробегает некоторое множество индексов I (не обязательно конечное или даже счетное), является булевой алгеброй, состоящей из всех I -кортежей (... x i ,...), i -й элемент которых взят из B i . Операции прямого произведения являются соответствующими операциями составляющих алгебр, действующими в их соответствующих координатах; в частности, операция n f j произведения действует на n I -кортежей, применяя операцию n f j из B i к n элементам в i -й координате n кортежей, для всех i из I .
Когда все алгебры, умножаемые таким образом, являются одной и той же алгеброй A, мы называем прямое произведение прямой степенью A. Булева алгебра всех 32-битных битовых векторов — это двухэлементная булева алгебра, возведенная в 32-ю степень, или алгебра степенных множеств 32-элементного множества, обозначаемая 2 32 . Булева алгебра всех множеств целых чисел — это 2 Z . Все булевы алгебры, которые мы продемонстрировали до сих пор, были прямыми степенями двухэлементной булевой алгебры, что оправдывает название «алгебра степенных множеств».
Можно показать, что каждая конечная булева алгебра изоморфна некоторой алгебре степенных множеств. [11] Следовательно, мощность (количество элементов) конечной булевой алгебры равна степени 2 , а именно одной из 1,2,4,8,...,2 n ,... Это называется теоремой о представлении , поскольку она дает представление о природе конечных булевых алгебр, давая их представление как алгебр степенных множеств.
Эта теорема о представлении не распространяется на бесконечные булевы алгебры: хотя каждая алгебра степенных множеств является булевой алгеброй, не каждая булева алгебра должна быть изоморфна алгебре степенных множеств. В частности, в то время как не может быть счетно бесконечных алгебр степенных множеств (наименьшая бесконечная алгебра степенных множеств — это алгебра степенных множеств 2 N множеств натуральных чисел, которая, как показал Кантор , несчетна ) , существуют различные счетно бесконечные булевы алгебры.
Чтобы выйти за рамки алгебр степенных множеств, нам нужна другая конструкция. Подалгебра алгебры A — это любое подмножество A, замкнутое относительно операций A. Каждая подалгебра булевой алгебры A должна по-прежнему удовлетворять уравнениям, выполняющимся для A , поскольку любое нарушение будет представлять собой нарушение для самой A. Следовательно, каждая подалгебра булевой алгебры является булевой алгеброй. [12]
Подалгебра алгебры степенных множеств называется полем множеств ; эквивалентно, поле множеств — это множество подмножеств некоторого множества W, включающее пустое множество и W и замкнутое относительно конечного объединения и дополнения относительно W (и, следовательно, также относительно конечного пересечения). Теорема Биркгофа [1935] о представлении для булевых алгебр утверждает, что каждая булева алгебра изоморфна полю множеств. Теперь теорему Биркгофа HSP для многообразий можно сформулировать так: каждый класс моделей эквациональной теории класса C алгебр является гомоморфным образом подалгебры прямого произведения алгебр из C. Обычно требуются все три из H, S и P; первая из этих двух теорем Биркгофа показывает, что для особого случая многообразия булевых алгебр гомоморфизм можно заменить изоморфизмом . Таким образом, теорема Биркгофа HSP для многообразий в целом становится теоремой Биркгофа ISP для многообразия булевых алгебр.
При обсуждении множества X натуральных чисел удобно рассматривать его как последовательность x 0 , x 1 , x 2 ,... битов, где x i = 1 тогда и только тогда, когда i ∈ X . Эта точка зрения облегчит обсуждение подалгебр алгебры степенных множеств 2 N , которую эта точка зрения делает булевой алгеброй всех последовательностей битов. [13] Она также хорошо согласуется со столбцами таблицы истинности: когда столбец читается сверху вниз, он представляет собой последовательность битов, но в то же время его можно рассматривать как набор тех оценок (назначений переменным в левой половине таблицы), при которых функция, представленная этим столбцом, оценивается как 1.
Пример 4. Последовательности с конечными константами . Любая булева комбинация последовательностей с конечными константами является конечным константой; следовательно, они образуют булеву алгебру. Мы можем идентифицировать их с целыми числами, рассматривая последовательности с конечными нулевыми числами как неотрицательные двоичные числа (бит 0 последовательности является младшим битом), а последовательности с конечными единицами как отрицательные двоичные числа (представьте себе арифметику с дополнительным кодом до двух , в которой последовательность из всех единиц равна −1 ). Это делает целые числа булевой алгеброй, в которой объединение является побитовым ИЛИ, а дополнение равно −x−1 . Существует только счетное количество целых чисел, поэтому эта бесконечная булева алгебра счетна. Атомы являются степенями двойки, а именно 1, 2, 4, .... Другой способ описания этой алгебры — как множества всех конечных и коконечных множеств натуральных чисел, при этом последовательности, состоящие в конечном счете из всех единиц, соответствуют коконечным множествам, причем эти множества исключают лишь конечное число натуральных чисел.
Пример 5. Периодическая последовательность . Последовательность называется периодической , когда существует некоторое число n > 0 , называемое свидетелем периодичности, такое, что x i = x i + n для всех i ≥ 0. Период периодической последовательности является ее наименьшим свидетелем. Отрицание оставляет период неизменным, в то время как дизъюнкция двух периодических последовательностей является периодической, причем период не превышает наименьшего общего кратного периодов двух аргументов (период может быть таким же малым, как 1 , как это происходит с объединением любой последовательности и ее дополнения). Следовательно, периодические последовательности образуют булеву алгебру.
Пример 5 похож на пример 4 тем, что он счетный, но отличается тем, что он безатомный. Последнее связано с тем, что конъюнкция любой ненулевой периодической последовательности x с последовательностью взаимно простого периода (больше 1) не равна ни 0 , ни x . Можно показать, что все счетно бесконечные безатомные булевы алгебры изоморфны, то есть с точностью до изоморфизма существует только одна такая алгебра.
Пример 6. Периодическая последовательность с периодом, равным степени двойки . Это собственная подалгебра из Примера 5 (собственная подалгебра равна пересечению себя со своей алгеброй). Их можно понимать как финитные операции, причем первый период такой последовательности дает таблицу истинности операции, которую она представляет. Например, таблица истинности x 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 .
Практическое значение этого соглашения как для программного обеспечения, так и для оборудования заключается в том, что n -арные булевы операции могут быть представлены в виде слов соответствующей длины. Например, каждая из 256 тернарных булевых операций может быть представлена в виде беззнакового байта. Доступные логические операции, такие как AND и OR, затем могут использоваться для формирования новых операций. Если мы возьмем x , y и z (пока что обходясь без индексных переменных) равными 10101010 , 11001100 и 11110000 соответственно (170, 204 и 240 в десятичной системе, 0xaa , 0xcc и 0xf0 в шестнадцатеричной), то их попарные конъюнкции будут x ∧ y = 10001000 , y ∧ z = 11000000 и z ∧ x = 10100000 , тогда как их попарные дизъюнкции будут x ∨ y = 11101110 , y ∨ z = 11111100 и z ∨ x = 11111010 . Дизъюнкция трех конъюнкций — это 11101000 , которая также является конъюнкцией трех дизъюнкций. Таким образом, мы вычислили, с дюжиной или около того логических операций над байтами, что две тернарные операции
и
на самом деле это одна и та же операция. То есть, мы доказали эквациональное тождество
для двухэлементной булевой алгебры. По определению «булевой алгебры» это тождество должно поэтому выполняться в каждой булевой алгебре.
Эта тернарная операция, между прочим, легла в основу тернарных булевых алгебр Грау [1947], которые он аксиоматизировал в терминах этой операции и отрицания. Операция симметрична, что означает, что ее значение не зависит от любой из 3! = 6 перестановок ее аргументов. Две половины ее таблицы истинности 11101000 являются таблицами истинности для ∨ , 1110 , и ∧ , 1000 , поэтому операцию можно сформулировать так: if z then x ∨ y else x ∧ y . Поскольку она симметрична, ее можно с равным успехом сформулировать как if x then y ∨ z else y ∧ z , или if y then z ∨ x else z ∧ x . Если рассматривать его как маркировку 8-вершинного 3-куба, то верхняя половина помечена 1, а нижняя — 0; по этой причине он был назван оператором медианы , с очевидным обобщением на любое нечетное число переменных (нечетное — для того, чтобы избежать ничьей, когда ровно половина переменных равна 0).
Метод, который мы только что использовали для доказательства тождества булевой алгебры, может быть обобщен на все тождества систематическим образом, который может быть принят как надежная и полная аксиоматизация или аксиоматическая система для эквациональных законов булевой логики . Обычная формулировка системы аксиом состоит из набора аксиом, которые «заправляют насос» некоторыми начальными тождествами, вместе с набором правил вывода для вывода оставшихся тождеств из аксиом и ранее доказанных тождеств. В принципе желательно иметь конечное число аксиом; однако с практической точки зрения это не обязательно, поскольку столь же эффективно иметь конечную схему аксиом, имеющую бесконечное число примеров, каждый из которых при использовании в доказательстве может быть легко проверен как законный пример, подход, которому мы следуем здесь.
Булевы тождества — это утверждения вида s = t , где s и t — n -арные термы, под которыми мы будем понимать здесь термы, переменные которых ограничены значениями x 0 через x n-1 . N -арный терм — это либо атом, либо приложение. Приложение m f i ( t 0 ,..., t m -1 ) — это пара, состоящая из m -арной операции m f i и списка или m -кортежа ( t 0 ,..., t m -1 ) m n -арных термов , называемых операндами .
С каждым термином связано натуральное число, называемое его высотой . Атомы имеют нулевую высоту, в то время как приложения имеют высоту, равную единице плюс высота их наивысшего операнда.
Теперь, что такое атом? Традиционно атом - это либо константа (0 или 1), либо переменная x i , где 0 ≤ i < n . Для техники доказательства здесь удобно определить атомы как n -арные операции n f i , которые, хотя и рассматриваются здесь как атомы, тем не менее означают то же самое, что и обычные термины точной формы n f i ( x 0 ,..., x n -1 ) (точной в том смысле, что переменные должны быть перечислены в указанном порядке без повторений или пропусков). Это не является ограничением, поскольку атомы этой формы включают в себя все обычные атомы, а именно константы 0 и 1, которые возникают здесь как n -арные операции n f 0 и n f −1 для каждого n (сокращение 2 2 n −1 до −1 ), и переменные x 0 ,..., x n -1 , как можно видеть из таблиц истинности, где x 0 появляется как унарная операция 1 f 2 и бинарная операция 2 f 10 , тогда как x 1 появляется как 2 f 12 .
Следующая схема аксиом и три правила вывода аксиоматизируют булеву алгебру 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 , выражает знакомую аксиому ¬¬ x = x двойного отрицания. Правило R3 позволяет нам вывести ¬¬¬ x = ¬ x, принимая s 0 равным 1 f 1 ( 1 f 1 ) или ¬¬ x 0 , t 0 равным 1 f 2 или x 0 , а m f i равным 1 f 1 или ¬ .
Для каждого m и n существует только конечное число аксиом, описывающих A1 , а именно 2 2 m × (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 → n , а m n как приложение m ( n ) , мы можем переосмыслить числа i , j , ĵ и i o ĵ как функции типа i : ( m →2)→2 , j : m →(( n →2)→2) , ĵ : ( n →2)→( m →2) и i o ĵ : ( n →2)→2 . Определение ( i o ĵ ) v = i ĵ v в A1 тогда переводится в ( i o ĵ )( v ) = i ( ĵ ( v )) , то есть i o ĵ определяется как композиция i и ĵ, понимаемых как функции. Итак, содержание A1 сводится к определению термина применения как по сути композиции, по модулю необходимости транспонировать m -кортеж j, чтобы типы соответствовали друг другу для композиции. Эта композиция находится в ранее упомянутой Ловером категории степенных множеств и их функций. Таким образом, мы перевели коммутирующие диаграммы этой категории, как эквациональную теорию булевых алгебр, в эквациональные следствия A1 как логическое представление этого конкретного закона композиции.
В основе каждой булевой алгебры B лежит частично упорядоченное множество или частично упорядоченное множество ( B ,≤) . Отношение частичного порядка определяется соотношением x ≤ y только тогда, когда x = x ∧ y , или, что эквивалентно, когда y = x ∨ y . Для заданного множества X элементов булевой алгебры верхняя граница X — это элемент y такой, что для каждого элемента x из X , x ≤ y , в то время как нижняя граница X — это элемент y такой, что для каждого элемента x из X , y ≤ x .
Sup X — это наименьшая верхняя граница на X , а именно, верхняя граница на X , которая меньше или равна любой верхней границе на X . Двойственно, inf X — это наибольшая нижняя граница на X . Sup x и y всегда существует в базовом частично упорядоченном множестве булевой алгебры , будучи x ∨ y , и аналогично существует их inf, а именно x ∧ y . Пустой sup равен 0 (нижний элемент), а пустой inf равен 1 (верхний). Из этого следует, что каждое конечное множество имеет как sup, так и inf. Бесконечные подмножества булевой алгебры могут иметь или не иметь sup и/или inf; в алгебре степенных множеств они всегда есть.
Любой посет ( B ,≤) такой, что каждая пара x , y элементов имеет как sup , так и inf , называется решеткой . Мы пишем x ∨ y для sup и x ∧ y для inf . Базовый посет булевой алгебры всегда образует решетку. Решетка называется дистрибутивной , когда x ∧( y ∨ z ) = ( x ∧ y )∨( x ∧ z ) , или, что эквивалентно, когда x ∨( y ∧ z ) = ( x ∨ y )∧( x ∨ z ) , поскольку любой закон влечет другой в решетке. Это законы булевой алгебры, откуда базовый посет булевой алгебры образует дистрибутивную решетку.
Если задана решетка с нижним элементом 0 и верхним элементом 1, то пара элементов x , y называется дополнительной, когда x ∧ y = 0 и x ∨ y = 1 , и тогда мы говорим, что y является дополнением x и наоборот. Любой элемент x дистрибутивной решетки с верхом и низом может иметь не более одного дополнения. Когда каждый элемент решетки имеет дополнение, решетка называется дополняемой. Из этого следует, что в дополняемой дистрибутивной решетке дополнение элемента всегда существует и является уникальным, что делает дополнение унарной операцией. Более того, каждая дополняемая дистрибутивная решетка образует булеву алгебру, и наоборот, каждая булева алгебра образует дополняемую дистрибутивную решетку. Это дает альтернативное определение булевой алгебры, а именно как любой дополняемой дистрибутивной решетки. Каждое из этих трех свойств может быть аксиоматизировано конечным числом уравнений, откуда эти уравнения, взятые вместе, составляют конечную аксиоматизацию эквациональной теории булевых алгебр.
В классе алгебр, определяемом как все модели набора уравнений, обычно бывает так, что некоторые алгебры класса удовлетворяют большему количеству уравнений, чем просто те, которые необходимы для квалификации их для класса. Класс булевых алгебр необычен тем, что, за одним исключением, каждая булева алгебра удовлетворяет только булевым тождествам и не более. Исключением является одноэлементная булева алгебра, которая обязательно удовлетворяет каждому уравнению, даже x = y , и поэтому иногда называется несовместимой булевой алгеброй.
Булев гомоморфизм — это функция h : A → B между булевыми алгебрами A , B такая, что для каждой булевой операции m f i :
Категория 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 различной мощности .) Такая алгебра может быть эквивалентно определена как полная булева алгебра, которая является атомной , что означает, что каждый элемент является sup некоторого множества атомов. Свободные CABA существуют для всех мощностей множества V генераторов , а именно алгебры степенных множеств 2 2 V , что является очевидным обобщением конечных свободных булевых алгебр. Это аккуратно спасает бесконечную булеву логику от судьбы, которую, казалось, предназначал ей результат Гайфмана–Хейлза .
Отсутствие свободных полных булевых алгебр можно проследить до неспособности расширить уравнения булевой логики соответствующим образом на все законы, которые должны выполняться для бесконечной конъюнкции и дизъюнкции, в частности, до игнорирования дистрибутивности в определении полной булевой алгебры. Полная булева алгебра называется полностью дистрибутивной , когда произвольные конъюнкции распределяются по произвольным дизъюнкциям и наоборот. Булева алгебра является CABA тогда и только тогда, когда она является полной и полностью дистрибутивной, что дает третье определение CABA. Четвертое определение — как любая булева алгебра, изоморфная алгебре степенных множеств.
Полный гомоморфизм — это тот, который сохраняет все существующие sups, а не только конечные sups, и то же самое для infs. Категория CABA всех CABA и их полных гомоморфизмов является двойственной к категории множеств и их функций, что означает, что она эквивалентна противоположности этой категории (категории, полученной в результате обращения всех морфизмов). Все не так просто для категории Bool булевых алгебр и их гомоморфизмов, которые Маршалл Стоун показал на деле (хотя у него не было ни языка, ни концептуальной основы, чтобы сделать двойственность явной), что является двойственной к категории полностью несвязных компактных хаусдорфовых пространств , впоследствии названных пространствами Стоуна .
Другим бесконечным классом, промежуточным между булевыми алгебрами и полными булевыми алгебрами, является понятие сигма-алгебры . Оно определяется аналогично полным булевым алгебрам, но с sups и infs, ограниченными счетной арностью. То есть сигма-алгебра — это булева алгебра со всеми счетными sups и infs. Поскольку sups и infs имеют ограниченную мощность , в отличие от ситуации с полными булевыми алгебрами , результат Гайфмана-Хейлза не применим, и свободные сигма-алгебры существуют. Однако, в отличие от ситуации с CABA, свободная счетно порожденная сигма-алгебра не является алгеброй степенных множеств.
Мы уже встречали несколько определений булевой алгебры, как модели эквациональной теории двухэлементной алгебры, как дополненной дистрибутивной решетки, как булевого кольца и как сохраняющего произведение функтора из определенной категории (Lawvere). Еще два определения, которые стоит упомянуть:
(Цикличность в этом определении можно устранить, заменив «конечную булеву алгебру» на «конечное множество степеней», снабженное булевыми операциями, стандартно интерпретируемыми для множеств степеней.)
Чтобы представить это в перспективе, бесконечные множества возникают как отфильтрованные копределы конечных множеств, бесконечные CABA как отфильтрованные пределы алгебр конечных множеств, а бесконечные пространства Стоуна как отфильтрованные пределы конечных множеств. Таким образом, если начать с конечных множеств и спросить, как они обобщаются на бесконечные объекты, есть два способа: «добавление» их дает обычные или индуктивные множества, в то время как «умножение» их дает пространства Стоуна или проконечные множества . Тот же выбор существует для алгебр конечных множеств как двойственных конечных множеств: сложение дает булевы алгебры как индуктивные объекты, в то время как умножение дает CABA или алгебры множеств как проконечные объекты.
Характерной отличительной чертой является то, что базовая топология объектов, построенных таким образом, когда они определены как Хаусдорфовы , является дискретной для индуктивных объектов и компактной для проконечных объектов. Топология конечных хаусдорфовых пространств всегда является как дискретной, так и компактной, тогда как для бесконечных пространств «дискретный» и «компактный» являются взаимоисключающими. Таким образом, при обобщении конечных алгебр (любого вида, не только булевых) до бесконечных, «дискретный» и «компактный» разделяются, и нужно выбрать, какой из них сохранить. Общее правило, как для конечных, так и для бесконечных алгебр, заключается в том, что финитные алгебры являются дискретными, тогда как их двойственные алгебры являются компактными и имеют бесконечные операции. Между этими двумя крайностями существует множество промежуточных бесконечных булевых алгебр, топология которых не является ни дискретной, ни компактной.
