Изменения

Любая булева функция от <mathtex>n</mathtex> аргументов <mathtex>f(x_1, x_2, ..., x_n)</mathtex> при базисе <mathtex>B = \{\neg, \lor, \land\}</mathtex> имеет схемную сложность <mathtex>size_B (f) \lesssim \frac{2^n}{n}</mathtex>.

Для начала поделим аргументы функции на два блока: первые <mathtex>k</mathtex> и оставшиеся <mathtex>(n - k)</mathtex>.

* '''По горизонтали''' на ней представлены все значения <mathtex>f(\sigma_1, \sigma_2, ..., \sigma_k, x_{k + 1}, x_{k + 2}, ..., x_n)</mathtex> (здесь и далее <mathtex>\sigma</mathtex> - фиксированное значение, <mathtex>x</mathtex> - переменное);* '''По вертикали''' на ней представлены все значения <mathtex>f(x_1, x_2, ..., x_k, \sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_n)</mathtex>.Таким образом, легко заметить, что значение <mathtex>f(x_1, x_2, ..., x_n)</mathtex> находится на пересечении строки <mathtex>x_1, x_2, ..., x_k</mathtex> и столбца <mathtex>x_{k + 1}, x_{k + 2}, ..., x_n</mathtex>.

Разделим таблицу на горизонтальные полосы шириной <mathtex>s</mathtex> (последняя полоса, возможно, будет короче остальных; её длину обозначим <mathtex>s'</mathtex>). Пронумеруем полосы сверху вниз от 1 до <mathtex>p=\lceil\frac{2^k}{s}\rceil</mathtex>.

Рассмотрим независимо некоторую полосу. Среди её столбцов при небольшом <mathtex>s</mathtex> будет много повторений, поэтому введём понятие '''''сорта''''' столбца.

Число сортов столбцов <mathtex>i</mathtex>-й полосы обозначим как <mathtex>t(i)</mathtex>. Понятно, что для любой полосы <mathtex>t(i) \leq 2^s</mathtex> (для последней <mathtex>t(i) \leq 2^{s'}</mathtex>).

[[Файл:Lupanov_fig2.png|330px|thumb|right|Рис. 2. Значения, возвращаемые функцией <mathtex>g_{ij}</mathtex>]]Пусть для некоторого <mathtex>i</mathtex>* <mathtex>\beta_{j}</mathtex> - столбец <mathtex>i</mathtex>-й полосы <mathtex>j</mathtex>-го сорта;* <mathtex>(\sigma_1^l, \sigma_2^l, ..., \sigma_k^l)</mathtex> - аргументы функции, соответствующие её значениям в <mathtex>l</mathtex>-й строке <mathtex>i</mathtex>-й полосы.

<mathtex>g_{ij}(x_1, x_2, ..., x_k) = \begin{cases}

\end{cases}</mathtex>

Другими словами, если строка, соответствующая аргументам функции <mathtex>x_1, x_2, ..., x_k</mathtex>, находится в <mathtex>i</mathtex>-й полосе, то функция возвращает значение, записанное в столбце сорта <mathtex>j</mathtex> для этой строки. Если же эта строка находится в другой полосе, то функция вернёт 0. Иллюстрация принципа работы функции <mathtex>g_{ij}</mathtex> приведена на рис. 2.

Поскольку изначальный столбец <mathtex>(\sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_{n})</mathtex> складывается из столбцов соответствующих сортов в полосах,<mathtex>f(x_1, x_2, ..., x_k, \sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_{n}) = \bigvee\limits_{i = 1}^p g_{ij_i}(x_1, x_2, ..., x_k)</mathtex>,где <mathtex>j_i</mathtex> - номер сорта столбца полосы <mathtex>i</mathtex>, являющегося соответствующей частью столбца <mathtex>(\sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_{n})</mathtex>.

* <mathtex>2^n</mathtex> булевых значений;* <mathtex>n</mathtex>-значное число <mathtex>x</mathtex> в двоичном представлениии возвращающий значение на <mathtex>x</mathtex>-м входе.

* булево значение <mathtex>z</mathtex>;* <mathtex>n</mathtex>-значное число <mathtex>x</mathtex> в двоичном представлениии выводящий <mathtex>z</mathtex> на <mathtex>x</mathtex>-й из своих <mathtex>2^n</mathtex> выходов. На все остальные выходы элемент выдаёт 0.

Можно доказать, что оба элемента представимы схемами с числом элементов <mathtex>\sim 2^n</mathtex> с помощью базиса <mathtex>B</mathtex>.

В качестве доказательства ниже будет предложен вариант такой схемы для произвольной функции <mathtex>f(x_1, x_2, ..., x_n)</mathtex> (представление Лупанова). Для удобства поделим схему на блоки:* '''Блок A''' - дешифратор, которому на вход подали 1 и <mathtex>(x_1, x_2, ..., x_k)</mathtex> в качестве двоичного представления числа.

Число элементов <mathtex>L_A \sim 2^k</mathtex>* '''Блок B''' - схемная реализация всех <mathtex>g_{ij}</mathtex>. Функцию <mathtex>g_{ij}</mathtex> можно реализовать как <mathtex>\bigvee\limits_{\beta_l = 1} y_{il}</mathtex>, где <mathtex>y_{il}</mathtex> - выдал ли дешифратор "1" на <mathtex>l</mathtex>-м выходе <mathtex>i</mathtex>-й полосы.

Число элементов <mathtex>L_B \leq (s - 1) \cdot (t(1) + t(2) + ... + t(p)) < sp \cdot 2^{s}</mathtex>* '''Блок C''' - схемная реализация всех <mathtex>f(x_1, x_2, ..., x_k, \sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_n)</mathtex>.

Число элементов <mathtex>L_C \sim p \cdot 2^{n - k} = \frac{2^n}{s}</mathtex>* '''Блок D''' - мультиплексор, получающий на вход все <mathtex>f(x_1, x_2, ..., x_k, \sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_n)</mathtex> и параметры функции <mathtex>x_{k + 1}, x_{k + 2}, ..., x_n</mathtex> в качестве двоичного представления числа.

Число элементов <mathtex>L_D \sim 2^{n - k}</mathtex>

Положим <mathtex>s = [n - 2\log_2 n]</mathtex>; <mathtex>k = [\log_2 n]</mathtex>. Тогда* <mathtex>L_A \sim 2^{\log_2 n} \lesssim \frac{2^n}{n}</mathtex>* <mathtex>L_B < sp \cdot 2^s = 2^{k + s} = \frac{2^n}{n}</mathtex>* <mathtex>L_C \sim \frac{2^n}{s} \sim \frac{2^n}{n}</mathtex>* <mathtex>L_D \sim 2^{n - k} = \frac{2^n}{n}</mathtex>

Итого, имеем схему с итоговым числом элементов <mathtex>\sim \frac{2^n}{n}</mathtex>, откуда следует, что <mathtex>size_B (f) \lesssim \frac{2^n}{n}</mathtex>, '''ч.т.д.'''