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

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

${\ Displaystyle ((а \ середина б) \ середина с) \ середина (а \ середина ((а \ середина с) \ середина а)) = с}$

где вертикальная полоса представляет логическую операцию НЕ-НЕ (также известную как штрих Шеффера ).

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

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

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

как эквивалентную булевой алгебре в сочетании с коммутативностью операции ИЛИ и предположением об ассоциативности . Герберт Роббинс предположил, что аксиому Хантингтона можно заменить ${\ Displaystyle х \ лор у = у \ лор х}$${\ Displaystyle (х \ лор у) \ лор г = х \ лор (у \ лор г)}$

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

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

${\ 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-базис с точки зрения инсульта Шеффера:

${\ Displaystyle (х \ середина х) \ середина (у \ середина х) = х,}$

${\ Displaystyle х | (у \ середина (х \ середина г)) = ((г \ середина у) \ середина у) \ середина х.}$

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

${\ displaystyle \ neg (\ neg (\ neg (х \ лор у) \ лор г) \ лор \ neg (х \ лор \ neg (\ отр г \ лор \ neg (г \ лор и)))) = г ,}$

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

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