Двухэлементная булева алгебра - Two-element Boolean algebra

В математика и абстрактная алгебра, то двухэлементная булева алгебра это Булева алгебра чей базовый набор (или же вселенная или же перевозчик) B это Логический домен. Элементы логической области равны 1 и 0 по соглашению, так что B = {0, 1}. Пол Халмос имя этой алгебры "2"имеет некоторые следования в литературе и будет использоваться здесь.

Определение

B это частично заказанный набор и элементы B также его границы.

An операция из арность п это отображение из B^п к B. Булева алгебра состоит из двух бинарные операции и унарный дополнение. Бинарные операции получили разные названия и обозначения. Здесь они называются «сумма» и «произведение» и обозначаются инфиксом «+» и «∙» соответственно. Сумма и произведение ездить и ассоциировать, как в обычном алгебра действительных чисел. Для порядок действий, скобки имеют решающее значение, если они присутствуют. В противном случае «∙» предшествует «+». Следовательно А ∙ В + С разбирается как (А ∙ В) + С а не как А ∙ (В + С). Дополнение обозначается чертой сверху над его аргументом. Числовой аналог дополнения Икс равно 1 -Икс. На языке универсальная алгебра, булева алгебра - это ${ displaystyle langle B, +,., { overline {..}}, 1,0 rangle}$ алгебра из тип ${ Displaystyle langle 2,2,1,0,0 rangle}$ .

Либо индивидуальная переписка от {0,1} до {Истинный,Ложь} дает классический бивалентная логика в эквациональной форме с дополнением, читаемым как НЕТ. Если 1 читается как Истинный, '+' читается как ИЛИ ЖЕ, и '∙' как И, и наоборот, если 1 читается как Ложь. Эти две операции определяют коммутативный полукольцо, известный как Логическое полукольцо.

Некоторые основные личности

2 можно рассматривать как основанный на следующей тривиальной «булевой» арифметике:

{ Displaystyle { begin {align} & 1 + 1 = 1 + 0 = 0 + 1 = 1 & 0 + 0 = 0 & 0 cdot 0 = 0 cdot 1 = 1 cdot 0 = 0 & 1 cdot 1 = 1 & { overline {1}} = 0 & { overline {0}} = 1 end {align}}}

Обратите внимание, что:

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

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

Теперь можно проверить следующие уравнения:

{ Displaystyle { begin {align} & A + A = A & A cdot A = A & A + 0 = A & A + 1 = 1 & A cdot 0 = 0 & { overline { overline {A}}} = A end {выровнено}}}

Каждый из "+" и "∙" распределяет над другими:

${ Displaystyle A CDOT (B + C) = A CDOT B + A CDOT C;}$
${ Displaystyle A + (B cdot C) = (A + B) cdot (A + C).}$

То, что '∙' распределяется по '+', согласуется с элементарная алгебра, но не "+" над "∙". По этой и другим причинам сумма произведений (приводящая к NAND синтез) используется чаще, чем произведение сумм (что приводит к НИ синтез).

Каждый из '+' и '∙' может быть определен в терминах другого и дополнения:

${ displaystyle A cdot B = { overline {{ overline {A}} + { overline {B}}}}}$
${ displaystyle A + B = { overline {{ overline {A}} cdot { overline {B}}}}.}$

Нам нужна только одна бинарная операция, и конкатенация достаточно обозначить это. Следовательно, для обозначения достаточно конкатенации и штриховки. 2. Это обозначение также Куайн с Схема логических терминов. Позволяя (Икс) обозначают дополнение к Икс а "()" обозначает либо 0, либо 1 дает синтаксис первичной алгебры Г. Спенсер-Браун с Законы формы.

А основа за 2 это система уравнений, называемая аксиомы, из которого могут быть выведены все приведенные выше уравнения (и другие). Есть много известных баз для всех булевых алгебр и, следовательно, для 2. Элегантная основа, записанная с использованием только конкатенации и верхней черты:

${ Displaystyle ABC = BCA}$ (Конкатенация коммутирует, товарищи)
${ displaystyle { overline {A}} A = 1}$ (2 это дополнен решетка, с верхняя граница из 1)
${ Displaystyle A0 = А}$ (0 - это нижняя граница ).
${ displaystyle A { overline {AB}} = A { overline {B}}}$ (2 это распределительная решетка )

Где конкатенация = ИЛИ, 1 = истина и 0 = ложь, или конкатенация = И, 1 = ложь и 0 = истина. (верхняя черта в обоих случаях означает отрицание.)

Если 0 = 1, (1) - (3) являются аксиомами для абелева группа.

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

Эта основа обеспечивает простой подход к доказательству, называемый «вычислением» в Законы формы, который осуществляется путем упрощения выражений до 0 или 1, с привлечением аксиом (2) - (4) и элементарных тождеств ${ displaystyle AA = A, { overline { overline {A}}} = A, 1 + A = 1}$ , и распределительный закон.

Метатеория

Теорема де Моргана заявляет, что если сделать следующее в указанном порядке с любым Логическая функция:

Дополнить каждую переменную;
Поменяйте местами операторы '+' и '∙' (добавьте скобки, чтобы порядок операций оставался прежним);
Дополняют результат,

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

Мощный и нетривиальный метатеорема утверждает, что любая теорема 2 справедливо для всех булевых алгебр.^[1] Наоборот, тождество, которое выполняется для произвольной нетривиальной булевой алгебры, также выполняется в 2. Следовательно, все математическое содержание булевой алгебры улавливается 2. Эта теорема полезна, потому что любое уравнение в 2 можно проверить процедура принятия решения. Логики называют этот факт "2 является разрешимый ". Все известные процедуры принятия решений требуется ряд шагов, что является экспоненциальная функция количества переменных N в уравнении, которое необходимо проверить. Существует ли процедура принятия решения, шаги которой полиномиальная функция из N подпадает под P = NP предположение.

Смотрите также

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

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

Мендельсон, Эллиот, 1970. Схема булевой алгебры Шаума. Макгроу – Хилл.

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

Стэнфордская энциклопедия философии: "Математика булева алгебры, "Дж. Дональда Монка.
Беррис, Стэнли Н. и Х.П. Санкаппанавар, Х. П., 1981. Курс универсальной алгебры. Springer-Verlag. ISBN 3-540-90578-2.

[1] Халмос, Пол; Гивант, Стивен (2009). Введение в булевы алгебры. Тексты для бакалавриата по математике. Дои:10.1007/978-0-387-68436-9. ISBN 978-0-387-40293-2.

[1]