Двухэлементная булева алгебра - 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 . Элегантная основа, записанная с использованием только конкатенации и верхней черты:
- (Конкатенация коммутирует, товарищи)
- ( 2 - решетка с дополнениями , верхняя граница равна 1)
- (0 - нижняя граница ).
- ( 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. Схема булевой алгебры Шаума . Макгроу – Хилл.
Следующие элементы показывают, насколько математически нетривиальна двухэлементная булева алгебра.
- Стэнфордская энциклопедия философии : « Математика булевой алгебры » Дж. Дональда Монка.
- Беррис, Стэнли Н., и HP Sankappanavar, HP, 1981. Курс универсальной алгебры. Springer-Verlag. ISBN 3-540-90578-2 .