Том 4, серия 1, номер 4, 1997 г., Стр. 79-95
УДК 519.6
Д. Ю. Черухин
Об одной бесконечной последовательности улучшающихся булевых базисов
Аннотация:
Рассматривается сложность реализации булевых функций формулами в конечных полных базисах. Показано, что с точки зрения сложности базис, состоящий из всех$(k+1)$ -местных функций, существенно лучше базиса, состоящего из всех$k$ -местных функций (при каждом$k\geqslant 2$ ).
Библиогр. 4.
Черухин Д. Ю. 1
1. МГУ, мех.-мат. факультет,
Воробьевы горы, 119899 Москва, Россия
Статья поступила 28 апреля 1997 г.
Исправленный вариант — 10 сентября 1997 г.
