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

Чтобы узнать о других значениях, см. Булеву алгебру (значения) .

В математике и математической логике булева алгебра является разделом алгебры . Она отличается от элементарной алгебры двумя способами. Во-первых, значения переменных — это истинностные значения true и false , обычно обозначаемые 1 и 0, тогда как в элементарной алгебре значения переменных являются числами. Во-вторых, булева алгебра использует логические операторы, такие как конъюнкция ( и ), обозначаемая как ∧ , дизъюнкция ( или ), обозначаемая как ∨ , и отрицание ( not ), обозначаемое как ¬ . С другой стороны, элементарная алгебра использует арифметические операторы, такие как сложение, умножение, вычитание и деление. Таким образом, булева алгебра представляет собой формальный способ описания логических операций , точно так же, как элементарная алгебра описывает числовые операции.

Булева алгебра была представлена ​​Джорджем Булем в его первой книге «Математический анализ логики» (1847 г.). и более полно изложено в его «Исследовании законов мышления» (1854 г.). По мнению Хантингтона , термин «булева алгебра» был впервые предложен Генри М. Шеффером в 1913 году. хотя Чарльз Сандерс Пирс дал название «Булевая [ sic ] алгебра с одной константой» первой главе своей «Простейшей математики» в 1880 году. Булева алгебра сыграла фундаментальную роль в развитии цифровой электроники и предусмотрена во всех современных языках программирования . Он также используется в теории множеств и статистике .

История

Предшественником булевой алгебры была Готфрида Вильгельма Лейбница алгебра понятий . Использование двоичного числа по отношению к « И Цзин» Лейбница было центральным в «универсальной характеристике» . В конечном итоге это создало основы алгебры понятий. Алгебра понятий Лейбница дедуктивно эквивалентна булевой алгебре множеств.

Алгебра Буля предшествовала современным разработкам в абстрактной алгебре и математической логике ; однако считается, что это связано с происхождением обеих областей. В абстрактной форме булева алгебра была усовершенствована в конце 19 века Джевонсом , Шрёдером , Хантингтоном и другими, пока не достигла современной концепции (абстрактной) математической структуры . Например, эмпирическое наблюдение о том, что можно манипулировать выражениями в алгебре множеств , переводя их в выражения в алгебре Буля, объясняется в современных терминах тем, что алгебра множеств является булевой алгеброй (обратите внимание на неопределенный артикль ). Фактически, М. Х. Стоун доказал в 1936 году , что каждая булева алгебра изоморфна полю множеств .

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

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

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

