75
правок
Изменения
→Доказательство: оформил более аккуратно
В качестве доказательства ниже будет предложен вариант такой схемы для произвольной функции <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> можно реализовать как <tex>\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>.
Положим <tex>s = [n - 2\log_2 n]</tex>; <tex>k = [\log_2 n]</tex>. Тогда
* <tex>L_A \sim 2^{\log_2 n} k \lesssim \frac{2^n}{n}</tex>* <tex>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>L_C \sim p \cdot 2^{n - k} = \frac{2^n}{s} \sim \frac{2^n}{n}</tex>
* <tex>L_D \sim 2^{n - k} = \frac{2^n}{n}</tex>
