Оценки активности схем из функциональных элементов, реализующих булевы операторы

Аннотация

Для схем из функциональных элементов в стандартном базисе рассматриваются две меры активности: мощность — число элементов с единицей на выходе и \(P\)-активность — число элементов с единицей на входе или выходе. Для первой меры найден порядок функции Шеннона \(\Theta (n+m\log n)\) для операторов с \(n\) входами и \(m\) выходами, \(1\le m\le 2^n\). Для второй получена нижняя оценка \(\Omega (n\log n)\) для почти всех булевых функций. Оба результата справедливы для средней и максимальной мер.

Ключевые слова: булевы функции, схемы из функциональных элементов, мощность схем, активность схем, функция Шеннона.

BibTeX
@article{IS-Kalachev2026,
  author  = {Калачев, Глеб Вячеславович},
  title   = {{Оценки активности схем из функциональных элементов, реализующих булевы операторы}},
  journal = {Интеллектуальные системы. Теория и приложения},
  year    = {2026},
  volume  = {30},
  number  = {4},
  pages   = {164--167},
}
AMSBIB
\RBibitem{IS-Kalachev2026}
\by Г.\,В.~Калачев
\paper Оценки активности схем из функциональных элементов, реализующих булевы операторы
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 4
\pages 164--167
Опубликовано на условиях лицензии Creative Commons Attribution 4.0 International (CC BY 4.0)

← К номеру журнала

× Issue cover