Минимальные аксиомы булевой алгебры

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

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

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

Это одна из 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}$

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

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

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

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

${\ 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]

Ссылки [ править ]