Булева алгебра (алгебра логики)

Основные операции

Основные операции булевой алгебры следующие:

• AND ( соединение ), обозначаемое x ∧ y (иногда x AND y или K xy ), удовлетворяет x ∧ y = 1, если x = y = 1, и x ∧ y = 0 в противном случае.
• OR ( дизъюнкция ), обозначаемая x ∨ y (иногда x OR y или A xy ), удовлетворяет x ∨ y = 0, если x = y = 0, и x ∨ y = 1 в противном случае.
• НЕ ( отрицание ), обозначаемое ¬ x (иногда НЕ x , N x , x̅, x ‘или! X ), удовлетворяет ¬ x = 0, если x = 1, и ¬ x = 1, если x = 0.

В качестве альтернативы значения x ∧ y , x ∨ y и ¬ x могут быть выражены путем табулирования их значений с таблицами истинности следующим образом:

Если значения истинности 0 и 1 интерпретируются как целые числа, эти операции могут быть выражены обычными операциями арифметики (где x y использует сложение, а xy использует умножение) или функциями минимума / максимума:

Икс∧узнак равноИксузнак равномин(Икс,у)Икс∨узнак равноИкс у-Иксузнак равноМаксимум(Икс,у)¬Иксзнак равно1-Икс{ displaystyle { begin {align} x wedge y & = xy = min (x, y) \ x vee y & = x y-xy = max (x, y) \ neg x & = 1 -x конец {выровнено}}}

Можно было бы считать, что только отрицание и одна из двух других операций являются основными из-за следующих тождеств, которые позволяют определять конъюнкцию в терминах отрицания и дизъюнкции, и наоборот ( законы Де Моргана ):

Икс∧узнак равно¬(¬Икс∨¬у)Икс∨узнак равно¬(¬Икс∧¬у){ displaystyle { begin {align} x wedge y & = neg ( neg x vee neg y) \ x vee y & = neg ( neg x wedge neg y) end {выровнено} }}

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

Приведенное выше определение абстрактной булевой алгебры как множества и операций, удовлетворяющих «булевым» законам, поднимает вопрос, что это за законы? Простой ответ – «все булевы законы», которые можно определить как все уравнения, которые выполняются для булевой алгебры 0 и 1.

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

Можно ли еще сократить этот список? И снова ответ – да. Начнем с того, что некоторые из вышеперечисленных законов подразумеваются некоторыми другими. Достаточное подмножество вышеупомянутых законов состоит из пар законов ассоциативности, коммутативности и поглощения, дистрибутивности по (или другого закона дистрибутивности – достаточно одного) и двух законов дополнения.

Введение дополнительных законов, не перечисленных выше, позволяет еще больше сократить список; например, с вертикальной чертой, представляющей операцию штриха Шеффера , одной аксиомы достаточно, чтобы полностью аксиоматизировать булеву алгебру. Также возможно найти более длинные одиночные аксиомы, используя более традиционные операции; см. Минимальные аксиомы булевой алгебры .
((а∣б)∣c)∣(а∣((а∣c)∣а))знак равноc{ Displaystyle ((а середина б) середина с) середина (а середина ((а середина с) середина а)) = с}

Булева алгебра

Вторичные операции

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

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

Материал условный

Первая операция x  →  y или C xy называется материальной импликацией . Если x истинно, то значение x  →  y принимается равным y (например, если x истинно, а y ложно, то x  →  y также ложно). Но если x ложно, то значение y можно игнорировать; однако операция должна возвращать какое-то логическое значение, и есть только два варианта. Таким образом , по определению, х  →  у является истинным , когда х является ложным. ( Логика релевантности предлагает это определение, рассматривая импликацию с ложной предпосылкой как нечто иное, чем истинное или ложное.)

Исключающее ИЛИ ( XOR )

Вторая операция, x  ⊕  y , или J xy , называется исключающей или (часто сокращенно XOR), чтобы отличать ее от дизъюнкции как включающей. Это исключает возможность того, что оба x и y будут истинными (например, см. Таблицу): если оба истинны, то результат будет ложным. С точки зрения арифметики это сложение, где mod 2 равен 1 1 = 0.

Логическая эквивалентность

Третья операция, дополнение к исключающему или, является эквивалентностью или логическим равенством: x  ≡  y , или E xy , истинна только тогда, когда x и y имеют одинаковое значение. Следовательно, x  ⊕  y как его дополнение может пониматься как x  ≠  y , что верно только тогда, когда x и y различны. Таким образом, его аналог в арифметическом модуле 2 – x y . Аналог эквивалентности в арифметическом модуле 2 – x y 1.

Учитывая два операнда, каждый с двумя возможными значениями, существует 2 2 = 4 возможных комбинации входных данных. Поскольку каждый выход может иметь два возможных значения, всего имеется 2 4 = 16 возможных двоичных логических операций .

