алгебра логики

1. значение [ ред. | ред. код ]
2. Предмет изучения [ ред. | ред. код ]
3. Базовые операции [ ред. | ред. код ]
4. Вторичные операции [ ред. | ред. код ]
5. Законы монотонности [ ред. | ред. код ]
6. Законы немонотонности [ ред. | ред. код ]
7. полнота [ ред. | ред. код ]
8. Принцип двойственности [ ред. | ред. код ]
9. Свойства логических операций [ ред. | ред. код ]
10. Представление в виде диаграмм [ ред. | ред. код ]
11. Цифровые логические цепи [ ред. | ред. код ]
12. Компьютеры [ ред. | ред. код ]

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

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

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

Высказывания строятся над множеством {B, ¬ {\ displaystyle \ lnot} , ∧ {\ displaystyle \ land} , ∨ {\ displaystyle \ lor} 0, 1}, где B - непустое множество, над элементами которой определены три операции :

¬ {\ displaystyle \ lnot} возражения

( унарная операция ) ∧ {\ displaystyle \ land} конъюнкция ( бинарная ) ∨ {\ displaystyle \ lor} дизъюнкция ( бинарная ), А логический ноль 0 и логическая единица 1 - константы .

Так же используются названия

Унарная операция отрицания в тексте формул оформляется либо в виде значка перед операндом (¬ x {\ displaystyle \ lnot x} ) Или в виде черты над операндом (x ¯ {\ displaystyle {\ bar {x}}} ), Что компактнее, но в целом менее заметно.

значение [ ред. | ред. код ]

В то время как в элементарной алгебре выражения как правило выражаются в числах , В алгебре логики они выражают значение истинности истина и ложь. Эти значения задают с помощью бит (Или двоичных чисел), а именно 0 и 1. Они не ведут себя так же как целые числа 0 и 1, для которых 1 + 1 = 2, а могут определяться как элементы двух- элементного поля GF (2) [En] , что является, целочисленных арифметикой по модулю 2 , Для которой 1 + 1 = 0 Алгебра логики также изучает функции , Принимающих значения в множестве {0, 1}.

Предмет изучения [ ред. | ред. код ]

Сначала проблематика алгебры логики пересекалась с проблематикой алгебры множеств (Теоретико-множественные операции).

Однако с окончанием формирования теории множеств ( Семидесятые годы 19 в. ), Которая включила в себя алгебру множеств, и дальнейшим развитием математической логики , Предмет алгебры логики значительно изменился.

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

Базовые операции [ ред. | ред. код ]

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

• И ( конъюнкция ), Сказывается x ∧ y (иногда x И y), удовлетворяет x ∧ y = 1, если x = y = 1 и x ∧ y = 0 в остальных случаях.
• ИЛИ ( дизъюнкция ), Сказывается x ∨ y (иногда x ИЛИ y), удовлетворяет x ∨ y = 0, если x = y = 0 и x ∨ y = 1 в других случаях.
• НЕТ ( возражения ), Сказывается ¬ x (иногда НЕ x или! X), удовлетворяет ¬ x = 0, если x = 1 и ¬ x = 1 if x = 0.

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

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

x ∧ y = xy = min (x, y) x ∨ y = x + y - xy = max (x, y) ¬ x = 1 - x {\ 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}}}

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

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

Вторичные операции [ ред. | ред. код ]

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

x → y = ¬ x ∨ y {\ displaystyle x \ rightarrow y = \ neg {x} \ vee y} x ⊕ y = (x ∨ y) ∧ ¬ (x ∧ y) = (x ∧ ¬ y) ∨ (¬ x ∧ y) {\ displaystyle x \ oplus y = (x \ vee y) \ wedge \ neg {( x \ wedge y)} = (x \ wedge \ neg y) \ vee (\ neg x \ wedge y)} x ≡ y = ¬ (x ⊕ y) = (x ∧ y) ∨ (¬ x ∧ ¬ y) {\ displaystyle x \ equiv y = \ neg {(x \ oplus y)} = (x \ wedge y) \ vee (\ neg x \ wedge \ neg y)}

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

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

Вторая операция, x ⊕ y, называется исключительной дизъюнкцией (Часто задается как аббревиатура XOR), чтобы отличить ее от дизъюнкции. Она является истиной, только когда x и y разные.

Третья операция, обратная к исключительной дизъюнкции, называется эквивалентность или булева равенство: x ≡ y будет истиной, только когда x и y имеют одинаковое значение.

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

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

