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

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

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

История [ править ]

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

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

В 1930-х годах, изучая схемы переключения , Клод Шеннон заметил, что можно также применить правила алгебры Буля в этом контексте ^[8], и он представил алгебру переключения как способ анализа и проектирования схем алгебраическими средствами в терминах логических вентилей. . Шеннон уже имел в своем распоряжении абстрактный математический аппарат, поэтому он представил свою переключающую алгебру как двухэлементную булеву алгебру . В современных установках схемотехники нет необходимости рассматривать другие булевы алгебры, поэтому «алгебра переключения» и «булева алгебра» часто используются как взаимозаменяемые. ^{[9] [10] [11]}

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

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

Хотя развитие математической логики не следовало программе Буля, связь между его алгеброй и логикой позже была прочно обоснована в контексте алгебраической логики , которая также изучает алгебраические системы многих других логик. ^[7] проблема определения , является ли переменные данной булевой (пропозициональными) формулами могут быть назначена таким образом, чтобы сделать формулу оценки истины называется проблемой булевой выполнимости (СБ), и имеет важное значение для теоретического компьютера наука , являясь первой проблемой, NP-завершенной . Тесно связанная модель вычислений, известная как логическая схемасвязывает временную сложность ( алгоритма ) со сложностью схемы .

Ценности [ править ]

В то время как выражения обозначают в основном числа в элементарной алгебре, в булевой алгебре они обозначают истинные значения false и true . Эти значения представлены битами (или двоичными цифрами), а именно 0 и 1. Они не ведут себя как целые числа 0 и 1, для которых 1 + 1 = 2 , но могут быть идентифицированы с элементами двухэлементного поля. GF (2) , то есть целочисленная арифметика по модулю 2 , для которой 1 + 1 = 0 . Сложение и умножение затем играют булевы роли XOR (исключающее ИЛИ) и AND (соединение), соответственно, с дизъюнкцией x ∨ y(включительно-или) определяется как x + y - xy .

Булева алгебра также имеет дело с функциями , значения которых находятся в наборе {0, 1}. Для таких функций обычно используется последовательность битов . Другим распространенным примером является подмножеств множества Е : к подмножеству F из Е , можно определить функцию индикатора , который принимает значение 1 на F , и 0 вне F . Самый общий пример - это элементы булевой алгебры , и все вышеперечисленное является их примерами.

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

Операции [ править ]

Основные операции [ править ]

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

• 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 могут быть выражены путем табулирования их значений с таблицами истинности следующим образом:

${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\wedge y}$ ${\displaystyle x\vee y}$ 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1

${\displaystyle x}$ ${\displaystyle \neg x}$ 0 1 1 0

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

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

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

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

Вторичные операции [ править ]

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

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

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

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