Двузначная логика

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

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

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

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

Двузначная логика может быть расширена до многозначной логики , в частности, путем замены логической области {0, 1} единичным интервалом [0,1], и в этом случае вместо того, чтобы принимать только значения 0 или 1, любое значение между и включая 0 и 1. Алгебраически отрицание (НЕ) заменяется на 1 –  x , конъюнкция (И) заменяется умножением ( ), а дизъюнкция (ИЛИ) определяется с помощью закона Де Моргана . Интерпретация этих значений как логических значений истинности дает многозначную логику, которая формирует основу нечеткой логики и вероятностной логики . В этих интерпретациях значение интерпретируется как «степень» истинности – насколько истинно предложение или вероятность того, что предложение истинно.
Иксу{ displaystyle xy}

Диаграммы венна

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

Три диаграммы Венна на рисунке ниже представляют соответственно конъюнкцию x ∧ y , дизъюнкцию x ∨ y и дополнение ¬ x .

Рис. 2. Диаграммы Венна для конъюнкции, дизъюнкции и дополнения.

Для соединения область внутри обоих кругов заштрихована, чтобы указать, что 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 ) ∧ (¬ y ) = ¬ ( x ∨ y ), начните со средней диаграммы для x ∨ y и дополните ее штриховкой так, чтобы была заштрихована только область за пределами обоих кругов, что это то, что описывает правая часть закона.

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

Второй закон Де Моргана, (¬ x ) ∨ (¬ y ) = ¬ ( x ∧ y ), работает таким же образом, если поменять местами две диаграммы.

Первый закон дополнения, x ∧¬ x = 0, гласит, что внутренняя и внешняя части круга x не перекрываются. Второй закон дополнения, x ∨¬ x = 1, говорит, что все находится либо внутри, либо вне круга x .

Историческая перспектива

• Джордж Буль (1848). « Исчисление логики », Cambridge and Dublin Mathematical Journal III: 183–98.
• Теодор Хайльперин (1986). Логика Буля и вероятность: критическое изложение с точки зрения современной алгебры, логики и теории вероятностей (2-е изд.). Эльзевир. ISBN 978-0-444-87952-3.
• Дов М. Габбей, Джон Вудс, изд. (2004). Возникновение современной логики: от Лейбница до Фреге . Справочник по истории логики. 3 . Эльзевир. ISBN 978-0-444-51611-4., несколько соответствующих глав от Hailperin, Valencia и Grattan-Guinness
• Каликсто Бадеса (2004). Рождение теории моделей: теорема Левенгейма в рамках теории родственников . Издательство Принстонского университета. ISBN 978-0-691-05853-5., глава 1, «Алгебра классов и исчисление высказываний»
• Беррис, Стэнли, 2009. Алгебра логической традиции . Стэнфордская энциклопедия философии .
• Радомир С. Станкович; Яакко Астола (2021). От булевой логики к коммутационным схемам и автоматам: к современным информационным технологиям . Springer. ISBN 978-3-642-11681-0.

История

Предшественник булевой алгебры был Лейбниц «ы алгеброй понятий . Алгебра понятий Лейбница дедуктивно эквивалентна булевой алгебре множеств.

Алгебра Буля предшествовала современному развитию абстрактной алгебры и математической логики ; однако считается, что он связан с истоками обеих областей. В абстрактном контексте булева алгебра была усовершенствована в конце 19 века Джевонсом , Шредером , Хантингтоном и другими, пока не достигла современной концепции (абстрактной) математической структуры .

Например, эмпирические наблюдения , что можно манипулировать выражения в алгебре множеств , переводя их в выражения в алгебре Буля, объясняется в современных условиях, говоря , что алгебра множеств Булева алгебра (обратите внимание на неопределенный артикль ).

На самом деле, М. Стоун доказал в 1936 году , что каждая булева алгебра изоморфна к области наборов .

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

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

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

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

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

Проблема определения , является ли переменные данной булевой (пропозициональных) формулы могут быть назначены таким образом, чтобы сделать формулу оценки истина называется проблемой Булева выполнимость (СБ), и имеет важное значение для теоретической информатики , будучи первая задача оказалась NP-полной .

Компьютеры

В начале 20 века несколько инженеров-электриков интуитивно поняли, что булева алгебра аналогична поведению определенных типов электрических цепей. Клод Шеннон формально доказал, что такое поведение логически эквивалентно булевой алгебре в своей магистерской диссертации 1937 года « Символьный анализ реле и коммутационных схем» .

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

Конечно, на любом носителе можно закодировать более двух символов. Например, можно использовать соответственно 0, 1, 2 и 3 вольта для кодирования четырехсимвольного алфавита на проводе или отверстий разных размеров в перфокарте. На практике жесткие ограничения, связанные с высокой скоростью, малым размером и малой мощностью, в совокупности делают шум основным фактором.

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