Законы монотонности [ ред. | ред. код ]

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

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

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

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

Законы немонотонности [ ред. | ред. код ]

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

Дополнение 1 x ∧ ¬ x = 0 дополнения 2 x ∨ ¬ x = 1 {\ displaystyle {\ begin {aligned} & {\ text {Дополнение 1}} & x \ wedge \ neg x & = 0 \\ & {\ text {Дополнение 2}} & x \ vee \ neg x & = 1 \ end {aligned}}}

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

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

Двойное отрицание ¬ (¬ x) = x {\ displaystyle {\ begin {aligned} & {\ text {двойное отрицание}} & \ neg {(\ neg {x})} & = x \ end {aligned}}}

Но если «обычная алгебра» удовлетворяет следующим двум законам

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

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

де Моргана 1 ¬ x ∧ ¬ y = ¬ (x ∨ y) где Моргана 2 ¬ x ∨ ¬ y = ¬ (x ∧ y) {\ displaystyle {\ begin {aligned} & {\ text {де Моргана 1}} & \ neg x \ wedge \ neg y & = \ neg {(x \ vee y)} \\ & {\ text {де Моргана 2}} & \ neg x \ vee \ neg y & = \ neg {(x \ wedge y) } \ end {aligned}}}

полнота [ ред. | ред. код ]

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

Принцип двойственности [ ред. | ред. код ]

Принцип Если {X, R} - частично упорядоченное множество , Тогда {X, R (обратная)} также частично упорядоченное множество.

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

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

Но если в дополнение к тому, что мы заменили местами имена переменных, мы заменим местами имена двух двоичных операций, теперь нет никакого следа от того что мы сделали. Конечный результат полностью не отличается от того, с чего мы начали. Мы заметим, что колонки для операций x ∧ y и x ∨ y в таблицах истинности изменили свои места, но это различие незначительно.

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

1. x ¯ ¯ = x {\ displaystyle {\ bar {\ bar {x}}} = x} , инволютивнисть возражения , закон снятия двойного отрицания
2. x ∨ x ¯ = 1 {\ displaystyle x \ lor {\ bar {x}} = 1}
3. x ∨ 1 = 1 {\ displaystyle \ x \ lor 1 = 1}
4. x ∨ x = x {\ displaystyle \ x \ lor x = x}
5. x ∨ 0 = x {\ displaystyle \ x \ lor 0 = x}
6. x ∧ x ¯ = 0 {\ displaystyle \ x \ land {\ bar {x}} = 0}
7. x ∧ x = x {\ displaystyle \ x \ land x = x}
8. x ∧ 0 = 0 {\ displaystyle \ x \ land 0 = 0}
9. x ∧ 1 = x {\ displaystyle \ x \ land 1 = x}

Простым и широко применяемым примером такой алгебраической системы является множество B, состоящий всего из двух элементов:

B = {Ошибочность (0), Истина (1)}

Как правило, в математических выражениях Ошибочность отождествляется с логическим нулем, а Истина - с логической единицей, а операции отрицания (НЕТ), конъюнкции (И) и дизъюнкции (ИЛИ) определяются в привычном нам понимании. Легко показать, что на этом множестве B можно задать четыре унарные и шестнадцать бинарных отношений и все они могут быть получены через суперпозицию трех выбранных операций.

Опираясь на этот математический инструментарий, логика высказываний изучает высказывания и предикаты . Также вводятся дополнительные операции, такие как эквивалентность ↔ {\ displaystyle \ leftrightarrow} ( «Тогда и только тогда, когда»), импликация → {\ displaystyle \ rightarrow} ( «Следовательно»), сложение по модулю два ⊕ {\ displaystyle \ oplus} ( «Исключительная дизъюнкция» ) штрих Шеффера | {\ Displaystyle \ mid} , стрелка Пирса ↓ {\ displaystyle \ downarrow} и другие.

логика высказываний послужила основным математическим инструментом при создании компьютеров. Она легко превращается в битную логику: истинность высказывания обозначается одним битом (0 - ЛОЖЬ, 1 - ИСТИНА) тогда операция ¬ {\ displaystyle \ neg} приобретает сути вычитания из единицы; ∨ {\ displaystyle \ lor} - немодульного добавления; & - умножение; ↔ {\ displaystyle \ leftrightarrow} - равенства; ⊕ {\ displaystyle \ oplus} - в буквальном смысле сумма по модулю 2 (исключающее ИЛИ - XOR) | {\ Displaystyle \ mid} - сумма не превышает 1 (т.е. A | {\ displaystyle \ mid} B = (A + B) <= 1).

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

