Войти
Булева алгебра - это математически богатая ветвь абстрактной алгебры. Так же, как теория групп имеет дело с группами, а линейная алгебра с векторными пространствами, булевы алгебры являются моделями эквациональная теория двух значений 0 и 1 (интерпретация которых не обязательно должна быть числовой). Общим для булевых алгебр, групп и векторных пространств является понятие алгебраической структуры, множества, закрытого нулем или более операций, удовлетворяющих определенным уравнениям.
Так же, как есть основные примеры групп, такие как группа Z из целых чисел и группа перестановок Snиз перестановок из n объектов, есть также базовые примеры булевой алгебры, такие как следующие.
Булева алгебра, таким образом, позволяет применять методы абстрактной алгебры к математической логике, цифровой логике и теоретико-множественные основы математики.
В отличие от групп конечного порядка, которые демонстрируют сложность и разнообразие и первого порядка теория разрешима только в особых случаях, все конечные булевы алгебры разделяют одни и те же теоремы и имеют разрешимую теорию первого порядка. Вместо этого сложности булевой алгебры разделены между структурой бесконечных алгебр и алгоритмической сложностью их синтаксической структуры.
Булева алгебра рассматривает эквациональную теорию максимальной двухэлементной конечной алгебры, называемой булевым прототипом, и модели этой теории, называемые булевыми алгебрами . Эти термины определены следующим образом.
алгебра - это семейство операций над набором, называемое базовым набором алгебры. Мы берем базовый набор логического прототипа равным {0,1}.
Алгебра является конечной, когда каждая из ее операций принимает только конечное число аргументов. Для прототипа каждый аргумент операции равен 0 или 1, как и результат операции. Максимальная такая алгебра состоит из всех финитарных операций на {0,1}.
Количество аргументов, принимаемых каждой операцией, называется арностью операции. Операция над {0,1} арности n или n-арная операция может применяться к любому из 2 возможных значений ее n аргументов. Для каждого выбора аргументов операция может возвращать 0 или 1, следовательно, есть 2 n-арные операции.
Таким образом, прототип имеет две операции без аргументов, называемые нулевыми или нулевыми операциями, а именно ноль и единица. Он имеет четыре унарные операции , две из которых являются постоянными операциями, другая - идентичностью, а наиболее часто используемая операция, называемая отрицанием, возвращает противоположность своему аргументу: 1, если 0, 0, если 1. Оно имеет шестнадцать двоичных операций ; снова два из них являются постоянными, другой возвращает свой первый аргумент, еще один возвращает свой второй, один называется конъюнкцией и возвращает 1, если оба аргумента равны 1, а в противном случае 0, другой называется дизъюнкцией и возвращает 0, если оба аргумента равны 0, а в противном случае - 1, и так далее. Количество (n + 1) -арных операций в прототипе является квадратом количества n-мерных операций, поэтому имеется 16 = 256 тернарных операций, 256 = 65 536 четвертичных операций и так далее.
A семейство индексируется набором индексов . В случае семейства операций, образующих алгебру, индексы называются символами операций, составляя язык этой алгебры. Операция, индексируемая каждым символом, называется обозначением или интерпретацией этого символа. Каждый символ операции указывает арность его интерпретации, поэтому все возможные интерпретации символа имеют одинаковую арность. В общем, алгебра может интерпретировать разные символы с помощью одной и той же операции, но это не относится к прототипу, символы которого находятся в однозначном соответствии с его операциями. Таким образом, прототип имеет 2 n-арных символа операций, называемых символами логических операций и образующих язык булевой алгебры. Лишь некоторые операции имеют обычные символы, такие как ¬ для отрицания, ∧ для соединения и ∨ для дизъюнкции. Удобно рассматривать i-й n-арный символ как f i, как это сделано ниже в разделе таблицы истинности.
эквациональной теории в данном язык состоит из уравнений между терминами, составленными из переменных с использованием символов этого языка. Типичные уравнения на языке булевой алгебры: x∧y = y∧x, x∧x = x, x∧¬x = y∧¬y и x∧y = x.
Алгебра удовлетворяет уравнению, когда уравнение выполняется для всех возможных значений его переменных в этой алгебре, когда символы операций интерпретируются, как указано в этой алгебре. Законы булевой алгебры - это уравнения на языке булевой алгебры, которым удовлетворяет прототип. Первые три из приведенных выше примеров являются булевыми законами, но не четвертым, поскольку 1∧0 ≠ 1.
эквациональная теория алгебры - это совокупность всех уравнений, которым удовлетворяет алгебра. Следовательно, законы булевой алгебры составляют эквациональную теорию булевого прототипа.
A модель теории - это алгебра, интерпретирующая символы операций на языке теории и удовлетворяющая уравнениям теории.
То есть, булева алгебра - это набор и семейство операций над ними, интерпретирующие символы булевых операций и удовлетворяющие тем же законам, что и булев прототип.
Если мы определяем гомолог алгебры как модель эквациональной теории этой алгебры, то булеву алгебру можно определить как любой гомолог прототипа.
Пример 1 . Логический прототип - это булева алгебра, поскольку она тривиально удовлетворяет своим собственным законам. Таким образом, это прототипическая булева алгебра. Первоначально мы не называли это так, чтобы избежать появления округлости в определении.
Нет необходимости указывать все операции явно. Базис - это любой набор, из которого можно получить остальные операции путем композиции. «Булева алгебра» может быть определена на основе любого из нескольких различных оснований. Обычно используются три базиса булевой алгебры: базис решетки, базис кольца и базис штрих Шеффера или базис И-НЕ. Эти основы придают субъекту соответственно логический, арифметический и экономный характер.
Общими элементами решетки и оснований кольца являются константы 0 и 1, а также ассоциативный коммутативный двоичная операция, называемая , соответствует x∧y в базисе решетки, и умножению xy в базисе кольца. Различие только терминологическое. Базис решетки имеет дальнейшие операции соединения, x∨y и дополнения, ¬x. Вместо этого кольцевой базис имеет арифметическую операцию x⊕y сложения (символ ⊕ используется вместо +, поскольку последнему иногда дается логическое чтение соединения).
Быть базисом - значит давать все остальные операции по композиции, поэтому любые две базы должны быть взаимопереводимыми. Базис решетки переводит x∨y в базис кольца как x⊕y⊕xy, а ¬x как x⊕1. Наоборот, базис кольца переводит x⊕y в базис решетки как (x∨y) ∧¬ (x∧y).
Обе эти базы позволяют определять булевы алгебры через подмножество эквациональных свойств булевых операций. Для базиса решетки достаточно определить булеву алгебру как дистрибутивную решетку, удовлетворяющую x∧¬x = 0 и x∨¬x = 1, называемую дополняемой дистрибутивной решеткой. Базис кольца превращает булеву алгебру в булево кольцо, а именно в кольцо, удовлетворяющее x = x.
Эмиль Пост дал необходимое и достаточное условие для того, чтобы набор операций был основой для ненулевых булевых операций. Нетривиальное свойство - это свойство, которое разделяют некоторые, но не все операции, составляющие основу. Пост перечислил пять нетривиальных свойств операций, идентифицируемых с пятью классами Поста, каждый из которых сохраняется составом, и показал, что набор операций формирует основу, если для каждого свойства набор содержит операцию, не имеющую этого свойства.. (Обратное к теореме Поста, расширяющее «если» до «тогда и только тогда, когда », является простым наблюдением, что свойство из этих пяти, удерживающее каждую операцию в кандидатном базисе, также будет выполняться для каждой операции формируется композицией из этого кандидата, поэтому из-за нетривиальности этого свойства кандидат не может быть основой.) Пять свойств Post:
И-НЕ (двойное ИЛИ НИ) операции всего этого не хватает, поэтому она сама составляет основу.
Конечные операции над {0,1} могут быть представлены как таблицы истинности, при этом 0 и 1 рассматриваются как значения истинности ложь и истина . Они могут быть размещены единообразно и независимо от приложений, что позволяет нам давать им имена или, по крайней мере, нумеровать их по отдельности. Эти имена представляют собой удобное сокращение для логических операций. Имена n-арных операций представляют собой двоичные числа по 2 бита. Таких операций 2, более емкой номенклатуры и не придумать. Обратите внимание, что каждая конечная операция может называться функцией переключения.
Этот макет и связанное с ним наименование операций полностью проиллюстрированы здесь для арностей от 0 до 2.
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Эти таблицы продолжаются с более высокой арностью, с двумя строками с арностью n, каждая строка дает оценку или привязку n переменных x 0,... x n-1 и каждый столбец, озаглавленный f i, дающий значение f i(x0,..., x n-1) i-го n-арная операция при такой оценке. Операции включают переменные, например, f 2 - это x 0, а f 10 - x 0 (как две копии его унарного аналог), а f 12 равно x 1 (без унарного аналога). Отрицание или дополнение ¬x 0 отображается как f 1 и снова как f 5 вместе с f 3 (¬x 1, который не появился в арности 1), дизъюнкция или объединение x 0∨x1как f 14, соединение или пересечение x 0∧x1как f 8, импликация x 0→x1как f 13, исключительная или симметричная разность x 0⊕x1как f 6, установить разность x 0−x1как f 2, и так на.
Как второстепенная деталь, важная больше для формы, чем содержания, операции алгебры традиционно организованы в виде списка. Хотя здесь мы индексируем операции булевой алгебры с помощью финитарных операций над {0,1}, приведенное выше представление таблицы истинности случайно упорядочивает операции сначала по арности, а во вторую - по компоновке таблиц для каждой арности. Это позволяет организовать набор всех логических операций в традиционном формате списка. Порядок в списке для операций данной арности определяется следующими двумя правилами.
При программировании на C или Java побитовая дизъюнкция обозначается x | y, соединение x yи отрицание ~ x. Таким образом, программа может представить, например, операцию x∧ (y∨z) на этих языках как x (y | z), предварительно установив x = 0xaa, y = 0xccи z = 0xf0(«0x» указывает, что следующая константа должна считываться в шестнадцатеричном формате или с основанием 16) либо путем присвоения переменным, либо путем определения как макросы. Эти однобайтовые (восьмибитные) константы соответствуют столбцам для входных переменных в расширении приведенных выше таблиц до трех переменных. Этот метод почти повсеместно используется в оборудовании для растровой графики для обеспечения гибкого разнообразия способов комбинирования и маскирования изображений, при этом типичные операции являются троичными и действуют одновременно с битами источника, назначения и маски.
Пример 2 . Все битовые векторы заданной длины образуют булеву алгебру «поточечно», что означает, что любая n-арная логическая операция может применяться к n битовым векторам по одной битовой позиции за раз. Например, троичное ИЛИ трех битовых векторов длиной 4 каждый является битовым вектором длины 4, образованным путем упорядочивания трех битов в каждой из четырех битовых позиций, таким образом, 0100∨1000∨1001 = 1101. Другой пример - таблицы истинности выше для n-арных операций, столбцы которых являются все битовыми векторами длины 2 и которые, следовательно, могут быть объединены поточечно, откуда n-арные операции образуют булеву алгебру. Это одинаково хорошо работает для битовых векторов конечной и бесконечной длины, единственное правило состоит в том, что все позиции битов должны индексироваться одним и тем же набором, чтобы "соответствующая позиция" была четко определена.
атомы такой алгебры - это битовые векторы, содержащие ровно одну единицу. Обычно атомами булевой алгебры являются такие элементы x, что x∧y имеет только два возможных значения: x или 0.
Пример 3 . Алгебра набора мощности, набор 2 всех подмножеств данного набора W. Это всего лишь замаскированный пример 2, где W служит для индексации позиций битов. Любое подмножество X из W можно рассматривать как битовый вектор, имеющий единицы только в тех битовых позициях, проиндексированных элементами X. Таким образом, вектор с нулевыми значениями является пустым подмножеством W, в то время как вектор всех единиц - это сам W, которые являются константы 0 и 1 соответственно алгебры степенных множеств. Аналог дизъюнкции x∨y - объединение X∪Y, а конъюнкции x∧y - пересечение X∩Y. Отрицание ¬x превращается в ~ X, дополнение относительно W. Также существует разность множеств X ∖ Y = X∩ ~ Y, симметричная разность (X ∖ Y) ∪ (Y ∖ X), троичное объединение X∪Y∪Z и т. на. Атомы здесь - синглтоны, те подмножества, которые содержат ровно один элемент.
Примеры 2 и 3 являются частными случаями общей конструкции алгебры, называемой прямым произведением, применимой не только к булевым алгебрам, но и ко всем видам алгебры, включая группы, кольца и т. Д. Прямое произведение любого семейства B i булевых алгебр, где i пробегает некоторый набор индексов I (не обязательно конечный или даже счетный), является булевой алгеброй, состоящей из всех I-кортежей (... x i,...), i-й элемент которого взят из B i. Операции прямого произведения - это соответствующие операции составляющих алгебр, действующих в пределах их соответствующих координат; в частности, операция f j продукта работает с n I-кортежами, применяя операцию f j of B i к n элементам в i-й координате наборов n для всех i в I.
Когда все алгебры, умножаемые таким образом, являются одной и той же алгеброй A, мы называем прямое произведение прямой степенью A. Булева алгебра всех 32- битовые битовые векторы - это двухэлементная булева алгебра, возведенная в 32-ю степень, или алгебра наборов степеней для 32-элементного набора, обозначаемого 2. Булева алгебра всех наборов целых чисел равна 2. Все булевы алгебры, которые мы показали до сих пор, имеют были прямыми степенями двухэлементной булевой алгебры, оправдывая название «алгебра степенных множеств».
Можно показать, что каждая конечная булева алгебра изоморфна некоторой алгебре степенных множеств. Следовательно, мощность (количество элементов) конечной булевой алгебры является степенью двойки, а именно одной из 1,2,4,8,..., 2,... Это называется теоремой о представлении, поскольку он дает представление о природе конечных булевых алгебр, предоставляя их представление как алгебры степенных множеств.
Эта теорема о представлении не распространяется на бесконечные булевы алгебры: хотя каждая алгебра множеств степеней является булевой алгеброй, не каждая булева алгебра должна быть изоморфна алгебре множеств степеней. В частности, в то время как не может быть счетно бесконечных алгебр множеств степеней (наименьшая бесконечная алгебра множеств степеней - это алгебра множеств степеней 2 наборов натуральных чисел, показано Кантором быть несчетным ), существуют различные счетно бесконечные булевы алгебры.
Чтобы выйти за рамки алгебр степенных множеств, нам нужна другая конструкция. Подалгебра алгебры A - это любое подмножество A, замкнутое относительно операций A. Каждая подалгебра булевой алгебры A должна по-прежнему удовлетворять уравнениям, справедливым для A, поскольку любое нарушение будет представлять собой нарушение для самой A. Следовательно, любая подалгебра булевой алгебры является булева алгеброй.
A подалгебра алгебры степенных множеств называется полем множеств ; эквивалентно, поле множеств - это множество подмножеств некоторого множества W, включая пустое множество и W, и замкнутых относительно конечного объединения и дополнения относительно W (и, следовательно, также относительно конечного пересечения). Теорема Биркгофа [1935] о представлении для булевых алгебр утверждает, что каждая булева алгебра изоморфна полю множеств. Теперь теорему Биркгофа о HSP для многообразий можно сформулировать следующим образом: каждый класс моделей эквациональной теории класса C алгебр является гомоморфным образом подалгебры прямой Произведение алгебр C. Обычно необходимы все три алгебры H, S и P; первая из этих двух теорем Биркгофа показывает, что для частного случая многообразия булевых алгебр гомоморфизм может быть заменен на изоморфизм. Теорема Биркгофа HSP для многообразий в общем становится теоремой Биркгофа ISP для многообразия булевых алгебр.
Когда речь идет о наборе X натуральных чисел, удобно рассматривать его как последовательность x 0,x1,x2,... битов с x i = 1 тогда и только тогда, когда i ∈ X. Эта точка зрения упростит разговор о подалгебрах алгебры степенных множеств 2, которые с этой точки зрения составляют булеву алгебру всех последовательностей битов. Он также хорошо сочетается со столбцами таблицы истинности: когда столбец читается сверху вниз, он представляет собой последовательность битов, но в то же время его можно рассматривать как набор этих оценок (присвоения переменным слева половина таблицы), в котором функция, представленная этим столбцом, оценивается как 1.
Пример 4 . В конечном итоге постоянные последовательности. Любая логическая комбинация предельно постоянных последовательностей в конечном итоге постоянна; следовательно, они образуют булеву алгебру. Мы можем идентифицировать их с целыми числами, рассматривая последовательности с конечным нулем как неотрицательные двоичные числа (бит 0 последовательности является младшим битом), а последовательности с конечной единицей как отрицательные двоичные числа (подумайте, дополнение до двух арифметика с последовательностью всех единиц, равной −1). Это делает целые числа булевой алгеброй, где объединение является побитовым ИЛИ, а дополнение - −x − 1. Целых чисел только счетное число, поэтому эта бесконечная булева алгебра счетна. Атомы являются степенями двойки, а именно 1,2,4,.... Другой способ описания этой алгебры - как совокупность всех конечных и кофинитных множеств натуральных чисел с последовательностями, в конечном счете состоящими из всех единиц, соответствующих кофинитным наборы, в которых опускается только конечное число натуральных чисел.
Пример 5 . Периодическая последовательность. Последовательность называется периодической, если существует некоторое число n>0, называемое свидетельством периодичности, такое, что x i = x i + n для всех i ≥ 0. Период периодическая последовательность - ее наименьший свидетель. Отрицание оставляет период неизменным, в то время как дизъюнкция двух периодических последовательностей является периодической, с периодом не более чем наименьшее общее кратное периодов двух аргументов (период может быть равен 1, как это происходит с объединением любой последовательности и ее дополнение). Следовательно, периодические последовательности образуют булеву алгебру.
Пример 5 похож на пример 4 в том, что он счетный, но отличается отсутствием атомов. Последнее связано с тем, что конъюнкция любой ненулевой периодической последовательности x с последовательностью большего периода не равна ни 0, ни x. Можно показать, что все счетные безатомные булевы алгебры изоморфны, т. Е. С точностью до изоморфизма существует только одна такая алгебра.
Пример 6 . Периодическая последовательность с периодом, равным степени двойки. Это собственная подалгебра из примера 5 (собственная подалгебра равна пересечению самой себя со своей алгеброй). Их можно понимать как конечные операции, причем первый период такой последовательности дает таблицу истинности операции, которую она представляет. Например, таблица истинности x 0 в таблице двоичных операций, а именно f 10, имеет период 2 (и поэтому ее можно распознать как использующую только первую переменную), даже если 12 бинарных операций имеют период 4. Когда период равен 2, операция зависит только от первых n переменных, то есть от того, в каком смысле операция является конечной. Этот пример также представляет собой счетную безатомную булеву алгебру. Следовательно, пример 5 изоморфен своей собственной подалгебре! Пример 6 и, следовательно, пример 5 составляют свободную булеву алгебру со счетным числом образующих, то есть булеву алгебру всех финитарных операций над счетно бесконечным набором образующих или переменных.
Пример 7 . В конечном итоге периодические последовательности, последовательности, которые становятся периодическими после начального конечного приступа беззакония. Они составляют собственное расширение Примера 5 (что означает, что Пример 5 является собственной подалгеброй Примера 7), а также Примера 4, поскольку постоянные последовательности периодичны с периодом один. Последовательности могут различаться в зависимости от того, когда они успокаиваются, но любой конечный набор последовательностей в конечном итоге установится не позднее, чем их член, который успокаивается наиболее медленно, поэтому в конечном итоге периодические последовательности закрываются при всех булевых операциях и, таким образом, образуют булеву алгебру. В этом примере используются те же атомы и коатомы, что и в примере 4, поэтому он не является безатомным и, следовательно, не изоморфен примеру 5/6. Однако она содержит бесконечную безатомную подалгебру, а именно пример 5, и поэтому не изоморфна примеру 4, каждая подалгебра которой должна быть булевой алгеброй конечных множеств и их дополнений и, следовательно, атомный. Этот пример изоморфен прямому продукту примеров 4 и 5, что дает другое его описание.
Пример 8 . прямое произведение периодической последовательности (пример 5) с любой конечной, но нетривиальной булевой алгеброй. (Тривиальная одноэлементная булева алгебра - это уникальная конечная безатомная булева алгебра.) Это похоже на пример 7 тем, что содержит как атомы, так и безатомную подалгебру, но отличается тем, что имеет только конечное число атомов. Пример 8 - это фактически бесконечное семейство примеров, по одному на каждое возможное конечное число атомов.
Эти примеры никоим образом не исчерпывают возможные булевы алгебры, даже счетные. В самом деле, существует несчетное количество неизоморфных счетных булевых алгебр, которые Юсси Кетонен [1978] полностью классифицировал в терминах инвариантов, представимых некоторыми наследственно счетными множествами.
Сами n-арные булевы операции составляют алгебру набора степеней 2, а именно, когда W принимается как набор из 2 оценок n входов. С точки зрения системы именования операций f i, где i в двоичном формате представляет собой столбец таблицы истинности, столбцы могут быть объединены с помощью логических операций любой степени для создания других столбцов, присутствующих в таблице. Таким образом, мы можем применить любую логическую операцию арности m к m логическим операциям арности n, чтобы получить логическую операцию арности n для любых m и n.
Практическое значение этого соглашения как для программного, так и для аппаратного обеспечения состоит в том, что n-арные логические операции могут быть представлены в виде слов соответствующей длины. Например, каждая из 256 тернарных логических операций может быть представлена как беззнаковый байт. Доступные логические операции, такие как И и ИЛИ, могут затем использоваться для создания новых операций. Если мы возьмем x, y и z (пока не будем использовать индексированные переменные) равными 10101010, 11001100 и 11110000 соответственно (170, 204 и 240 в десятичной форме, 0xaa, 0xcc и 0xf0 в шестнадцатеричной системе), их попарные соединения будут x∧y = 10001000, y∧z = 11000000 и z∧x = 10100000, а их попарные дизъюнкции равны x∨y = 11101110, y∨z = 11111100 и z∨x = 11111010. Дизъюнкция трех конъюнкций равна 11101000, который также является соединением трех дизъюнкций. Таким образом, мы вычислили с помощью дюжины или около того логических операций с байтами, что две тернарные операции
и
- фактически одна и та же операция. То есть мы доказали эквациональное тождество
для двухэлементной булевой алгебры. Следовательно, по определению «булева алгебры» это тождество должно выполняться в каждой булевой алгебре.
Эта тернарная операция случайно легла в основу тернарных булевых алгебр Грау [1947], которые он аксиоматизировал в терминах этой операции и отрицания. Операция симметрична, то есть ее значение не зависит от любого из 3! = 6 перестановок его аргументов. Две половины его таблицы истинности 11101000 являются таблицами истинности для ∨, 1110 и ∧, 1000, поэтому операцию можно сформулировать как ifz, затем x∨y else x∧y. Поскольку он симметричен, его можно также сформулировать как ifx, затем y∨z else y∧z, или ify затем z∨x else z∧x. Если рассматривать как разметку 8-вершинного 3-куба, верхняя половина помечена цифрой 1, а нижняя половина - 0; по этой причине он был назван медианным оператором с очевидным обобщением на любое нечетное количество переменных (нечетное, чтобы избежать связи, когда ровно половина переменных равна 0).
Техника, которую мы только что использовали для доказательства тождества булевой алгебры, может быть систематически обобщена на все тождества, что можно рассматривать как правильную и полную аксиоматизацию или аксиоматическая система для эквациональных законов булевой логики. Обычная формулировка системы аксиом состоит из набора аксиом, которые «заряжают насос» некоторыми начальными тождествами, а также набором правил вывода для вывода остальных тождеств из аксиом и ранее доказанных тождеств. В принципе желательно иметь конечное число аксиом; однако с практической точки зрения в этом нет необходимости, поскольку столь же эффективно иметь конечную схему аксиом, имеющую бесконечное количество экземпляров, каждый из которых при использовании в доказательстве может быть легко проверен как юридический, подход, которого мы придерживаемся здесь.
Булевы тождества - это утверждения формы s = t, где s и t - n-арные термины, под которыми мы будем понимать термины, переменные которых ограничены значениями от x 0 до x <45.>п-1. N-арный термин является либо атомом, либо приложением. Приложение f i(t0,..., t m-1) представляет собой пару, состоящую из m-арной операции f i и списка или m-кортежа (t 0,..., t m-1) m n-арных терминов, называемых операндами .
С каждым термином связано натуральное число, называемое его высотой . Атомы имеют нулевую высоту, в то время как приложения имеют высоту один плюс высота их самого высокого операнда.
Что такое атом? Обычно атом - это либо константа (0 или 1), либо переменная x i, где 0 ≤ i < n. For the proof technique here it is convenient to define atoms instead to be n-ary operations fi, которые, хотя и рассматриваются здесь как атомы, тем не менее означают то же, что и обычные термины точной формы f i(x0,..., x n-1) (точно в том, что переменные должны быть перечислены в указанном порядке без повторений или пропусков). Это не ограничение, потому что атомы этой формы включают в себя все обычные атомы, а именно константы 0 и 1, которые возникают здесь как n-арные операции f 0 и f −1 для каждого n (сокращенно от 2-1 до -1), а переменные x 0,..., x n-1, как видно из таблиц истинности, где x 0 отображается как унарная операция f 2 и двоичная операция f 10, тогда как x 1 отображается как f 12.
Следующая аксиома схема и три правила вывода аксиоматизируют булеву алгебру n-мерных терминов.
Значение побочного условия на A1 состоит в том, что i o ĵ равно это 2-битное число, v-й бит которого является ĵ v -м битом i, где диапазоны каждой величины равны u: m, v: 2, j u : 2 и ĵ v : 2. (Таким образом, j - это m-кортеж из 2-битных чисел, а ĵ в качестве транспонированного j представляет собой 2-кортеж из m-битных чисел. Следовательно, как j, так и ĵ содержат m2 битов.)
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, если записано как двухбитовое число). Результирующий пример, а именно f 1(f1) = f 2, выражает знакомую аксиому ¬¬x = x двойного отрицания. Правило R3 затем позволяет нам вывести ¬¬¬x = ¬x, взяв s 0 как f 1(f1) или ¬¬x 0, t 0 должно быть f 2 или x 0, а f i быть f 1 или ¬.
Для каждого m и n существует только конечное число аксиом, реализующих A1, а именно 2 × (2). Каждый экземпляр определяется 2 + m2 битами.
Мы рассматриваем R1 как правило вывода, хотя отсутствие предпосылок похоже на аксиому, потому что это правило, не зависящее от предметной области, наряду с R2 и R3 общий для всех аксиоматизаций по уравнениям, будь то группы, кольца или любое другое разнообразие. Единственная особенность булевых алгебр - это схема аксиом A1 . Таким образом, когда мы говорим о различных эквациональных теориях, мы можем отодвинуть правила в сторону, как независимые от конкретных теорий, и ограничить внимание аксиомами как единственной частью системы аксиом, характеризующей конкретную рассматриваемую эквациональную теорию.
Эта аксиоматизация завершена, что означает, что любой логический закон s = t доказуем в этой системе. Сначала индукцией по высоте s показано, что любой логический закон, для которого t является атомарным, доказуем, используя R1 для базового случая (поскольку разные атомы никогда не равны) и A1 и R3 для ступени индукции (приложения). Эта стратегия доказательства сводится к рекурсивной процедуре вычисления s для получения атома. Затем, чтобы доказать s = t в общем случае, когда t может быть приложением, используйте тот факт, что если s = t является тождеством, тогда s и t должны оценивать один и тот же атом, назовите его u. Итак, сначала докажите s = u и t = u, как указано выше, что есть, вычислить s и t, используя A1, R1и R3, а затем вызвать R2, чтобы вывести s = t.
В A1, если мы рассматриваем число n как тип функции m → n, а m n как приложение m (n), мы можем переинтерпретировать числа i, j, ĵ и i o ĵ как функции типа i: (m → 2) → 2, j: m → ((n → 2) → 2), ĵ: (n → 2) → (m → 2) и i o ĵ: (n → 2) → 2. Затем определение (i oĵ)v= i ĵvв A1 преобразуется в (i o ĵ) (v) = i (ĵ (v)), то есть i o ĵ определяется как композиция i и ĵ, понимаемых как функции. Таким образом, содержание A1 сводится к определению термина «приложение по существу как композиция», по модулю необходимости транспонировать m- кортеж j, чтобы типы соответствовали композиции. Эта композиция относится к ранее упомянутой Ловером категории степенных множеств и их функций. Таким образом, мы перевели коммутирующие диаграммы этой категории как эквациональную теорию булевых алгебр, в эквациональные последствия A1 как логического представления этого конкретного закона композиции.
В основе каждой булевой алгебры B лежит частично упорядоченное множество или poset (B, ≤). Отношение частичного порядка определяется как x ≤ y только тогда, когда x = x∧y, или, что эквивалентно, когда y = x∨y. Для набора X элементов логического алгебры, верхняя граница на X - это такой элемент y, что для каждого элемента x из X, x ≤ y, в то время как нижняя граница на X - это такой элемент y, что для каждого элемента x из X, y ≤ х.
A sup (supremum ) X - это наименьшая верхняя граница X, а именно верхняя граница X, которая меньше или равна каждой верхней границе X. Двойное значение inf (infimum ) X является точной нижней границей X. Sup x и y всегда существует в базовом множестве булевой алгебры, будучи x∨y, и аналогично существует их inf, а именно x∧y. Пустой sup равен 0 (нижний элемент), а пустой inf - 1 (верхний элемент). Отсюда следует, что каждое конечное множество имеет как sup, так и inf. Бесконечные подмножества булевой алгебры могут иметь или не иметь sup и / или inf; в алгебре степенных множеств они всегда так делают.
Любой элемент poset (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 такая, что для любой булевой операции 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, а именно power set алгебры 2, что является очевидным обобщением конечных свободных булевых алгебр. Это аккуратно спасает бесконечную булеву логику от той участи, которой, казалось, ее предал результат Гайфмана – Хейлза.
Отсутствие свободных полных булевых алгебр можно проследить до неспособности расширить уравнения булевой логики соответствующим образом на все законы, которые должны выполняться для бесконечного соединения и дизъюнкции, в частности, пренебрежение дистрибутивностью в определении полной булевой алгебры. Полная булева алгебра называется полностью дистрибутивной, когда произвольные конъюнкции распределяются по произвольным дизъюнкциям и наоборот. Булева алгебра является CABA тогда и только тогда, когда она является полной и полностью дистрибутивной, что дает третье определение CABA. Четвертое определение - это как любая булева алгебра, изоморфная алгебре степенных множеств.
Полный гомоморфизм - это гомоморфизм, который сохраняет все существующие супы, а не только конечные суппорты, и то же самое для infs. Категория CABA всех CABA и их полных гомоморфизмов двойственна категории множеств и их функций, что означает, что она эквивалентна противоположности этой категории (категории, полученной в результате обращения всех морфизмов). Не все так просто для категории Bool булевых алгебр и их гомоморфизмов, которые Маршалл Стоун продемонстрировал на практике (хотя ему не хватало как языка, так и концептуальной основы, чтобы сделать двойственность явной.) быть двойственным категории полностью несвязных компактных хаусдорфовых пространств, впоследствии названных каменными пространствами.
Еще один бесконечный класс, промежуточный между булевыми алгебрами и полными булевыми алгебрами. - это понятие сигма-алгебры. Это определяется аналогично полным булевым алгебрам, но с sups и infs, ограниченными счетной арностью. То есть сигма-алгебра - это булева алгебра со всеми счетными суппортами и инфами. Поскольку sups и infs имеют ограниченную мощность, в отличие от ситуации с полными булевыми алгебрами, результат Гайфмана-Хейлза не применяется и free сигма -алгебры существуют. Однако, в отличие от ситуации с CABA, свободная счетно порожденная сигма-алгебра не является алгеброй степенных множеств.
Мы уже встречали несколько определений булевой алгебры, как модели эквациональной теории двухэлементной алгебры, как дополненной дистрибутивной решетки, как булевой кольцо, и как сохраняющий произведение функтор из определенной категории (Ловер). Следует упомянуть еще два определения:
(Круговость в этом определении можно удалить, заменив «конечную булеву алгебру» на «набор конечной мощности», снабженный булевыми операциями, стандартно интерпретируемыми для наборов степеней.)
Чтобы представить это в перспективе, бесконечные множества возникают как фильтрованные копределы конечных множеств, бесконечные CABA как отфильтрованные пределы алгебр конечных степеней и бесконечные пространства Стоуна как отфильтрованные пределы конечных множеств. Таким образом, если кто-то начинает с конечных множеств и спрашивает, как они обобщаются на бесконечные объекты, есть два способа: «сложение» их дает обычные или индуктивные множества, а «умножение» их дает Пространства камня или. Такой же выбор существует для алгебр множеств конечной мощности как двойников конечных множеств: сложение дает булевы алгебры как индуктивные объекты, а умножение дает CABA или алгебры множеств степеней как проконечные объекты.
Характерной отличительной чертой является то, что основная топология построенных таким образом объектов, если она определена как Хаусдорф, является дискретной для индуктивных объектов и компактной для бесконечных объектов. Топология конечных хаусдорфовых пространств всегда и дискретна, и компактна, тогда как для бесконечных пространств «дискретное» и «компактное» исключают друг друга. Таким образом, при обобщении конечных алгебр (любого вида, не только булевых) на бесконечные, «дискретная» и «компактная» часть объединяются, и нужно выбирать, какую из них оставить. Общее правило как для конечных, так и для бесконечных алгебр состоит в том, что финитарные алгебры дискретны, а двойственные к ним компактны и содержат бесконечные операции. Между этими двумя крайностями существует множество промежуточных бесконечных булевых алгебр, топология которых не является ни дискретной, ни компактной.
