75
правок
Изменения
получил рецензию
{{
Теорема|statement=
Любая [[Определение булевой функции | булева функция]] от <tex>n</tex> аргументов <tex>f(x_1, x_2, ..., x_n)</tex> при базисе <tex>B = \{\neg, \lor, \land\}</tex> имеет [[Реализация булевой функции схемой из функциональных элементов#Схемная сложность | схемную сложность]] <tex>size_B (f) \lesssim = O(\frac{2^n}{n})</tex>.
}}
Поделим аргументы функции на два блока: первые <tex>k</tex> и оставшиеся <tex>(n - k)</tex>.
Для удобства дальнейших рассуждений представим булеву функцию в виде таблицы, изображённой на рис. 1.* '''По горизонтали''' на ней представлены все значения Строки индексируются значениями первых <tex>f(\sigma_1, \sigma_2, ..., \sigma_k, x_{k + 1}, x_{k + 2}, ..., x_n)</tex> (здесь и далее <tex>\sigma</tex> {{---}} фиксированное значениепеременных, столбцы — значениями оставшихся <tex>x</tex> {{(n ---}} переменное);* '''По вертикали''' на ней представлены все значения <tex>f(x_1, x_2, ..., x_k, \sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_n)</tex>.Таким , таким образом, легко заметить, что значение <tex>f(x_1, x_2, ..., x_n)</tex> находится на пересечении столбца и строки <tex>x_1, x_2, ..., x_k</tex> и столбца <tex>x_{k + 1}, x_{k + 2}, ..., x_n</tex>находится значение функции для соответствующего набора аргументов.
== Разделение на полосы ==
Разделим таблицу на '''''горизонтальные полосы ''''' шириной <tex>s</tex> (последняя полоса, возможно, будет короче остальных; её длину обозначим <tex>s'</tex>). Пронумеруем полосы сверху вниз от 1 до <tex dpi="145">p=\left\lceil\frac{2^k}{s}\right\rceil</tex>.
Рассмотрим независимо некоторую полосу. Среди её столбцов при небольшом <tex>s</tex> будет много повторений, поэтому введём можно ввести понятие '''''сорта''''' столбца.
{{
Определение|definition=
'''Сорт''' столбца полосы {{---}} [[Отношение эквивалентности#Классы эквивалентности | класс эквивалентности]]среди столбцов одной полосы, к которому столбец принадлежит (два столбца [[Отношение эквивалентности | эквивалентны]], если совпадают по значениям).
}}
Число сортов столбцов <tex>i</tex>-й полосы обозначим как <tex>t(i)</tex>. Понятно, что для любой полосы <tex>t(i) \leq 2^s</tex> (для последней <tex>t(p) \leq 2^{s'}</tex>).
[[Файл:Lupanov_fig2.png|330px|thumb|right|Рис. 2. Значения, возвращаемые функцией <tex>g_{ij}</tex>]]
Пусть для некоторого <tex>i</tex>
* <tex>\beta_{j}</tex> {{---}} столбец <tex>i</tex>-й полосы <tex>j</tex>-го сорта(точное положение столбца далее не будет иметь значение, см. определение сортов);* <tex>(\sigma_1^l, \sigma_2^l, ..., \sigma_k^l)</tex> {{---}} аргументы функции, соответствующие её значениям в <tex>l</tex>-й строке <tex>i</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{elseotherwise}
\end{cases}</tex>
и выводящий <tex>z</tex> на <tex>x</tex>-й из своих <tex>2^n</tex> выходов. На все остальные выходы элемент выдаёт 0.
}}
{||[[Файл:Mux_demux.png|400px500px|thumb|right|Рис. 3. Мультиплексор слева, дешифратор справа]]Иллюстрации элементов приведены на рис. 3.|}
Можно доказать, что оба элемента представимы схемами с числом элементов <tex>\sim O(2^n)</tex> с помощью базиса <tex>B</tex>.
== Доказательство ==
[[Файл:Lupanov_scheme.png|400px550px|thumb|right|Иллюстрация частного случая представления Лупанова, описанного здесь]]
В качестве доказательства ниже будет предложен вариант такой схемы для произвольной функции <tex>f(x_1, x_2, ..., x_n)</tex> (представление Лупанова). Для удобства поделим схему на блоки:
* '''Блок A''' {{---}} дешифратор, которому на вход подали 1 и <tex>(x_1, x_2, ..., x_k)</tex> в качестве двоичного представления числа.
Положим <tex>s = [n - 2\log_2 n]</tex>; <tex>k = [\log_2 n]</tex>. Тогда число элементов в блоках
* <tex dpi="145">L_A \sim = O(2^k \lesssim ) = O(\frac{2^n}{n})</tex>
* <tex dpi="145">L_B \leq (s - 1) \cdot (t(1) + t(2) + ... + t(p)) < sp \cdot 2^s = 2^{k + s} = \frac{2^n}{n}</tex>
* <tex dpi="145">L_C \sim = O(p \cdot 2^{n - k} ) = O(\frac{2^n}{s} \sim ) = O(\frac{2^n}{n})</tex>* <tex dpi="145">L_D \sim = O(2^{n - k} ) = O(\frac{2^n}{n})</tex>
Итого, имеем схему c числом элементов <tex>\sim O(\frac{2^n}{n})</tex>, откуда следует, что <tex>size_B (f) \lesssim = O(\frac{2^n}{n})</tex>, '''''ч.т.д.'''''
== Ссылки ==