Свойства логических операций [ ред. | ред. код ]

1. коммутативной : X ∘ {\ displaystyle \ circ} y = y ∘ {\ displaystyle \ circ} x, ∘ ∈ {\ displaystyle \ circ \ in} {&, ∨, ⊕, ~, |, ↓ {\ displaystyle \ lor, \ oplus, \ sim, \ mid, \ downarrow} }.
2. идемпотентность : X ∘ {\ displaystyle \ circ} x = x, ∘ ∈ {\ displaystyle \ circ \ in} {&, ∨ {\ displaystyle \ lor} }.
3. ассоциативность : (X ∘ {\ displaystyle \ circ} y) ∘ {\ displaystyle \ circ} z = x ∘ {\ displaystyle \ circ} (Y ∘ {\ displaystyle \ circ} z), ∘ ∈ {\ displaystyle \ circ \ in} {&, ∨, ⊕, ~ {\ displaystyle \ lor, \ oplus, \ sim} }.
4. дистрибутивность конъюнкций и дизъюнкции относительно дизъюнкции, конъюнкции и суммы по модулю два соответственно:
5. Законы де Моргана :
6. Законы поглощения:
7. Другие (1):
8. Другие (2):
9. Другие (3) (Дополнение законов де Моргана):

Существуют методы упрощения логической функции: например, Карта Карно , метод Куайна - Мак-Класки

Представление в виде диаграмм [ ред. | ред. код ]

Диаграмма Венна [ ред. | ред. код ]

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

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

Цифровые логические цепи [ ред. | ред. код ]

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

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

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

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

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

Компьютеры [ ред. | ред. код ]

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

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

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

Компьютеры используют булевы схемы для двух значений по описанным выше причинам. Сами типичные архитектуры компьютеров используют упорядоченные последовательности булевых значений, например, в 32 или 64 значений, называют битами. 01101000110101100101010101001011. При программировании на машинном коде , языке ассемблера И определенных других языках программирования , Программисты работают с низкоуровневой цифровой структурой с регистров данных . Эти регистры работают с уровнями напряжения, при которых близко к нулю значение напряжения представляет булево значение 0, и опорное напряжение (часто + 5V, + 3.3V, + 1.8V) задает булево значение 1. Такие языки поддерживают числовые операции и логические операции. В контексте «числовые» означает, что компьютер будет рассматривать последовательность битов как двоичные числа (Числа с основанием два) и выполнять арифметические операции такие как сложение, вычитание, умножение или деление. «Логические» относится к логическим булевых операций дизъюнкции, конъюнкции и отрицания между двумя последовательностями бит, при которых каждый бит одной последовательности простым способом сравнивается с соответствующим битом в другой последовательности. Таким образом программисты имеют возможность выбирать как работать, применяя правила числовой алгебры или булевой алгебры в зависимости от потребности. Основной отличительной функцией между семьями операций является существование операции переноса [En] в первой алгебре, и отсутствие в последний.

Основы алгебры логики сформулировал британский Джорджем Булем в 1847 году. Алгебра Буля предшествовала современному развитию абстрактной алгебры и математической логики; и считают, что она связана с появлением обеих этих областей. [9] В абстрактном толковании, булава алгебра была развита в конце 19-м веке, чему значительно приложили усилия математики Уильям Джевонс , Эрнст Шредер , Эдвард Хантингтон [En] и другие, пока она не достигла современного понятия (абстрактной) математической структуры . [9] Например, эмпирические наблюдения о том, что возможно манипулировать выражениями в алгебре множеств , Если перевести их в выражения булевой алгебры объясняются в современных терминах, алгебра множеств это булева алгебра . На самом деле, Н. Г. Стоун в 1936 доказал , Что каждая булева алгебра является изоморфной полю множеств .

В 1930-х, во время изучения переключении электрических цепей [En] , Клод Шеннон заметил, что в данной теме можно использовать законы булевой алгебры, и предложил коммутационную алгебру, что позволяет анализировать и проектировать схемы с помощью алгебраических методов в терминах логических элементов . При разработке схемотехники сегодня, нет большой необходимости рассматривать другие булевы алгебры, поэтому понятие «коммутационная алгебра» и «булева алгебра» часто используются как взаимозаменяемые. [10] [11] [12] при разработке схем комбинационной логики фундаментальной задачей является эффективная реализация [En] булевых функций . современные средства автоматизации проектирования электронных систем для интегральных схем сверхбольшого уровня интеграции часто полагаются на эффективное представление булевых функций, называют (сокращенными упорядоченными) двоичными диаграммами решений для синтеза логики и формальной верификации . [13]

