Изменения
Нет описания правки
{{
Теорема|statement=
Любая [[Определение булевой функции | булева функция]] от <tex>n</tex> аргументов <tex>f(x_1, x_2, ..., x_n)</tex> в базисе <tex>B = \{\neg, \lor, \land\}</tex> имеет [[Реализация булевой функции схемой из функциональных элементов#Схемная сложность | схемную сложность]] <tex>size_B (f) = O</tex> <tex dpi = "150"> \left(\frac{2^n}{n}\right)</tex>.
}}
== Разделение на полосы ==
Разделим таблицу на '''''горизонтальные полосы''''' шириной <tex>s</tex> (последняя полоса, возможно, будет короче остальных; её ширину обозначим <tex>s'</tex>). Пронумеруем полосы сверху вниз от 1 до <tex dpi="145130">p=</tex> <tex dpi = "150"> \left\lceil\frac{2^k}{s}\right\rceil</tex>.
Рассмотрим независимо некоторую полосу. Заметим, что среди её столбцов при небольшом <tex>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>. Тогда число элементов в блоках
* <texdpi = "130">L_A = O(2^k) = O(2^{\log_2 n}) = O(n)</tex>* <texdpi = "130">L_B \leq (s - 1) \cdot (t(1) + t(2) + ... + t(p)) < sp \cdot 2^s = n \cdot </tex> <tex dpi = "150"> \frac{2^n}{n^2} </tex> <tex dpi = "130"> = </tex> <tex dpi = "150"> \frac{2^n}{n}</tex>* <texdpi = "130">L_C = O(p \cdot 2^{n - k}) = O</tex> <tex dpi = "150"> \left(\frac{p}{n} \cdot 2^n\right) </tex> <tex dpi = "130"> = O</tex> <tex dpi = "150"> \left(\frac{2^n}{s}\right) </tex> <tex dpi = "130"> = O</tex> <tex dpi = "150"> \left(\frac{2^n}{n - 2\log_2 n}\right)</tex>* <texdpi = "130">L_D = O(2^{n - k}) = O</tex> <tex dpi = "150"> \left(\frac{2^n}{n}\right)</tex>
Итого, имеем схему c числом элементов <tex>L_A + L_B + L_C + L_D = O(n) + O</tex> <tex dpi = "150"> \left(\frac{2^n}{n}\right) </tex> <tex dpi = "130"> + O</tex> <tex dpi = "150"> \left(\frac{2^n}{n - 2\log_2 n}\right) </tex> <tex dpi = "130"> + O</tex> <tex dpi = "150"> \left(\frac{2^n}{n}\right) </tex> <tex dpi = "130"> = O</tex> <tex dpi = "150"> \left(\frac{2^n}{n}\right)</tex>, откуда следует, что <texdpi = "130">size_B (f) = O</tex> <tex dpi = "150"> \left(\frac{2^n}{n}\right)</tex>, '''''ч.т.д.'''''
== Ссылки ==