Хотя развитие математической логики не шло по программе Буля, связь его алгебры с логикой позже была заложена прочно в рамках алгебраической логики , изучающей также алгебраические системы многих других логик. Проблема определения того, могут ли переменные данной булевой (пропозициональной) формулы быть назначены таким образом, чтобы сделать формулу истинной, называется проблемой булевой выполнимости (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. Другим распространенным Самый общий пример — множество элементов булевой алгебры , причем все вышеперечисленное является их экземплярами.

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

Операции

Дополнительная информация: Таблица истинности.

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

В то время как элементарная алгебра имеет четыре операции (сложение, вычитание, умножение и деление), булева алгебра имеет только три основные операции: соединение , дизъюнкция и отрицание , выраженные с помощью соответствующих бинарных операторов AND ( $\land$) и ИЛИ ( $\lor$) и унарный оператор NOT ( $\neg$), которые вместе называются логическими операторами . Переменные в булевой алгебре, которые хранят логические значения 0 и 1, называются логическими переменными . Они используются для хранения истинных или ложных значений. Основные операции над логическими переменными x и y определяются следующим образом:

Логическая операция	Оператор	Обозначения	Альтернативные обозначения	Определение
Соединение	И	х ∧ у	х И у , К ху	x ∧ y = 1, если x = y = 1, x ∧ y = 0 в противном случае
Дизъюнкция	ИЛИ	х ∨ у	x ИЛИ y , A xy	x ∨ y = 0, если x = y = 0, x ∨ y = 1 в противном случае
Отрицание	НЕТ	¬ x	НЕ x , N x , x̅ , x' , ! х	¬ x = 0, если x = 1, ¬ x = 1, если x = 0

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

$x$	$y$	$x\wedge y$	$x\vee y$
0	0	0	0
1	0	0	1
0	1	0	1
1	1	1	1

$x$	$\neg x$
0	1
1	0

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

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

${\begin{aligned}x\wedge y&=xy=\min(x,y)\\x\vee y&=x+y-xy=x+y(1-x)=\max(x,y)\\\neg x&=1-x\end{aligned}}$

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

${\begin{aligned}x\wedge y&=\neg (\neg x\vee \neg y)\\x\vee y&=\neg (\neg x\wedge \neg y)\end{aligned}}$

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

Операции, состоящие из основных операций, включают, среди прочего, следующие:

Материал условно :	${\textstyle x\rightarrow y=\neg {x}\vee y}$
Материал двуусловный :	${\textstyle x\leftrightarrow y=(x\land y)\lor (\neg x\land \neg y)=(x\lor \neg y)\land (\neg x\lor y)}$
Исключительное ИЛИ ( XOR ):	${\textstyle x\oplus y=\neg (x\leftrightarrow y)=(x\vee y)\wedge \neg (x\wedge y)=(x\vee y)\wedge (\neg x\vee \neg y)=(x\wedge \neg y)\vee (\neg x\wedge y)}$

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

Вторичные операции. Таблица 1

$x$	$y$	$x\rightarrow y$	$x\oplus y$	$x\leftrightarrow y,x\equiv y$
0	0	1	0	1
1	0	0	1	0
0	1	1	1	0
1	1	1	0	1

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

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

Эксклюзивное ИЛИ ( 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.

Законы

Закон определяется как выражение , булевой алгебры — это тождество, такое как x ∨ ( y ∨ z ) = ( x ∨ y ) ∨ z между двумя логическими терминами, где логический термин составленное из переменных и констант 0 и 1 с использованием операции ∧, ∨ и ¬. Эту концепцию можно распространить на термины, включающие другие логические операции, такие как ⊕, → и ≡, но такие расширения не являются необходимыми для целей, ради которых применяются законы. Такие цели включают определение булевой алгебры как любой модели булевых законов и как средства вывода новых законов из старых, как при выводе x ∨ ( y ∧ z ) = x ∨ ( z ∧ y ) из y ∧ z = z ∧ y (как это рассматривается в § Аксиоматизация булевой алгебры ).

Монотонные законы

Булева алгебра удовлетворяет многим тем же законам, что и обычная алгебра, когда сопоставляют ∨ со сложением и ∧ с умножением. В частности, следующие законы являются общими для обоих видов алгебры:

Ассоциативность ∨ :		$x\vee (y\vee z)$	$=(x\vee y)\vee z$
Ассоциативность ∧ :		$x\wedge (y\wedge z)$	$=(x\wedge y)\wedge z$
Коммутативность ∨ :		$x\vee y$	$=y\vee x$
Коммутативность ∧ :		$x\wedge y$	$=y\wedge x$
Дистрибутивность ∧ по ∨ :		$x\wedge (y\vee z)$	$=(x\wedge y)\vee (x\wedge z)$
Идентичность для ∨ :		$x\vee 0$	$=x$
Идентичность для ∧ :		$x\wedge 1$	$=x$
Аннигилятор для ∧ :		$x\wedge 0$	$=0$

Следующие законы выполняются в булевой алгебре, но не в обычной алгебре:

Аннигилятор для ∨ :		$x\vee 1$	$=1$
Идемпотентность ∨ :		$x\vee x$	$=x$
Идемпотентность ∧ :		$x\wedge x$	$=x$
Поглощение 1:		$x\wedge (x\vee y)$	$=x$
Поглощение 2:		$x\vee (x\wedge y)$	$=x$
Дистрибутивность ∨ по ∧ :		$x\vee (y\wedge z)$	$=(x\vee y)\wedge (x\vee z)$

Если принять x = 2 в третьем законе выше, это показывает, что это не обычный закон алгебры, поскольку 2 × 2 = 4 . Остальные пять законов можно фальсифицировать в обычной алгебре, приняв все переменные равными 1. Например, в законе поглощения 1 левая часть будет 1(1 + 1) = 2 , а правая часть будет 1 ( и так далее).

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

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

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

${\begin{aligned}&{\text{Complementation 1}}&x\wedge \neg x&=0\\&{\text{Complementation 2}}&x\vee \neg x&=1\end{aligned}}$

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

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

${\begin{aligned}&{\text{Double negation}}&\neg {(\neg {x})}&=x\end{aligned}}$

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

${\begin{aligned}(-x)(-y)&=xy\\(-x)+(-y)&=-(x+y)\end{aligned}}$

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

${\begin{aligned}&{\text{De Morgan 1}}&\neg x\wedge \neg y&=\neg {(x\vee y)}\\&{\text{De Morgan 2}}&\neg x\vee \neg y&=\neg {(x\wedge y)}\end{aligned}}$

Полнота

Перечисленные выше законы определяют булеву алгебру в том смысле, что они влекут за собой остальную часть предмета. законов Дополнения 1 и 2 вместе с монотонными законами достаточны для этой цели и поэтому могут быть приняты как один возможный полный набор законов или аксиоматизация булевой алгебры. Любой закон булевой алгебры логически вытекает из этих аксиом. Более того, булевы алгебры затем могут быть определены как модели этих аксиом, как это рассматривается в § Булевы алгебры .

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

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

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

Основная статья: Двойственность конъюнкции/дизъюнкции

Принцип: если {X, R} — частично упорядоченное множество , то {X, R(inverse)} — также частично упорядоченное множество.

В выборе символов для значений булевой алгебры нет ничего особенного. 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 .

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

Схематические изображения

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

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

Три диаграммы Венна на рисунке ниже представляют соответственно конъюнкцию 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 .

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

Цифровая логика — это применение булевой алгебры 0 и 1 к электронному оборудованию, состоящему из логических элементов, соединенных в принципиальную схему . Каждый вентиль реализует логическую операцию и схематически изображается формой, обозначающей операцию. Формы, связанные с воротами соединения (И-вентили), дизъюнкции (ИЛИ-вентили) и дополнения (инверторы), следующие:

Слева направо: вентили И , ИЛИ и НЕ .

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

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

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

В более общем смысле, можно дополнить любое из восьми подмножеств трех портов логического элемента И или ИЛИ. Полученные в результате шестнадцать возможностей порождают только восемь логических операций, а именно операций с нечетным числом единиц в таблице истинности. Таких восемь, потому что «нечетный бит» может быть либо 0, либо 1 и может занимать любую из четырех позиций в таблице истинности. Поскольку существует шестнадцать двоичных логических операций, в результате должно остаться восемь операций с четным числом единиц в таблицах истинности. Двумя из них являются константы 0 и 1 (как двоичные операции, игнорирующие оба входа); четыре — это операции, которые нетривиально зависят ровно от одного из двух входных данных, а именно x , y , ¬x и ¬y ; а остальные два — это x ⊕ y (XOR) и его дополнение x ≡ y .

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

Основная статья: Булева алгебра (структура)

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

алгебры

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

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

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

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

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

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

Подмножества в виде битовых векторов

Подмножество Y из X может быть идентифицировано с индексированным семейством битов с набором индексов X , причем бит, индексированный x ∈ X, равен 1 или 0 в зависимости от того, принадлежит ли x к Y или нет . (Это так называемое понятие характеристической функции подмножества.) Например, 32-битное компьютерное слово состоит из 32 битов, индексированных набором {0,1,2,...,31}, с 0 и 31. индексирование младших и старших битов соответственно. Для меньшего примера, если $X=\{a,b,c\}$ где 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. Однако, поскольку таких законов бесконечно много, на практике это неудовлетворительный ответ, что приводит к Для этого достаточно потребовать, чтобы соблюдалось лишь конечное число законов.

В случае булевых алгебр ответ «да»: достаточно конечного числа перечисленных выше уравнений. Таким образом, булева алгебра называется конечно аксиоматизируемой или конечно базируемой .

Более того, количество необходимых уравнений можно дополнительно сократить. Начнем с того, что некоторые из вышеперечисленных законов подразумеваются некоторыми другими. Достаточное подмножество вышеупомянутых законов состоит из пар законов ассоциативности, коммутативности и поглощения, дистрибутивности ∧ над ∨ (или другого закона дистрибутивности - одного достаточно) и двух законов дополнения. По сути, это традиционная аксиоматизация булевой алгебры как дополняемой дистрибутивной решетки .

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

Пропозициональная логика

Основная статья: Исчисление высказываний

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

Синтаксически каждый логический термин соответствует пропозициональной формуле логики высказываний. В этом переводе между булевой алгеброй и логикой высказываний логические переменные x, y, ... становятся пропозициональными переменными (или атомами ) P, Q , ... логические термины, такие как x ∨ y, становятся пропозициональными формулами P ∨ Q ; становится ложным или ⊥ , а 1 становится истинным или T. 0 При обращении к родовым высказываниям удобно использовать греческие буквы Φ, Ψ,... в качестве метапеременных (переменных вне языка исчисления высказываний, используемых, когда говорят об исчислении высказываний) для обозначения высказываний.

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

Эта семантика позволяет осуществлять перевод между тавтологиями логики высказываний и эквациональными теоремами булевой алгебры. Любую тавтологию Φ логики высказываний можно выразить как булево уравнение Φ = 1, которое будет теоремой булевой алгебры. Обратно, каждой теореме Φ = Ψ булевой алгебры соответствуют тавтологии (Φ ∨ ¬Ψ) ∧ (¬Φ ∨ Ψ) и (Φ ∧ Ψ) ∨ (¬Φ ∧ ¬Ψ). Если → есть в языке, эти последние тавтологии также можно записать как (Φ → Ψ) ∧ (Ψ → Φ) или как две отдельные теоремы Φ → Ψ и Ψ → Φ; если ≡ имеется, то можно использовать единственную тавтологию Φ ≡ Ψ.

Приложения

Одним из мотивирующих применений исчисления высказываний является анализ высказываний и дедуктивных аргументов на естественном языке. В то время как предложение «если х = 3, то х + 1 = 4» зависит от значений таких символов, как + и 1, предложение «если х = 3, то х = 3» не зависит; оно истинно лишь в силу своей структуры и остается истинным независимо от того, ли « х заменяется = 3» на « х = 4» или «луна сделана из зеленого сыра». Общая или абстрактная форма этой тавтологии: «если P , то P на языке булевой алгебры P → P. », или

Замена P на x = 3 или любое другое предложение называется созданием P с помощью этого предложения. Результат реализации P в абстрактном предложении называется экземпляром предложения. Таким образом, x = 3 → x поскольку является примером абстрактной тавтологии P → P. = 3 является тавтологией , Все экземпляры конкретной переменной должны быть созданы с помощью одного и того же предложения, чтобы избежать такой ерунды, как P → x = 3 или x = 3 → x = 4.

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

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

Дедуктивные системы для логики высказываний

Аксиоматизация исчисления высказываний представляет собой набор тавтологий, называемых аксиомами , и одно или несколько правил вывода для создания новых тавтологий из старых. Доказательство представляет собой конечную непустую последовательность предложений, каждое из в системе аксиом A которых либо является экземпляром аксиомы A , либо следует по некоторому правилу A из предложений, появившихся ранее в доказательстве (тем самым запрещая круговые рассуждения). Последнее предложение представляет собой теорему, доказанную доказательством. Каждый непустой начальный сегмент доказательства сам по себе является доказательством, следовательно, каждое предложение в доказательстве само по себе является теоремой. Аксиоматизация правильна , когда каждая теорема является тавтологией, и полна , когда каждая тавтология является теоремой.

Расчеты следуют

Основная статья: Секвенционное исчисление

Исчисление высказываний обычно организуется как система Гильберта , операции которой аналогичны операциям булевой алгебры, а теоремы представляют собой булевы тавтологии, булевы термины, равные булевой константе 1. Другой формой является секвенциальное исчисление , которое имеет два вида: предложения, как в обычном исчислении. исчисление высказываний и пары списков предложений, называемых секвенциями , такие как A ∨ B , A ∧ C , ... ⊢ A , B → C , .... Две половины секвенции называются антецедентом и последователем соответственно. . Обычная метапеременная, обозначающая антецедент или его часть, — это Γ, а для последующего Δ; таким образом, Γ, A ⊢ Δ будет обозначать секвенцию, преемником которой является список Δ, а антецедентом которого является список Γ с дополнительным предложением A. добавленным после него Антецедент интерпретируется как соединение своих предложений, последующее — как дизъюнкция своих предложений, а само секвенциальное — как следствие последующего по антецеденту.

Следствие отличается от импликации тем, что последняя представляет собой бинарную операцию , возвращающую значение в булевой алгебре, а первая представляет собой бинарное отношение , которое либо выполняется, либо не выполняется. В этом смысле следование - это внешняя форма импликации, то есть внешняя по отношению к булевой алгебре, думая о читателе секвенции как о внешнем, интерпретируя и сравнивая предшествующие и последующие элементы в некоторой булевой алгебре. Естественная интерпретация ⊢ — это как ≤ в частичном порядке булевой алгебры, определяемом x ≤ y, только тогда, когда x ∨ y = y . Эта способность смешивать внешнюю импликацию ⊢ и внутреннюю импликацию → в одной логике является одним из существенных различий между секвенциальным исчислением и исчислением высказываний.

Приложения

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

Компьютеры

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

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

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

Компьютеры используют логические схемы с двумя значениями по вышеуказанным причинам. Наиболее распространенные компьютерные архитектуры используют упорядоченные последовательности логических значений, называемые битами, из 32 или 64 значений, например 01101000110101100101010101001011. При программировании на машинном коде , языке ассемблера и некоторых других языках программирования программисты работают с низкоуровневой цифровой структурой регистры данных . Эти регистры работают с напряжением, где ноль вольт соответствует логическому значению 0, а опорное напряжение (часто +5 В, +3,3 В или +1,8 В) соответствует логическому значению 1. Такие языки поддерживают как числовые операции, так и логические операции. В этом контексте «числовой» означает, что компьютер обрабатывает последовательности битов как двоичные числа (числа по основанию два) и выполняет арифметические операции, такие как сложение, вычитание, умножение или деление. «Логический» относится к логическим операциям дизъюнкции, соединения и отрицания между двумя последовательностями битов, в которых каждый бит в одной последовательности просто сравнивается со своим аналогом в другой последовательности. Таким образом, программисты имеют возможность работать и применять правила числовой или булевой алгебры по мере необходимости. Основной отличительной особенностью этих семейств операций является наличие перенеси операцию в первое, но не во второе.

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

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

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

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

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

Булевы операции

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

Естественный язык

В естественных языках, таких как английский, есть слова для нескольких логических операций, в частности соединения ( и ), дизъюнкции ( или ), отрицания ( not ) и импликации ( подразумевает ). Но not является синонимом and not . Когда они используются для объединения ситуативных утверждений, таких как «блок лежит на столе» и «кошки пьют молоко», которые наивно либо истинны, либо ложны, значения этих логических связок часто имеют значения их логических аналогов. Однако при описании поведения, такого как «Джим вошел в дверь», начинают замечаться такие различия, как нарушение коммутативности, например, соединение «Джим открыл дверь» с «Джим вошел в дверь» именно в таком порядке. не эквивалентно их соединению в другом порядке, поскольку и обычно означает и то в таких случаях . Вопросы могут быть схожими: порядок «Небо голубое и почему небо голубое?» имеет больше смысла, чем обратный порядок. Конъюнктивные команды, касающиеся поведения, подобны поведенческим утверждениям, например, одеться и пойти в школу. . Разделительные команды, такие как «люби меня» или «оставь меня» , «лови рыбу» или «режь наживку», имеют тенденцию быть асимметричными, поскольку подразумевают, что одна альтернатива менее предпочтительна. Соединенные существительные, такие как чай и молоко, обычно описывают агрегацию как объединение множества, тогда как чай или молоко являются выбором. Однако контекст может изменить эти смыслы, поскольку ваш выбор — кофе и чай , что обычно означает то же самое, что ваш выбор — кофе или чай (альтернативы). Двойное отрицание, например «Я не люблю молоко», редко означает буквально «Я люблю молоко», а скорее передает своего рода страховку, как бы подразумевая, что существует третья возможность. «Не не Р» можно в общих чертах интерпретировать как «наверняка Р», и хотя Р обязательно подразумевает «не не Р », обратное в английском языке сомнительно, как и в интуиционистской логике . Ввиду весьма своеобразного использования союзов в естественных языках булева алгебра не может считаться надежной основой для их интерпретации.

Цифровая логика

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

Наивная теория множеств

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

Видеокарты

Свободная булева алгебра из 256 элементов на трех генераторах развертывается в компьютерных дисплеях на основе растровой графики , которые используют битовый блитинг для управления целыми областями, состоящими из пикселей , полагаясь на логические операции, чтобы указать, как исходная область должна быть объединена с целевой областью, обычно с помощью третьей области, называемой маской . Современные видеокарты предлагают все 2 ^{2 3} = 256 троичных операций для этой цели, при этом выбор операции осуществляется однобайтовым (8-битным) параметром. Константы SRC = 0xaa или 0b10101010 , Летнее время = 0xcc или 0b11001100 и MSK = 0xf0 или 0b11110000 разрешает логические операции, такие как (SRC^DST)&MSK (что означает XOR источника и назначения, а затем И результат с маской), который будет записан непосредственно как константа, обозначающая байт, рассчитанный во время компиляции, 0x80 в (SRC^DST)&MSK пример, 0x88, если просто SRC^DSTи т. д. Во время выполнения видеокарта интерпретирует байт как растровую операцию, указанную исходным выражением, единым способом, который требует очень мало аппаратных средств и занимает время, совершенно независимое от сложности выражения.

Моделирование и САПР

твердотельного моделирования Системы для автоматизированного проектирования предлагают множество методов построения объектов из других объектов, одним из которых является комбинация логических операций. понимается как набор S вокселей В этом методе пространство, в котором существуют объекты , (трехмерный аналог пикселей в двухмерной графике), а формы определяются как подмножества S , что позволяет объединять объекты в наборы посредством объединения. пересечение и т. д. Одно из очевидных применений — построение сложной формы из простых фигур просто как объединение последних. Другое использование - скульптура, понимаемая как удаление материала: любая операция шлифования, фрезерования, фрезерования или сверления, которая может быть выполнена с помощью физического оборудования на физических материалах, может быть смоделирована на компьютере с помощью логической операции x ∧ ¬ y или x - y , что в теории множеств является разностью множеств, удалите элементы y из элементов x . Таким образом, при наличии двух форм, одна из которых подлежит обработке, а другая представляет собой материал, который необходимо удалить, результат обработки первой для удаления второй описывается просто как их установленная разность.

Логический поиск

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

• Двойные кавычки используются для объединения слов, разделенных пробелами, в один поисковый запрос.
• Пробелы используются для указания логического И, поскольку это оператор по умолчанию для объединения условий поиска:

"Search term 1" "Search term 2"

• Ключевое слово OR используется для логического ИЛИ:

"Search term 1" OR "Search term 2"

• Для логического НЕ используется префиксный знак минус:

"Search term 1" −"Search term 2"

См. также

• Булевы алгебры канонически определены
• Булево дифференциальное исчисление
• Булео
• Канторова алгебра
• Алгебра Гейтинга
• Список тем по булевой алгебре
• Логический дизайн
• Математические принципы
• Трехзначная логика
• Векторная логика

Дальнейшее чтение

• Мано, Моррис; Силетти, Майкл Д. (2013). Цифровой дизайн . Пирсон. ISBN  978-0-13-277420-8 .
• Уайтситт, Дж. Элдон (1995). Булева алгебра и ее приложения . Публикации Courier Dover . ISBN  978-0-486-68483-3 .
• Двингер, Филип (1971). Введение в булевы алгебры . Вюрцбург, Германия: Physica Verlag.
• Сикорский, Роман (1969). Булевы алгебры (3-е изд.). Берлин, Германия: Springer Verlag . ISBN  978-0-387-04469-9 .
• Боченский, Юзеф Мария (1959). Краткое изложение математической логики . Перевод с французского и немецкого изданий Отто Берда. Дордрехт, Южная Голландия: Д. Рейдель.

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

• Буль, Джордж (1848). «Логическое исчисление» . Кембриджский и Дублинский математический журнал . III : 183–198.
• Хайльперин, Теодор (1986). Логика и вероятность Буля: критическое изложение с точки зрения современной алгебры, логики и теории вероятностей (2-е изд.). Эльзевир . ISBN  978-0-444-87952-3 .
• Габбай, Дов М.; Вудс, Джон, ред. (2004). Становление современной логики: от Лейбница до Фреге . Справочник по истории логики. Том. 3. Эльзевир . ISBN  978-0-444-51611-4 . , несколько соответствующих глав от Hailperin, Valencia и Grattan-Guinness.
• Бадеса, Каликсто (2004). «Глава 1. Алгебра классов и исчисление высказываний». Рождение теории моделей: теорема Левенгейма в рамках теории родственников . Издательство Принстонского университета . ISBN  978-0-691-05853-5 .
• Станкович, Радомир С. [на немецком языке] ; Астола, Яакко Тапио [на финском языке] (2011). Написано в Нише, Сербия, и Тампере, Финляндия. От булевой логики к коммутационным схемам и автоматам: на пути к современным информационным технологиям . Исследования в области вычислительного интеллекта. Том. 335 (1-е изд.). Берлин и Гейдельберг, Германия: Springer-Verlag . стр. xviii + 212. doi : 10.1007/978-3-642-11682-7 . ISBN  978-3-642-11681-0 . ISSN   1860-949X . LCCN   2011921126 . Проверено 25 октября 2022 г.
• «Алгебра логической традиции» Запись Берриса, Стэнли в Стэнфордской энциклопедии философии , 21 февраля 2012 г.