Изменения
Нет описания правки
{{
Теорема|statement=
Любая [[Определение булевой функции | булева функция]] от <tex>n</tex> аргументов <tex>f(x_1, x_2, ..., x_n)</tex> в базисе <tex>B = \{\neg, \lor, \land\}</tex> имеет [[Реализация булевой функции схемой из функциональных элементов#Схемная сложность | схемную сложность]] <tex>size_B (f) = O\left(\fracdfrac{2^n}{n}\right)</tex>.
}}
== Разделение на полосы ==
Разделим таблицу на '''''горизонтальные полосы''''' шириной <tex>s</tex> (последняя полоса, возможно, будет короче остальных; её ширину обозначим <tex>s'</tex>). Пронумеруем полосы сверху вниз от 1 до <tex dpi="145">p=\left\lceil\fracdfrac{2^k}{s}\right\rceil</tex>.
Рассмотрим независимо некоторую полосу. Заметим, что среди её столбцов при небольшом <tex>s</tex> будет много повторений; далее про одинаковые столбцы, находящиеся в одной полосе, будем говорить, что они одного '''''сорта'''''.
'''Сорт''' некоторого столбца данной полосы {{---}} его [[Отношение эквивалентности#Классы эквивалентности | класс эквивалентности]] по отношению поэлементного равенства столбцов данной полосы.
}}
Число сортов столбцов <tex>i</tex>-й полосы обозначим как <tex>t(i)</tex>. Понятно, что для любой полосы <tex>t(i) \leq leqslant 2^s</tex> (для последней <tex>t(p) \leq leqslant 2^{s'}</tex>).
== Функция для одной полосы ==
<tex>g_{ij}(x_1, x_2, ..., x_k) = \begin{cases}
\beta_{jl}& , \mbox{if } \exists l \in [1; s]~(x_1, x_2, ..., x_k) = (\sigma_1^l, \sigma_2^l, ..., \sigma_k^l) \\ 0&, \mbox{otherwise}
\end{cases}</tex>
Положим <tex>s = \lfloor n - 2\log_2 n\rfloor</tex>; <tex>k = \lfloor\log_2 n\rfloor</tex>. Тогда число элементов в блоках
* <tex>L_A = O(2^k) = O(2^{\log_2 n}) = O(n)</tex>
* <tex>L_B \leq leqslant (s - 1) \cdot (t(1) + t(2) + ... + t(p)) < sp \cdot 2^s = n \cdot \fracdfrac{2^n}{n^2} = \fracdfrac{2^n}{n}</tex>* <tex>L_C = O(p \cdot 2^{n - k}) = O\left(\fracdfrac{p}{n} \cdot 2^n\right) = O\left(\fracdfrac{2^n}{s}\right) = O\left(\fracdfrac{2^n}{n - 2\log_2 n}\right)</tex>* <tex>L_D = O(2^{n - k}) = O\left(\fracdfrac{2^n}{n}\right)</tex>
Итого, имеем схему c числом элементов <tex>L_A + L_B + L_C + L_D = O(n) + O\left(\frac{2^n}{n}\right) + O\left(\fracdfrac{2^n}{n - 2\log_2 n}\right) + O\left(\fracdfrac{2^n}{n}\right) = O\left(\fracdfrac{2^n}{n}\right)</tex>, откуда следует, что <tex>size_B (f) = O\left(\fracdfrac{2^n}{n}\right)</tex>, '''''ч.т.д.'''''
== Ссылки ==
