75
правок
Изменения
м
повысил читаемость формул
== Разделение на полосы ==
Разделим таблицу на горизонтальные полосы шириной <tex>s</tex> (последняя полоса, возможно, будет короче остальных; её длину обозначим <tex>s'</tex>). Пронумеруем полосы сверху вниз от 1 до <tex>p=\left\lceil\frac{2^k}{s}\right\rceil</tex>.
Рассмотрим независимо некоторую полосу. Среди её столбцов при небольшом <tex>s</tex> будет много повторений, поэтому введём понятие '''''сорта''''' столбца.
=== Вывод исходной функции для фиксированной части параметров ===
Поскольку изначальный столбец <tex>(\sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_{n})</tex> складывается из столбцов соответствующих сортов в полосах,
<texdpi="145">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)</tex>,
где <tex>j_i</tex> {{---}} номер сорта столбца полосы <tex>i</tex>, являющегося соответствующей частью столбца <tex>(\sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_{n})</tex>.
В качестве доказательства ниже будет предложен вариант такой схемы для произвольной функции <tex>f(x_1, x_2, ..., x_n)</tex> (представление Лупанова). Для удобства поделим схему на блоки:
* '''Блок A''' {{---}} дешифратор, которому на вход подали 1 и <tex>(x_1, x_2, ..., x_k)</tex> в качестве двоичного представления числа.
* '''Блок B''' {{---}} схемная реализация всех <tex>g_{ij}</tex>. Функцию <tex>g_{ij}</tex> можно реализовать как <texdpi="145">\bigvee\limits_{\beta_l = 1} y_{il}</tex>, где <tex>y_{il}</tex> {{---}} выдал ли дешифратор "1" на <tex>l</tex>-м выходе <tex>i</tex>-й полосы.
* '''Блок C''' {{---}} схемная реализация всех <tex>f(x_1, x_2, ..., x_k, \sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_n)</tex>.
* '''Блок D''' {{---}} мультиплексор, получающий на вход все <tex>f(x_1, x_2, ..., x_k, \sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_n)</tex> и параметры функции <tex>x_{k + 1}, x_{k + 2}, ..., x_n</tex> в качестве двоичного представления числа. '''''Результат работы схемы''''' {{---}} вывод мультиплексора.
Положим <tex>s = [n - 2\log_2 n]</tex>; <tex>k = [\log_2 n]</tex>. Тогда число элементов в блоках
* <texdpi="145">L_A \sim 2^k \lesssim \frac{2^n}{n}</tex>* <texdpi="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>* <texdpi="145">L_C \sim p \cdot 2^{n - k} = \frac{2^n}{s} \sim \frac{2^n}{n}</tex>* <texdpi="145">L_D \sim 2^{n - k} = \frac{2^n}{n}</tex>
Итого, имеем схему с итоговым числом элементов <tex>\sim \frac{2^n}{n}</tex>, откуда следует, что <tex>size_B (f) \lesssim \frac{2^n}{n}</tex>, '''''ч.т.д.'''''
