Оценки активности схем из функциональных элементов, реализующих булевы операторы
Получена: 26.10.2026 Принята: 27.10.2026
Опубликована: 2026 год, том 30, выпуск 4, С. 164–167
Аннотация
Для схем из функциональных элементов в стандартном базисе рассматриваются две меры активности: мощность — число элементов с единицей на выходе и \(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
EN