${\displaystyle x}$	${\displaystyle y}$	${\displaystyle x\rightarrow y}$	${\displaystyle x\oplus y}$	${\displaystyle 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 ложно. ( Логика релевантности предлагает это определение, рассматривая импликацию с ложной предпосылкой как нечто иное, чем истинное или ложное.)

Вторая операция, x  ⊕  y , ^[1] или 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 ² = 4 возможных комбинации входных данных. Поскольку каждый выход может иметь два возможных значения, всего имеется 2 ⁴ = 16 возможных двоичных логических операций . Любая такая операция или функция (а также любая логическая функция с большим количеством входов) может быть выражена с помощью базовых операций, указанных выше. Следовательно, основные операции функционально завершены .

Законы [ править ]

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

Монотонные законы [ править ]

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

Ассоциативность :${\displaystyle \vee }$		${\displaystyle x\vee (y\vee z)}$	${\displaystyle =(x\vee y)\vee z}$
Ассоциативность :${\displaystyle \wedge }$		${\displaystyle x\wedge (y\wedge z)}$	${\displaystyle =(x\wedge y)\wedge z}$
Коммутативность :${\displaystyle \vee }$		${\displaystyle x\vee y}$	${\displaystyle =y\vee x}$
Коммутативность :${\displaystyle \wedge }$		${\displaystyle x\wedge y}$	${\displaystyle =y\wedge x}$
Распределение более :${\displaystyle \wedge }$${\displaystyle \vee }$		${\displaystyle x\wedge (y\vee z)}$	${\displaystyle =(x\wedge y)\vee (x\wedge z)}$
Идентичность для :${\displaystyle \vee }$		${\displaystyle x\vee 0}$	${\displaystyle =x}$
Идентичность для :${\displaystyle \wedge }$		${\displaystyle x\wedge 1}$[19]	${\displaystyle =x}$
Аннигилятор для :${\displaystyle \wedge }$		${\displaystyle x\wedge 0}$	${\displaystyle =0}$

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

Аннигилятор для :${\displaystyle \vee }$		${\displaystyle x\vee 1}$	${\displaystyle =1}$[19]
Идемпотентность :${\displaystyle \vee }$		${\displaystyle x\vee x}$	${\displaystyle =x}$
Идемпотентность :${\displaystyle \wedge }$		${\displaystyle x\wedge x}$	${\displaystyle =x}$
Поглощение 1:		${\displaystyle x\wedge (x\vee y)}$	${\displaystyle =x}$
Поглощение 2:		${\displaystyle x\vee (x\wedge y)}$	${\displaystyle =x}$
Распределение более :${\displaystyle \vee }$${\displaystyle \wedge }$		${\displaystyle x\vee (y\wedge z)}$	${\displaystyle =(x\vee y)\wedge (x\vee z)}$

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

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

Немонотонные законы [ править ]

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

${\displaystyle {\begin{aligned}&{\text{Complementation 1}}&x\wedge \neg x&=0\\&{\text{Complementation 2}}&x\vee \neg x&=1\end{aligned}}}$^[19]

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

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

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

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

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

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

${\displaystyle {\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 (инверсия)} также чум.

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

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

Схематические изображения [ править ]

Диаграммы Венна [ править ]

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

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

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

Цифровые логические вентили [ править ]

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

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

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

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

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

Пример 4. В качестве менее тривиального примера точки, сделанной в примере 2, рассмотрим диаграмму Венна, образованную n замкнутыми кривыми, разбивающими диаграмму на 2 ⁿ областей, и пусть X будет (бесконечным) множеством всех точек на плоскости, не лежащих на любая кривая, но где-то в пределах диаграммы. Таким образом, внутренность каждой области представляет собой бесконечное подмножество X , и каждая точка в X находится ровно в одной области. Тогда множество всех 2 ^{2 n} возможных объединений регионов (включая пустое множество, полученное как объединение пустого множества регионов, и 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 не обязательно должны быть битовыми векторами или подмножествами, но могут быть чем угодно. Это приводит к более общему абстрактному определению.

Булева алгебра это любой набор с бинарными операциями ∧ и ∨ и одноместный операция ¬ на нем , удовлетворяющую булевы законы. ^[23]

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

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

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

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

Представимые булевы алгебры [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

Введение дополнительных законов, не перечисленных выше, позволяет еще больше сократить список. В 1933 году Эдвард Хантингтон показал, что если в качестве базовых операций взять x ∨ y и ¬ x , то x ∧ y считается производной операцией (например, с помощью закона Де Моргана в форме x ∧ y = ¬ (¬ x ∨¬ y )), то уравнение ¬ (¬ x ∨¬ y ) ∨¬ (¬ x ∨ y ) = xвместе с двумя уравнениями, выражающими ассоциативность и коммутативность полностью аксиоматизированной булевой алгебры. Когда единственной базовой операцией является бинарная операция И-НЕ ¬ ( x ∧ y ), Стивен Вольфрам в своей книге A New Kind of Science предложил единственную аксиому (( xy ) z ) ( x (( xz ) x )) = z как аксиоматизация булевой алгебры с одним уравнением, где для удобства здесь xy обозначает И-НЕ, а не И для x и y .

Логика высказываний [ править ]

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

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

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

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

Приложения [ править ]

Одним из мотивирующих приложений исчисления высказываний является анализ предложений и дедуктивных аргументов на естественном языке. ^[24] В то время как утверждение «если x = 3, то x +1 = 4» зависит от значений таких символов, как + и 1, утверждение «если x = 3, то x = 3» - нет; это верно только в силу своей структуры и остается верным независимо от того, заменяется ли « x = 3» на « x = 4» или «луна сделана из зеленого сыра». Общая или абстрактная форма этой тавтологии - «если P, то P », или на языке булевой алгебры »P → P ". ^{[цитата необходима ]}

Замена P от й = 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 ).

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

Дедуктивные системы для логики высказываний [ править ]

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

Последовательное исчисление [ править ]

Исчисление высказываний обычно организовано как система Гильберта , операции которой аналогичны операциям булевой алгебры, а теоремы являются булевыми тавтологиями, а эти булевы члены равны булевой константе 1. Другой формой является исчисление секвенций , которое имеет два вида предложений, как и в обычном исчисление высказываний и пары списков предложений, называемые секвентами , такие как A ∨ B , A ∧ C , ... A , B → C${\displaystyle \vdash }$ , .... Две половины секвенции называются антецедентом и преемником соответственно. Обычной метапеременной, обозначающей антецедент или его часть, является Γ, а для преемника Δ; таким образом, Γ, A ∆ будет обозначать секвенцию, преемником которой является список ∆, а антецедентом - список Γ с дополнительным предложением A, добавленным после него. Антецедент интерпретируется как соединение его предложений, преемник - как разъединение его предложений, а сама секвенция - как следствие наследника антецедентом.${\displaystyle \vdash }$

Вступление отличается от импликации тем, что, в то время как последняя является бинарной операцией , возвращающей значение в булевой алгебре, первая представляет собой бинарное отношение, которое либо выполняется, либо не выполняется. В этом смысле следствие - это внешняя форма импликации, то есть внешняя по отношению к булевой алгебре, когда мы думаем о читателе секвенции как о внешнем и интерпретируем и сравниваем антецеденты и последователи в некоторой булевой алгебре. Естественная интерпретация как ≤ в частичном порядке булевой алгебры, определяемом как x ≤ y, как раз тогда, когда x ∨ y = y . Эта способность смешивать внешние последствия${\displaystyle \vdash }$${\displaystyle \vdash }$и внутренняя импликация → в одной логике - одно из существенных различий между исчислением секвенций и исчислением высказываний. ^[26]

Приложения [ править ]

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

Компьютеры [ править ]

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

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

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

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

Двузначная логика [ править ]

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

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

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

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

Логические операции [ править ]

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

Естественный язык [ править ]

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

Цифровая логика [ править ]

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

Наивная теория множеств [ править ]

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

Видеокарты [ править ]

Свободная 256-элементная булева алгебра на трех генераторах развернута в компьютерных дисплеях на основе растровой графики , которые используют битовое преобразование для управления целыми областями, состоящими из пикселей , полагаясь на логические операции, чтобы указать, как исходная область должна быть объединена с местом назначения, обычно с помощью третьей области, называемой маской . Современные видеокарты предлагают все 2 ^{2 3} = 256 тернарных операций для этой цели, причем выбор операции является однобайтовым (8-битным) параметром. Константы SRC = 0xaa или 10101010, DST = 0xcc или 11001100 и MSK = 0xf0 или 11110000 позволяют записывать логические операции, такие как (SRC ^ DST) и MSK (то есть XOR источника и назначения, а затем AND результат с маской) непосредственно как константа, обозначающая байт, вычисленный во время компиляции, 0x60 в примере (SRC ^ DST) и MSK, 0x66, если просто SRC ^ DST, и т. д. Во время выполнения видеокарта интерпретирует байт как растровую операцию, указанную исходным выражением единообразным способом, который требует очень мало оборудования и времени, полностью независимого от сложности выражения.

Моделирование и САПР [ править ]

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

Логический поиск [ править ]

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

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

«Поисковый запрос 1» «Поисковый запрос 2»

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

"Поисковый запрос 1" ИЛИ "Поисковый запрос 2"

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

"Поисковый запрос 1" - "Поисковый запрос 2"

См. Также [ править ]

Ссылки [ править ]

Источники [ править ]

• Мано, Моррис; Чилетти, Майкл Д. (2013). Цифровой дизайн . Пирсон. ISBN 978-0-13-277420-8.

Дальнейшее чтение [ править ]

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

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

• Джордж Буль (1848). « Исчисление логики », Кембриджский и Дублинский математический журнал 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. Алгебра логической традиции . Стэнфордская энциклопедия философии .
• Радомир С. Станкович; Яакко Астола (2011). От булевой логики к коммутационным схемам и автоматам: к современным информационным технологиям . Springer. ISBN 978-3-642-11681-0.

Внешние ссылки [ править ]

В Wikibook How To Search есть страница по теме: Логическая логика

В Викибуке Электроника есть страница по теме: Булева алгебра

• Глава булевой алгебры на Все о схемах
• Как работает Stuff - логическая логика
• Наука и технологии - Булева алгебра содержит список и доказательства булевых теорем и законов.