Двухэлементная булева алгебра

редактировать

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

Содержание

1 Определение
2 Некоторые основные идентичности
3 метатеория
4 См. Также
5 ссылки
6 Дальнейшее чтение

Определение

B - частично упорядоченное множество, и элементы B также являются его границами.

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

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

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

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

{\ Displaystyle {\ begin {align} amp; 1 + 1 = 1 + 0 = 0 + 1 = 1 \\ amp; 0 + 0 = 0 \\ amp; 0 \ cdot 0 = 0 \ cdot 1 = 1 \ cdot 0 = 0 \\ amp; 1 \ cdot 1 = 1 \\ amp; {\ overline {1}} = 0 \\ amp; {\ overline {0}} = 1 \ end {align}}}

\ begin {align} amp; 1 + 1 = 1 + 0 = 0 + 1 = 1 \\ amp; 0 + 0 = 0 \\ amp; 0 \ cdot0 = 0 \ cdot1 = 1 \ cdot0 = 0 \\ amp; 1 \ cdot1 = 1 \\ amp; \ overline {1} = 0 \\ amp; \ overline {0} = 1 \ end {align}

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

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

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

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

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

{\ begin {align} amp; A + A = A \\ amp; A \ cdot A = A \\ amp; A + 0 = A \\ amp; A + 1 = 1 \\ amp; A \ cdot 0 = 0 \\ amp; \ overline {\ overline { A}} = A \ end {выровнено}}

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

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

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

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

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

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

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

${\ Displaystyle \ ABC = BCA}$ $\ ABC = BCA$ (Конкатенация коммутирует, товарищи)
${\ displaystyle {\ overline {A}} A = 1}$ $\ overline {A} A = 1$ ( 2 - решетка с дополнениями, верхняя граница равна 1)
${\ Displaystyle \ A0 = А}$ $\ A0 = А$ (0 - нижняя граница ).
${\ displaystyle A {\ overline {AB}} = A {\ overline {B}}}$ $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}$ $AA = A, \ overline {\ overline {A}} = A, 1 + A = 1$

Метатеория

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

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

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

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

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

Рекомендации

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

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

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

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

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