Компьютеры используют логические схемы с двумя значениями по указанным выше причинам. Наиболее распространенные компьютерные архитектуры используют упорядоченные последовательности логических значений, называемые битами, из 32 или 64 значений, например 01101000110101100101010101001011.

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

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

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

Конкретные булевы алгебры

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

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

Однако это исключение противоречит предпочтительному чисто эквациональному определению «булевой алгебры», поскольку нет способа исключить одноэлементную алгебру, используя только уравнения – 0 ≠ 1 не считается, будучи отрицательным уравнением. Следовательно, современные авторы допускают вырожденное Булева алгебра и пусть X пусто.)

Пример 1. силовой агрегат 2 X из X , состоящее из всех подмножеств из X . Здесь X может быть любым множеством: пустым, конечным, бесконечным или даже несчетным .

Пример 2. Пустое множество и Х . Эта двухэлементная алгебра показывает, что конкретная булева алгебра может быть конечной, даже если она состоит из подмножеств бесконечного множества. Можно видеть , что каждое поле подмножеств X должно содержать пустое множество и X .

Пример 3. Множество конечных и конфинитных множеств целых чисел, где конфинитное множество – это множество, пропускающее только конечное число целых чисел. Это явно замкнуто относительно дополнения и замкнуто относительно объединения, потому что объединение конфинитного множества с любым множеством конфинитно, в то время как объединение двух конечных множеств конечно. Пересечение ведет себя как союз с взаимозаменяемыми «конечным» и «кофинитным».

Пример 4. В качестве менее тривиального примера точки, сделанной в примере 2, рассмотрим диаграмму Венна, образованную n замкнутыми кривыми, разбивающими диаграмму на 2 n областей, и пусть X будет (бесконечным) множеством всех точек на плоскости, не лежащих на любая кривая, но где-то в пределах диаграммы.

Таким образом, внутренность каждой области представляет собой бесконечное подмножество X , и каждая точка в X находится ровно в одной области. Тогда множество всех 2 2 n возможных объединений регионов (включая пустое множество, полученное как объединение пустого множества регионов, и X, полученное как объединение всех 2 n регионов) замкнуто относительно объединения, пересечения и дополнения относительно X и, следовательно, образует конкретную булеву алгебру.

Логика высказываний

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

Синтаксически каждый логический термин соответствует пропозициональной формуле пропозициональной логики. В этом переводе между булевой алгеброй и логикой высказываний булевы переменные x, y … становятся пропозициональными переменными (или атомами )

P, Q , …, логические термины, такие как x ∨ y, становятся пропозициональными формулами P ∨ Q , 0 становится ложным. или ⊥ , и 1 становится истинным или Т .

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

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

Эта семантика допускает перевод между тавтологиями логики высказываний и эквациональными теоремами булевой алгебры. Всякая тавтология Φ логики высказываний может быть выражена как булево уравнение Φ = 1, которое будет теоремой булевой алгебры. Наоборот, каждая теорема Φ = Ψ булевой алгебры соответствует тавтологиям (Φ∨¬Ψ) ∧ (¬Φ∨Ψ) и (Φ∧Ψ) ∨ (¬Φ∧¬Ψ).

Логические функции двух переменных

Функция	Название	Обозначение
	Константа нуля	или False
	Логическое умножение, конъюнкция, “И”	или или или
	Запрет по	или
	Переменная
	Запрет по	или
	Переменная
	Сложение по модулю 2, отрицание эквивалентности, исключающее “ИЛИ”	или или
	Логическое сложение, дизъюнкция, “ИЛИ”	или или или
	Функция Пирса (Вебба), “ИЛИ-НЕ”	или или
	Логическая равнозначность, эквиваленция	или или или
	Отрицание
	Правая импликация	или
	Отрицание
	Левая импликация	или
	Функция Шеффера, “И-НЕ”	или или
	Константа единицы	или True

Ниже дана таблица истинности для логических функций от двух переменных.

В логических схемах функции могут быть реализованы с произвольных количеством
входных переменных, примеры – в материале Логические схемы и таблицы истинности.

Немонотонные законы

Операция дополнения определяется следующими двумя законами.

Дополнение 1Икс∧¬Иксзнак равно0Дополнение 2Икс∨¬Иксзнак равно1{ displaystyle { begin {align} & { text {Complementation 1}} & x wedge neg x & = 0 \ & { text {Complementation 2}} & x vee neg x & = 1 end {выровнено} }}

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

Как в обычной, так и в булевой алгебре отрицание работает путем обмена парами элементов, поэтому в обеих алгебрах оно удовлетворяет закону двойного отрицания (также называемому законом инволюции)