Логические выражения, которые можно представить в классическом многочисленные высказываний имеют эквивалентные выражения [En] в булевой алгебре. Таким образом, срок булева логика иногда используется для указания исчисления высказываний, осуществляется следующим образом. [14] [15] [16] Булевой алгебры недостаточно для работы с логическими формулами, в которых используются кванторы , Как в логике первого порядка . Хотя развитие математической логики не соответствует Булева, связь между его алгеброй и логикой позже был заложен в основу алгебраической логики , Что также изучает алгебраические системы многих других логик. [9] Задача принятия решений о том ли переменные данной булевой формулы (выражения) принимать такие значения, формула будет рассчитана как истина называется задачей осуществимости булевых формул И очень порочные для теоретической информатики , Что является первой задачей для которой было показано, что она имеет сложность NP-полной задачи . Тесно связана с этим модель вычисления , Которая известна как булева схема [En] соотносит временную сложность ( алгоритма ) с сложностью схем [En] .

1. ↑ алгебра логики / Большая советская энциклопедия . Главн. ред. А. М. Прохоров 3-е изд. Тома 1-30. - М.: «Советская энциклопедия» , 1969-1978. (Рус.)
2. ↑ Boole, George (2003) [1854]. An Investigation of the Laws of Thought. Prometheus Books. ISBN 978-1-59102-089-9 .
3. ↑ «The name Boolean algebra (or Boolean 'algebras') for the calculus originated by Boole, extended by Schröder, and perfected by Whitehead seems to have been first suggested by Sheffer, in 1913» EV Huntington, « New sets of independent postulates for the algebra of logic , with special reference to Whitehead and Russell's Principia mathematica », In Trans. Amer. Math. Soc. 35 (1933), 274-304; footnote, page 278.
4. ↑ Peirce, Charles S. (1931). Collected Papers 3. Harvard University Press. с. 13. ISBN 978-0-674-13801-8 .
5. ↑ а б в г Givant, Steven; Halmos, Paul (2009). Introduction to Boolean Algebras. Undergraduate Texts in Mathematics, Springer . ISBN 978-0-387-40293-2 .
6. ↑ Venn, John (July 1880). I. On the Diagrammatic and Mechanical Representation of Propositions and Reasonings . The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science . 5 10 (59): 1-18. doi : 10.1080 / 14786448008626877 . архив оригинала 2017-05-16. [1] [2]
7. ↑ Shannon, Claude (1949). The Synthesis of Two-Terminal Switching Circuits. Bell System Technical Journal 28: 59-98. doi : 10.1002 / j.1538-7305.1949.tb03624.x .
8. ↑ а б в J. Michael Dunn; Gary M. Hardegree (2001). Algebraic methods in philosophical logic . Oxford University Press US. с. 2. ISBN 978-0-19-853192-0 .
9. ↑ Norman Balabanian; Bradley Carlson (2001). Digital logic design principles. John Wiley. с. 39-40. ISBN 978-0-471-29351-4 . , online sample
10. ↑ Rajaraman & Radhakrishnan (2008-03-01). Introduction To Digital Computer Design . PHI Learning Pvt. Ltd. с. 65. ISBN 978-81-203-3409-0 .
11. ↑ John A. Camara (2010). Electrical and Electronics Reference Manual for the Electrical and Computer PE Exam . www.ppi2pass.com. с. 41. ISBN 978-1-59126-166-7 .
12. ↑ Shin-ichi Minato, Saburo Muroga (2007). Binary Decision Diagrams. В Wai-Kai Chen. The VLSI handbook (изд. 2nd). CRC Press. ISBN 978-0-8493-4199-1 . chapter 29.
13. ↑ Alan Parkes (2002). Introduction to languages, machines and logic: computable languages, abstract machines and formal logic . Springer. с. 276. ISBN 978-1-85233-464-2 .
14. ↑ Jon Barwise ; John Etchemendy ; Gerard Allwein; Dave Barker-Plummer; Albert Liu (1999). Language, proof, and logic. CSLI Publications. ISBN 978-1-889119-08-3 .
15. ↑ Ben Goertzel (1994). Chaotic logic: language, thought, and reality from the perspective of complex systems science . Springer. с. 48. ISBN 978-0-306-44690-0 .