Аннотация:
Доказано, что при $n=3, 5$ и при $n,$ равном степени
двойки, любое минимальное правильное разбиение множества рёбер
$n$-мерного куба является совершенным. Следствием этих результатов
является описание классов всех минимальных
параллельно-последовательных контактных схем ($\pi$-схем),
реализующих линейные булевы функции, существенно зависящие от $n$
переменных при соответствующих значениях $n$. Библиогр. 16.
Ключевые слова:булева функция, $\pi$-схема, правильное разбиение множества рёбер $n$-мерного куба, нижняя оценка сложности.
УДК:519.714
Статья поступила: 10.06.2019 Переработанный вариант: 29.07.2019 Принята к публикации: 28.08.2019