Аксиома Вольфрама является результатом исследований, осуществлённых Стивеном ВольфрамомStephen Wolfram, A New Kind of Science, 2002, p. 808–811 and 1174. при поиске кратчайшей аксиомы из одного уравнения, эквивалентной аксиомам булевой алгебры (или логике высказываний). РезультатомRudy Rucker, A review of NKS, The Mathematical Association of America, Monthly 110, 2003. его поиска стала аксиома с шестью логическими операциями «НЕ-И» (так же известными как штрих Шеффера) и тремя переменными, которая эквивалентна булевой алгебре:
((a | b) | c) | (a | ((a | c) | a)) = c
Знаком | обозначена логическая операция «НЕ-И» (штрих Шеффера), а высказывание X | Y означает, что X и Y несовместны, т. е. не являются истинными одновременно. Эта булева функция названа в честь Генри Шеффера, который доказал, что логику остальных операций булевой алгебры («НЕ», «И», «ИЛИ» и пр.) можно выразить с использованием только операции «НЕ-И» (штрих Шеффера), которая образует базис для пространства булевых функций от двух переменных.
Вольфрам отобрал 25 тождеств Шеффера, состоящих не более чем из 15 элементов (без учёта зеркальных изображений), которые не имеют некоммутативных моделей размером, меньшим или равным 4 переменныхWilliam Mccune, Robert Veroff, Branden Fitelson, Kenneth Harris, Andrew Feist and Larry Wos, Short Single Axioms for Boolean algebra, J. Automated Reasoning, 2002..
Исследователи знали о существовании аксиомы из одного уравнения, эквивалентной булевой алгебре, которую можно выразить в терминах дизъюнкции, отрицания и штриха Шеффера. Вольфрам доказал, что не существует более короткой записи такой аксиомы, чем найденная им. Доказательство приведено в его книге «A New Kind of Science» и занимает две страницы. Таким образом, аксиома Вольфрама является простейшей (по количеству операций и переменных) аксиомой с одним уравнением, необходимой для воспроизведения булевой алгебры.
Тождества Шеффера были независимо получены различными способами и опубликованы в техническом меморандумеRobert Veroff and William McCune, A Short Sheffer Axiom for Boolean algebra, Technical Memorandum No. 244 в июне 2000 года, подтверждая соответствие с результатом Вольфрама, который нашёл аксиому в 1999 году при подготовке своей книги. В техническом отчётеRobert Veroff, Short 2-Bases for Boolean algebra in Terms of the Sheffer stroke. Tech. Report TR-CS-2000-25, Computer Science Department, University of New Mexico, Albuquerque, NM также приведена кратчайшая аксиома из пары уравнений, которая эквивалента булевой алгебре.
См. также
Булева алгебра
Примечания
Ссылки Stephen Wolfram, 2002, "A New Kind of Science, online".
http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
Категория:Булева алгебра Категория:Логика Категория:Логика высказываний