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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. (Конкатенация коммутирует, товарищи)
  2. ( 2 - решетка с дополнениями , верхняя граница равна 1)
  3. (0 - нижняя граница ).
  4. ( 2 - распределительная решетка )

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

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

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

Этот базис обеспечивает легкий подход к доказательству, называемый «вычислением» в Законах формы , который заключается в упрощении выражений до 0 или 1, с использованием аксиом (2) - (4), элементарных тождеств и закона распределения.

Метатеория

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

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

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

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

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

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

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

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

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

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