Том 2, номер 1, 1995 г., Стр. 7-20

УДК 519.6
О. М. Касим-Заде
О сложности реализации булевых функций схемами в одном бесконечном базисе

Аннотация:
Изучается сложность реализации булевых функций схемами из функциональных элементов в бесконечном базисе $AC$, состоящем из всевозможных антицепных булевых функций. Показано, что при $n\to\infty$ порядок роста сложности реализации линейной функции $n$ переменных схемами в базисе $AC$ не меньше $(n/\ln n)$. Установлено, что наибольшая сложность булевых функций $n$ переменных при реализации схемами в базисе $CA$ по порядку роста заключена между $(n/\ln n)$ и $n$.
Библиогр. 3.

Касим-Заде О. М. ¹
1. МГУ, мех.-мат. факультет
Воробьевы горы, 119899 Москва, Россия

Статья поступила 22 ноября 1994 г.