В математике и математической логике булева алгебра является разделом алгебры . Она отличается от элементарной алгебры двумя способами. Во-первых, значениями переменных являются значения истинности true и false , обычно обозначаемые 1 и 0, тогда как в элементарной алгебре значениями переменных являются числа. Во-вторых, булева алгебра использует логические операторы, такие как конъюнкция ( и ), обозначаемая как ∧ , дизъюнкция ( или ), обозначаемая как ∨ , и отрицание ( не ), обозначаемое как ¬ . Элементарная алгебра, с другой стороны, использует арифметические операторы, такие как сложение, умножение, вычитание и деление. Таким образом, булева алгебра является формальным способом описания логических операций таким же образом, как элементарная алгебра описывает числовые операции.
Булева алгебра была введена Джорджем Булем в его первой книге «Математический анализ логики» (1847), [1] и более полно изложена в его «Исследовании законов мышления» (1854). [2] По словам Хантингтона , термин «булева алгебра» был впервые предложен Генри М. Шеффером в 1913 году, [3] хотя Чарльз Сандерс Пирс дал название «Булева [ sic ] алгебра с одной константой» первой главе своей «Простейшей математики» в 1880 году. [4] Булева алгебра сыграла основополагающую роль в развитии цифровой электроники и предусмотрена во всех современных языках программирования . Она также используется в теории множеств и статистике . [5]
Предшественником булевой алгебры была алгебра понятий Готфрида Вильгельма Лейбница . Использование двоичного числа в отношении И Цзин было центральным в characteristicsa universalis Лейбница . В конечном итоге это создало основы алгебры понятий. [6] Алгебра понятий Лейбница дедуктивно эквивалентна булевой алгебре множеств. [7]
Алгебра Буля предшествовала современным разработкам в абстрактной алгебре и математической логике ; однако она рассматривается как связанная с истоками обеих областей. [8] В абстрактной обстановке булева алгебра была усовершенствована в конце 19 века Джевонсом , Шредером , Хантингтоном и другими, пока не достигла современной концепции (абстрактной) математической структуры . [8] Например, эмпирическое наблюдение, что можно манипулировать выражениями в алгебре множеств , переводя их в выражения в алгебре Буля, объясняется в современных терминах, говоря, что алгебра множеств является булевой алгеброй ( обратите внимание на неопределенный артикль ). Фактически, М. Х. Стоун доказал в 1936 году , что каждая булева алгебра изоморфна полю множеств .
В 1930-х годах, изучая схемы переключения , Клод Шеннон заметил, что в этой обстановке можно также применять правила алгебры Буля, [9] и он ввел алгебру переключения как способ анализа и проектирования схем алгебраическими средствами в терминах логических вентилей . Шеннон уже имел в своем распоряжении абстрактный математический аппарат, поэтому он определил свою алгебру переключения как двухэлементную булеву алгебру . В современных условиях схемотехники нет особой необходимости рассматривать другие булевы алгебры, поэтому «алгебра переключения» и «булева алгебра» часто используются взаимозаменяемо. [10] [11] [12]
Эффективная реализация булевых функций является фундаментальной проблемой в проектировании комбинационных логических схем. Современные электронные средства автоматизации проектирования для схем сверхбольшой интеграции (VLSI) часто полагаются на эффективное представление булевых функций, известных как (упрощенные упорядоченные) бинарные диаграммы решений (BDD) для логического синтеза и формальной проверки . [13]
Логические предложения, которые могут быть выражены в классическом исчислении высказываний, имеют эквивалентное выражение в булевой алгебре. Таким образом, булева логика иногда используется для обозначения исчисления высказываний, выполненного таким образом. [14] [15] [16] Булевой алгебры недостаточно для записи логических формул с использованием квантификаторов , таких как те, что из логики первого порядка .
Хотя развитие математической логики не следовало программе Буля, связь между его алгеброй и логикой позже была поставлена на прочную основу в рамках алгебраической логики , которая также изучает алгебраические системы многих других логик. [8] Проблема определения того, могут ли переменные данной булевой (пропозициональной) формулы быть назначены таким образом, чтобы сделать формулу истинной, называется проблемой булевой выполнимости (SAT) и имеет важное значение для теоретической информатики , будучи первой проблемой, для которой было показано, что она NP-полна . Тесно связанная модель вычислений, известная как булева схема, связывает временную сложность (алгоритма ) со сложностью схемы .
В то время как выражения обозначают в основном числа в элементарной алгебре, в булевой алгебре они обозначают значения истинности false и true . Эти значения представлены битами , 0 и 1. Они не ведут себя как целые числа 0 и 1, для которых 1 + 1 = 2 , но могут быть отождествлены с элементами двухэлементного поля GF(2) , то есть целочисленной арифметикой по модулю 2 , для которой 1 + 1 = 0 . Сложение и умножение затем играют булевы роли XOR (исключающее ИЛИ) и AND (конъюнкция) соответственно, с дизъюнкцией x ∨ y (включающее ИЛИ), определяемой как x + y − xy , а отрицание ¬ x как 1 − x . В GF(2) , − может быть заменено на + , поскольку они обозначают одну и ту же операцию; Однако такой способ записи булевых операций позволяет применять обычные арифметические операции целых чисел (это может быть полезно при использовании языка программирования, в котором GF(2) не реализован).
Булева алгебра также имеет дело с функциями , значения которых находятся в множестве {0,1} . Последовательность битов является часто используемым примером такой функции. Другим распространенным примером является совокупность подмножеств множества E : для подмножества F множества E можно определить индикаторную функцию , которая принимает значение 1 на F и 0 вне F. Наиболее общим примером являются элементы множества булевой алгебры , все вышеперечисленное является их примерами.
Как и в случае с элементарной алгеброй, чисто эквациональная часть теории может быть разработана без рассмотрения явных значений переменных. [17]
В то время как элементарная алгебра имеет четыре операции (сложение, вычитание, умножение и деление), булева алгебра имеет только три основные операции: конъюнкция , дизъюнкция и отрицание , выраженные с помощью соответствующих бинарных операторов AND ( ) и OR ( ) и унарного оператора NOT ( ), которые вместе называются булевыми операторами . [18] Переменные в булевой алгебре, которые хранят логические значения 0 и 1, называются булевыми переменными . Они используются для хранения либо истинных, либо ложных значений. [19] Основные операции над булевыми переменными x и y определяются следующим образом:
В качестве альтернативы значения x ∧ y , x ∨ y и ¬ x можно выразить, записав их значения с помощью таблиц истинности следующим образом: [20]
При использовании в выражениях операторы применяются в соответствии с правилами приоритета. Как и в элементарной алгебре, выражения в скобках оцениваются первыми, следуя правилам приоритета. [21]
Если значения истинности 0 и 1 интерпретируются как целые числа, эти операции могут быть выражены с помощью обычных операций арифметики (где x + y использует сложение, а xy использует умножение) или с помощью функций минимума/максимума:
Можно было бы считать, что только отрицание и одна из двух других операций являются основными из-за следующих тождеств, которые позволяют определить конъюнкцию через отрицание и дизъюнкцию, и наоборот ( законы де Моргана ): [22]
Операции, состоящие из основных операций, включают, среди прочего, следующее:
Эти определения приводят к следующим таблицам истинности, дающим значения этих операций для всех четырех возможных входов.
Закон булевой алгебры — это тождество , например x ∨ ( y ∨ z ) = ( x ∨ y ) ∨ z между двумя булевыми терминами, где булев термин определяется как выражение, построенное из переменных и констант 0 и 1 с использованием операций ∧, ∨ и ¬. Эту концепцию можно распространить на термины, включающие другие булевы операции, такие как ⊕, → и ≡, но такие расширения не нужны для целей, для которых применяются законы. Такие цели включают определение булевой алгебры как любой модели булевых законов и как средства для вывода новых законов из старых, как при выводе x ∨ ( y ∧ z ) = x ∨ ( z ∧ y ) из y ∧ z = z ∧ y (как это рассматривается в § Аксиоматизация булевой алгебры ).
Булева алгебра удовлетворяет многим из тех же законов, что и обычная алгебра, когда мы сопоставляем ∨ с сложением и ∧ с умножением. В частности, следующие законы являются общими для обоих видов алгебры: [23] [24]
Следующие законы справедливы в булевой алгебре, но не в обычной алгебре:
Взятие x = 2 в третьем законе выше показывает, что это не обычный закон алгебры, поскольку 2 × 2 = 4. Оставшиеся пять законов можно опровергнуть в обычной алгебре, приняв все переменные равными 1. Например, в законе поглощения 1 левая часть будет 1(1 + 1) = 2 , тогда как правая часть будет 1 (и так далее).
Все рассмотренные до сих пор законы были для конъюнкции и дизъюнкции. Эти операции обладают тем свойством, что изменение любого аргумента либо оставляет выход неизменным, либо выход изменяется так же, как и вход. Эквивалентно, изменение любой переменной с 0 на 1 никогда не приводит к изменению выхода с 1 на 0. Операции с этим свойством называются монотонными . Таким образом, все аксиомы до сих пор были для монотонной булевой логики. Немонотонность входит через дополнение ¬ следующим образом. [5]
Операция дополнения определяется следующими двумя законами.
Все свойства отрицания, включая законы, приведенные ниже, вытекают только из двух вышеупомянутых законов. [5]
Как в обычной, так и в булевой алгебре отрицание работает путем обмена парами элементов, поэтому в обеих алгебрах оно удовлетворяет закону двойного отрицания (также называемому законом инволюции).
Но тогда как обычная алгебра удовлетворяет двум законам
Булева алгебра удовлетворяет законам Де Моргана :
Перечисленные выше законы определяют булеву алгебру в том смысле, что они влекут за собой остальную часть предмета. Законы дополнения 1 и 2 вместе с монотонными законами достаточны для этой цели и поэтому могут быть приняты как один возможный полный набор законов или аксиоматизация булевой алгебры. Каждый закон булевой алгебры логически следует из этих аксиом. Более того, булевы алгебры затем могут быть определены как модели этих аксиом, как это рассматривается в § Булевы алгебры .
Запись дальнейших законов булевой алгебры не может породить никаких новых следствий этих аксиом, и не может исключить никакую их модель. Напротив, в списке некоторых, но не всех тех же законов, могли бы быть булевы законы, которые не следовали бы из тех, что в списке, и, более того, могли бы быть модели перечисленных законов, которые не были бы булевыми алгебрами.
Эта аксиоматизация ни в коем случае не является единственной или даже обязательно самой естественной, учитывая, что не обращалось внимания на то, следуют ли некоторые аксиомы из других, а просто был выбор остановиться, когда было замечено достаточно законов, рассмотренных далее в § Аксиоматизация булевой алгебры . Или промежуточное понятие аксиомы можно обойти вообще, определив булев закон непосредственно как любую тавтологию , понимаемую как уравнение, которое выполняется для всех значений его переменных над 0 и 1. [25] [26] Можно показать, что все эти определения булевой алгебры эквивалентны.
Принцип: Если {X, R} — частично упорядоченное множество , то {X, R(обратное)} также является частично упорядоченным множеством.
В выборе символов для значений булевой алгебры нет ничего особенного. 0 и 1 можно было бы переименовать в α и β , и если бы это делалось последовательно, это все равно была бы булева алгебра, хотя и с некоторыми очевидными косметическими отличиями.
Но предположим, что 0 и 1 были переименованы в 1 и 0 соответственно. Тогда это все еще была бы булева алгебра, и более того, работающая с теми же значениями. Однако, это не было бы идентично нашей исходной булевой алгебре, потому что теперь ∨ ведет себя так, как раньше ∧, и наоборот. Так что все еще есть некоторые косметические различия, показывающие, что обозначение было изменено, несмотря на тот факт, что 0 и 1 все еще используются.
Но если в дополнение к перестановке названий значений, также переставляются названия двух бинарных операций, то теперь нет и следа того, что было сделано. Конечный продукт совершенно неотличим от того, с чего начиналось. Столбцы для x ∧ y и x ∨ y в таблицах истинности поменялись местами, но эта перестановка несущественна.
Когда значения и операции могут быть объединены в пары таким образом, что все важные элементы остаются неизменными при одновременном переключении всех пар, члены каждой пары называются дуальными друг другу. Таким образом, 0 и 1 являются дуальными, а ∧ и ∨ являются дуальными. Принцип дуальности , также называемый дуальностью Де Моргана , утверждает, что булева алгебра не изменяется при перестановке всех дуальных пар.
Одно изменение, которое не нужно было делать в рамках этого обмена, — это дополнение. Дополнение — это самодвойственная операция. Тождественная или ничего не делающая операция x (копирование ввода в вывод) также является самодвойственной. Более сложный пример самодвойственной операции — ( x ∧ y ) ∨ ( y ∧ z ) ∨ ( z ∧ x ) . Не существует самодвойственной бинарной операции, которая зависит от обоих своих аргументов. Композиция самодвойственных операций является самодвойственной операцией. Например, если f ( x , y , z ) = ( x ∧ y ) ∨ ( y ∧ z ) ∨ ( z ∧ x ) , то f ( f ( x , y , z ), x , t ) является самодвойственной операцией четырех аргументов x , y , z , t .
Принцип двойственности можно объяснить с точки зрения теории групп тем фактом, что существует ровно четыре функции, которые являются взаимно-однозначными отображениями ( автоморфизмами ) множества булевых многочленов обратно в себя: функция тождества, функция дополнения, двойственная функция и контрадуальная функция (дополняемая двойственная). Эти четыре функции образуют группу относительно композиции функций , изоморфную четверной группе Клейна , действующей на множестве булевых многочленов. Вальтер Готтшалк заметил, что, следовательно, более подходящим названием для этого явления будет принцип ( или квадрат ) кватернальности . [5] : 21–22
Диаграмма Венна [27] может быть использована в качестве представления булевой операции с использованием затененных перекрывающихся областей. Для каждой переменной существует одна область, все из которых в приведенных здесь примерах имеют круглую форму. Внутренняя и внешняя части области x соответствуют значениям 1 (истина) и 0 (ложь) для переменной x соответственно . Затенение указывает значение операции для каждой комбинации областей, причем темный цвет обозначает 1, а светлый — 0 (некоторые авторы используют противоположное соглашение).
Три диаграммы Венна на рисунке ниже представляют соответственно конъюнкцию x ∧ y , дизъюнкцию x ∨ y и дополнение ¬ x .
Для конъюнкции область внутри обоих кругов заштрихована, чтобы указать, что x ∧ y равно 1, когда обе переменные равны 1. Остальные области остаются незаштрихованными, чтобы указать, что x ∧ y равно 0 для остальных трех комбинаций.
Вторая диаграмма представляет дизъюнкцию x ∨ y, заштриховав те области, которые лежат внутри одного или обоих кругов. Третья диаграмма представляет дополнение ¬ x, заштриховав область, не находящуюся внутри круга.
Хотя мы не показали диаграммы Венна для констант 0 и 1, они тривиальны, представляя собой соответственно белый и темный ящики, ни один из которых не содержит круга. Однако мы могли бы поместить круг для x в эти ящики, и в этом случае каждый из них будет обозначать функцию одного аргумента, x , которая возвращает то же значение независимо от x , называемую константной функцией. Что касается их выходных данных, константы и константные функции неразличимы; разница в том, что константа не принимает аргументов, называется нулевой или нулевой операцией, в то время как константная функция принимает один аргумент, который она игнорирует, и является унарной операцией.
Диаграммы Венна полезны для визуализации законов. Законы коммутативности для ∧ и ∨ можно увидеть из симметрии диаграмм: бинарная операция, которая не является коммутативной, не имела бы симметричной диаграммы, поскольку перестановка x и y имела бы эффект горизонтального отражения диаграммы, и тогда любое нарушение коммутативности выглядело бы как нарушение симметрии.
Идемпотентность ∧ и ∨ можно визуализировать, сдвинув два круга вместе и заметив, что затемненная область затем становится всем кругом как для ∧, так и для ∨.
Чтобы увидеть первый закон поглощения, x ∧ ( x ∨ y ) = x , начните с диаграммы в середине для x ∨ y и обратите внимание, что часть заштрихованной области, общая с кругом x , является всем кругом x . Для второго закона поглощения, x ∨ ( x ∧ y ) = x , начните с левой диаграммы для x ∧ y и обратите внимание, что заштриховка всего круга x приводит к заштриховке только круга x , поскольку предыдущая заштриховка была внутри круга x .
Закон двойного отрицания можно увидеть, дополнив штриховку на третьей диаграмме для ¬ x , которая затеняет круг x .
Чтобы визуализировать первый закон Де Моргана, (¬ x ) ∧ (¬ y ) = ¬( x ∨ y ) , начните со средней диаграммы для x ∨ y и дополните ее штриховку так, чтобы была заштрихована только область за пределами обоих кругов, что и описывает правая часть закона. Результат будет таким же, как если бы мы заштриховали ту область, которая находится как за пределами круга x , так и за пределами круга y , то есть соединение их внешних частей, что и описывает левая часть закона.
Второй закон Де Моргана, (¬ x ) ∨ (¬ y ) = ¬( x ∧ y ) , работает таким же образом, если поменять местами две диаграммы.
Первый закон дополнения, x ∧ ¬ x = 0 , гласит, что внутренняя и внешняя части окружности x не имеют перекрытия. Второй закон дополнения, x ∨ ¬ x = 1 , гласит, что все находится либо внутри, либо снаружи окружности x .
Цифровая логика — это приложение булевой алгебры 0 и 1 к электронному оборудованию, состоящему из логических вентилей, соединенных для формирования схемы цепи . Каждый вентиль реализует булеву операцию и схематически изображается формой, указывающей операцию. Формы, связанные с вентилями для конъюнкции (И-вентили), дизъюнкции (ИЛИ-вентили) и дополнения (инверторы), следующие: [28]
Линии слева от каждого вентиля представляют входные провода или порты . Значение входа представлено напряжением на выводе. Для так называемой логики «активный высокий» 0 представлен напряжением, близким к нулю или «земле», в то время как 1 представлен напряжением, близким к напряжению питания; активный низкий меняет это на противоположное. Линия справа от каждого вентиля представляет выходной порт, который обычно следует тем же соглашениям о напряжении, что и входные порты.
Дополнение реализовано с помощью инверторного вентиля. Треугольник обозначает операцию, которая просто копирует вход на выход; маленький кружок на выходе обозначает фактическую инверсию, дополняющую вход. Соглашение о размещении такого кружка на любом порте означает, что сигнал, проходящий через этот порт, дополняется на пути, независимо от того, является ли он входным или выходным портом.
Принцип дуальности, или законы Де Моргана , можно понимать как утверждение, что дополнение всех трех портов вентиля И преобразует его в вентиль ИЛИ и наоборот, как показано на рисунке 4 ниже. Однако дополнение обоих портов инвертора оставляет операцию неизменной.
В более общем смысле, можно дополнить любое из восьми подмножеств трех портов вентиля И или ИЛИ. Результирующие шестнадцать возможностей приводят только к восьми булевским операциям, а именно к тем, в таблице истинности которых содержится нечетное число единиц. Таких операций восемь, поскольку «нечетный бит» может быть либо 0, либо 1 и может занимать любую из четырех позиций в таблице истинности. Поскольку существует шестнадцать двоичных булевых операций, это должно оставить восемь операций с четным числом единиц в их таблицах истинности. Две из них — константы 0 и 1 (как двоичные операции, игнорирующие оба своих входа); четыре — операции, которые нетривиально зависят только от одного из своих двух входов, а именно x , y , ¬ x и ¬ y ; а оставшиеся две — это x ⊕ y (XOR) и его дополнение x ≡ y .
Термин «алгебра» обозначает как субъект, а именно субъект алгебры , так и объект, а именно алгебраическую структуру . В то время как вышеизложенное касалось предмета булевой алгебры, в этом разделе рассматриваются математические объекты, называемые булевыми алгебрами, определяемые в полной общности как любая модель булевых законов. Мы начнем с частного случая понятия, определяемого без ссылки на законы, а именно с конкретных булевых алгебр, а затем дадим формальное определение общего понятия.
Конкретная булева алгебра или поле множеств — это любое непустое множество подмножеств заданного множества X, замкнутое относительно операций объединения , пересечения и дополнения относительно X. [5 ]
(Исторически X сам по себе должен был быть непустым, чтобы исключить вырожденную или одноэлементную булеву алгебру, что является единственным исключением из правила, согласно которому все булевы алгебры удовлетворяют одним и тем же уравнениям, поскольку вырожденная алгебра удовлетворяет каждому уравнению. Однако это исключение противоречит предпочтительному чисто эквациональному определению «булевой алгебры», поскольку нет способа исключить одноэлементную алгебру, используя только уравнения — 0 ≠ 1 не считается, будучи отрицательным уравнением. Поэтому современные авторы допускают вырожденную булеву алгебру и позволяют X быть пустым.)
Пример 1. Множество 2 X множества X , состоящее из всех подмножеств X. Здесь X может быть любым множеством : пустым , конечным, бесконечным или даже несчетным .
Пример 2. Пустое множество и X . Эта двухэлементная алгебра показывает, что конкретная булева алгебра может быть конечной, даже если она состоит из подмножеств бесконечного множества. Видно, что каждое поле подмножеств X должно содержать пустое множество и X . Следовательно, невозможен никакой меньший пример, кроме вырожденной алгебры, полученной путем взятия X пустым, чтобы сделать пустое множество и X совпадающими.
Пример 3. Множество конечных и коконечных множеств целых чисел, где коконечным множеством является множество, исключающее только конечное число целых чисел. Это, очевидно, замкнуто относительно дополнения и замкнуто относительно объединения, поскольку объединение коконечного множества с любым множеством является коконечным, в то время как объединение двух конечных множеств является конечным. Пересечение ведет себя как объединение, где «конечное» и «коконечное» поменяны местами. Этот пример счетно бесконечен, поскольку существует только счетное число конечных множеств целых чисел.
Пример 4. Для менее тривиального примера точки, высказанной в примере 2, рассмотрим диаграмму Венна, образованную n замкнутыми кривыми, разбивающими диаграмму на 2 n областей, и пусть X будет (бесконечным) множеством всех точек плоскости не на какой-либо кривой, а где-то внутри диаграммы. Таким образом, внутренняя часть каждой области является бесконечным подмножеством X , и каждая точка в X находится ровно в одной области. Тогда множество всех 2 2 n возможных объединений областей (включая пустое множество, полученное как объединение пустого множества областей, и X , полученное как объединение всех 2 n областей) замкнуто относительно объединения, пересечения и дополнения относительно X и, следовательно, образует конкретную булеву алгебру. Опять же, существует конечное число подмножеств бесконечного множества, образующих конкретную булеву алгебру, причем пример 2 возникает как случай n = 0 отсутствия кривых.
Подмножество Y множества X можно идентифицировать с помощью индексированного семейства битов с набором индексов X , при этом бит, индексированный x ∈ X, равен 1 или 0 в зависимости от того, x ∈ Y или нет . (Это так называемое понятие характеристической функции подмножества.) Например, 32-битное компьютерное слово состоит из 32 битов, индексированных набором {0,1,2,...,31}, при этом 0 и 31 индексируют младшие и старшие биты соответственно. Для меньшего примера, если где a, b, c рассматриваются как позиции битов в указанном порядке слева направо, восемь подмножеств {}, { c }, { b }, { b , c }, { a }, { a , c }, { a , b } и { a , b , c } множества X можно идентифицировать с соответствующими битовыми векторами 000, 001, 010, 011, 100, 101, 110 и 111. Битовые векторы, индексированные набором натуральных чисел, представляют собой бесконечные последовательности битов, в то время как те, которые индексированы действительными числами в единичном интервале [0,1], упакованы слишком плотно, чтобы их можно было записать обычным образом, но тем не менее образуют четко определенные индексированные семейства (представьте, что вы раскрашиваете каждую точку интервала [0,1] либо в черный, либо в белый цвет независимо; черные точки тогда образуют произвольное подмножество [0,1]).
С этой точки зрения битового вектора конкретная булева алгебра может быть эквивалентно определена как непустое множество битовых векторов, имеющих одинаковую длину (в более общем смысле, индексированных одним и тем же множеством) и замкнутых относительно операций битовых векторов побитового ∧, ∨ и ¬, как в 1010∧0110 = 0010 , 1010∨0110 = 1110 и ¬1010 = 0101 , реализациях битовых векторов пересечения, объединения и дополнения соответственно.
Множество {0,1} и его булевы операции, рассмотренные выше, можно понимать как особый случай битовых векторов длины один, которые путем идентификации битовых векторов с подмножествами можно также понимать как два подмножества одноэлементного множества. Это называется прототипической булевой алгеброй, что подтверждается следующим наблюдением.
Это наблюдение доказывается следующим образом. Конечно, любой закон, которому удовлетворяют все конкретные булевы алгебры, удовлетворяет прототипическая, поскольку она конкретна. И наоборот, любой закон, который не выполняется для некоторой конкретной булевой алгебры, должен был не выполняться в определенной битовой позиции, и в этом случае эта позиция сама по себе дает однобитовый контрпример к этому закону. Невырожденность гарантирует существование по крайней мере одной битовой позиции, поскольку существует только один пустой битовый вектор.
Конечную цель следующего раздела можно понимать как исключение «конкретного» из вышеприведенного наблюдения. Эта цель достигается посредством более сильного наблюдения, что с точностью до изоморфизма все булевы алгебры являются конкретными.
До сих пор все булевы алгебры были конкретными, состоящими из битовых векторов или, что эквивалентно, из подмножеств некоторого множества. Такая булева алгебра состоит из множества и операций на этом множестве, которые, как можно показать, удовлетворяют законам булевой алгебры.
Вместо того, чтобы показывать, что булевы законы выполняются, мы можем постулировать множество X , две бинарные операции над X и одну унарную операцию и потребовать , чтобы эти операции удовлетворяли законам булевой алгебры. Элементы X не обязательно должны быть битовыми векторами или подмножествами, но могут быть чем угодно. Это приводит к более общему абстрактному определению.
Для целей этого определения не имеет значения, как операции пришли к удовлетворению законов, будь то по указу или доказательству. Все конкретные булевы алгебры удовлетворяют законам (по доказательству, а не по указу), откуда каждая конкретная булева алгебра является булевой алгеброй согласно нашим определениям. Это аксиоматическое определение булевой алгебры как множества и определенных операций, удовлетворяющих определенным законам или аксиомам по указу, полностью аналогично абстрактным определениям группы , кольца , поля и т. д., характерным для современной или абстрактной алгебры .
При любой полной аксиоматизации булевой алгебры, например, аксиомах для дополненной дистрибутивной решетки , достаточным условием для того, чтобы алгебраическая структура такого рода удовлетворяла всем булевым законам, является то, что она удовлетворяет только этим аксиомам. Поэтому следующее определение является эквивалентным.
В разделе об аксиоматизации перечислены другие аксиоматизации, любая из которых может быть положена в основу эквивалентного определения.
Хотя каждая конкретная булева алгебра является булевой алгеброй, не каждая булева алгебра должна быть конкретной. Пусть n — положительное целое число без квадратов , не делящееся на квадрат целого числа, например 30, но не 12. Операции наибольшего общего делителя , наименьшего общего кратного и деления на n (то есть ¬ x = n / x ) можно показать, что они удовлетворяют всем булевым законам, когда их аргументы пробегают положительные делители n . Следовательно, эти делители образуют булеву алгебру. Эти делители не являются подмножествами множества, что делает делители n булевой алгеброй, которая не является конкретной согласно нашим определениям.
Однако, если каждый делитель n представлен набором его простых множителей, эта неконкретная булева алгебра изоморфна конкретной булевой алгебре, состоящей из всех наборов простых множителей n , с объединением, соответствующим наименьшему общему кратному, пересечением — наибольшему общему делителю, а дополнением — делению на n . Таким образом, этот пример, хотя и не является технически конкретным, по крайней мере «морально» конкретен через это представление, называемое изоморфизмом . Этот пример является примером следующего понятия.
На следующий вопрос дается положительный ответ.
То есть, с точностью до изоморфизма, абстрактные и конкретные булевы алгебры — это одно и то же. Этот результат зависит от теоремы о простом идеале Буля , принципа выбора, немного более слабого, чем аксиома выбора . Эта сильная связь подразумевает более слабый результат, усиливающий наблюдение в предыдущем подразделе до следующего простого следствия представимости.
Он слабее в том смысле, что сам по себе не подразумевает представимости. Булевы алгебры здесь являются особыми, например, алгебра отношений является булевой алгеброй с дополнительной структурой, но это не тот случай, когда каждая алгебра отношений представима в том смысле, который присущ алгебрам отношений.
Приведенное выше определение абстрактной булевой алгебры как множества вместе с операциями, удовлетворяющими "этим" булевым законам, поднимает вопрос о том, что это за законы. Упрощенный ответ - "все булевы законы", которые можно определить как все уравнения, которые выполняются для булевой алгебры 0 и 1. Однако, поскольку существует бесконечно много таких законов, это неудовлетворительный ответ на практике, что приводит к вопросу о том, достаточно ли требовать выполнения только конечного числа законов.
В случае булевых алгебр ответ «да»: конечное число уравнений, перечисленных выше, достаточно. Таким образом, булева алгебра называется конечно аксиоматизируемой или конечно базируемой .
Более того, число необходимых уравнений может быть еще больше сокращено. Для начала, некоторые из приведенных выше законов подразумеваются некоторыми другими. Достаточное подмножество приведенных выше законов состоит из пар законов ассоциативности, коммутативности и поглощения, дистрибутивности ∧ над ∨ (или другого закона дистрибутивности — одного достаточно) и двух законов дополнения. Фактически, это традиционная аксиоматизация булевой алгебры как дополненной дистрибутивной решетки .
Вводя дополнительные законы, не перечисленные выше, становится возможным еще больше сократить список необходимых уравнений; например, с вертикальной чертой, представляющей операцию штриха Шеффера , одной аксиомы достаточно для полной аксиоматизации булевой алгебры. Также возможно найти более длинные отдельные аксиомы, используя более традиционные операции; см. Минимальные аксиомы для булевой алгебры . [30]
Пропозициональная логика — это логическая система , тесно связанная с булевой алгеброй. [5] Многие синтаксические концепции булевой алгебры переносятся в пропозициональную логику лишь с незначительными изменениями в обозначениях и терминологии, в то время как семантика пропозициональной логики определяется посредством булевых алгебр таким образом, что тавтологии (теоремы) пропозициональной логики соответствуют эквациональным теоремам булевой алгебры.
Синтаксически каждый булев термин соответствует пропозициональной формуле пропозициональной логики. В этом переводе между булевой алгеброй и пропозициональной логикой булевы переменные x, y, ... становятся пропозициональными переменными (или атомами ) P, Q , ... Булевы термины, такие как x ∨ y, становятся пропозициональными формулами P ∨ Q ; 0 становится ложным или ⊥ , а 1 становится истинным или T. При ссылке на общие предложения удобно использовать греческие буквы Φ, Ψ, ... в качестве метапеременных (переменных вне языка пропозиционального исчисления, используемых при обсуждении пропозиционального исчисления) для обозначения предложений.
Семантика пропозициональной логики опирается на присвоения истинности . Основная идея присвоения истинности заключается в том, что пропозициональные переменные отображаются в элементы фиксированной булевой алгебры, а затем истинностное значение пропозициональной формулы, использующей эти буквы, является элементом булевой алгебры, который получается путем вычисления значения булева термина, соответствующего формуле. В классической семантике используется только двухэлементная булева алгебра, в то время как в булевозначной семантике рассматриваются произвольные булевы алгебры. Тавтология — это пропозициональная формула, которой присваивается истинностное значение 1 каждым присвоением истинности ее пропозициональных переменных произвольной булевой алгебре (или, что эквивалентно, каждым присвоением истинности двухэлементной булевой алгебре).
Эта семантика допускает перевод между тавтологиями пропозициональной логики и эквациональными теоремами булевой алгебры. Каждая тавтология Φ пропозициональной логики может быть выражена как булево уравнение Φ = 1, которое будет теоремой булевой алгебры. Наоборот, каждая теорема Φ = Ψ булевой алгебры соответствует тавтологиям (Φ ∨ ¬Ψ) ∧ (¬Φ ∨ Ψ) и (Φ ∧ Ψ) ∨ (¬Φ ∧ ¬Ψ). Если в языке есть →, эти последние тавтологии также могут быть записаны как (Φ → Ψ) ∧ (Ψ → Φ) или как две отдельные теоремы Φ → Ψ и Ψ → Φ; если ≡ доступно, то можно использовать одинарную тавтологию Φ ≡ Ψ.
Одним из мотивирующих применений исчисления высказываний является анализ высказываний и дедуктивных аргументов на естественном языке. [31] В то время как высказывание «если x = 3, то x + 1 = 4» зависит от значений таких символов, как + и 1, высказывание «если x = 3, то x = 3» не зависит; оно истинно просто в силу своей структуры и остается истинным, независимо от того, заменено ли « x = 3» на « x = 4» или «луна сделана из зеленого сыра». Общая или абстрактная форма этой тавтологии — «если P , то P », или на языке булевой алгебры P → P. [ требуется ссылка ]
Замена P на x = 3 или любое другое предложение называется инстанциацией P этим предложением. Результат инстанциации P в абстрактном предложении называется экземпляром предложения. Таким образом, x = 3 → x = 3 является тавтологией в силу того, что является экземпляром абстрактной тавтологии P → P . Все вхождения инстанцированной переменной должны быть инстанциированы с помощью того же предложения, чтобы избежать такой бессмыслицы, как P → x = 3 или x = 3 → x = 4.
Пропозициональное исчисление ограничивает внимание абстрактными предложениями, которые построены из пропозициональных переменных с использованием булевых операций. Инстанцирование все еще возможно в пропозициональном исчислении, но только путем инстанцирования пропозициональных переменных абстрактными предложениями, такими как инстанцирование Q с помощью Q → P в P → ( Q → P ) для получения экземпляра P → (( Q → P ) → P ).
(Наличие инстанцирования как части механизма исчисления высказываний позволяет избежать необходимости в метапеременных в языке исчисления высказываний, поскольку обычные пропозициональные переменные могут рассматриваться в языке для обозначения произвольных предложений. Сами метапеременные находятся вне досягаемости инстанцирования, не являясь частью языка исчисления высказываний, а скорее частью того же языка для обсуждения, на котором написано это предложение, где необходимо иметь возможность различать пропозициональные переменные и их инстанцирования как отдельные синтаксические сущности.)
Аксиоматизация исчисления высказываний — это набор тавтологий, называемых аксиомами , и одно или несколько правил вывода для получения новых тавтологий из старых. Доказательство в системе аксиом A — это конечная непустая последовательность предложений, каждое из которых является либо примером аксиомы A , либо следует по некоторому правилу A из предложений, появляющихся ранее в доказательстве (тем самым исключая круговые рассуждения). Последнее предложение — это теорема , доказанная доказательством. Каждый непустой начальный сегмент доказательства сам по себе является доказательством, откуда каждое предложение в доказательстве само по себе является теоремой. Аксиоматизация является корректной , когда каждая теорема является тавтологией, и полной , когда каждая тавтология является теоремой. [32]
Исчисление высказываний обычно организовано как система Гильберта , операции которой являются операциями булевой алгебры, а теоремы — булевыми тавтологиями, булевыми терминами, равными булевой константе 1. Другая форма — исчисление последовательностей , которое имеет два вида: предложения, как в обычном исчислении высказываний, и пары списков предложений, называемых секвенциями , например, A ∨ B , A ∧ C , ... ⊢ A , B → C , .... Две половины секвенции называются антецедентом и сукцедентом соответственно. Обычная метапеременная, обозначающая антецедент или его часть, — это Γ, а для сукцедента — Δ; таким образом, Γ, A ⊢ Δ будет обозначать секвенцию, сукцедент которой является списком Δ, а антецедент которой является списком Γ с добавленным после него дополнительным предложением A. Антецедент интерпретируется как конъюнкция его предложений, сукцедент — как дизъюнкция его предложений, а сам секвенция — как следствие сукцедента из антецедента.
Вывод отличается от импликации тем, что в то время как последний является бинарной операцией , которая возвращает значение в булевой алгебре, первый является бинарным отношением , которое либо выполняется, либо не выполняется. В этом смысле вывод является внешней формой импликации, то есть внешней по отношению к булевой алгебре, думая о читателе секвенции как о внешнем и интерпретируя и сравнивая антецеденты и сукцеденты в некоторой булевой алгебре. Естественная интерпретация ⊢ — это ≤ в частичном порядке булевой алгебры, определяемом как x ≤ y, только когда x ∨ y = y . Эта способность смешивать внешнюю импликацию ⊢ и внутреннюю импликацию → в одной логике является одним из существенных различий между исчислением секвенций и исчислением высказываний. [33]
Булева алгебра как исчисление двух значений является основополагающей для компьютерных схем, компьютерного программирования и математической логики, а также используется в других областях математики, таких как теория множеств и статистика. [5]
В начале 20-го века несколько инженеров-электриков [ кто? ] интуитивно поняли, что булева алгебра аналогична поведению некоторых типов электрических цепей. Клод Шеннон формально доказал, что такое поведение логически эквивалентно булевой алгебре в своей магистерской диссертации 1937 года « Символический анализ релейных и коммутационных цепей» .
Сегодня все современные компьютеры общего назначения выполняют свои функции, используя двузначную булеву логику; то есть их электрические схемы являются физическим проявлением двузначной булевой логики. Они достигают этого различными способами: как напряжения на проводах в высокоскоростных схемах и емкостных запоминающих устройствах, как ориентации магнитного домена в ферромагнитных запоминающих устройствах, как отверстия в перфокартах или бумажной ленте и т. д. (Некоторые ранние компьютеры использовали десятичные схемы или механизмы вместо двузначных логических схем.)
Конечно, можно закодировать более двух символов на любом данном носителе. Например, можно использовать соответственно 0, 1, 2 и 3 вольта для кодирования алфавита из четырех символов на проводе или отверстий разного размера в перфокарте. На практике жесткие ограничения высокой скорости, малого размера и низкой мощности объединяются, чтобы сделать шум основным фактором. Это затрудняет различение символов, когда есть несколько возможных символов, которые могут появиться в одном месте. Вместо того чтобы пытаться различать четыре напряжения на одном проводе, цифровые дизайнеры остановились на двух напряжениях на провод, высоком и низком.
Компьютеры используют двухзначные булевы схемы по указанным выше причинам. Наиболее распространенные компьютерные архитектуры используют упорядоченные последовательности булевых значений, называемые битами, из 32 или 64 значений, например, 0110100011010110010101010101001011. При программировании на машинном коде , языке ассемблера и некоторых других языках программирования программисты работают с низкоуровневой цифровой структурой регистров данных . Эти регистры работают с напряжениями, где ноль вольт представляет собой логический 0, а опорное напряжение (часто +5 В, +3,3 В или +1,8 В) представляет собой логический 1. Такие языки поддерживают как числовые операции, так и логические операции. В этом контексте «числовой» означает, что компьютер обрабатывает последовательности бит как двоичные числа (числа с основанием два) и выполняет арифметические операции, такие как сложение, вычитание, умножение или деление. «Логический» относится к булевым логическим операциям дизъюнкции, конъюнкции и отрицания между двумя последовательностями битов, в которых каждый бит в одной последовательности просто сравнивается со своим аналогом в другой последовательности. Таким образом, программисты имеют возможность работать и применять правила либо числовой алгебры, либо булевой алгебры по мере необходимости. Основной отличительной чертой между этими семействами операций является наличие операции переноса в первом, но не во втором.
Другие области, где два значения являются хорошим выбором, — это право и математика. В повседневной непринужденной беседе приемлемы нюансированные или сложные ответы, такие как «может быть» или «только на выходных». Однако в более конкретных ситуациях, таких как суд или математика, основанная на теоремах, считается выгодным формулировать вопросы таким образом, чтобы допускать простой ответ «да» или «нет» — виновен ли подсудимый или нет, истинно или ложно утверждение — и не допускать никаких других ответов. Однако ограничение этого может оказаться на практике для ответчика, принцип простого вопроса «да» или «нет» стал центральной чертой как судебной, так и математической логики, делая двузначную логику заслуживающей организации и изучения сама по себе.
Центральным понятием теории множеств является членство. Организация может допускать несколько степеней членства, таких как новичок, ассоциированный член и полный член. Однако в случае с множествами элемент либо находится внутри, либо отсутствует. Кандидаты на членство в множестве работают так же, как провода в цифровом компьютере: каждый кандидат является либо членом, либо нечленом, так же как каждый провод является либо высоким, либо низким.
Поскольку алгебра является основополагающим инструментом в любой области, поддающейся математической обработке, эти соображения в совокупности делают алгебру двух величин фундаментально важной для компьютерного оборудования, математической логики и теории множеств.
Двузначная логика может быть расширена до многозначной логики , в частности, путем замены булевой области {0, 1} на единичный интервал [0, 1], в этом случае вместо того, чтобы принимать только значения 0 или 1, можно предполагать любое значение между 0 и 1 включительно. Алгебраически отрицание (НЕ) заменяется на 1 − x , конъюнкция (И) заменяется на умножение ( xy ), а дизъюнкция (ИЛИ) определяется с помощью закона Де Моргана . Интерпретация этих значений как логических значений истинности дает многозначную логику, которая составляет основу нечеткой логики и вероятностной логики . В этих интерпретациях значение интерпретируется как «степень» истинности — в какой степени предложение истинно, или вероятность того, что предложение истинно.
Первоначально булевы операции применялись в математической логике , где они объединяли значения истинности (истина или ложь) отдельных формул.
В естественных языках, таких как английский, есть слова для нескольких булевых операций, в частности, конъюнкция ( и ), дизъюнкция ( или ), отрицание ( не ) и импликация ( подразумевает ). Но не является синонимом и не . При использовании для объединения ситуативных утверждений, таких как «блок находится на столе» и «кошки пьют молоко», которые наивно являются либо истинными, либо ложными, значения этих логических связок часто имеют значение их логических аналогов. Однако при описании поведения, такого как «Джим вошел через дверь», начинаешь замечать различия, такие как отсутствие коммутативности, например, конъюнкция «Джим открыл дверь» с «Джим вошел через дверь» в этом порядке не эквивалентна их конъюнкции в другом порядке, поскольку и обычно означает и затем в таких случаях. Вопросы могут быть похожими: порядок «Небо голубое, и почему небо голубое?» имеет больше смысла, чем обратный порядок. Конъюнктивные команды о поведении похожи на поведенческие утверждения, например, одеться и пойти в школу . Дизъюнктивные команды, такие как love me or leave me or fish or cut bait, как правило, асимметричны из-за подразумевания, что одна альтернатива менее предпочтительна. Союзные существительные, такие как tea and milk , обычно описывают агрегацию как с объединением множеств, в то время как tea or milk — это выбор. Однако контекст может поменять эти значения местами, как в your choices are coffee and tea , что обычно означает то же самое, что your choices are coffee or tea (альтернативы). Двойное отрицание, как в "I don't not like milk", редко означает буквально "I do like milk", а скорее передает своего рода хеджирование, как будто подразумевая, что есть третья возможность. "Not not P" можно вольно интерпретировать как "surely P", и хотя P обязательно подразумевает "not not P ", обратное в английском языке подозрительно, как и в случае с интуиционистской логикой . Ввиду весьма своеобразного использования союзов в естественных языках, булева алгебра не может считаться надежной основой для их интерпретации.
Булевы операции используются в цифровой логике для объединения битов, передаваемых по отдельным проводам, тем самым интерпретируя их по {0,1}. Когда вектор из n идентичных двоичных вентилей используется для объединения двух битовых векторов, каждый из которых состоит из n битов, отдельные битовые операции можно рассматривать как одну операцию над значениями из булевой алгебры с 2 n элементами.
Наивная теория множеств интерпретирует булевы операции как действия над подмножествами заданного множества X. Как мы видели ранее, это поведение в точности соответствует покоординатным комбинациям битовых векторов, при этом объединение двух множеств соответствует дизъюнкции двух битовых векторов и так далее.
256-элементная свободная булева алгебра на трех генераторах развернута в компьютерных дисплеях на основе растровой графики , которые используют битовый блит для манипулирования целыми областями, состоящими из пикселей , полагаясь на булевы операции для указания того, как исходная область должна быть объединена с целевой, обычно с помощью третьей области, называемой маской . Современные видеокарты предлагают все 2 2 3 = 256 тернарных операций для этой цели, причем выбор операции является однобайтовым (8-битным) параметром. Константы SRC = 0xaa или 0b10101010 , DST = 0xcc или 0b11001100 , и MSK = 0xf0 или 0b11110000 позволяют записывать булевы операции, такие как (то есть XOR источника и назначения, а затем AND результата с маской), непосредственно как константу, обозначающую байт, вычисленный во время компиляции, 0x80 в примере, 0x88, если just , и т. д. Во время выполнения видеокарта интерпретирует байт как растровую операцию, указанную исходным выражением, единообразно, что требует исключительно мало оборудования и занимает время, совершенно независимое от сложности выражения.(SRC^DST)&MSK(SRC^DST)&MSKSRC^DST
Системы твердотельного моделирования для автоматизированного проектирования предлагают множество методов построения объектов из других объектов, одним из которых является объединение с помощью булевых операций. В этом методе пространство, в котором существуют объекты, понимается как набор S вокселей ( трехмерный аналог пикселей в двумерной графике), а формы определяются как подмножества S , что позволяет объединять объекты в наборы посредством объединения, пересечения и т. д. Одно из очевидных применений — построение сложной формы из простых форм просто как объединения последних. Другое применение — в скульптуре, понимаемой как удаление материала: любая операция шлифования, фрезерования, маршрутизации или сверления, которая может быть выполнена с помощью физического оборудования на физических материалах, может быть смоделирована на компьютере с помощью булевой операции x ∧ ¬ y или x − y , которая в теории множеств является разностью множеств, удаляющей элементы y из элементов x . Таким образом, если заданы две формы, одна из которых должна быть обработана, а другая — материал, который должен быть удален, результат обработки первой для удаления последнего описывается просто как их разность множеств.
Поисковые запросы также используют булеву логику. Для этого приложения каждая веб-страница в Интернете может рассматриваться как «элемент» «множества». В следующих примерах используется синтаксис, поддерживаемый Google . [NB 1]
"Поисковый термин 1" "Поисковый термин 2"
«Поисковый запрос 1» ИЛИ «Поисковый запрос 2»
«Поисковый термин 1» − «Поисковый термин 2»
