Минимальные аксиомы булевой алгебры - Minimal axioms for Boolean algebra

В математическая логика, минимальные аксиомы для булевой алгебры являются предположениями, которые эквивалентны аксиомам Булева алгебра (или же пропозициональное исчисление ), выбранное как можно короче. Например, аксиома с шестью NAND операций и трех переменных эквивалентна булевой алгебре:

${\displaystyle ((a\mid b)\mid c)\mid (a\mid ((a\mid c)\mid a))=c}$

где вертикальная полоса представляет логическую операцию NAND (также известную как Инсульт Шеффера ).

Это одна из 25 аксиом-кандидатов на это свойство, идентифицированных Стивен Вольфрам, путем перечисления тождеств Шеффера длиной меньше или равной 15 элементам (исключая зеркальные изображения), которые не имеют некоммутативных моделей с четырьмя или меньшим количеством переменных, и были впервые доказаны эквивалентными Уильям МакКьюн, Бранден Фителсон, и Ларри Вос.^[1][2] MathWorld, сайт, связанный с Wolfram, назвал эту аксиому «аксиомой Wolfram».^[3] McCune et al. также нашел более длинную единственную аксиому для булевой алгебры, основанную на дизъюнкции и отрицании.^[2]

В 1933 г. Эдвард Вермиль Хантингтон определил аксиому

${\displaystyle {\neg ({\neg x}\lor {y})}\lor {\neg ({\neg x}\lor {\neg y})}=x}$

как эквивалент булевой алгебры в сочетании с коммутативностью ИЛИ ЖЕ операция ${\displaystyle x\lor y=y\lor x}$, и предположение об ассоциативности, ${\displaystyle (x\lor y)\lor z=x\lor (y\lor z)}$.^[4] Герберт Роббинс предположил, что аксиому Хантингтона можно заменить

${\displaystyle \neg (\neg (x\lor y)\lor \neg (x\lor {\neg y}))=x,}$

что требует на один меньше использования оператора логического отрицания ${\displaystyle \neg }$. Ни Роббинс, ни Хантингтон не смогли доказать эту гипотезу; и не мог Альфред Тарский, который впоследствии сильно заинтересовался этим. Гипотеза была в конечном итоге доказана в 1996 году с помощью программное обеспечение для доказательства теорем.^[5][6][7] Это доказательство установило, что аксиома Роббинса вместе с ассоциативностью и коммутативностью образуют 3-основа для булевой алгебры. Существование 2-базиса было установлено в 1967 г. Кэрью Артур Мередит:^[8]

${\displaystyle \neg ({\neg x}\lor y)\lor x=x,}$

${\displaystyle \neg ({\neg x}\lor {\neg y})\lor (z\lor y)=y\lor (z\lor x).}$

В следующем году Мередит нашла 2-базис с точки зрения инсульта Шеффера:^[9]

${\displaystyle (x\mid x)\mid (y\mid x)=x,}$

${\displaystyle x|(y\mid (x\mid z))=((z\mid y)\mid y)\mid x.}$

В 1973 году Падманабхан и Квакенбуш продемонстрировали метод, который, в принципе, дает 1-базис для булевой алгебры.^[10] Прямое применение этого метода привело к «аксиомам огромной длины»,^[2] Тем самым возникает вопрос, как можно найти более короткие аксиомы. Этот поиск дал 1-базис с точки зрения приведенного выше штриха Шеффера, а также 1-базис

${\displaystyle \neg (\neg (\neg (x\lor y)\lor z)\lor \neg (x\lor \neg (\neg z\lor \neg (z\lor u))))=z,}$

который написан в терминах ИЛИ и НЕ.^[2]

Рекомендации

1. Вольфрам, Стивен (2002). Новый вид науки. Wolfram Media. ISBN  978-1579550080.
2. МакКьюн, Уильям; Верофф, Роберт; Фителсон, Бранден; Харрис, Кеннет; Файст, Эндрю; Вос, Ларри (2002), "Краткие одиночные аксиомы для булевой алгебры", Журнал автоматизированных рассуждений, 29 (1): 1–16, Дои:10.1023 / А: 1020542009983, МИСТЕР  1940227
3. Роуленд, Тодд; Вайсштейн, Эрик В. "Вольфрам Аксиома". MathWorld.
4. Хантингтон, Э. В. (1933). "Новые наборы независимых постулатов для алгебры логики, с особым упором на Уайтхеда и Рассела. Principia Mathematica". Пер. Амер. Математика. Soc. 25: 247–304.
5. Хенкин, Леон; Монк, Дж. Дональд; Тарский, Альфред (1971). Цилиндрические алгебры, часть I. Северная Голландия. ISBN  978-0-7204-2043-2. OCLC  1024041028.
6. МакКьюн, Уильям (1997). «Решение проблемы Роббинса». Журнал автоматизированных рассуждений. 19: 263–276. Дои:10.1023 / А: 1005843212881.
7. Колата, Джина (1996-12-10). «Доказательство компьютерной математики демонстрирует силу рассуждений». Нью-Йорк Таймс. Для исправлений см. МакКьюн, Уильям (1997-01-23). "Комментарии к истории Роббинса". Аргоннская национальная лаборатория. Архивировано из оригинал на 1997-06-05.
8. Мередит, К.А.; Приор, А.Н. (1968). «Эквациональная логика». Нотр-Дам Дж. Формальная логика. 9: 212–226. Дои:10.1305 / ndjfl / 1093893457. МИСТЕР  0246753.
9. Мередит, К.А. (1969). «Постулаты уравнения для мазка Шеффера». Нотр-Дам Дж. Формальная логика. 10: 266–270. Дои:10.1305 / ndjfl / 1093893713. МИСТЕР  0245423.
10. Padmanabhan, R .; Quackenbush, R. W. (1973). «Эквациональные теории алгебр с дистрибутивными конгруэнциями». Proc. Амер. Математика. Soc. 41: 373–377. Дои:10.1090 / S0002-9939-1973-0325498-2.