Вопрос по булевым функциям. Опции

[des333]

Вопрос, вроде, простой, а что-то никак додуматься не могу.
Даже гуглить пытался - безуспешно.

Какое минимальное количество булевых функций арности (n-1) нужно, чтобы выразить любую булеву функцию арности n?

Заранее спасибо!

[Alexium]

Имеется в виду количество именно функций, или термов? Если функций - мне кажется, что одна, т.е. всегда найдется базис из одной функции (если n > 1), хотя доказать не могу.

[des333]

Имеется в виду количество именно функций, или термов?

Имелось в виду, конечно, количество термов (так сказать количество "вызовов" любых функций).


Неправильно выразился. А так-то и стрелка Пирса или штрих Шеффера образуют базис при n=2.

[Sergey'F]

Неправильно выразился. А так-то и стрелка Пирса или штрих Шеффера образуют базис при n=2.

Штрих Шеффера и стрелка Пирса определяют базис для любого n.

Для получения базисов из n-арных булевых функций, а также полных систем функций¹⁾, можно предложить такой подход: перебираем все n-арные функции (а их у нас 2^(2^n)) и проверяем их на принадлежность 5 классам Поста, после чего по полученной таблице принадлежности к классам Поста составляем базисы. Думаю, их будет много.

Вот здесь приведено доказательство, что базис содержит не более 4 функций для любого n.

Заинтересовались синтезом в базисе таблиц перекодировки?

¹⁾Например, если говорить строго - И-ИЛИ-НЕ - это полная система, но не базис, так как она избыточна. Удалением И или ИЛИ получаем уже базис. Хотя я и сам иногда говорю "в базисе И-ИЛИ-НЕ", что неправильно.