Двойное отрицание¬(¬Икс)знак равноИкс{ displaystyle { begin {align} & { text {двойное отрицание}} & neg {( neg {x})} & = x end {align}}}

Но в то время как обычная алгебра удовлетворяет двум законам

(-Икс)(-у)знак равноИксу(-Икс) (-у)знак равно-(Икс у){ Displaystyle { begin {выровнено} (- х) (- у) & = ху \ (- х) (- у) & = – (х у) конец {выровнено}}}

Булева алгебра удовлетворяет законам Де Моргана :

Де Морган 1¬Икс∧¬узнак равно¬(Икс∨у)Де Морган 2¬Икс∨¬узнак равно¬(Икс∧у){ displaystyle { begin {align} & { text {De Morgan 1}} & neg x wedge neg y & = neg {(x vee y)} \ & { text {Де Морган 2} } & neg x vee neg y & = neg {(x wedge y)} end {align}}}

Последовательное исчисление

Исчисление высказываний обычно организовано как система Гильберта , операции которой аналогичны операциям булевой алгебры, а теоремы являются булевыми тавтологиями, а эти булевы члены равны булевой константе 1. Другой формой является исчисление секвенций , которое имеет два вида предложений, как и в обычном исчисление высказываний и пары списков предложений, называемых секвенциями , такие как A ∨ B , A ∧ C , … A , B → C , …. Две половины секвенции называются антецедентом и преемником соответственно. Обычной метапеременной, обозначающей антецедент или его часть, является Γ, а для преемника Δ; таким образом, Γ, A ∆ будет обозначать секвенцию, преемником которой является список ∆, а антецедентом – список Γ с добавленным после него дополнительным предложением A. Антецедент интерпретируется как соединение его предложений, преемник – как разъединение его предложений, а сама секвенция – как следствие преемника антецедентом.
⊢{ displaystyle vdash}⊢{ displaystyle vdash}Вступление отличается от импликации тем, что, в то время как последняя является бинарной операцией , возвращающей значение в булевой алгебре, первая представляет собой бинарное отношение, которое либо выполняется, либо не выполняется. В этом смысле следствие – это внешняя форма импликации, то есть внешняя по отношению к булевой алгебре, когда мы думаем о читателе секвенции как о внешнем и интерпретируем и сравниваем антецеденты и последователи некоторой булевой алгебры. Естественная интерпретация как ≤ в частичном порядке булевой алгебры, определяемом как x ≤ y, как раз тогда, когда x ∨ y = y . Эта способность сочетать внешнюю импликацию и внутреннюю импликацию → в единой логике – одно из существенных различий между последовательным исчислением и пропозициональным исчислением.
⊢{ displaystyle vdash}⊢{ displaystyle vdash}

Представимые булевы алгебры

Хотя каждая конкретная булева алгебра является булевой алгеброй, не каждая булева алгебра должна быть конкретной. Пусть n будет положительным целым числом без квадратов , которое не делится на квадрат целого числа, например 30, но не 12.

Операции наибольшего общего делителя , наименьшего общего кратного и деления на n (то есть ¬ x = n / x ), можно показать, что они удовлетворяют всем логическим законам, когда их аргументы превышают положительные делители числа n .

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

Булева алгебра называется представимой, если она изоморфна конкретной булевой алгебре.

На следующий очевидный вопрос можно дать положительный ответ.

Всякая булева алгебра представима.

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

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

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

Принцип двойственности

Принцип: если {X, R} – это чум , то {X, R (обратный)} также чум.

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

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

Но если помимо обмена именами значений мы также поменяем местами имена двух бинарных операций, то теперь не останется и следа того, что мы сделали. Конечный продукт совершенно неотличим от того, с чего мы начали. Мы могли бы заметить, что столбцы для 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 .

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

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

Цифровые логические вентили

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

Слева направо: ворота «

И»

, «

ИЛИ»

и «

НЕ»

.

Линии слева от каждого затвора представляют входные провода или порты . Значение входа представлено напряжением на проводе. Для так называемой логики «активный высокий» 0 представлен напряжением, близким к нулю или «землей», а 1 представлен напряжением, близким к напряжению питания; active-low меняет это положение на противоположное.

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

Принцип двойственности , или законы Де Моргана , можно понимать как утверждение, что дополнение всех трех портов логического элемента И преобразует его в логический элемент ИЛИ и наоборот, как показано на рисунке 4 ниже. Однако добавление обоих портов инвертора оставляет работу без изменений.

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

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

Две из них – это константы 0 и 1 (как двоичные операции, которые игнорируют оба их входа); четыре – это операции, которые нетривиально зависят ровно от одного из двух входов, а именно x , y , ¬ x и ¬ y ; а остальные две являются х ⊕ у (исключающее ИЛИ ) и его дополнение х ≡ у .