Алгебра Роббинса

В абстрактной алгебре алгебра Роббинса — это алгебра , содержащая одну бинарную операцию , обычно обозначаемую $\lor$и одна унарная операция , обычно обозначаемая $\neg$ удовлетворяющие следующим аксиомам :

Для всех элементов a , b и c :

1. Ассоциативность : $a\lor \left(b\lor c\right)=\left(a\lor b\right)\lor c$
2. Коммутативность : $a\lor b=b\lor a$
3. Уравнение Роббинса : $\neg \left(\neg \left(a\lor b\right)\lor \neg \left(a\lor \neg b\right)\right)=a$

В течение многих лет предполагалось, но не было доказано, что все алгебры Роббинса являются булевыми алгебрами . Это было доказано в 1996 году, поэтому термин «алгебра Роббинса» теперь является просто синонимом «булевой алгебры».

История

В 1933 году Эдвард Хантингтон предложил новый набор аксиом для булевых алгебр, состоящий из (1) и (2), приведенных выше, плюс:

• Уравнение Хантингтона : $\neg (\neg a\lor b)\lor \neg (\neg a\lor \neg b)=a.$

Из этих аксиом Хантингтон вывел обычные аксиомы булевой алгебры.

Очень скоро после этого Герберт Роббинс сформулировал гипотезу Роббинса , а именно, что уравнение Хантингтона можно заменить тем, что стало называться уравнением Роббинса, и результатом по-прежнему будет булева алгебра . $\lor$ будет интерпретировать логическое соединение и $\neg$ Булево дополнение . Булево сочетание и константы 0 и 1 легко определяются из примитивов алгебры Роббинса. До проверки гипотезы систему Роббинса называли «алгеброй Роббинса».

Для проверки гипотезы Роббинса потребовалось доказать уравнение Хантингтона или некоторую другую аксиоматизацию булевой алгебры как теоремы алгебры Роббинса. Хантингтон, Роббинс, Альфред Тарский и другие работали над этой проблемой, но не смогли найти ни доказательства, ни контрпримера.

Уильям МакКьюн доказал эту гипотезу в 1996 году, используя автоматизированное средство доказательства теорем EQP . Полное доказательство гипотезы Роббинса в единых последовательных обозначениях, внимательно следуя МакКьюну, см. в Mann (2003). Дан (1998) упростил машинное доказательство МакКьюна.

См. также

• Алгебраическая структура
• Минимальные аксиомы булевой алгебры

Ссылки

• Дан, Б.И. (1998) Аннотация к книге « Алгебры Роббинса являются логическими: пересмотр компьютерного решения задачи Роббинса МакКьюна », Journal of Algebra 208(2): 526–32.
• Манн, Аллен (2003) « Полное доказательство гипотезы Роббинса » .
• Уильям МакКьюн , « Алгебры Роббинса являются логическими », со ссылками на доказательства и другие статьи.