Аксиома Вольфрама

Аксиома Вольфрама является результатом исследований, осуществлённых Стивеном Вольфрамом при поиске кратчайшей аксиомы из одного уравнения, эквивалентной аксиомам булевой алгебры (или логике высказываний). Результатом его поиска стала аксиома с шестью логическими операциями «НЕ-И» (так же известными как штрих Шеффера) и тремя переменными, которая эквивалентна булевой алгебре:

Знаком | обозначена логическая операция «НЕ-И» (штрих Шеффера), а высказывание X | Y означает, что X и Y несовместны, т. е. не являются истинными одновременно. Эта булева функция названа в честь Генри Шеффера, который доказал, что логику остальных операций булевой алгебры («НЕ», «И», «ИЛИ» и пр.) можно выразить с использованием только операции «НЕ-И» (штрих Шеффера), которая образует базис для пространства булевых функций от двух переменных.

Вольфрам отобрал 25 тождеств Шеффера, состоящих не более чем из 15 элементов (без учёта зеркальных изображений), которые не имеют некоммутативных моделей размером, меньшим или равным 4 переменных.

Исследователи знали о существовании аксиомы из одного уравнения, эквивалентной булевой алгебре, которую можно выразить в терминах дизъюнкции, отрицания и штриха Шеффера. Вольфрам доказал, что не существует более короткой записи такой аксиомы, чем найденная им. Доказательство приведено в его книге «A New Kind of Science» и занимает две страницы. Таким образом, аксиома Вольфрама является простейшей (по количеству операций и переменных) аксиомой с одним уравнением, необходимой для воспроизведения булевой алгебры.

Тождества Шеффера были независимо получены различными способами и опубликованы в техническом меморандуме в июне 2000 года, подтверждая соответствие с результатом Вольфрама, который нашёл аксиому в 1999 году при подготовке своей книги. В техническом отчёте также приведена кратчайшая аксиома из пары уравнений, которая эквивалента булевой алгебре.