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

В абстрактная алгебра, а Алгебра Роббинса является алгебра содержащий единственный бинарная операция, обычно обозначаемый ${displaystyle lor}$ , и один унарная операция обычно обозначается ${displaystyle eg}$ . Эти операции удовлетворяют следующим аксиомы:

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

Ассоциативность: ${displaystyle alor left (blor cight) = left (alor bight) lor c}$
Коммутативность: ${displaystyle alor b = blor a}$
Уравнение Роббинса: ${стиль отображения, например, left (например, left (alor bight) lor eg left (alor eg bight) ight) = a}$

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

История

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

Уравнение Хантингтона: ${displaystyle eg (например, alor b) lor eg (например, alor eg b) = a.}$

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

Очень скоро после этого Герберт Роббинс поставил Гипотеза Роббинса, а именно, что уравнение Хантингтона можно заменить тем, что стало называться уравнением Роббинса, и результат все равно будет Булева алгебра. ${displaystyle lor}$ интерпретирует логическое значение присоединиться и ${displaystyle eg}$ Булево дополнять. Булево встреча а константы 0 и 1 легко определяются из примитивов алгебры Роббинса. В ожидании проверки гипотезы система Роббинса получила название «алгебра Роббинса».

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

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

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

использованная литература

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