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

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

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

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

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


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

Ну вот и я о том же подумал
Тогда на ваш вопрос и мне интересно узнать ответ.

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

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

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

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

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

может я мыслю примитивно, да и половина слов в теме мне неизвестна

но я понял вопрос так - у нас есть таблица истинности для n переменных (2^n строк), сколькими таблицами для n-1 переменных ее можно представить?

для n>2 кажется очевидным, что нужно 3 таблицы - группируем строки так, чтобы по одной переменной было упорядочено, верхняя таблица n-1 для этой переменной==0, нижняя n-1 для ==1 и мультиплексор - трехвходовая функция/таблица

кажется, что по этой причине всякие ксайлинсы/альтеры пихают мультиплексор в свой слайс - таким образом задешего поднимают "арность"
----------
а тупой актел так не делает и херня получается

Я уже пояснил, что имел в виду не количество функций, а количество термов.

Например, сколько минимум нужно использовать функций стрелки Пирса (считайте, вызовов функций - термов), чтобы выразить любую функцию от 3-х аргументов.




Вы правильно поняли вопрос.





Вы абсолютно правы. Посыпаю головы пеплом - как можно было до этого не додуматься.
Правда, думал над вариантом n = 2, дальше не стал, т.к. подумал, что если так не могу додуматься, то больше - и подавно. А при n=3 все становиться гораздно легче.
Спасибо!

Да, в таком смысле не понял вопрос. На всякий случай - в дискретной математике это называется разложением Шеннона. Еще используется разложение Рида через XOR. Вот здесь в начале выведены.

Спасибо! Как-то быстро я забыл дискретную математику.