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

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

Определение [ править ]

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

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

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

Некоторые основные личности [ править ]

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

{\begin{aligned}&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{aligned}}

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

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

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

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

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

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

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

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

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

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

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

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

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

См. Также [ править ]

Булева алгебра
Ограниченное множество
Решетка (заказ)
Теория порядка

Ссылки [ править ]

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

Дальнейшее чтение [ править ]

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

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

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

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

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