Аксиома Вольфрама
Аксиома Вольфрама является результатом исследований, осуществлённых Стивеном Вольфрамом[1] при поиске кратчайшей аксиомы из одного уравнения, эквивалентной аксиомам булевой алгебры (или логике высказываний). Результатом[2] его поиска стала аксиома с шестью логическими операциями «НЕ-И» (так же известными как штрих Шеффера) и тремя переменными, которая эквивалентна булевой алгебре:
- ((a | b) | c) | (a | ((a | c) | a)) = c
Знаком | обозначена логическая операция «НЕ-И» (штрих Шеффера), а высказывание X | Y означает, что X и Y несовместны, т. е. не являются истинными одновременно. Эта булева функция названа в честь Генри Шеффера, который доказал, что логику остальных операций булевой алгебры («НЕ», «И», «ИЛИ» и пр.) можно выразить с использованием только операции «НЕ-И» (штрих Шеффера), которая образует базис для пространства булевых функций от двух переменных.
Вольфрам отобрал 25 тождеств Шеффера, состоящих не более чем из 15 элементов (без учёта зеркальных изображений), которые не имеют некоммутативных моделей размером, меньшим или равным 4 переменных[3].
Исследователи знали о существовании аксиомы из одного уравнения, эквивалентной булевой алгебре, которую можно выразить в терминах дизъюнкции, отрицания и штриха Шеффера. Вольфрам доказал, что не существует более короткой записи такой аксиомы, чем найденная им. Доказательство приведено в его книге «A New Kind of Science» и занимает две страницы. Таким образом, аксиома Вольфрама является простейшей (по количеству операций и переменных) аксиомой с одним уравнением, необходимой для воспроизведения булевой алгебры.
Тождества Шеффера были независимо получены различными способами и опубликованы в техническом меморандуме[4] в июне 2000 года, подтверждая соответствие с результатом Вольфрама, который нашёл аксиому в 1999 году при подготовке своей книги. В техническом отчёте[5] также приведена кратчайшая аксиома из пары уравнений, которая эквивалента булевой алгебре.
См. также
[править | править код]Примечания
[править | править код]- ↑ 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.
- ↑ William Mccune, Robert Veroff, Branden Fitelson, Kenneth Harris, Andrew Feist and Larry Wos, Short Single Axioms for Boolean algebra, J. Automated Reasoning, 2002.
- ↑ Robert Veroff and William McCune, A Short Sheffer Axiom for Boolean algebra, Technical Memorandum No. 244
- ↑ 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".
- Weisstein, Eric W. Wolfram Axiom (англ.) на сайте Wolfram MathWorld.
- http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
- Weisstein, Eric W. Boolean algebra (англ.) на сайте Wolfram MathWorld.
- Weisstein, Eric W. Robbins Axiom (англ.) на сайте Wolfram MathWorld.
- Weisstein, Eric W. Huntington Axiom (англ.) на сайте Wolfram MathWorld.