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

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

Определение

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

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

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

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

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

{\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 , включая аксиомы, путем проверки всех возможных назначений нулей и единиц каждой переменной (см. процедуру принятия решения ).

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

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

Каждый из знаков «+» и «∙» распределяется по другому:

$\ A\cdot (B+C)=A\cdot B+A\cdot C;$
$\ A+(B\cdot C)=(A+B)\cdot (A+C).$

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

Каждый из знаков «+» и «∙» можно определить через другой и дополнение:

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

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

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

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

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

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

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

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

Метатеория

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

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

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

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

Вышеуказанная метатеорема не выполняется, если мы рассматриваем справедливость более общих формул логики первого порядка вместо только атомарных положительных равенств. В качестве примера рассмотрим формулу $(x = 0) \lor (x = 1)$ . Эта формула всегда истинна в двухэлементной булевой алгебре. В четырехэлементной булевой алгебре, областью определения которой является множество ⁠ ⁠ $\{0,1\}$ , эта формула соответствует утверждению $(x = \emptyset) \lor (x = {0,1})$ и ложна, когда x равен ⁠ ⁠ $\{1\}$ . Разрешимость для теории первого порядка многих классов булевых алгебр все еще может быть показана с использованием исключения кванторов или свойства малой модели (с размером области, вычисляемым как функция формулы и обычно большим 2).

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

Ссылки

^ Халмош, Пол; Дживант, Стивен (2009). Введение в булевы алгебры . Бакалаврские тексты по математике. doi :10.1007/978-0-387-68436-9. ISBN 978-0-387-40293-2.

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

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

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

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

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